Page Replacement

물리 Memory에 위치한 Page를 Disk에 저장하고, 요구된 Page가 해당 Frame을 할당 받도록 하는 방법

Page Replacement 배경

Memory 과다 할당 상태 (Over Allocation of Memory)

• Multi Programming System에서 Memory 내에 위치한 User Process의 수가 증가함에 따라 발생
• 모든 User Process가 사용하는 Page 수보다 물리 Memory의 Frame수가 적은 상황

-> Page Fault 처리에 Page Replacement를 추가

Page Fault with Page Replacement

1. 디스크에서 요구된 Page의 위치를 찾음

2. 물리 Memory에서 Free Frame을 찾음

• Free Frame이 있다면 사용
• 없다면, Page Replacement Algorithm을 사용하여 교체할 Frame(Victim Frame)을 선택
• 교체할 Frame을 Disk에 저장하고, Page Table을 변경한다.

3. 요구된 Page를 2에서 선택된 Free Frame으로 읽어 들이고, 해당 Page Table을 적절하게 변경

4. User Process를 재시작

Page Replacement 도식

Page Replacement 고려사항

• 각각의 User Process에게 어떻게 Frame을 분배해 줄 것인가?
  -> Frame Allocation Algorithm

• Page 교체가 필요할 때 어떻게 교체할 Page를 고를 것인가?
  -> Page Replacement Algorithm

위 Algorithm들은 모두 Page 교체에 의한 I/O 작업 수행 횟수를 최대한 줄이려는 목적을 갖고 있으며, 적합한 Algorithm의 사용은 System의 성능을 크게 좌우하는 요소임
-> I/O 작업은 매우 큰 비용을 사용하기 때문

Page Replacement Algorithm

• 가장 낮은 Page Fault 발생 빈도를 가진 Algorithm
• 가장 낮은 I/O 작업 횟수를 요구하는 Algorithm

환경에 대한 가정 (여러 Algorithm을 Test하기 위해)

• 세개의 Frame이 할당
  -> Page Fault 발생 빈도는 Frame의 개수와 반비례
• 한번 참조된 Page는 Page 교체가 일어나기 전에는 물리 Memory에 위치함
  -> 다시 참조할 때 물리 Memory에 Page가 존재하는 경우에는 Page Fault가 발생하지 않음

Page를 참조하는 순서(20번)를 가정하여 Alogorithm 설명
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

Optimal Algorithm

가장 오랫동안 사용되지 않을 Page 부터 먼저 교체

• 이론상 최적으로 모든 Algorithm 중 가장 낮은 Page Fault 발생 빈도를 가짐
• 앞으로 어떤 Page가 사용될지를 미리 알 수 없기 때문에 실제 구현은 불가능함
  Page Fault 발생 횟수: 9번

FIFO Algorithm

먼저 Frame이 할당된 Page를 먼저 교체

• 가장 단순한 Algorithm
• FIFO Queue를 이용하여 구현
• 멀티미디어 Data로 인해 주목받음
  Page Fault 발생 횟수: 15번

SCR Algorithm

(Second Chance Replacement)

• FIFO 기법의 단점 보완 기법
• 오랫동안 주 기억 장치에 존재하던 Page 중에서 자주 사용되는 Page의 교체를 방지하기 위해 고안
• FIFO Queue를 만들고 사용하되 참조 Bit(Reference bit)를 두어 Page를 관리

  참조 Bit(Reference bit)

  • 최초로 Frame에 Load될 때와 Page가 참조되었을 때마다 1로 Set
  • 일정 주기마다 다시 0으로 Reset됨

제거 대상으로 선택된 Page의 참조 Bit가 1로 Setting된 경우,
최근에 사용된 Page이므로 제거하는 대신 참조 Bit만 0으로 Reset

참조 비트 없이 Page Table Hit이 발생하는 경우, 해당 Frame을 FIFO Queue의 맨 끝으로 옮기는 방식으로 SRC를 구현하기도 함

Clock Algorithm

• SCR 기법의 발전형
• Circular Queue를 사용하여 Frame 관리
• 다음에 제거될 Page를 가리키는 Hand라는 Pointer를 두어 관리
• Hand Queue를 따라 1칸씩 이동
• Hand가 가리키는 Page의 참조 Bit가 1이라면,
  최근에 접근한 Page이므로 제거하는 대신 참조 Bit만 0으로 Reset
  

LFU Algorithm

(Least Frequently Used)

사용 빈도가 가장 적은 Page를 교체

• 지금까지 가장 적게 참조된 Page가 교체대상으로 선택
• 일단 Program 실행 초기에 많이 사용된 Page는, 그 후로 사용되지 않더라도 Frame을 계속 차지하는 문제가 있음
  

NRU Algorithm

(Not Recently Used)

최근에 사용하지 않은 Page를 교체하는 기법

• Page마다 참조 Bit와 변형 Bit를 두어 관리

  참조 Bit (Reference Bit)

  • 최초로 Frame에 Load 될 때와 Page가 참조되었을 때마다 1로 Set
  • 일정 주기마다 다시 0으로 Reset

  변형 Bit (Modified Bit)

  • 최초로 Frame에 Load 될 때는 0
  • Page의 내용이 바뀔 때 1로 Set

Page 교체가 필요한 시점에 다음 순서대로 교체 대상으로 삼음
1. 참조 0, 변형 0 (교체 대상 1순위)
2. 참조 1, 변형 0
3. 참조 0, 변형 0
4. 참조 1, 변형 1

LRU Algorithm

(Least Recently Used)

가장 오랫 시간 참조되지 않은 Page부터 먼저 교체

• Page 사용의 지역성(Locality)을 고려하여
• Optimal Algorithm과 유사
• 실제 구현 가능한 Algorithm

구현 방법
Counter의 사용: 참조된 시간을 기록
Queue의 사용: 한번 사용한 Page를 Queue의 가장 위로 이동시킨다.

• 가장 위의 Page: 가장 최근에 사용된 Page
• 가장 아래의 Page: 가장 오래 전에 사용된 Page
  Page Fault 발생 횟수: 12번

Swapping

Page Out 으로 Memory 부족을 해결하지 못할 경우 필요

Swap Out 대상이 된 process 전체를 Secondary Storage로 보냄

Swap 영역: Page Out이나 Swapping에 사용되는 Secondary Storage(Backing Store)

Physical Memory 부족으로 Swapping이 발생

Swapping 도식

(Swap in, Swap out operation)

Contiguous Memory Allocation

1. Single Partition Allocation

• 가장 단순하게 Memory를 사용
• User Program 영역을 한 번에 1개의 User Program만 사용하도록

2. Multiple Partition Allocation

• "1" 의 방법에 Multiprogramming 개념을 추가하여 User Program 영역을 여러 개의 User Program이 사용하도록

3. No Partition

• 각 Program이 필요에 따라 전체 User Program 영역을 사용
• 이 경우, Page/Swap Out 시에 Garbage Collection이 필요함

Memory Allocation Problem

User Program이 Load 될 때, 물리 Memory의 OS 영역을 제외한 User 영역에 배치됨

• Protection Relocation, 그리고 Swap 기법을 사용함
• Program을 Memory에 Load할 때, Memory의 빈 공간 중 어디에 Program을 Load할지에 대한 고려가 필요

First-fit : 가장 먼저 발견한 곳에 배치
Best-fit: 사용 가능한 공간 중 가장 작은 곳에 배치
Worst-fit: 사용 가능한 공간 중 가장 큰 곳에 배치

Fragmentation

External Fragmentation

• Program에게 할당 후 남은 Memory의 총 공간은 새로운 할당 요청에 충분하지만, 그 공간이 연속적이지 않아 사용할 수 없는 경우
• Paging은 External Fragmentation을 해결하기 위한 방법임

Internal Fragmentation

• 할당된 Memory의 크기가 요청된 Memory의 크기보다 조금 더 커서 할당에는 성공했지만, 그 차이만큼의 영역을 사용할 수 없는 경우
• Paging에서 Page Frame은 4KB로 고정되었지만, 요청한 물리 Memory 영역이 3998B인 경우, 2B의 Internal Fragmentation이 발생하게 됨

• Paging 으로 해결 불가능

Fragmentation 예제

Protection

Contiguous Memory Allocation 방법을 사용할 때, OS의 Memory영역과 User Program의 Memory영역은 서로 구분되어야 함

서로의 영역을 침범하지 못하도록 보호해야 함

Relocation

User Program은 재배치 가능한 주소로 표현됨

재배치 가능한 주소를 이용하여 Program이 어느 위치에 Load되더라도 쉽게 Code의 주소를 결정할 수 있어야 함

Protection과 Relcation의 구현

-> Hardware의 Limit Register와 Relocation Register를 이용하여 구현

• Limit Register: 참조가 허용되는 주소의 최대값
  Limit Register의 값을 비교하여 참조하는 주소가 허용되는 영역인지 판별

• Relocation Register: Program이 차지하는 주소 영역 중 첫 번째 주소
  재배치 가능한 주소를 통해서 실제 물리 Memory의 주소로 참조 가능하게 함