LRU 알고리즘

LRU 알고리즘 이란?

LRU 알고리즘은 Least Recently Used의 약자로 기억장치 바깥으로 내보내야할 페이지를 선정할 때 가장 오랜 기간 사용되지 않았던 페이지부터 교체하는 페이지 교체 알고리즘 입니다. 이는 일반적으로 가장 오랫동안 액세스 되지 않았던 페이지는 앞으로도 액세스 되지 않을 확률이 제일 크다는 것에 기반한 것이다.

이 규칙은, 일반적으로 가장 오랫동안 액세스되지 않았던 페이지는, 조만 간에도 액세스되지 않을 확률이 가장 크다는 시간적 집약성에 기반을 두고 있다. LRU는 Belady의 변이를 나타내지 않는다.


오라클에서는 두가지 모드의 LRU 알고리즘이 있다.

MRU (Most Recently Used)
LRU (Least Recently Used)


1. standard mode
   가장 최근에 사용된 buffer의 헤더가  MRU end로 들어감.
  
2. modified mode
    Index로 읽어진 buffer의 헤더는 MRU end로 들어가고, full table 스캔에 의해서 사용된 buffer의 헤더는 LRU end로 들어간다.

단점 : 서버프로세스가 full table scan을 하면 그 때 사용된 buffer는 LRU list의 LRU end로 들어감 프리버퍼 찾을 때 금방 재이용된다.
        full table 스캔이라도 MRU end로 넣는다. -> 쓸데없는 io를 줄인다.


참고 : http://www.juliandyke.com/Presentations/Presentations.html#LogicalIO