안녕하세요! daily_D 입니다! 👩🏻💻 Show LRU 란?LRU(Least Recently Used)는 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식입니다. 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 💡 Hit Ratio & Miss Ratio LRU 의 구현하기1. 아까 말했듯이 LRU는 Doubly Linked List 로 구현되기때문에 두 개의 class 를 만들어야합니다! 첫번째는 Node class 로, 각 node 는 '자신의 정보를 저장할 data' 와 '이전 node 를 저장할 prev', '다음 node 를 저장할 next' 가 필요합니다.
두번째는 DoublyLinkedList class 로, head node 와 tail node 가 있어야하며 서로 연결되어있어야합니다.
※ 여기서 매개변수로 들어온 cacheSize는 LRU를 구현하기위해 필요한 변수입니다! 2. 이제 두개의 클래스를 모두 만들었다면! LRU 를 구현하는데 필요한 함수들을 만들차례입니다! 1) LRU 첫번째로 LRU 함수는 새롭게 넣을 data 를 매개변수로 받아
두번째로
cacheHit 함수는 캐시에 data 가 존재하는 경우이므로,
마지막으로 cacheMiss 함수는 캐시에 data 가 존재하지 않는 경우이므로,
이제 우리가 만든 코드로 [1, 2, 1, 3, 4, 1, 5, 4] 예시를 확인해볼까요?
위의 코드를 추가한 후 print 주석들을 해제하면 아래와 같이 우리가 원하는 결과가 출력됩니다!! |