LRU Implementation in more detail

Implementing LRU Algorithm

Counter implementation

• 모든 page table에는 counter가 있다
• page는 entry를 통해서 참조 되고, counter에 clock을 복사한다.
• clock은 memory에 참조가 일어날 때마다 증가한다.
• page가 replace 되야할 때, counter를 확인하여 어떤 page가 replace 될 지 결정한다.

Stack implementation

• doubly linked list 형식으로 page number를 stack으로 만든다.
• page가 참조 될 때마다 해당 page number를 stack의 top에 올려놓는다. 즉, top이 most recently used가 되고 bottom이 LRU가 된다.
• update하는데 비용이 늘어나기는 하지만 search가 필요가 없다는 장점이 든다.

---

LRU Approximation Algorithm 1

1. 각각의 page에 reference bit를 넣어준다.(초기값 0)
2. page가 참조되었을 때, hardware로 reference bit을 1로 만들어 준다.
3. Replace를 해야한다면 reference bit가 0인 값을 replace해준다.

위의 algorithm은 어떤 page를 참조했는지는 알 수 있으나, 순서는 알 수 없다.

 

Additional Reference Bits Algorithm (Reference Byte algorithm)

• reference bit를 8개 즉 1byte로 사용한다.
• Regular interval을 정하고 그 시간 동안 참조된 page를 기억한다.
• Regular interval이 끝날 때마다 기억한 정보를 바탕으로, 모든 page의 reference bit들을 right shift해주고 참조된 page는 1을 그렇지 않은 page에는 0을 넣어준다.
• 만약 page fault가 발생하면, reference bit가 가장 낮은 것을 LRU라고 여기고 replace시킨다.

Second Chance (Clock) Algorithm

• Circular list의 page는 memory에 load된다.
• page가 처음 load되면 reference bit를 1로 set한다.
• victim pointer가 가리키고 있는 page의 reference bit이 0이라면 replace를 진행한다.
• reference bit이 1이라면 0으로 바꿔주고 victim pointer가 clock order에 다음 순서의 page를 가르키게 한다.

example of Second Chance (Clock) Algorithm

여기서 6번째 e가 어떻게 삽입되는지 더 자세히 보자.

 

Enhanced Second Chance Algorithm

 

Enhanced Second Chance Algorithm은 reference와 modify bit(Dirty bit)을 동시에 고려한다.

 

Four classes

• (0,0) : niether recently used nor modified - best
• (0,1) : not recently used but modified
• (1,0) : recently used but clean
• (1,1) : recently used and modified

위 순으로 순위가 높은 것부터 replace를 실행한다.

이 방식은 queue를 여러 번 확인해야하는 것이 단점이다.