[운영체제] 페이지 교체

오늘은 페이지 교체가 발생하는 원인과 페이지 교체의 방법들을 알아보도록 하겠습니다.

 

 

  페이지 교체

메모리는 한정적입니다. 아무리 가상 주소 공간을 이용하여 많은 수의 프로세스를 메모리 상에 올린다고 하더라도, 메모리에 프로세스를 로드할 수 없는 상황은 필연적으로 발생합니다.

 

이 때, 우리는 어떠한 프로세스를 swap할 것인지를 정해야합니다. 자주 쓰는 프로세스보다는 덜 쓰는 프로세스를, 또는 최근에 사용됐던 프로세스 보다는 예전에 사용했던 프로세스를 swap out해야할 지도 모릅니다. 여기서는 이러한 페이지 교체를 하는 방법론에 대해서 알아보겠습니다.

 

 

   FIFO(First-In, First-Out)

말 그대로, 가장 먼저 들어온 것을 가장 먼저 밖으로 내보내는. 그러니까 가장 예전에 쓰인 프로세스를 내쫓는 방법이 되겠습니다. 구현이 간단하다는 장점이 있지만, 우리가 swap out한 프로세스를 빠른 시간 내에 다시 load할 수도 있다는 단점이 존재하기도 합니다.

 

아래는 접근하려는 페이지의 번호를 순서대로 나열하였고, 그 때(page fault가 발생할 때)의 상태를 그림으로 나타낸 것입니다.

그림이 나타나있지 않은 곳은 page fault가 발생하지 않았음을 의미합니다.

 

총 15번의 page fault가 일어남을 알 수 있습니다.

 

 

   Optimal Policy

쉽게 말해 가장 나중에 쓰일 페이지를 out시키자는 방법론입니다. 이론적으로는 사실 가장 좋은 성능을 낼 것 같아 보입니다. 하지만 실제로 이후에 쓰일 것을 예측하는 행위는 쉬운 계산이 아닙니다. 실질적으로 불가능에 가깝기에 위 알고리즘은 우수한 성능을 이론적으로 보이지만, 실사용이 불가능하다는 아쉬운 점이 존재합니다.

 

현재 위 알고리즘은 실제 사용되는 알고리즘의 성능을 측정하기 위한 비교 기준으로 사용되고 있습니다.

 

총 9번의 page fault가 일어났습니다.

 

 

   LRU(Least Recently Used)

LRU는 가장 오래 전에 사용된 것을 교체하는 방식의 방법론입니다. Locality 성질에 의해서 가장 오래 전에 쓰인 것은 향후에도 잘 쓰이지 않을 경향이 높습니다. 하지만 이러한 사용되는 빈도를 저장하기 위한 저장공간이 별도로 필요하게 됩니다. 따라서 overhead가 발생하게 됩니다.

 

총 12번의 page fault가 일어났습니다.

 

 

   Clock Policy(second change algorithm)

LRU 알고리즘을 근사하는 방법입니다. 사용된 횟수 또는 사용여부를 나타내는 비트를 두지 않고 Page Table 또는 TLB에 존재하는 P비트를 이용합니다. 아래와 같은 방식으로 swap out할 페이지를 결정할 수 있습니다.

 

1. 가장 먼저 로드된 페이지는 P 비트가 1로 세팅되어 있을 것입니다.
2. OS는 P 비트를 확인하며 P 비트가 0인 페이지를 swap out할 것입니다.
3. P 비트가 만약 1이라면, 해당 비트를 0으로 바꾸고 다음 페이지를 2번과 같이 반복합니다.

 

이러한 방식으로 우리는 swap out의 대상을 고를 수 있습니다. 마치 next-fit과 같이 circular한 배열로 간주하며 페이지를 찾는다는 것이 특징이 되겠습니다.

 

0번 인덱스부터 찾아보면서 use bit의 값이 0인 것을 찾습니다. 아마 4번째 인덱스인 556번째 테이블이 swap out의 대상이 될 것입니다. 또한 0번 인덱스부터 3번 인덱스까지의 user bit는 0으로 변경될 것입니다.

 

 

   Enhanced Clock Policy

Clock Policy는 use bit만을 사용했지만 여기서는 use bit와 modified bit 두 개의 조합을 이용합니다.

 

use bit = 0, modify bit = 0

최근에 사용되지도, 수정되지도 않은 페이지입니다. 이 페이지는 교체되기 아주 좋은 페이지이며 발견 즉시 해당 페이지를 swap out합니다.

 

use bit = 0, modify bit = 1

최근에 사용되지는 않았지만, 수정한 적이 있는 페이지입니다.

 

use bit = 1, modify bit = 0

최근에 사용되었고, 수정한 적이 없는 페이지입니다.

 

use bit = 1, modify bit = 1

최근에 사용되었고, 수정한 적이 있는 페이지입니다.

 

앞서 소개한 순서대로 페이지 우선순위가 낮아집니다. 즉, (use  bit, modify bit) = (0, 0)일 때 필수적으로 swap out이 진행되죠.

 

하지만 궁금점이 생깁니다. 왜, modify bit를 이용해서 우선순위를 한층 더 나누었을까요?? 이는 우리가 swap out할 때의 과정을 생각해보면 됩니다. swap out을 할 때, 해당 비트가 수정되었다면 우리는 보조 기억 장치에 저장하는 과정을 거쳤어야했습니다. 수정이 되었으니까요! 하지만 수정되지 않았다면 저장할 필요 없이 바로 버려버리면 됩니다. 따라서 우리는 modify 비트를 사용하고 해당 비트가 0일 때, 가장 먼저 swap하도록 설정하였습니다.

 

이 그림에서도 마찬가지입니다. 우리는 인덱스 3을 교체했었고 이제 인덱스 4부터 탐색을 시작합니다. 인덱스 8번이 최적의 조건인 (0, 0)을 이루고 있네요. 따라서 해당 페이지인 47번 페이지를 swap out합니다. 이 때, 저장하지 않고 바로 버려주는 과정으로 진행됩니다.

 

---

 

지금까지 여러 페이지 교체 방법에 대해서 다뤄봤습니다. 감사합니다.