Memory Management 2.

페이징은 메모리 관리기법 중 불연속 할당의 방법의 하나이다.
본 포스팅에서는 페이징 기법의 종류, 구조 및 구현 방법에 대해서 다룬다.

Page Table

페이징은 하나의 프로그램을 구성하는 주소 공간을 같은 크기(4 kB) 여러 단위로 쪼개놓은 형태라서 연속 할당처럼 논리 주소를 Base Register와 Limit Register만으로 간단히 주소 변환할 수 없기 때문에 페이지 테이블(Page Table)을 사용하여 주소를 변환한다.

페이지 테이블은 어떤 페이지가 어떤 프레임에 가야하는지 가리키는 매핑 테이블(Mapping Table)이다. 몇 번 페이지가 어떤 프레임에 대응되는지는 이미 정해져 있기 때문에 페이지 번호만큼 오프셋(Offset)¹하면 바로 물리적 메모리 주소로 변환할 수 있다.

Paging Implementation

연속 할당 방식에서 Relocation(Base) Register와 Limit Register가 주소 변환을 수행하는 역할을 페이징 방식에서는 Page Table Base Register(이하 PTBR)와 Page Table Length Register(이하 PTLR)가 수행한다.

• PTBR: 페이지 테이블의 위치(시작 위치)를 가리킨다.
• PTLR: 페이지 테이블의 크기를 보관한다.

페이지 하나의 크기는 4 kB이다. 따라서 32비트 운영체제를 기준으로 페이지 테이블의 엔트리(Entry)는 1 Mega개가 필요하다. 엔트리의 크기는 4 Byte 이므로 페이지 테이블을 위하여 프로그램 하나당 4 MB 크기 만큼의 공간이 필요하게 된다. 이는 캐시(Cache)에 넣기에는 큰 사이즈이다. 이러한 이유로 페이지 테이블은 캐시 메모리에 비해 넉넉한 공간을 가진 메인 메모리에 상주하게 된다.

• 32비트로 표현 가능한 수: 4 GB (\(2^{32}\) Byte)
• 페이지 크기: 4 kB ( \(2^{12}\) Byte)
• 필요한 엔트리 수: 1M개 ( \(2^{20}\) 개)

페이지 테이블이 메모리에 상주하게 되면서, 페이지 테이블도 메모리에 있고 접근해야 하는 데이터도 메모리에 있다보니 어떤 데이터를 가져오려면 메모리에 2번 액세스해야 하는 문제가 생긴다. 메모리에 최대한 적은 횟수로 접근하면서 원하는 데이터를 가져오기 위하여 TLB(Translation Look-aside Buffer)가 등장한다.

TLB(Translation Look-aside Buffer)

TLB는 메모리 변환을 위해 빈번히 참조되는 일부 Entry를 캐싱하는 캐시 메모리이다. CPU와 메모리 사이에 위치한 고속 Look-up Hardware 캐시로 TLB는 순회가 필요없는 병렬 탐색(Parallel Search)이 가능한 Associative register로 구현된 캐시이기 때문에 빠른 속도로 탐색이 가능하다.

논리적 주소(Logical Address)와 프레임 번호(Frame Number)를 쌍으로 갖는 구조로 되어 있으며 TLB에서 먼저 검색한 뒤 캐시에 없으면 페이지 테이블에서 찾는 방식으로 동작하여 평균 메모리 엑세스 타임을 단축시킨다.

EAT(Effective Access Time)

TLB로 인한 메모리 액세스 타임 단축 효과는 다음과 같이 정리할 수 있다.

• Associative Register Look-up Time: \(ε\) (1보다는 훨씬 작은 값이다.)
• Memory Cycle Time: \(t\)
• Memory Access Count: \(n\)
• TLB Hit Ratio: \(⍺\)

위 식에 나타나 있듯 같이 캐시 Hit를 잘 높이면 그냥 페이지 테이블만 사용한 시스템에 비하여 속도가 향상된다. TLB를 검색했을 때 Hit되면 \(1+ε\)만큼의 시간만 발생하고 Miss나면 \(2+ε\)만큼 시간이 발생하지만 Hit Ratio가 높으면 궁극적으로 \(1+ε\)가 필요한 경우가 \(2+ε\)가 필요한 경우보다 많아지므로 평균적인 액세스 타임이 단축되기 때문이다.

TLB도 컨텍스트 스위치(Context Switch)가 발생하면 여타 레지스터와 같이 Flush된다.

Memory Protection

페이지 테이블에는 특정 페이지에 대한 접근 가능 여부를 표시한 부가 정보가 있다.

Protection bit

어떤 연산에 대한 접근권한이 있느냐를 나타낸다. 예를 들어 프로세스의 코드(Code)･데이터(Data)･스택(Stack) 영역 중 코드 섹션은 변경되면 안되기 때문에 Read만 허용되어야 하고, 데이터나 스택은 중간에 데이터를 쓰고 업데이트할 수 있어야 하므로 Read/Write 권한이 필요하다. Protection bit은 이를 나타낸다.

참고로 프로세스마다 고유의 페이지 테이블이 존재하기 때문에 애초에 다른 프로세스가 페이지 테이블에 접근할 수 없다. 따라서 다른 프로세스가 접근하지 못하게 막을 필요가 없다. Protection bit이라는 네이밍으로 이와 같은 접근을 막는 것으로 혼동할 수 있는데 아니라는 점에 유의할 필요가 있다.

Valid-Invalid bit

실제 사용되는 페이지인지 사용되지 않는 페이지인지를 나타내는 정보이다. 페이지 테이블 엔트리는 모든 논리적 주소 범위를 커버해야 하기 때문에 사용하지 않는 페이지에 대한 주소일지라도 엔트리는 모두 생성되어야만 한다. 이 때 실제 사용하는 페이지와 사용되지 않는 페이지를 구분하기 위하여 Valid/Invalid bit을 사용한다.

Valid는 사용되는 페이지로 실제 메모리에 올라와 있다는 것을 나타낸다. Invalid는 사용되지 않는 페이지를 뜻하며 애초에 사용되지 않거나, 또는 Swap area(Backing Store)에 내려가 있음을 나타낸다.

• Valid: 해당 주소의 Frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함. (접근 허용)
• Invalid: 해당 주소의 Frame에 유효한 내용이 없음을 뜻함 (접근 불허)

{% include figure image_path="/assets/images/2022-03-07/1.png" alt=“Valid and invalid bit in a page table.” caption=“Valid and invalid bit in a page table.” %}

Two-level Page Table

앞서 설명한 페이지 테이블을 하나 더(총 2개) 두는 기법을 말한다.
페이지 테이블을 하나만 두는 경우 다음과 같은 이유로 공간적인 낭비가 발생하기 때문에 사용한다.

• 앞서 설명한 것을 복습해보면 페이지의 사이즈가 4 kB이므로 32비트 운영체제를 가정했을 때 필요한 엔트리(Entry)의 숫자는 100만(1M)개이다. 또한 엔트리는 개당 4 Byte이므로 프로세스당 4 MB의 공간이 필요하게 된다. 이는 적은 수치가 아니다.

• 또한 논리적 주소에는 실제론 잘 안 쓰이는 공간도 존재하고 있으나 그렇다고 해서 페이지 테이블에도 해당 부분을 빼고 만들 순 없기 때문에 대응되는 모든 엔트리를 만들어야 하는데 여기서 공간 낭비가 발생한다.

2단계 페이지 테이블에는 바깥 페이지 테이블(Outer-Page Table), 안쪽 페이지 테이블(Page of Page Table)이 있는데 안쪽 페이지 테이블에는 실제로 사용하는 페이지에 해당하는 엔트리만 만들고 바깥 페이지 테이블에는 모든 엔트리(그래봤자 \(2^{10}\)개 이다.)를 만들되, 만들어지지 않은 안쪽 페이지 테이블을 가리키는 포인터는 Null을 가리키게 두어 공간을 절약하게 된다.

Multilevel Paging and Performance

주소 공간이 더 커지면 커지는만큼 메모리 공간이 낭비되므로 효율적인 메모리 관리를 위하여 더 많은 Level depth(3단계, 4단계 등)를 가진 페이지 테이블이 필요해진다. 이러한 경우 다단계 페이지 테이블(Multilevel Page Table)을 사용한다.

다단계 페이지 테이블을 사용하면 공간은 효율적으로 사용할 수 있겠지만 각 단계의 페이지 테이블이 메모리에 존재하게 되므로 논리적 주소를 물리적 주소로 주소 변환하는데 더 많은 횟수의 메모리 접근이 발생하게 된다. 이는 시스템의 오버헤드로 작용하나 TLB를 사용하여 접근시간을 줄일 수 있다.

Inverted Page Table

Inverted Page Table는 역참조 페이지 테이블로 페이지 테이블의 단점인 주소 공간이 허용하는 만큼 엔트리가 생성되어야 하는 문제와 프로세스마다 각각 주소 변환해야 하므로 공간 오버헤드가 큰 문제를 해결하기 위하여 등장한 솔루션 중 하나다.

일반적인 페이지 테이블(Page table)이 페이지(Page) 번호로 페이지 프레임(Page frame)을 매핑시키는 구조라면 Inverted page table은 역으로 물리적 페이지 프레임을 통하여 페이지를 찾아내는 역방향의 구조를 갖고 있다.

즉, Inverted Page Table은 페이지 프레임 하나당 페이지 테이블에 하나의 엔트리(Entry)를 둔 것이다. 각 페이지 테이블 엔트리(Page table entry)는 각각의 물리적 메모리의 페이지 프레임이 담고 있는 내용(Process-ID 이하 pid, Process의 Logical address 이하 p)을 표시한다.

프로세스마다 페이지 테이블을 둘 이유가 없어지기 때문에 시스템에 단 하나의 페이지 테이블만 존재하며 테이블 엔트리 순서는 프로세스 페이지의 논리적 주소 기준으로 구성되지 않고 페이지 프레임 순서대로 구성한다. 즉, 첫 번째 엔트리에는 첫 번째 페이지 프레임의 정보가 있고, 두 번째 페이지에는 두 번째 페이지 프레임의 정보가 있게 된다.

논리적 주소 기준으로 구성되지 않았기 때문에 주소 변환을 할 때 인덱스를 사용하여 빠르게 주소 변환할 수 없으며 페이지 테이블 전체를 탐색(Search pid, p)해야 하며 이로인한 시간적 오버헤드가 발생하는 단점이 있다. Associative Register를 사용(병렬 탐색)하면 이를 극복할 수 있으나 시스템 비용이 증가하게 된다.

Shared Page (Re-entrant Code, Pure Code)

각 프로세스가 실행되는동안 같은 코드를 사용하는 경우, 공유할 수 있는 코드(Shared code)에 대해서는 물리적 메모리에 한 번만 올려서 공유하도록 하는 기법이다. Shared page 기법을 사용하면 프로세스별 주소변환 페이지 테이블은 따로 존재할지언정 공유 코드에 대해서는 같은 페이지 프레임으로 매핑시킨다.

단, 이를 사용하기 위해서는 아래의 두 가지 조건을 만족해야만 한다.

1. Read only 코드일 것. (IPC(Read/Write 가능)와 차이가 발생하는 지점.)
2. Shared code는 동일한 논리적 주소에 위치할 것.

Reference

반효경, “반효경 [운영체제] 19. Memory Management 2”. KOCW. 2014년 4월 29일. video, http://www.kocw.net/home/cview.do?lid=122d1fe7b150f1fb
반효경, “반효경 [운영체제] 20. Memory Management 3”. KOCW. 2014년 5월 2일. video, http://www.kocw.net/home/cview.do?lid=2eb97ae1bd16eb86