(68) LRU Approximation Page Replacement

### LRU Approximation Page Replacement ###

< Reference bit >

: 대상 page가 invalid or valid를 나타내주는 정보

​

: page reference bit는 해당 page가 reference(valid) 될 때마다 (page의 임의의 byte에 대한 read or write) H/W에 의해 설정된다.

​

: reference bit는 page table의 각 항목과 관련이 있다.

​

​

< Additional reference bits algorithm >

: regular intervals(일정한 시간 간격)으로 reference bit를 기록하여 추가 ordering information을 얻을 수 있다.

(각 page 최근 접근 상황, 대략적 page간의 접근 시점 순서 정렬 정보를 얻을 수 있다)

 

=> regular intervals으로 time interrupt가 발생하여 OS가 reference bit를 8bit register값에

즉 1개의 high-order bit(most significant bit)에 기록한다.

 

==>> 해당 bit값이 1이면 가장 최근 기록 시점에 해당 page접근 요청을 했다는 것을 알 수 있다.

​

​

: 0000 0000 -> page가 8time periods 동안 사용되지 않았다.

: 1111 1111 -> page가 각 period에 한 번 이상 사용된다.

: 1100 0100의 page가 0111 0111의 page보다 최근에 사용되었다.(0111 0111이 victim frame으로 선정된다.)

=> 순서대로 1234 5678번째이다.

​

​

< Second chance algorithm > == LRU Approximation algorithm

: page에 머무른 시간이 오래된 것을 victim으로 결정 but 최근에 계속 접근이 되고 있는 page이면 memory에 남아 있을 기회를 준다.

​

: basic algorithm은 FIFO replacement algorithm이다.

​

: second-chance algorithm(가끔 clock algorithm이라고도 불린다.)을 구현하기 위해 circular queue를 사용한다.

 

 

출처: Operating System Concepts 10th Ed (John Wiley & Sons, Inc. 2018) ​