페이지 교체 알고리즘
한마디로FIFO는 들어온 때, LRU는 마지막으로 쓴 때, LFU는 쓴 횟수, OPT는 다음에 쓸 때를 봐요.
3D 해설 영상

책상(주기억장치)엔 책이 세 권만 놓여요. 찾는 책이 없으면 페이지 부재, 무엇을 내보낼지가 교체 알고리즘이에요.
직접 해 보기
프레임 표 · FIFO · 프레임 3개
| 참조 | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 프레임 1 | 6 | 6 | 6 | 6 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 1 | 1 | 1 |
| 프레임 2 | 2 | 2 | 2 | 2 | 6 | 6 | 6 | 6 | 5 | 5 | 5 | 3 | 3 | |
| 프레임 3 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 6 | 6 | 6 | 2 | |||
| 부재 | F | F | F | F | F | F | F | F | F | F | F | F |
F는 페이지 부재예요. 부른 페이지가 프레임에 없었다는 뜻이에요. 처음 빈 프레임을 채울 때도 부재로 세요. 파란 숫자는 그때 새로 들어온 페이지예요. 밑줄 친 숫자는 적중한(이미 있던) 페이지예요. 위쪽 참조 번호를 누르면 그 시점으로 가요.
14번째 참조 · 페이지 2 · 부재, 6을 내보냄
2는 프레임에 없고 빈 프레임도 없어요. 가장 먼저 들어온 6을 내보내요(11번째 참조 때 들어옴). 그 자리(프레임 3)에 2를 넣어요.
들어온 순서(먼저 나갈 것부터): 1 → 3 → 2
참조 14번 끝까지
부재 12번
부재율 12 ÷ 14 = 85.7%
적중 2번 · 적중률 14.3%
같은 참조열, 프레임 3개로 기법 비교
| 기법 | 부재 | 부재율 | 막대 |
|---|---|---|---|
| 12 | 85.7% | ||
| 11 | 78.6% | ||
| 9 | 64.3% | ||
| 11 | 78.6% | ||
| 8 | 57.1% | ||
| 11 | 78.6% | ||
| 12 | 85.7% |
OPT보다 부재가 적은 기법은 없어요. 부재율 = 부재 수 ÷ 참조 수(14).
프레임 수를 바꾸면 부재는? (위쪽 숫자가 프레임 수)
| 기법 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| FIFO | 14 | 12 | 12 | 10 | 8 | 6 | 6 |
| LRU | 14 | 12 | 11 | 9 | 8 | 6 | 6 |
| LFU | 14 | 11 | 9 | 8 | 8 | 6 | 6 |
| MFU | 14 | 12 | 11 | 10 | 8 | 6 | 6 |
| OPT | 14 | 10 | 8 | 7 | 6 | 6 | 6 |
| 2차 기회 | 14 | 12 | 11 | 8 | 8 | 6 | 6 |
| NUR | 14 | 12 | 12 | 10 | 10 | 6 | 6 |
이 참조열에서는 프레임을 늘렸을 때 부재가 늘어난 기법이 없어요. ‘벨레이디의 모순’ 예제를 눌러 보세요.
LRU와 OPT는 프레임을 늘리면 부재가 절대 늘지 않아요. 프레임이 적을 때 들어 있던 페이지가 프레임이 많을 때도 늘 들어 있는 스택 알고리즘이라서예요. FIFO 계열은 늘 수 있어요.
참조열을 고치거나 기법·프레임 수를 바꾸면 표가 다시 채워져요. '다음'을 눌러 한 칸씩 넘기며 왜 그 페이지를 내보냈는지 읽고, 아래 표에서 기법마다 부재가 몇 번인지 견줘 보세요. 횟수가 같을 때 무엇을 고를지처럼 문제마다 다른 조건은 직접 맞출 수 있어요.
핵심 정리
필요한 페이지가 메모리에 없으면: 페이지 부재
프레임(메모리 칸)이 3개일 때 1 2 3 1을 차례로 부르면, 1·2·3은 처음이라 부재 3번이고 마지막 1은 이미 있어서 적중이에요. 이렇게 참조한 페이지가 주기억장치의 프레임에 없으면 페이지 부재(page fault)이고, 처음 빈 프레임을 채울 때도 부재로 세요. 빈 프레임이 없으면 교체 기법이 내보낼 페이지를 골라요. 부재율 = 부재 횟수 ÷ 전체 참조 횟수라서, 이 예는 3 ÷ 4예요.
무엇을 기준으로 내보낼까: FIFO · LRU · LFU · MFU
냉장고가 꽉 차서 하나를 버려야 할 때, 가장 먼저 산 반찬을 버리면 FIFO(먼저 들어온 것부터)이고 가장 오래 안 먹은 반찬을 버리면 LRU(가장 오랫동안 안 쓴 것부터)예요. LFU(가장 적게 쓴 것부터)는 참조 횟수가 가장 적은 페이지를, MFU(가장 많이 쓴 것부터)는 가장 많은 페이지를 내보내요. LFU·MFU는 횟수가 같은 페이지가 자주 생겨서, 문제에 '횟수가 같으면 FIFO(또는 LRU)로' 같은 조건이 붙어요.
미래를 안다면: OPT(최적 교체)
프레임 1·2·3이 꽉 찼을 때 4가 들어오고 그다음 참조가 2 3 1 순서라면, 가장 늦게 다시 쓰이는 1을 내보내요. 이렇게 OPT는 앞으로 가장 오랫동안 쓰이지 않을 페이지를 내보내요. 벨레이디(Belady)가 제안했고 페이지 부재가 가장 적지만, 미래의 참조열을 미리 알아야 해서 실제로는 구현할 수 없어요. 그래서 다른 기법이 얼마나 잘하는지 재는 기준으로 써요.
최근에 썼으면 한 번 봐주기: 2차 기회와 NUR
가장 먼저 들어와 나갈 차례인 페이지라도 최근에 쓴 표시가 있으면 이번에는 봐줘요. 2차 기회(Second Chance)는 FIFO에 참조 비트(최근에 쓰면 1)를 더한 기법이라, 내보낼 차례인 페이지의 참조 비트가 1이면 0으로 바꾸고 큐 뒤로 보내 한 번 더 기회를 줘요. NUR(최근에 안 쓴 것부터)은 참조 비트와 변형 비트(내용을 고쳤으면 1)를 함께 보고 (0,0) → (0,1) → (1,0) → (1,1) 순으로 내보내요. 참조 비트는 일정 주기마다 0으로 되돌려요.
칸을 늘렸는데 부재가 늘어나는 FIFO: 벨레이디의 모순
참조열 1 2 3 4 1 2 5 1 2 3 4 5를 FIFO로 돌리면 프레임 3개에서 9번, 4개에서 10번 부재가 나요. 이렇게 FIFO는 프레임을 늘렸는데 페이지 부재가 오히려 늘어날 수 있어요. LRU와 OPT는 이런 일이 없어요. 프레임이 적을 때 들어 있던 페이지가 프레임이 많을 때도 늘 들어 있는 스택 알고리즘이라서예요.
자주 쓰는 페이지가 모자라면: 지역성 · 워킹 셋 · 스래싱
반복문은 방금 쓴 변수를 곧 다시 쓰고(시간 지역성), 배열 순회는 바로 옆 칸을 이어서 읽어요(공간 지역성). 워킹 셋은 이렇게 최근 일정 기간 동안 참조한 페이지 집합이에요. 수험서는 '자주 참조하는 페이지'라고 흔히 쓰지만, 정확히는 그 기간에 한 번이라도 참조한 페이지가 모두 들어가요. 프레임이 워킹 셋보다 모자라면 교체에 시간을 다 써서 CPU 이용률이 뚝 떨어지는데, 이것이 스래싱이에요. 다중 프로그래밍 정도(메모리에 함께 올린 프로그램 수)를 낮추거나 워킹 셋·페이지 부재 빈도(PFF) 방식으로 프레임을 맞춰 줘서 막아요.
이렇게 외워요
무엇을 보고 내보내나
FIFO 들어온 때 · LRU 마지막으로 쓴 때 · LFU 쓴 횟수 · OPT 다음에 쓸 때
NUR 교체 순서
(참조, 변형) 00 → 01 → 10 → 11 · 안 쓰고 안 고친 것부터 나가요
벨레이디의 모순
1 2 3 4 1 2 5 1 2 3 4 5 → FIFO 3칸 9번, 4칸 10번. LRU·OPT에는 없어요
암기 카드
남은 카드 9장. ‘다시 볼래요’를 누르면 맨 뒤로 가요.
OX 퀴즈
- 1
OPT는 페이지 부재가 가장 적어서 실제 운영체제가 주로 쓰는 기법이다.
- 2
FIFO는 프레임 수를 늘려도 페이지 부재가 늘어날 수 있다.
- 3
LRU에서도 벨레이디의 모순이 나타날 수 있다.
- 4
프레임이 비어 있을 때 처음 들어오는 페이지도 페이지 부재로 센다.
- 5
NUR에서 (참조 1, 변형 0)인 페이지는 (참조 0, 변형 1)인 페이지보다 먼저 교체된다.
- 6
스래싱이 일어나면 다중 프로그래밍 정도를 높여 CPU 이용률을 되살린다.
- 7
배열을 앞에서부터 차례로 읽는 것은 공간 지역성의 예다.
- 8
LFU는 참조 횟수가 가장 많은 페이지를 교체한다.
컴퓨터일반 자료 전체의 카드와 OX를 한 번에 풀려면 컴퓨터일반 카드·OX 모아 풀기로 가요.
근거
- 운영체제 표준 이론 (가상 메모리, 페이지 교체, 스래싱)
- L. A. Belady, "A study of replacement algorithms for a virtual-storage computer", IBM Systems Journal, 1966 (OPT)
- L. A. Belady, R. A. Nelson, G. S. Shedler, "An anomaly in space-time characteristics of certain programs running in a paging machine", Communications of the ACM, 1969
- P. J. Denning, "The working set model for program behavior", Communications of the ACM, 1968
- 계리직 컴퓨터일반 출제 범위는 우정사업본부 공고 확인
학습을 돕는 자료예요. 법령과 제도는 바뀔 수 있으니 시험 직전에는 공식 자료로 다시 확인하세요.
컴퓨터일반 다른 개념
- OSI 7계층 한 번에 끝내기3D로 쌓은 7개 층을 하나씩 눌러 보며 층마다 하는 일, 데이터 이름, 프로토콜, 장비를 익혀요.3D 해설 영상컴퓨터일반 · 3D 모델 · 계리직
- 기억장치 계층 구조층을 하나씩 눌러 보며 레지스터부터 보조기억장치까지 속도·용량·가격이 어떻게 달라지는지 익혀요.3D 해설 영상컴퓨터일반 · 3D 모델 · 계리직
- CPU 스케줄링 시뮬레이터프로세스마다 도착 시간과 실행 시간을 넣고 CPU를 줄 순서를 정하는 규칙(FCFS·SJF·SRT·RR·HRN)을 바꾸면, 누가 언제 CPU를 쓰는지 그린 간트 차트와 평균 대기 시간이 바로 나와요.3D 해설 영상컴퓨터일반 · 시뮬레이터 · 계리직
- 메모리 배치와 디스크 관리빈 메모리에 프로그램을 넣고, 주소를 바꾸고, 디스크의 이동 거리와 고장에 견디는 범위를 직접 계산해요.3D 해설 영상컴퓨터일반 · 주소 변환·디스크 스케줄링 · 계리직
- 파이프라인·입출력·오류 검출명령어가 기다리는 이유를 찾고, 데이터를 옮기는 담당자와 오류를 고치는 과정을 직접 확인해요.3D 해설 영상컴퓨터일반 · 파이프라인 타임라인·해밍 코드 실험 · 계리직
- 운영체제 구조·시스템 호출·리눅스 권한파일 권한을 바꾸고, 커널에 일을 부탁하는 과정과 디스크에 파일을 놓는 방식을 직접 비교해요.3D 해설 영상컴퓨터일반 · 권한 계산기·시스템 호출 따라가기 · 계리직
- 접근통제·방화벽·전자봉투·백업등급에 맞는 접근을 고르고, 전자봉투를 조립하고, 통신 규칙과 백업 순서를 직접 확인해요.3D 해설 영상컴퓨터일반 · 등급 판정·방화벽 규칙·백업 복원 계산 · 계리직
- 코드 읽기: 파이썬·C·자바 출력 따라가기출력을 먼저 예상하고, 한 문장씩 실행하며 변수와 출력이 어떻게 바뀌는지 확인해요.3D 해설 영상컴퓨터일반 · 코드 따라가기·출력 예측 · 계리직
- 기초영어 어휘·관용 표현 덱영어 낱말은 비슷한 뜻끼리 묶고, 생활 표현은 대화에 넣어 보며 외워요.3D 해설 영상컴퓨터일반 · 어휘·관용 표현 덱·유의어 퀴즈 · 계리직
- 엑셀 셀 참조 복사 시뮬레이터D6에 수식 하나를 넣고 오른쪽·아래로 복사해 보면서, $를 어디에 붙여야 표 전체가 맞게 채워지는지 직접 찾아봐요.3D 해설 영상컴퓨터일반 · 복사 시뮬레이터 · 계리직
- 엑셀 함수 결과 실험실작은 표에 수식을 넣고 결과와 참조 셀을 확인하면서 자주 나오는 엑셀 함수를 익혀요.3D 해설 영상컴퓨터일반 · 미니 시트·결과 맞히기 · 계리직
- 정규화 단계 따라가기수강신청 표 하나를 1NF부터 BCNF까지 직접 나눠 보면서, 단계마다 무엇을 떼어 내고 어떤 문제가 사라지는지 확인해요.3D 해설 영상컴퓨터일반 · 단계별 풀이 · 계리직
- SQL 쿼리 실험실사원·부서 표에 SELECT 문을 한 절씩 붙여 보면서, 어떤 행이 걸러지고 어떻게 묶이는지, NULL과 조인이 결과를 어떻게 바꾸는지 눈으로 확인해요.3D 해설 영상컴퓨터일반 · 쿼리 실험실 · 계리직
- 데이터베이스 기초학생 표에서 키를 찾고, 표를 합치거나 부모 행을 바꾸면서 데이터베이스의 규칙을 확인해요.3D 해설 영상컴퓨터일반 · 키 판별기·관계대수 실험 · 계리직
- IPv4 서브네팅 계산기IP 주소와 프리픽스를 넣어 32비트가 네트워크와 호스트로 갈리는 모습과 네트워크·브로드캐스트 주소·호스트 수를 보고, 두 주소가 같은 서브넷인지와 몇 개로 나눌 수 있는지도 직접 따져 봐요.3D 해설 영상컴퓨터일반 · 서브넷 계산기 · 계리직
- 자료구조와 정렬스택·큐에 직접 넣고 꺼내 보고, 우리가 쓰는 식(중위식)을 연산자를 뒤에 쓰는 식(후위식)으로 바꾸고, 트리를 순서대로 돌아보고, 정렬이 회전마다 배열을 어떻게 바꾸는지 한 단계씩 확인해요.3D 해설 영상컴퓨터일반 · 자료구조 실험실 · 계리직
- 컴퓨터 구조: 수 표현·논리회로·명령어·메모리10진수를 2의 보수와 IEEE 754 비트로 바꿔 보고, 카르노 맵을 눌러 식을 줄이고, 같은 계산을 0·1·2·3-주소 명령어로 실행하고, 명령어가 값을 어디서 찾는지 따라가며, 상황에 맞는 메모리(SRAM·DRAM·플래시)를 골라 봐요.3D 해설 영상컴퓨터일반 · 수 표현·회로 실험실 · 계리직
- 프로세스·인터럽트·교착상태 실험실CPU 하나에 프로세스 여럿을 올려 상태가 바뀌는 모습을 보고, 한꺼번에 몰린 인터럽트를 차례로 처리하고, 교착상태를 만들었다 풀고, 은행원 알고리즘으로 안전한 순서를 직접 찾아봐요.3D 해설 영상컴퓨터일반 · 상태·교착 실험실 · 계리직
- 소프트웨어공학 실험실상황에 맞는 생명 주기 모형을 고르고, 경계값·커버리지·순환 복잡도로 테스트 케이스를 직접 만들고, 가상의 우체국 앱 기능을 세어 기능 점수까지 계산해 봐요.3D 해설 영상컴퓨터일반 · 테스트·FP 실험실 · 계리직
- 인공지능·머신러닝 기초여러 상황을 지도·비지도·강화학습으로 나눠 보고, 점을 찍어 k-NN과 k-평균을 돌려 보고, 스팸 필터의 기준값을 옮기며 정확도·정밀도·재현율·F1을 계산해 봐요.3D 해설 영상컴퓨터일반 · 학습·평가 실험실 · 계리직
- 트랜잭션과 동시성 제어·회복계좌 이체 두 건을 섞어 실행해 갱신 분실·오손 읽기·모순성을 직접 만들어 보고, 2PL을 켜면 누가 기다리는지, 장애가 나면 무엇을 REDO·UNDO하는지 확인해요.3D 해설 영상컴퓨터일반 · 스케줄·회복 실험실 · 계리직
- 인터넷 프로토콜: 메일·웹·DNS·TCP/UDP메일 한 통을 SMTP로 보내고 POP3·IMAP으로 받아 어디에 남는지 보고, DNS 질의·TCP 연결·DHCP와 ping을 한 단계씩 따라가고, 포트 번호와 IPv6 줄여 쓰기를 연습해요.3D 해설 영상컴퓨터일반 · 프로토콜 실험실 · 계리직
- 정보보안 핵심 실험실어떤 키로 잠가야 하는지 골라 보고, 해시·전자서명·블록 사슬을 일부러 깨뜨려 보고, 공격 사례와 ISMS-P 의무 대상, 침입탐지·클라우드 책임까지 직접 판정해 봐요.3D 해설 영상컴퓨터일반 · 보안 실험실 · 계리직
- 클라우드와 신기술 실험실서비스 책임 범위를 직접 칠하고, 블록을 고쳐 해시 연결을 깨 보고, IoT·빅데이터·엣지 개념을 사례로 골라 봐요.3D 해설 영상컴퓨터일반 · 누가 관리할까?·블록체인 실험 · 계리직
- 계리직 기초영어 핵심우체국·은행·전화 장면의 대화 빈칸을 채우고, 밑줄 친 곳이 맞는지 틀린지 가리고, 자주 나오는 어휘와 독해 유형별 푸는 순서를 직접 풀면서 익혀요.3D 해설 영상컴퓨터일반 · 기초영어 연습 · 계리직