페이지 교체 알고리즘

Lys·2023년 11월 13일

운영체제

목록 보기

20/23

페이지 교체 알고리즘

페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시(페이지 부재) 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라고 한다.

프레임: 물리 메모리를 일정한 크기로 나눈 블록

페이지: 가상 메모리를 일정한 크기로 나눈 블록

페이지 교체 알고리즘은 page-fault 발생 비율을 줄이는 것을 목표로 한다.

페이지 교체 알고리즘 종류

FIFO - First In First Out : 가장 먼저 메모리에 올라온 페이지를 교체

OPT - Optimal : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체

LRU - Least Recently Used : 가장 오랫동안 사용되지 않은 페이지 교체

LFU - Least Frequently Used : 참조 횟수가 가장 작은 페이지 교체

MFU - Most Frequently used : 참조 횟수가 가장 많은 페이지 교체

NUR - Not Used Recently : 최근에 사용하지 않은 페이지 교체

FIFO(First in First out)

이름 그대로 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘이다.

구현이 간단하지만 성능은 좋지 않은 편이다.

들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장할 수 있다.

Belady`s Anomaly 현상이 발생할 수 있다.

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

OPT(Optimal)

앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘이다.

모든 페이지 교체 알고리즘 중 page-fault 발생이 가장 적다.

프로세스가 앞으로 사용할 페이지를 미리 알아야한다.

실제로 구현하기 거의 불가능한 알고리즘이다.

실제로 사용하기 보다는 연구 목적을 위해 사용된다.

Belady`s Anomaly 현상이 발생하지 않는다.

LRU(Least Recently Used)

가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘이다.

최적 알고리즘과 비슷한 효과를 낼 수 있다.

성능이 좋은 편이다.

많은 운영체제가 채택하는 알고리즘이다.

큐로 구현이 가능하며 사용한 데이터를 큐에서 제거하여 맨 위로다시 올리고, 프레임이 모자랄 경우 맨 아래에 있는 데이터를 삭제한다.

LFU(Least Frequently Used)

참조횟수가 가장 적은 페이지를 교체하는 알고리즘이다.

교체 대상이 여러 개라면 가장 오랫동안 사용하지 않은 페이지를 교체한다.

LRU는 직전 참조된 시점만을 반영하지만, LFU는 참조횟수를 통해 장기적 시간규모에서의 참조 성향을 고려할 수 있다.

가장 최근에 불러온 페이지가 교체될 수 있다.

구현하기에 복잡하고 막대한 오버헤드를 불러온다는 단점이 있다.

MFU(Most Frequently User)

LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다.

NUR = NRU(Not Used Recently, Not Recently Used)

최근에 사용하지 않은 페이지를 교체한다. (LRU를 근사한 알고리즘)

교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 못한다.

적은 오버헤드로 적절한 성능을 나타낸다.

동일 그룹 내에서 무작위로 선택한다.

각 페이지마다 두개의 비트 참조 비트(Reference Bit)와 변형 비트(Modified Bit, Birty Bit)가 사용된다.

참조 비트: 페이지가 참조되지 않았을 때 0, 호출되었을 때 1 (모든 참조비트를 주기적으로 0으로 변경)

변형 비트: 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때 1
우선순위: 참조비트 > 변형비트