페이지 교체 알고리즘 계산기 (FIFO, LRU, Optimal)

메모리가 가득 찼는데 프로그램이 적재되지 않은 페이지를 필요로 하면 운영체제는 내보낼 페이지를 골라야 합니다. 이 선택이 페이지 폴트가 몇 번 일어나는지를 결정합니다. 이 계산기는 대표적인 교체 알고리즘인 FIFO, LRU, Optimal, LFU, Clock(두 번째 기회)을 참조 문자열에 적용해 참조마다의 프레임과 히트·폴트를 보여 주고, 히트율을 구하며, 모든 알고리즘을 프레임 수별로 비교해 벨레이디의 이상 현상이 있으면 드러냅니다.

사용 방법

1. 참조 문자열을 입력합니다. 사용되는 순서대로 나열한 페이지 번호입니다.
2. 프레임 수를 정합니다.
3. 알고리즘을 고릅니다.
4. 프레임 표, 폴트 횟수, 프레임 수별 비교를 확인합니다.

계산식

히트율 = 히트 ÷ 참조 수 · 폴트율 = 폴트 ÷ 참조 수 · 폴트에는 빈 프레임에 처음 적재하는 것도 포함

FIFO는 가장 먼저 적재된 페이지를, LRU는 가장 오래 전에 사용된 페이지를, Optimal은 다음 사용이 가장 먼(또는 다시 쓰이지 않는) 페이지를, LFU는 적재된 뒤 가장 적게 사용된 페이지(동점이면 먼저 적재된 것)를 내보냅니다. Clock은 프레임을 돌며 참조 비트를 지우다가 비트가 이미 꺼진 첫 페이지를 내보냅니다. 모든 알고리즘은 교재처럼 처음 적재를 폴트로 셉니다. 비교표는 프레임 1개부터 12개까지 반복해서 실행한 결과입니다.

예시

교재의 참조 문자열 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1과 프레임 3개에서 LRU는 페이지 폴트 12회, 히트 8회(히트율 40%)이고, FIFO는 15회, Clock은 14회, Optimal은 하한인 9회입니다. 문자열 1 2 3 4 1 2 5 1 2 3 4 5에서 FIFO는 프레임 3개일 때 폴트 9회, 4개일 때 10회가 되는데, 이것이 벨레이디의 이상 현상입니다.