Virtual Memory (가상 메모리) - 2

---

Page Replacement

정의

• 실제 메모리에 Free Frame이 존재하지 않을 시 해결책
• 실제 메모리에 있는 Frame을 지금 당장 실행해야 할 Page에게 넘겨줄 Victim Frame을 찾는 과정입니다.

1. First-In-First-Out (FIFO) Algorithm

가장 오래된 Frame을 Victim Frame으로 지정합니다.

• 실제 메모리에 올라온 지 (Frame을 차지한지) 가장 오래된 Frame을 선택하는 알고리즘입니다.
• 위 그림에서, 2번 Page에 대한 Frame 요청이 들어왔을 때, 가장 오래된 7번 Page의 Frame이 Victim Frame으로 선택되는 것을 보실 수 있습니다.

• 하지만 FIFO 알고리즘은 Frame 수가 증가하여도, Page Fault가 더 많이 발생하는 모순을 일으키게 됩니다.
  (Frame이 많다면 Page Fault가 적어야 한다.)

2. Optimal Algorithm

오랜 기간동안 사용되지 않을 Frame을 Victim Frame으로 지정합니다.

• 위 그림에서, 2번 Page에 대한 Frame 요청이 들어왔을 때, 가장 오랫동안 사용되지 않았을 7번 Page의 Frame이 Victim Frame으로 선택되는 것을 보실 수 있습니다.

• "사용되지 않을" Frame을 예측하여야 한다.
• 예측이 필요한 알고리즘이기 때문에 이론상으로만 존재한다.
• 다른 알고리즘들의 성능 비교를 위해 사용됩니다.

3. Least Recently Used (LRU) Algorithm

가장 오랫동안 사용되지 않은 Page의 Frame을 Victim Frame으로 지정합니다.
(각 Page의 마지막 사용 time으로 결정됩니다.)

• 위 그림에서, 6번째 실행 순서인 3번 Page에 대한 Frame 요청이 들어왔을 때, 0번 Page에 대한 Frame은 바로 직전에 사용되었기 때문에, 사용된지 가장 오래된 1번 Page에 대한 Frame을 Victim Frame으로 선택되는 것을 보실 수 있습니다.

구현 방법

1. 해당 Page가 실행될 때, 실행된 시간을 Page Table의 해당 부분에 저장하는 방법
2. 실행되는 순서를 Stack으로 쌓아서 관리하는 방법. Stack의 순서는 위에서 아래로 최근에서 과거 순이 됩니다.

• 이러한 구현 방법들은 하드웨어적인 지원을 필요로 합니다.
• 하드웨어적인 지원을 필요로 하지 않는 개선된 LRU Algorithm이 존재 합니다.

4. LRU Approximation Algorithm

LRU Algorithm을 H/W의 지원 없이, Reference Bit를 이용하여 구현한 알고리즘 입니다.

Reference Bit

• 각 Page에 대한 Bit를 0으로 초기화 합니다.
• Page가 Reference될 때, 해당 Bit를 1로 설정합니다.
• Victim Frame이 필요할 때, Reference Bit가 0인 Page가 차지하고 있는 Frame으로 지정합니다.
  (Reference Bit가 0인 Page들이 다수 존재 시, FIFO 알고리즘을 이용하여 Victim Frame을 지정)

LRU Approximation Algorithm에는 위 방법 외에, 여러 가지 방법이 존재합니다.

4-1. Additional-Reference Bits Algorithm

• Page Table내 각각의 Pagedp 8 bit 크기의 참조 Bit가 존재합니다.
• 일정 시간의 간격마다 Reference되었던 Page들의 Bit들을 오른쪽으로 Shift하는 연산을 합니다.
• Victim Frame이 필요할 때, 가장 작은 Bit값을 가진 Page가 차지하고 있는 Frame으로 지정합니다.
  (가장 작은 Bit값을 가진 Page들이 다수 존재 시, FIFO 알고리즘을 이용하여 Victim Frame을 지정)

4-2. Second Chance (Clock) Algorithm

• 말 그대로 한번의 기회를 더 주는 알고리즘 입니다.
• 기존 FIFO Algorithm 방식 + Reference Bit
• Reference Bit가 0일 시, Victim Frame으로 선정됩니다.
• Reference Bit가 1일 시,
  • Reference Bit를 0으로 설정 후, 해당 Page를 우선 Memory에 유지합니다.
  • 0으로 설정 되었기 때문에, FIFO Algorithm에 의해 다음번엔 Victim Frame으로 선정됩니다.

4-3. Enhanced Second Chance Algorithm

• Reference Bit와 Modify Bit를 이용하여 구현한 알고리즘 입니다.
• Modify Bit : 해당 부분의 값이 변하게 되면 Modify Bit의 값을 1로 변형해줍니다.

• Reference Bit와 Modify Bit가 둘 다 0 이라는 뜻은 최근에 Reference 되지 않았고, 값의 변화가 없으므로, 다시 선택될 가능성이 낮다는 뜻입니다.
  즉, 해당 Page가 차지하고 있는 Frame은 Victim Frame으로 적절하다는 것을 의미합니다.
• 하지만, 모든 Page Table을 전부 뒤져야 한다는 단점이 존재합니다.

5. Counting Algorithms

Reference된 횟수를 Page Table의 각 Page에 저장을 하여 횟수를 통해 Victim Page를 결정하는 알고리즘 입니다.

5-1. Least Frequently Used (LFU) Algorithm

• 횟수가 가장 적은 Page를 Victim Page로 선택합니다.
• Reference 횟수가 적다는 것은 앞으로도 선택이 안될 것이다라고 판단합니다.

5-2. Most Frequently Used (MFU) Algorithm

• 횟수가 가장 많은 Page를 Victim Page로 선택합니다.
• Reference 횟수가 많다는 것은 지금까지 많이 Reference 했으니, 앞으로는 Reference 하지 않을 것이다라고 판단합니다.

6. Page Buffering Algorithm

Page Fault시 Victim Frame을 찾는 것 대신, 운영체제가 Pool of Free Frames을 항상 유지합니다.

다음 장에서는 프로세스에게 Frame을 할당해주는 방법과 Page Replacement시 생기는 문제점에 관하여 다룰 예정입니다.