본문으로 건너뛰기
장원급제

페이지 교체 알고리즘

참조열(페이지를 부르는 순서)과 프레임 수(메모리 칸 수)를 넣고 FIFO·LRU·LFU·OPT 등을 고르면, 언제 페이지 부재가 나고 무엇을 왜 내보내는지 표로 한 칸씩 보여 줘요.

한마디로FIFO는 들어온 때, LRU는 마지막으로 쓴 때, LFU는 쓴 횟수, OPT는 다음에 쓸 때를 봐요.

3D 해설 영상

책상과 책장: 책상(주기억장치)엔 책이 세 권만 놓여요. 찾는 책이 없으면 페이지 부재, 무엇을 내보낼지가 교체 알고리즘이에요.

책상(주기억장치)엔 책이 세 권만 놓여요. 찾는 책이 없으면 페이지 부재, 무엇을 내보낼지가 교체 알고리즘이에요.

0:00 / 2:44

직접 해 보기

교체 기법

가장 먼저 들어온 페이지를 내보내요. 적중해도 들어온 순서는 바뀌지 않아요.

프레임 수 (메모리 칸)

프레임 표 · FIFO · 프레임 3개

참조
프레임 166663334444111
프레임 22222666655533
프레임 311122226662
부재FFFFFFFFFFFF

F는 페이지 부재예요. 부른 페이지가 프레임에 없었다는 뜻이에요. 처음 빈 프레임을 채울 때도 부재로 세요. 파란 숫자는 그때 새로 들어온 페이지예요. 밑줄 친 숫자는 적중한(이미 있던) 페이지예요. 위쪽 참조 번호를 누르면 그 시점으로 가요.

14번째 참조 · 페이지 2 · 부재, 6을 내보냄

2는 프레임에 없고 빈 프레임도 없어요. 가장 먼저 들어온 6을 내보내요(11번째 참조 때 들어옴). 그 자리(프레임 3)에 2를 넣어요.

들어온 순서(먼저 나갈 것부터): 1 → 3 → 2

참조 14번 끝까지

부재 12번

부재율 12 ÷ 14 = 85.7%

적중 2번 · 적중률 14.3%

같은 참조열, 프레임 3개로 기법 비교

기법부재부재율막대
1285.7%
1178.6%
964.3%
1178.6%
857.1%
1178.6%
1285.7%

OPT보다 부재가 적은 기법은 없어요. 부재율 = 부재 수 ÷ 참조 수(14).

프레임 수를 바꾸면 부재는? (위쪽 숫자가 프레임 수)

기법1234567
FIFO14121210866
LRU1412119866
LFU141198866
MFU14121110866
OPT141087666
2차 기회1412118866
NUR141212101066

이 참조열에서는 프레임을 늘렸을 때 부재가 늘어난 기법이 없어요. ‘벨레이디의 모순’ 예제를 눌러 보세요.

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에는 없어요

암기 카드

외운 카드 0 / 9

남은 카드 9장. ‘다시 볼래요’를 누르면 맨 뒤로 가요.

OX 퀴즈

0 / 8 풀었어요
  1. 1

    OPT는 페이지 부재가 가장 적어서 실제 운영체제가 주로 쓰는 기법이다.

  2. 2

    FIFO는 프레임 수를 늘려도 페이지 부재가 늘어날 수 있다.

  3. 3

    LRU에서도 벨레이디의 모순이 나타날 수 있다.

  4. 4

    프레임이 비어 있을 때 처음 들어오는 페이지도 페이지 부재로 센다.

  5. 5

    NUR에서 (참조 1, 변형 0)인 페이지는 (참조 0, 변형 1)인 페이지보다 먼저 교체된다.

  6. 6

    스래싱이 일어나면 다중 프로그래밍 정도를 높여 CPU 이용률을 되살린다.

  7. 7

    배열을 앞에서부터 차례로 읽는 것은 공간 지역성의 예다.

  8. 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
  • 계리직 컴퓨터일반 출제 범위는 우정사업본부 공고 확인

학습을 돕는 자료예요. 법령과 제도는 바뀔 수 있으니 시험 직전에는 공식 자료로 다시 확인하세요.

컴퓨터일반 다른 개념

계리직 개념 전체 보기