17. 페이지 교체(Page Replacement)

썹스·2022년 8월 24일

운영체제

목록 보기

17/20

1. 페이지 교체(Page Replacement)

가상 메모리 환경에서 메모리 적재는 요구되는 페이지만 backing store(H/W 디스크)에서 가져온다. 프로그램 실행이 계속됨에 따라 점차 요구하는 페이지수가 증가하면, 언젠가는 메모리의 용량이 가득 차게 된다.

메모리가 가득 차게 된 상태에서 페이지 요구가 추가되면, 어떤 페이지는 backing store로 몰아내고(page-out), 몰아낸 공간에 요구된 페이지가 적재(page-in)된다. 이렇게 page-out에 의해 backing store로 이동하게 되는 페이지를 희생 페이지(victim page)라 부른다.

1-1. 희생 페이지(Victim Page)

메모리가 가득 찬 상태에서 추가 페이지 요청이 들어오면, 메모리에 적재 중인 페이지 중에서 어떤 것을 희생할지 결정해야 한다. 결정할 때는 페이지 부재율(page fault) 최소화하면서, CPU에 의한 수정(modify)이 없는 페이지를 결정하는 것이 가장 효율적이라고 볼 수 있다.

CPU에 의한 수정(modify)이 없는 페이지를 찾는 방법은 페이지 테이블에 modified bit를 추가하여 찾는다. 해당 페이지가 수정되었다면 modified bit 값을 "1", 수정되지 않았다면 modified bit 값을 "0"으로 둔다.

위 그림처럼 수정되지 않은 페이지(modified bit값 = 0)의 수가 2개 이상 존재하면, 다양한 페이지 교체 알고리즘에 의해 결정된다.

1-2. 페이지 교체 알고리즘

수정되지 않은 페이지의 수가 2개 이상 존재하면, 아래와 같은 다양한 방법으로 페이지를 선택해야 한다.

First-In First-Out(FIFO)
FIFO 알고리즘은 가장 먼저 page-in 한 페이지를 먼저 page-out 시키는 방법이다. (선입 선출 방식)
Optimal(OPT)
OPT 알고리즘은 가장 효율적인 페이지 교체 알고리즘이다. 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 방법이다. 하지만 운영체제가 가장 오랫동안 사용하지 않을 페이지를 알아내는 것이 불가능하기 때문에 OPT 알고리즘은 현실적으로 불가능한 방법이다.
Least-Recently-Used(LRU)
LRU 알고리즘은 최근에 가장 오랫동안 사용하지 않은 페이지 찾아 교체하는 방법이다. 최근에 오랫동안 사용하지 않았다면, 앞으로도 사용할 가능성이 적다고 판단하는 방식이다.
Least-Frequently-Used(LFU)
LFU 알고리즘은 사용 빈도가 가장 적은 페이지를 교체하는 방법이다.
Not-Used-Recently(NUR)
NUR 알고리즘은 최근에 사용하지 않은 페이지를 교체하는 방법이다. LRU 알고리즘과 근사하지만, 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지 않는 방식을 가지고 있다.