LRU 알고리즘 파헤치기

LRU

페이지 교체 알고리즘 중에 하나로, Least Recently Used의 약자입니다. 즉, 가장 최근에 사용되지 않았던 것을 찾는 알고리즘입니다. 사실 페이지 교체를 위한 Optimal solution(가장 오랫동안 사용되지 않을 것을 선택하는 것)은 이론적인 방법이기 때문에 그것을 위한 근사 방법 중 하나입니다. 페이지 교체와 관련된 내용은 추후에 다뤄보고 여기서는 LRU에 대해서만 이야기하고자 합니다. LRU를 JAVA를 이용해 구현한 내용은 이 게시글을 참조하세요.

 

LRU page-replacement algorithm

 

 

Implementing LRU

LRU 알고리즘을 구현하기 위해서는 다음과 같은 방식이 있습니다.

 

Counter

• 가장 단순하게 떠올릴 수 있는 방법 중 하나로, `clock register`를 이용하는 방식입니다. (모든 메모리 참조마다 클락이 증가)
• 페이지가 참조될 때 마다 페이지 테이블의 시간 필드에 복사합니다.
• 페이지를 교체할 때 시간 필드에서 가장 작은 값을 찾아 그것을 Victim으로 선정합니다.

하지만, 이 방식은 full Scan 해야 한다는 단점을 가지고 있고, clock register의 오버플로우를 고려해야 합니다.

 

Stack

• 페이지 번호를 관리하는 Stack을 `Doubly Linked List`를 이용해 관리하는 방식입니다.
• 가장 최근에 사용되는 페이지 번호는 Stack의 상단에 위치할 것이기 때문에, OS는 하단에 위치한 페이지 번호를 Victim으로 선정하면 됩니다.
• 교체에 대한 검색이 없습니다.

이 방식은 업데이트 비용의 단점이 있습니다.

 

Use of a stack to record the most recent page references.

 

LRU Approximation Algorithm

사실, 위 방식에 대해 하드웨어 지원을 제공하는 컴퓨터 시스템은 거의 없습니다.

많은 시스템에 있는 `reference bit`를 이용하는 방법이 있습니다.

 

Reference bit

• OS에 의해 모든 비트가 0으로 초기화됩니다.
• HW에 의해 페이지가 참조될 때 1로 변경됩니다.
• 하지만, 순서를 알지 못합니다.
• 이 bit를 이용해 다음의 알고리즘이 개발되었습니다.

 

Additional-Reference-Bits Algorithm

• 페이지 별 `8 bit register`를 이용합니다.
• 주기적인 간격으로 OS는 각 페이지의 `reference bit`를 고차 비트로 Copy 하고, `shift right`합니다.
• 가장 작은 숫자가 LRU page입니다.

 

Second-chance algorithm

• `Reference bit`가 0인 페이지를 victim으로 선택합니다.
• 만약 1이라면 0으로 바꿉니다. 이 방식이 두 번째 기회를 주는 것입니다.
• circular queue로 구현할 수 있습니다.

Example of second-chance alghrothim.

 

Enhanced Second-chance Algorithm

• Reference bit 뿐만 아니라, `Modify bit`도 이용합니다.

• (0,0) : old, not modified (BEST)
• (0,1) : old, but modified
• (1,0) : recent, but clean
• (1,1) : recent, modified

Victim을 선정하기 위해 circular queue 여러 번 순회해야 할 수도 있습니다.

 

참조

• 공룡책
• https://velog.io/@huttzza/OS-Ch10-Virtual-Memory-2