[문제해설] 3개의 페이지 프레임을 가진 주기억장치 FIFO 교체알고리즘을 사용할 경우 페이지 부재는 몇 회 발생하는가?

전자계산기조직응용기사 실기 필답형 기출문제 (FIFO 페이지 교체 알고리즘)- 2008년3회, 2013년1회, 2015년3회, 2017년1회

---

3개의 페이지 프레임을 가진 주기억장치 FIFO 교체알고리즘을 사용할 경우 페이지 부재는 몇 회 발생하는가?

참조 페이지 순서 : 2, 3, 2, 1, 5, 2, 4, 3, 2, 5

 

 

 

 

---

- 문제 해설 -

가상 메모리(Virtual Memory)는 실제 물리 메모리보다 더 큰 용량의 프로그램을 실행시키기 위하여, 용량이 상대적으로 큰 보조기억장치를 주기억장치처럼 사용하는 것입니다. 하지만, 이것은 CPU를 속이는 것일 뿐, 실제 프로그램이 실행 상태로 있으려면 주기억장치에 적재되어 있어야 합니다. 페이징 기법은 덩치가 큰 프로그램을 페이지 단위로 쪼개는 것과 비슷한 방법인데, CPU가 메모리에 적재되어 있지 않은 페이지를 요구하는 것을 페이지 부재(page fault)라고 하여, 이때 이미 상주되어 있는 페이지를 희생(victim) 시킨 후, 필요한 페이지를 보조기억장치로 가져옵니다.

위 그림처럼 보조기억장치에 있는 페이지를 주기억장치로 적재시키기 위해 기존에 페이지 중 어떤 페이지를 희생(victim) 시킬 것인지를 결정하는 것이 페이지 표체 알고리즘입니다.

주요 페이지 교체 알고리즘은 위 표와 같습니다. FIFO와 LRU는 반드시 알고리즘을 정확히 이해하고 있어야 합니다.

그럼 문제를 풀어보겠습니다.

문제에선 3개의 페이지 프레임을 가지고 있다는 조건이 주어졌습니다. 프레임은 주기억장치에서 하나의 페이지를 담을 수 있는 파티션입니다. 3개의 프레임과 10개의 대기 큐에 있는 페이지 번호를 표기하기 위해 표를 하나 그립니다.

이제 문제에서 주어진 참조 페이지 순서대로 페이지는 기입하면 됩니다. 단, 페이지는 넣을 때, 프레임 중에 이미 존재 여부를 확인하여야 합니다. 우선 처음 2개(2,3)를 기입해보겠습니다.

위처럼 2와 3을 순서대로 넣을 때마다 세 개의 프레임에서는 2와 3이 없었습니다. 없었던 상태를 페이지 부재 상태라고 합니다. 2회 발생을 했습니다. 페이지 폴트가 발생한 곳은 붉은색으로 표시하겠습니다. 그다음 T3에는 페이지 2를 요구합니다. 이때는 프레임 1에 이미 2가 존재하므로, 페이지 폴트가 발생하지 않습니다.

페이지 폴트가 발생하지 않는 경우는 위처럼 ○로 표시하겠습니다. 그럼 다음 순서대로 인 1과 5를 넣어 보겠습니다.

T4에서 1은 비어있는 프레임 3에 넣었습니다. 물론 주기억장치에 없었으니 페이지 부재가 발생했습니다. T5에서 5를 넣을 때는 빈 프레임이 없습니다. 그래서 FIFO 알고리즘이 가동됩니다. FIFO알고리즘은 맨 처음 들어온 페이지를 희생시키는 알고리즘입니다. 그래서 맨 처음(T1) 들어왔던 2를 희생시키고 프레임 1에 5를 넣습니다. 물론 이때도 5가 없었으니 페이지 부재는 발생합니다. 이런 요령으로 나머지 페이지를 순서대로 넣어보겠습니다.

이렇게 결과가 나왔습니다. 페이지 부재의 횟수를 구하는 것이니, 붉은색으로 표시한 부분이 8곳이니, 정답은 8회입니다.

 

 

 

 

 

https://youtube.com/playlist?list=PLboXycXmAIDt4ObBRPVj29BuD2d27oRnO

전자계산기조직응용기사 실기 필답형