[정보처리기사 실기] 페이지 교체 알고리즘
1. FIFO
1) 예제
3개의 페이지 프레임을 갖는 시스템에서 페이지 참조순서가 1,2,1,0,4,1,3 일때 FIFO 알고리즘에 의한 페이지 교체의 경우 프레임의 최종 상태는?
4 1 3
1 2 1 0 4 1 3
1 1 1 1 4 4 4
2 2 2 2 1 1
0 0 0 3
O O X O O O O - 6번의 페이지 부재가 발생했다.
2) 예제
3개의 페이지 프레임을 가진 기억장치에서 페이지 요청을 다음과 같은 페이지 번호 순으로 요청했을 때 교체 알고리즘으로 FIFO 방법을 사용한다면 몇번의 페이지 부재가 발생하는가?
(단, 현재 기억장치는 모두 비었다고 가정)
| 요청된 페이지 번호 순서 2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2 |
페이지 부재 - 9
| 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 |
| 2 | 2 | 2 | 2 | 5 | 5 | 5 | 5 | 3 | 3 | 3 | 3 |
| 3 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 5 | 5 | |
| 1 | 1 | 1 | 4 | 4 | 4 | 4 | 4 | 2 | |||
| O | O | X | O | O | O | O | X | O | X | O | O |
3) 예제
3개의 페이지를 수용할 수 있는 주기억 장치가 있으며 초기에는 모두 비어있다고 가정한다. 다음의 순서로 페이지 참조가 발생할 때 FIFO 페이지 교체 알고리즘을 사용할 경우 몇번의 페이지 결함이 발생하는가?
| 페이지 참조순서 1, 2, 3, 1, 2, 4, 1, 2, 5 |
7번
| 1 | 2 | 3 | 1 | 2 | 4 | 1 | 2 | 5 |
| 1 | 1 | 1 | 1 | 1 | 4 | 4 | 4 | 5 |
| 2 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | |
| 3 | 3 | 3 | 3 | 3 | 2 | 2 | ||
| O | O | O | X | X | O | O | O | O |
https://www.youtube.com/watch?v=qEgXhnujBA8&t=29s
2. LRU (Least Recently Used)
최근에 사용하지 않은 페이지 교체
1) 예제
3개의 페이지를 수용할 수 있는 주기억 장치가 있으며 초기에는 모두 비어있다고 가정한다. 다음의 순서로 페이지 참조가 발생할 때 LRU 페이지 교체 알고리즘을 사용할 경우 몇번의 페이지 결함이 발생하는가?
| 페이지 참조순서 1, 2, 3, 1, 2, 4, 1, 2, 5, 4 |
6번
| 1 | 2 | 3 | 1 | 2 | 4 | 1 | 2 | 5 | 4 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 4 |
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | |
| 3 | 3 | 3 | 4 | 4 | 4 | 5 | 5 | ||
| O | O | O | X | X | O | X | X | O | O |
2) 예제
3개의 페이지 프레임을 갖는 시스템에서 페이지 참조순서가 1,2,1,0,4,1,3 일때 LRU 알고리즘에 의한 페이지 교체의 경우 프레임의 최종 상태는?
1, 4, 3
| 1 | 2 | 1 | 0 | 4 | 1 | 3 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 4 | 4 | 4 | |
| 0 | 0 | 0 | 3 | |||
| O | O | X | O | O | X | O |
3) 예제
4개의 페이지를 수용할 수 있는 주기억 장치가 있으며 초기에는 모두 비어있다고 가정한다. 다음의 순서로 페이지 참조가 발생할 때 LRU 페이지 교체 알고리즘을 사용할 경우 몇번의 페이지 결함이 발생하는가?
| 페이지 참조순서 1, 2, 3, 1, 2, 4, 1, 2, 5 |
5회
| 1 | 2 | 3 | 1 | 2 | 4 | 1 | 2 | 5 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | |
| 3 | 3 | 3 | 3 | 3 | 3 | 5 | ||
| 4 | 4 | 4 | 4 | |||||
| O | O | O | X | X | O | X | X | O |
https://www.youtube.com/watch?v=9CCAK-N8Nwg
3. LFU (Least Frequently Used)
참조횟수가 적은 페이지 교체
1) 예제
3개의 페이지 프레임을 가진 기억장치에서 페이지 요청을 다음과 같은 페이지 번호 순으로 요청했을 때 교체 알고리즘으로 LFU 방법을 사용한다면 몇 번의 페이지 부재가 발생하는가?
(단, 현재 기억장치는 모두 비었다고 가정)
| 요청된 페이지 번호 순서 2, 3, 1, 2, 1, 2, 4, 2, 1, 3, 2 |
5번
위 헤더가 참조횟수이다.
| 2 | 3 | 1 | 2 | 1 | 2 | 4 | 2 | 1 | 3 | 2 |
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 3 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 3 | 3 | |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||
| O | O | O | X | X | X | O | X | X | O | X |
2) 예제
4개의 페이지 프레임을 가진 기억장치에서 페이지 요청을 다음과 같은 페이지 번호 순으로 요청했을 때 교체 알고리즘으로 LFU 방법을 사용한다면 페이지 대치의 최종 결과는?
(단, 현재 기억장치는 모두 비었다고 가정)
| 요청된 페이지 번호 순서 2, 3, 1, 3, 1, 2, 4, 5 |
2,3,1,5
| 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 | ||||||
| O | O | O | X | X | X | O | O |
그 외에도 OPT(나중계산), NUR(참조비트, 변형비트), SCR(FIFO 개선) 가 있음
https://www.youtube.com/watch?v=eyF_y15iYi4