Operating Systems 10. Virtual Memory - (2)

Demand Paging

- pure demand paging : 어떤 page 가 필요해지기 전까지는 그 page 를 메모리에 load 하지 않는다. 

- 실제로는 page fault 가 지역성(시간 지역성, 공간 지역성) 으로 인해 잘 일어나지 않는다.

- Hardware 는 demand paging 을 지원하기 위해 다음과 같은 지원을 한다.

• valid/ invalid bit 를 가진 Page table
• swap space 
• Instruction restart

 

 

Performance of Demand Paging

- Demand Paging 발생시 단계

• trap 이 발생한다.
• user register, process state 를 저장한다.
• 인터럽트가 page fault 인지 결정한다.
• page reference 를 확인하고, disk 에 있는 페이지의 위치를 확인한다.
• disk 로부터 free frame 에 페이지를 읽어온다.
• 기다리는 동안 CPU 는 다른 사용자에게 할당된다.
• page 가 page table 에 올라왔다면 CPU 가 다시 할당되고 프로세스가 재개된다.

- Page fault time 은 interrupt 시간 + disk 에서 page 를 읽어오는 시간(가장 긴 시간, ms 단위) + Process 를 재시작 하는 시간으로 구성된다.

Page fault 가 발생할 확률을 p라고 할 때, Efffective Access Time 은 다음과 같이 계산될 수 있다. 

 

- demand paging 최적화에 필요한 요소

-> swap space

- 프로세스를 로드할 때 프로세스의 모든 페이지를 swap space 로 복사한 다음에 프로세스를 시작하고, page 를 교체할 때에는 swap space 로 내보내는 방식 

-> 오래된 방법이고, 오버헤드가 너무 커서 잘 안쓰는 방법이다.

 

 

 

Copy-on-Write

- fork() 를 사용하여 프로세스를 생성했을 때 child process 는 parent process 와 같은 page를 공유하고, 쓰기 동작을 할 때에만 해당 페이지를 실제로 복사해온다.

- 보통 free page frame 을 할당할 때에는 0으로 채워 이전 내용을 지운 후 할당한다. -> Zero-fill-on-demand

-> 프로세스1번과 2번은 세개의 페이지를 공유해서 사용한다. 이때 프로세스1이 페이지 c에 대해 쓰기 동작을 하는 순간, 페이지 c에 대한 복사가 이루어져 프로세스1은 페이지 c에 대한 별도의 copy본을 가지게 되고, 그곳에서 쓰기가 이루어진다. 

 

vfork() 

- 자식 프로세스가 부모 프로세스의 주소 공간을 그대로 사용하게 된다. 

 

free frame 이 없는 경우

- page replacement : 사용중이 아닌 page frame 을 선택하여 swap out 하고, 새로운 page 를 swap in 한다.

- modify (dirty) bit : 페이지가 수정되었음을 표시하여, 수정된 페이지만 쓰기를 수행하도록 하여 overhead 를 줄인다.

 

 

 

Basic Page Replacement Algorithm

1. disk 에서 page fault 를 일으킨 페이지의 위치를 찾는다.

2. 이 페이지를 불어들일 free frame 을 찾는다. 이때 free frame 이 없다면, page replacement algorithm 을 이용해 victim frame 을 찾는다. 그리고 victim page 의 dirty bit 이 1이라면 swap space 로 쓰기 (백업)를 해야 하고, 그렇지 않다면 zero fill to demand 로 0으로 채운다.

3. 새로운 page 를 free frame 에 가져왔다면 page table 을 update 한다.

4. 프로세스를 재시작한다.

 

 

 

페이지 부재 횟수와 프레임 개수 그래프

일반적으로 프로세스에게 프레임을 많이 할당할수록 페이지 fault 횟수는 줄어든다.

 

 

 

 

First-In-First-Out (FIFO) Algorithm

가장 오래된 page frame 을 교체하는 방법이다.

-> FIFO 에서는 page frame 을 늘리면 오히려 page fault 가 늘어나는 경우가 생길 수도 있다. : Belady's Anomaly

 

 

 

 

 

Optimal Algorithm

가장 오랫동안 사용되지 않을 page를 교체한다. -> 실제로 그러한 page를 예측할 수 없기 때문에 구현이 어렵다.

 

 

 

Least Recently Used (LRU) Algorithm

가장 오래 전에 참조된 page 를 교체한다. (가장 덜 최근에 사용한 것을 교체)

- 이는 참조할 때마다 counter 로 기록이 필요하므로, 구현이 어렵다.

- 또한, 페이지 번호 저장용 stack 이 필요하므로 이를 유지하는데 overhead 가 발생한다.

 

 

 

LRU Approximation Algorithms (LRU 근사 알고리즘)

- Reference bit : page가 참조되면 1로 설정, 참조되지 않은(참조 비트 = 0) page 중 하나를 선택하여 교체한다.

- Second chance : 기본적으로 FIFO 로 구현하되, reference bit 를 사용한 알고리즘이다. 너무 오래전에 사용된 page 에 기회를 주지 않게 하기 위해서 주기적으로 reference bit 를 reset 해줘야 한다. 

페이지들을 순차적으로 검사해나가면서 reference bit 가 1인 페이지는 bit를 0으로 바꿔주고 건너뛰고, 0인 페이지를 만나면 그 page 를 victim 으로 선정하고 교체한다. 즉, 참조된 적이 있는 페이지에게는 한 번 더 쫓겨나지 않을 기회를 주는 것이다.

 

 

 

Enhanced Second-Chance Algorithm

reference bit 뿐만 아니라 modify bit(write 쓰기동작이 수행되었는지) 도 함께 참조하는 방식이다.

페이지마다 (reference, modify) 쌍을 가진다. 

1. (0,0) : 최근에 사용되지도 않고, 수정되지도 않음

2. (0,1) : 최근에 사용되지는 않았으나 수정된 페이지

3. (1,0) : 최근에 사용되었지만 수정되지 않은 페이지

4. (1,1) : 최근에 사용되었고 수정된 페이지

이는 가장 낮은 등급을 가진 페이지부터 교체하는 방법이다.

 

 

 

Counting Algorithms

각 page 의 참조 횟수로 판단하는 알고리즘이다.

- LFU(Least Frequently Used) : 참조횟수가 가장 적은 페이지를 교체

- MFU(Most Frequently Used) ; 가장 작은 참조횟수를 가진 페이지가 앞으로 사용될 것이라는 판단으로, 가장 많이 사용된 페이지를 교체한다.

-> 비용에 비해 성능이 최적에 근사하지 않아 잘 사용되지 않는다.

 

 

 

Page-Buffering 알고리즘

가용 프레임 여러 개를 pool 로 유지하고 있다가, 교체가 필요하면 페이지를 빈 프레임 중 한 곳에 할당해서 읽어들이는 방법이다.

교체될 페이지를 디스크에 기록하기 전에, 새로운 페이지를 읽어 들이는 방식으로 프로세스가 빨리 시작하게 된다.

즉, 쫓아낸 것을 buffer 에 두고 천천히 disk 로 쓰기 때문에, 쫓아내는 시간을 기다리지 않고 가용 pool 에 바로 사용가능하다.