21. 페이징

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

첫 번째 방법은 가변 크기의 조각들로 분할하는 것이다.

이러한 방법은 공간을 다양한 크기의 청크로 분할할 때 공간 자체가 단편화(fragmented) 될 수 있고, 할당은 점점 어려워진다.

두 번째 방법은 공간을 동일 크기의 조각으로 분할하는 것을 고려한다.

가상 메모리에서 이를 페이징(paging)이라 부른다.

프로세스의 주소 공간을 몇 개의 가변 크기의 논리 세그먼트(코드, 힙, 스택)로 나누는 것이 아니라 고정 크기의 단위로 나눈다.

이 각각의 고정 크기 단위를 페이지(page)라고 부른다.

물리 메모리도 페이지 프레임(page frame)이라 부르는 고정 크기의 슬롯의 배열이라 생각한다.

프레임 각각은 하나의 가상 메모리 페이지를 저장할 수 있다.

페이지를 사용하여 어떻게 메모리를 가상화할 수 있을까

세그멘테이션의 문제점을 해결하기 위해 페이지를 사용하여 어떻게 메모리를 가상화할 수 있는가?

어떠한 기법을 사용하는가?

공간과 시간 오버헤드를 최소로 하면서 그 기법을 잘 동작하게 만들기 위한 방법은 무엇인가?

21.1 개요

64바이트이면서 4개의 16바이트 페이지로 구성된 (가상 페이지 0, 1, 2, 4) 작은 주소 공간을 예로 들 수 있다.

물리 메모리는 고정 크기의 슬롯들로 구성되며 해당 예시의 경우 8개의 페이지 프레임, 총 128바이트의 작은 물리 메모리이다.

가상 주소 공간의 페이지들은 물리 메모리 전체에 분산 배치되어 있다.

페이징의 가장 큰 장점은 유연성으로 페이징을 사용하면 프로세스의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념을 지원할 수 있다.

또 다른 장점은 페이징이 제공하는 빈 공간 관리의 단순함이다.

운영체제가 작은 64바이트 주소 공간을 8페이지 물리 메모리에 배치하기를 원한다고 할 때, 운영체제는 비어 있는 네 개의 페이지만 찾으면 된다.

운영체제는 모든 비어 있는 페이지의 빈 공간 리스트를 유지하고 리스트의 첫 네 개의 페이지를 선택할 것이다.

주소 공간의 각 가상 페이지에 대한 물리 메모리 위치 기록을 위하여 운영체제는 프로세스 마다 페이지 테이블(page table)이라는 자료 구조를 유지한다.

페이지 테이블의 역할은 주소 공간의 가상 페이지 주소 변환(address translation) 정보를 저장하는 것이며 각 페이지는 저장된 물리 메모리의 위치가 어디인지 알려준다.

페이지 테이블은 (VP 0 -> PF 3), (VP 1 -> PF 7), (VP2 -> PF5) 및 (VP3 -> PF 2)의 4개의 항목을 가진다.

페이지 테이블은 프로세스마다 존재하며 다른 프로세스를 실행해야 한다면 운영체제는 이 프로세스를 위한 다른 페이지 테이블이 필요하다.

새 프로세스의 가상 페이지는 다른 물리 페이지에 존재하기 때문이다.

프로세스가 생성한 가상 주소의 변환을 위해 먼저 가상 주소를 가상 페이지 번호(virtual page number, VPN)와 페이지 오프셋 2개의 구성 요소로 분할한다.

가상 주소 공간의 크기가 64바이트이기 때문에 가상 주소는 6비트(2^6 = 64)가 필요하다.

페이지 크기는 64바이트의 주소 공간에서 16바이트이다.

따라서 4페이지를 선택할 수 있어야 하고 주소의 최상위 2비트가 그 역할을 한다.

2비트 가상 페이지 번호(VPN)를 가지고 나머지 비트는 페이지 내에서 사용자가 원하는 바이트의 위치를 나타내는 오프셋이다.

프로세스가 가상 주소를 생성하면 운영체제와 하드웨어가 의미있는 물리 주소로 변환한다.

예를 들어, 탑재 명령어의 가상 주소가 21이라고 한다.

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

따라서 가상 주소 "21"은 가상 페이지 "01"의 5번째 "0101"번째 바이트이다.

이 가상 페이지 번호를 가지고 페이지 테이블의 인덱스로 사용하여 가상 페이지 1이 어느 물리 프레임에 저장되어 있는지 찾을 수 있다.

페이지 테이블에서 물리 프레임 번호(physical frame number, PFN) 혹은 물리 페이지 번호(physical page number, PPN)는 7(이진수 111)이다.

VPN을 PFN으로 교체하여 가상 주소를 변환할 수 있다.

그런 후에 물리 메모리에 탑재 명령어를 실행한다.

오프셋은 변환되지 않는다.

오프셋은 페이지 내에서의 우리가 원하는 위치를 알려주기 때문이다.

최종적으로 계산된 물리 주소는 1110101(십진수 117)이며, 이 곳이 탑재할 데이터가 저장된 정확한 의치이다.

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

예를 들어 4KB 크기의 페이지를 가지는 전형적인 32비트 주소 공간의 경우 가상 주소는 20비트 VPN과 12비트 오프셋으로 구성된다.

(1KB 페이지 크기를 위해 10비트가 필요하며, 4KB 페이지를 위해서는 두 비트만 추가하면 된다.)

20비트 VPN은 운영체제가 각 프로세스를 위해 관리해야 하는 변환의 개수가 2^20이라는 것을 의미한다.

물리 주소로의 변환 정보와 다른 필요한 정보를 저장하기 위하여 페이지 테이블 항목(page table entry, PTE) 마다 4바이트가 필요하다고 가정하면, 각 페이지 테이블을 저장하기 위하여 4MB의 메모리가 필요하게 된다.

(4KB 크기의 페이지 32비트 주소 공간 가상 주소는 20비트 VPN과 12비트 오프셋)

프로세스 100개가 실행 중이라고 가정하면 주소 변환을 위해서 운영체제가 400MB의 메모리를 필요로 하게 된다.

페이지 테이블이 매우 크기 때문에 현재 실행 중인 프로세스의 페이지 테이블을 저장할 수 있는 회로를 MMU 안에 유지하지 않을 것이다.

대신 각 프로세스의 페이지 테이블을 메모리에 저장한다.

당분간 페이지 테이블은 운영체제가 관리하는 물리 메모리에 상주한다고 가정한다.

페이지 테이블은 운영체제 가상 메모리에 저장할 수 있고 디스크에 스왑될 수 있다.

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

페이지 테이블은 가상 주소(가상 페이지 번호)를 물리 주소(물리 프레임 번호)로 매핑하는 데 사용되는 자료구조이다.

가장 단순한 형태는 선형 페이지 테이블(linear page table)이다.

운영체제는 원하는 물리 프레임 번호(PFN)를 찾기 위하여 가상 페이지 번호(VPN)로 배열의 항목에 접근하고 그 항목의 페이지 테이블 항목(PTE)를 검색한다.

각 PTE에는 이해가 필요한 비트들이 존재한다.

유효 비트(valid bit)는 특정 변환의 유효 여부를 나타내기 위하여 포함된다.

프로그램이 실행을 시작할 때 코드와 힙이 주소 공간의 한쪽에 위치하고 반대쪽은 스택이 차지하고 있다.

그 사이의 모든 미사용 공간은 무효(invalid)로 표시되고, 프로세스가 그런 메모리를 접근하려고 하면 운영체제에 트랩을 발생시킨다.

운영체제는 그 프로세스를 종료시킬 확률이 높다.

유효 비트는 할당되지 않은 주소 공간을 표현하기 위해 필요하다.

주소 공간의 미사용 페이지를 모두 표시함으로써 이러한 페이지들에게 물리 프레임을 할당할 필요를 없애 대량의 메모리를 절약한다.

페이지가 읽을 수 있는지, 쓸 수 있는지, 또는 실행될 수 있는지를 표시하는 protection bit가 있다.

protection bit가 허용되지 않는 방식으로 페이지에 접근하려고 하면 운영체제가 트랩을 생성한다.

21.6 요약

메모리 가상화에 대한 해결책으로 페이징은 메모리를 고정 크기의 단위로 나눈다.

페이징은 가상 주소 공간의 드문 사용을 허용한다.

페이징을 제대로 구현하지 못하면 컴퓨터가 매우 느려지고(페이지 테이블 접근을 위한 많은 추가적 접근) 뿐만 아니라 메모리 낭비(유용한 응용 데이터 대신 페이지 테이블로 가득 참)를 초래한다.