다음은 가상 메모리의 페이지 교체 정책 중 최적(optimal) 알고리… | [9급 지방직 컴퓨터일반] 16년 1회차 기출문제 상세 페이지
1[9급 지방직 컴퓨터일반] 16년 1회차
다음은 가상 메모리의 페이지 교체 정책 중 최적(optimal) 알고리즘을 적용하여 페이지를 할당한 예이다. 참조열 순으로 페이지가 참조될 때, 페이지 부재(page fault)가 6회 발생하였다. 동일한 조건 하에서 LRU(Least Recently Used) 알고리즘을 적용할 경우 페이지 부재가 몇 회 발생하는가?
| 참조열 | 1 | 2 | 0 | 3 | 0 | 5 | 2 | 3 | 7 | 5 | 3 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 페이지 프레임 | 1 | 1 | 1 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | 7 | 7 | 7 | ||
| 0 | 0 | 0 | 5 | 5 | 5 | 5 | 5 | 5 | |||
| F | F | F | F | F | F |
1
6
2
7
3
8
4
9
해설
프레임 3개에 LRU를 적용하면 페이지 부재는 9회 발생한다.
LRU는 부재 시 가장 오래전에 참조된 페이지를 교체한다. 1, 2, 0, 3 참조에서 4회 부재(3이 들어올 때 1 교체), 0은 적중, 5는 2를 교체, 2는 3을 교체, 3은 0을 교체, 7은 5를 교체, 5는 2를 교체해 모두 부재이고, 마지막 3만 적중한다.
참조 11회 중 적중은 0과 마지막 3의 2회뿐이므로 부재는 11 − 2 = 9회이다.
- 6회는 미래 참조를 아는 최적 알고리즘의 결과로, 최적 알고리즘은 부재 횟수의 하한이므로 LRU는 이보다 많거나 같다.
- 7회·8회는 2, 3, 5 재참조 직전에 해당 페이지가 이미 LRU로 밀려난 점을 빠뜨린 값이다.
내용에 오류가 있거나 최신 법령·기준과 다른 부분이 보이면 알려주세요. 확인 후 반영하겠습니다.