페이징 기법

프로세스의 논리 주소 공간은 고정된 크기의 블록인 페이지로 나뉜다. 페이지는 일반적으로 4KB, 8KB, 16KB와 같은 2의 거듭제곱 크기를 가지며, 운영체제에 의해 관리되는 연속적인 논리적 단위이다. 반면, 물리 메모리는 페이지와 동일한 크기의 블록인 프레임으로 나뉜다. 프레임은 실제 데이터가 저장되는 물리적 저장 공간의 단위이다.

페이징의 핵심은 프로세스의 페이지를 물리 메모리의 어떤 프레임에 할당할지 매핑하는 것이다. 이 매핑은 연속성을 요구하지 않는다. 즉, 프로세스의 0번 페이지는 물리 메모리의 5번 프레임에, 1번 페이지는 20번 프레임에 할당될 수 있다. 이로 인해 프로세스가 물리 메모리에 연속적으로 위치할 필요가 없어져 메모리 관리의 유연성이 크게 향상된다.

각 프로세스는 자신의 페이지가 어떤 프레임에 매핑되어 있는지 기록하는 페이지 테이블을 가진다. 페이지 번호는 페이지 테이블의 인덱스로 사용되며, 해당 항목에는 대응되는 프레임 번호와 접근 권한 등의 제어 정보가 저장된다. 따라서 논리 주소는 (페이지 번호, 페이지 내 오프셋)의 쌍으로, 물리 주소는 (프레임 번호, 프레임 내 오프셋)의 쌍으로 구성된다.

페이지 테이블은 페이징 기법의 핵심 자료 구조로, 운영체제가 각 프로세스마다 유지하는 매핑 테이블이다. 이 테이블은 프로세스의 논리적 주소 공간에 있는 페이지가 실제 물리 메모리의 어떤 프레임에 할당되었는지에 대한 정보를 담고 있다. 각 프로세스는 독립적인 페이지 테이블을 가지며, 이는 CPU의 메모리 관리 장치(MMU)가 논리 주소를 물리 주소로 변환할 때 참조하는 지도 역할을 한다.

페이지 테이블의 각 항목을 페이지 테이블 항목(PTE)이라고 부른다. 일반적인 PTE는 다음과 같은 정보를 포함한다.

페이지 테이블은 일반적으로 물리 메모리의 커널 영역에 상주한다. 페이지 테이블의 시작 주소는 페이지 테이블 베이스 레지스터(PTBR)에 저장되어 있으며, 주소 변환 시 이 레지스터 값이 기준 주소로 사용된다. 논리 주소의 페이지 번호(p)는 페이지 테이블 내의 인덱스로 활용되어, 해당 PTE를 찾고 그 안의 프레임 번호(f)를 얻는다. 이후 논리 주소의 페이지 오프셋(d)과 결합하여 최종 물리 주소(f + d)가 생성된다[1].

논리 주소는 프로세스의 관점에서 사용하는 주소 공간이다. 각 프로세스는 0번지부터 시작하는 자신만의 독립적인 논리 주소 공간을 가지며, 이 공간은 페이지 단위로 나뉜다. CPU가 명령어를 실행하거나 데이터에 접근할 때 생성하는 주소는 모두 이 논리 주소이다. 논리 주소는 다시 페이지 번호(p)와 페이지 오프셋(d)으로 구성된다.

반면, 물리 주소는 실제 메인 메모리(RAM)의 하드웨어 주소를 가리킨다. 물리 메모리는 프레임이라는 고정 크기의 블록으로 나뉘며, 각 프레임에는 고유한 물리 주소가 부여된다. 운영체제와 메모리 관리 장치(MMU)의 핵심 역할은 프로세스가 사용하는 논리 주소를 하드웨어가 이해할 수 있는 물리 주소로 변환하는 것이다.

이 변환은 페이지 테이블을 통해 이루어진다. 페이지 테이블은 각 논리적 페이지 번호에 대응하는 물리적 프레임 번호(f)를 저장하는 매핑 테이블이다. 변환 과정에서 페이지 번호(p)는 프레임 번호(f)로 대체되고, 페이지 오프셋(d)은 그대로 유지되어 최종 물리 주소를 형성한다[2]. 이로 인해 프로세스는 물리 메모리가 실제로 어디에 할당되었는지 알 필요 없이 연속된 논리 공간을 사용할 수 있다.

논리 주소와 물리 주소의 분리는 여러 중요한 이점을 제공한다. 각 프로세스의 주소 공간이 분리되어 한 프로세스의 오류가 다른 프로세스나 운영체제에 영향을 미치지 않는 메모리 보호를 구현할 수 있다. 또한, 물리 메모리에서 연속되지 않은 프레임에 페이지를 할당할 수 있어 외부 단편화 문제를 해결하며, 가상 메모리 시스템의 기반이 된다.

주소 변환 과정은 CPU가 생성한 논리 주소를 실제 메모리 상의 물리 주소로 매핑하는 핵심 절차이다. 이 과정은 운영체제와 MMU가 관리하는 페이지 테이블을 통해 이루어진다.

변환 과정은 다음과 같은 단계로 진행된다. 먼저, CPU가 내는 논리 주소는 페이지 번호(p)와 페이지 오프셋(d) 두 부분으로 나뉜다. 페이지 번호는 해당 주소가 속한 가상 메모리 페이지를, 오프셋은 그 페이지 내에서의 상대 위치를 나타낸다. MMU는 페이지 번호를 인덱스로 사용하여 페이지 테이블을 조회한다. 페이지 테이블 항목에는 해당 페이지가 적재된 물리 메모리 프레임의 번호(f)가 저장되어 있다. MMU는 찾아낸 프레임 번호(f)와 원래의 오프셋(d)을 결합하여 최종 물리 주소를 생성한다.

이 변환 과정은 모든 메모리 접근마다 발생해야 하므로, 성능이 매우 중요하다. 페이지 테이블이 주 메모리에만 존재한다면, 한 번의 메모리 접근을 위해 페이지 테이블 조회(1번)와 실제 데이터 접근(1번)으로 총 두 번의 메모리 접근이 필요해져 속도가 크게 저하된다. 이 문제를 해결하기 위해 TLB라는 고속 캐시가 사용된다. TLB는 최근에 사용된 페이지 테이블 항목들을 저장하여, 대부분의 변환 요청을 주 메모리 접근 없이 고속으로 처리할 수 있게 한다.

주소 변환 과정을 요약하면 다음과 같다.

TLB(Translation Lookaside Buffer)는 페이징 시스템의 성능을 크게 향상시키기 위해 설계된 특수한 고속 캐시 하드웨어이다. 이는 CPU와 메인 메모리 사이에 위치하여, 최근에 사용된 페이지 테이블 항목(논리 페이지 번호와 물리 프레임 번호의 매핑)을 저장한다.

주소 변환 과정에서 CPU가 생성한 논리 주소의 페이지 번호를 TLB에서 먼저 검색한다. 이때 원하는 매핑 정보가 TL리브에 존재하면 이를 TLB 히트(TLB hit)라고 하며, 변환에 필요한 물리 프레임 번호를 즉시 얻을 수 있다. 이 경우 메모리에 접근하여 전체 페이지 테이블을 참조할 필요가 없으므로, 주소 변환 속도가 매우 빨라진다. 반대로, 필요한 매핑이 TLB에 없으면 TLB 미스(TLB miss)가 발생하며, 이때는 속도가 느린 메인 메모리에 있는 전체 페이지 테이블을 접근하여 필요한 항목을 찾아야 한다. 찾은 항목은 이후 참조를 위해 TLB에 로드된다.

TLB의 효율성은 참조의 지역성(Locality of Reference) 원리에 기반한다. 프로그램은 일반적으로 일정 시간 동안 특정 메모리 영역(코드, 데이터, 스택 등)을 집중적으로 접근하는 경향이 있어, 제한된 크기의 TLB라도 높은 히트율을 달성할 수 있다. TLB의 성능은 크기, 연관 방식(직접 매핑, 집합 연관, 완전 연관), 그리고 TLB 미스 발생 시의 처리 오버헤드에 의해 결정된다. 현대 대부분의 운영체제와 CPU 아키텍처는 페이징 성능을 위해 TLB를 필수적으로 사용한다.

내부 단편화는 페이징 기법에서 발생하는 주요 문제 중 하나로, 할당된 메모리 블록 내부에서 사용되지 않고 낭비되는 공간을 의미한다. 이는 페이징 시스템이 프로세스의 주소 공간을 고정된 크기의 페이지로 나누고, 물리 메모리 역시 같은 크기의 프레임으로 나누어 관리하기 때문에 발생한다.

문제는 프로세스가 필요로 하는 총 메모리 크기가 페이지 크기의 정확한 배수가 아닐 때 나타난다. 예를 들어, 페이지 크기가 4KB이고, 프로세스의 크기가 10KB라면, 이 프로세스를 수용하기 위해서는 세 개의 페이지(12KB)가 필요하다. 그러나 실제로 프로세스는 10KB만 사용하므로, 마지막 페이지 내부의 2KB 공간은 할당은 되었지만 사용되지 않은 채로 남게 된다. 이렇게 페이지 내부에서 낭비되는 공간이 내부 단편화이다.

내부 단편화의 정도는 페이지 크기에 직접적으로 영향을 받는다. 일반적으로 페이지 크기가 클수록 평균적인 내부 단편화의 크기도 커지는 경향이 있다[6]. 반대로 페이지 크기를 줄이면 내부 단편화는 평균적으로 감소하지만, 그 대신 하나의 프로세스에 필요한 페이지 수가 증가하여 페이지 테이블의 크기가 커지고, 페이지 폴트 발생 빈도가 높아질 수 있다. 따라서 시스템은 이러한 트레이드오프를 고려하여 적절한 페이지 크기를 결정한다.

내부 단편화는 세그멘테이션 기법에서 발생하는 외부 단편화와 대비되는 개념이다. 외부 단편화는 할당 가능한 총 메모리 공간은 충분하지만, 그 공간들이 작고 분산되어 있어 큰 연속 공간을 할당하지 못하는 문제인 반면, 내부 단편화는 이미 할당된 공간 내부의 낭비를 의미한다. 페이징 기법은 외부 단편화 문제는 근본적으로 해결하지만, 대신 내부 단편화 문제를 안게 된다.

페이지 폴트(Page Fault)는 프로세스가 접근하려는 논리 주소에 해당하는 페이지가 현재 주기억장치(물리 메모리)에 로드되어 있지 않을 때 발생하는 예외 상황이다. 이는 가상 메모리 시스템, 특히 요구 페이징 환경에서 핵심적인 메커니즘으로 작동한다. 운영체제의 메모리 관리 장치(MMU)가 페이지 테이블을 조회할 때, 해당 페이지 항목의 유효 비트가 '무효'로 표시되어 있거나 페이지가 존재하지 않음을 감지하면 페이지 폴트 트랩을 발생시킨다.

페이지 폴트가 발생하면 운영체제의 페이지 폴트 핸들러가 호출되어 다음과 같은 일련의 과정을 처리한다. 먼저, 요청된 가상 주소의 접근이 유효한지(예: 해당 주소가 프로세스의 주소 공간 내에 있는지)를 확인한다. 유효하지 않은 접근이라면 프로세스에 세그멘테이션 폴트(일반적으로 접근 위반)를 알리고 종종 프로세스를 강제 종료시킨다. 접근이 유효하다면, 운영체제는 필요한 페이지를 보조기억장치(예: HDD나 SSD)에서 빈 물리 메모리 프레임을 찾아 로드한다. 이때 사용 가능한 프레임이 없다면 페이지 교체 알고리즘(예: LRU)을 통해 희생될 페이지를 선택하여 디스크로 내보내고, 그 프레임에 새로운 페이지를 로드한다. 페이지 테이블을 갱신한 후, 중단되었던 프로세스의 명령어를 재실행한다.

페이지 폴트는 시스템 성능에 직접적인 영향을 미친다. 페이지 폴트 처리에는 디스크 입출력이 수반되므로, 그 지연 시간은 메모리 접근 시간에 비해 수천 배에서 수만 배까지 길다. 따라서 빈번한 페이지 폴트는 시스템의 전반적인 성능을 심각하게 저하시키는 스레싱(Thrashing) 현상을 초래할 수 있다. 성능 최적화를 위해 TLB(변환 색인 버퍼)나 페이지 프리페칭 기법이 사용되며, 페이지 폴트율을 모니터링하고 관리하는 것은 운영체제의 중요한 임무 중 하나이다.

페이지 교체 알고리즘은 주기억장치에 남은 프레임이 없을 때, 어떤 페이지를 보조기억장치로 내보낼지 결정하는 규칙이다. 이 알고리즘의 선택은 페이지 폴트 발생 빈도와 시스템 전체 성능에 직접적인 영향을 미친다. 이상적인 교체는 앞으로 가장 오랫동안 사용되지 않을 페이지를 선택하는 것이지만, 미래의 접근을 예측하는 것은 불가능하기 때문에 다양한 근사 알고리즘이 개발되었다.

주요 페이지 교체 알고리즘은 다음과 같다.

이러한 알고리즘들은 각각 장단점을 가지며, 시스템의 요구 사항과 하드웨어 지원에 따라 선택된다. 예를 들어, 클럭 알고리즘은 추가 하드웨어 비용이 적으면서도 LRU에 근접한 성능을 내어 많은 현대 운영체제에서 채택되고 있다. 알고리즘의 성능 평가는 일반적으로 주어진 페이지 참조 열에 대해 발생하는 페이지 폴트 횟수를 비교하는 방식으로 이루어진다.

워킹셋 모델은 프로세스가 짧은 시간 동안 집중적으로 접근하는 페이지들의 집합인 워킹셋을 유지하여, 페이지 교체를 보다 효율적으로 수행하고 페이지 폴트 발생률을 줄이기 위한 이론적 모델이다. 1968년 피터 데닝이 제안한 이 개념은 지역성 원리에 기반을 두고 있다. 프로세스의 실행은 시간적 지역성과 공간적 지역성을 보이므로, 특정 시간 구간(워킹셋 윈도우) 동안 참조된 페이지들은 가까운 미래에도 다시 참조될 가능성이 높다.

워킹셋 모델의 핵심은 각 프로세스에 대해 현재 워킹셋을 동적으로 식별하고, 이 워킹셋에 속한 페이지들은 물리 메모리(주기억장치)에 유지하는 것이다. 워킹셋에서 벗어난, 즉 일정 시간 동안 참조되지 않은 페이지들은 더 이상 활발히 사용되지 않는다고 판단하여 교체 후보로 간주한다. 이를 구현하기 위해 각 페이지 테이블 항목에는 마지막 참조 시간이나 참조 비트 같은 정보가 기록된다.

이 모델의 주요 목적은 스레싱을 방지하는 것이다. 프로세스에 할당된 물리 프레임의 수가 그 프로세스의 워킹셋 크기보다 작으면 페이지 폴트가 빈번히 발생하여 스레싱이 일어난다. 따라서 메모리 관리자는 각 프로세스의 워킹셋 크기를 추정하여 최소한 그만큼의 프레임을 할당해주어야 효율적인 실행이 보장된다. 워킹셋 모델은 이상적인 이론 모델에 가까우며, 정확한 구현에는 상당한 오버헤드가 따르므로 실제 시스템에서는 이를 근사한 알고리즘(예: 참조 비트를 주기적으로 확인하는 방식)이 더 많이 사용된다.

요구 페이징은 페이징 기법의 발전된 형태로, 프로그램 실행에 필요한 페이지만을 주기억장치에 적재하는 방식을 말한다. 이는 프로그램 전체를 메모리에 미리 올리는 일반적인 페이징과 구분되는 개념이다. 프로그램이 시작될 때는 실행에 필요한 최소한의 페이지만 메모리에 로드하고, 나머지 페이지들은 보조기억장치에 그대로 둔다. 이후 프로그램 실행 중 특정 페이지에 대한 접근 요청이 발생했을 때, 즉 '요구'가 있을 때 비로소 해당 페이지를 메모리로 불러온다. 이 방식은 가상 메모리 시스템의 핵심 구현 기법 중 하나이다.

요구 페이징의 동작 과정은 다음과 같다. CPU가 접근하려는 논리 주소가 속한 페이지가 현재 메모리에 존재하지 않으면, 이를 페이지 폴트라고 한다. 페이지 폴트가 발생하면 운영체제가 개입한다. 운영체제는 먼저 요청된 페이지의 위치를 보조기억장치에서 찾고, 메모리에 빈 프레임이 있는지 확인한다. 빈 프레임이 없으면 페이지 교체 알고리즘을 통해 희생될 페이지 하나를 선택하여 보조기억장치로 내보낸다. 그 후, 필요한 페이지를 빈 프레임에 적재하고, 해당 프로세스의 페이지 테이블을 갱신한다. 마지막으로, 중단되었던 프로세스의 명령을 재실행한다.

요구 페이징은 시스템의 효율성을 크게 높인다. 프로그램 전체를 로드할 필요가 없으므로 메모리 공간을 절약할 수 있고, 프로그램 시작 시간이 단축된다. 또한 실제 물리 메모리 크기보다 훨씬 큰 가상 주소 공간을 프로그램에 제공할 수 있다. 그러나 반복적인 페이지 폴트 처리로 인한 오버헤드가 주요 단점이다. 페이지 폴트 발생 빈도가 지나치게 높아지면 시스템 성능이 급격히 저하되는 스레싱 현상이 발생할 수 있다. 이를 완화하기 위해 워킹셋 모델이나 페이지 프리페이징 같은 보조 기법이 함께 사용되기도 한다.

계층적 페이징은 매우 큰 가상 주소 공간을 가진 시스템에서 페이지 테이블 자체가 차지하는 메모리 공간이 과도하게 커지는 문제를 해결하기 위한 방법이다. 전통적인 단일 수준 페이지 테이블은 각 프로세스마다 가상 주소의 모든 페이지에 대한 항목을 포함해야 하므로, 32비트 이상의 주소 체계에서는 테이블 크기가 수 메가바이트에 달해 메모리 낭비가 심각해진다. 계층적 페이징은 이 거대한 테이블을 여러 개의 작은 테이블로 나누어 트리 구조로 구성함으로써, 실제로 사용되는 주소 공간에 대해서만 페이지 테이블 공간을 할당하는 기법이다.

가장 일반적인 형태는 2단계 페이징으로, 논리 주소를 여러 개의 필드로 분할한다. 첫 번째 필드는 바깥쪽 페이지 테이블(페이지 디렉터리)의 인덱스로 사용되고, 두 번째 필드는 안쪽 페이지 테이블의 인덱스로, 마지막 필드는 페이지 내의 변위(오프셋)로 사용된다. 주소 변환 시, 상위 테이블의 항목이 하위 테이블의 물리적 주소를 가리키고, 최종적으로 하위 테이블의 항목이 실제 물리 메모리의 프레임 주소를 제공한다. 이를 통해 사용되지 않는 주소 공간에 대응하는 안쪽 페이지 테이블은 아예 생성하지 않을 수 있어, 페이지 테이블의 전체적인 메모리 사용량을 크게 줄일 수 있다.

계층을 더 늘린 3단계 또는 4단계 페이징은 64비트 시스템에서 필수적으로 사용된다. x86-64 아키텍처의 경우 4단계 페이징(페이지 맵 레벨 4, 페이지 디렉터리 포인터 테이블, 페이지 디렉터리, 페이지 테이블)을 표준으로 채택하고 있다[10]. 계층이 증가하면 주소 변환에 필요한 메모리 접근 횟수가 늘어나는 단점이 있지만, TLB의 효율적인 캐싱과 결합되어 이 오버헤드는 대부분 상쇄된다. 이 방식은 현대 운영체제가 방대한 가상 주소 공간을 효율적으로 관리할 수 있는 근간을 제공한다.