[ORACLE] LRU 알고리즘

1. LRU 알고리즘 

- 기본적으로 오라클은 메모리에서의 Queuing 알고리즘으로써 LRU(Least Recently Used) 리스트를 사용한다. 사용빈도가 높은 버퍼일수록 더 오래 데이터베이스 버퍼 캐시 내에 존재할 수 있도록 관리하는 알고리즘이다. 반대로 자주 사용하지 않는 버퍼들의 경우에는 임의의 시점에서 데이터 버퍼 캐시 밖으로 나가야 한다. 

 

* LRU 리스트 : 더티 버퍼를 제외한 모든 버퍼를 관리

* Dirty 리스트 : 같은 데이터 블록에 대한 데이터베이스 버퍼 캐시에 저장된 버퍼 이미지와 데이터 파일에 저장되어 있는 물리적인 블록 이미지가 서로 다른 버퍼들을 관리하는 리스트

 

종 류	내 용
LRU 리스트 (대체 리스트)	메인 리스트 : 사용된 버퍼들의 리스트, 핫 영역과 콜드 영역으로 구분하여 관리
	보조 리스트 : 미 사용된 버퍼들이나 DBWR에 의해 기록된 버퍼들의 리스트를 관리
LRUW 리스트	메인 리스트 : 변경된 버퍼들의 리스트
	보조 리스트 : Dirty buffer 중 현재 DBWR에 의해 기록중인 버퍼들의 리스트

 

 

2. LRU 메인 리스트의 구조

* LRU 리스트의 메인 리스트는 크게 핫 영역과 콜드 영역으로 나누어진다. 

* 자주 사용되는 블록들은 핫 영역에서 머물 가능성이 크며 자주 사용되지 않는 블록들은  콜드 영역에 머물 가능성이 크다. 

* 개별 버퍼마다 터치 카운트를 사용하여 관리하는데 프로세스에 의하여 스캔이 이루어질 때마다 터치 카운트가 1씩 증가하게 된다. 

* LRU 끝에 있는 버퍼의 터치 카운트가 1 이하면서 프리 상태일 경우 프리 버퍼로 사용되고 터치 카운트가 2 이상인 블록은 핫 영역의 머리 부분(Head of hot end)으로 옮겨지고 터치 카운트는 0으로 초기화된다. 

 

- 사용자가 요청하는 데이터를 디스크에서 읽어 들이고 이들을 데이터베이스 버퍼 캐시로 가지고 올라가게 되면 다음과 같은 과정이 진행된다. 우선 LRU의 보조 리스트에서 프리 버퍼를 제일 먼저 확보하고자 한다. 이때 프리 버퍼의 수가 충분하면 바로 사용하지만 만약 프리 버퍼가 부족한 경우에는 메인 리스트의 콜드 영역 끝부터 프리 버퍼를 찾게 된다. LRUW 리스트(메인 리스트)에 존재하는 더티 버퍼들은 임의의 조건이 만족되는 경우 DBWR에 의해 데이터 파일로 내려 적히게 되며 이후 이들은 프리 버퍼로 전환되면서 LRU의 보조 리스트로 등록된다.