안녕하세요! 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 주석들을 해제하면 아래와 같이 우리가 원하는 결과가 출력됩니다!!