[운영체제] 페이징(Paging) | Page Table, Copy-on-Write, TLB

Paging, 메모리 관리의 혁신

지난 글에서는 세그멘테이션(Segmentation)이 외부 단편화(External Fragmentation)라는 치명적인 문제에 봉착했음을 확인했다. 가변적인 크기의 세그먼트들이 생성되고 사라지기를 반복하면서, 물리 메모리에는 그 누구도 사용할 수 없는 애매한 크기의 구멍들이 숭숭 뚫려버렸다.

Review: External Fragmentation

이 문제를 해결하기 위해 OS 개발자들은 새로운 접근을 시도했다. "더 이상 프로세스에게 크기의 자유를 주지 말자." 대신, 모든 메모리 공간을 고정된 크기(Fixed-sized unit)로 잘게 썰어서 관리하기로 한 것이다. 이것이 바로 페이징(Paging)의 시작이다.

1. 페이징의 핵심 아이디어

페이징은 메모리 관리의 패러다임을 완전히 바꿨다. 논리적인 의미(코드, 힙, 스택)보다는 물리적인 규격을 우선시한다.

가상 페이지 (Virtual Page): 가상 주소 공간을 고정된 크기로 나눈 조각.
페이지 프레임 (Page Frame): 물리 메모리를 가상 페이지와 동일한 크기로 나눈 조각.

이제 OS는 '크기'를 고민할 필요가 없다. 64바이트 가상 페이지는 64바이트 물리 프레임 어디에나 쏙 들어간다. 즉, 외부 단편화가 완벽하게 사라진다. 또한, 힙과 스택이 어느 방향으로 자라나는지 신경 쓸 필요 없이, 필요한 만큼 페이지만 할당해 주면 되므로 관리가 매우 수월해진다.

Simple paging

2. 주소 변환: VPN과 Offset

가상 주소(Virtual Address)를 물리 주소(Physical Address)로 바꾸는 방법도 세그멘테이션과는 다르다. 가상 주소는 크게 두 부분으로 나뉜다.

VPN (Virtual Page Number): 해당 주소가 몇 번째 페이지에 있는가?
Offset (VPO): 페이지 내부에서 정확히 어디에 위치하는가?

주소 변환의 핵심은 "VPN을 물리 프레임 번호(PFN)로 교체하되, Offset은 그대로 둔다"는 것이다.

예를 들어, 64바이트 주소 공간에서 16바이트 크기의 페이지를 사용한다고 가정해보자. 가상 주소 21 (이진수 010101)이 들어왔다.

VPN 추출: 상위 2비트 01은 1번 페이지를 의미한다.
변환: 페이지 테이블을 조회하여 1번 페이지가 물리 메모리의 7번 프레임(PFN 7)에 있다는 것을 알아낸다.
병합: PFN 111 (7)과 기존 Offset 0101 (5)을 합쳐 물리 주소를 완성한다.

Address translation for paging

3. 페이지 테이블 (Page Table)

그렇다면 "몇 번 페이지가 몇 번 프레임에 있는지"는 어디에 적혀 있을까? 이 매핑 정보를 담고 있는 거대한 자료 구조가 바로 페이지 테이블(Page Table)이다.

Page Table

역할: 가상 주소의 VPN을 인덱스로 사용하여 해당 PTE(Page Table Entry)를 찾고, 거기서 PFN을 얻는다.
구조: 가장 단순한 형태는 선형 배열(Linear Array)이다.
위치: 세그멘테이션 때는 레지스터 몇 개로 충분했지만, 페이징에서는 페이지 개수가 워낙 많기 때문에 페이지 테이블을 메모리(Memory)에 저장한다.

4. PTE (Page Table Entry)

페이지 테이블의 각 행인 PTE는 단순히 물리 주소(PFN)만 담고 있는 것이 아니다. OS가 메모리를 정교하게 관리하기 위한 중요한 상태 비트(Flags)들을 포함한다.

Valid bit: 이 페이지가 실제로 사용 중인지, 즉 유효한 변환인지 나타낸다.
Protection bit: 읽기(Read), 쓰기(Write), 실행(Execute) 권한을 설정한다.
Present bit: 해당 페이지가 물리 메모리에 있는지, 아니면 디스크(Swap)로 쫓겨났는지 알려준다.
Dirty bit: 메모리에 올라온 이후 수정된 적이 있는지 표시한다.
Reference bit: 최근에 접근된 적이 있는지 나타내며, 이는 나중에 페이지 교체 알고리즘에서 중요하게 쓰인다.

PTE with flags

5. 페이징의 힘: 공유와 보호 (Sharing & Protection)

페이징 시스템은 메모리를 단순히 나누는 것을 넘어, 프로세스 간의 협업과 보안을 가능하게 한다.

페이지 공유 (Page Sharing)

fork() 시스템 콜을 생각해보자. 프로세스를 복제할 때 메모리를 전부 복사하는 것은 비효율적이다. 페이징을 사용하면 부모와 자식 프로세스의 페이지 테이블이 동일한 물리 프레임(Physical Frame)을 가리키게 함으로써 코드를 공유할 수 있다.

Page Sharing

만약 둘 중 하나가 데이터를 수정하려고 하면? 그때 OS가 개입하여 해당 페이지만 복사해 주는 CoW (Copy-on-Write) 기법을 통해 효율성을 극대화한다.

CoW

페이지 보호 (Page Protection)

코드(Code) 영역은 실행되어야 하지만 수정되면 안 된다. PTE의 Protection bit를 Read-Execute로 설정해두면, 해커나 버그가 코드 영역에 쓰기(Write)를 시도할 때 하드웨어가 이를 막고 Trap을 발생시켜 시스템을 보호한다.

6. 페이징의 문제점: 두 번의 기억, 한 번의 실행

앞서 페이징이 외부 단편화 문제를 해결하고 메모리 관리를 유연하게 만든다는 것을 확인했다. 이론적으로는 완벽해 보였다. 하지만 페이징 시스템이 도입되면서 CPU가 메모리에 접근하는 과정은 더 복잡해졌다.

문제 1: 성능 저하 (Performance Degradation)

가장 심각한 문제는 메모리 접근 횟수의 증가다.

기존에는 주소 0x1000에 있는 데이터를 읽으려면 메모리에 한 번만 가면 됐다. 하지만 페이징 환경에서는 다음과 같은 과정을 거쳐야 한다.

페이지 테이블 접근: 가상 주소의 VPN을 이용해 메모리 어딘가에 있는 페이지 테이블 엔트리(PTE)를 읽어와야 한다. (1번 접근)
주소 변환: PTE에서 얻은 PFN과 오프셋을 합쳐 실제 물리 주소를 계산한다.
데이터 접근: 계산된 물리 주소로 실제 데이터에 접근한다. (2번 접근)

즉, 단순한 변수 하나를 읽으려 해도 메모리 접근 비용이 2배로 뛴다. 메모리는 CPU보다 훨씬 느리기 때문에, 이는 전체 시스템 성능을 반토막 내는 결과를 초래한다.

Performance Degradation

문제 2: 내부 단편화 (Internal Fragmentation)

외부 단편화는 해결했지만, 페이지 크기가 고정되어 있다 보니 프로세스가 필요한 메모리가 페이지 크기의 배수가 아닐 때 마지막 페이지의 일부 공간이 낭비된다. 예를 들어 2KB 페이지 시스템에서 100바이트만 필요해도 2KB 전체를 할당해야 하므로 1948바이트가 낭비되는 식이다.

결국 돌고돌아 가장 처음에 배운 Base and Bounds와 같이 내부 단편화 문제로 돌아왔냐?라고 생각할 수 있지만, 다행히도 free space 전부 낭비되던 Base and Bounds와 달리 고정된 페이지의 크기로 인한 일부의 내부 단편화만 일어난다.

Internal fragmentation

문제 3: 거대한 페이지 테이블 (Huge Page Tables)

32비트 주소 공간에서 4KB(12비트) 페이지를 사용하면 프로세스 하나당 약 4MB의 페이지 테이블이 필요하다. 100개의 프로세스가 실행되면 페이지 테이블만으로 400MB 메모리가 낭비된다. (이 문제는 추후 멀티 레벨 페이징에서 다룰 예정이다.)

Huge Page Table

2. 해결책: TLB (Translation Lookaside Buffer)

성능 저하 문제를 해결하기 위해 OS는 하드웨어의 도움을 요청했다. 그것이 바로 CPU 내부의 MMU(Memory Management Unit)에 위치한 TLB다.

TLB는 주소 변환을 위한 전용 하드웨어 캐시다.

가상 주소 VPN이 물리 주소 PFN으로 변환되는 매핑 정보를 아주 빠른 SRAM에 저장해 둔다.

TLB Entry

TLB의 동작 원리

프로세스가 메모리 접근을 요청하면 하드웨어는 페이지 테이블을 보기 전에 먼저 TLB를 확인한다.

TLB Hit: 찾고자 하는 VPN이 TLB에 있다.
- 페이지 테이블을 거치지 않고 바로 PFN을 얻는다. 메모리 접근 횟수가 1번으로 줄어든다 (원래 성능 회복).
  TLB Hit
TLB Miss: TLB에 정보가 없다.
- 어쩔 수 없이 메모리에 있는 페이지 테이블에 접근하여 PTE를 가져온다.
- 가져온 정보를 TLB에 기록하고, 명령어를 재실행한다.
  TLB Miss

왜 이것이 효과적일까? (Locality)

TLB Miss가 일어나면 결국 2번의 메모리 접근이 필요함에도 불구하고, 성능을 비약적으로 높여주는 이유는 프로그램의 지역성(Locality) 덕분이다.

시간적 지역성: 방금 접근한 주소(페이지)는 곧 다시 접근할 확률이 높다 (예: 루프 내의 변수).
공간적 지역성: 지금 접근한 주소 근처의 주소는 곧 접근할 확률이 높다 (예: 배열 순회).

배열 a[10]을 순회하는 코드를 상상해 보자 . 첫 번째 원소 a[0]에 접근할 때는 TLB Miss가 발생하지만, a[0]이 속한 페이지 정보가 TLB에 캐싱된다. 같은 페이지에 있는 a[1]부터 a[2], a[3] 등은 모두 TLB Hit가 되어 메모리 접근 없이 즉시 주소 변환이 가능하다. 결과적으로 평균 접근 시간은 획기적으로 줄어든다.

Locality

3. TLB Miss는 누가 처리하는가?

TLB에 정보가 없을 때(Miss), 누가 페이지 테이블을 뒤져서 정보를 가져올 것인가? 여기에는 두 가지 철학이 있다.

하드웨어 관리 (CISC 스타일, 예: Intel x86)

하드웨어가 페이지 테이블의 위치(PTBR 레지스터)와 구조를 이미 알고 있다.

Miss가 발생하면 하드웨어가 알아서 페이지 테이블을 탐색(Walk)하고 TLB를 업데이트한다.
OS는 페이지 테이블을 표준 규격에 맞춰 만들어주기만 하면 된다. 빠르지만 하드웨어 설계가 복잡하다.

Hardware-managed TLB

소프트웨어 관리 (RISC 스타일, 예: MIPS, RISC-V)

하드웨어는 Miss가 발생하면 예외(Exception)를 발생시키고 멈춘다.

OS의 Trap Handler가 깨어나서 소프트웨어적으로 페이지 테이블을 조회하고 TLB를 업데이트한 뒤 리턴한다.
OS가 페이지 테이블 구조를 마음대로 정할 수 있어 유연하지만, 처리 속도는 상대적으로 느리다.

Software-managed TLB

4. 문맥 교환(Context Switching)의 딜레마

프로세스가 바뀌면(Context Switch) 가상 주소 공간의 의미가 완전히 달라진다. 프로세스 A의 10번 페이지와 프로세스 B의 10번 페이지는 서로 다른 물리 주소를 가리켜야 한다. 하지만 TLB에는 "10번 페이지 -> 100번 프레임"이라는 정보만 남아있다. 이 문제를 어떻게 해결할까?

Confliction on TLB

방법 1: 싹 비우기 (Flush)

문맥 교환이 일어날 때마다 TLB의 모든 내용을 지운다(Valid bit를 0으로 설정).

장점: 구현이 단순하다.
단점: 프로세스가 바뀔 때마다 'Cold Start'가 되어 초반에 TLB Miss가 폭발적으로 발생한다. 성능 타격이 크다.

방법 2: 꼬리표 붙이기 (ASID)

TLB 엔트리에 ASID(Address Space ID)라는 프로세스 식별 필드를 추가한다.

이제 TLB는 "프로세스 A의 10번 페이지"와 "프로세스 B의 10번 페이지"를 구분할 수 있다.
문맥 교환 시 TLB를 비울 필요가 없으므로 성능 유지에 훨씬 유리하다.

ASID

마치며

오늘 학습을 통해 페이징이 세그멘테이션의 고질병이었던 외부 단편화 문제를 해결하고, 고정된 크기로 메모리 관리를 얼마나 간편하게 만들었는지 확인했다.

하지만 완벽해 보이는 이 시스템에도 속도와 용량 측면에서 한계가 있었다. 이때 TLB는 하드웨어의 지역성 원리를 이용해 그 속도를 다시 찾아주었다. 이제 우리는 '외부 단편화 없는 메모리(페이징)'를 '빠른 속도(TLB)'로 사용할 수 있게 되었다.

하지만 아직 해결하지 못한 마지막 문제가 남았다.

"프로세스마다 4MB씩 차지하는 페이지 테이블의 크기는 어떻게 줄일까?"

TLB가 속도 문제를 해결했다면, 공간을 구원할 기술도 분명 존재할 것이다. 다음 기록에서는 이 문제를 해결하는 멀티 레벨 페이징(Multi-level Paging)에 대해 알아보겠다.

추천글:

[운영체제] Operating System 전체 포스팅 모음집

[운영체제] 가상 메모리(Virtual Memory) | 운영체제는 어떻게 프로세스에게 독점 공간을 제공할까?

[운영체제] 세그멘테이션(Segmentation) | Segment, External Fragmentation, Free Space management