FIFO 페이지 교체 알고리즘
정처기 공부하다 답답해서 적는 FIFO 페이지 교체 알고리즘 계산법 설명!
먼저, FIFO에 대해서 알고 넘어가는 게 이해에 도움이 될 듯하다.
계산법만 궁금하신 분은 바로 4번으로 skip!
1. FIFO란?
-First In Fisrt Out의 약어로 선입선출이라고도 한다.
-FIFO는 '큐'라는 자료구조를 참고하면 이해하기가 쉬운데, 가로로 긴 파이프 모형을 상상하고 한쪽에 구슬을 넣으면 자연스럽게 다른 한쪽은 그 구슬이 나오게 되는 형태를 상상하면 된다. 한쪽은 입력만 한쪽은 출력만 실행하는 것.
-아래의 이미지가 큐 자료구조로, 넣은(줄을 선) 순서대로 먼저 들어온 게 먼저 나간다고 이해하면 쉽다.
2. 페이지 교체 알고리즘 이란?
-메모리에 요청한 페이지가 존재하지 않는 페이지 부재 현상이 발생하여 메모리(CPU)에 해당 페이지를 적재하려 할 때, 메모리에 남아 있는 공간이 없어 현재 메모리에 있는 페이지 중에 내보낼 페이지를 결정하는 알고리즘.
3. 페이지 부재(Page Fault) 란?
-CPU에서 현재 요청한 페이지가 메모리에 없어 무효로 세팅되어 있는 경우로, 페이지를 디스크에서 읽어오는 과정에서 overhead가 발생하여 성능에 큰 영향을 미친다.
4. FIFO 페이지 교체 알고리즘 계산법
| 참조페이지 | 2 | 3 | 2 | 1 | 5 | 2 | 3 | 5 |
| 주기억장치 | ||||||||
| 페이지부재 |
-페이지 교체 알고리즘 계산법은 표를 그려 이해하는데, 먼저 위의 빈 표를 그리고 참조할 페이지 수만큼 표의 열을 추가해 그린다. 알고리즘의 특성대로 참조 페이지를 넣어주는 과정을 표로 그린다고 생각하면 된다.
-아래에서 위로, 위에서 아래로 표의 세로 한 줄이 위에서 말한 큐가 되어 입력된다고 생각하면 되는데, 아래에서 위로 넣는다고 생각하는 게 조금 더 쉬운 것 같아 해당 방법으로 설명할 예정.
-FIFO의 경우에는 들어온 순서대로 삭제되기 때문에, 제일 안쪽에 넣은 게 삭제의 대상이 되어 표의 다음 세로줄에는 삭제되고 이후에 들어온 페이지로 채워진다.
-넣으려는 페이지가 이미 주기억 장치에 있다면 주기억 장치에 다시 적재할 이유가 없기 때문에, 페이지 부재가 발생하지 않는다.
표를 채워 계산해 보자면,
다시 정리!
1) 세로줄마다 알고리즘대로 채워가면 되고,
2) 주기억 장치에 새로 해당 페이지를 적게 되면 해당 페이지 값이 페이지 부재가 발생한 것
| 참조페이지 | 2 | 3 | 2 | 1 | 5 | 2 | 3 | 5 |
| 주기억장치 (↑in ) |
2 | 2 | 2 | 2 | 3 | 1 | 5 | 5 |
| 3 | 3 | 3 | 1 | 5 | 2 | 2 | ||
| 1 | 5 | 2 | 3 | 3 | ||||
| 페이지부재 | o | o | x | o | o | o | o | x |
-3번째 페이지인 2는 이미 존재하는 페이지이기 때문에 페이지 부재가 발생하지 않아, 주기억 장치에 다시 적재되지 않았다.
-4번째 페이지인 1에서 2가 제일 먼저 들어와 삭제 대상이 되어 다음 페이지 부재가 발생한 세로줄에서는 삭제되고, 이후의 페이지로 채워졌다.
-위의 두 설명이 반복된다.
-FIFO페이지 교체 알고리즘대로 참조 페이지의 페이지 부재를 계산한다면 6번의 Page Fault가 발생하게 된다!
끝!
도움이 되었다면 공감 꾹! 클릭해 주세요~