[전산기조직] 메모리 계층 구조(Memory Hierarchy)

5.1 Introduction

책꽂이에서 매번 책을 찾아 읽는것보다는, 많이 읽는 책을 책상 위에 두면 시간을 절약할 수 있다. 우리가 필요한 정보는 모든 책에 균등하게 분포되어있지 않기 때문이다. 프로그램 또한, 필요한 코드와 데이터가 균등하게 분포되어 있지 않다. 비슷한 방법으로, 프로그램에게 우리의 메모리가 더 빨라진듯한 환상을 느끼게 해줄 수 있다. 하지만, 빠르면서 큰 메모리는 존재할 수 없다. 책꽂이를 책상위에 얹을수는 없기 때문이다.

프로그램의 실행은 지역성의 원리(principle of locality)를 따른다. 프로그램은 시간적/공간적으로 이미 참조한 데이터와 가까운 데이터를 다시 참조할 것이라는 의미이다. 구체적으로 설명하자면, 지역성에는 두 가지 종류가 있다.

• 시간적 지역성(Temporal locality): 한 번 참조된 데이터는 조만간 다시 참조될 가능성이 높다.
• 공간적 지역성(Spatial locality): 어떤 주소공간이 참조되면, 그 주변 주소공간도 곧 참조될 가능성이 높다.

프로그램들이 대개 반복문이나 데이터 구조들을 포함하여 작성된다. 그리고, 인스트럭션은 순차적으로 실행되기에, 지역성의 원리는 현실에서도 높은 빈도로 관찰된다.

지역성의 원리를 이용하기 위해, 컴퓨터의 메모리는 계층적으로 구현된다. 메모리 계층(Memory hierarchy)은 서로 다른 크기와 속도의 메모리들로 구성된다. 빠른 메모리일수록 비트당 가격이 비싸고, 그래서 크기도 작다.

우리는 작지만 프로세서와 가깝고 빠른 위 계층과 그렇지 않은 아래 계층으로 메모리를 추상화할 것이다. 여기서 메모리에 저장되는 최소 단위의 정보를 블럭(block, or line)이라고 부른다.

processor가 찾으려는 데이터가 위 계층에 있으면 히트(hit), 아니면 미스(miss)됐다고 표현한다. 메모리 접근 중 히트 비율(hit rate)는 메모리 계층의 퍼포먼스 척도로 사용된다. 또 다른 퍼포먼스의 척도로는 히트 타임(hit time)이 있다. 히트 타임은 데이터 접근이 히트인지 미스인지를 결정하기 까지 걸리는 시간이다. 미스 페널티(Miss penalty)는 윗 계층의 블럭을 대응하는 아래 계층의 블럭으로 교체하고, 프로세서에 이 블럭을 가져다주기까지의 시간이다.

5.2 Memory Technologies

오늘날의 메모리 계층구조를 구현하는 네 가지 핵심 기술에 대해 알아보자. 첫째로, 메인 메모리의 구현에 쓰이는 DRAM과, 둘째로, 프로세서(캐시)에 가까운 계층에서 사용되는 SRAM이 있다. DRAM은 비트 당 가격이 SRAM보다 저렴하지만, 느리다. 가격이 차이나는 이유는, DRAM이 같은 비트를 저장하는데에 특히 더 적은 양의 면적, 즉, 더 적은 양의 실리콘을 사용하기 때문이다. 속도에서 차이가 나는 이유는 부록 B를 참고하라. 세번째 기술은 플래시 메모리(flash memory)이다. 플래시 메모리는 비휘발성으로, 모바일 기기의 2차 기억장치(secondary memory)로 사용된다. 네 번째로, 가장 크고 느린 메모리인 자기 디스크(magnetic disk)이다.

SRAM

SRAM은 보통 읽기와 쓰기를 모두 지원하는 하나의 접근 포트를 갖는다. SRAM은 어떤 데이터에 접근하든 동일한 접근 시간을 가진다.(읽기와 쓰기 시간은 다르다.) SRAM은 새로고침(refresh)이 필요없어서, 접근 시간이 사이클 시간과 거의 동일하다. 보통 비트당 6~8개의 트랜지스터를 가지며, 준비상태에서도 최소한의 전력만으로 충전이 유지된다. 과거에는 여러 캐시들이 별도의 SRAM 칩으로 구분되었으나, 이른바 무어의 법칙 덕에 프로세서 칩 하나로 통합되었다.

DRAM

SRAM에서 전원이 공급되는 한 데이터 값을 무한정 유지할 수 있다. 반면, DRAM은 저장된 값이 축전기(capacitor)의 전하로 보관된다. 비트 당 6~8개의 트랜지스터를 요구한 SRAM과 달리, DRAM은 비트 당 하나의 트랜지스터가 읽기와 쓰기를 모두 가능케 한다. 그래서 SRAM보다 높은 밀도와 저렴한 가격을 갖는다. DRAM은 축전기에 전하를 보존하기 때문에, 무한정 저장할 수 없다. 주기적으로 새로고침(refresh)해주어야 하며, 그것이 이 RAM의 이름에 “Dynamic”이 붙은 이유이다. 그 반대의 이유로 SRAM에는 “Static”이라는 이름이 붙었다.

새로고침하는 방법은 간단하다. 값을 읽고, 그대로 다시 쓰기 하면 된다. 몇 밀리초안에 끝난다. 만약 모튼 비트를 DRAM에서 각각 읽고 다시 써야 한다면, DRAM을 끊임없이 고치느라 막상 데이터에 접근할 시간이 부족했을지도 모른다. 하지만, DRAM은 2단계의 디코딩 구조를 사용하므로, 하나의 행(동일 워드 라인 공유)을 한꺼번에 읽고 쓸수 있다.

행 구조는 새로 고침뿐 아니라 성능에도 도움을 준다. 성능 향상을 위해, DRAM은 자주 사용되는 행을 버퍼에 저장해준다. 버퍼는 SRAM처럼 작동하며, 다른 행에 접근하기 전까지 해당 버퍼 내의 임의의 비트에 접근하게 해준다.

성능향상을 위해 클락이 추가된 DRAM을 Synchonronous DRAM 또는 SDRAM이라고 부른다. 이를 통해 메모리와 프로세서의 동기화에 드는 시간을 제거할 수 있다. 또한, 클록은 연속적인 비트들을 버스트(burst) 방식으로 전송한다. 가장 빠른 형태는 DDR SDRAM(Double Data Rate SDRAM)이며, 클록의 상승 엣지와 하강 엣지에서 모두 데이터를 전송한다. 두배의 대역폭이 되는것이다.

Flash Memory

플래시 메모리는 EEPROM(Electrically Erasable Programmable Read-Only Memory)의 일종이다. 디스크나 DRAM과는 달리, 이 종류의 메모리는 쓰기 작업에 의해 마모(wear out)될 수 있다. 그래서, 메모리에 포함된 컨트롤러가 쓰기 작업을 덜 마모된 블럭으로 분산 시키는 웨어 레벨링(wear leveling) 기술을 이용한다.

Disk Memory

자기 디스크는 여러 개의 원판으로 구성되어, 분당 5,400~15,000번 회전한다. 움직이는 암(arm)에 달린 읽기-쓰기 헤드(read-write head)는 표면 바로 위에 위치한다. 디스크 표면은 트랙(track)이라고 불리는 동심원들로 나눠져 있고, 각 트랙은 섹터(sector)로 다시 나뉜다. 섹터의 크기는 512~4096바이트이다.

5.3 The Basics of Caches

캐시라는 이름은 프로세서와 메인 메모리 사이의 추가 계층을 표현하기 위한 단어로 주로 사용된다. 또한, 지역성 측면의 이점을 누리기 위한 부가적인 저장소를 표현하는 단어로 사용된다. 이 챕터에서는 프로세서 요청은 하나의 워드, 하나의 블럭 또한 하나의 워드로 구성된 매우 단순한 캐시를 다룬다. 아래의 그림에서 프로세서가 워드 Xn을 요청하기 전까지는 캐시에 없었으나, 미스가 난 후 워드 Xn은 메모리로부터 캐시로 옮겨졌다.

두 가지 해결해야 할 질문이 있다. 캐시에 원하는 데이터가 있는지 어떻게 알 수 있는가? 있다면, 어떻게 찾을 수 있는가? 모든 워드의 메모리 주소가 모두 캐시의 어느 한 곳으로 정확이 연결된다면, 우리는 곧장 캐시의 워드를 찾아갈 수 있다. 이런 캐시 구조를 direct-mapped 구조라고 부른다. 거의 모든 direct-mapped 캐시는 아래의 방법으로 블럭을 찾는다.

(Block 주소) mod (cache의 블럭 개수)
= 블럭 주소를 cache의 블럭 개수로 나눈 나머지

캐시의 블럭의 개수가 2의 n제곱 형태로 표현되면, 특히 편리하다. 8-블럭 캐시의 경우, mod를 계산하려면 블럭 주소의 맨 아래 3비트만 보면 되기 때문이다.

반대로, 하나의 캐시 공간은 여러개의 메모리 주소와 매칭되므로, 캐시 공간 속 지금 들어있는 데이터가 어떤 메모리 주소와 연결되는지 알 필요가 있다. 그래서 캐시에는 태그(tags)가 필요하다. 태그는 지금 캐시에 있는 워드가 어느 메모리 주소와 매칭되는지 식별한다. 앞서 8-블럭 캐시는 블럭 주소의 맨 아래 3비트를 매칭에 이용했는데, 블럭 주소의 나머지 윗쪽 비트들(32비트 주소에서는 앞쪽 29비트)이 태그가 된다.

현재 캐시에 들어있는 블럭이 유효한지 아닌지를 판단하는 식별자도 필요하다. 그것을 유효 비트(valid bit)라고 한다.

종합하면 캐시 메모리는 아래의 모양처럼 생겼다. 메모리 주소 10110(2)의 데이터를 요청하고 캐시 미스가 발생하여, 인덱스는 110, 태그는 10, 가져온 데이터를 캐시에 저장하고, 유효 비트도 true로 갱신한 모습이다.

MIPS에서 워드는 4바이트의 배수로 정렬된다. 그래서, 캐시 인덱스 계산을 위해 나머지(mod) 연산을 할때, 맨 아래의 2비트는 무시하고, 그 다음 비트들부터 따져 계산해도 문제가 없다. 32비트 주소 체계를 이용하는 MIPS 구조는 아래와 같을 것이다.

캐시블럭은 2^10(=1024)개를 사용했다. 태그는 주소 32비트 중, 맨 아래 2비트와 캐시 인덱스용 10비트를 제외한 20비트의 길이를 갖게 됐다. 여기서는 캐시 블럭 하나당 워드 하나를 저장하고 있어서 데이터는 32비트 안에 저장된다. 캐시 블럭에 여러개의 워드를 저장할 수도 있으며, 이것 역시 2의 m제곱 개의 워드를 저장한다. 그러면, 데이터 영역은 32*m 비트가 필요할 것이고, tag는 10비트보다 m비트 만큼 덜 필요할 것이다.

캐시 블럭의 크기가 커질수록, 공간적 지역성을 더 활용하기에 미스 비율은 낮아진다. 그러나, 캐시 블럭의 크기가 너무 커져도, 전체 캐시 블럭의 수를 줄여서 블럭끼리의 경쟁을 심화하기 때문에, 오히려 미스 비율이 다시 높아진다. 아래 차트에서 4개의 선은 각각 다른 캐시 크기를 의미하고, x 축은 캐시 블럭 크기를 의미한다.

블럭 사이즈를 늘리는 것은 미스 발생 시 패널티를 늘리는 데에도 일조한다. 미스 패널티는 메모리로부터 데이터를 가져오고(fetch), 그것을 캐시에 저장(load)하는 시간이다. 메모리의 구조 자체를 바꾸지 않는 이상, 당연히 블록 사이즈가 커질 수록 캐시에 데이터를 옮겨담는 시간도 늘어나므로, 비효율적이다.

Chapter4에서 배운 파이프라인을 떠올려보자. 데이터 파이프라인에서 배웠던 메모리는 우리가 지금껏 다룬 캐시로 대체된다. 인스트럭션을 로딩할 때 캐시 미스를 핸들링 하는법은 단순하다. 파이프라인에 정지(stall)를 걸고, 캐시 하위 계층인 메모리에서 데이터를 읽어온 후, 캐시에 기록하고 다시 EX 과정으로 보낸다. 파이프라인은 이제 캐시에서 인스트럭션을 가져올 수 있다.

반면, 쓰기는 좀 더 복잡하다. Store 인스트럭션을 실행할 때, 캐시에만 쓰기 작업을 해준다면, 메모리와 캐시의 값이 일관되지 않는 문제가 발생한다. 가장 단순한 방법은 캐시와 메모리에 항상 같이 쓰기 작업을 해주는 것이다. 이 방법을 write-through라고 한다. 그러나, store 인스트럭션을 실행할 때 마다 메모리에도 쓰기 작업을 하는 것은 비효율적이다. 그래서 쓰기 버퍼(write buffer)를 도입한다. 메모리에 값을 쓰기 전에 쓰기 버퍼에 값을 담아두었다가, 차차 메모리에 저장한다.

다른 쓰기 접근으로 write-back 방법이 있다. 이 방법에서는 새로운 데이터는 캐시에만 기록하되, 수정된 블럭임을 dirty bit로 기억한다. 이 수정된 블럭이 다시 다른 블럭으로 대체되는 때에, 메모리에 기록된다. 성능 면에서 뛰어나지만, 구현은 복잡하다. 또, 한 사이클만에 처리되는 write-through에 비해 write-back은 처리하는데 두 사이클이 걸린다.(히트 여부 확인 + 실제로 데이터 저장 2사이클)

캐시미스가 난 경우 write-back의 작동방식이 조금 헷갈린다. 아래와 같다.

1. 캐시에서 읽어야할 데이터가 없는 것을 확인(미스)
2. 메모리에서 캐시로 필요한 값을 로드, 이 때 캐시 블럭에 이미 다른 값이 차있을 수 있음.
3. 만약 다른 값이 차있다면, dirty 여부를 확인하여, dirty 하면 메모리에 다시 이 값을 갱신해야함. 이 때도, 메모리에 즉시 갱신을 하는 것이 아니라 write-back buffer를 둬서 작업을 지연시킬 수 있음.

캐시 미스 상황에서도 두가지 전략이 있다. Write-allocate 전략은메모리에 쓰기 된 데이터를 캐시에도 가져와서, 적절한 곳에 덮어쓴다. No-write-allocate 전략은 메모리에만 데이터를 쓰고, 캐시는 갱신하지 않는다. 이 전략은 어떤 프로그램이 블럭 전체를 0으로 덮는 상황 등 블럭들을 한꺼번에 업데이트 하려는 상황에 유효하다.

5.4 Measuring and Improving Cache Performances

이 챕터에서는 캐시 성능을 측정하고 분석하는 방법을 다룬다. 또, 캐시 성능을 개선하는 두 가지 방법을 다룬다. 첫번째 방법은, 두 가지 메모리 블록이 하나의 캐시 블록을 두고 경합하는 상황을 줄이는 법을 고민한다. 두번째 방법은, 캐시를 다시 여러 계층으로 나누는, 이른바 멀티레벨 캐싱(multilevel caching)을 통해 미스 패널티를 줄이는 법을 고민한다.

CPU 실행 시간은 아래와 같이 계산된다고 앞선 챕터에서 다뤘다.

(CPU 실행시간) = IC(인스트럭션 수) X CPI(인스트럭션 당 요구 사이클) X CC(사이클당 실행시간)

인스트럭션 당 요구 사이클은 memory-stall 사이클을 고려하여 이렇게 표현된다.

(CPU 실행시간) = IC X CC X (이상적일때의 CPI + 캐시 미스로 인한 stall 사이클)

캐시 미스로 인한 stall 사이클은 read-stall 사이클과 write-stall 사이클로 나뉜다. 이 두 사이클은 또 각각 아래와 같이 표현된다.

(Read-stall 사이클) = (프로그램당 읽기 횟수) X (읽기 미스 비율) X (읽기 미스 패널티)
										
(Write-stall 사이클) = (프로그램당 쓰기 횟수) X (쓰기 미스 비율) X (쓰기 미스 패널티) + 쓰기 버퍼 stall

만약, 읽기와 쓰기의 미스패널티가 동일하고, 쓰기 버퍼 stall은 무시할 정도라고 현실적인 가정을 보태어, 아래의 결론을 얻을 수 있다.

(memory-stall 사이클) = (access/program) x 미스 비율 X 미스패널티

여기서, 히트 타임은 캐시 성능에 무관하다고 가능했으나, 사실은 그렇지 않다. 예를 들어, 캐시 사이즈가 커진다면 히트 타임이 늘어날 것이고, 프로세서의 사이클 시간을 늘릴 수 있다.히트 타임과 미스 타임 모두를 고려하기 위해 평균 메모리 접근 시간(AMAT, average memory access time)이라는 개념을 이용한다.

AMAT = 히트 타임 + 미스 비율 X 미스 패널티

우리는 지금까지 direct-mapped 구조 만을 가정했다. 실은 이것은 하나의 메모리 주소가 하나의 캐시 블럭에만 들어가는 극단적인 경우이다. 메모리주소가 캐시 블럭의 모든 곳에 들어갈 수 있는 구조를 fully associative라고 한다. 그리고, 메모리 주소가 n개의 캐시 블럭에 속할 수 있는 구조를 set associative, 특히 n-way set-associative라고 부른다. 이제 메모리 주소가 캐시 블럭에 매핑되는 식을 아래처럼 바꿀수 있다.

(Block 주소) mod (cache의 set 개수)

associativity의 차수를 늘리는 것은 미스 비율을 낮출 수 있지만, 히트 타임을 낮춘다. 아래의 그림을 생각하면 된다. Direct mapped 에서는 히트 여부 판단을 위해 하나의 태그만 확인 하면 되지만, 2-way set associative에서는 2개의 태그를, fully associative에서는 8개 모두의 태그를 확인해야 한다.

Set associative에서 tag들을 비교하는 것은 병렬적으로 일어난다. N-way set associative라면 n개의 태그 비교가 병렬적으로 일어나며, n-to-1 Mux에 의해 데이터가 가져와진다. 아래는 4-way set의 경우를 그림으로 표현한 것이다.

Direct-mapped 에서는 고민할 필요 없었지만, set-associative에서는 미스가 발생하여 데이터를 캐시에 덮어쓸때, 어떤 블럭을 대체될 블럭으로 결정할지도 고민할 수 있다. Direct-mapped에서는 후보 블럭이 1개 뿐이였고, n-way set-associative에서는 n개의 블럭이 후보가 된다. 가장 많이 쓰이는 방식은 LRU(least recently used)이다. n개의 블럭 중 가장 쓰인지 오래된 블럭을 대체한다.

현대의 컴퓨터는 1차 캐시에서 미스가 나면 2차 캐시에서 데이터를 탐색하는 멀티레벨 캐싱을 지원한다. L1, L2 캐시 라고 표현한다. L1 캐시는 히트 타임을 최소화 하는데에 집중하는 반면, L2 캐시는 미스 비율을 줄이는 데에 집중한다. L1 캐시의 미스 패널티는 L2 캐시 덕에 줄어드는 효과를 얻는다. 그래서 L1 캐시는 미스 비율이 높아지더라도, 블럭 사이즈는 작게, associativity는 적게 설정하여 히트 타임을 줄인다. 반면 L2 캐시는 큰 블럭 사이즈와 큰 associativity를 갖는다.

5.5 Dependable Memory Hierarchy

5.6 Virtual Machines

 

5.7 Virtual Memory

앞선 섹션에서, 캐시가 어떻게 최근에 사용된 프로그램의 코드와 데이터에 대한 접근시간을 개선하는지 알아봤다. 비슷하게, 메인 메모리가 2차 저장소(보통 자기 디스크)의 캐시 역할도 해줄 수 있다. 이 기술을 가상 메모리(virtual memory)라고 부른다. 가상메모리는 두 가지 목적이 있다. 먼저, 서로 다른 프로그램들 간의 안전하고 효율적인 메모리 공유를 담당한다. 둘째로, 작고 제한된 메인 메모리에서 불필요한 프로그래밍 조각들을 제거한다.

  

가상메모리와 캐시는 개념은 동일하지만, 서로 다른 역사적 배경으로 인해 용어가 다르다. 가상메모리에서의 캐시블럭은 페이지(page), 캐시 미스는 페이지 폴트(page fault)라고 한다. 가상 메모리에서는 가상 주소가 생성되어, 메인 메모리의 물리주소와 매핑된다. 이 과정을 주소 매핑(address mapping), 혹은 주소 변환(address translation)이라고 한다. 프로그램의 실행을 위해 로드하는 과정에서, 프로그램이 사용하는 가상주소를 서로다른 물리주소에 매핑하는 것은 재배치(relocation)라고 부른다.

가상 주소는 페이지 넘버(page number)와 페이지 오프셋(page offset)으로 나뉜다. 가상 페이지 넘버는 물리 페이지 넘버보다 비트수가 많아서, 가상 페이지 수가 물리 페이지 수보다 많은 환상을 제공할 수 있다. 페이지 오프셋은 페이지의 크기를 결정한다.

디스크로의 접근 시간은 메인 메모리로의 접근 시간보다 10만 배 오래 걸린다. 이런 엄청난 미스패널티는 아래의 디자인 결정을 하게 만든다.

• 페이지는 너무 긴 접근 시간을 상쇄할 수 있도록, 충분히 커야함. (4KiB~16KiB)
• 페이지 폴트를 줄여야 함. 그래서 페이지들을 메모리에 fully associative하게 배치함.
• 너무 긴 접근 시간을 겪을 바에, 페이지를 배치하는 방법을 알고리즘을 돌려서 계산 비용을 소모하더라도 페이지 폴트율을 줄임.
• 쓰기작업이 너무 오래걸리기 때문에 write-through는 불가능함. write-back만 가능.

고정 크기 블록을 사용하는 페이징(paging)에 대해서 지금 까지 다루었는데, 가변 크기 블록을 사용하는 세그멘테이션(segmentaion)이라는 방식도 있다. 세그멘테이션은 페이징과 달리, 가상 주소 관련 맥락을 사용자 프로그램에도 노출시켜야한다는 물편이 있다. 많은 아키텍쳐들이 주소 공간을 영역을 나누어 사용하는 세그멘트(segment)와는 다른 매커니즘이다.

Fully associative 방식은 캐시 히트 여부를 판단할 때, 검색해야하는 엔트리가 너무 많다는 점이다. 그래서, 메모리를 인덱싱한 테이블을 참고하여, 원하는 페이지를 찾아가도록 하는데, 이 구조를 페이지 테이블(page table)이라고 한다. 페이지 테이블은 페이지 번호로 인덱싱되어, 해당하는 물리 주소를 매핑한다. 이 페이지 테이블이 어디에 있는지를 또 알기 위하여, 페이지 테이블의 시작 위치를 가리키는 레지스터를 페이지 테이블 레지스터(page table register)라고 부른다.

가상 페이지의 유효비트가 꺼져있으면, 페이지 폴트가 발생한다. 그러면, 4장에서 다룬 예외(exception) 처리 매커니즘에 의해, OS가 제어권을 얻는다. OS는 페이지를 디스크로부터 가져와서, 메모리에 배치해야한다. 그런데, 가상 주소 만으로는 디스크에서 페이지가 어디 있는지 알 수 없다.

메모리에 있는 페이지는 언제 교체될지 알 수 없다. 그래서, OS는 프로세스를 생성할 때, 해당 프로세스의 모든 페이지에 대해 디스크에 공간을 만든다. 이 공간을 스왑 공간(swap space)이라고 한다. 각 가상 페이지가 디스크의 어디에 있는지를 기록하는 데이터 구조도 만든다. 좀 전, 페이지 테이블은 페이지 번호를 인덱스로, 해당하는 물리 주소를 저장한다고 했는데, 메모리 물리 주소를 저장한다고 했는데, 디스크의 주소 또한 저장할 수 있다.

페이지 폴트가 발생했을때, 메인 메모리의 어떤 페이지를 교체할지 선택해야 한다. 이 때, LRU(Least Recently Used)방식을 주로 사용하며, 교체된 페이지는 디스크의 스왑공간에 기록된다.

페이지 테이블 자체도 메모리에 저장되므로, 저장공간을 줄이는 것이 좋다. 32bit 가상주소, 4KiB(2^12비트)의 페이지의 아키텍쳐에서, 2^20 개의 페이지 번호가 등장한다. 페이지 테이블 엔트리 하나당 4 바이트라면 페이지 테이블은 2^24비트, 4MiB 나 차지한다.

이 저장공간을 줄이기 위해 첫번째로, 리미트 레지스터(limit register)를 사용한다. 리미트 레지스터는 특정 프로세스의 페이지 테이블 크기를 제한하여, 실제로 프로세스가 사용하는 페이지의 수 만큼만 페이지 테이블을 만들도록 제한한다. 보통 프로그래밍 언어는 스택/힙 양방향으로 데이터를 저장하므로, 두 개의 페이지 테이블과 두 개의 리미트 레지스터가 필요하다.

두번째 방법은 인버티드 페이지 테이블(inverted page table)을 이용하는 것이다. 가상 페이지 수는 너무 많이 때문에 페이지 테이블의 엔트리 수를 물리 페이지 수에 맞추는 것이다. 가상 페이지 번호를 인덱스로 물리 주소를 저장한 페이지 테이블과 달리, 물리 주소에 저장된 페이지를 인덱스로 가상 페이지 번호를 저장한다.

또, 페이지 테이블 자체를 다단계(multi-level)로 구성할 수 있다. 페이지 테이블 중에서도 쪼개서, 필요한 테이블만 메모리에 올려두는 것이다. 그 말인 즉슨, 페이지 테이블 자체도 페이징한다는 것이다.

페이지 테이블이 메모리에 저장되어 있기 때문에, 프로그램의 메모리 접근은 페이지 테이블로부터 물리 주소를 얻는데에 한 번, 실제로 그 주소에서 데이터를 얻는데 한 번, 총 두번의 접근이 필요하다. 그래서 페이지 테이블의 내용을 다시 캐싱한다. 이 캐시를 TLB(translation-lookaside buffer)라고 한다.

모든 참조에서 페이지 테이블보다 TLB에 먼저 접근하게 된다. 읽기 작업에서 TLB 히트가 발생하면 참조(ref) 비트를 켜고, 쓰기 작업에서 히트가 발생하면 더티(dirty) 비트도 켠다. 만약 TLB 미스가 발생하면 단순 TLB 미스인지, 페이지 폴트인지 구분해야 한다. 단순 TLB 미스라면 페이지 테이블을 참조하여, TLB를 갱신하고, 페이지 폴트라면 OS의 예외처리에 맡긴다.