개발 공부
[운영체제][OSTEP] 페이징
페이지를 사용하여 메모리를 가상화하는 방법에 대해 공부해봅니다.
![[운영체제][OSTEP] 페이징](https://www.datocms-assets.com/66479/1686988115-ostep.jpg?auto=format&w=860)
🚪 들어가며
운영체제는 거의 모든 공간 관리 문제를 해결할 때 두 가지 중 하나를 사용
[1] 가변 크기의 조각들로 분할 ➡️ 단편화(fragmented) 문제
[2] 공간을 동일 크기의 조각으로 분할 ➡️ 페이징(paging)
페이지(page): 프로세스의 주소 공간을 몇 개의 가변 크기의 논리 세그멘트(코드, 힙, 스택 등)로 나누는 것이 아닌, 고정 크기의 단위로 나눌 때의 단위
이에 상응하여 물리 메모리도 페이지 프레임(page frame)이라고 불리는 고정 크기의 슬롯의 배열이라고 생각 ➡️ 이 프레임 각각은 하나의 가상 메모리 페이지를 저장
1️⃣ 간단한 예제 및 개요
다음의 간단한 예시와 함께 페이징 방식을 살펴보자.
총 크기가 64바이트이면서 4개의 16바이트 페이지로 구성된(가상 페이지 0, 1, 2, 3) 작은 주소 공간을 가정하자.
0 ┌────────────────┐
│ │ (page 0 of the address space)
16 ├────────────────┤
│ │ (page 1)
32 ├────────────────┤
│ │ (page 2)
48 ├────────────────┤
│ │ (page 3)
64 └────────────────┘물리 메모리는 아래와 같이 고정 크기의 슬롯들로 구성된다.
0 ┌─────────────────┐
│ reserved for OS │ page frame 0 of physical memory
16 ├─────────────────┤
│ (unused) │ page frame 1
32 ├─────────────────┤
│ page 3 of AS │ page frame 2
48 ├─────────────────┤
│ page 0 of AS │ page frame 3
64 ├─────────────────┤
│ (unused) │ page frame 4
80 ├─────────────────┤
│ page 2 of AS │ page frame 5
96 ├─────────────────┤
│ (unused) │ page frame 6
112 ├─────────────────┤
│ page 1 of AS │ page frame 7
128 └─────────────────┘위에서 확인할 수 있듯이, 가상 주소 공간의 페이지들은 물리 메모리 전체에 분산 배치되어 있다.
또한 운영체제가 자기자신을 위해 물리 메모리의 일부를 사용하는 것도 확인할 수 있다.
✅ 페이징 사용의 장점1
➡️ 유연성: 효율적으로 주소 공간 개념을 지원할 수 있음.(힙과 스택이 어느 방향으로 커지는지 등에 대해 가정할 필요X)
✅ 페이징 사용의 장점2
➡️ 빈 공간 관리의 단순함: 운영체제는 필요한 만큼 비어 있는 페이지를 찾으면 됨.
주소 공간의 각 가상 페이지에 대한 물리 메모리 위치 기록을 위하여 운영체제는 프로세스마다 페이지 테이블(page table)이라는 자료 구조를 유지한다.
➡️ 주소 공간의 가상 페이지 주소 변환(address translation) 정보를 저장
위의 예시의 경우 페이지 테이블은 다음과 같은 4개의 항목을 가지게 될 것이다.
가상 페이지(VP) 0 ➡️ 물리 프레임(PF) 3
VP 1 ➡️ PF 7
VP 2 ➡️ PF 5
VP 3 ➡️ PF 2
⭐ 페이지 테이블은 프로세스마다 존재한다는 사실을 기억하자!
➡️ ⚠️ 역 페이지 테이블(inverted page table)이라는 예외적인 기법도 존재
다른 프로세스를 실행해야한다면 운영체제는 해당 프로세스를 위한 다른 페이지 테이블이 필요하다. 공유 중인 페이지가 없다면 새 프로세스의 가상 페이지는 다른 물리 페이지에 존재하기 때문이다.
위의 예시에 이어 <virtual address>의 데이터를 eax 레지스터에 탑재한다고 해보자.
movl <virtual address>, %eax프로세스가 생성한 가상 주소의 변환을 위해 먼저 가상 주소를 가상 페이지 번호(virtual page number, VPN)와 페이지 내의 오프셋 2개의 구성 요소로 분할한다.
이 예시에서 가상 주소 공간의 크기가 64바이트이므로 가상 주소는 6비트가 필요하다.(2^6 = 64)
우리는 페이지 크기(16바이트)를 알고 있으므로 아래와 같이 Va5를 최상위 비트, Va0를 최하위 비트로 하여 가상 주소를 나눌 수 있다.
VPN offset
┌───────────┬───────────────────────┐
┌─────┬─────┬─────┬─────┬─────┬─────┐
│ Va5 │ Va4 │ Va3 │ Va2 │ Va1 │ Va0 │
└─────┴─────┴─────┴─────┴─────┴─────┘가상 주소의 구성 요소를 살펴보면 다음과 같다.
VPN: 최상위 2비트 = 4페이지 표현(64바이트의 주소 공간 중 각 16바이트)
offset: 페이지 내에서 우리가 원하는 바이트의 위치를 나타냄.
프로세스가 가상 주소 생성 ➡️ 운영체제와 하드웨어가 의미있는 물리 주소로 변환
예를 들어, 위 탑재 명령어의 가상 주소가 21인 경우
movl 21, %eax여기서 21은 이진 형식으로 010101이므로 이 가상 주소를 해석해보자.
VPN offset
┌───────────┬───────────────────────┐
┌─────┬─────┬─────┬─────┬─────┬─────┐
│ 0 │ 1 │ 0 │ 1 │ 0 │ 1 │
└─────┴─────┴─────┴─────┴─────┴─────┘즉, 가상 페이지 1(01)의 5(0101)번째 바이트를 의미한다.
이때, 위의 페이지 테이블 예시에서 가상 페이지 1에 대응하는 물리 프레임 번호(physical frame number, PFN) 혹은 물리 페이지 번호(physical page number, PPN)는 7(111)이므로 VPN을 PFN으로 교체하여 가상 주소를 변환할 수 있다.
VPN offset
┌───────────┬───────────────────────┐
┌─────┬─────┬─────┬─────┬─────┬─────┐
Virtual │ 0 │ 1 │ 0 │ 1 │ 0 │ 1 │
Address └─────┴─────┴─────┴─────┴─────┴─────┘
↓ ↓ │ │ │ │
┌─────────────────┐ │ │ │ │
│ Address │ │ │ │ │
│ Translation │ │ │ │ │
└─────────────────┘ │ │ │ │
↓ ↓ ↓ ↓ ↓ ↓ ↓
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
Physical │ 1 │ 1 │ 1 │ 0 │ 1 │ 0 │ 1 │
Address └─────┴─────┴─────┴─────┴─────┴─────┴─────┘
└─────────────────┴───────────────────────┘
PFN offset⚠️ 위에 나타난 것처럼 오프셋은 변환 후에도 동일함을 알 수 있다.
최종적으로 계산된 1110101(십진수 117)이 탑재할 데이터가 저장된 정확한 위치이다.
2️⃣ 페이지 테이블은 어디에 저장되는가
페이지 테이블은 이전의 작은 세그멘트 테이블 혹은 베이스-바운드 쌍에 비해 매우 커질 수 있다.
예를 들어, 4KB 크기의 페이지를 갖는 전형적인 32비트 주소 공간의 경우
➡️ 20비트 VPN과 12비트 오프셋으로 가상 주소가 구성된다.
20비트 VPN은 운영체제가 각 프로세스를 위해 관리해야 하는 변환의 개수가 2^20(약 백만)이라는 것을 의미
물리 주소로의 변환 정보와 다른 필요한 정보를 저장하기 위하여 페이지 테이블 항목(page table entry, PTE)마다 4바이트가 필요하다고 가정
➡️ 각 페이지 테이블을 저장하기 위하여 4MB의 메모리가 필요
➡️ 프로세스가 100개 실행 중이면, 주소 변환을 위해 운영체제가 400MB의 메모리를 필요로 함.
페이지 테이블이 매우 큼. ➡️ 현재 실행 중인 프로세스의 페이지 테이블을 저장할 수 있는 회로를 MMU 안에 유지X
현재는 각 프로세스의 페이지 테이블이 운영체제가 관리하는 물리 메모리에 상주한다고 가정
➡️ 페이지 테이블은 운영체제 가상 메모리에 저장할 수 있고, 디스크에 스왑될 수도 있음.
운영체제 메모리 영역(PFN 0)에 페이지 테이블이 존재하는 경우 다음과 같이 표현할 수 있음.
0 ┌─────────────────┐
│ page table: │ page frame 0 of physical memory
│ 3 7 5 2 │
16 ├─────────────────┤
│ (unused) │ page frame 1
32 ├─────────────────┤
│ page 3 of AS │ page frame 2
48 ├─────────────────┤
│ page 0 of AS │ page frame 3
64 ├─────────────────┤
│ (unused) │ page frame 4
80 ├─────────────────┤
│ page 2 of AS │ page frame 5
96 ├─────────────────┤
│ (unused) │ page frame 6
112 ├─────────────────┤
│ page 1 of AS │ page frame 7
128 └─────────────────┘3️⃣ 페이지 테이블에는 실제 무엇이 있는가
페이지 테이블: 가상 주소(가상 페이지 번호)를 물리 주소(물리 프레임 번호)로 매핑(mapping)하는 데 사용되는 자료 구조
가장 간단한 형태는 선형 페이지 테이블(linear page table)
위 구조 사용 시 운영체제는 원하는 물리 프레임 번호(PFN)를 찾기 위하여 다음과 같은 순서를 거친다.
가상 페이지 번호(VPN)으로 배열의 항목에 접근
그 항목의 페이지 테이블 항목(PTE)을 검색
각 PTE에는 심도있는 이해가 필요한 비트들이 존재하는데, 이를 하나씩 살펴보자.
Valid bit
특정 변환의 유효 여부를 나타내기 위하여 포함된다.
프로그램이 실행을 시작할 때, 코드와 힙이 주소 공간의 한쪽에 있고 반대쪽은 스택이 차지하고 있는 경우 그 사이의 모든 미사용 공간은 무효(invalid)로 표시됨.
➡️ 프로세스가 그런 메모리 접근 시 운영체제에 트랩을 발생
Valid bit는 할당되지 않은 주소 공간을 표현하기 위해 반드시 필요
주소 공간의 미사용 페이지를 모두 표시
➡️ 이러한 페이지들에게 물리 프레임을 할당할 필요를 없애 대량의 메모리를 절약
Protection bit
페이지가 읽을 수 있는지, 쓸 수 있는지, 또는 실행될 수 있는지를 표시한다.
Protection bit가 허용하지 않는 방식으로 페이지에 접근하려고 하면 운영체제에 트랩을 생성
Present bit
해당 페이지가 물리 메모리에 있는지 혹은 디스크에 있는지(스왑 아웃되었는지) 가리킨다.
Dirty bit
메모리에 반입된 후 페이지가 변경되었는지 여부를 나타낸다.
Reference bit 또는 Accessed bit
때때로 페이지가 접근되었는지를 추적하기 위해 사용된다.
어떤 페이지가 인기가 있는지 결정하여 메모리에 유지되어야 하는 페이지를 결정하는 데에도 유용
➡️ 페이지 교체에 매우 중요한 정보
아래는 x86 아키텍처의 페이지 테이블 항목을 보여준다.
31 ... 12 ... 9 8 7 6 5 4 3 2 1 0
┌───────────┬─────┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ │ │ │ P │ │ │ P │ P │ U │ R │ │
│ PFN │ │ G │ A │ D │ A │ C │ W │ / │ / │ P │
│ │ │ │ T │ │ │ D │ T │ S │ W │ │
└───────────┴─────┴───┴───┴───┴───┴───┴───┴───┴───┴───┘구성요소는 다음과 같다.
Present bit(P)
읽기/쓰기 비트(R/W): 이 페이지에 쓰기가 허용되는지 결정
사용자/슈퍼바이저 비트(U/S): 사용자 모드 프로세스의 페이지 엑세스 여부를 결정
PWT, PCD, PAT, G: 이 페이지에 대한 하드웨어 캐시의 동작을 결정
Reference bit(A)
Dirty bit(D)
페이지 프레임 번호(PFN)
4️⃣ 페이징: 너무 느림
페이지 테이블의 크기가 메모리 상에서 매우 크게 증가할 수 있다.
➡️ 페이지 테이블로 인해 처리 속도가 저하될 수 있다.
위에 있던 예시와 함께 이를 살펴보자.
movl 21, %eax이때, 하드웨어가 주소 변환을 담당한다고 가정한다.
원하는 데이터를 가져 오기 위해 다음과 같은 과정을 거친다.
시스템은 가상 주소(21)를 정확한 물리 주소(117)로 변환해야 한다.
주소 117에서 데이터를 반입하기 전 다음의 과정을 거친다.
시스템은 프로세스의 페이지 테이블에서 적절한 페이지 테이블 항목을 가져온다.
변환을 수행한다.
물리 메모리에서 데이터를 탑재한다.
이를 위해서 하드웨어는 현재 실행 중인 프로세스의 페이지 테이블의 위치를 알아야 한다.
당분간은 하나의 페이지 테이블 베이스 레지스터(page table base register)가 페이지 테이블의 시작 주소(물리 주소)를 저장한다고 가정한다.
하드웨어는 원하는 PTE의 위치를 찾기 위해 다음과 같은 연산을 수행한다.
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE))이 예시에서 위 코드의 값들은 다음과 같이 지정된다.
VPN_MASK: 0x30(이진수 110000) ➡️ 전체 가상 주소에서 VPN 비트만 골라냄.SHIFT: 4(오프셋 비트 수) ➡️ 올바른 정수 가상 페이지 번호 형성을 위해 쉬프트 수행
따라서 가상 주소 21(010101)은 다음과 같이 처리된다.
010101 ➡️ 마스킹 ➡️ 010000 ➡️ 쉬프트 ➡️ 01
이렇게 나온 01값을 페이지 테이블 베이스 레지스터가 가리키는 PTE 배열에 대한 인덱스로 사용한다.
이 물리 주소가 알려지면 하드웨어는 다음을 수행할 수 있다.
메모리에서 PTE를 반입
PFN을 추출
가상 주소의 오프셋과 연결하여 원하는 물리 주소 생성
PFN을 SHIFT 만큼 왼쪽으로 쉬프트
오프셋과 OR 연산
최종 주소 형성
위 과정의 3번을 코드로 나타내면 아래와 같다.
offset = VirtualAddress & OFFSET_MASK
PhysAddr = (PFN << SHIFT) | offset정리하며, 각 메모리 참조 시 일어나는 세부 동작을 살펴보자.
// 가상 주소에서 VPN 추출
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
// 페이지 테이블 항목(PTE)의 주소 형성
PTEAddr = PTBR + (VPN * sizeof(PTE))
// PTE 반입
PTE = AccessMemory(PTEAddr)
// 프로세스가 페이지를 접근할 수 있는지 확인
if (PTE.Valid == False)
RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
RaiseException(PROTECTION_FAULT)
else
// 접근 가능하면 물리 주소 만들고 값 가져오기
offset = VirtualAddress & OFFSET_MASK
PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
Register = AccessMemory(PhysAddr)명령어 반입, load 또는 store 명령어 실행을 비롯한 모든 메모리 참조에 대해 먼저 페이지 테이블에서 변환 정보를 반입해야 함.
➡️ 반드시 한 번의 추가적인 메모리 참조가 필요
따라서 메모리 참조는 큰 비용이 들고, 이 경우에 프로세스는 2배 이상 느려진다.
이를 해결하기 위해 이제 우리는 두 개의 문제를 알게 되었다.
하드웨어와 소프트웨어의 신중한 설계 없이는 페이지 테이블로 인해 시스템이 매우 느려질 수 있다.
또한 너무 많은 메모리를 차지한다.
5️⃣ 메모리 트레이스
다음의 예시를 통해 페이징을 사용했을 때 발생하는 모든 메모리 접근을 살펴보자.
다음과 같은 코드를 가정하자.
int array[1000];
...
for (i = 0; i < 1000; i++)
array[i] = 0;이제 위 코드를 컴파일하고 실행한다.
prompt> gcc −o array array.c −Wall −O
prompt> ./array루프 안에서 배열을 초기화하기 위해 어떤 어셈블리 명령어를 사용하는지 보기 위하여 결과 이진 파일을 디스어셈블(disassemble)한다.
0x1024 movl $0x0, (%edi,%eax,4)
0x1028 incl %eax
0x102c cmpl $0x03e8,%eax
0x1030 jne 0x1024위의 명령어의 의미를 하나씩 살펴보자.
첫 번째 명령어: 값 0(
$0x0)을 가상 메모리 주소로 옮긴다.0 값이 저장될 가상 메모리 주소 =
%edi+%eax* 4(int의 크기)%edi는 배열의 시작 주소를,%eax는 배열 인덱스(i)를 저장한다.
두 번째 명령어:
%eax에 저장된 배열 인덱스를 증가시킨다.세 번째 명령어:
%eax의 값과0x03e8(십진수 1000)을 비교한다.네 번째 명령어: 비교 결과 아직 두 값이 같지 않다면(
jne명령어가 검사), 루프의 상단으로 다시 분기한다.
이 예시에 다음과 같은 가정을 추가하자.
가상 주소 공간은 64KB이다.
페이지의 크기는 1KB이다.
선형(배열 기반) 페이지 테이블이고 물리 주소 1KB(1024)에 위치한다.
이 예시에서 신경 써야 할 몇 개의 페이지 테이블의 페이지는 다음과 같다.
코드가 상주하는 가상 페이지
페이지의 크기가 1KB이므로 가상 주소 1024는 가상 주소 공간의 두 번째 페이지(VPN=1)에 상주한다.
물리 프레임(4)에 매핑된다고 가정하자.(VPN 1 ➡️ PFN 4)
배열 자체
크기는 4000바이트(1000개의 정수)이고, 가상 주소 40000에서 44000까지 존재한다고 가정한다.
이 범위에 해당하는 가상 페이지는 VPN=39 ... VPN=42이다.
가상-대-물리 주소 매핑은 다음과 같다고 가정하자.
VPN 39 ➡️ PFN 7
VPN 40 ➡️ PFN 8
VPN 41 ➡️ PFN 9
VPN 42 ➡️ PFN 10
프로그램이 실행되면, 각 명령어의 반입 시에 메모리가 다음과 같이 두 번 참조된다.
명령어의 위치를 파악하기 위한 페이지 테이블 접근
명령어 자체에 접근
mov 명령어의 경우 추가적인 메모리 참조를 한다.
페이지 테이블 접근(배열의 가상 주소를 올바른 물리 메모리 주소로 변환하기 위해)
배열 자체에 접근
처음 네 번의 루프 반복에 대한 전체 과정을 아래에서 확인하자.
PageTable[39] ┌ 1224
* * * * ├ 1174 Page
├ 1124 Table
PageTable[1] ├ 1074 (PA)
*───*─*─*─*───*─*─*─*───*─*─*─*───*─*─*─┼ 1024
m
o
v
40012 ┐ * ┌ 7244
Array 40008 ┤ * ├ 7240 Array
(VA) 40004 ┤ * ├ 7236 (PA)
40000 ┼──*────────────────────────────────────┼ 7232
m i c j
o n m n
v c p e
1036 ┐ * * * *┌ 4108
Code 1032 ┤ * * * * ├ 4104 Code
(VA) 1028 ┤ * * * * ├ 4100 (PA)
1024 ┼*────────┬*────────┬*────────┬*────────┼ 4096
0 10 20 30 40
Memory Access가장 아래쪽이 명령어 메모리 참조, 중앙이 배열에 대한 접근, 맨 위가 페이지 테이블 메모리 접근에 대한 그래프이다.
왼편은 가상 주소, 오른편은 물리 주소를 나타내는데, 맨 위(페이지 테이블 메모리 접근) 그래프의 경우 예시에서 페이지 테이블은 물리 메모리만 존재하므로 왼편의 값은 없다.
루프당 10번의 메모리 접근이 존재하는 것을 알 수 있다.
➡️ 명령어 반입 4번 + 메모리 갱신 1번 + 페이지 테이블 접근 5번
➡️ 페이지 테이블 접근 5번 = 반입 4번을 위해 + 명시적 갱신을 위한 주소 변환 1번을 위해
📚 참고 문헌
Operating Systems: Three Easy Pieces ― 18: Paging: Introduction
![[운영체제][OSTEP] 빈 공간 관리](https://www.datocms-assets.com/66479/1686988115-ostep.jpg?ar=1&auto=format&crop=focalpoint&dpr=0.47&fit=crop&fp-x=0.5&fp-y=0.5&w=430)