[OS/운영체제] 페이징 (Paging) - (1)

페이징 (Paging)

페이징은 프로세스가 차지하는 물리적 메모리 공간이 비연속적이 되도록 허용하는 메모리 관리 기법을 말한다.

페이징은 외부 단편화가 발생하지 않으며, 따라서 별도의 Compaction 과정이 필요하지 않다.

또한 다양한 크기의 메모리 덩어리(Chunk)들을 Backing store에 맞춰야 하는 문제를 해결해 준다. 이 문제는 메인 메모리를 차지한 코드나 데이터가 swap out될 때, 그만한 공간을 Backing store에서 찾아야 하기 때문에 발생한다. Backing store에서도 동일하게 단편화 문제가 발생하지만, 메인 메모리에서보다 접근 속도가 훨씬 느리기 때문에 Compaction을 적용할 수 없다.

이러한 장점들 때문에 현재 대부분의 운영체제에서 다양한 형태로 사용되는 방법이다.

 

Basic Method

페이징을 구현하는 기본적인 방법은 물리적 메모리를 고정된 크기의 프레임(Frame)으로 나누고, 논리적 메모리를 동일한 크기의 페이지(Page)로 나누는 것이다.

프로세스가 실행되면 프로세스의 페이지들은 메모리의 사용가능한 프레임으로 적재된다. Backing store 역시 고정된 크기의 block들로 나누어진다.

페이징을 위한 하드웨어의 지원은 다음 그림과 같다.

Paging Hardware

CPU에 의해 생성된 모든 주소들은 페이지 번호(Page Number, p)와 페이지 간격(Page Offset, d)로 나뉜다. 페이지 번호는 페이지 테이블의 인덱스로써 사용된다. 

Paging model of logical and physical memory

페이지 테이블(Page Table)은 물리적 메모리의 각 페이지의 Base 주소(시작 주소)를 저장하고 있다. 즉 페이지와 대응하는 물리적 메모리의 프레임 주소를 가리킨다. 이 시작 주소를 페이지 간격과 합해 메모리 단위의 물리적 메모리 주소를 정의할 수 있다.

페이지의 크기(프레임의 크기)는 하드웨어에 의해 정의된다. 페이지의 크기는 논리적 주소를 페이지 주소와 페이지 간격으로 바꾸는 것이 수월하도록 보통 2의 제곱 형태로 정해지며, 컴퓨터 구조에 따라 보통 한 페이지 당 512 byte ~ 16MB의 크기를 갖는다.

만약 논리적 주소의 크기가 2^m이고 페이지의 크기가 2^n이라면, 높은 순의 m - n개 비트가 페이지 번호, 나머지 n개의 비트가 페이지 간격이 된다.

Paging Example (32-byte memory, with 4-byte pages)

다음과 같은 예시에서 페이징의 동작 과정을 살펴보자. 논리적 주소는 n = 2, m = 4인 상태이다.

메모리는 32byte, 페이지의 크기는 4byte이므로, 메모리에는 총 8개의 페이지가 존재한다.

논리적 주소 0은 p = 0, d = 0으로 변환되고, 페이지 테이블에서 0번 페이지는 5번 프레임에 대응하므로, 논리적 주소 0에 대한 실제 물리적 메모리 주소는 5 * 4(페이지 크기) + 0(d) = 20이다. 

논리적 주소 11은 이진수로 1011이므로, p = 10(2) = 2, d = 11(2) = 3으로 변환된다. 페이지 테이블에서 2번 페이지는 1번 프레임에 대응하므로, 논리적 주소 11에 대한 실제 물리적 메모리 주소는 1 * 4 + 3 = 7이다.

 

내부 단편화 발생

페이징 기법을 사용할 때, 외부 단편화는 발생하지 않는다. 모든 사용 가능한 프레임은 그것을 필요로 하는 프로세스에게 할당될 수 있기 때문이다. 하지만 내부 단편화는 발생할 수 있다. 프레임은 일정한 크기로 할당되기 때문이다.

만약 프로세스가 메모리를 요구할 때, 마지막 프레임은 정해진 메모리 크기를 모두 할당하지 못할 수도 있다. 만약 페이지 하나의 크기가 2,048byte일 때 프로세스의 크기가 72,776byte라면 이는 35페이지에 1,086byte를 필요로 하게 된다.

하지만 프레임은 고정된 크기로 할당되기 때문에 실제로 할당되는 프레임의 수는 36개이다. 마지막 프레임에는 962byte의 내부 단편화가 발생하게 되는 것이다. 최악의 경우에는 단 1byte 차이 때문에 하나의 프레임을 더 할당해야 할 수도 있다.

그렇다면 페이지의 크기를 작게 만들수록 내부 단편화가 그만큼 덜 발생하지 않을까? 하지만 페이지의 크기가 줄어들수록 총 페이지의 갯수가 그만큼 늘어나고, 이 페이지들을 관리하는 오버헤드 또한 증가하게 된다. 또한 디스크 입출력은 한 번에 옮겨지는 데이터의 양이 많을수록 효율적이기 때문에, (일반적으로 디스크 입출력의 횟수를 줄일수록 효율이 좋다) 오늘날 일반적인 페이지의 크기는 4KB 또는 8KB로 정해졌다.

 

페이징의 가장 중요한 측면은 사용자 관점의 메모리와 실제 메모리를 분명하게 구분하는 것이다. 사용자 프로그램은 메모리를 하나의 단일 공간으로 보지만, 실제로는 메모리 여기저기에 흩어져 있다. 논리적 주소가 물리적 주소로 변환되는 것은 운영체제에 의해 사용자에게는 보여지지 않는다.

Free frames (a) before allocation, (b) after allocation

물리적 메모리를 관리하는 것은 운영체제이기 때문에, 운영체제는 반드시 물리적 메모리가 어떻게 할당되는지에 대한 내용을 알고 있어야 한다. 어떤 프레임이 할당되었고, 어떤 프레임이 사용 가능한지에 대해 말이다. 이러한 정보는 프레임 테이블(Frame Table)이라는 자료구조에 저장된다.

또한 운영체제는 사용자 프로세스가 사용자 공간(user space)에서 동작할 때, 모든 논리적 주소가 대응되는 물리적 주소를 알고 있어야 한다. 사용자가 논리적 주소를 인자로 시스템 콜을 발생시켰을 때 그 주소는 올바른 물리적 주소로 대응되어야 하기 때문이다. 따라서 운영체제는 각 프로세스의 페이지 테이블 복사본을 가지고 있다.

 

Hardware Support

페이지 테이블을 하드웨어적으로 구현하기 위한 방법은 여러가지가 존재한다.

Dedicated Registers

그 중 가장 단순한 방법은 페이지 테이블을 Dedicated Registers의 집합으로 구현하는 것이다. 이 레지스터들은 페이징 주소 변환을 아주 빠르게 효율적으로 처리한다. 

CPU의 Dispatcher는 프로세스를 시작할 때 이 레지스터들을 다른 레지스터들과 마찬가지로 reload한다. 

페이지 테이블의 크기가 작을 때만 효과적이다.

 

 PTBR (Page-Table Base Register)

현대의 컴퓨터들은 페이지 테이블의 크기가 매우 큰 경우도 허용하기 때문에, Dedicated Register를 사용한 방법은 그렇게 효과적이지 않다. 대신, 페이지 테이블을 메인 메모리에 유지하여 PTBR이 페이지 테이블을 가리키도록 할 수 있다.

이러한 접근의 문제는 사용자 메모리에 접근하는 데 걸리는 시간이다.

주소에 접근하기 위한 과정이 많아졌고, 페이지 테이블을 확인하기 위해선 메인 메모리에 존재하는 PTBR의 값을 사용해야 하며, 이 때 메모리 접근을 필요로 하기 때문이다.

 

TLB (Translation Look-aside Buffer)

이 문제에 대한 일반적인 해결책은 TLB라는 Cache의 일종이다.

TLB는 key(또는 tag), value의 두 가지 값을 저장한다. 어떤 항목이 메모리에 제시된다면 그 항목은 모든 key들에 대해 동시에 비교된다. 만약 해당 항목을 찾았다면 그 key값에 상응하는 value값을 반환한다.

Paging HW with TLB

TLB는 적은 수의 페이지 테이블만을 포함하고 있다. CPU에 의해 논리적 주소가 생성될 때, 그 주소의 페이지 번호가 TLB에게 제시된다. 만약 그 페이지 번호가 TLB에서 발견됐다면(TLB Hit) 해당하는 프레임 번호는 즉시 사용가능해지며 메모리에 접근할 수 있다.

하지만 만약 페이지 번호가 TLB에서 발견되지 않았다면, (TLB Miss) 그 페이지 테이블에 대한 메모리 참조가 만들어져야 한다. 그림에서와 같이 페이지 번호에 대응하는 프레임 번호를 TLB에 저장하여, 다음에 해당 페이지를 참조할 때 빠르게 메모리에 접근할 수 있도록 한다.

Hit Ratio : 특정 페이지 번호가 TLB에서 발견될 확률을 의미한다.

Effective Memory-Access Time : (Hit ratio) * (TLB Hit시 접근시간) + (1 - Hit ratio) * (TLB Miss시 접근 시간)

(단, 접근 시간은 TLB 검색 시간을 포함한다)

 

 

 

※ 본 게시글은 『Operating System Concepts』 를 참고하여 작성되었습니다.