Virtual Memory Management - Page Replacement, Page replcaement algorithm, Thrashing, Working Set Model

Virtual Memory Management

Page Replacement

- Page를 할당할 frame이 없는 경우 Swap out을 통해 빈 frame을 만들고 해당 page를 swap in 해준다.

-> 최소한의 page fault를 목표로 해야한다.

Basic Replacement

1) Disk에서 가져올 page의 위치를 찾는다.

2) 비어있는 frame을 찾는다.

-> 비어있는 frame이 있는 경우, 그 frame에 할당

-> 비어있는 frame이 없는 경우, page replacement algorithm을 이용

해 victim frame을 선정한다

3) 비어있는 frame에 가져온 page를 할당하고 page table을 update한다.

4) Process를 재시작한다.

- 위와 같은 방식에서는 swap in, swap out 총 두번의 disk 접근이 필요하다. disk 접근하는 데에 드는 overhead를 줄이기 위해 modify bit를 사용할 수 있다. victim page가 memory에 있는 상태에서 수정이 되었다면 modify bit를 1로 변경해 swap out을 하고 변경 사항이 없다면 swap out을 해 disk에 저장할 필요가 없어진다.

Page Replcaement Algorithm

- Page fault의 비율을 줄이기 위한 algorithm이 필요하다. page fault가 일어날 때마다 victim page를 선정하고 swap in, swap out을 해서 overhead가 커지므로 page fault rate를 낮춰야한다.

Belady's Anomaly

- Frame수를 늘렸지만 page fault가 감소하지않고 오히려 더 증가하는 현상

Example) 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 순으로 page를 요청할 때

Frame size가 3일 때는 page fault가 총 9번 일어난다.(1,2,3,4,1,2,5,3,4)

Page fault를 줄이기 위해 frame size를 4로 증가시켰지만 page fault는 총 10번 일어나 더 증가하게 된다.

(1,2,3,4,5,1,2,3,4,5)

frame size를 증가시켰지만 오히려 page fault가 증가하는 현상을 Belady's Anomaly라고 한다.

1) FIFO algorithm

- Victim Page를 선정할 때 FIFO 개념을 사용한다. 먼저 들어왔던 page를 victim으로 선택하여 교체하는 방법을 사용한다.

위와 같은 page 요청이 들어왔을 때, FIFO방식으로 교체하면 위와 같이 총 7번의 Page fault가 생긴다.

2) Optimal algorithm

- 최적의 알고리즘으로 앞으로 가장 오랫동안 사용되지 않을 page를 교체하는 방법이다.

- 이론적으로는 가장 최적화되어있지만, 앞으로 요청할 page를 알 수 없기때문에 현실적으로는 불가능한 page 교체 알고리즘이다.

Optimal Algorithm을 사용하면, 총 6번의 Page fault가 일어난다. 최적이지만 실제로는 들어올 page요청을 알 수 없기 때문에 사용할 수 없다.

3) LRU algorithm(Least Recently Used)

- 가장 오랫동안 사용되지 않았던 page를 교체하는 방법이다.

- frame에 들어가있는 page중 가장 오랫동안 요청이 없었던 page를 victim으로 선정한다.

가장 최근에 사용되지 않은 page를 교체해주는 방식인 LRU를 사용했을 때의 모습이다. 위 예제에서는 FIFO와 같은 수의 page fault가 생기지만, 실제로 많은 page가 들어올 때 가장 효율적인 알고리즘으로 가장 많이 사용되는 page 교체 알고리즘이다.

- 가장 최근에 사용된 page를 기록하여 page를 교체해야 한다. 여기에는 두가지 방법이 있다.

① Counter implementation : 모든 page의 entry에 counter를 기록하는 방법이다.

② Stack implementation : stack을 이용한 방법으로 page가 요청되면 stack에 넣어준다. 이 후에 stack의 bottom에 있는 page를 victim으로 선택한다.

-> stack방식으로 search가 필요없기 때문에 search 시간은 더 적지만, reference overhead는 더 크다.

3) LRU-approximation algorithm

- LRU 알고리즘에서 약간의 변형이 생긴 알고리즘이다.

- LRU 알고리즘에서 추가적으로 각 page의 entry에 Reference bit를 추가한다

- reference bit는 0으로 초기화하고 참조될 때 reference bit를 1로 변경한다.

- victim page를 선택할 때는 reference bit가 0인 page중에 선택한다.

- 여러개의 page의 reference bit가 0일 때, reference bit를 하나만 사용해서는 문제가 생길 수 있다. 그러므로 추가적인 다른 방법을 사용한다.

① Additional-reference-bits algorithm

 - 각 page마다 8비트의 reference bit를 만들고, 참조될 때 가장 왼쪽 bit를 1로 바꿔주고 요청이 올때마다 오른쪽으로 shift한다. 

 - Page 교체가 필요할 때, Reference bit의 값이 가장 작은 값이 교체된다.

② Second chacne algorithm

 - Reference bit 하나를 사용하여 교체를 위해 모든 page를 순회하며 victim의 reference bit가 0이라면 교체되고, 1이라면 0으로 바꾼 후 한번의 기회를 더 주는 알고리즘이다.

③ Enhanced Second chance algorithm

- Reference bit 하나와 함께 modify bit도 사용하는 방법이다.

 - 4개의 클래스로 나눌 수 있다.

 - class 1 : (0,0) -> 최근에 사용되지 않았고 수정되지도 않은 경우

 - class 2 : (0,1) -> 최근에 사용되지는 않았지만 수정된 경우

 - class 3 : (1,0) -> 최근에 사용되었지만 수정되지 않은 경우

 - class 4 : (1,1) -> 최근에 사용되었고 수정된 경우

 -> 낮은 class를 가진 page부터 victim으로 선택한다.

4) Counter-Based algorithm

- LRU와 같이 요청된 시간과 상관없이 사용된 빈도를 이용하여 Page를 교체하는 알고리즘이다.

① LFU Algorithm : Page가 요청된 빈도를 기록하여 가장 적게 참조되었던 page를 victim으로 선택하여 교체하는 방법이다.

② MFU Algorithm : Page가 요청된 빈도를 기록하여 가장 많이 참조되었던 page를 victim으로 선택하여 교체하는 방법이다.

Thrashing

Definition : Process가 충분한 page를 가지지 못해 page fault의 비율이 올라가 프로세스가 계속해서 swap in/swap out하느라 CPU 이용률이 낮아지는 현상이다.

- Thrashing 현상을 줄이기 위해서는 Process에 필요한 만큼의 frame을 할당해주는 것이 중요하다.

- Locality model을 사용하는 것이 좋다. Locality를 사용하여 Page를 참조하는 모델이다.

- Locality의 size가 총 memory size보다 커지는 경우에 thrashing이 발생한다.

Working Set Model

- Thrashing을 측정하기 위한 방법이다. 

- Locality Reference의 특성을 이용하여 한 시기에 집중적으로 참조되는 page들의 locality set을 이용한다

- 프로세스가 수행되기 위해 한꺼번에 memory에 올라와있는 page의 집합을 working set이라고 한다.

- Process의 working set전체가 memory에 올라와있으면 실행되고, 아니라면 page를 요청하지 않고 모든 page frame을 swap out해 Thrashing을 방지한다.