운영체제 - 9장 메인 메모리

9장 주제

• 논리 주소와 물리 주소의 차이점과 주소를 변환할 때 MMU(메모리 관리 장치의 역할을 설명한다.
• 메모리를 연속적으로 할당하기 위해 최초, 최적 및 최악 접합 전략을 적용한다.
• 내부 및 외부 단편화의 차이점을 설명한다.
• TLB (translation look-aside buffer)가 포함된 페이징 시스템에서 논리 주소를 물리 주소로 변환한다.
• 계층적 페이징, 해시 페이징 및 역 페이지 테이블을 설명한다.
• IA-32, X86-64 및 ARMv8 아키텍처의 주소 변환에 관해 설명한다.

배경

프로그램들은 디스크에서 메모리로 가져가지고, 프로세스에 위치되서 실행되어야 한다.

메인 메모리와 레지스터는 CPU가 직접적으로 접근할 수 있는 유일한 저장 공간이다.

메모리들은 주소들 + 읽기 요청이나 주소 + 데이터 그리고 쓰기 요청의 연속만 볼 수 있다.

각 CPU 코어에 내장된 레지스터들은 일반적으로 CPU 클록(clock)의 1 사이클(cycle) 내에 접근이 가능하다.

메인 메 모리의 접근을 완료하기 위해서는 많은 CPU 클록 틱 사이클이 소요되며, 이 경우 CPU가 필요한 데이터가 없어서 명령어를 수행하지 못하고 지연되는(stall) 현상이 발생하게 된다.

캐쉬(cache)는 메인 메모리와 CPU 레지스터 사이에 위치한다.

시스템이 올바르게 동작하기 위해서는 사용자 프로그램으로부터 운영체제 영역을 보호해야 할 뿐만 아니라 사용자 프로그램 사이도 서로 보호해야 한다.

보호

먼저 각각의 프로세스가 독립된 메모리 공간을 가지도록 보장해야 한다.

개별적인 프로세스별 메모리 공간은 서로를 보호하고 병행 실행을 위해 여러 프로세스가 메모리에 적재되게 하는 것이 필수적이다.

개별적인 메모리 공간을 분리하기 위해서 특정 프로세스만 접근할 수 있는 합법적인(legal) 메모리 주소 영역을 설정하고, 프로세스가 합법적인 영역만을 접근하도록 하는 것이 필요하다.

기준(base)과 상한(limit)이라고 불리는 두 개의 레지스터들을 사용하여 이러한 보호 기법을 제공한다.

기준 레지스터는 가장 작은 합법적인 물리 메모리 주소의 값을 저장하고, 상한 레지스터는 주어진 영역의 크기를 저장한다.

예를 들어, 만약 기준 레지스터의 값이 300040이고, 상한 레지스터의 값이 120900이라면 프로그램은 300040에서 420940까지의 모든 주소를 접근할 수 있다.

메모리 공간의 보호는 CPU 하드웨어가 사용자 모드에서 만들어진 모든 주소와 레지스터를 비교함으로써 이루어진다.

사용자 모드에서 수행되는 프로그램이 운영체제의 메모리 공간이나 다른 사용자 프로그램의 메모리 공간에 접근하면 운영체제는 치명적인
오류로 간주하고 트랩(trap)을 발생시킨다.

기준과 상한 레지스터는 여러 가지 특권 명령(special privileged instruction)을 사용하는 운영체제에 의해서만 적재(load)된다.

• 이 레지스터를 OS는 설정할 수 있지만 사용자 프로그램은 변경할 수 없어야 한다.

주소의 할당

전통적으로 메모리 주소 공간에서 명령어와 데이터의 바인딩은 그 바인딩이 이루어지는 시점에 따라 다음과 같이 구분된다.

• 컴파일 시간(compile time) 바인딩: 만일 프로세스가 메모리 내에 들어갈 위치를 컴파일 시간에 미리 알 수 있으면 컴파일러는 절대 코드를 생성할 수 있다. 예를 들면 사용자 프로세스가 $R$번지로부터 시작한다는 것을 미리 알 수 있으면 컴파일러는 번역할 코드를 그 위치에서 시작해 나간다. 그러나 만일 이 위치가 변경되어야 한다면 이 코드는 다시 컴파일되어야 한다.

• 적재 시간(load time) 바인딩: 만일 프로세스가 메모리 내 어디로 올라오게 될지를 컴파일 시점에 알지 못하면 컴파일러는 일단 이진 코드를 재배치 가능 코드로 만들 메인 메모리어야 한다. 이 경우에 심볼과 진짜 번지수와의 바인딩은 프로그램이 메인 메모리로 실제로 적재되는 시간에 이루어지게 된다. 이렇게 만들어진 재배치 가능 코드는 시작 주소가 변경되면 아무 때나 사용자 코드를 다시 적재하기만 하면 된다.

• 실행 시간(execution time) 바인딩: 만약 프로세스가 실행하는 중간에 메모리 내의 한 세그먼트로부터 다른 세그먼트로 옮겨질 수 있다면(스와핑, 페이징) 우리는 바인딩이 실행 시간까지 허용되었다고 이야기한다. (특별한 하드웨어 구조가 필요하다. (가상 메모리))
  

논리 대 물리 주소 공간

CPU가 생성하는 주소를 일반적으로 논리 주소(logical address)라 하며, 반면에 메모리가 취급하게 되는 주소［즉, 메모리 주소 레지스터(MAR)에 주어지는 주소］는 일반적으로 물리 주소(physical address)라 한다.

컴파일 또는 적재 시에 주소를 바인딩하면 논리 주소와 물리 주소가 같다. 그러나 실행 시간 바인딩 기법에서는 논리, 물리 주소가 다르다.

이 때는 논리 주소를 가상 주소라 한다. (이 책에서는) 논리 주소나 가상 주소나 같은 뜻으로 사용한다.

• 논리 주소 공간 : 프로그램에 의해 생성된 모든 논리 주소 집합
• 물리 주소 공간 : 프로그램에 의해 생성된 논리 주소와 일치하는 모든 물리 주소 집합

메모리 관리 장치 : 로그램의 실행 중에는 이와 같은 가상 주소를 물리 주소로 바꾸어줘야 하는데 이 변환(mapping) 작업은 하드웨어 장치

기준 레지스터(base register) 기법을 일반화시킨 기준 레지스터 스키마를 보자.

이제 기준 레지스터를 재배치(relocation) 레지스터라고 부른다.

재배치 레지스터 속에 들어있는 값은 주소가 메모리로 보내질 때마다 그 모든 주소에 더해진다.

예를 들어, 재배치 레지스터 값이 14000이라면 프로세스가 346번지에 액세스할 때, 실은 메인 메모리의 14346번지에 액세스하게 된다.

동적 적재

• 프로그램의 모든 부분이 반드시 메모리에 적재 되어야 실행되지는 않는다.

• 동적 적재에서 각 루틴은 실제 호출되기 전까지는 메모리에 올라오지 않고 재배치 가능한 상태로 디스크에서 대기하고 있다.

• 먼저 main 프로그램이 메모리에 올라와 실행된다. 이 루틴이 다른 루틴을 호출하게 되면 호출된 루틴이 이미 메모리에 적재됐는지를 조사한다.

• 만약 적재되어 있지 않다면, 재배치 가능 연결 적재기가 불려 요구된 루틴을 메모리로 가져오고, 이러한 변화를 테이블에 기록해 둔다. 그 후 CPU 제어는 중단되었던 루틴으로 보내진다.

• 동적 적재의 장점은 루틴이 필요한 경우에만 적재된다는 것이다. 이러한 구조는 오류 처리 루틴과 같이 아주 간혹 발생하면서도 실행할 코드가 많은 경우에 특히 유용하다.

• 동적 적재는 운영체제로부터 특별한 지원이 필요없다.

  • 사용자 자신이 프로그램의 설계를 책임져야 한다.

  • 운영체제는 동적 적재를 구현하는 라이브러리 루틴을 제공해 줄 수는 있다.

동적 연결 및 공유 라이브러리

• 동적 연결 라이브러리(DLL) : 사용자 프로그램이 실행될 때, 사용자 프로그램에 연결되는 시스템 라이브러리이다.

• 정적 연결 : 정적 연결만 지원하는 시스템에서는 라이브러리가 이 프로그램의 이진 프로그램 이미지(image)에 끼어 들어가게 된다.

• 동적 연결 : 연결이 실행 시간 때까지 연기된다.

동적 연결은 주로 표준 C 언어 라이브러리와 같은 시스템 라이브러리에 사용된다. 이 기능이 없으면 시스템의 각 프로그램은 실행 가능 이미지에 해당 언어 라이브러리(또는 최소한 프로그램이 참조하는 루틴)의 사본을 포함해야 한다.

이 요구 사항은 실행 가능 이미지의 크기를 증가시킬 뿐만 아니라 메인 메모리를 낭비할 수도 있다.

DLL의 두 번째 장점은 이러한 라이브러리를 여러 프로세스 간에 공유할 수 있어 메인 메모리에 DLL 인스턴스가 하나만 있을 수 있다는 것이다.

이러한 이유로 DLL은 공유 라이브러리라고도 불린다.

동적 적재와는 달리 동적 연결과 공유 라이브러리는 일반적으로 운영체제의 도움이 필요하다.

연속 메모리 할당

메인 메모리는 운영체제와 사용자 프로세스 둘 다 수용해야 한다.

각 영역은 각각 목적에 맞도록 효율적으로 관리되어야 한다.

연속 메모리 할당은 초기 메모리 할당 방법의 하나이다.

메인 메모리는 일반적으로 두 개의 부분으로 나누어진다.

• 하나는 운영체제를 위한 것이고 보통 낮은 메모리 주소 배치하고 인터럽트 벡터를 가진다.
• 사용자 프로세스는 높은 메모리 주소에 배치한다.

일반적으로 여러 사용자 프로세스가 동시에 메모리에 상주하기를 원한다. 따라서 메모리에 적재되기를 기다리는 프로세스에 사용 가능한 메모리를 할당하는 방법을 고려해야 한다.

연속적인 메모리 할당에서 각 프로세스는 다음 프로세스가 적재된 영역과 인접한 하나의 메모리 영역에 적재된다.

논리적으로 연속적인 메모리 내에 있어야 하지만 물리적으로는 그렇지 않을 수도 있다.

메모리 보호

메모리 할당

메모리를 할당하는 가장 간단한 방법 중 하나는 프로세스를 메모리의 가변 크기 파티션에 할당하는 것이다.

각 파티션에는 정확히 하나의 프로세스만 적재될 수 있다.

• 가변 파티션 : 운영체제는 사용 가능한 메모리 부분과 사용 중인 부분을 나타내는 테이블을 유지한다.

• 처음에는 모든 메모리가 사용자 프로세스에 사용 가능하며, 하나의 큰 사용 가능한 메모리 블록인 hole로 간주한다.

위 그림은 이 기법을 보여준다. 처음에는 프로세스 5, 8 및 2를 적재되어 있고 메모리가 완전히 활용 중이다. 프로세스 8이 종료된 후 하나의 연속된 hole이 생긴다. 나중에 프로세스 9가 도착하고 메모리가 할당된다. 그런 프로세스 5가 종료되면 두 개의 연속되지 않은 hole이 생긴다.

• 프로세스가 시스템에 들어오면, 운영체제는 각 프로세스가 메모리를 얼마나 요구하며, 또 사용 가능한 메모리 공간이 어디에 얼마나 있는지를 고려하여 공간을 할당한다.

동적 메모리 할당 문제(dynamic storage allocation problem)

• 일련의 가용 공간-리스트로부터 크기 바이트 블록을 요구하는 것을 어떻게 만족시켜 줄 것이냐를 결정하는 문제

동적 메모리 할당 문제 해결안

• 최초 적합: 첫 번째 사용 가능한 가용 공간을 할당한다.

• 최적 적합: 사용 가능한 공간 중에서 가장 작은 것을 택한다. 리스트가 크기 순으로 되어 있지 않다면 전 리스트를 검색해야만 한다.

• 최악 적합: 가장 큰 가용 공간을 택한다. 이 방식에서 할당해 주고 남게 되는 가용 공간은 충분히 커서 다른 프로세스들을 위하여 유용하게 사용될 수 있다.

  • 최초 적합과 최적 적합이 모두가 시간과 메모리 이용 효율 측면에서 최악 적합보다 좋다.
  • 최초 적합이 일반적으로 가장 빠르다.

단편화

프로세스들이 메모리에 적재되고 제거되는 일이 반복되다 보면, 어떤 가용 공간은 너무 작은 조각이 되어 버린다.

외부 단편화 : 유휴 공간들을 모두 합치면 충분한 공간이 되지만 그것들이 너무 작은 조각들로 여러 곳에 분산되어 있을 때 발생한다.

내부 단편화 : 일반적으로는 메모리를 먼저 아주 작은 공간들로 분할하고 프로세스가 요청하면 할당을 항상 이 분할된 크기의 정수배로만 해주는 것이 보통이다. 이 경우 할당된 공간은 요구된 공간보다 약간 더 클 수 있다. 이들 두 크기 사이의 남는 부분이 내부 단편화이다.

50% 규칙 : 메모리의 전체 크기와 프로세스 크기들은 모두 외부 단편화에 따라 큰 영향을 미칠 수 있다.
예를 들어, 최초 적합의 경우 통계적인 분석을 해보면 N개의 블록이 할당되었을 때 0.5N개의 블록이 단편화 때문에 손실될 수 있다는 것을 알 수 있다.

즉, 메모리의 3분의 1이 쓸 수 없게 될 수 있다는 것이다.

압축(compaction, 조각 모음) : 메모리 모든 내용을 한군데로 몰고 모든 가용 공간을 다른 한군데로 몰아서 큰 블록을 만드는 것

• 조각 모음은 실행중인 코드를 옮길 수 있어야 가능하다.

• I/O를 실행중에 조각모음을 하게 되면 버퍼의 위치가 변경되서 문제가 발생한다. -> 해결책으로는 I/O를 OS 버퍼에서만 수행한다.

• 저장 공간은 fragmentation 문제를 가지고 있다.

페이징

페이징 : 프로세스의 물리 주소 공간이 연속되지 않아도 되는 메모리 관리 기법.

• 페이징은 연속 메모리 할당을 괴롭히는 두 가지 문제인 외부 단편화와 관련 압축의 필요성을 피한다.

기본 방법

• 프로세스의 물리적 주소 공간은 비연속적일 수 있습니다. 즉, 물리적 메모리가 사용 가능할 때마다 프로세스에 할당된다.

  • 이를 통해 외부 단편화를 피할 수 있습니다. 또한 메모리 덩어리 크기의 변동 문제도 피할 수 있다.

• 물리적 메모리를 프레임이라는 고정 크기의 블록으로 나눕니다.

  • 그 크기는 2의 거듭제곱이며, 512 바이트에서 16 메가바이트 사이다.

• 논리적 메모리도 같은 크기의 블록, 즉 페이지로 나눈다.

• 모든 빈 프레임을 추적힌다.

• N 페이지 크기의 프로그램을 실행하려면 N개의 빈 프레임을 찾아 프로그램을 로드해야 한다.

• 논리적 주소를 물리적 주소로 변환하기 위해 페이지 테이블을 설정한다.

• 백업 저장소 역시 페이지로 나누어진다.

• 그러나 여전히 내부 단편화 문제가 있을 수 있다.

CPU에 의해 생성된 주소는 다음으로 나누어진다:

• 페이지 번호 (p) - 물리 메모리의 각 페이지의 기본 주소를 포함하는 페이지 테이블로 사용되는 인덱스다.
• 페이지 오프셋 (d) - 기본 주소와 결합하여 메모리 유닛으로 전송되는 물리적 메모리 주소를 정의한다.

• 주어진 논리 주소 공간은 $2^m$ 페이지 크기는 $2^n$이다.

모든 프로세스는 각자 페이지 테이블을 가지고 있다.

OS는 각 프로세스의 페이지 테이블을 관리해야 한다.

내부 단편화 계산 방법

• 페이지 크기 = 2,048 바이트
• 프로세스 크기 = 72,766 바이트
• 35페이지 + 1,086 바이트
• 내부 단편화 = 2,048 - 1,086 = 962 바이트
• 최악의 경우 단편화 = 1 프레임 - 1 바이트
• 평균적으로 단편화 = 1 / 2 프레임 크기
• 그래서 작은 프레임 크기가 바람직한가? (페이지 테이블 엔트리 증가)
• 하지만 각 페이지 테이블 엔트리를 추적하는 데 메모리가 필요하다
• 일반적으로 페이지 크기는 점점 커지는 추세다.
• Solaris는 8KB와 4MB의 두 가지 페이지 크기를 지원한다. (가장 인기 있는 크기는 4KB와 8KB입니다.)

페이지 테이블에는 프레임 값 이외에도 추가 정보를 저장할 공간이 충분히 있어야 한다.

프레임 테이블 : 프레임 테이블은 각 프 레임당 하나의 항목을 가지고 있으며, 프레임이 비어 있는지, 할당되었는지, 그리고 할당되었다면 어느 프로세스의 어느 페이지에 할당되었는지를 나타낸다.

하드웨어 지원

페이지 테이블들은 메인 메모리에 보관된다.

• 페이지 테이블 기준 레지스터 (page-table base register, PTBR) : 페이지 테이블을 포인트한다.
• 페이지 테이블 길이 레지스터 (page-tabel length register, PTLR) : 페이지 테이블의 크기를 가르킨다.

이 스키마를 사용하면 데이터에 액세스하려면 두 번의 메모리 액세스가 필요하다.

• 한 번은 페이지 테이블
• 다른 한 번은 실제 데이터와 명령어

이 두 번의 메모리 엑세스 문제는 TLB(Translation look-aside buffers)라는 특수한 소형 하드웨어 캐시가 사용된다.
(연관 메모리, associative memory라고 불린다.)

Translation Look-aside Buffers

• 어떤 TLB는 각 항목에 ASIDs (address-space identifiers)를 저장하기도 한다. ASID는 그 TLB 항목이 어느 프로세스에 속한 것인지를 알려주며 그 프로세스의 정보를 보호하기 위해 사용된다.

• ASID 지원이 없으면 새로운 페이지 테이블이 선택될 때마다 다음 실행 프로세스가 잘못 변환하지 않도록 하기 위해서 TLB는 전부 플러시(flush)가 되어야 한다.

  (예를 들어, 새 프로세스가 문맥 교환을 해서 실행을 재개하는 경우)

• 파이프라인 단계 동안 검색을 하기 위해서는 TLB의 크기는 작게 유지할 수밖에 없으며 통상 32개에서 1,024개의 항목을 유지한다.

• 페이지 번호가 TLB에 없으면 (TLB 미스라고 함) 여기서 페이지 테이블에 대한 메모리 참조가 이루어져야 한다. 프레임 번호가 확보되면 이를 사용하여 메모리에 액세스 할 수 있다.

  • 또한 페이지 번호와 프레임 번호를 TLB에 추가하여 다음 참조에서 빠르게 찾을 수 있도록 한다.

    • 만약 TLB가 가득 차면, 기존 항목 중에서 교체될 항목을 선택해야 한다. (LRU, 라운드 로빈, 무작위 등)

    • 몇몇 TLB는 특정 항목들을 TLB에 고정하는데, 이러한 항목들은 TLB에서 제거될 수 없다.

이전에 보았던 것처럼 현재의 CPU는 여러 단계의 TLB를 가지고 있다. 따라서 현대 CPU에서 메모리 접근 시간을 계산하는 것은 위의 예제보다는 훨씬 복잡하다.

예를 들어, Intel Core i7 CPU는 128개의 항목을 가지는 L1 명령어 TLB와 64개의 항목을 가지는 L1 데이터 TLB를 가지고 있다.
L1 에서 미스가 발생한 경우, 512개의 항목을 가지고 있는 L2 TLB를 검색하는 데 6 CPU 사이클이 필요하다.

L2에서 미스가 발생했다는 것은 해당 프레임 주소를 얻기 위하여 CPU가 메모리에 존재하는 페이지 테이블 항목을 검색해야만 한다는 것을 의미하고 이 연산은 수백 사이클이 필요하다. 아니면 운영체제에게 인터럽트를 걸어 운영체제가 처리하도록 해야 한다.

TLB lookup은 instruction pipeline의 일부이기 때문에 성능 손실이 전혀 없다.

---

적중률 : 접근하려는 메모리의 페이지 번호가 TLB에서 발견되는 비율

80% 적중률이란 TLB에서 원하는 페이지 번호를 발견할 횟수가 80%라는 것을 의미한다.

• 만일 TLB에서 페이지 번호를 찾지 못한 경우에는 우선 페이지 테이블에 접근하여 프레임 번호를 얻어내야 한다(10 ns).
• 그리고서 원하는 데이터를 메모리에서 읽어야 하므로(10 ns) 총 20ns의 시간이 소용된다.

실질 메모리 접근 시간 : 두 가지 경우에 대해 적중률에 따른 가중치를 적용한다.

실질 접근 시간 $= 0.80 \times 10 + 0.20 \times 20 = 12 nanoseconds$

이 예에서는 평균 메모리 접근 시간이 20% 정도 시간이 더 걸린다는 것을 알 수 있다(10ns에서 12 ns로).

더 현실적으로 적중률이 99%라면, 메모리 접근시간은 겨우 1% 늘어난다

실질 접근 시간 $= 0.99 \times 10 + 0.01 \times 20 = 10.1 nanoseconds$

보호

메모리 보호 구현은 각 페이지에 붙어있는 보호 비트에 의해 구현된다.

각 비트는 이 페이지가 읽고, 쓰기 또는 읽기 전용임을 각각 정의할 수 있다.

페이지 테이블의 각 엔트리에는 유효/무효(valid/invalid)라는 하나의 비트가 더 있다.

• 유효(valid) : 이 비트는 관련된 페이지가 프로세스의 합법적인 페이지임을 나타낸다.

• 무효(invalid) : 이 비트는 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다.

• PTLR을 사용하면 된다.

이러한 검사에서 오류가 나타나면 트랩을 발생시킨다.

• 만약 14비트의 주소 공간을 사용한다면 위의 그림처럼 페이지 크기가 2k인 8개의 페이지 할당이 가능하다.

• 주어진 프로그램은 0에서 10,468의 주소만 사용하는 경우라면 (즉, 5개 페이지만 사용), 페이지 5번을 사용할 수 없음에도 불구하고 그림처럼 valid로 나타나는 오류가 발생할 수 있다.

• 우리는 페이지 5~7번을 "페이징으로 인한 내부 조각"(internal fragmentation of paging)"이라고 한다. PTLR을 사용하면 해결이 가능하다.

공유 페이지

페이징의 장점은 공통의 코드를 공유할 수 있다는 점이다.

공유 코드

• 프로세스 간에 공유된 읽기 전용 코드의 복사본(reentrant) (i.e. 텍스트 편집기, 컴파일러, 공유 라이브러리)

• 시스템에서 프로세스들 사이의 메모리 공유는 4장에서 설명했던 스레드에서의 주소 공간 공유와 유사하다.

• 만약 읽기/쓰기 페이지들이 허용된다면, 프로세스 간의 상호 통신(interprocess communication)에도 유용하다.

프라이버시 코드와 데이터

• 각 프로세스는 코드와 데이터의 별도의 사본을 유지합니다
• 개인 코드와 데이터를 위한 페이지는 논리적 주소 공간의 어디에서나 나타날 수 있습니다.

표준 C 라이브러리 공유 사례

페이지 테이블의 구조

직접적인 방법을 사용하면 페이징을 위한 메모리 구조가 굉장히 크게 될 수 있습니다.

• 현대 컴퓨터에서처럼 32비트 논리 주소 공간을 고려해 보자.

• 페이지 크기는 4 KB(2^12)

• 페이지 테이블은 1백만 개의 항목을 가질 것이다. (2^32 / 2^12) = 2^20

• 각 항목이 4바이트라면, 각 프로세스는 물리적 페이지 테이블 크기로 4MB가 필요하다.

  • 페이지 테이블만을 위한 주소 공간 = 4 * 2^20 = 4MB
    • 4 이것을 주 메모리에 연속적으로 할당하고 싶지는 않을 것이다.

• 간단한 해결책은 페이지 테이블을 더 작은 단위로 나누는 것이다.

  • 계층적 페이징(Hierarchical Paging)
  • 해시된 페이지 테이블(Hashed Page Tables)
  • 역 페이지 테이블(Inverted Page Tables)

계층적 페이징

• 논리 주소 공간을 여러 페이지 테이블로 나눈다.
• 간단한 기법으로는 이중 레벨 페이지 테이블이 있습니다.
• 그 다음에는 페이지 테이블을 페이지 처리합니다.

4 KB의 크기를 가진 32비트 기계의 예를 들어보자

• 이 경우 논리 주소는 20비트짜리 페이지 번호와 12비트 짜리 페이지 오프셋으로 이루어진다.

• 이제는 페이지 테이블도 페이지로 나누어지기 때문에, 페이지 번호는 다시 10비트짜리 페이지 번호와 10비트짜리 페이지 오프셋으로 나누어진다.

즉, 논리 주소는 다음과 같이 된다.

여기서 $P_1$은 바깥 페이지 테이블의 인덱스이고, $P_2$는 안쪽 페이지 테이블의 페이지 내의 오프셋이다.

이 방식에서는 주소 변환이 바깥 페이지 테이블에서 시작하여 안쪽으로 들어오므로 이 방식을 forward-mapped 페이지 테이블이라고도 부른다.

• 64비트 논리 주소 공간을 가진 시스템에서는 2단계 페이징 기법도 적절하지 못하다.

• 페이지 크기가 4 KB라고 가정하자($2^{12}$)

  • 이 경우 페이지 테이블은 $2^{52}$ 항목으로 구성될 것이다.
  • 2단계 페이징 기법을 사용하면 안쪽 페이지 테이블은 1페이지가 되거나 $2^{10}$개의 4B짜리 항목을 가지게 될 것이다.
  • 주소는 다음과 같이 나타내질 것이다.
    
  • 바깥 페이지 테이블은 $2^{42}$ 항목을 가지게 되고 $2^{44}$ 바이트로 구성될 것이다.
  • 그 같은 큰 바깥 테이블을 피하는 방법은 바깥 페이지 테이블을 작게 나누는 것이다.

해시 페이지 테이블

• 주소 공간이 32비트보다 커지면 가상 주소를 해시로 사용하는 해시 페이지 테이블을 많이 쓴다.

• 가상 페이지 번호는 해쉬화되어 페이지 테이블에 들어간다.

  • 해시 페이지 테이블의 각 항목은 연결 리스트를 가지고 있다.

• 각 원소는 세 개의 필드를 가진다:
  (1) 가상 페이지 번호
  (2) 사상되는 페이지 프레임 번호
  (3) 연결 리스트상의 다음 원소 포인터

역 페이지 테이블

스와핑

기본 스와핑

페이징에서의 스와핑

모바일 시스템에서의 스와핑

사례: Intel 32비트와 64비트 구조

IA-32 구조

Intel IA-32 세그먼테이션

Intel IA-32 페이징

페이지 주소 확장

Intel X86-64

사례: ARM 구조