LRU(Least Recently Used) 알아보기

LRU 알고리즘은 페이지 교체 알고리즘 종류 중의 하나이다. 우선 페이지 교체 알고리즘이란 무엇인지 살펴보자.

0. 페이지 교체 알고리즘

페이지 교체 알고리즘은 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다.즉 가상기억장치를 모두 같은 크기의 블록으로 편성하여 운용하는 기법이다. 이때의 일정한 크기를 가진 블록을 페이지라고 한다.

페이지 교체 알고리즘은 온라인 알고리즘의 일종이다.

페이징 기법?
컴퓨터가 메인 메모리에서 사용하기 위해 2차 기억 장치로부터 데이터를 저장하고 검색하는 메모리 관리 기법이다. -위키백과-

온라인 알고리즘?
전산학에서 온라인 알고리즘이란 시작할 때 모든 입력 정보를 가지고 있지 않고, 입력을 차례로 받아들이면서 처리하는 알고리즘. 온라인 알고리즘은 기계 학습 분야에서 많이 연구된다. -위키백과-

페이지 교체 알고리즘의 예로 FIFO, LFU, LRU 알고리즘 등이 있다.

• FIFO: 페이지가 주기억장치에 적재된 시간을 기준으로 교체될 페이지를 선정하는 기법
• LFU: 가장 적은 횟수를 참조하는 페이지를 교체
• LRU: 가장 오랫동안 참조되지 않은 페이지를 교체

1. LRU

주로 캐시에서 메모리를 다루기 위해 사용된다. 

1.1 원리

LRU를 구현하기 위해서는 캐시가 가득 찼을 때, 가장 오랫동안 참조되지 않은 페이지를 찾아서 없애는 과정이 필요하다. 페이지를 새로 참조할 때마다 연결리스트의 맨 앞에 페이지 번호를 추가한다. 그러면 맨 뒤에 있는 페이지 번호가 가장 오랫동안 참조되지 않은 페이지 번호가 된다. 

 

1.2  구현

LRU의 구현은 Double Linked List를 통해 이루어진다. Head에 가까운 데이터일수록 최근에 사용된 데이터이고, Tail에 가까울수록 오랫동안 사용되지 않은 데이터로 간주한다. 따라서 새로운 데이터를 삽입할 때, Tail 값을 가장 먼저 삭제시키고, Head에 데이터를 삽입하도록 하여 캐시 교체 시간 복잡도를 O(1)로 갖게 한다.

그리고 만약 캐시에 적재된 데이터를 사용한 경우, 해당 데이터를 Head로 옮겨 가장 최근에 사용된 값임을 명시한다.

이미지 출처:  https://dailylifeofdeveloper.tistory.com/355

1.2.1 코드로 살펴보는 LRU 구현

코드 구현 부분은 이 블로그를 참조하였다.

LRU는 Double Linked List로 구현하기 때문에 두 개의 class를 만들어야 한다.

 

첫 번째는 Node class로, 각 node는 '자신의 정보를 저장할 data'와 '이전 node를 저장할 prev', '다음 node 를 저장할 next'가 필요하다. 

class Node:
    def __init__(self, data, prev=None, next=None):
        self.data = data
        self.prev = prev
        self.next = next

두 번째는 DoubleLinkedList class로, head node와 tail node가 있어야 하며, 서로 연결되어 있어야 한다.

class DoubleLinkedList:
    def __init__(self, cacheSize):
        self.cacheSize = cacheSize
        self.head = Node("")
        self.tail = Node("")
        self.head.next = self.tail
        self.tail.prev = self.head

두 개의 클래스를 만들었다면, LRU를 구현하는데 필요한 함수를 만들 차례이다. 크게 3 가지의  함수가 필요하다.

1. LRU
2. cacheHit: CPU가 참조하고자 하는 메모리가 캐시에 존재하고 있는 경우
3. cacheMiss: CPU가 참조하고자 하는 메모리가 캐시에 존재하지 않는 경우

첫 번째 LRU 함수는 새롭게 넣을 data를 매개 변수로 받아, 캐시에 존재하는 data면 cacheHit, 캐시에 존재하지 않는 data면 cacheMiss를 실행한다.

def LRU(self, data):
    node = self.head.next
    while(node.data):
        if node.data == data:
            self.cacheHit(node, data)
            return
        node = node.next
    self.cacheMiss(data)

두 번째로 cacheHit 함수는 캐시에 data가 존재하는 경우이므로, 원래의 위치에서 node를 삭제하고 head 바로 뒤에 원소를 추가한다.

# 원소 맨앞으로 이동
def cacheHit(self, node, data):
    self.removeNode(node)
    self.addFront(data)
 
# node 삭제
def removeNode(self, node):
    node.prev.next, node.next.prev = node.next, node.prev
    
# head 의 바로 뒤에 원소 넣기
def addFront(self, data):
    newNode = Node(data)
    self.head.next.prev = newNode
    newNode.next = self.head.next
    self.head.next = newNode
    newNode.prev = self.head

마지막으로 cacheMiss 함수는 캐시에 data가 존재하지 않는 경우이므로, 무조건 list의 맨 앞에 data를 추가하고 만약 DoubleLinkedList의 초기매개변수로 들어왔던 cacheSize 보다 원소의 개수가 많아지면 tail에 가까운 원소를 제거한다.

# 원소의 맨앞에 추가 (cacheSize 보다 커지면 tail에 가까운 노드 삭제)
def cacheMiss(self, data):
    self.addFront(data)
    if self.totalLen() > self.cacheSize:
        self.removeTail()
        
# linked list 의 총 길이 반환
def totalLen(self):
    answer = 0
    node = self.head.next
    while(node.data):
        answer += 1
        node = node.next
    return answer
        
# tail 에 가장 가까운 원소 삭제
def removeTail(self):
    self.tail.prev.prev.next = self.tail
    self.tail.prev = self.tail.prev.prev

최종코드는 다음과 같다

class Node:
    def __init__(self, data, prev=None, next=None):
        self.data = data
        self.prev = prev
        self.next = next
    
class DoublyLinkedList:
    def __init__(self, cacheSize):
        self.cacheSize = cacheSize
        self.head = Node("")
        self.tail = Node("")
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def LRU(self, data):
        print("[Put " + data + "]", end=" ")
        node = self.head.next
        while(node.data):
            if node.data == data:
                self.cacheHit(node, data)
                return
            node = node.next
        self.cacheMiss(data)
    
    # 원소 맨앞으로 이동
    def cacheHit(self, node, data):
        self.removeNode(node)
        self.addFront(data)
        print("[Hit ]", end=" ")
        self.printAll()
    
    # node 삭제
    def removeNode(self, node):
        node.prev.next, node.next.prev = node.next, node.prev
       
    # head 의 바로 뒤에 원소 넣기
    def addFront(self, data):
        newNode = Node(data)
        self.head.next.prev = newNode
        newNode.next = self.head.next
        self.head.next = newNode
        newNode.prev = self.head
        
    # 원소의 맨앞에 추가 (cacheSize 보다 커지면 tail에 가까운 노드 삭제)
    def cacheMiss(self, data):
        self.addFront(data)
        if self.totalLen() > self.cacheSize:
            self.removeTail()
        print("[Miss]", end=" ")
        self.printAll()
        
    # linked list 의 총 길이 반환
    def totalLen(self):
        answer = 0
        node = self.head.next
        while(node.data):
            answer += 1
            node = node.next
        return answer
        
    # tail 에 가장 가까운 원소 삭제
    def removeTail(self):
        self.tail.prev.prev.next = self.tail
        self.tail.prev = self.tail.prev.prev
      
    # For Debug  
    # head 부터 tail 까지 순환하면서 date 전부 출력
    def printAll(self):
        node = self.head.next
        while(node.data):
            print(node.data, end="")
            node = node.next
            if (node.data):
                print(" -> ", end="")
        print()

테스트를 해보자

test = DoublyLinkedList(3)
inputArray = ["1", "2", "1", "3", "4", "1", "5", "4"]
for input in inputArray:
    test.LRU(input)

다음과 같은 결과를 얻을 수 있다.

---

 

참고

https://ko.wikipedia.org/wiki/%ED%8E%98%EC%9D%B4%EC%A7%80_%EA%B5%90%EC%B2%B4_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

페이지 교체 알고리즘 - 위키백과, 우리 모두의 백과사전

https://j2wooooo.tistory.com/121

LRU 알고리즘 (Least Recently Used Algorithm)

https://dailylifeofdeveloper.tistory.com/355

LRU 알고리즘 (Least Recentely Used) 개념 및 구현방법

https://velog.io/@haero_kim/LRU-Cache-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0