[OS] 외부 단편화를 해결한 Paging: 등장 배경과 한계

 

왜 메모리 가상화(Virtualization)가 필요할까?

우리가 만든 프로그램, 즉 프로세스들은 실행되려면 메모리(RAM)에 올라가야한다. 그런데 실제로는 여러 프로세스가 동시에 돌아가고 있다. 각 프로세스가 다른 프로세스의 메모리 영역을 침범하지 않으면서도, 마치 자신이 메모리 전체를 독점하는 것처럼 동작해야 한다. 이게 바로 메모리 가상화의 핵심 목표이다.

 

 

Segmentation의 문제점

지난번 포스팅 한 것 처럼 초기에는 Segmentation처럼 프로세스마다 가변적인 크기로 메모리를 할당하는 방식도 썼다. 이는 크기가 다른 서랍을 여러 개 사용하는 옷장과 비슷하다. 근데 이 방식의 가장 큰 문제점은 시간이 지날수록 메모리에 작고 쓸모없는 구멍들이 생기는 외부 단편화(External Fragmentation)가 발생한다. 비유하자면, 큰 옷을 넣을 공간은 없는데, 작은 양말 넣을 공간만 잔뜩 남는 것이다. 이러면 큰 프로세스가 메모리에 올라오기 힘들어지는 문제가 발생한다.
 
 

Paging: Fixed-Sized(고정 크기) 블록으로 문제를 해결

이 외부 단편화 문제를 해결하기 위해 도입된 기법이 바로 페이징(Paging)이다. Paging은 고정 크기 할당(Fixed-Sized Allocation) 전략을 사용한다.

 

1. 가상 메모리(Virtual Memory)를 페이지(Pages)라는 같은 크기의 블록으로 나눈다.
2. 물리 메모리(Physical Memory)도 프레임(Frames)이라는 페이지와 동일한 고정 크기 블록으로 나눈다.

 

 
이렇게 하면 모든 메모리 공간의 단위가 똑같으니까, 어떤 프로세스든 필요한 페이지 수만큼 빈 프레임을 찾아서 메모리에 올리기만 하면된다. 레고 블록처럼, 모든 조각의 크기가 같으니 원하는 모양을 만들기 쉽고, 빈 공간을 메우기도 깔끔하다.

 

가장 큰 장점은 외부 단편화가 없다는 것이다..!
 
 
 

---

 
 

Page Table

Paging을 쓰면 프로세스의 페이지들이 물리 메모리의 여기저기 흩어져서 비연속적으로 저장될 수 있다. CPU가 발생시킨 가상 주소(Virtual Address)를 실제 메모리 위치인 물리 주소(Physical Address)로 어떻게 변환할까?
 

 

이 역할을 하는 게 바로 Page Table이다.

 

1. 주소 분리: 가상 주소는 VPN(Virtual Page Number)과 Offset, 두 부분으로 나뉜다.

• VPN: 프로세스 내에서 해당 데이터가 몇 번째 페이지에 있는지 나타낸다.
• Offset: 해당 페이지 블록 내에서 정확히 몇 번째 바이트에 데이터가 있는지 나타낸다.
   

 

2. PFN 찾기

• OS는 프로세스마다 유지하는 페이지 테이블에서 VPN을 인덱스로 사용해서
• 이 페이지가 물리 메모리의 몇 번째 프레임에 있는지 나타내는 물리 프레임 번호(PFN, Physical Frame Number)를 찾는다.

 
3. 물리 주소 생성: 찾은 PFN을 가상 주소의 VPN 위치에 덮어쓰고, 오프셋은 그대로 유지하면 실제 물리 주소가 완성된다.

 
 
 
Paging에서 주소 변환을 구조화하면 다음과 같다.

 
 
 

---

 
 
 

Page table은 어디에 저장될까?

Paging주소변환 가정은 이해가 되는데, 한 가지 궁금증이 생긴다. 그러면 Page table은 어디에 저장될까? 
우선 Page table은 크기가 매우 크다.

 

간단한 예를 들어보자.

• 32비트 주소 공간을 사용하는 시스템이 있다.
• 4KB (2^12 바이트) 크기의 페이지를 쓴다고 가정해 보자.

1. 32비트 주소에서 아래 12비트는 페이지 내 위치를 나타내는 Offset에 할당된다. (페이지의 크기가 2^12B이기 때문이다: 페이지 크기 = 필요한 오프셋 비트 수)
2. 나머지 20비트가 VPN에 할당된다.
3. VPN이 20비트라는 건, 페이지 테이블에 2^20 개의 엔트리(PTE)가 필요하다는 뜻이다.
4. PTE 하나가 4바이트라고 치면, 프로세스 하나당 페이지 테이블 크기는 2^20×4B=4MB가 된다.
5. 만약 시스템에서 100개의 프로세스가 돌고 있다면? 즉, 단순히 페이지 테이블만으로 약 400MB의 메모리를 소모하게 된다.

 

 

이 크기는 옛날 Base and Bounds 방식에서 썼던 레지스터에 비하면 매우 큰 크기이다. 
 
페이지 테이블이 이렇게 크기 때문에 CPU 안에 있는 MMU(Memory Management Unit) 같은 칩 상의 특별한 하드웨어에 저장할 수가 없다.

 

 

 

최종 Page table 위치

결국, 운영체제(OS)가 관리하는 일반적인 물리 메모리(OS-managed physical memory)에 저장할 수밖에 없다. 다시 말해, 사용자가 깔아놓은 게임이나 코드가 쓰는 RAM 공간 일부를 떼어다가 OS가 페이지 테이블을 보관하는 용도로 쓴다.
 

 
 

---

 
 

PTE의 구성 

페이지 테이블은 결국 가상 주소(VPN)를 물리 주소(PFN)로 매핑하는 역할을 한다. 가장 단순한 형태는 그냥 배열인 선형 페이지 테이블(Linear Page Table)이다.

 

OS는 가상 페이지 번호인 VPN을 배열의 인덱스로 사용해서 해당 페이지에 대한 정보를 담고 있는 PTE(Page Table Entry)를 찾아낸다. 이 PTE 안에는 PFN 외에도 OS가 프로세스를 관리하는 데 필요한 여러 비트(bit) 정보들이 담겨 있다.

• Valid Bit
  • 해당 주소 변환이 유효한지 여부. 만약 유효하지 않은 영역(예: 힙과 스택 사이의 빈 공간)에 접근하면 세그멘테이션 폴트 (Segmentation Fault) 발생.
• Protection Bit
  • 해당 페이지에 읽기(Read), 쓰기(Write), 실행(Execute) 권한이 있는지 설정. 권한이 없는데 접근하면 보호 폴트 (Protection Fault) 발생.
• Present Bit
  • 페이지가 현재 물리 메모리(RAM)에 있는지 아니면 디스크에 Swap-out되어 있는지 나타낸다.
• Dirty Bit
  • 페이지가 메모리에 올라온 후 수정(Write)되었는지 여부. 수정되지 않았다면 디스크 I/O를 생략할 수 있다.
• Reference Bit (Accessed Bit)
  • 페이지가 최근에 접근(Read/Write)되었는지 여부. 이는 메모리 부족 시 어떤 페이지를 디스크로 내보낼지 결정하는 페이지 교체 알고리즘에 사용.

 

 

 

 

 

---

 
 

Paging의 한계: Too Slow

 
페이지 테이블이 물리 메모리에 저장된다는 걸 알게 되었다. 이 사실이 바로 페이징이 안고 있는 가장 심각한 문제, 즉 메모리 접근 오버헤드를 만든다.

 

모든 접근에 추가되는 메모리 참조

CPU는 현재 실행 중인 프로세스의 페이지 테이블 시작 주소를 PTBR(Page-Table Base Register)에 저장하고 있다.
CPU가 어떤 가상 주소로 메모리에 접근하려고 할 때 일어나는 일은 이래:

 

1. 예를 들어, 16바이트 페이지를 쓰는 64바이트 주소 공간이라면, 6비트 중 상위 2비트가 VPN, 하위 4비트가 오프셋이다.
2. VPN 추출: 가상 주소를 VPN(Virtual Page Number)과 Offset으로 나눈다.
3. PTE 인출 (첫 번째 메모리 접근): VPN을 사용해서 PTBR이 가리키는 물리 메모리에서 PTE를 가져온다.
4. PFN 추출: PTE에서 PFN(Physical Frame Number)을 추출한다.
5. 물리 주소 완성: PFN과 Offest을 결합하여 최종 물리 주소를 만든다.
6. 실제 데이터 접근 (두 번째 메모리 접근): 완성된 물리 주소로 다시 물리 메모리에 접근해서 데이터를 가져오거나 쓴다.

 

 
결과: 원래 1번이면 끝날 메모리 접근이, PTE를 가져오는 과정이 추가되면서 2번으로 늘어난다. 이로 인해 메모리 접근이 두 배로 늘어나며, 시스템 전체 성능 저하로 이어진다.

 

 

오버헤드의 현실

이 오버헤드가 현실에서 얼마나 발생하는지 간단한 반복문 코드로 살펴보자:

for (i=0; i<1000; i++)
    array[i] = 0;

 

먼저, 우리가 살고 있는 가상의 OS 환경부터 정리하자.
 

1. 페이지 크기: 1KB (2^10B).
   • 주소 중 하위 10비트가 오프셋, 상위 6비트가 VPN이다.
2. 페이지 테이블 위치 (PTBR): 페이지 테이블은 물리 주소 1024에서 시작한다.
   
   • 102410​=00000100000000002​ 이니까, VPN 1에 있다.
   • 이 VPN 1은 PFN 4로 매핑된다.
3. 코드 위치: for 루프의 코드는 가상 주소 1024에서 시작하며, 이는 VPN 1에 해당하고, 이 VPN 1은 PFN 4로 매핑된다.
4. 배열 위치: 배열 array[1000]은 가상 주소 40000에서 시작한다.

• 40000은 이 환경에서 VPN 39로 시작한다.
  
  • 배열은 여러 페이지에 걸쳐 있는데, VPN 39는 PFN 7로 매핑된다.

 
 
 
 

핵심 명령어 분석: movl $0x0, (%edi,%eax,4) 

우리가 분석할 명령어는 array[i] = 0에 해당하는 이 명령어 하나이다. 이 명령어는 "배열의 특정 위치(데이터)에 0을 써라"는 뜻이다.
이 명령어 하나가 실행되려면 CPU는 두 가지를 해야한다: 명령어 자체를 읽어야 하고 (Code Fetch), 데이터를 읽거나 써야 한다 (Data Access).
 

단계	목적	필요한 정보	메모리 접근 횟수
1. 코드 페치 (Code Fetch)	movl 명령어 자체를 읽어오는 과정	movl의 가상 주소 1024	2회
2. 데이터 접근 (Data Access)	array[i]에 0을 쓰는 과정	array[i]의 가상 주소 40000	2회
총계	명령어 1개 실행		4회

 

 

 

 

 
단 하나의 movl 명령어 처리 과정에서만 4번의 메모리 접근이 필요하다. 그중 절반인 2번은 PTE를 위한 접근이다.
핵심은, 단 하나의 명령어를 실행할 때도 코드 접근과 데이터 접근 각각에서 페이지 테이블을 참조해야 한다는 점이다. 이 때문에 실제 메모리 접근 횟수가 두 배로 늘어나며, 성능 저하로 이어진다.
 
 

• 나머지 3개 명령어 (incl, cmpl, jne)는 데이터 접근(배열)이 없지만, 명령어 인출 자체를 위해 각각 PTE 접근 1회 (PT[1]) + 명령어 인출 1회가 필요하다.
• 따라서 3 * 2 = 6회의 추가 메모리 접근이 발생한다.
• 루프 한 번(i=0일 때)의 총 메모리 접근 횟수는 4회(movl) + 6회(나머지) = 10회이다.

 
결론적으로, 루프 한 번 돌 때 총 10번의 메모리 접근이 발생하며, PTE를 위한 참조가 대다수이다. 페이징이 메모리 관리의 유연성을 가져왔지만, 성능 면에서는 끔찍한 대가를 치르고 있다.
 

 

 

---

 
 

정리

1. 주소 분리 

CPU가 메모리에 접근하려고 가상 주소(virtual address)를 발생시키면, MMU(Memory Management Unit)가 이 주소를 두 부분으로 쪼갠다:

• p (VPN, Virtual Page Number): 데이터가 프로세스의 몇 번째 페이지에 있는지 나타내는 번호.
• d (Offset, 오프셋): 해당 페이지 블록 내에서 정확히 몇 번째 바이트에 있는지 나타내는 위치.

 

2. 페이지 테이블 조회 

쪼개진 p (VPN)는 페이지 테이블(page table)을 인덱스로 조회하는 데 사용된다.

• 페이지 테이블은 p에 해당하는 엔트리(Entry)를 찾고, 그 안에 저장된 정보를 확인한다.
• 가장 핵심적인 정보는 v (Valid Bit)와 f (PFN, Physical Frame Number)이다.

 

3. 물리 주소 생성

페이지 테이블에서 유효성(v)이 확인된 후, f (PFN)를 가져온다:

• f (PFN)는 가상 주소의 p (VPN) 자리를 대체하고,
• d (Offset)는 그대로 유지되어,
• 물리 주소(physical address)가 완성된다.

이렇게 변환된 물리 주소를 사용해 CPU는 실제 메모리에 접근한다.
 

 

 
 

페이징의 장점과 한계

이 작동 방식을 통해 페이징은 다음과 같은 장단점을 가지게 된다.
 

Paging의 장점

• external fragment 제거 : 고정 크기 단위로 메모리를 관리하기 때문에, 크기가 다른 빈 공간 때문에 발생하는 낭비가 없다.
• 빠른 할당 및 해제 : 연속된 공간을 찾을 필요가 없고, 해제 시 주변 공간과 병합할 필요가 없어 메모리 관리가 단순하고 빠르다.
• 쉬운 디스크 스와핑 : 페이지 단위로 메모리를 디스크에 쉽게 옮길 수 있으며, Valid Bit으로 페이지가 메모리에 없는 상태를 감지할 수 있다.
• 쉬운 보호 및 공유 : 페이지 단위로 메모리 접근 권한을 설정하거나, 여러 프로세스가 하나의 프레임을 공유하기 쉽다.

 

Paing의 한계

• internal fragment(내부 단편화) : 프로세스가 페이지의 마지막 공간을 다 쓰지 못하면 발생하는 낭비 공간(wasted space)은 남아있다.
• 메모리 참조 오버헤드 : 매번 PTE를 가져오기 위해 메모리에 추가로 접근해야한다.
  
  • 해결책: 하드웨어 캐시를 사용하면 된다.
• 페이지 테이블 크기 : 32비트/4KB 페이지 기준으로 프로세스당 4MB씩, 총 400MB 이상의 메모리를 페이지 테이블 유지에 낭비할 수 있다.
  
  • 해결책: Multi-level Page Tables 같은 구조를 사용해야한다.

 
결론적으로, 페이징은 메모리 관리의 효율성과 안정성을 크게 높였지만, 성능 오버헤드 문제를 해결하기 위해 TLB와 Multi-level Page Tables 같은 추가 기술이 필요하다.
 
 
 
 

출처: 경북대학교 한명균 교수님, “운영체제” 강의 자료