페이지 교체 알고리즘
페이지 교체를 위해서는 현재 메인 메모리에 존재하는 페이지를 가상 메모리로 저장한 후에,
가상메모리에서 조회한 페이지를 메인 메모리에 올려야한다.
-
프레임
물리 메모리를 일정한 크기로 나눈 블록 -
페이지
가상 메모리를 일정한 크기로 나눈 블록
페이지 교체 알고리즘의 종류
-
OPT - Optimal
앞으로 가장 오랫동안 사용되지 않을 페이지 교체 -
FIFO - First In First Out
제일 먼저 들어와있던 페이지를 교체 -
LRU - Least Recently Used
가장 오랫동안 사용되지 않은 페이지 교체 -
LFU - Least Frequently Used
참조 횟수가 가장 적은 페이지 교체 -
MFU - Most Frequently Used
참조 횟수가 가장 많은 페이지 교체 -
NUR - Not Used Recently
최근에 사용하지 않은 페이지 교체
OPT(Optimal)
앞으로 가장 오랫동안 사용되지 않을 페이지 교체
- 가장 이상적이다.
- 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다. -> 불가능의 영역
- 비교 연구 목적을 위해 사용된다.
FIFO(First In First Out)
가장 먼저 들어온 페이지를 교체
- 메모리에 가장 먼저 올라온 페이지를 먼저 내보냈다.
- 간단하고, 초기화 코드에 대해 적절한 방법이다.
- 들어온 시간을 저장하거나 올라온 순서를 큐에 저장한다.
- 직관적으로 생각할 때 프레임 수가 많아질 수록 페이지 결함의 횟수는 감소한다.
하지만 Belady's Anomaly(FIFO Anomlay) 실제로 그렇지 않게 되는 현상이 나타날 수 있다.
Belady's Anomaly (FIFO Anomaly)
벨라디의 이상현상은 페이지 교체 알고리즘에서 발생하는 비정상적인 현상이다.
페이지 프레임 수를 늘렸음에도 불구하고 페이지 폴트가 오히려 더 증가하는 현상이다.
위 사진에서 보면 전체 프레임 수가 3에서 4로 증가할 때 페이지 폴트가 증가하는 모습을 볼 수 있다.
아래 그림은 3개의 페이지 프레임을 가질 경우의 예시다.
9번의 페이지 폴트와 3번의 페이지 히트가 발생했다.
아래 그림은 페이지를 4개로 증가했을 때다.
10번의 페이지 폴트와 2번의 페이지 히트가 발생했다.
페이지 프레임을 더 많이 사용하지만, 페이지 폴트가 증가하는 이상현상(anomaly)이 발생했다.
LRU (Least Recently Used)
가장 오랫동안 사용하지 않은 페이지를 교체한다.
-
가장 오랫동안 사용되지 않았던 데이터라면 앞으로도 사용할 확률이 적다.
-
사용된 시간을 알 수 있는 부분을 저장하여 가장 오랫동안 참조되지 않는 데이터를 제거한다. (페이지마다
카운터필요하다.) -
카운터(Counter)
각 페이지별로 존재하는논리적인 시계(Logical Clock)로, 해당 페이지가 사용될 때마다 0으로 클리어시킨 후 시간을 증가시킨다.
LRU에서는 시간이 가장 오래된 페이지를 교체한다. -
단점
프로세스가 메인 메모리에 접근할 때마다 참조된 페이지 시간을 기록해야하므로 오버헤드가 발생.
LFU (Least Frequently Used)
참조 횟수가 가장 낮은 페이지를 교체한다.
-
페이지의 참조 횟수로 교체할 페이지 결정한다.
-
LRU 는 직전 참조된 시점만을 반영하지만, LFU는 참조횟수를 통해 장기적 시간 규모에서 참조 성향 고려할 수 있다.
-
단점
가장 최근에 불러온 페이지가 교체될 수 있다.
MFU (Most Frequently Used)
가장 많이 참조된 페이지를 교체한다.
- 참조 횟수가 적은 페이지가 최근 참조된 것으로 보고 앞으로 사용될 가능성이 높다고 판단한 알고리즘이다.
NUR/NRU (Not Used Recently, Not Recently Used)
최근에 사용하지 않은 페이지를 교체한다.
- 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 못한다.
- 적은 오버헤드로 적절한 성능을 낸다.
- 동일 그룹 내에서 선택 무작위
- 각 페이지마다 두 개의 비트가 사용된다.
참조 비트
페이지가 참조되지 않았을 때 0, 참조되었을 때 1 (모든 참조 비트를 주기적으로 0으로 변경)변형 비트
페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때 1
- 우선순위 : 참조 비트 > 변형 비트
FIFO 알고리즘 기반
FIFO 페이지 교체 알고리즘을 기반으로 한다.
즉큐를 사용하되페이지 접근할 때마다 순서의 변화를 주어 성능을 향상한 알고리즘들이다.
2차 기회 페이지 교체 알고리즘 (Second Chance)
FIFO 알고리즘 기반이다. 사용된 페이지를 큐의 맨 뒤로 보낸다.
- FIFO는 사용되었어도 먼저 들어온 페이지를
사용유무 관계없이 먼저 교체하지만,
Second chance 알고리즘에서는 먼저 들어온 페이지라도사용했다면 다시 큐의 뒤로 보내교체되지 않도록 방지한다.
시계 알고리즘
원형 큐를 사용해서 대상 페이지를 교체한다.
위 그림과 같이 대상 페이지를 가리키는 포인터를 사용하는 데, 이 포인터가 큐의 맨 아래로 내려가면
시계처럼 다음번에는 큐의 처음을 가리키게 된다.
기본 원리
위 그림은 시계 알고리즘의 동작 과정을 나타낸 것이다.
- 시계 알고리즘은
참조 비트를 사용하며 성공적으로참조 시 0에서 1로 변경된다. 대상 페이지가 교체되면 포인터가 다음 대상 페이지를 가리킨다.- 대상 포인터가 가리키는 페이지의 참조 횟수가 1일 경우 0으로 변경하고 다음 대상 포인터로 건너뛴다.
위 그림의 동작 방식은
-
1번
A 페이지가 큐에 들어온다.
(페이지 폴트 발생) -
2번
B 페이지가 큐에 들어온다.
(페이지 폴트 발생) -
3번
C 페이지가 큐에 들어온다.
(페이지 폴트 발생) -
4번
D 페이지를 요구하고 대상 포인터는 A를 가리키고 있다.
큐에 D페이지가 없으므로 A 제거 후 D로 교체.
대상 포인터는 다음 페이지인 B 를 가리킨다.
(페이지 폴트 발생) -
5번
B 페이지를 요구하고, 대상 포인터는 B를 가리키고 있다.
참조 성공했으므로 B의 참조횟수는 1로 증가한다.
대상 포인터는 B의 참조횟수를 0으로 변경하고 다음 페이지를 가리킨다. -
6번
A 페이지를 요구하고 대상 포인터는 C를 가리키고 있다.
큐에 A페이지가 없으므로 C 제거 후 A로 교체.
대상 포인터는 다음 페이지인 D를 가리킨다.
(페이지 폴트 발생) -
7번
B 페이지를 요구한다.
참조 성공했으므로 B페이지의 참조 횟수를 1로 변경시킨다. -
8번
A 페이지를 요구한다.
참조 성공했으므로 A페이지의 참조 횟수를 1로 변경시킨다. -
9번
C 페이지를 요구하고, 대상 포인터는 D를 가리킨다.
큐에 C페이지가 없으므로 D 제거 후 C로 교체
대상 포인터는 다음 페이지인 B를 가리키지만 참조횟수가 1이라 0으로 변경 후 그 다음 페이지인 A를 가리킨다.
A 페이지도 참조횟수가 1이라 0으로 변경 후 그 다음 페이지인 C페이지를 가리킨다.
(페이지 폴트 발생) -
10번
A 페이지를 요구한다.
참조 성공했으므로 A 페이지의 참조 횟수를 1로 변경시킨다.
레퍼런스
