정보처리기사 실기 프로그래밍 기출 페이지 교체 알고리즘 FIFO / LRU / LFU 문제 풀이
정보처리기사
정보처리기사 실기 프로그래밍 기출 페이지 교체 알고리즘 FIFO / LRU / LFU 문제 풀이
페이지 교체 알고리즘
헷갈리지말 것*
"페이지의 부재 발생" == 페이지가 새로 적재된다
💡 FIFO 페이지 교체 알고리즘 (First In First Out)
- 시간상으로 메모리에 가장 먼저 들어온 페이지를 먼저 교체하는 알고리즘
📝 문제풀이
3개의 페이지 프레임을 갖는 시스템에서 페이지 참조 순서가 1, 2, 1, 0, 4, 1, 3일 경우 FIFO 알고리즘에 의한 페이지 교체의 경우 프레임의 최종 상태를 쓰시오.
프레임이 3이므로 순서대로 1, 2까지 넣는다. 다음 1은 이미 할당되어 있으므로 패스한다.
다음 0을 세번째로 넣는다. 여기까지 넣으면 1, 2, 0으로 현재 프레임이 전부 찼다.
다음은 4인데 가장 먼저 들어온 페이지 먼저 나가므로 맨 앞에서 들어갔던 1을 빼고 그 자리에 4를 넣어 4, 2, 0이 된다.
그 다음 다시 1이 들어가는데 현재 프레임 4, 2, 0에서 두번째로 들어왔던 2가 빠지고 그 자리에 1이 들어간다. 그러면 4, 1, 0이 된다.
마지막으로 3이 들어가는데, 이 때도 마찬가지로 4, 1, 0중에 가장 먼저 들어온 값인 0이 빠지고 3으로 채운다.
그러면 아래와 같은 프레임 최종 상태가 된다.
4, 1, 3
💡 LRU 페이지 교체 알고리즘 (Least Recently Used)
- 메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘
📝 문제풀이
3개의 페이지를 수용할 수 있는 주기억장치가 있으며, 초기에는 모두 비어있다고 가정한다. 다음과 같은 순서로 페이지 참조가 발생할 때, 페이지 교체 알고리즘으로 LRU(Least Recently Used)를 사용한다면 몇 번의 페이지 결함이 발생하는지 쓰시오.
페이지 참조 순서: 1, 2, 3, 1, 2, 4, 1, 2, 5, 4
위의 이미지를 참고하자. 3개를 수용할 수 있는 페이지를 그린다.
페이지 결함 일어나는 횟수를 cnt라고 하고 cnt값이라고 부르겠다.
페이지 결함 횟수 쉽게 구하기*
cnt값을 일일이 기억하면서 하지 않더라도,처음 프레임에 들어간 n개의 페이지 + x로 지운 횟수 = 결함 횟수쉽게 셀 수 있으므로 기억하자.
편의상 위에서부터 들어오는 순서로 넣는다. 보기의 1, 2, 3이 먼저 들어가므로 3번의 페이지 적재, 즉 cnt = 3이 된다.
다음에 들어오는 1은 이미 프레임에 들어있는 값이므로 페이지 결함은 일어나지 않고, 대신 다시 사용되었으므로 그 표시로 1을 다시 적어준다*. 2도 마찬가지로 페이지 결함은 일어나지 않지만 다시 쓰였다는 표시*로 옆에 2를 적는다.
LRU는 다시 참조된 페이지* 표시가 중요!
가장 오래 사용되지 않은 것을 버려야 함으로 표시하여 가장 오래 전 참조된 페이지를 버린다.
그 다음 4가 들어가야하는데, 4는 새로 적재되어야 하므로 페이지 결함이 일어난다. cnt = 4가 된다. 이때 가장 오랫동안 쓰이지 않은 페이지는 3이므로 3을 버리고 그 자리에 4를 넣는다.
다음은 1, 2가 나오는데 이 두 페이지는 이미 적재되어 있으므로 결함은 없지만 다시 쓰였으므로 옆 자리에 다시 적어준다.
5가 들어오면 페이지 결함이 발생하는데, 기존 프레임의 1, 2, 4중에 4가 가장 오래됐으므로 4가 빠지고 그자리에 5가 들어간다. cnt = 5
그 다음은 다시 4가 들어오는데, 기존 프레임에 1, 2, 5가 들어있고 이 중에 가장 오랫동안 참조되지 않은 1이 빠지고 그 자리에 4가 들어간다. cnt = 6
6번
💡 LFU 페이지 교체 알고리즘 (Least Frequently Used)
- 현재 프레임에 있는 페이지들이 그동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 교체시키는 알고리즘
📝 문제풀이
3개의 페이지 프레임으로 구성된 기억장치에서 다음과 같은 순서대로 페이지 요청이 일어날 때, 페이지 교체 알고리즘으로 LFU(Least Frequently Used)를 사용한다면 몇 번의 페이지 부재가 발생하는가? (단, 초기 페이지 프레임은 비어있다고 가정한다.)
요청된 페이지 번호의 순서: 2, 3, 1, 2, 1, 2, 4, 2, 1, 3, 2
LFU 알고리즘의 경우 어떤 페이지를 먼저 교체할지의 기준이 현재 프레임에 들어있는 페이지가 얼마나 자주 쓰이고 있냐이다. 앞에서 자주 쓰인 페이지는 앞으로도 자주 쓰일 가능성이 높다는 것에 의미를 두기 때문이다.
페이지 부재를 계산하는 과정은 비슷하다. 위의 그림을 참고하면서 보자.
일단 페이지 프레임이 3이므로 3개의 페이지를 순서대로 2, 3, 1 넣어준다. 일단 부재값 cnt = 3 이다.
다음은 2, 1, 2인데 묶어서 보는 이유는 어차피 적재된 페이지이므로 부재가 일어나지 않기 때문이고, 대신 자주 쓰인 것을 기억하기 위해 같은 위치의 옆자리에 사용된 횟수만큼 2, 2와 1을 각각 적어준다.
그 다음은 4인데 기존 프레임에 2, 3, 1이 적재되어 있으므로 4를 넣기 위해 페이지 하나를 빼야하는데, 2는 지금껏 3번 사용됐고, 1은 두번 사용됐지만 3은 사용된 적이 없으므로 가장 필요없는 것으로 판단, 3을 제거하고 그 자리에 4를 넣는다. cnt = 4
다음으로 2, 1이 들어오는데 이미 적재된 페이지들이므로 또 옆에 각각 2, 1을 적어준다. 부재는 일어나지 않는다.
그 다음은 3이 들어오는데, 3이 들어갈 자리는 4가 있는 자리다. 기존 프레임의 2는 지금까지 4번 쓰였고, 1은 3번 쓰였는데 4는 1번밖에 안쓰였기 때문이다. c = 5
마지막은 2가 들어오는데 이미 적재된 페이지이므로 무시한다. 따라서 부재 횟수는 아래와 같다.
5번
🙋🏻 참고하면 좋을 사이트
🔗 [코드연구소] 페이지 교체 알고리즘
🔗 [평범한 공대생의 개발 노트] 페이지 교체 알고리즘
🙋🏻 참고한 곳
🔗 홍달쌤 유튜브 🔗 홍달쌤의 정보처리기사 실기 책
