페이지 폴트가 발생했을때 교체 방법
// OPT, FIFO, LRU, LFU, NUR, SCR 등
OPT
- 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법
- 각 페이지의 호출 순서와 참조 상황을 미리 예측해야 하므로 실현 가능성이 희박
참조페이지 | 2 | 3 | 2 | 1 | 5 | 2 | 3 | 5 |
페이지 프레임 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
3 | 3 | 3 | 3 | 3 | 3 | 3 | ||
1 | 5 | 5 | 5 | 5 |
페이지 폴트 4번 (하늘색 셀)
FIFO(First In First Out)
- 각 페이지가 주기억장치에 적재될 때마다 그때의 시간을 기억시켜 가장 먼저
들어와서 가장 오래 있었던 페이지를 교체하는 기법
`- 벨레이디의 모순현상이 발생
: 페이지 프레임 수가 많으면 페이지 부재의 수가 줄어드는 것이 일반적이지만,
페이지 프레임 수를 증가시켰는데도 불구하고 페이지 폴트가 더 많이 일어나는 현상
참조페이지 |
2 |
3 |
2 |
1 |
5 |
2 |
3 |
5 |
페이지 프레임 |
2 |
2 |
2 |
2 |
5 |
5 |
5 |
5 |
|
3 |
3 |
3 |
3 |
2 |
2 |
2 |
|
|
|
|
1 |
1 |
1 |
3 |
3 |
페이지 폴트 6번 (하늘색 셀)
LRU(Least Recently Used)
- 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법
- 각 페이지마다 계수기나 스택을 두어 현 시점에서 가장 오랫동안 사용하지 않은,
즉 가장 오래 전에 사용된 페이지를 교체한다.
- 계수기나 스택과 같은 별도의 하드웨어가 필요하며, 시간적인 오버헤드가 발생
참조페이지 | 2 | 3 | 2 | 1 | 5 | 2 | 3 | 5 |
페이지 프레임 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
3 | 3 | 3 | 5 | 5 | 5 | 5 | ||
1 | 1 | 1 | 3 | 3 |
페이지 폴트 5번 (하늘색 셀)
LFU(Least Frequently Used)
- 사용 빈도가 가장 적은 페이지를 교체하는 기법
참조페이지 | 2 | 3 | 1 | 3 | 1 | 2 | 4 | 5 |
페이지 프레임 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
3 | 3 | 3 | 3 | 3 | 3 | 3 | ||
1 | 1 | 1 | 1 | 1 | 1 | |||
|
|
|
|
|
| 4 | 5 |
페이지 폴트 5번 (하늘색 셀)
NUR(Not Used Recently)
- LRU와 비슷한 알고리즘으로, 최근에 사용하지 않은 페이지를 교체하는 기법
- 최근에 사용되지 않은 페이지는 향후에도 사용되지 않을 가능성이 높다는 것을 전제로,
LRU에서 나타나는 시간적인 오버헤드를 줄일 수 있다.
- 최근의 사용 여부를 확인하기 위해서 각 페이지마다 두 개의 비트,
즉 참조 비트(Reference Bit)와 변형 비트(Modified Bit, Dirty Bit)가 사용된다.
- 참조 비트 : 페이지가 호출되지 않았을 때는 0, 호출되었을 때는 1로 저장된다.
- 변형 비트 : 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때는 1로 지정된다.
참조 비트 |
변형 비트 |
교체 순서 |
0 |
0 |
1 |
0 |
1 |
2 |
1 |
0 |
3 |
1 |
1 |
4 |
SCR(Second Chance Replacement)
- 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것으로,
FIFO 기법의 단점을 보완하는 기법이다.
- 각 페이지마다 참조 비트를 두고, FIFO 기법을 이용하여 페이지 교체 수행중 참조
비트가 0일 경우에는 교체하고, 참조비트가 1일 경우에는 참조 비트를 0으로 지정한 후
FIFO 리스트의 맨 마지막으로 피드백시켜 다음 순서를 기다리게 한다.
'ComputerScience > OperatingSystem' 카테고리의 다른 글
| 디스크 스케줄링 (0) | 2017.10.16 |
|---|---|
| 가상기억장치 구현 기법 (0) | 2017.10.16 |
| 단편화 (0) | 2017.10.16 |
| 주기억장치 할당 기법 - 연속 할당 기법 (0) | 2017.10.16 |
| 교착상태 (0) | 2017.10.16 |