[OS 21장] 메모리 관리 - 페이지 교체

- 페이지 교체(1) -

 

요구 페이징은 요구되어지는 페이지만 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 페이지 참조열이라고 부른다. 이에 대한 내용은 뒤에서 나오는 페이지 알고리즘에 대한 기초 지식이라고 생각하면 된다.

- 페이지 교체(2) : 페이지 교체 알고리즘 -

 

가상 메모리는 요구 페이지 기법을 통해 필요한 페이지만 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를 선정하게 되는데 선정하는 기준이 전체를 기준으로 하느냐 자기 프로세스의 페이지에서를 기준으로 하느냐에 대한 차이이다. 실제로 전체를 기준으로 페이지를 교체하는 것이 더 효율적이라고 할 수 있다.