[운영체제] 20. Swapping - Policy

 

Reference - Operating Systems: Three Easy Pieces

 

 

https://pages.cs.wisc.edu/~remzi/OSTEP/

Operating Systems: Three Easy Pieces

 

 

Replacement Policy

 

Swapping의 Mechanism(How)에 대해 알아봤다면 이번엔 어떤 Page를 교체할지, 즉 Swapping Policy(What)에 대해 알아보겠다. 이는 당연히 오버헤드가 매우 큰 page fault를 최소화하는 것이 목적이다. 

 

미래를 알고 있을 때, 최선의 Policy를 Optimal이라 하자. 이때의 Hit rate와 다른 Policy의 Hit rate를 비교할 것이다.

 

- FIFO

먼저 FIFO의 경우, 좋지 않은 Hit rate를 보여준다. 

Belady's anomaly(벨레이디 모순) : 페이지 프레임 수를 늘리면 페이지가 없는 page fault 발생이 감소해야하지만, 오히려 늘어나는 경우가 발생한다. 

 

- Random

두번째로 Random의 경우, optimal만큼 좋은 경우의 수도 존재한다. 하지만 이는 운에 의존하는 일이다.

 

- LRU

따라서 세번째, LRU를 쓸 수 있다.

Least Recently Used의 약자로, history를 보고 교체할 page를 선택하는 것이다. 이는 곧 temporal locality를 활용한다는 뜻이다.  이렇게 하면 일반적인 경우 Hit rate를 높일 수 있다.

 

이때 Workload의 형태에 따라 Hit rate가 바뀔 수 있다. workload는 locality 때문에 아래 경향성을 띤다.

- 80-20 Workload - 80%의 reference가 20%의 page에 의해 이루어지는 workload , general case)

: LRU is good, RAND is bad

- looping sequential - 0부터 n개의 page까지 순서대 loop하는 workload

: LRU와 FIFO는 오래된 page를 제거하기 때문에, page frame이 page보다 커지기 전까지 Hit rate가 0이다가 더 커지는 순간부터 ratio가 100이 된다. random은 0부터 지수 곡선으로 page frame = page까지 상승하다 이후 100%가 된다.

 

LRU를 구현할 때 History로 page를 고르는 알고리즘의 연산을 최대한 줄여야 한다. 이를 위해 하드웨어의 지원을 받는다.

먼저 Counter를 사용할 수 있다. page가 referencing될 때마다 clock을 counter에 copy하고, counter가 가장 작은 값을 교체하는 것이다. 하지만 이는 O(n)의 complexity가 발생하기에 메모리가 커질수록 성능이 안좋아진다.

다음으로 Stack을 사용할 수 있다. page가 reference되면 stack을 통해 top으로 옮긴다. 이때 데이터를 옮길 때의 overhead가 존재한다.

 

- Approximating LRU

마지막으로 Approximating LRU가 있다. hardware support를 통해 reference bit을 써서 LRU와 최대한 비슷하게 동작하도록 한다. default는 1bit지만, 더 많은 bit를 쓸수록 정확도는 올라가고 메모리 소모는 심해지는 tradeoff 관계다.

이때 clock Algorithm을 사용하는데, 모든 page를 circular list로 만들고 현재 가리키는 page의 reference bit가 1보다 크면 bit를 -1하고 다른 page를 찾는다. 이 과정을 reference bit이 0인 page를 찾을때까지 반복하고, 0인 page에 접근하면 해당 page를 victim으로 선택한다. 모든 history를 탐색하지 않아도 돼서 performance가 좋다.

 

- considering dirty pages

page가 write(update)됐을 때 dirty page라 한다. 이 경우 victim으로 선정되어도 disk로 데이터를 옮기는 작업까지 수행해야 하기 때문에 page fault time이 늘어나게 된다. 일반적으로, clean page가 victim으로 선정되며, PTE의 dirty bit로 dirty page 유무를 알 수 있다.

 

- when to bring a page into memory?

메모리로 page를 옮기는 swap은 언제 수행되어야할까?

그 방법에는 Demand paging - 접근할 때 옮기는 방식과 prefetching - 자주 쓰는 page를 미리 올려두는 방식이 있다.

prefetching의 경우 grouping을 사용해 disk에서 한번에 여러 page를 메모리로 옮기므로 overhead 훨씬 줄어듬. 

(called delayed write)

 

- thrashing

많은 프로그래밍을 동시에 올릴수록(=프로세스가 요구하는 메모리가 커질수록) cpu utilization이 올라가다가, 실제 물리적인 메모리보다 커지게 되면, page fault를 계속해서 발생시키며 가치있는 메모리도 evict하는 I/O가 발생하게 되어 utilization이 훅 줄어든다. 이를 thrashing이라 한다.