9. 페이지 교체 알고리즘

페이지 교체

요구 페이징은 요구되어지는 페이지만 backing store에서 가져와 메인 메모리에 적재하는 방법이다. 필요한 페이지만 메인 메모리에 올려 메모리의 낭비를 줄이는 방법으로 사용된다. valid 비트를 추가한 페이지 테이블과 필요하지 않은 페이지를 보관하는 backing store를 가지고 기능을 수행할 수 있다. 하지만 프로그램 실행이 계속 진행되면 요구 페이지가 늘어나게 되고 언젠가는 메모리가 가득 차게 될 것이다. 페이지를 backing store에서 가져와 메로리에 올려야 되는데 메모리에 없을 때, 메인 메모리에 있는 특정 페이지를 내보내야 할 필요가 있다. 그러고 나서 그 자리에 필요한 다른 페이지를 올려야 한다. 이를 페이지 교체라고 한다.

 

메모리가 가득 차면 추가로 페이지를 가져오기 위해 어떤 페이지는 backing store로 몰아내고 그 빈 공간으로 페이지를 가져온다. backing store로 페이지를 몰아내는 것을 page-out이라고 하고 반대로 빈 공간으로 페이지를 가져오는 것을 page-in이라고 한다. 여기서 몰아내는 페이지를 victim page라고 한다. 말 그대로 희생 페이지라는 것을 의미한다.

페이지를 교체하기 위해서는 특정 페이지를 몰아내는 page-out으로 희생양 페이지를 만들어야 한다. 그러면 어떤 페이지를 victim page로 만들어야 되는가를 선정해야 한다. 만약 페이지를 backing store로 몰아낼 때 페이지 명령에 수정이 일어나지 않는다면 우리는 page-out과정에서 수정을 할 필요가 없다. 하지만 명령에서 수정이 일어났다면 하드디스크에 저장하기 위해 수정하는 작업이 필요하다. 따라서 두 가지의 경우에는 page-out과정에서 발생하는 시간이 다르다. 수정이 필요하지 않으면 몰아내는 과정만 진행하면 되지만 수정이 필요한 경우에는 수정하는 작업의 시간이 추가로 발생하게 된다. 따라서 시간을 절약하기 위해서 victim page로 수정되지 않은 페이지를 victim으로 선택하는 경우가 많다. 이를 위해서는 페이지가 수정이 되었는지 아닌지에 대한 기록이 필요하다. modified bit (dirty bit)를 만들어 이 값을 통해 수정이 되었는지 아닌지를 판별할 수 있게 한다.

 

위와 같은 과정으로 victim page가 될 수 있는 후보를 선정할 수 있었다. 하지만 실제로victim page로 나가는 페이지는 특정한 페이지일 것이다. 이는 페이지 교체 알고리즘에 의해서 선정이 된다. 교체 알고리즘에는 다양한 종류가 존재한다. Random으로 선택이 될 수도 있고 FIFO와 같이 첫번째로 메모리에 들어온 페이지를 먼저 보내는 방법이 있을 수도 있다. 이외에도 Optimal, LRU(Least Recently- Used) 알고리즘도 존재한다.

 

CPU는 메모리에 주소를 보내 명령어나 데이터를 요구한다. 하지만 메모리의 관리를 위해 페이지 테이블을 두어 주소 변환을 하게 된다. 따라서 실제로는 CPU에서 보내는 주소 보다 페이지 테이블에서 어떤 주소를 가리키는 것이 더 중요한 정보가 될 수 있다. 그래서 페이지 교체를 할 때에도 중요한 정보는 페이지 번호이다. 만약 CPU가 내는 주소가 아래와 같다고 가정해보자.

 

100 101 102 432 612 103 104 611 612

 

여기에 페이지 사이즈가 100바이트라면 각각의 페이지 번호는 1,1,1,4,6,1,1,6,6 이 될 것이다. 물론 100바이트 단위를 제외한 나머지 부분은 변위 부분을 가지게 될 것이다. 첫 번째 페이지를 읽으면 페이지 결함이 일어난다. 따라서 backing store인 하드디스크에서 번호가 1번에 해당하는 페이지를 가져오게 된다. 그러면 뒤에서 1번에 대한 페이지를 불러 온다면 페이지 결함이 일어나지 않을 것이다. 따라서 연속되는 값을 생략하여 표시하면 1,4,6,1,6 으로 나타낼 수 있다. 떨어져 있으면 페이지 교체에 의해 페이지 결함이 일어날 수도 있지만 연속된 경우에는 일어날 일이 없다. 이와 같이 표시하는 것을 page reference string , 페이지 참조열이라고 부른다. 

 

요약

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

반응형

페이지 교체 알고리즘

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

 

FIFO (First-in First Out)

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

 

하지만 프레임의 수가 많아질수록 페이지 결함의 횟수가 증가하는 경우도 있는데 이를 Belady's Anomaly 라고 한다.

Belady's Anomaly 이란?

-> 간단히 말해서 페이지 교체 알고리즘 중의 하나인 FIFO(First In First Out)에서, 원래 페이지 프레임의 개수를 늘리면 page fault발생이 감소 해야 하나, 오히려 늘어나는 경우가 발생하는데 그것을 Belady's Anomaly라 한다. 

참고 - https://en.wikipedia.org/wiki/B%C3%A9l%C3%A1dy%27s_anomaly

 

 

OPT (Optimal Page Replacement) - 최적 페이지 교체

OPT 알고리즘은 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내려 보내는 알고리즘이다. FIFO에 비해서 페이지 결함이 일어날 횟수가 더 적다. 하지만 OPT의 경우 앞으로도 사용이 잘 되지 않을 것이라는 보장이 없으므로 미래를 알 수 없기 때문에 실질적으로 수행하기에는 큰 어려움이 있다고 할 수 있다.

 

 

LRU (Least-Recently-Used)

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

 

 

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

 

출처: copycode.tistory.com/117