[ OS ] 8.paging • 욕망이 가득한 블로그

들어가며

운영체제는 거의 모든 공간 관리 문제를 해결할 때 두 가지 중 하나를 사용한다. 첫번째 방법은 전에 보았던 세그멘테이션이다. 세그멘테이션은 가변 크기의 조각들로 분할하게 되는데, 이 해결책은 태생적인 문제가 있다. 공간을 다양한 크기의 청크로 분할할 때 공간 자체가 단편화(fragmented)될 수 있고, 할당이 점점 어려워진다. 이 문제를 해결하기 위해 페이징이라는 기법을 사용한다.

Paging

페이징은 프로세스의 주소공간을 몇개의 가변 크기의 논리 세그멘트로 나누는 것이 아니라 고정 크기의 단위로 나눈다. 이 각각의 고정 크기 단위를 페이지(page)라 부른다. 여기서 물리 메모리는 페이지 프레임(page frame)이라고 부른다.

페이징 예시

페이지 테이블(page table)

물리 메모리는 위 그림처럼, 고정 크기의 슬롯들로 구성된다. 그림에서 볼 수 있듯이, 가상 주소 공간의 페이지들은 물리 메모리 전체에 분산 배치되어 있다. 그리고 또한, 운영체제가 자기 자신을 위해서 물리 메모리의 일부를 사용하는 것도 보여준다.

페이징은 이전 방식에 비해 많은 장점을 가지고 있다. 가장 중요한 개선은 유연성일 것이다. 페이징을 사용하면 프로세스의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념을 지원할 수 있다. 예를 들어, 힙과 스택이 어느 방향으로 커지는가, 어떻게 사용되는가에 대한 가정을 하지 않아도 된다.

또 다른 장점은 페이징이 제공하는 빈 공간 관리의 단순함이다. 만약 64바이트 주소 공간을 8페이지 물리 메모리에 배치하기를 원한다고 할 때, 운영체제는 비어 있는 네 개의 페이지만 찾으면 된다.

위 그림의 예시로는

VP 0 -> PF 3
VP 1 -> PF 7
VP 2 -> PF 5
VP 3 -> PF 2

주소 공간의 각 가상 페이지에 대한 물리 메모리 위치 기록을 위하여 운영체제는 프로세스마다 페이지 테이블(page table)이라는 자료구조를 유지한다. 페이지 테이블의 주요 역할은 주소 공간의 가상 페이지 주소 변환(address translation) 정보를 저장하는 것이다. 각 페이지가 저장된 물리 메모리의 위치가 어디인지 알려준다.

가상 주소(virtual address)

가상 주소 구조

프로세스가 생성한 가상 주소의 변환을 위해 먼저 가상 주소를 가상 페이지 번호(virtual page number, VPN)와 페이지 내의 오프셋 2개의 구성 요소로 분할한다. 위 그림에서 Va5는 가상 주소의 최상위 비트이며, Va0는 최하위 비트를 나타낸다. 우리는 페이지 크기(16바이트)를 알고 있기 때문에, 다름과 같이 가상 주소를 나눌 수 있다.

가상 주소 분할

페이지 크기는 64바이트의 주소공간에서 16바이트이다. 따라서 4페이지를 선택할 수 있어야 하고 따라서 주소의 최상위 2비트가 그 역할을 한다. 우리는 2비트 가상 페이지 번호(VPN)를 가지게 된다. 나머지 비트는 페이지 내에서 우리가 원하는 바이트의 위치를 나타낸다. 이것을 오프셋이라고 부른다.

예를 들어, 위 탑재 명령어의 가상 주소가 21이라고 하자.

movl 21, %eax

“21”을 이진 형식으로 변환하면 “010101”을 얻고, 이 가상 주소를 검사하고 가상 페이지 번호와 오프셋으로 나눈다.

가상 주소 변환

위 그림처럼 VPN을 PFN으로 교체하여 가상 주소를 변환할 수 있다. 그런 후에 물리메모리에 탑재 명령어를 실행한다. 오프셋은 동일하다. 오프셋은 페이지 내에서의 우리가 원하는 위치를 알려 주기 때문이다. 최종적으로 계산된 물리 주소는 1110101(십진수 117)이며, 이곳이 탑재할 데이터가 저장된 정확한 위치이다. 오프셋같은 경우에는, 결국 기준점에서 어떤 순서에 있냐이기 때문에 가상주소에서 물리 주소로 바뀔 때 변환이 일어나지 않는다.

페이지 테이블은 어디에 저장되나

페이지 테이블은 매우 커질 수 있다. 만약 32-bit 주소공간에 4KB 페이지들이 있다고 하자. 이 경우, 가상주소는 20-bit VPN, 12-bit offset 으로 구성된다.(총 32bit, 32비트 운영체제는 32비트 길이의 메모리 주소를 사용) 20비트 VPN은 운영체제가 각 프로세스를 위해 관리해야 하는 변환의 개수가 2^20 이라는 것을 의미한다.(약 백만) 물리 주소로의 변환 정보와 다른 필요한 정보를 저장하기 위해 PTE마다 4바이트가 필요하다고 가정하면, 각 페이지 테이블을 저장하기 위하여 4MB의 메모리가 필요하게 된다. 만약 프로세스가 100개 실행중이라면, 주소 변환을 위해 운영체제가 400MB의 메모리가 필요하게 된다. 컴퓨터가 GB 단위의 메모리를 가지고 있는 요즘도 변환만을 위해 이정도를 할당한 다는것은 매우 비정상적이다.

이렇게 페이지 테이블이 매우 크기 때문에 현재 실행중인 프로세스의 페이지 테이블을 저장할 수 있는 회로를 MMU안에 유지하지 않는다. 대신 각 프로세스의 페이지 테이블을 메모리에 저장한다. 페이지 테이블은 운영체제 가상 메모리에 저장할 수 있고 심지어 디스크에 스왑될 수 있다.

페이지 테이블

페이지 테이블 구조

PFN(Page Frame Number): 실제 물리 메모리 프레임의 번호를 저장
PTE(Page Table Entry): PFN 외에 페이지에 대한 다른 정보(접근 권한 등)를 저장하는 영역

페이지 테이블에 실제로 있는 것

페이지 테이블은 가상주소(또는 실제로는 가상 페이지 번호)를 물리 주소(물리 프레임 번호)로 매핑하는데 사용되는 자료구조이다. 가장 간단한 형태는 선형 페이지 테이블이다. 단순한 배열이다. 운영체제는 원하는 물리 프레임 번호를 찾기 위해 가상 페이지 번호로 배열의 항목에 접근하고 그 항목의 페이지 테이블 항목을 검색한다. (지금은 간단한 선형 자료구조를 사용한다고 가정. 나중에 페이징과 관련된 문제를 해결하기 위해 고급 자료구조 사용 예정)

PTE(Page Table Entry)

x86-32 PTE

x86-32 PTE 구조

P: present bit
R/W: read/write bit
U/S: user/supervisor bit
A: accessed bit
D: dirty bit
PWT, PCD, PAT, G: hardware caching policy
PFN: page frame number

Valid bit

위 그림에서는 표현되지 않음. 굳이 있다면 present bit(P)가 어느정도의 역할을 수행
특정 주소 변환이 유효한지 여부를 나타냄
사용되지 않는 주소 공간은 모두 유효하지 않음(invalid)으로 표시
이를 통해 부족한 주소 공간을 효율적으로 지원할 수 있음

Protection bits

위 그림에서 U/S, R/W에 해당
해당 페이지에 대한 읽기, 쓰기, 실행 권한을 지정
메모리 보호를 위해 프로세스별로 페이지 접근 권한을 제어할 수 있음

Present bit

이 페이지가 실제 물리 메모리에 있는지, 디스크에 스왑아웃(swapped out) 되었는지를 나타냄

Dirty bit

페이지가 수정되었는지 여부를 표시함
스왑아웃 시 수정된 페이지만 디스크에 저장할 수 있음

Reference bit

페이지 교체 알고리즘(페이지 교체 정책)에서 참조 여부를 판단하는 데 사용됨

Address translation이 일어나는 과정

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
PTEAddr = PTBR + (VPN * sizeof(PTE))

a. 먼저, 가상 주소에서 페이지 번호(VPN: Virtual Page Number)를 추출합니다. 이는 VPN_MASK(가상 페이지 번호를 추출하기 위한 비트 마스크)를 사용하여 가상 주소에서 마스크를 씌워 추출한 후, SHIFT(시프트)를 통해 적절한 위치로 이동시킨다.

b. 다음으로, 페이지 테이블의 주소를 계산함. 페이지 테이블 기준 레지스터(PTBR: Page Table Base Register)에 가상 페이지 번호를 곱하고 페이지 테이블 엔트리의 크기를 곱한 값에 PTBR을 더하여 페이지 테이블 엔트리의 주소를 계산한다.

6- bit addressing(64-byte address space)

VPN_MASK: 0x30(110000)
SHIFT: 4

PTE = AccessMemory(PTEAddr)
if (PTE.Valid == False)
	RaiseExcrption(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
	RaiseException(PROTECTION_FAULT)
else
	offset = VirtualAddress & OFFSET_MASK
	PhysAddr = (PTE.PFN << SHIFT) | offset
	Register = AccessMemory(PhysAddr)

c. 페이지 테이블 엔트리를 읽어온다. 이 엔트리는 물리 페이지 번호(PFN: Page Frame Number)와 보호 비트(Protect Bits) 등의 정보를 포함한다.

d. 페이지 테이블 엔트리의 유효성을 확인한다. 엔트리가 유효하지 않으면(SEGMENTATION_FAULT) 예외를 발생시킨다.

e. 페이지에 접근 가능한지 확인한다. 만약 접근이 불가능하면(PROTECTION_FAULT) 예외를 발생시킨다.

f. 모든 검사를 통과하면, 물리 페이지 번호와 오프셋을 조합하여 물리 주소를 계산한다. 이것이 실제 메모리에서 데이터에 접근하기 위한 물리 주소이다.

g. 마지막으로, 계산된 물리 주소를 사용하여 메모리에 접근하여 데이터를 읽거나 쓰게 된다.