이 장에서는 메모리 공간 관리 문제를 해결하는 두 가지 방법에 대해 이야기한다. 첫 번째는 가변 크기의 조각으로 나누는 것으로, 가상 메모리의 segmentation에서 볼 수 있다. 그러나 이 방법은 조각남으로 인한 문제가 발생할 수 있다. 그래서 두 번째 방법으로는 고정 크기로 공간을 나누는 것이다. 이를 paging이라고 하며, 이는 Atlas 시스템에서 처음으로 사용되었다. 가상 메모리를 페이지 단위로 가상화하는 기술에 대해 다룬다. segmentation의 문제를 회피하면서 메모리를 가상화하는 방법과 기본 기술, 최소한의 시간과 공간 오버헤드로 어떻게 잘 작동할 수 있는지를 알아본다. 이 문제를 해결하는 핵심은 페이지 크기와 페이지 테이블, 페이지 교체 알고리즘에 대한 이해이다.
1. A Simple Example And Overview
페이지 교체 기법은 가상 메모리를 구현하기 위해 사용되며, 가상 주소 공간을 고정 크기인 페이지로 분할하여 물리적 메모리와 연결하는 방식이다. 이를 통해 가상 메모리를 물리적 메모리와 분리하여 프로세스가 필요한 만큼의 메모리만 사용할 수 있게 되며, 이를 통해 다중 프로그래밍을 지원한다.
예시를 통해 이를 살펴보면, 64바이트의 작은 가상 주소 공간을 가진 프로세스의 페이지를 16바이트 단위로 4개의 페이지로 나누어, 8개의 페이지 프레임에 배치하는 것을 보여준다. 이때, 페이지 테이블이라는 프로세스마다 유지되는 데이터 구조를 통해 가상 페이지와 물리 페이지 간의 매핑 정보를 기록한다. 프로세스가 가상 주소에 접근하면, 이를 가상 페이지 번호와 오프셋으로 분리하여 페이지 테이블을 참조하여 물리 페이지로 변환한다.
이를 통해 가상 메모리를 구현할 수 있으며, 프로세스마다 별도의 페이지 테이블을 유지하여 다중 프로그래밍을 지원한다. 페이지 교체 기법은 유연성과 간단한 공간 관리 등의 장점을 가지고 있으며, 성능 저하를 유발하지 않도록 고려하여 구현해야 한다. 페이지 테이블은 프로세스마다 유지되는 데이터 구조이며, 일반적으로 프로세스의 메모리 요구에 따라 크기가 달라질 수 있다.
이러한 페이지 교체 기법을 통해, 가상 메모리를 구현하고 프로세스의 메모리 사용을 최적화할 수 있다.
2. Where Are Page Tables Stored?
가상 메모리를 구현하기 위한 페이지 테이블은 매우 큰 데이터 구조이다. 예를 들어, 32비트 주소 공간에서 4KB 페이지를 사용하는 경우, 페이지 번호에 필요한 비트 수는 20비트이다. 이는 각 프로세스마다 2의 20승 개의 페이지 번역을 관리해야 함을 의미한다.
이를 위해서는 각 페이지 테이블 항목(PTE)에 물리적 주소와 같은 유용한 정보를 저장하기 위해 4바이트가 필요하며, 따라서 하나의 페이지 테이블당 4MB의 메모리가 필요하다. 100개의 프로세스가 실행되고 있다면, OS는 이러한 주소 번역을 위해 400MB의 메모리를 필요로 하게 된다. 페이지 테이블은 가상 주소 공간의 각 페이지가 물리 메모리에서 어디에 위치하는지를 알려주는 데이터 구조로, 일반적으로 프로세스 당 하나씩 존재한다.
페이지 테이블의 구조는 하드웨어에 따라 결정될 수도 있으며, 최신 시스템에서는 OS에서 더 유연하게 관리될 수 있다. 하지만 페이지 테이블이 매우 크기 때문에, 현재 실행 중인 프로세스의 페이지 테이블을 저장하기 위해 특별한 칩 하드웨어를 MMU에 유지하지 않는다. 대신, 각 프로세스의 페이지 테이블을 메모리 어딘가에 저장하고 있다. 페이지 테이블은 메모리 관리 서브시스템에서 가장 중요한 데이터 구조 중 하나이다.
3. What’s Actually In The Page Table?
가상 주소 공간과 물리 주소 공간 간의 매핑 정보를 저장하는 데이터 구조인 페이지 테이블은 가상 메모리 시스템에서 중요한 역할을 한다. 페이지 테이블은 가상 페이지 번호와 물리 페이지 번호를 매핑해주며, 각각의 프로세스마다 페이지 테이블이 존재한다. 페이지 테이블은 간단한 선형 배열로 구성되며, 가상 페이지 번호를 인덱스로 사용해 PTE(페이지 테이블 엔트리)를 찾고, PTE에서 물리 페이지 번호를 찾아내어 매핑한다.
PTE는 다양한 비트로 구성되어 있으며, 유효 비트는 해당 페이지가 유효한지 여부를 나타내고, 보호 비트는 페이지의 읽기/쓰기/실행 권한 여부를 나타낸다. 이 외에도 존재 비트, 더티 비트, 참조 비트 등이 있다. 이러한 비트들은 가상 주소 공간을 효율적으로 사용하고, 페이지 교체 및 스왑아웃 등 가상 메모리 관리에서 중요한 역할을 한다. x86 아키텍처에서 사용되는 PTE 구조는 여러 비트를 포함하고 있다. PTE를 사용하는 OS 개발자들은 매뉴얼을 자세히 읽어야 하지만, 이를 이해하는 것은 어려울 수 있다.
4. Paging: Also Too Slow
이번에는 메모리 참조마다 page table을 조회하는 과정에서 생기는 성능 저하와 메모리 공간 문제에 대해 살펴보자. 예를 들어, "movl 21, %eax" 명령어를 실행하려면 먼저 가상 주소(21)를 물리 주소(117)로 번역해야 한다. 이를 위해 하드웨어는 현재 실행 중인 프로세스의 페이지 테이블에서 해당 페이지 테이블 엔트리를 가져와야 하며, 이 과정에서 메모리 참조를 한 번 더 수행해야 한다. 이러한 추가적인 메모리 참조는 시스템 성능을 느리게 하고, 프로세스가 더 많아질수록 문제가 심각해진다.
현재 실행 중인 프로세스의 페이지 테이블을 찾기 위해 하드웨어는 페이지 테이블 베이스 레지스터를 사용한다. 페이지 테이블 베이스 레지스터는 페이지 테이블의 시작 위치를 가리키는 물리적 주소를 포함하고 있다. 페이지 테이블 엔트리의 위치를 찾기 위해 하드웨어는 다음과 같은 함수를 수행한다: VPN = (VirtualAddress & VPN_MASK) >> SHIFT, PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE)). VPN_MASK는 0x30(hex 30)과 같이 VPN 비트를 가져오는 마스크를 의미하며, SHIFT는 4와 같이 VPN 비트를 이동시켜 정수 가상 페이지 번호를 만드는 데 사용된다.
PTE를 찾았으면 하드웨어는 해당 PTE에서 PFN(물리 프레임 번호)을 추출하고, 가상 주소에서 오프셋과 연결하여 물리 주소를 구한다. 최종적으로, 하드웨어는 메모리에서 데이터를 가져와 레지스터에 넣는다. 하지만 이러한 과정에서 매번 페이지 테이블을 조회하므로 메모리 참조마다 추가적인 메모리 참조가 필요해 성능 저하를 유발한다.
따라서 하드웨어와 소프트웨어가 공동으로 page table의 문제를 해결해야 한다. 이러한 문제가 해결되지 않으면, 메모리 가상화의 해결책으로는 좋지만 메모리 공간과 성능 저하라는 두 가지 심각한 문제를 야기할 수 있다.
5. A Memory Trace
Paging은 메모리 가상화를 위한 좋은 솔루션으로 보이지만, 이를 사용할 때 문제점이 있다. 첫 번째로, 페이지 테이블이 너무 큰 경우가 있으며, 두 번째로는 성능 저하가 일어날 수 있다. 예를 들어, 메모리 참조가 발생할 때마다, 페이지 테이블에서 변환을 위해 메모리 참조가 추가로 발생하게 된다. 따라서 메모리 참조마다 한 번의 추가적인 메모리 참조가 필요하기 때문에 성능 저하가 발생하게 된다.
이번에는 C 코드를 사용하여 간단한 배열 초기화 예제를 통해 메모리 접근에 대한 모든 결과 메모리 접근을 보여줄 것이다. 페이지 크기가 1KB이고, 가상 주소 공간이 64KB인 경우, 가상 페이지 1024는 가상 주소 공간의 두 번째 페이지(VPN=1)에 해당한다. 이 가상 페이지가 물리 프레임 4로 매핑되도록 가정한다. 또한 배열의 크기가 4000바이트이며, 가상 주소 40000에서 44000까지 위치한다고 가정한다. 배열에 대한 가상 페이지(VPN 39~42)에 대한 가상 주소와 물리 프레임의 매핑을 예를 들어 가정한다.
메모리 참조가 발생할 때마다, 페이지 테이블에서 변환을 위해 메모리 참조가 추가로 발생하며, 명시적인 메모리 참조도 하나 발생한다. 첫 다섯 번째 루프의 경우, 이를 그래프로 나타낸다면, 한 루프당 10개의 메모리 참조가 발생하며, 총 네 개의 명령어 가져오기, 하나의 명시적 메모리 업데이트, 그리고 다섯 개의 페이지 테이블 접근이 있다. 이번 예제는 간단하지만 실제 애플리케이션의 메모리 동작을 이해하는 것이 복잡할 수 있기 때문에, 새로운 메모리 위치와 새로운 접근 패턴을 예측하고 해결하는 것은 어렵다.
