운영체제 24장 - 메모리 관리(11) : 페이지 교체 알고리즘 -

운영체제 24장

- 페이지 교체 알고리즘 -

 

가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 backing store에서 메모리로 적재를 하고 사용하지 않는 부분은 그대로 둔다. 하지만 필요한 페이지만 올린다고 하더라도 메모리가 나중에는 가득 차게 되고 올라와있던 페이지가 사용이 다 된 후에도 자리만 차지하고 있을 수 있다. 메모리가 가득 차면 추가로 페이지를 가져오기 위해 어떤 페이지는 page-out을 해야 하고 그 빈 공간에 필요한 페이지가 page-in을 해야 한다. 여기서 어떤 페이지를 backing store로 page-out을 시킬 것인지에 대해서 고민을 하게 된다. page-out이 되는 페이지를 victim page라고 부르는데 기왕이면 수정이 되지 않는 페이지를 선택하려고 한다. 만약 수정이 된다면 메인 메모리에서 내보낼 때 수정에 대해 하드디스크 또한 수정을 진행해야 함으로 시간이 더 오래 걸리기 때문이다. 아지만 이러한 조건으로 특정 페이지를 선정할 수는 없다. 그래서 다양한 페이지 교체 알고리즘이 존재하게 된다.

페이지 교체 알고리즘을 알기 전에 Page reference string에 대해서 알아야 되는데 CPU가 논리 주소를 통해 특정 주소를 요구하는데 메인 메모리에 올라와 있는 주소들은 페이지의 단위로 가져오기 때문에 페이지 번호가 연속되어 나타나게 되면 페이지 결함이 일어나지 않는다. 따라서 CPU의 주소 요구에 따라 페이지 결함이 일어나지 않는 부분은 생략하여 표시하는 방법을 page reference string이라고 한다. 자세한 내용은 운영체제 23장에 서술해져 있다.

알고리즘들은 그림의 예시를 통해 이해하면 더욱 빠르게 이해할 수 있을 것이다. 예시를 읽는 법을 보면 파란색의 경우는 페이지 결함이 일어난 경우가 되고 참조열은 Page reference string이라고 볼 수 있다. 프레임의 개수는 모두 3개만 존재하여 페이지는 3개의 프레임에 할당되게 되는 것이다.

첫 번째 알고리즘은 FIFO로 First-in First-Out이다. 메모리에 먼저 올라온 페이지를 먼저 내보낸다는 알고리즘이다. 따라서 victim page의 대상은 가장 먼저 메모리에 올라온 페이지가 되는 것이다. 이 방법은 가장 간단한 방법이다. 특히 초기화 코드에 대해서 적절한 방법이라고 할 수 있다. 초기화 코드는 처음에 프로세스가 실행될 때 최초 초기화를 시키는 역할만 진행하고 다른 역할은 수행하지 않기 때문에 메인 메모리에서 내려 보내도 괜찮다. 하지만 처음에 프로세스를 실행시키는데 무조건 필요하다. 따라서 FIFO의 방법을 사용하면 초기화 시켜준 후 가장 먼저 내려 보내지게 된다. 그러면 프레임의 수가 커질수록 페이지 결함은 어떻게 되겠는가? FIFO의 알고리즘은 프레임의 수가 적을수록 페이지 결함이 더 많이 일어나게 된다. 계속 교체를 해주어야하기 때문이다. 하지만 프레임의 수가 많아질수록 페이지 결함의 횟수는 감소하게 된다. 이를 Belady’s Anomaly라고 부른다.

두 번째 알고리즘은 OPT(Optimal) 이다. OPT 알고리즘은 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내려 보내는 알고리즘이다. 이름과 같게 가장 적절할 수 있는 알고리즘이라고 할 수 있다. 확실하게 앞의 FIFO에 비해서 페이지 결함이 일어날 횟수가 많이 감소하는 것을 알 수 있다. 하지만 Optimal의 경우 앞으로도 사용이 잘 되지 않을 것이라는 보장이 없으므로 미래를 알 수 없는 조건에 의해 실질적으로 수행하기에는 큰 어려움이 있다고 할 수 있다.

세 번째는 LRU 알고리즘은 Least-Recently-Used이다. LRU 알고리즘은 최근에 사용하지 않은 페이지를 가장 먼저 내려 보내는 알고리즘이다. 최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 아이디어로부터 온 것이다. OPT의 경우에는 미래에 대한 예측이지만 LRU의 경우에는 과거를 보고 판단하므로 실질적으로 사용 가능한 알고리즘이라고 할 수 있다. 실제로도 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다고 할 수 있다. 비록 OPT 보단 페이지 결함이 더 일어날 수 있지만 실제로 사용할 수 있는 알고리즘 중에서는 좋은 방법 중 하나라고 할 수 있다.

교체하는 방식에는 Global 교체와 Local 교체로 두 가지의 방식이 존재한다. Global 교체는 메모리상의 모든 프로세스 페이지에 대해 교체를 하는 방식이고 Local 교체는 메모리상의 자기 프로세스 페이지에서만 교체를 하는 방식이다. 다중 프로그래밍의 경우 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있는데 따라서 다양한 프로세스의 페이지가 메모리에 존재하게 된다. 페이지를 교체할 때 앞의 다양한 알고리즘에 의해 victim page를 선정하게 되는데 선정하는 기준이 전체를 기준으로 하느냐 자기 프로세스의 페이지에서를 기준으로 하느냐에 대한 차이이다. 실제로 전체를 기준으로 페이지를 교체하는 것이 더 효율적이라고 할 수 있다.