[ 페이지 교체 알고리즘의 종류 ]
- FIFO(First In First Out): 가장 먼저 들어온 페이지를 교체하는 기법
- LRU(Least Recently Used): 최근에 사용하지 않은(참조하지 않은) 페이지를 교체하는 기법
- LFU(Least Frequently Used): 참조횟수가 가장 적은 페이지를 교체하는 기법
- OPT: 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법 (나중에 교체될 페이지를 계산)
- NUR: 참조비트와 변형비트를 두어 둘 다 사용하면 나중에 교체하는 기법
- SCR: FIFO를 개선한 교체 기법
계산 문제는 FIFO, LRU, LFU가 주로 나오기 때문에 요 3가지만 익혀보자~
[ FIFO ]
1. 3개의 페이지 프레임을 갖는 시스템에서 페이지 참조 순서가 1, 2, 1, 0, 4, 1, 3일 경우 FIFO 알고리즘에 의한 페이지 교체의 경우 프레임의 최종 상태는?
[ 답 ]
4, 1, 3
[ 풀이 ]
FIFO 알고리즘에 의한 페이지 프레임 변화는 아래와 같다.
페이지 프레임
| 1 | 1 | 1 | 1 | 2 | 0 | 4 |
| 2 | 2 | 2 | 0 | 4 | 1 | |
| 0 | 4 | 1 | 3 |
따라서 프레임의 최종 상태는 4, 1, 3
2. 3개의 페이지 프레임(Frame)을 가진 기억장치에서 페이지 요청을 다음과 같은 페이지 번호 순으로 요청했을 때 교체 알고리즘으로 FIFO 방법을 사용한다면 몇 번의 페이지 부재(Fault)가 발생하는가? (단, 현재 기억장치는 모두 비어있다고 가정한다.)
| 요청된 페이지 번호의 순서: 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 |
[ 답 ]
9번
[ 풀이 ]
페이지 부재(Fault)는 참조하려는 페이지가 현재 프레임에 있지 않을 때 발생한다.
표에서 페이지 부재가 발생했을 경우 O로 표기한다.
페이지 프레임
| O | O | X | O | O | O |
| 2 | 2 | 2 | 2 | 3 | 1 |
| 3 | 3 | 3 | 1 | 5 | |
| 1 | 5 | 2 |
이어서 7번째~마지막 페이지 교체
| O | X | O | X | O | O |
| 5 | 5 | 2 | 2 | 4 | 3 |
| 2 | 2 | 4 | 4 | 3 | 5 |
| 4 | 4 | 3 | 3 | 5 | 2 |
따라서 페이지 부재 횟수는 총 9번
3. 3개의 페이지를 수용할 수 있는 주기억장치가 있으며, 초기에는 모두 비어 있다고 가정한다. 다음의 순서로 페이지 참조가 발생했을 때, FIFO 페이지 교체 알고리즘을 사용할 경우 몇 번의 페이지 결함이 발생하는가?
| 페이지 참조 순서: 1, 2, 3, 1, 2, 4, 1, 2, 5 |
[ 답 ]
7
[ 풀이 ]
페이지 부재(Fault)는 참조하려는 페이지가 현재 프레임에 있지 않을 때 발생한다.
표에서 페이지 부재가 발생했을 경우 O로 표기한다.
페이지 프레임
| O | O | O | X | X | O | O | O | O |
| 1 | 1 | 1 | 1 | 1 | 2 | 3 | 4 | 1 |
| 2 | 2 | 2 | 2 | 3 | 4 | 1 | 2 | |
| 3 | 3 | 3 | 4 | 1 | 2 | 5 |
따라서 페이지 부재 횟수는 총 7번
[ LRU(Least Recently Used) ]
1. 3개의 페이지를 수용할 수 있는 주기억장치가 있으며, 다음의 순서로 페이지 참조가 발생할 때, LRU(Least Recently Used) 페이지 교체 알고리즘을 사용할 경우 몇 번의 페이지 결함이 발생하는가?
| 페이지 참조 순서: 1, 2, 3, 1, 2, 4, 1, 2, 5, 4 |
[ 답 ]
6
[ 풀이 ]
페이지 부재(Fault)는 참조하려는 페이지가 현재 프레임에 있지 않을 때 발생한다.
표에서 페이지 부재가 발생했을 경우 O로 표기한다.
페이지 프레임
| O | O | O | X | X | O | X | X | O | O |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 |
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 5 | |
| 3 | 3 | 3 | 4 | 4 | 4 | 5 | 4 |
따라서 페이지 부재 횟수는 총 6번
2. 3개의 페이지 프레임을 갖는 시스템에서 페이지 참조 순서가 1, 2, 1, 0, 4, 1, 3 일 경우 LRU(Least Recently Used) 알고리즘에 의한 페이지 대체의 최종 결과는?
[ 답 ]
1, 4, 3
[ 풀이 ]
LRU 알고리즘에 의한 페이지 프레임 변화는 아래와 같다.
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 0 | 0 | 4 | |
| 0 | 4 | 4 | 3 |
따라서 페이지 대체의 최종 결과는 1, 4, 3
3. 4개의 페이지를 수용할 수 있는 주기억장치가 있으며, 초기에는 모두 비어 있다고 가정한다. 다음의 순서로 페이지 참조가 발생할 때, LRU 페이지 교체 알고리즘을 사용할 경우 몇 번의 페이지 결함이 발생하는가?
| 페이지 참조 순서: 1, 2, 3, 1, 2, 4, 1, 2, 5 |
[ 답 ]
5회
[ 풀이 ]
페이지 부재(Fault)는 참조하려는 페이지가 현재 프레임에 있지 않을 때 발생한다.
표에서 페이지 부재가 발생했을 경우 O로 표기한다.
페이지 프레임
| O | O | O | X | X | O | X | X | O |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | |
| 3 | 3 | 3 | 4 | 4 | 4 | 5 |
따라서 페이지 부재 횟수는 총 5번
[ LFU(Least Frequently Used) ]
1. 3개의 페이지 프레임으로 구성된 기억장치에서 다음과 같은 순서대로 페이지 요청이 일어날 때, 페이지 교체 알고리즘으로 LFU(Least Frequently Used)를 사용한다면 몇 번의 페이지 부재가 발생하는가? (단, 초기 페이지 프레임은 비어있다고 가정한다.)
| 요청된 페이지 번호의 순서: 2, 3, 1, 2, 1, 2, 4, 2, 1, 3, 2 |
[ 답 ]
5번
[ 풀이 ]
페이지 부재(Fault)는 참조하려는 페이지가 현재 프레임에 있지 않을 때 발생한다.
표에서 페이지 부재가 발생했을 경우 O로 표기한다.
페이지 프레임
| O | O | O | X | X |
| 2 | 2 | 2 | 2 | 2 |
| 3 | 3 | 3 | 3 | |
| 1 | 1 | 1 |
이어서 6번째 ~ 마지막 페이지 교체
| X | O | X | X | O | X |
| 2 | 2 | 2 | 2 | 2 | 2 |
| 3 | 4 | 4 | 4 | 3 | 3 |
| 1 | 1 | 1 | 1 | 1 | 1 |
7번째에서 각 페이지의 참조횟수
1의 참조횟수: 2
2의 참조횟수: 3
3의 참조횟수: 1
해당 시점까지 3의 참조횟수가 가장 적기 때문에 3이 4로 교체된다.
따라서 페이지 부재 횟수는 총 5번
2. 4개의 페이지 프레임으로 구성된 기억장치에서 다음과 같은 순서대로 페이지 요청이 일어날 때, 페이지 교체 알고리즘으로 LFU(Least Frequently Used)를 사용한다면 페이지 대치의 최종 결과는? (단, 초기 페이지 프레임은 비어있다고 가정한다.)
| 요청된 페이지 번호의 순서: 2, 3, 1, 3, 1, 2, 4, 5 |
[ 답 ]
2, 3, 1, 5
[ 풀이 ]
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 3 | 3 | 3 | 3 | 3 | 3 | 3 | |
| 1 | 1 | 1 | 1 | 1 | 1 | ||
| 4 | 4 | 5 |
따라서 페이지 대체의 최종 결과는 2, 3, 1, 5
