Concept of Paging¶

운영체제가 가상 메모리를 관리하는 방법

1. Segment (가변 크기로 분할)

프로세스의 주소 공간을 여러 개의 가변 길이 논리 세그먼트(예: 코드, 힙, 스택)로 나누는 것

Paging (고정된 방법으로 분할)

프로세스의 주소 공간을 고정된 크기의 단위(페이지)로 나누고, 물리적 메모리도 같은 크기로로 페이지 프레임(Page frame) 슬롯으로 나눈다.
프로세스 당 Page table을 갖고있고, 가상 메모리 주소를 실제 메모리 주소로 변환하는 과정이 필요하다.

Paging의 장점
1. Flexibility: 추상화된 주소 공간을 효과적으로 지원 (heap, stack 성장 방향과 사용 방법에 대해서 신경쓸 필요 없다.)
2. Simplicity: 가상 주소 공간의 미사용 부분 관리가 더 쉬움
3. Efficiency: 페이징(설계에 따라)은 메모리를 고정된 크기의 단위로 분할하기 때문에 외부의 단편화 문제를 해결할 수 있다.
Paging 단점
1. 메모리 낭비 (실제 애플리케이션 데이터가 아닌 페이지 테이블로 메모리가 가득 차게 됨)
2. 페이지 테이블에 액세스하기 위한 추가 메모리 액세스 필요하다.

A Simple Example And Overview¶

64바이트 크기의 주소 공간을 고정된 사이즈 16 바이트 씩 나눔

위 그림은 4개의 16바이트 페이지(가상 페이지 0, 1, 2, 3)가 있는 64바이트 크기의 작은 주소 공간의 예를 보여준다.

128 바이트 물리 메모리 with 16 바이트 페이지 프레임 예시도 보자.

가상 주소 공간의 페이지는 전체 물리적 메모리에서 서로 다른 위치에 배치되어 있다는 것을 볼 수 있다.
OS는 물리적 프레임 3의 주소 공간(AS)에 가상 페이지 0, 물리적 프레임 7의 AS에 가상 페이지 1, 프레임 5의 페이지 2, 프레임 2의 페이지 3을 배치한다. 페이지 프레임 1, 4, 6은 현재 빈 공간이다.

- Address Translation¶

Page Table¶

프로세스의 가상 주소를 물리주소로 변환하기 위한 2가지 필수 요소
1. 가상 페이지 번호(VPN) - 주소 상위 2비트
  
  가상 주소의 페이지 번호
2. 페이지 내 오프셋
  
  페이지 프레임에서 어느 바이트에 있는지

가상 주소 <페이지 VPN, 거리 Offset> → 물리 메모리 <프레임 PFN, 거리 Offset>

페이지 테이블

프로세스 단위의 데이터 구조 (모든 데이터 구조 사용 가능)
주소 공간의 각 가상 페이지가 물리적 메모리에 배치되는 위치를 기록하여 가상 주소(또는 실제로는 가상 페이지 번호)를 물리적 주소(물리적 프레임 번호)에 매핑하는 데 사용

가장 간단한 형태: 선형 페이지 테이블이라고 불리는 단순한 배열
- 물리 프레임 번호를 찾기 위해 가상 페이지 번호로 배열에 접근하여 페이지 테이블 항목을 검색하는 구조

DATA STRUCTURE - THE PAGE TABLE

현대 OS의 메모리 관리 서브시스템에서 가장 중요한 데이터 구조 중 하나는 페이지 테이블이다.
일반적으로 페이지 테이블은 가상 주소에서 물리적 주소로의 변환을 저장하여 주소 공간의 각 페이지가 실제로 물리적 메모리 내에 어디에 존재하는지 시스템에 알려준다.
각 주소 공간에는 이러한 변환이 필요하기 때문에 일반적으로 시스템에는 프로세스마다 하나의 페이지 테이블이 있다.
페이지 테이블의 정확한 구조는 하드웨어(구형 시스템)에 의해 결정되거나 OS(최신 시스템)에 의해 보다 유연하게 관리된다.

Text Only

movl <virtual address>, %eax

가상 주소를 eax 레지스터에 저장하여 변환한다.

Address Translation 과정
1. CPU에서 프로세스가 요청한 가상주소를 확인
2. OS는 VPN을 사용해 해당 가상 주소의 페이지 번호를 찾음
3. page table에서 해당 페이지 번호에 대한 물리적인 page frame 주소를 찾음
4. VPN과 Offset을 결합해 물리적인 주소를 생성
5. 물리적인 주소를 사용해 메모리 접근

이 그림에서 Va5는 가상 주소의 최상위 비트이고, Va0는 최하위 비트이다.

프로세스가 가상 주소를 생성하는 경우 OS와 하드웨어를 결합하여 의미 있는 물리적 주소로 변환해야 한다.

예시) 작은 주소 공간(64바이트)을 가진 프로세스가 가상 주소 21번 (010101)의 메모리 액세스를 실행하고 있다고 가정해보자.

C

movl 21, %eax

프로세스가 생성한 이 가상 주소를 가상 페이지 번호(VPN)와 페이지 내 오프셋의 두 가지 구성 요소로 분할

프로세스의 가상 주소 공간의 크기: 64바이트로 가정하면
가상 주소: (\(2^6\) = 64)에 총 6비트 → 상위 2비트: VPN (가상 페이지 번호) + 나머지 4비트: offset
페이지 크기: 16바이트
따라서 가상 주소 21은 가상 페이지 '01'(또는 '1')의 5번째 (0101번째) 바이트에 있다.

가상 페이지 번호를 사용하여 페이지 테이블을 인덱싱하고 가상 페이지 1이 어떤 물리적 프레임에 있는지 찾을 수 있다.

운영체제와 하드웨어가 의미 있는 물리 주소로 변환한다.
1. 가상 주소를 바탕으로 이진 주소로 변환한다.
2. 가상 주소가 유효한지 검사한다.
3. 가상 페이지 번호와 오프셋으로 나눈다.
4. 가상 페이지 번호를 바탕으로 어느 물리 프레임에 저장되어 있는지 찾는다.
  물리 프레임 번호(Physical Frame Number, PFN) 혹은 물리 페이지 번호(Physical Page Number, PPN)
찾은 물리 프레임 번호와 기존 제공된 오프셋으로 물리 메모리에 탑재 명령어를 실행한다.

위의 페이지 테이블에서 물리적 프레임 번호(PFN)(물리적 페이지 번호 또는 PPN이라고도 함)는 7(바이너리 111)이다.
VPN을 PFN으로 대체하여 이 가상 주소를 변환하여 물리적 메모리에 로드한다.

오프셋은 페이지의 어떤 바이트가 필요한지 알려줄 뿐이므로 오프셋은 변환되지 않는다.
우리의 최종 물리적 주소는 0111 0101 (10진수로는 117)이며, 정확히 필요한 데이터를 로드하고 가져온다.

알아야 할 것

페이지 테이블 저장 장소
페이지 테이블의 일반적인 내용과 크기
페이징으로 인한 시스템 속도 차이

Page Table Entry (PTE, 페이지 테이블에서 각 페이지의 정보)¶

Page Table in Kernel Physical Memory

페이지 테이블은 단순히 32비트 페이지 지정자의 배열임
페이지 테이블은 그 자체로 하나의 페이지이므로 4KB의 메모리 또는 최대 1K의 32비트 항목을 포함한다.

메모리 페이지를 주소 지정하는 데는 두 가지 수준의 테이블이 사용된다.

상위 수준에는 페이지 디렉터리가 있다.
페이지 디렉터리는 두 번째 레벨의 페이지 테이블을 최대 1K까지 주소 지정한다.

두 번째 수준의 페이지 테이블은 최대 1K 페이지까지 주소 지정한다.
따라서 하나의 페이지 디렉터리에서 주소 지정하는 모든 테이블은 1M 페이지(\(2^{20}\))를 주소 지정할 수 있다.
각 페이지에는 4K 바이트 \(2^{12}\) 바이트가 포함되므로 한 페이지 디렉터리의 테이블은 80386의 전체 물리적 주소 공간에 걸쳐 있을 수 있다. (\(2^{20} \times 2^{12} = 2^{32}\)).

x86 기준 현재 페이지 디렉터리의 물리적 주소는 페이지 디렉터리 기본 레지스터(PDBR)라고도 하는 CPU 레지스터 CR3에 저장된다.

메모리 관리 소프트웨어에는 모든 작업에 하나의 페이지 디렉터리를 사용하거나 각 작업에 하나의 페이지 디렉터리를 사용하거나 이 두 가지를 조합하여 사용할 수 있는 옵션이 있다.

각 프로그램 인스턴스를 실행하기 전에 올바른 페이지 테이블에 대한 포인터와 함께 이 레지스터를 로드하는 것이 운영 체제의 작업이다.

각 메모리 액세스 시 CPU는 레지스터에서 테이블 포인터를 읽고 테이블에서 액세스한 페이지에 대한 매핑된 프레임을 찾는다.
이 작업은 전적으로 하드웨어에서 이루어지며 실행 중인 프로그램에는 전혀 보이지 않습니다.

또한 번역 프로세스의 속도를 높이기 위해 많은 CPU 아키텍처에는 마지막 변환 결과를 기억하는 특수 캐시가 있다.

Common Flags of Page Table Entry¶

VPN으로 해당 프로세스의 page table 배열을 인덱싱하고 변환을 위해 해당 인덱스의 page table entry(PTE)를 조회한다.
여기서 PTE는 page table에서 각 page의 정보라고 생각하면 된다.

Example: X86 Page Table Entry

페이지 프레임 번호(PFN) 외 비트 정보

Present(P) 비트

해당 페이지가 물리 메모리에 존재하는지 여부를 나타냄
0일 경우, 해당 페이지는 물리 메모리에 없으며 디스크에 swap out된 것임. 이 경우, 해당 페이지에 대한 메모리 접근 시, swap in이 필요함
Read/Write 비트(R/W): 이 페이지의 쓰기 허용 여부를 결정
User/Supervisor 비트(U/S): User mode 프로세스가 페이지에 접근할 수 있는지에 대한 비트
PWT, PCD, PAT, G 비트: 이 페이지의 하드웨어 캐싱이 어떻게 작동하는지 결정
Accessed 비트(A, Reference Bit): 최근 참조된 적이 있는지에 대한 정보 (페이지 교체 정책에서 사용됨)

페이지가 액세스되었는지 여부를 추적하는 데 사용된다.
어떤 페이지가 자주 액세스되고 필요하며 메모리에 보관해야 하는지를 결정하는 데 유용하다.
최적화 기능에서 사용됨. 가장 오랫동안 접근되지 않은 페이지는 스왑아웃의 대상이 될 수 있음.
Dirty 비트

해당 페이지가 메모리에 적재된 후 변경되었는지 여부를 나타내는 비트
1일 경우, 해당 페이지는 메모리에서 디스크로 swap out될 때, 변경된 내용을 디스크에 기록해야 함
Valid 비트

해당 페이지가 읽기, 쓰기, 실행 등의 접근 권한을 갖고 있는지 나타내는 비트. 보안 관련 기능에서 중요한 역할을 함.
예를 들어, 코드 세그먼트는 읽기와 실행만 가능하고 쓰기는 불가능해야 함
Protection 비트

페이지의 읽기, 쓰기, 실행이 가능한지 여부를 나타낸다.
이 비트에 의해 허용되지 않는 방식으로 페이지에 액세스하면 OS가 트랩을 생성한다.
추가 지식
x86_64 아키텍처는 4레벨 페이지 테이블과 4KB의 페이지 크기를 사용한다.
각 페이지 테이블은 레벨에 관계없이 512개 항목으로 고정된 크기를 갖는다.
각 항목의 크기는 8바이트이므로 각 테이블의 크기는 512 * 8B = 4KB이므로 한 페이지에 정확히 들어 맞음.

각 레벨의 페이지 테이블 인덱스는 가상 주소에서 직접 파생된다

각 테이블 인덱스는 9비트로 구성되어 있으며, 이는 각 테이블에 2^9 = 512개의 항목이 있음.
가장 낮은 12비트는 4KB 페이지의 오프셋입니다(2^12바이트 = 4KB).
48비트에서 64비트는 버려지므로 x86_64는 48비트 주소만 지원하므로 실제 64비트가 아니다.

48~64비트는 버려지지만 임의의 값으로 설정할 수는 없습니다.
대신 이 범위의 모든 비트는 주소를 고유하게 유지하고 5단계 페이지 테이블과 같은 향후 확장을 허용하기 위해 비트 47의 복사본이어야 한다.
이를 부호 확장이라고 부르는데, 이는 2의 보수에서 부호 확장과 매우 유사하기 때문입니다. 주소가 올바르게 부호 확장되지 않으면 CPU는 예외를 던진다.

더 자세히는 Intel® 64 and IA-32 Architectures Developer’s Manual: Vol. 1

Problems¶

Problem 1: 페이징 테이블 저장 문제¶

페이지 테이블 관리의 가장 큰 문제는 페이지 테이블의 크기가 작지 않다는 것이다.

예를 들어, 일반적인 32비트 주소 공간에서 4KB의 페이지가 있다고 가정해보자.
이 시스템이 가질 수 있는 물리 메모리의 최대 크기는 4GB 이다.

이 가상 주소는 20비트 VPN과 12비트 오프셋으로 분할된다
(1KB의 페이지 크기 당 10비트가 필요, 4KB는 12비트)

20비트 VPN은 각 프로세스에서 OS가 관리해야 하는 \(2^{20}\)개 (대략 100만개)의 변환이 있음을 나타낸다.
실제 변환에 더해 페이지 테이블 항목(PTE) 당 4바이트가 필요하다면 각 페이지 테이블에 필요한 메모리는 4MB가 된다.

100개의 프로세스가 실행되고 있다고 가정한다면, 주소 변환에만 400MB의 메모리가 필요하다.

MMU (CPU 레지스터) 내에 저장 (X) — 크기가 너무 커서 부적절
OS 메모리에 저장 (O)
- 물리 메모리 뿐만 아니라 가상 메모리, 디스크 등에도 저장할 수 있다.
- OS의 메모리 자체를 가상화할 수 있기 때문에 페이지 테이블을 OS의 가상 메모리에 저장할 수 있다. (디스크에 스왑할 수도 있다).

Problem 2: 페이징은 너무 느리다.¶

원하는 PTE(Page Table Entry)의 위치를 찾으려면 page table의 시작 위치가 필요함
1. 만약 큰 메모리 공간에서 작은 페이지를 사용하면(page size가 작으면), page table 크기가 매우 커질 수 있음. 이 경우 원하는 PTE 위치 찾는데 시간이 길어질 수 있다.
2. 메모리 참조 시에 항상 페이지 테이블에서 변환 정보를 반입해야 하므로 2배 이상 느려진다.
모든 메모리 참조에 관계없이 페이징은 OS에서 하나의 추가 메모리 참조를 수행해야 함
1. 페이징에 대한 오버헤드가 증가할 수 있음. 작은 페이지 크기를 사용할 경우 이런 추가 비용이 더 발생함
2. 추가 메모리 참조는 비용이 들며, 이 경우 프로세스가 두 배 이상 느려질 수 있다
3. 페이지 테이블의 구조 때문에 메모리를 많이 사용한다.

코드 예시
C
```
movl 21, %eax  
```

이 예제에서는 하드웨어가 변환을 수행한다고 가정한다.

가상 주소를 물리적 주소로 변환
필요한 데이터를 가져 오기 위해 시스템은 먼저 가상 주소(21)를 올바른 물리적 주소(117)로 변환해야 한다.

따라서 주소 117에서 데이터를 가져 오기 전에 시스템은 먼저 프로세스의 페이지 테이블에서 적절한 페이지 테이블 항목을 가져와 변환을 수행한 다음 물리적 메모리에서 데이터를 로드해야 한다.

이를 위해 하드웨어는 현재 실행 중인 프로세스에서 페이지 테이블이 어디에 있는지 알아야 한다.
여기서는 단일 페이지 테이블 베이스 레지스터에 페이지 테이블의 시작 위치의 물리적 주소가 포함되어 있다고 가정한다.

가상 페이지 생성

원하는 페이지 테이블 항목(PTE)의 위치를 찾기 위해 하드웨어는 다음과 같은 기능을 수행한다.
이 예에서 VPN Mask는 0x30(16진수 또는 110000)으로 설정되어 전체 가상 주소에서 VPN 비트를 선택하고, SHIFT는 4(오프셋의 비트 수)로 설정되어 있으므로 VPN 비트를 아래로 이동하여 올바른 정수형 가상 페이지 번호를 형성한다.

예를 들어, 가상 주소 21(010101)에서 마스크하면 이 값은 010000이 된다. 이를 이동시키면 01이 된다. 이것이 가상 페이지 1이 된다.

그런 다음 이 값을 페이지 테이블 베이스 레지스터가 가리키는 PTE의 배열에 대한 인덱스로 사용한다.

물리적 주소 생성
이 물리적 주소를 알면 하드웨어는 메모리에서 PTE를 꺼내어 PFN을 추출하고 가상 주소의 오프셋과 연결하여 필요한 물리적 주소를 형성할 수 있다.

구체적으로는 SHIFT에 의해 왼쪽으로 이동된 PFN을 생각할 수 있다.

그런 다음 오프셋과 OR을 통해 최종 주소를 다음과 같이 구한다.

Accessing Memory With Paging

C

 // 가상 주소에서 VPN 만 추출한다. (VPN_MASK, SHIFT 값 이용)  
 VPN = (VirtualAddress & VPN_MASK) >> SHIFT  

 // 페이지 테이블 엔트리(PTE)의 주소를 계산한다.  
 // PTBR(Page Table Base Register) 값과 VPN 이용  
 // Page Table 주소에 vpn 값으로 현재 접근하는 프로세스의 PTE 값을 찾는다.  
 PTEAddr = PTBR + (VPN * sizeof(PTE))  

 // 계산된 PTE 주소로부터 PTE(Page Table Entry)값 읽어옴  
 PTE = AccessMemory(PTEAddr)  

 // 프로세스가 페이지에 접근할 수 있는지 확인  
 // PTE의 Valid bit 값을 확인해 유효한지 검사하고 유효하지 않으면 예외 발생  
 if (PTE.Valid == False) RaiseException(SEGMENTATION_FAULT)  
    // PTE의 Pretection bit 값을 확인해 페이지에 접근할 수 있는지 확인하고   
    // 접근 권한이 없으면 PROTECTION_FAULT 예외 발생  
 else if (CanAccess(PTE.ProtectBits) == False) RaiseException(PROTECTION_FAULT)  
 else  
     // Access is OK (페이지에 접근할 수 있으면): 물리적 메모리 주소 계산하고 가져온다.  
     offset = VirtualAddress & OFFSET_MASK  
     // 이 때, PFN(Page Frame Number) 값과 offset 값 사용  
     PhysAddr = (PTE.PFN << PFN_SHIFT) | offset  
     // 계산된 물리적 메모리 주소로부터 데이터를 읽어와 레지스터에 저장함  
     Register = AccessMemory(PhysAddr)

A Memory Trace¶

간단한 메모리 액세스의 예를 추적하여 페이징을 사용할 때 발생하는 메모리 액세스

C

// 크기가 100인 배열 원소 0으로 초기화  
int array[1000];  
...  
for (i = 0; i < 1000; i++)  
    array[i] = 0;  

prompt> gcc -o array array.c - Wall -o  
prompt> ./array  

// 걍 위 코드의 어셈블리어로 작성된 코드  
// movl, incl, cmpl, jne 모두 어셈블리 명령어  
0x1024 movl $0x0,(%edi,%eax,4) //[edi+eax*4]= 0  
// edi, eax는 각각 인덱스 변수 i와 배열 변수 array의 주소를 저장  
// ,4는 배열 원소의 크기가 4바이트이기 때문에 인덱스에 4를 곱해야 함을 나타냄  
// $0x0은 0을 의미  
// 위 코드는 array[i] = 0과 같은 의미  

0x1028 incl %eax   
// eax 값을 1 증가시킴. 즉, 다음 배열 원소를 가리키게 된다.  

0x102c cmpl $0x03e8,%eax //0000 0011 1110 10002 = 100010  
// %eax가 0x03e8(즉, 1000)와 같은지 비교함  

0x1030 jne 0x1024  
// %eax가 0x03e8과 다르다면 (즉, 배열의 끝까지 도달하지 않았다면) 루프를 계속 반복  
// %eax가 0x03e8과 같다면 (즉, 배열의 끝까지 도달했다면) 루프를 종료

요약¶

우리는 메모리 가상화 문제에 대한 해결책으로 페이징이라는 개념을 도입했다.
페이징은 이전 접근 방식(세그멘테이션 등)에 비해 많은 장점이 있다 .

페이징(설계에 따라)은 메모리를 고정된 크기의 단위로 분할하기 때문에 외부의 파편화로 이어지지 않는다.
가상 주소 공간의 미사용 부분을 사용할 수도 있고 사용하지 않을 수도 있는 매우 유연한 방식이다.

해결해야 할 두 가지 문제

페이지 테이블은 시스템 속도를 너무 느리게 만든다.
너무 많은 메모리를 차지한다.

다음 두 장에서는 머신을 더 빠르게 만드는 방법, 메모리 낭비를 없애는 방법에 대해서 배울 것이다.

참고 자료¶

80386 Programmer’s Reference Manual – Section 5.2

마지막 업데이트 : 2025년 4월 23일
작성일 : 2023년 4월 2일