10. 가상 메모리 관리 - 요구 페이징, 페이지 부재, 페이지 교체 알고리즘

 

💡 1분 핵심 요약 (TL;DR)

• ✅ 요구 페이징(Demand Paging) — 프로세스가 실제로 요청할 때만 메모리로 가져오는 가져오기 정책. 메모리 절약 + 응답 속도 향상
• ✅ 페이지 부재(Page Fault) — 요청한 페이지가 메모리에 없는 상황. 유효 비트로 메모리/스왑영역 위치를 판단
• ✅ 페이지 교체 알고리즘 — 메모리가 꽉 찼을 때 내보낼 페이지를 정하는 알고리즘. 무작위·FIFO·최적(이론) → LRU·LFU·NUR(최적 근접) → 2차 기회·시계(FIFO 변형)

 

 

 

 

01 요구 페이징과 가져오기 정책

프로세스의 일부만 메모리에 올리는 이유

 

📖 가져오기 정책과 요구 페이징
가져오기 정책(fetch policy)은 프로세스가 필요로 하는 데이터를 언제 메모리로 가져올지 결정하는 것입니다. 가장 일반적인 방식은 프로세스가 실제로 요청할 때 메모리로 가져오는 것인데, 이를 요구 페이징(demand paging)이라고 부릅니다. 메모리에는 꼭 필요한 프로세스만 유지하는 것이 좋으므로, 프로세스 전체가 아니라 일부만 메모리로 가져와 실행하는 방법입니다.

 

일부만 가져오는 이유	설명
효율적인 메모리 관리	메모리가 꽉 차면 관리가 어려워지므로, 가급적 적은 양의 프로세스만 메모리에 유지
응답 속도 향상	용량이 큰 프로세스를 전부 가져와 실행하면 응답이 늦어지므로, 필요한 모듈만 올려 실행

 

✓ 예시로 이해하기
포토샵처럼 기능이 많은 프로그램도 프로그램 전체가 아니라 일부 모듈만 먼저 메모리에 올려 실행하고, 사용자가 특정 기능(예: 필터 효과)을 요구할 때 해당 모듈을 그제서야 메모리에 올립니다. 이 방식으로 메모리 절약, 효율적 관리, 응답 속도 향상의 세 가지 효과를 동시에 얻을 수 있습니다.

 

요구 페이징 · 프로세스가 요청할 때 메모리로 가져옴 · 메모리 절약, 효율적 관리에 유리 · 당장 필요 없는 페이지는 스왑영역에 남겨둠

미리 가져오기 · 요구 페이징과 반대로, 앞으로 필요할 것으로 예상되는 페이지를 미리 가져옴 · 대표적인 예가 캐시(Cache) · 예상이 틀리면 오히려 비효율적일 수 있음

 

 

 

 

02 페이지 부재와 유효 비트

요청한 페이지가 메모리에 없을 때 벌어지는 일

 

앞서 가상 메모리 글에서 페이지 부재라는 키워드를 잠깐 언급했었는데, 이번 단원에서는 발생 조건과 처리 과정을 좀 더 깊이 다룹니다.

 

📖 페이지 부재(Page Fault)
프로세스가 어떤 페이지를 요청했을 때, 그 페이지가 메모리에 없는 상황을 말합니다. 페이지 부재가 발생하면 운영체제는 해당 페이지를 스왑영역에서 물리 메모리로 옮겨와야 프로세스가 작업을 계속할 수 있습니다.

 

페이지가 스왑영역에 있는 두 가지 경우

 

① 처음부터 못 올라간 경우 요구 페이징으로 인해 애초에 물리 메모리에 적재되지 않은 페이지

② 밀려난 경우 메모리가 꽉 차서 나중에 스왑영역으로 옮겨진 페이지

 

어떤 경우든 페이지 테이블에는 해당 페이지가 메모리에 있는지, 스왑영역에 있는지 표시해야 하는데 이때 사용하는 비트가 유효 비트(Valid Bit)입니다.

 

유효 비트	페이지 위치	주소 필드에 저장되는 값
0	물리 메모리	물리 메모리의 프레임 번호
1	스왑영역	스왑영역 내 페이지 주소

 

⚠️ 시험 포인트 — 유효 비트 값의 의미
교재에 따라 유효 비트 0/1의 의미가 다르게 서술되는 경우가 있습니다. 이번 강의노트 기준으로는 0이면 메모리에 있음, 1이면 스왑영역에 있음으로 정의하고 있으니, 시험을 준비할 때는 강의에서 제시한 정의를 우선으로 외워두는 것이 안전합니다.

 

페이지 테이블 엔트리의 구성

 

페이지 테이블 엔트리 마지막에 있는 프레임 번호는 가상 주소의 해당 페이지가 어느 프레임에 있는지 알려주는 핵심 자료 구조입니다. 메모리 관리자는 이 프레임 번호로 가상 주소를 물리 주소로 변환합니다. 이때 사용되는 플래그 비트에는 접근 비트, 변경 비트, 유효 비트, 읽기 비트, 쓰기 비트, 실행 비트 등이 모여 있습니다.

 

① 페이지 부재 발생 요청한 페이지가 메모리에 없음 (유효 비트 확인)

→

② 빈 프레임 탐색 빈 프레임이 있으면 바로 적재

→

③ 없으면 교체 페이지 교체 알고리즘으로 내보낼 페이지 선정 후 적재

 

 

 

 

 

03 페이지 교체 알고리즘과 지역성

메모리가 꽉 찼을 때, 누구를 내보낼 것인가

 

📖 페이지 교체 알고리즘이란
페이지 부재가 발생했을 때 메모리가 꽉 차 있다면, 메모리에 있는 페이지 중 하나를 스왑영역으로 내보내야 합니다. 페이지 교체 알고리즘(Page Replacement Algorithm)은 이때 스왑영역으로 보낼 대상 페이지를 결정하는 알고리즘입니다. 앞으로 사용할 가능성이 적은 페이지를 골라내야 페이지 부재를 줄이고 시스템 성능을 높일 수 있습니다.

 

⚠️ 성능 평가 기준
페이지 부재 횟수, 페이지 요청 후 실제 작업 시작까지의 평균 대기 시간, 전체 작업 시간으로 알고리즘 성능을 비교할 수 있습니다. 다만 성능이 뛰어나더라도 계산량이 많거나 메모리를 많이 차지한다면 좋은 알고리즘이라 보기 어렵습니다.

 

📖 지역성(Locality)
기억장치에 접근하는 패턴이 메모리 전체에 고루 분포되는 것이 아니라, 특정 영역에 집중되는 성질입니다. 페이지 교체 알고리즘은 이 지역성을 바탕으로 앞으로 사용하지 않을 페이지를 골라냅니다. 자주 쓰는 페이지를 내보내면 곧바로 다시 불러와야 하므로 성능이 떨어지기 때문입니다.

 

지역성 종류	설명
공간의 지역성	현재 위치에서 가까운 데이터에 접근할 확률이, 먼 거리의 데이터보다 높음
시간의 지역성	현재를 기준으로 가까운 시간에 접근한 데이터가, 먼 시간에 접근한 데이터보다 다시 사용될 확률이 높음
순차적 지역성	여러 작업이 순서대로 진행되는 경향 (일반적인 프로그램은 처음부터 마지막 순서로 실행)

 

✓ 지역성의 사용 예
캐시 메모리는 지역성 이론을 사용하는 대표적인 장치로, 시간적·공간적으로 가까운 데이터를 가져와 적중률을 높입니다. 프로그래밍에서 goto문 사용을 지양하는 것도 같은 이유입니다. 현재 실행 행과 가까운 행을 캐시로 가져온 상태에서 갑자기 엉뚱한 행으로 건너뛰면, 이미 가져온 데이터가 쓸모없어지기 때문입니다.

 

📖 지역성의 실무 적용 — 워킹셋(Working Set)
운영체제는 이 지역성 이론을 바탕으로, 프로세스가 일정 시간 동안 집중적으로 참조하는 페이지들의 묶음인 워킹셋(Working Set)을 통째로 메모리에 유지하는 모델을 사용합니다. 워킹셋만 메모리에 올려두면 잦은 페이지 부재 없이 프로세스를 실행할 수 있습니다.

 

⚠️ 가상 메모리의 치명적 부작용 — 스래싱(Thrashing)
반대로 물리 메모리가 너무 작거나 프로세스가 지나치게 많이 올라와 워킹셋조차 제대로 유지되지 못하면, CPU가 실제 연산은 거의 하지 못하고 페이지를 스왑인·스왑아웃 하는 데에만 시간을 소모하게 됩니다. 이렇게 페이지 교체만 반복되며 시스템 성능이 급격히 떨어지는 현상을 스래싱이라고 부릅니다.

 

 

 

 

04 무작위·FIFO·최적 — 가장 단순한 방법부터 이상까지

간단한 알고리즘과 이론적 알고리즘

 

분류	알고리즘	특징
간단한 알고리즘	무작위	무작위로 대상 페이지를 선정해 스왑영역으로 보냄
간단한 알고리즘	FIFO	처음 메모리에 올라온 페이지를 스왑영역으로 보냄
이론적 알고리즘	최적	미래의 접근 패턴을 보고 대상 페이지를 선정해 스왑영역으로 보냄

 

무작위 페이지 교체 · 특별한 로직 없이 무작위로 대상 페이지 선정 · 구현이 가장 간단 · 지역성을 전혀 고려하지 않아 성능이 낮음

FIFO 페이지 교체 · 메모리에 가장 먼저 들어온 페이지를 내보냄 · 큐로 쉽게 구현 가능 · 올라온 시간만 고려해 자주 쓰는 페이지도 내보낼 수 있음

 

 

 

❌ FIFO만의 치명적 단점 — 벨라디의 모순(Belady's Anomaly)
상식적으로는 메모리(프레임)를 더 많이 할당해주면 페이지 부재가 줄어들어야 하지만, FIFO 알고리즘은 오히려 프레임을 늘려줬는데도 페이지 부재가 더 많이 발생하는 기이한 현상이 나타날 수 있습니다. 이를 벨라디의 모순이라고 하며, FIFO 계열 시험 문제에서 빠지지 않는 키워드입니다.

 

FIFO의 동작을 표시할 때는 페이지 부재가 일어난 경우(원하는 페이지가 메모리에 없는 경우)를 F, 그렇지 않은 경우(메모리에 있는 경우)를 S로 표시하는 방식이 자주 사용됩니다.

 

📖 최적 페이지 교체 알고리즘
앞으로 사용하지 않을 페이지를 스왑영역으로 옮기는 방식입니다. 페이지 교체 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상으로 선정하기 때문에 이론상 가장 이상적인 방법이지만, 미래의 접근 패턴을 미리 안다는 것이 불가능해 실제로는 구현할 수 없습니다.

 

📖 그래서 등장한 최적 근접 알고리즘
최적 알고리즘은 구현할 수 없으므로, 과거의 데이터를 바탕으로 미래의 접근 패턴을 추정해 최적에 근접한 성능을 내는 알고리즘들이 개발되었습니다. 이것이 LRU, LFU, NUR이며, 다음 섹션에서 차례로 살펴봅니다.

 

 

 

 

05 최적 근접 알고리즘 — LRU·LFU·NUR

과거 데이터로 미래를 예측하는 현실적인 대안

 

알고리즘	특징
LRU (Least Recently Used)	시간적으로 가장 멀리 떨어진(가장 오랫동안 사용되지 않은) 페이지를 스왑영역으로 보냄
LFU (Least Frequently Used)	사용 빈도(횟수)가 가장 적은 페이지를 스왑영역으로 보냄
NUR (Not Used Recently)	최근에 사용한 적이 없는 페이지를 스왑영역으로 보냄

 

 

LRU의 구현 방법 3가지

 

구현 방식	설명
접근 시간 기반	가장 간단한 형태. 읽기·쓰기·실행 연산이 이루어진 시간을 기준으로, 접근한 지 가장 오래된 페이지를 교체
카운터 기반	카운터로 접근 시간을 기록. 접근 시간을 기록하든 카운트를 하든 추가 메모리 공간이 필요해 공간이 낭비됨
참조 비트 시프트	각 페이지에 참조 비트(초기값 0, 접근 시 1)를 두고 주기적으로 오른쪽으로 시프트. 갱신 중 가장 작은 값을 대상 페이지로 선정

 

LFU는 현재 프레임에 있는 페이지마다 사용된 횟수를 세어, 횟수가 가장 적은 페이지를 스왑영역으로 옮깁니다. 처음 메모리에 올라온 페이지의 사용 빈도는 1이고, 사용될 때마다 하나씩 증가합니다.

 

❌ LRU·LFU의 공통 단점
접근 시간이나 사용 빈도를 표시하려면 페이지마다 추가 메모리 공간이 필요합니다. 이 추가 공간 때문에 사용자가 실제로 쓸 수 있는 메모리 공간이 줄어드는 것이 두 알고리즘의 공통된 단점입니다.

 

NUR은 LRU, LFU와 성능이 거의 비슷하면서도 이 공간 낭비 문제를 해결한 알고리즘입니다. 페이지마다 참조 비트(읽기/실행 시 1)와 변경 비트(쓰기/추가 시 1), 단 2비트만 추가로 사용합니다.

 

⚠️ 시험 포인트 — LRU vs LFU 성능
특정 예시에서 LRU의 페이지 성공 횟수가 4회, LFU가 5회로 LFU가 한 번 더 성공한 사례가 있지만, 일반적으로 두 알고리즘의 성능은 비슷하다고 평가됩니다. 다만 LRU·LFU·NUR(최적 근접 알고리즘) 모두 FIFO보다는 성능이 우수합니다.

 

 

 

 

06 FIFO 변형 알고리즘 — 2차 기회·시계

FIFO의 단점을 보완한 실용적인 알고리즘

 

📖 FIFO 변형 알고리즘이란
FIFO는 메모리에 올라온 순서만 고려하고 자주 사용하는 페이지를 고려하지 않아 성능이 좋지 않습니다. 2차 기회 페이지 교체 알고리즘과 시계 알고리즘은 FIFO 방식을 기본으로 하면서, 페이지에 접근할 때마다 순서에 변화를 주어 성능을 끌어올린 알고리즘입니다.

 

2차 기회 알고리즘 · FIFO처럼 큐를 사용 · 페이지 부재 없이 접근에 성공하면 해당 페이지를 큐 맨 뒤로 이동 · 성공한 페이지에게 기회를 한 번 더 줌

시계 알고리즘 · 2차 기회와 유사하지만 원형 큐 사용이 핵심 차이점 · 스왑영역으로 옮길 대상 페이지를 가리키는 포인터 사용 · 실제 구현 방식은 2차 기회와 다름

 

 

 

 

📌 핵심 정리

· 요구 페이징 : 프로세스가 요청할 때만 메모리로 가져오는 가져오기 정책 (반대 개념 : 미리 가져오기, 대표 예 캐시)
· 페이지 부재 : 요청한 페이지가 메모리에 없는 상황 — 유효 비트로 메모리/스왑영역 위치 판단
· 유효 비트 : 0이면 메모리에 있음(프레임 번호 저장), 1이면 스왑영역에 있음(스왑영역 주소 저장)
· 지역성 : 접근 패턴이 특정 영역에 집중되는 성질 — 공간·시간·순차적 지역성
· 워킹셋 : 일정 시간 집중적으로 참조되는 페이지 묶음을 통째로 메모리에 유지하는 지역성 기반 모델
· 스래싱 : 메모리 부족·과도한 프로세스로 워킹셋이 깨져 페이지 교체만 반복되며 성능이 급격히 떨어지는 현상
· 간단한 알고리즘 : 무작위(로직 없음) · FIFO(가장 오래된 페이지 교체, 큐로 구현, 벨라디의 모순 발생 가능)
· 이론적 알고리즘 : 최적(미래 패턴 기반, 이상적이나 구현 불가)
· 최적 근접 알고리즘 : LRU(시간상 가장 오래 미사용) · LFU(사용 빈도 최소) · NUR(참조+변경 비트 2개로 공간 낭비 해결)
· FIFO 변형 알고리즘 : 2차 기회(큐, 성공 시 맨 뒤로 이동) · 시계(원형 큐 + 포인터)
· 다음 주 예고 : 12단원 "입출력 시스템과 저장장치 관리"로 이어집니다

 

 

태그 : 요구페이징이란페이지부재 발생원인유효비트란페이지교체알고리즘 종류LRU LFU NUR 차이FIFO 페이지교체최적페이지교체알고리즘지역성이란2차기회 시계알고리즘운영체제 가상메모리관리