[OS 기초] Demanding Paging 2 - Virtual Memory Management

# Page Replacement Policies

> Page replacement Algorithms

1. Random - 주로 하드웨어 적으로 구현할 때 사용

2. FIFO

- Linked List로 구현

3. Optimal - 가장 먼 미래까지 전혀 사용되지 않을 페이지를 교체. 

* Reference String : Sequenced of Referenced Pages. 어떤 프로세스가 수행하는데 프로세스가 ref했던 시퀀스.

4. LRU - Least Recently Used. 최근에 가장 사용되지 않은 페이지들을 교체. 

Temporal Locality에 기반한 Page Replacement 정책.

Timestamp 사용하여 page frame 하나하나마다 count 정보를 저장해야 하지만 굉장히 오버헤드 크기때문에 Counter 대신 Reference Bit를 사용하기로 함

<Memory Management에서 사용되는 flag bit 종류>

* Reference Bit : Use Bit, Main Memory에 로드된 페이지가 엑세스 되면 Set되는 Bit Flag.

* Resident Bit : 내가 사용려는 page가 1이면 현재 Ram에 존재하고 있을때, 0이면 swap device에 있을 때

* Dirty Bit

> Belay's anomaly : FIFO의 문제점을 명시. 메모리를 늘렸음에도 불구하고 페이지폴트가 더 많이 발생하는 현상

* Stack Algorithm : N개의 Frame으로 구성된 메모리에 로드된 Page들이 항상 N+1개의 Frame으로 구성된 메모리에 로드된 page들의 부분집합이 되는 알고리즘.

절대 Belay's anomaly를 나타나지 않음

ex. LRU ...

(이름이 stack algorithm인 이유는 항상 나가고들어오는 부분이 stack처럼 어느 부분에서만 일어나기 때문에 stack에 비유)

* Page Replacement를 수행할 때, 미래를 예측하여 수행하면 굉장히 효율적일 것이나, 현실적으로는 불가능.

하지만 프로그램은 Locality라는 속성을 가지므로 과거를 통해 미래를 어느정도 예측할 수 있음.

=> LRU algorithm

> LRU

1. reference bits algorithm(8bits)

: reference bits를 하나 두고 8개의 8bits 짜리 register를 붙인 후, 일정한 간격으로 reference bits을 shift right하여 가장 사용이 안된 것을 고름. 

=>  사용여부 체크(00000000이 0이므로 가장 작겠지)

액세스의 여부만으로는 정확한 우선순위를 정하기 어렵기 떄문에, OS는 시간을 일정 간격으로 시간을 나눈 후 해당 interval에서 사용이 되었는지의 여부를 체크

2. Clock Algorithm

: linear한 frame들을 clock처럼 wrap around 형태로 연결 시킨 후, 현재 가리키고있는 임의의 페이지를 가리키는 clock hand로 페이지를 교체할 시점엔 어느페이지를 선택할 지 결정해야 함

* Clock Algorithm에서 교체할 Page를 선택하는 방법 

: Clock Hand가 가리키는 page의 reference bit이 1인경우, 0으로 바꾸고 Clock Hand가 다음 page를 가리키도록 함(최근에 사용되었다는 의미이므로 skip). 이 과정을 반복하다가 reference bit이 0인 page를 만나면 최근에 사용되지 않은 page이므로 해당 page를 교체체.

(UNIX OS 에서 많이 사용되는 알고리즘)

- 모든 reference bit이 1이면 모든 page가 reference 되고 있다는 의미이므로 main memory가 현재 overcommit되고 있다는 의미이며, 모든 페이지가 빈번하게 access되고 있으며 skip구간이 굉장히 많이 되므로 clock hand도 빠르게 회전하게 됨

=> clock algorithm은 LRU algorithm을 기반으로 업그레이드 한 것이지만, 메모리 Over Commit이 일어나게되면 FIFO algorithm으로 전환됨

3. Enhanced clock algorithm

- reference 안됐고 clean한 page

- reference 안됐고 dirty한 page

- reference 됐고 clean한 page

- reference 됐고 dirty한 page

* 기본적으로 clean한 페이지를 dirty한 페이지보다 우선적으로 처리한다. clean하면 swapping시 따로 지워주지 않아도 되므로 비교적 처리가 쉬움.

=> but, clean page라고해서 무조건 내보내는게 좋은 건 아니다. code page일 수 있다?

* Micro Architecture의 MMU기능의 단순화로 reference bit을 지원하지 않는다면?

> FIFO 사용

> Frame Buffering : 단순 FIFO를 기반으로 빈번하게 사용되는 frame을 다이나믹하게 관리하여 유용하게 사용하기 위해 free list를 사용

- used page frame list (linked list)

- free page frame list (linked list)

* Optimization : clean page와 dirty page가 섞여있는 free list에서, swap device와 DMA Controller가 IDLE 하다면, dirty page를 Swap-out하여 clean하게 해주기!

# Page Replacement Style

: allocation style

1. Global replacement

: 시스템 단위로 replacement

- 단점 : 메모리를 지나치게 사용하는 동작이 있다면 메모리를 효율적으로 사용하기 어렵다.

- 장점 : 메모리를 모두 고르게 분배하여 사용하면 메모리를 낭비없이 효율적으로 사용할 수 있다.

2. Per-process replacement

3. Per-job replacement(per-user replacement)

* 2,3번의 경우에는 Process나 Job단위로 나누어 replacement되므로 

간섭을 받지 않는다는 장점이 있지만, 어떤 부분은 메모리가 모자를수도, 어떤 부분은 메모리가 남아돌수도 있는 단점이 나타날 수 있음.

=> 할당되는 메모리를 dynamic하게 조절해 줄 수 있는 기능이 추가적으로 필요

: 단위시간동안 Page Fault횟수를 확인하여 메모리가 남는지 부족한지를 판단하여 이용한다.