📒LRU 알고리즘

LRU 알고리즘이란?

LRU(Least Recently Used)는 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식이다.

LRU 원리

LRU를 구현하기 위해서는 가장 오랫동안 참조 되지 않은 페이지를 찾아서 없애는 과정이 필요하다.

예시와 함께 정리해보자.
[1,2,1,4,3,1,5,4] 일 경우

Head에 가까울수록 최신
Tail에 가까울수록 오래된 페이지이다.
Catch size는 3이다.

• 데이터가 새로 들어오면 Head 바로 뒤에 추가 해준다.
• 데이터가 catch size를 넘으면 tail과 가장 가까운(가장 오랫동안 참조되지 않은 페이지)데이터가 삭제된다.
• catch hit 발생 시 데이터를 head뒤에 추가해주고 참조된 기존 데이터는 삭제해준다.

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