지난 포스팅에서는 page fault가 발생했을 때의 handling 과정에 대해서 알아보았다. 하지만 만약 free frame이 없다면 어떻게 할까?
당연하다. 현재 사용하지 않는 page 하나를 swap out하고, free frame을 하나 만들면 된다. 그런데 swap out 할 page를 어떻게 선정할 것인가? 아무 page나 선정하면 분명히 page fault rate 와 performence에 좋지 않은 영향을 끼칠게 뻔하다. 자주 사용하는 page를 할당 해제하면 당연히 얼마 안가 다시 swap in 해야 하기 때문이다.
따라서 page replacement algorithm 을 통해 적절한 page를 선정하는 것이 중요하다. 또한 page에 수정이 없었다면 굳이 디스크에 백업할 필요가 없다. swap out overhead도 분명히 성능에 영향을 미치기 때문이다. 이럴 때 사용할 수 있는 것이 modify or dirty bit이다.
Basic Page Replacement
Page Replacement Algorithms
-
Frame - allocation algorithm
: 각각의 프로세스가 몇 개의 frame을 할당받을 수 있게 할 것인가?
( 프로세스마다 할당받을 수 있는 frame 개수를 제한 ) -
Page - replacement algorithm
: 프로세스 간의 구분을 두지 않고 낮은 page fault rate를 위해 page replacement를 수행하는 알고리즘.
지금부터 알아볼 알고리즘들은 page - replacement 방식이다.
FIFO Page Replacement
page fault가 발생했을 때, 가장 오래된 page를 교체하는 것이 FIFO ( First - In - First - Out ) 알고리즘이다.
- Belady's Anomaly
논리적으로 frame 개수가 증가하면 (메모리 용량이 증가하면), page fault가 발생하는 횟수가 감소해야 하는데 그렇지 않은 구간이 존재한다는 것이 Belady's Anomaly 현상이다.
Optimal Page Replacement
Opimal 에서 알 수 있듯이 가장 낮은 page fault rate를 제공한다. 가장 오랜 시간 동안 사용되지 않을 page를 교체하는 것이 이 알고리즘의 핵심이다. 하지만 어떻게 앞으로 어떤 page가 사용되지 않을지를 계산하고 예측하는 것이 매우 어렵다. 따라서 예측이 얼마나 정확한지가 해당 알고리즘의 성능에 중요한 영향을 미친다.
LRU Page Replacement
Least Recently Used (LRU) 알고리즘은 가장 오랫동안 참조되지 않은 페이지를 교체한다. 즉, 최근에 참조된 페이지가 앞으로도 또 참조될 가능성이 높다고 판단하는 것이다. FIFO 알고리즘과 헷갈릴 수도 있지만 동작 방식을 보면 확실히 다른 부분이 있고 성능도 더 좋다.
LRU 알고리즘에서 가장 마지막에 참조된 페이지를 알기 위해서는 하드웨어의 도움이 필요하다.
-
Counter
: 모든 페이지가 counter를 갖도록 한다. 카운터는 클락과 타임 스탬프 등을 통해 구현할 수 있다. 이후 페이지 교체가 필요할 때 카운터의 값을 참조해 교체할 페이지를 결정한다. -
Stack
: 페이지를 스택으로 관리하는 것이다. 가장 최근에 참조된 페이지는 스택의 가장 위에 위치하며, 페이지 교체가 필요할 때는 스택의 가장 밑에 있는 페이지를 교체한다. 하지만 스택의 순서를 유지하기 위해 페이지의 순서를 업데이트 하는 비용이 더 많이 들어갈 수도 있다.
위의 그림에서는 7번 페이지가 참조되고 스택에서 7번 페이지를 상단으로 올리기 위해 총 6번의 이동이 필요하다.
LRU Approximation Algoritms
: LRU 알고리즘과 비슷한 동작을 수행하기 위한 알고리즘들이다.
Reference bit
: reference bit는 해당 페이지가 참조될 때, 1로 설정되는 비트이다. 따라서 처음에는 항상 0으로 초기화된다. 따라서 페이지 교체가 필요할 때 reference bit 값이 0인 페이지를 선택할 수 있다.
Second Chance algorithm
: 일반적으로 FIFO의 동작 방식과 유사하지만 refernce bit를 함께 사용한다. page fault가 발생했을 때, 페이지를 순회하면서 refernce bit가 1일 경우 0으로 초기화하고 다음 페이지로 넘어간다. 이렇게 페이지를 순회하면서 reference bit가 0인 페이지를 교체한다. reference bit가 1인 페이지를 0으로 초기화하고 다음 페이지 순회 시에도 비트 값이 0이면 교체하기 때문에 second chance 알고리즘이라고 불린다. 즉, 하나의 페이지에 대해서 비트 값이 1이라면 기회를 한 번 더 주기 때문이다. 다음 순회 때도 비트 값이 1이라면 똑같이 교체하지 않고 비트를 0으로 초기화 한 다음에 다음 페이지로 넘어간다.
Global vs Local Replacement
-
Global Replacement
: 프로세스가 페이지 폴트를 처리할 때, 시스템 내 모든 프레임 중에서 교체할 프레임을 선택한다. 즉, 하나의 프로세스가 다른 프로세스의 프레임을 가져올 수 있다는 의미이다. -
Local Replacement
: 프로세스가 페이지 폴트를 처리할 때, 자신의 프로세스에 할당된 프레임 중에서만 교체할 프레임을 선택할 수 있다. 각 프로세스는 일관된 성능을 보일 수 있지만, 메모리의 효율이 떨어진다.
