OSTEP 18 - Introduction fo Paging

운영체제는 거의 모든 공간 관리 문제를 해결할 때 두가지 중 하나를 사용한다.

• 가변 크기의 조각들로 분할 (세그멘테이션) 그러나 다양한 크기로 분할하면서 공간에 대한 단편화가 많이 발생하고, 할당이 어려워진다.
  
• 동일 크기의 조각으로 분할 이번 장에서 배우게 될 Paging이 이런 방식이다. 주소 공간을 Page라고 부르는 고정 크기 단위로 나눈다. 물리 메모리는 페이지 프레임이라고 불리는 페이지 배열을 통해 페이지들을 저장한다.
  

핵심 질문: 페이지를 사용하여 어떻게 메모리를 가상화할 수 있을까?
*세그멘테이션의 문제점을 해결하기 위해 페이지를 사용해 어떻게 메모리를 가상화할 수 있을까? 공간과 시간적인 오버헤드를 어떻게 줄일까?*

1. 간단한 예제 및 개요

명확한 이해를 위해 간단한 예시를 들어보자. 총 크기가 64바이트이고 16바이트 페이지 4개로 구성된 주소 공간의 상황을 가정하자. 그러나 실제 주소 공간은 32비트는 4GB, 64비트는 훨씬 크다.

물리 메모리는 128바이트의 크기를 가지고, 고정 크기의 슬롯을 가진다. 일부는 OS를 위한 커널 메모리 공간이다.

페이징은 이전 방식에 비해 많은 장점이 있다.

1. 유연성

   프로세스의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념을 지원할 수 있다. 예를 들어, 힙과 스택이 커지는 방향, 어떻게 사용되는 가를 고려할 필요가 없다.

2. 빈 공간 관리가 단순하다.

   만약 64바이트 주소 공간을 물리 메모리에 배치하기 원한다면, 운영체제는 4개의 비어있는 페이지를 찾기만 하면 된다. 이를 위해 OS는 고정 크기의 빈 공간 리스트를 가지고 찾아줄 것이다.

주소 공간의 각 가상 페이지 테이블에 대한 물리 메모리의 위치가 필요할텐데, 운영체제는 프로세스마다 페이지 테이블이라는 자료구조를 유지한다. 주소 공간의 가상 페이지를 물리 메모리에서의 위치가 어디인지 알려주는 주소 변환 정보를 가지고 있다.

페이지 테이블은 프로세스마다 존재한다는 것을 숙지해야한다. 공유 중인 페이지가 없다면,

이제 주소 변환을 실제로 해보자.

movl <virtual address>, %eax

주소 를 eax 레지스터에 탑재하는 과정을 살펴보자

먼저 가상 주소를 가상 페이지 번호(virtual page number, VPN)와 페이지 내의 오프셋 2개의 구성 요소를 분할 한다. 위 예의 경우 주소 공간의 크기는 64이기 때문에 6비트가 필요하다($2^6=64$).

페이지의 크기는 64바이트의 공간 중에 16바이트이다. 즉, 4페이지 선택할 수 있어야 하기 때문에 상위 2비트가 그 역할을 한다. 나머지 비트는 페이지 내에서 우리가 원하는 바이트의 위치를 나타낸다.

movl 21, %eax

같은 경우는 아래와 같은 가상 주소 공간을 가진다.

페이지 페이블에서는 VPN을 물리 페이지 번호(물리 프레임 번호)로 매핑한다. (PFN, PPN) 해당 예시의 경우 VPN 1은 PFN 7(111)에 매핑된다고 가정하자. OS는 VPN을 PFN으로 교체하여 가상 주소 변환을 한다.

오프셋은 그대로 가져가고, 그 결과인 1110101이 물리 메모리의 주소이다.

그렇다면, 페이지 테이블은 어디에 저장될까? 페이지 테이블의 내용은 무엇인가? 페이지 테이블의 크기는 얼마인가? 페이징이 시스템을 느리게 만들지는 않을까? 지금부터 알아보자

2. 페이지 테이블은 어디에 저장되는가

페이지 테이블은 매우 커질 수 있다.

4KB 크기의 페이지를 가지는 32비트 주소 공간을 상상해보자. 이 가상 주소는 20비트의 VPN과 12 비트의 오프셋을 가진다. (1KB 페이지를 위해 10비트가 필요하기 때문에, 4KB에서는 12비트가 필요함)

20비트 VPN은 OS가 각 프로세스를 위해 관리해야하는 변환의 개수가 $2^{20}$이라는 것을 의미한다. 물리 주소로의 변환 정보를 저장하기 위해 페이지 테이블 항목(page table entry, PTE)마다 4바이트가 필요하다고 가정하면, 각 페이지 테이블을 저장하기 위해서 4MB($2^{20} * 4byte$) 가 필요하게 된다.

만약 프로세스가 100개가 실행중이라면, 400MB가 필요하게 된다. 만약 64비트 주소 공간을 사용한다면, 더더욱이 커질 것이다.

페이지 테이블의 큰 크기 때문에, 프로세스의 페이지 테이블을 MMU 안에서 유지하지 않는다. 일단 지금은 페이지 테이블은 운영체제가 관리하는 물리 메모리에 상주한다고 가정하자.

나중에 운영체제 메모리 자체의 많은 부분이 가상화 될 수 있다는 것을 알게될 것이다. 페이지 테이블은 OS의 가상 메모리에 저장되기도 하고, 디스크로 스왑되기도 한다.

3. 페이지 테이블에는 실제 무엇이 있는가

페이지 테이블의 구성에 대해 살펴보자. 페이지 테이블은 가상 주소를 물리 주소(물리 프레임 번호)로 매핑하는데 필요한 자료구조이다. 가장 간단한 형태는 선형 페이지 테이블이다. VPN을 인덱스로 PTE를 검색할 수 있다.

이후 페이징 관련 문제를 해결하기 위해 고급 자료 구조가 사용된다.

• Valid bit - 특정 변환의 유효여부 표시, 주소 공간의 스택과 힙 사이는 유효하지 않을 것이다. 이렇게 할당되지 않은 공간을 표시하기 위해 필요하다.
• protection bit - protection bit가 허용하지 않는 방식으로 페이지에 접근하려 하면 트랩 발생
• present bit - 페이지가 물리 메모리에 있는지, 디스크에 있는지(스왑 아웃)
• dirty bit - 메모리에 반입된 후 페이지의 변경 여부
• reference(access) bit - 페이지의 접근 여부 추적, 페이지 인기도 기반의 페이지 교체 알고리즘에 용이하다.

4. 페이징: 너무 느림

페이지 테이블의 크기가 메모리 상에서 매우 크게 증가할 수 있다. 페이지 테이블로 인해 처리 속도가 저하될 수 있다. 간단한 명령어를 예로 들어보자

movl 21, %eax

하드웨어가 주소 변환을 담당한다고 가정하자.

가상주소(21)을 물리주소(117)로 변환하기 위해서 시스템은 페이지 테이블에서 적절한 페이지 테이블 항목 가져오기 / 변환 수행 / 물리 메모리에서 데이터 탑재의 과정을 거친다. 이렇게 하기 위해, 하드웨어는 현재 실행 중인 프로세스의 테이블 페이지 위치를 알아야한다. 일단 하나의 페이지 테이블 베이스 레지스터가 페이지 테이블의 시작 주소를 저장한다고 가정하자

원하는 PTE의 위치를 찾기 위해 1-4 라인의 연산을 수행한다. 이후 페이지 테이블에 접근하여 물리 주소를 매핑하게 된다. 이 경우, 모든 메모리 참조에 대해 먼저 페이지 테이블에서 변환 정보를 반입해야하기 때문에 반드시 한번의 추가적인 메모리 참조가 필요하다. 메모리 참조는 비용이 비싸고, 프로세스의 속도도 2배 이상 느려진다.

하드웨어와 소프트웨어의 신중한 설계가 없다면, 페이지 테이블로 인해 시스템이 매우 느려질 수 있고 많은 메모리를 차지하게 된다.페이징이 메모리 가상화에 필요한 훌륭한 정책처럼 보이지만 이 문제를 해결해야 한다.

5. 메모리 트레이스

int arr[1000];
...
for (i = 0; i < 1000; i++) {
	arr[i] = 0;
}

페이지 크기를 1KB라고 가정하면, 정수 1000개 (4000바이트)를 위해서는 4개의 페이지 테이블이 필요할 것이고, 코드를 위해 1개의 페이지 테이블이 더 필요할 것이다.

메모리 참조의 경우 명령어 반입시 2번(명령어 위치 파악/ 명령어 자체)한다. mov 명령어에서도 한번의 메모리 참조가 이루어지고, 페이지 테이블 한번 접근, 다음 배열 접근을 위해 한번 또 참조된다.

위 코드를 5번 실행시켰을 때의 메모리 트레이스다.

루프 1번에 대해서 보면, 네번의 명령어 반입 / 한번의 메모리 갱신 / 두 과정에서 주소 변환을 위한 페이지 테이블 참조까지 루프당 10번의 메모리 접근이 필요하다. 이렇게 간단한 코드에도 메모리가 복잡하게 동작함을 알 수 있다.