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

안녕하세요! daily_D 입니다! 👩🏻‍💻
오늘은 페이지 교체 알고리즘 중에서 LRU에 대해서 공부해볼까요?!

---

LRU 란?

LRU(Least Recently Used)는 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식입니다.
LRU 는 사용된지 가장 오래된 페이지는 앞으로도 사용될 확률이 낮다는 가설에 의해 만들어진 알고리즘입니다.

 

LRU 의 원리

LRU 를 구현하기 위해서는 캐시가 가득 찼을때, 가장 오랫동안 참조되지 않은 페이지를 찾아서 없애는 과정이 필요합니다.

페이지를 새로 참조할 때마다 연결리스트의 맨 앞에 페이지번호를 추가합니다.
그러면 맨 뒤에 있는 페이지번호가 가장 오랫동안 참조되지 않은 페이지번호가 되겠죠?

따라서 LRU의 원리는

캐시의 크기가 3인데 이미 3개의 페이지가 캐시에 들어있다면 맨 뒤에 있는 페이지번호 node 를 지우고 새로운 페이지번호 node 를 앞에 연결해주는 방식입니다.

LRU를 구현할때는 Doubly Linked List 를 사용하고 head 에 가까운 node 일수록 가장 최근에 참조된 페이지, tail 에 가까운 node 일수록 가장 오랫동안 참조되지 않는 페이지입니다. LRU 의 개념에 따라 cache size 를 넘어서게 된다면 tail 에 가까운 페이지가 먼저 삭제되도록 합니다. 

[1, 2, 1, 3, 4, 1, 5, 4] 예시를 그림으로 정리해보면 아래와 같습니다!

💡 Cache Hit & Cache Miss
Cache Hit : CPU 가 참조하고자 하는 메모리가 캐시에 존재하고 있을 경우
Cache Miss : CPU 가 참조하고자 하는 메모리가 캐시에 존재하지 않을 경우

💡 Hit Ratio & Miss Ratio
Hit Ratio : Cache Hit / (Cache Hit + Cache Miss)
Miss Ratio : Cache Miss / (Cache Hit + Cache Miss)
※ 위의 예시 : Hit Ratio = 3/8, Miss Ratio = 5/8 

 

LRU 의 구현하기

1. 아까 말했듯이 LRU는 Doubly 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

 

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

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

※ 여기서 매개변수로 들어온 cacheSize는 LRU를 구현하기위해 필요한 변수입니다!

 

2. 이제 두개의 클래스를 모두 만들었다면! LRU 를 구현하는데 필요한 함수들을 만들차례입니다!
우리는 크게 3 가지의 함수가 필요합니다.

1) LRU
2) cacheHit
3) cacheMiss

 

첫번째로 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 를 추가하고 만약 doublyLinkedList 의 초기매개변수로 들어왔던 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()

 

이제 우리가 만든 코드로 [1, 2, 1, 3, 4, 1, 5, 4] 예시를 확인해볼까요?

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

 

위의 코드를 추가한 후 print 주석들을 해제하면 아래와 같이 우리가 원하는 결과가 출력됩니다!!