LRU - 페이지 교체 알고리즘

Least Recently Used - LRU  

- 최근에 사용되지 않은 

- 페이지에서 최근에 사용되지 않은것을 제거한다.
- 가장 오랫동안 사용되지 않았던 데이터는 앞으로도 사용될 확률이 적다.
- 1번째 방법 : 페이지에 저장된 데이터가 언제 저장되었는지 알 수 있는 부분을 구현하여 제일 오랫동안 사용되지 않은 데이터 제거하는 방법

- 2번째 방법 : 페이지에 데이터 큐형식으로 저장하는 방식. 페이지에 데이터가 존재한다면 데이터를 페이지 내에 제거하고 가장위로 올리고 만약 데이터가 존재하지 않는다면 바로 입력하여 맨 아래에 있는 데이터를 삭제하는 방법

LRU 알고리즘 페이지 상태 변환 과정

다음과 같이 페이지 크기가 3개일 때 7번에서 3은 사용되었기 때문에 8 번에서 2가 페이지내에 존재하지 않아도 2번은 3번을 대체하지 않고 가장 오랫동안 쓰이지않은 4가 삭제되고 2가 들어간다.

cache hit  : 캐시 적중률 (Cache hit rate)만약 원하는 정보가 캐시 메모리에 있을때 적중(Hit)되었다고 하고 ,없다면 실패했다고 한다. 적중률 = 적중횟수/ 총 접근횟수 이고 컴퓨터의 성능을 나타내는 척도로 사용된다.

cache miss :  해당 데이터가 없어서 DRAM에서 가져와야 한다면 '캐시 부적중(cache miss)'라 부른다