LRU(Least Recently Used) 페이지 교체 알고리즘

LRU(Least Recently Used)

• 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식
• 가장 오랫동안 참조되지 않은 페이지는 앞으로도 사용될 가능성이 낮다는 가정하에 생겨난 알고리즘

 

원리

• 캐시가 꽉 찼을 경우 가장 오랫동안 참조되지 않은 페이지를 찾아서 없애는 과정이 필요하다.
• 1. 페이지를 새로 참조할 때마다 연결리스트의 맨 앞에 페이지번호를 추가한다.
• 2. 그렇게 진행하다보면 맨 뒤에 있는 페이지번호가 가장 오랫동안 참조되지 않은 페이지 번호가 된다.
  
  

용어

• Cache : 컴퓨터 과학에서 데이터나 값을 미리 복사해 놓는 임시 장소
• Cache Hit: CPU가 참조하고자 하는 메모리가 캐시안에 존재하는 경우
• Cache Miss: CPU가 참조하고자 하는 메모리가 캐시안에 존재하지 않는 경우

 

관련문제 -  https://c0mmedes.tistory.com/74