운영체제(OS)-WEEK7 (1) Multi-Level Page Table

이전 내용 복습 및 정리]

페이징 기법(순수)에서 무조건 고정된 페이지 단위로 나누어 실제 데이터가 들어가는 공간도 고정된 크기로 매핑됨.

-> 물리 메모리의 외부 단편화 아예 존재하지 않음. (프로세스 가상공간만큼 물리메모리 차지?)

하이브리드 기법에서도 내부단편화 생기는게 아닌가? -> if 특정 세그먼트가 차지하는 실제 크기가 페이지 크기(ex:4KB)의 배수로 딱 떨어지지 않는다면, 해당 세그먼트에 할당된 마지막 페이지 내부에는 남는 빈 공간이 생길 수 밖에 없다. 이것이 전형적인 내부 단편화! 페이징 기법을 혼합하여 사용하는 이상 피할 수 없는 현상.

하이브리드 기법의 딜레마: 메모리 낭비를 줄이기 위해 세그먼트마다(Code,Heap,Stack) 페이지 테이블을 따로 만든다. 그런데 프로세스마다, 그리고 세그먼트마다 사용하는 공간의 크기가 다 다르기 때문에, 각 세그먼트를 위한 '페이지 테이블의 크기' 역시 제각각(가변적)이 된다.

문제 발생: 운영체제는 이렇게 '크기가 제각각인 페이지 테이블들'을 물리적 메모리에 연속적인 공간으로 할당해야 한다. 가변적인 크기의 덩어리(페이지 테이블)들을 메모리에 할당하고 해제하다 보면, 메모리 조각들이 쪼개져서 결국 자잘한 빈 공간들이 생겨난다. 이것이 바로 하이브리드 기법의 치명적인 단점으로 꼽히는 (페이지 테이블 할당 과정에서의) 외부 단편화다.

하이브리드 기법에서는 두 가지 단편화가 다른 층위에서 모두 발생합니다.

데이터가 저장되는 물리 메모리 공간: 페이지 단위로 나뉘기 때문에 내부 단편화가 발생합니다.
페이지 테이블이 저장되는 물리 메모리 공간: 세그먼트별로 페이지 테이블의 크기가 가변적이기 때문에 외부 단편화가 발생합니다. (교안에서 지적한 하이브리드 기법의 고질적 한계)

1. 순수 페이징에서 말하는 '내부 단편화'의 진짜 의미

순수 페이징 기법에서의 내부 단편화 역시 앞서 설명드린 것과 완전히 똑같습니다. **"고정된 페이지 크기 때문에 딱 나누어 떨어지지 않아서, 할당된 마지막 페이지에 남는 자투리 공간"**만을 의미합니다.

예시: 페이지 크기가 4KB인데, 프로그램의 코드가 총 13KB의 메모리를 차지합니다.
운영체제는 무조건 4KB 단위로만 자를 수 있으므로, 이 코드 영역에 총 4개의 페이지(16KB)를 할당합니다.
3개의 페이지는 12KB로 꽉 차게 사용되지만, 마지막 4번째 페이지는 1KB만 사용되고 3KB가 텅 빈 상태로 남습니다.
이 마지막 페이지 안의 3KB 자투리, 이것이 바로 페이징의 내부 단편화입니다.

2. 그렇다면 한 덩어리 내부에서 안 쓰고 놀고 있는 '그 넓은 공간'은 무엇일까?

프로세스의 전체 가상 주소 공간을 보면, 힙(Heap) 영역과 스택(Stack) 영역 사이에는 데이터를 할당하지 않아 텅텅 비어있는 아주 거대한 공간이 존재합니다.

컴퓨터 공학에서는 이것을 단편화(Fragmentation)라고 부르지 않고, 그냥 프로그램이 아직 쓰지 않은 '미사용 주소 공간(Unused Address Space)' 또는 **'희소 공간(Sparse Space)'**이라고 부릅니다.

3. 순수 페이징의 진짜 문제는 무엇이었을까?

과거 순수 페이징 기법의 가장 치명적인 단점은 바로 저 '미사용 주소 공간'을 처리하는 방식에 있었습니다.

순수 페이징은 가상 메모리의 처음(0번지)부터 끝까지를 모두 덮는 단 하나의 거대한 '선형 페이지 테이블(Linear Page Table)'을 사용합니다. 따라서 힙과 스택 사이에 텅텅 비어있는 '미사용 공간'조차도 지도(페이지 테이블) 상에는 무조건 빈칸(Invalid)으로 자리를 만들어 두어야 했습니다. 결과적으로 실제 데이터를 저장하는 물리 메모리가 낭비되는 것이 아니라, **"비어있는 공간을 비어있다고 표시하기 위한 거대한 지도(페이지 테이블)를 만드는 데 메모리가 낭비되는 것"**이 순수 페이징의 진짜 문제였습니다.

이 '지도 낭비'를 막기 위해, 진짜로 쓰고 있는 덩어리(세그먼트)들만 지도를 따로따로 그리자고 도입한 것이 바로 하이브리드(세그멘테이션 + 페이징) 기법입니다.

멀티레벨 페이지 기법에서의 궁금한 점]

큰 덩어리로 나누고 페이지로 나눈다. 이 때 큰 덩어리 중 내부에 유효부분(페이지)가 없는 덩어리는 PDE의 Vaild=0으로 설정되는데 이 때 메모리를 차지하고 있는가? -> 차지함.

📊 멀티 레벨 페이지 시나리오 완벽 분석

전제 조건: 전체 주소 공간이 4개의 큰 덩어리로 나뉘어 있고, 각 덩어리용 하위 페이지 테이블 크기는 4KB이다.
상황: 4개의 덩어리 중 2개는 내부에 유효부분 있고, 2개는 아예 안 쓴다(텅 빈 공간).

1. 만약 과거의 '선형 페이지 테이블'이었다면? (비교 대상) 빈 공간이든 아니든 무조건 하나의 거대한 표를 만들어야 합니다.

4개 덩어리 분량의 페이지 테이블 무조건 생성 = 총 16KB 메모리 차지 (엄청난 낭비 발생)

2. 멀티 레벨 페이지 테이블을 적용한 계산

유효한 덩어리 (2개): 안에 쓸 데이터가 있으니 진짜 하위 페이지 테이블 2개를 만듭니다. -> 8KB 할당
텅 빈 덩어리 (2개): 하위 페이지 테이블을 아예 안 만듭니다! 대신 페이지 디렉터리에 있는 Valid=0짜리 PDE 2개(4바이트 + 4바이트 = 8바이트)만 남겨둡니다. -> 8KB(8192바이트) 할당 안 함 = 정확히 8KB 절약!!

💡 결론

*"정확히 8KB의 메모리를 아낀 것"**이 맞습니다!

이 상황을 우리가 처음에 이야기했던 명언으로 바꿔보면 이렇게 됩니다.

"고작 8바이트(PDE 2개 자리)를 내어주고, 무려 8192바이트(8KB)의 메모리 낭비를 완벽하게 방어해 냈다!"

이어서 확실하게 바로잡기. 필요한 공간은 (PDE 4개)16바이트 + 8KB가 아니라, 4KB(디렉터리) + 8KB(하위 테이블) = 총 12KB

"그럼 디렉터리 자리는 16바이트인가?"

왜 16바이트가 아니라 4KB가 되는지, 그 'OS의 절대 원칙'을 설명.

1. OS의 절대 원칙: "모든 할당은 '페이지 단위(4KB)'로만 이루어진다"

운영체제는 물리 메모리(RAM)를 1바이트, 16바이트 단위로 쪼개서 빌려주지 않습니다. 무조건 하나의 프레임(보통 4KB 크기의 상자) 단위로만 던져줍니다.

최상위 목차인 페이지 디렉터리를 만들 때, 그 안에 들어갈 PDE가 4개(16바이트)든 1024개(4096바이트)든 상관없이, 운영체제는 무조건 온전한 1페이지(4KB) 상자 1개를 통째로 할당합니다.
16바이트만 쓰고 남은 4080바이트의 공간은 빈칸으로 두더라도 상자 전체를 차지하게 됩니다. (이것이 이전에 배웠던 '내부 단편화'의 일종입니다.)

2. 진짜 메모리 소비량 최종 정산

시나리오(총 4덩어리 중 2개만 유효함)를 바탕으로 진짜 영수증을 뽑아보겠습니다.

페이지 디렉터리 (최상위 목차): 무조건 1장 필요 = 4KB
페이지 테이블 (하위 본문): 유효한 덩어리 2개 분량 = 8KB
총 차지하는 메모리: 12KB

📊 선형 구조 vs 멀티 레벨 진짜 비교

과거 (선형 페이지 테이블): 디렉터리 없이 그냥 거대한 본문 4장 = 16KB
현재 (멀티 레벨 테이블): 목차 1장(4KB) + 유효 본문 2장(8KB) = 12KB
최종 절약된 메모리: 정확히 4KB (1페이지 분량 절약!)

💡 최종 결론 멀티 레벨 구조는 하위 테이블을 안 만들어서 메모리를 엄청나게 아끼는 대신, **"페이지 디렉터리라는 4KB짜리 상위 목차용 상자를 무조건 하나 유지해야 한다"**는 작은 초기 비용(Overhead)을 지불하는 구조입니다.

<문제 하나로 복습 간단히 진행>

가상 주소 공간(32bit), 페이지 크기(4KB), PTE크기(4Byte), PDE 1개 크기: 4바이트

[계산과정]

1. 페이지 테이블 1조각에 PTE 몇 개가 들어가지?

- 4KB / 4바이트 = 2^10 = 1024개

2. 이 시스템은 총 몇 개의 가상 페이지(VPN)를 가질까?

- 4GB(주소공간 2^32) / 4KB(페이지크기) = 2^20 (약 100만 개) (총 100만 개의 잎사귀(페이지) 존재.

3. 그럼 하위 페이지 조각은 총 몇 개가 필요할까?(모든 페이지 유효하다고 치고 할당할 때?)

총 페이지 수 / 한 페이지 테이블 PTE 총 개수 = 하위 페이지 조각 개수

- 2^20 / 1024 = 1024개!!

1. 멀티 레벨 페이지 테이블의 마무리 (13~20페이지)

[13페이지] 멀티 레벨 테이블의 장단점
- 장점: 사용 중인 주소 공간에 비례해서만 페이지 테이블을 할당하므로 메모리가 획기적으로 절약됩니다 . 또한 공간이 더 필요해지면 OS가 물리 메모리의 빈 페이지(4KB 프레임)를 쉽게 가져다 붙일 수 있습니다.
- 단점: 테이블을 여러 번 참조해야 하므로 구조가 복잡해지고, 시간(Time)과 공간(Space)을 맞바꾼 트레이드오프(Trade-off)가 발생합니다 .
[14페이지] 간접 참조 (Level of indirection)
- 멀티 레벨 구조는 '페이지 디렉터리'라는 목차를 두어 간접 참조의 수준을 조절합니다 . 이 덕분에 하위 테이블 조각들을 물리 메모리 상의 빈 공간 아무 곳에나 마음대로 흩뿌려 배치할 수 있게 됩니다.

[15~17페이지] VPN 쪼개기 예시 (2단계 구조)
- 우리가 앞서 완벽히 계산했던 예시입니다! 가상 주소 14비트 중 VPN 8비트를 반으로 쪼갭니다 .
  - 앞의 4비트는 최상위 디렉터리에서 큰 덩어리를 찾는 '디렉터리 인덱스'로 쓰고 , 뒤의 4비트는 그 덩어리 안에서 진짜 PTE를 찾는 '페이지 테이블 인덱스'로 사용합니다 . (페이지 크기 = 페이지 디렉 크기 =페이지 테이블 크기 = 64Byte인데 PTE 크기 = 4Byte이면 테이블에 들어갈 수 있는 PTE 갯수는 16개이므로 VPN에서 PTE INDEX를 위한 비트 수는 4비트가 필요하게 되며, 자연스럽게 PDE INDEX를 위한 비트 수도 4bit가 필요하기에 4bit 4bit로 VPN이 쪼개지게 된다.

[18~20페이지] 3단계(Level) 이상의 구조
- 만약 주소 공간이 30비트로 엄청 커지면 어떻게 될까요? VPN이 21비트가 됩니다 .
- 페이지 크기 512Byte -> 오프셋 9bit, 페이지 크기 / PTE 크기 = PTE 갯수 -> 128개 (7bit 필요) 이게 PTE index를 위해 필요 + PDE index를 위해 필요. 근데 그렇게 14bit 할애해도 7bit가 남네??
- 테이블 1조각에 128개의 항목(7비트 필요)이 들어간다면, 21비트를 7비트씩 3번 쪼개야 합니다 .
- 이렇게 되면 페이지 디렉터리가 2계층으로 늘어나, 총 3단계(3-level) 트리 구조가 됩니다 . 하드웨어가 주소 변환을 위해 메모리를 3번이나 뒤져야 하는 구조입니다.

2. 획기적인 발상: 역 페이지 테이블 (21~22페이지)

[21~22페이지] 역 페이지 테이블 (Inverted Page Tables)
- 기존에는 프로세스마다 1개씩 테이블을 가졌지만, 이 방식은 발상을 뒤집어 시스템 전체의 '물리 메모리 프레임' 개수만큼만 딱 1개의 거대한 테이블을 만듭니다 .
- "물리 메모리 1번 방에는 프로세스 A의 5번 가상 페이지가 들어있다"는 식으로 기록합니다 .
- 장단점: 메모리 소비량은 극단적으로 줄어듭니다. 하지만 변환 정보를 찾기 위해 TLB miss 시에 표를 처음부터 끝까지 다 뒤져야(Search) 해서 속도가 매우 느리다는 치명적인 단점이 있습니다. (이를 해결하기 위해 해시(Hash) 기법을 씁니다.)

3. 가상 메모리의 마법: 스와핑과 페이지 폴트 (23~34페이지)

[23~31페이지] 스와핑 (Swapping)의 개념

컴퓨터의 메모리에는 계층 구조가 있습니다 (레지스터 -> 캐시 -> 메인 메모리 -> 하드 디스크) .
램(RAM)의 용량이 꽉 차면, OS는 당장 안 쓰는 페이지를 하드 디스크의 특정 구역인 **'스왑 공간(Swap Space)'**으로 잠시 쫓아냅니다 (Swap-out) .
나중에 필요해지면 다시 메모리로 불러옵니다 (Swap-in). 이 마법 덕분에 여러 프로그램이 동시에 실행되며 거대한 메모리를 쓰는 것처럼 착각하게 됩니다 .

[32페이지] Present 비트
- PTE 안에 '이 데이터가 진짜 물리 메모리에 있는가?'를 나타내는 Present 비트가 추가됩니다. 1이면 메모리에 있는 것이고, 0이면 디스크(스왑)로 쫓겨난 상태입니다 .
[33~34페이지] 페이지 폴트 (Page Fault)
- Present 비트가 0인 데이터를 읽으려 하면 하드웨어가 SOS를 치는데, 이를 **페이지 폴트(Page Fault)**라고 부릅니다 .
- 이때 OS(Page-fault handler)가 깨어나 디스크에서 해당 페이지를 찾아 빈 물리 메모리에 올려주고, 테이블을 수정한 뒤 프로그램을 다시 실행시켜 줍니다 .

4. 누구를 쫓아낼 것인가? 교체 정책 (35~63페이지)

[35~40페이지] 교체 시기와 대상
- OS는 메모리가 완전히 0%가 될 때까지 기다리지 않고, 여유 공간이 하한선(LW) 밑으로 떨어지면 백그라운드 데몬(스레드)을 깨워 미리미리 페이지를 디스크로 쫓아내 여유를 확보합니다 . (여유 메모리 공간이 LW 밑으로 떨어지면 HW까지 도달할 때까지 쫓아냄)
- OS 커널의 중요 코드나 페이지 테이블은 절대 쫓겨나지 않고(Not swapped), 주로 유저 프로그램의 힙/스택 페이지들이 교체 대상이 됩니다 .

커널, 페이지 테이블들은 스왑안됨. disk에 저장되어 있는 애들은 스왑하며 비용쓰는 것보다 삭제해서 필요하면 가져오면된다.(힙/스택)

파일들, 페이지 캐시 페이지들은 버리거나 파일시스템으로!

[41~51페이지] 교체 알고리즘의 기초 (OPT, FIFO, Random)

목표는 캐시 미스율을 낮추는 것입니다 .
OPT (Optimal): 가장 먼 미래에 사용될 페이지를 쫓아내는 완벽한 신의 알고리즘입니다 . 하지만 미래를 예측할 수 없기에 실제 구현은 불가능하고, 성능 비교용 기준으로만 쓰입니다.
FIFO: 무조건 가장 먼저 들어온 놈을 쫓아냅니다 . 편하지만, 자주 쓰는 중요한 데이터도 오래되었다고 쫓아내는 멍청함이 있습니다 . (캐시를 늘려도 오히려 성능이 떨어지는 **Belady's Anomaly(벨라디의 모순)**가 발생할 수 있습니다 .)
Random: 운에 맡기고 아무나 쫓아냅니다. 어떨 땐 최적만큼 좋고, 어떨 땐 최악입니다 .

[52~58페이지] 역사를 잊은 자에게 미래는 없다: LRU (중요!)

과거의 기록으로 미래를 예측합니다 .
LRU (Least Recently Used): '가장 오랫동안 사용되지 않은' 페이지를 쫓아냅니다 . 자주 쓰는 데이터만 계속 쓰는 현실적인 환경(Locality, 80-20 워크로드)에서 최적(OPT)에 가까운 최고의 성능을 냅니다 . (다만, 순차적으로 계속 반복 순회하는 Looping-Sequential 환경에서는 최악의 성능을 보입니다 .)

[59~62페이지] 현실적인 타협안: 시계(Clock) 알고리즘

순수한 LRU는 매번 시간을 기록해야 해서 구현이 너무 무겁습니다 .
그래서 Use 비트 (하드웨어가 페이지를 읽을 때마다 1로 켜주는 스위치)를 활용합니다 .
시계바늘이 빙글빙글 돌면서 검사합니다. Use 비트가 1이면 "최근에 썼군. 한 번 봐준다"라며 0으로 바꾸고 넘어갑니다. 하지만 바늘이 돌고 돌아왔는데도 Use 비트가 여전히 0이라면 "최근에 안 썼군!" 하고 가차 없이 쫓아냅니다 .

[63페이지] 더티 비트 (Dirty Bit)
- 메모리에서 수정된 적이 있는 페이지(Dirty)는 쫓겨날 때 변경 사항을 디스크에 적어줘야(Write-back) 하므로 비용이 큽니다 . 반면 수정된 적 없는 깨끗한 페이지(Clean)는 그냥 버리기만 하면 무료입니다. OS는 이왕이면 공짜인 깨끗한 페이지를 먼저 쫓아내려 합니다.

5. 메모리의 과부하 현상 (64~68페이지)

[64~66페이지] 기타 똑똑한 정책들. OS는 메모리로 페이지 가져올 때 결정해야함!(Page Selection policy)

Prefetching (선반입): 1번 페이지를 요청할 때, OS가 '어? 2번 3번도 곧 쓰겠네?' 하고 미리 묶어서 가져옵니다 .

Clustering: 디스크에 쓸 때도 하나씩 안 쓰고 모아놨다가 한 번에 왕창 씁니다 (비용 절감) .

[67페이지] 쓰레싱 (Thrashing)
- 실행 중인 프로그램들이 요구하는 메모리의 총합이 실제 물리 메모리를 훌쩍 넘어선 과부하 상태입니다 .
- OS가 디스크와 메모리 사이에서 짐(페이지)을 넣고 빼느라 너무 바빠서, 정작 CPU는 일(계산)을 하나도 못하고 멍때리는 최악의 상태가 됩니다 (그래프에서 CPU 이용률이 급락하는 구간) .

가상 머신 메커니즘: 물리&가상 주소 / 파편화, 세그먼테이션, 페이징 / 페이지 테이블 관리, TLBs

가상 머신 정책: 페이지 교체 정책, 페이지 할당 정책

가상 머신 최적화: 요구 페이징, copy on write(공간) / 멀티 레벨 페이지 테이블 (공간) / TLB 이용한 효율적 변환(시간)/ 페이지 교체 정책(시간)

'CS > OS' 카테고리의 다른 글

운영체제(OS)-WEEK6 (2) Disadvantage of Linear Tables, Hybrid Approach, Multi-Level Page tables (0)	2026.04.09
운영체제(OS)-WEEK5 (2) [페이징(Paging)]+WEEK6 (1) (0)	2026.04.03
운영체제(OS)-WEEK4 [메모리 가상화(Memory Virtualization)] (0)	2026.04.01
운영체제(OS)-WEEK3(2) MLFQ 시뮬레이터 구현하기 (with C) (0)	2026.03.26
운영체제(OS)-WEEK3(1) 스케줄링(Scheduling) (0)	2026.03.17

assidu 님의 블로그