(67) Least Recently Used Algorithm

### Least Recently Used Algorithm ###

< LRU page replacement >

: 최근에 사용하지 않은 page를 가장 먼저 내려 보내는 algorithm

​

: LRU에서는 가장 오랜 시간동안 사용되지 않은 page를 교체할 수 있다.

=> 미래는 알 수 없지만 과거는 알 수 있다. (page의 과거는 미래를 반영한다)

​

: Optimal(최적)은 가능하지 않지만 근사값은 가능하다

​

: FIFO는 page를 memory로 가져온 시간을 사용하고 OPT는 page를 사용하는 시간을 사용한다.

​

: 이것은 종종 page replacement algorithm으로 사용되며 좋은 것으로 간주된다.

​

: 주요 문제는 LRU교체를 구현하는 방법이다.

​

: 상당한 하드웨어 지원이 필요할 수 있다.

(physical memory에 언제 접근되어야 하는가 알 수 있어야 한다)

(counter, stack)

 

 

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

 

 

+

<H/W>

1.<Counters> - 시간

: 각 page-table entry(항목)과 time-of-use field를 연결하고 cpu에 logical clock or counter을 추가한다.

​

: clock은 모든 memory reference에 대해 증가한다.

=> time-of-use field를 봐야하기 때문에 overhead 발생 시킬 수 있다.

​

2.<Stack> - 순서

: page numbers을 쌓아 둔다.

​

: page reference 될때 마다 stack에서 제거되어 맨 위에 놓인다.

=> stack내 순서 변경이 overhead발생 시킬 수 있다.

 

 

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

(tail이 교체될 것이다.)

​

​

+(번외)

<Locality>

1. 공간적 locality: 어떤 memory부분을 요청하면 해당 영역과 비슷한 곳에서 memory요청을 한다.

2. 시간적 locality: 과거의 trend가 미래 trend를 반영한다.

​

​

​

​