운영체제 페이지 교체 알고리즘

제129회 예상문제(토픽)

 

정보관리 117회 4교시
4. 운영체제에서 페이지 교체 알고리즘을 사용한다.
가. 페이지 교체 알고리즘을 사용하는 이유에 대하여 설명하시오.
나. 페이지 교체 알고리즘의 종류를 나열하고, 각 종류별 동작 과정에 대하여 설명하시오.

 

문제4) 1) 페이지교체 알고리즘 사용 이유, 2) 페이지 교체 알고리즘 종류, 3) 각 종류별 동작과정

답)

I. 페이지 교체 알고리즘 사용 이유

페이징기법으로 메모리를 관리하는 운영체제에서 페이지 부재가 발생했을 경우 가상 기억장치의 필요한 페이지를 주기억장치의 어떤 페이지 프레임을 선택/교체하는지 결정하기 위해 사용

 

II. 페이지 교체 알고리즘의 종류

알고리즘	설명	특징
FIFO(First in First Out)	각 페이지가 주 기억장치에 적재될때마다 시간을 기억하여 가장 먼저, 가장 오래 있었던 페이지를 교체하는 방법	이해하기 쉬우며 프로그래밍 및 설계가 간단함
LRU(Least Recently Used)	최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법	각 페이지마다 Counter나 Stack을 두어 현 시점에서 가장 오랫동안 사용하지 않은 페이지를 교체함
LFU(Least Frequently Used)	사용 빈도가 가장 적은 페이지를 교체하는 기법	사용 여부를 확인하기 위하여 각 페이지마다 참조비트와 변형비트가 사용됨
OPT(Optiml replacement)	앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법	각 페이지의 호출 순서와 참조 상황을 미리 예측해야 하므로 실현 가능성 희박함

III. 오래된 페이지 교체 알고리즘 동작 과정

가 FIFO

각 페이지가 주기억 장치에 적재될 때마다 그 때의 시간을 기억시켜 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법

(FIFO Page Fault: 6회 발생)

 

나. LRU

최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법으로 시간적인 오버헤드가 발생함

LRU Page Fault: 5회 발생

 

IV. 최소 호출 예정 페이지 교체 알고리즘

가. LFU

사용빈도가 가장 적은 페이지를 교체하는 기법

LFU Page Fault: 5회 발생

 

나. OPT

페이지 부재횟수가 가장 적게 발생하는 가장 효율적인 알고리즘

OPT Page Fault: 4회 발생

 

-OPT 알고리즘이 페이지 부재횟수가 가정 적게 발생, 현실에서는 앞으로 사용되지 않을 페이지를 알 수없으므로 비현실적