Paging

박정빈·2024년 3월 30일

목록 보기

13/25

운영체제는 공간 관리 문제를 해결할 때 두 가지 접근법 중 하나를 취한다.

첫 번째는 가변 크기의 세그먼트(코드,힙,스택)로 나누는 것이다. 앞 포스팅에서 살펴본 이 방법(가상 메모리의 세그멘테이션)은 공간이 단편화가 되어 할당이 어려워지는 단점이 있다. 이 문제는 메모리를 고정 크기로 나누면 생기지 않는다.

두 번째는 페이징(Paging)이라고 부르는, 고정 크기의 조각으로 나누는 방법이다. 프로세스를 고정크기의 단위로 나누어 이를 페이지(Page) 라고 부른다. 물리적 메모리를 페이지 프레임(Page Frames)이라고 부르는 슬롯 배열로 본다.

예제로 살펴보기

아래 그림처럼 고정 크기로 주소공간이 나뉘어져 있고, OS의 공간도 있다.
A 64-Byte Address Space In A 128-Byte Physical Memory
페이징 기법을 사용하면서 다음과 같은 장점을 얻는다.

유연성
힙과 스택이 커지는 방향 같은 것을 고려하지 않아도 되니 유연성이라는 장점을 얻었다.
단순함
또 다른 장점은 여유 공간(free space) 관리의 간단함이다. 프로세스가 필요한 크기만큼의 페이지를 할당하면 된다.

페이징 기법은 할당 정보(가상 주소 페이지가 몇 번 페이지 프레임에 있나?)를 기억하기 위해 페이지 테이블(page table)이라는 데이터 구조를 유지한다. 페이지 테이블의 역할은 가상 페이지에 대한 주소 변환을 저장하여 실제 물리 메모리의 어디에 위치하는지 알려주는 것이다. 페이지 테이블은 프로세스별 데이터 구조이다. 다른 프로세스가 실행된다면 다른 물리 페이지에 매핑되는 것이므로 OS는 그에 따른 페이지 테이블을 관리한다.

실제 주소 변환의 예시를 살펴보자
movl <가상 주소>, %eax
프로세스가 생성한 가상 주소를 번역하기 위해 가상 페이지 번호(VPN:virtual page number)과 offset으로 나눠 봐야한다. 가상 주소 공간이 64바이트라고 하면, 가상 주소에 총 6비트가 필요하다.(2의 6승 = 64)

가상 주소를 표현하는 여섯 비트를 위의 사진으로 표현하였다. 주소 공간이 64바이트이고, 페이지 크기가 16바이트 인 경우, 4개의 페이지를 선택해야하므로 주소의 상위 2비트로 페이지를 선택해야한다. 따라서 상위 두 비트는 페이지를 구별, 나머지 비트는 페이지의 어느 바이트인지 나타내는 offset을 표현한다.

가상 주소 21로 가정해보자 movl 21, %eax
21의 이진 형식은 010101 이고 VPN은 상위 두 비트인 01, offset은 나머지인 01010 이다. 따라서 가상주소 21은 1번째 가상페이지의 5번째 바이트에 있다.

페이지 테이블에서 1번째 가상페이지의 물리적 위치는 7(예시)이다. 이 정보를 활용하여 가상 주소를 물리 프레임 번호(PFN:physical frame number 또는 PPN:physical page number 라고 부름)로 변환하여 실제 물리적 메모리의 위치를 알 수 있다.
The Address Translation Process
offset은 페이지 내에서 어떤 바이트인지를 나타낸다. 페이지 프레임과 가상 주소 페이지의 크기가 같으니 offset은 변형이 필요 없이 그대로 유지된다.

페이지 테이블은 어디 있나요?

페이지 테이블은 굉장히 크다. 4KB 페이지를 가지는 32비트 주소 공간을 상상해보자.
이 가상 주소는 12비트의 (4KB = $4\times 2^{10}$ = $2^{12}$ ) offset과
20비트의 (32(비트)-12(offset 비트)=20) VPN으로 나뉜다.

20비트 VPN은 $2^{20}$ 개의 변환을 의미한다. 각 페이지 테이블 항목(PTE:page table entry)에는 페이지 당 4바이트가 필요하다고 가정하면, 각 페이지 테이블에는 4MB의 메모리가 필요하다. 만약 100개의 프로세스가 실행중이라면, 400MB가 필요하다는 것이다!

아래 사진은 페이지 프레임(물리 메모리) 중 하나인 OS Kernel에 페이지 테이블을 위치시킨 모습이다.
Page Table in Kernel Physical Memory

페이지 테이블 안에 뭐가 있을까?

페이지 테이블의 구성에 대하여 더 알아보자
페이지 테이블은 가상 주소를 물리 주소로 매핑하는 데이터 구조일 뿐이라 어떤 데이터 구조든지 사용할 수 있다. 가장 간단한 형태는 선형 페이지 테이블(linear page table)이다.
선형 테이블 페이지는 배열로 구성된다. 가상 테이블 번호(VPN)으로 페이지 테이블 항목(PTE)를 조회하여 물리 프레임 번호(PFN)을 찾는다.
페이지 테이블 항목(PTE)는 몇가지 비트로 이루어진다.

유효 비트 (valid bit)
변환이 유효한지를 나타낸다. 실제 사용되지 않는 (스택과 힙의 사이같은) 공간에 엑세스하려할때 OS에 트랩이 발생하여 프로세스가 종료될 것이다. 주소공간에서 미사용 페이지를 유효하지 않은 상태로 표시함으로써 프레임 할당을 하지 않고 메모리를 절약할 수 있다.
보호 비트 (protection bit)
페이지에 대한 읽기,쓰기등 실행 여부를 나타내는 비트이다. 허용되지 않은 방식으로 페이지에 엑세스하면 OS에 트랩이 발생한다.
프레젠트 비트 (present bit)
페이지가 물리 메모리에 있는지, 디스크에 있는지를 나타낸다. 물리 메모리 보다 더 큰 주소공간을 지원하기 위한 swap 메커니즘을 나중에 알게될 것이다. 스왑은 OS가 물리 메모리를 해제하여 사용되지 않는 페이지를 디스크로 이동시킨다.
더티 비트 (dirty bit)
페이지가 메모리로 가져온 후에 수정되었는지를 나타낸다.
참조 비트 (reference bit)
페이지가 엑세스되었는지를 추적한다. 어떤 페이지가 인기있는지 결정하는데 사용된다. 페이지 교체에 대한 내용을 나중에 알게될 것이다.엑세스 되었는지 추적하는데 사용된다.

아래 사진은 PTE의 예시(intel)이다.
이 항목에는 '프레젠트'(P) 비트,
이 페이지에 대한 쓰기가 허용되는지를 결정하는 '읽기/쓰기'(R/W) 비트,
사용자 모드 프로세스가 페이지에 액세스할 수 있는지를 결정하는
'사용자/슈퍼바이저'(U/S) 비트,
이러한 페이지에 대한 하드웨어 캐싱 작동 방식을 결정하는
몇 가지 비트(PWT, PCD, PAT, G),
액세스된 비트(A) 및 더티 비트(D),
그리고 마지막으로 페이지 프레임 번호(PFN) 자체가 포함되어 있다.
PTE

Paging: Also Too Slow

메모리에 페이지 테이블이 있으면 그 크기가 너무 크다는 것을 앞서 기술했다. 그리고 이것은 작업을 느리게 만들수 있다. 예를 들어보겠다. movl 21, %eax
원하는 데이터를 가져오기 위해 가상 주소 21을 물리주소 117로 변환해야 한다. 데이터를 117에서 가져오기 전에 시스템은 프로세스의 페이지 테이블에서 적절한 테이블 항목을 가져와야 하고, 변환을 한 뒤 물리 메모리에서 데이터를 로드해야 한다.

이를 위해 하드웨어는 프로세스의 페이지 테이블의 위치를 알아야한다. 페이지 테이블 시작위치의 물리적 주소가 담긴 단일 페이지 테이블 베이스 레지스터(page-table base register)가 있다고 가정해보자 원하는 PTE의 위치를 찾기 위해 하드웨어는 다음 함수를 수행할 것이다.

//가상 주소에서 VPN 알아내기
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
//VPN 값으로 PTE 찾기
PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE))
//가상 주소에서 offset 알아내기
offset = VirtualAddress & OFFSET_MASK
//offset과 PFN으로 실제 메모리 주소 찾기
PhysAddr = (PFN << SHIFT) | offset

페이징은 명령어 fetch나 load, store이 진행될 때마다 메모리 참조를 수행해야한다. 메모리 참조는 비용이 많이 들며 프로세스 속도를 느리게 만든다.

// 가상 주소에서 VPN 알아내기
VPN = (VirtualAddress & VPN_MASK) >> SHIFT
// VPN 값으로 PTE 찾기
PTEAddr = PTBR + (VPN * sizeof(PTE))
// Fetch the PTE
PTE = AccessMemory(PTEAddr)
// valid로 프로세스가 페이지에 엑세스 가능한지 확인
if (PTE.Valid == False)
	RaiseException(SEGMENTATION_FAULT)
    //protection으로 엑세스 가능한지 확인
else if (CanAccess(PTE.ProtectBits) == False)
	RaiseException(PROTECTION_FAULT)
else
	// Access OK: form physical address and fetch it
	offset = VirtualAddress & OFFSET_MASK
	PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
	Register = AccessMemory(PhysAddr)

A Memory Trace

페이징에서 발생하는 메모리 참조를 보여주기 위해 메모리 엑세스 예제를 살펴보자

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

위의 코드가 컴파일된 어셈블리 코드는 아래와 같다. (loop 한 번)

1024 movl $0x0,(%edi,%eax,4)
1028 incl %eax
1032 cmpl $0x03e8,%eax
1036 jne 1024

첫 번째 명령은 값 0을 가상 메모리 주소로 옮긴다. %edi(배열 주소)를 가져와서 %eax(i)에 4(정수는 4바이트)를 곱한 값을 더하여 계산된다.
두 번째 명령은 %eax의 값을 증가시키고 (배열 인덱스 i)
세 번째 명령은 %eax를 0x03e8(10진수 1000)과 비교한다.
네 번째 명령은 세 번째 명령이 같지 않을때 루프 맨 위로 점프시킨다.

실제 예를 들어보겠다. 페이지 크기가 1KB인 64KB인 가상 주소 공간이 있다.
그리고 위의 코드가 물리적 주소 1KB에 위치한다고 가정해보자.
페이지 테이블의 내용과 물리 메모리의 위치를 생각해야한다. 배열 페이지 테이블이라고 가정하면, 가상 메모리의 위치의 인덱스를 통해 물리 메모리 위치로 매핑할 수 있다.
페이지 크기가 1KB이므로 가상 주소 공간의 두번째 페이지에 있다.
이 가상페이지가 물리적 프레임 4에 매핑된다고 가정해보자(VPN1->PFN4)
가상 주소 공간의 배열 또한 매핑된다. (VPN39~40 -> PFN7~10)

이제 메모리 참조를 추적할 준비가 되었다. 명령어 fetch는 두개의 메모리 참조를 생성한다. 물리적 메모리를 찾기 위한 페이지 테이블 참조와 명령어를 CPU로 가져오는 것이다.
mov명령어의 메모리 참조는 페이지 테이블 엑세스(배열의 엑세스)를 추가한다.
아래 사진을 참고해보자
A Virtual (And Physical) Memory Trace
이 사진은 1000번의 loop중 5번을 나타낸 그림이다. 컴파일된 코드는 4줄의 어셈블리 코드가 되고 이를 통해 4번의 메모리 엑세스가 발생한다. 그리고 배열의 엑세스 한 번, 5번의 페이지 테이블 엑세스가 발생한다. 즉 한 번의 반복에서 10번의 메모리 엑세스가 발생하는 것이다.(비효율)

정리

페이징에 대한 소개를 하였다. 페이징은 세그멘테이션과 비교해서
1. 고정 크기의 단위로 메모리를 분할하기에 외부 단편화가 발생하지 않는다.
2. 가상 주소 공간을 효율적으로 사용할 수 있다.(유연성)
이런 장점을 가지고 있지만
1. 페이지 테이블로 메모리가 채워지는 메모리 낭비
2. 추가적인 메모리 (페이지 테이블로) 엑세스
이런 단점도 가지고 있다.

박정빈

이전 포스트

Free-Space Management

다음 포스트