운영 체제는 대부분의 공간 관리 문제를 해결하기 위해 두 가지 접근 방식 중 하나를 취한다고 할 때가 있다. 첫 번째 접근 방식은 가변 크기의 조각으로 공간을 나누는 것이다. 우리는 가상 메모리에서 세분화로 이를 확인했다. 하지만, 이 해결책은 고유한 어려움을 가지고 있다. 특히, 공간을 다른 크기의 조각으로 나누면, 공간 자체가 조각화되어 시간이 지남에 따라 할당이 더 어려워진다.
그러므로, 두 번째 접근 방식을 고려하는 것이 좋을 수 있다. 공간을 고정 크기의 조각으로 나누는 것이다. 가상 메모리에서는 이 아이디어를 "페이징(paging)"이라고 부르며, 이는 초기에 중요한 시스템인 Atlas에서부터 시작되었다. 프로세스의 주소 공간을 가변 크기의 논리적 세그먼트(예: 코드, 힙, 스택)로 분할하는 대신에, 우리는 고정된 크기의 단위로 나누어 각각을 "페이지(page)"라고 부른다. 이에 상응하게, 물리적 메모리를 페이지 프레임이라고 하는 고정된 크기의 슬롯 배열로 보며, 각각의 프레임은 단일 가상 메모리 페이지를 포함할 수 있다.
1. A Simple Example And Overview
간단한 예시를 통해 이 접근 방식을 명확히 이해해보자. 도식 18.1(2 페이지)은 매우 작은 주소 공간의 예시를 보여준다. 전체 크기는 총 64바이트이고, 16바이트로 이루어진 4개의 가상 페이지(가상 페이지 0, 1, 2, 3)가 있다. 실제 주소 공간은 훨씬 크며, 보통 32비트 또는 64비트의 주소 공간을 갖는다. 책에서는 이해하기 쉽게 작은 예시를 자주 사용한다.
도식 18.2에서 볼 수 있듯이, 물리적 메모리도 일정한 크기의 슬롯으로 구성되어 있다. 이 경우 8개의 페이지 프레임(128바이트 물리적 메모리로도 매우 작음)이 있다. 다이어그램에서는 가상 주소 공간의 페이지가 물리적 메모리의 다른 위치에 배치되어 있으며, 운영 체제가 일부 물리적 메모리를 사용하고 있는 것도 표시되어 있다.
페이징은 이전 방식에 비해 여러 가지 이점을 가지고 있다. 아마도 가장 중요한 개선점은 유연성일 것이다. 완전히 발전된 페이징 접근 방식을 사용하면, 시스템은 프로세스가 주소 공간을 어떻게 사용하든지 효과적으로 주소 공간의 추상화를 지원할 수 있다. 예를 들어, 힙과 스택이 어떤 방향으로 성장하고 사용되는지에 대한 가정을 하지 않을 것이다.
또 다른 이점은 페이징이 제공하는 자유 공간 관리의 간단함이다. 예를 들어, 운영 체제가 64바이트의 작은 주소 공간을 8개의 페이지로 구성된 물리적 메모리에 배치하려는 경우, 운영 체제는 간단히 4개의 빈 페이지를 찾으면 된다. 아마도 운영 체제는 이를 위해 모든 빈 페이지의 목록을 유지하고 있으며, 이 목록에서 처음 4개의 빈 페이지를 가져오는 것일 것이다. 예시에서는 운영 체제가 주소 공간의 가상 페이지 0을 물리적 프레임 3에, 가상 페이지 1을 프레임 7에, 페이지 2를 프레임 5에, 페이지 3을 프레임2에 배치했다. 페이지 프레임 1, 4 및 6은 현재 빈 상태이다.
각 가상 페이지가 물리적 메모리의 어디에 위치하는지를 기록하기 위해 운영 체제는 일반적으로 페이지 테이블이라고 하는 프로세스당 데이터 구조를 유지한다. 페이지 테이블의 주요 역할은 주소 공간의 각 가상 페이지에 대한 주소 변환을 저장하여 어느 페이지가 물리적 메모리의 어디에 있는지 알 수 있게 하는 것이다. 위의 간단한 예시에서는 페이지 테이블에 다음 네 가지 항목이 있을 것이다: (가상 페이지 0 → 물리적 프레임 3), (VP 1 → PF 7), (VP 2 → PF 5), (VP 3 → PF 2).
이 페이지 테이블은 프로세스 당 데이터 구조이며 (우리가 다루는 대부분의 페이지 테이블 구조는 프로세스 단위의 구조이며, 역전된 페이지 테이블에 대해서는 예외적으로 다룰 것이다), 다른 프로세스가 위의 예시에서 실행된다면 해당 프로세스를 위해 별도의 페이지 테이블을 관리해야 한다. 가상 페이지는 당연히 다른 물리적 페이지에 매핑되기 때문이다.
이제 우리는 주소 변환 예시를 수행하기에 충분한 지식을 갖고 있다. 작은 주소 공간 (64바이트)을 갖는 프로세스가 메모리 접근을 수행한다고 가정해보자:
movl <가상 주소>, %eax
구체적으로, 레지스터 eax로부터 주소 <가상 주소>에 있는 데이터를 명시적으로 로드하는 것에 주목하자 (앞서 발생한 명령어 페치는 무시한다).
프로세스가 생성한 가상 주소를 번역하기 위해 운영 체제와 하드웨어는 협력하여 의미 있는 물리적 주소로 변환해야 한다. 예를 들어, 위의 로드가 가상 주소 21로 수행되었다고 가정해보자:
movl 21, %eax
"21"을 이진 형태로 변환하면 "010101"이 되며, 이를 통해 가상 주소가 가상 페이지 번호 (VPN)와 오프셋으로 어떻게 분해되는지 살펴볼 수 있다:
따라서 가상 주소 "21"은 가상 페이지 "01" (또는 1)의 5번째 ("0101"번째) 바이트에 해당한다. 가상 페이지 번호를 사용하여 페이지 테이블을 인덱싱하고 가상 페이지 1이 속한 물리적 프레임을 찾을 수 있다. 위의 페이지 테이블에서 물리적 프레임 번호 (PFN)는 7 (이진 111)이다. 따라서 가상 주소를 가상 페이지 번호 대신 PFN으로 대체하고, 물리적 메모리에 로드를 수행할 수 있다 (도식 18.3 참조).
오프셋은 동일한 상태로 유지되며 (즉, 변환되지 않음), 오프셋은 우리가 원하는 페이지 내의 바이트를 가리킨다. 최종적인 물리적 주소는 1110101 (10진수로 117)이며, 데이터를 로드해야 할 위치와 정확히 일치한다 (도식 18.2, 2 페이지 참조).
이 기본적인 개요를 기반으로 페이징에 관해 간단한 질문 몇 가지를 하고 (아마도) 답할 수 있다. 예를 들어, 이 페이지 테이블은 어디에 저장되는가? 페이지 테이블의 일반적인 내용과 크기는 어떻게 되는가? 페이징은 시스템을 (너무) 느리게 만드는가? 이와 같은 궁금증에 대한 답변은 아래 텍스트에서 부분적으로 제공된다.
2. Where Are Page Tables Stored?
페이지 테이블은 작은 세그먼트 테이블이나 베이스/바운드 쌍보다 훨씬 크다. 예를 들어, 일반적인 32비트 주소 공간에서 4KB 페이지를 사용하는 경우, 각 프로세스마다 약 4MB의 메모리가 페이지 테이블에 필요하다. 따라서 여러 프로세스가 실행되는 경우, 주소 변환을 위해 막대한 양의 메모리가 필요하게 된다.
이로 인해 페이지 테이블을 MMU 칩 안에 저장하는 것은 현실적이지 않다. 대신, 각 프로세스의 페이지 테이블은 메모리의 어딘가에 저장된다. 일단은 페이지 테이블이 OS가 관리하는 물리적 메모리에 위치한다고 가정해보자. 나중에 우리는 OS 메모리의 많은 부분을 가상화할 수 있고, 따라서 페이지 테이블을 OS 가상 메모리에 저장할 수 있다는 것을 알게 될 것이다. 그러나 현재는 너무 혼란스러우므로 이를 무시하겠다. 도식 18.4(5페이지)는 OS 메모리에 있는 페이지 테이블의 그림이다. 거기에 작은 번역 세트가 있다.
페이지 테이블이 너무 크기 때문에 현재 실행 중인 프로세스의 페이지 테이블을 저장하기 위해 특별한 내장 하드웨어를 MMU에 유지하지 않는다. 대신, 각 프로세스의 페이지 테이블은 메모리의 어딘가에 저장된다.
3. What’s Actually In The Page Table?
페이지 테이블은 가상 주소를 물리 주소로 매핑하는 데이터 구조이다. 가장 간단한 형태는 선형 페이지 테이블로, 가상 페이지 번호를 인덱스로 사용하여 해당하는 페이지 테이블 항목을 찾아 물리적 프레임 번호를 얻는다. 각 페이지 테이블 항목에는 유효 비트, 보호 비트(읽기, 쓰기, 실행), 존재 비트, 변경 비트, 참조 비트 등 여러 가지 정보가 담긴다.
페이지 테이블은 크기가 매우 크기 때문에 현재 실행 중인 프로세스의 페이지 테이블을 메모리에 저장한다. 페이지 테이블은 가상 주소 공간의 희소성을 지원하기 위해 유효하지 않은 페이지를 표시함으로써 불필요한 물리적 프레임 할당을 방지하고 메모리를 절약한다. 또한, 보호 비트는 올바르지 않은 방식으로 페이지에 접근하는 것을 방지하고, 변경 비트와 참조 비트는 페이지 교체 및 인기 페이지 관리에 유용하다.
페이지 테이블의 구조는 하드웨어에 따라 정해질 수도 있고, 운영 체제에 의해 유연하게 관리될 수도 있다. 페이지 테이블은 가상 주소와 물리 주소 간의 중요한 매핑을 담당하기 때문에 현대 운영 체제에서는 메모리 관리 하위 시스템에서 가장 중요한 데이터 구조 중 하나이다.
4. Paging: Also Too Slow
페이지 테이블을 통해 가상 주소를 물리 주소로 변환하는 과정은 추가적인 메모리 참조를 필요로 한다. 각 메모리 참조마다 페이지 테이블에서 변환 정보를 가져와야 하기 때문이다. 이는 많은 작업을 필요로 하며, 추가적인 메모리 참조는 비용이 크며, 프로세스의 실행 속도를 두 배 이상 느리게 만들 수 있다.
이로 인해 우리는 두 가지 실제 문제를 해결해야 한다는 것을 알 수 있다. 하드웨어와 소프트웨어의 신중한 설계 없이는 페이지 테이블이 시스템의 실행 속도를 늦추고 메모리를 지나치게 사용할 수 있다. 메모리 가상화를 위한 훌륭한 해결책처럼 보이지만, 이 두 가지 중요한 문제를 극복해야 한다.
