가상 메모리

1. 가상 메모리 시스템

가상 메모리는 물리 메모리(실제 메모리)의 크기와 상관없이 메모리를 이용할 수 있도록 지원하는 기술이다. 프로그래머는 가상 메모리 덕분에 물리 메모리의 크기에 구애받지 않고 작업할 수 있는 커다란 공간을 얻게 되는 셈이다. 즉, 가상 메모리(virtual memory)는 크기가 다른 물리 메모리에서 일관되게 프로세스를 실행할 수 있는 기술이다.

1.1 가상 메모리 개념

메모리의 크기는 컴퓨터마다 다른데, 운영체제가 물리 메모리의 크기에만 의존한다면 2GB의 메모리에서 동작하는 프로그램이 1GB의 메모리에서는 동작하지 않을 수 있다. 프로그래머 또한 메모리 크기에 맞는 응용 프로그램만 개발해야하는데, 실제로 메모리 크기를 고려하여 프로그래밍하기란 매우 어렵다. 사용할 수 있는 배열의 개수가 한정되거나 특정 변수에 접근할 수 없다는 제약은 프로그래머에게 큰 장벽이다.

현대 메모리 관리의 가장 큰 특징은 물리 메모리의 크기와 프로세스가 올라갈 메모리의 위치를 신경 쓰지 않고 프로그래밍을 하도록 지원한다는 것이다. 이러한 메모리 시스템을 가상 메모리라고 부른다. 가상 메모리는 물리 메모리의 크기와 상관없이 프로세스에 커다란 메모리 공간을 제공하는 기술이다. 프로세스는 운영체제가 어디에 있는 지, 물리 메모리의 크기가 어느 정도인지 신경쓰지 않고 메모리를 마음대로 사용할 수 있다.

1.2 가상 메모리의 크기와 주소

가상 메모리 시스템의 모든 프로세스는 물리 메모리와 별개로 자신이 메모리의 어느 위치에 있는지 상관없이 0번지부터 시작하는 연속된 메모리 공간을 가진다. 이는 이전에 소개한 논리 주소와 비슷해보이지만 차이점이 있다. 논리 주소는 물리 메모리의 주소 공간에 비례하고, 가상 주소는 물리 메모리 공간이 아닌 가상의 주소 공간을 가진다는 것이다.

위는 가상 메모리의 구성을 나타낸 것이다. 가상 메모리는 크게 프로세스가 바라보는 메모리 영역과 메모리 관리자가 바라보는 메모리 영역으로 나뉜다.

이론적으로 가상 메모리는 무한대의 크기이다. 그러나 실제로 가상 메모리의 최대 크기는 컴퓨터 시스템이 가진 물리 메모리의 최대 크기로 한정되며, 이전에 설명했듯이 cpu의 비트에 따라 결정된다. 32bit의 경우 표현할 수 있는 최대값이 2^32 -1, 즉 16진수로 0xFFFFFFFF 이므로, 4GB가 메모리의 최대 크기이다. 가상 메모리의 최대 크기도 약 4GB이다.

그런데 가상 메모리는 실제로 사용할 수 있는 최대 크기의 제약에도 불구하고 어떻게 이론적으로는 무한대의 크기가 있는 것처럼 구현할 수 있는 것일까??

32bit CPU의 최대 메모리 크기는 4GB이다. 이 시스템에서 각각 4GB 주소 공간을 차지하는 10개의 프로세스를 동시에 실행하려면 운영체제를 포함하여 적어도 40GB의 메모리가 필요하다. 이 경우 가상 메모리 시스템에서는 물리 메모리의 내용 중 일부를 하드디스크의 일부 공간, 즉 스왑 영역으로 옮긴다. 스왑 영역은 하드디스크에 존재하지만 메모리 관리자가 롼지하는 영역으로 메모리의 일부이며, 가상 메모리의 구성 요소 중 하나이다. 메모리 관리자는 물리 메모리의 부족한 부분을 스왑 영역으로 보충한다. 즉, 물리 메모리가 곽 찼을 때 일부 프로세스를 스왑 영역으로 보내고(스왑 아웃), 몇 개의 프로세스가 작업을 마치면 스왑 영역에 있는 프로세스를 메모리로 가져온다(스왑인)

따라서 가상 메모리에서 메모리 관리자가 사용할 수 있는 메모리의 전체 크기는 물리 메모리(실제 메모리)와 스왑 영역을 합한 크기이다.

가상 메모리 시스템에서 메모리 관리자는 물리 메모리와 스왑 영역을 합쳐서 프로세스가 사용하는 가상 주소를 실제 메모리의 물리 주소로 변환하는데, 이러한 작업을 동적 주소 변환(Dynamic Address Translation, DAT)라고 한다. 동적 주소 변환을 거치면 프로세스가 아무 제약 없이 사용자의 데이터를 물리 메모리에 배치할 수 있다. 이 과정에서 메모리 관리자는 물리 메모리를 어떤 방법으로 나눌지, 사용자 프로세스를 어디에 배치할 지, 부족한 물리 메모리를 어떻게 처리할 지 등의 복잡한 문제를 처리한다.

1.3 가상 메모리의 분할 방식

실제 메모리에 있는 물리 주소 0번지는 운영체제 영역이므로 일반 프로세스가 사용할 수 없다. 따라서 가상 메모리 시스템에서는 운영체제를 제외한 나머지 영역을 일정한 크기로 나누어 일반 프로세스에게 할당한다. 메모리 분할 방식은 크게 가변 분할 방식과 고정 분할 방식으로 나뉜다고 했는데, 가상 메모리 시스템도 마찬가지이다. 가상 메모리 시스템에서 가변 분할 방식을 이용한 메모리 관리 기법은 세그먼테이션, 고정분할 방식을 이용한 메모리 관리 기법은 페이징이라고 한다.

이 중 세그먼테이션 기법은 가변 분할 방식의 단점인 외부 단편화 등의 문제 때문에 잘 사용되지 않는다. 또한, 페이징 기법은 페이지 관리에 어려움이 있다. 따라서 가상 메모리 시스템에서는 두 가지 단점을 보완한 세그멘테이션-페이징 혼용 기법을 주로 사용한다.

구분	가상 메모리	물리 메모리
최대 메모리 크기	CPU의 비트 값에 의존	CPU의 비트 값에 의존
주소 지정 방식	가상 주소	절대 주소, 상대 주소
	세그멘테이션	가변 분할 방식
메모리 분할 방식	페이징	고정 분할 방식
	세그멘테이션-페이징 혼용 기법

지금까지 정리한 내용을 테이블로 정리하면 다음과 같다.

1.4 Mapping 테이블의 필요성과 역할

메모리를 관리할 때, 가상 메모리 시스템에서 가상 주소는 실제로 물리 주소나 스왑 영역 중 한 곳에 위치하며 메모리 관리자는 가상 주소와 물리 주소를 일대일 매핑 테이블로 관리한다.

다음은 메모리 매핑 테이블을 나타낸 것으로, 가상 주소가 메모리의 어느 위치에 있는 지 알 수 있다. 가상 주소의 프로세스 A는 물리 메모리의 세그먼트 0에 위치하고, 프로세스 B는 세그먼트 1에 위치한다. 프로세스 D의 경우 물리 메모리가 아니라 스왑 영역에 있다. 프로세스 A의 어떤 값이 필요할 때는 물리 메모리의 세그먼트 0에서 원하는 데이터를 가져오면 된다.

매핑 테이블은 위 그림처럼 물리 메모리가 세그먼테이션으로 분할된 경우 뿐아니라, 페이징으로 분할된 경우에도 똑같은 방식으로 적용된다. 페이징 기법에서 사용하는 매핑 테이블은 페이지 매핑 테이블(page mapping table)또는 페이지 테이블이라고 부르며, 세그먼테이션 기법에서 사용하는 매핑 테이블은 세그먼테이션 매핑 테이블(segmentation mapping table) 또는 세그먼테이션 테이블이라고 부른다.

2. 페이징 기법

고정 분할 방식으로 메모리를 분할하여 관리하는 페이징 기법에서 가상 주소를 물리 주소로 변환하는 방법과 매핑 테이블 관리 방법을 알아보자.

2.1 패이징 기법의 구현

페이징 기법은 고정 분할 방식을 이용한 가상 메모리 관리 기법으로, 물리 주소 공간을 같은 크기로 나누어 사용한다. 아래 그림에서 왼쪽의 가상 주소는 프로세스 입장에서 바라본 메모리 공간으로 항상 0번지부터 시작한다. 가상 주소의 분할된 각 영역은 페이지라고 부르며 첫번째 영역은 페이지 0, 두번째 영역은 페이지 1과 같이 번호를 매겨 관리한다.

물리 메모리의 각 영역은 가상 주소의 페이지와 구분하기 위해 프레임이라고 부른다. 프레임도 페이지와 마찬가지로 번호를 배겨 관리하고, 이 둘의 크기는 같다.

위의 그림은 가상 주소의 각 페이지가 물리 메모리의 어디에 위치하는 지를 나타낸다. 페이지와 프레임은 크기가 같기 때문에 어떤 프레임에도 배치될 수 있다. 이에 대한 맵핑 정보는 페이지 테이블에 담겨져 있다.

페이지 테이블은 하나의 열(column)으로 구성된다. 모든 페이지의 정보를 순서대로 가지고 있기 때문에 위에서부터 차례대로 페이지 0, 페이지 1, 페이지 2... 와 같은 프레임 번호를 가지고 있어 추가 열이 필요없다. 그런데 페이지 테이블에는 숫자만 있는 것이 아니다. 페이지 5는 물리 메모리에 없기 때문에 페이지 테이블에 invalid라고 표시되어있다. invalid는 해당 페이지가 스왑 영역에 있다는 의미이다.

3. 페이징 기법의 주소 변환

3.1 주소 변환 과정

아래의 그림은 페이징 기법에서 가상 주소가 물리 주소로 어떻게 변환되는 지를 보여준다.

메모리는 1Byte기준으로 작성된다. 페이지와 프레임의 각 크기를 10byte로 잡아놓으면, 총 10개의 주소를 저장할 수 있다. 즉, 페이지 0에는 0~9번지의 10개의 주소가 있고, 페이지 1에는 10~19번지의 10개의 주소가 있다. 물리 주소 공간도 마찬가지로 각 프레임에 10개의 주소가 있다.

가상 주소를 물리 주소로 변환하는 과정을 살펴보자, 프로세스가 30번지의 내용을 읽으려고 할 때의 주소 변환 과정은 다음과 같다.

1. 가상 주소 30번지가 어느 페이지에 있는 지 찾는다. 30번지는 페이지 3의 0번째 위치에 있다.
2. 페이지 테이블의 페이지 3으로 가서 해당 페이지가 프레임 1에 있다는 것을 알아낸다.
3. 물리 메모리 프레임 1의 0번째 위치에 접근한다. 이 주소가 가상 주소 30번지의 물리 주소이다.

이번에는 프로세스가 가상 주소 18번지에 어떤 값을 저장하려고 할 떄의 주소 변환 과정을 살펴보자.

1. 가상 주소 18번지가 어느 페이지에 있는 지 찾는다. 18번지는 페이지 1의 8번째 위치에 있다.
2. 페이지 테이블의 페이지 1로 가서 해당 페이지가 프레임 3에 있다는 것을 알아낸다.
3. 프로세스가 저장하려는 값을 프레임 3의 8번 위치에 저장한다.

3.2 정형화된 주소 변환

지금까지 살펴본 주소 변환 과정을 정형화해보자, 페이징 기법에서는 가상 주소를 VA=<P,D>로 표현하는데, 여기서 VA는 가상주소, P는 페이지, D는 페이지의 처음 위치에서 해당 주소까지의 거리(distance)를 말한다. 또는 D를 Offset이라고도 표현한다.

위의 예시에서 가상 주소 30번지를 VA=<P,D>로 표현하면 VA=<3,0>으로 작성할 수 있다. 이는 가상 주소 페이지 3의 0번째 주소라는 것이다. 같은 방법으로 가상 주소 18번지는 VA=<1,8>로 작성하며, 이는 페이지 1의 8번째 주소라는 의미이다. 여기서는 페이지 하나의 크기를 10byte로 규정했기 때문에 정형화된 표기법으로 작성하기 쉽다. 예를 들어, 8번지는 VA=<0,8>, 72번지는 VA=<7,2>, 567번지는 VA=<56,7>이다.

페이징 기법에서의 주소 변환은 가상 주소 VA=<P,D>를 물리 주소 PA=<F,D> 로 변환하는 것이다. PA는 물리 메모리 주소를 가리키는 용어로 '물리 주소' 또는 '실제 주소' 라고도 한다. F는 프레임, D는 프레임의 처음 위치에서 해당 주소까지의 거리를 의미한다. VA=<3,0>이 PA=<1,0>으로 변환되었다는 것은 가상 주소 30번지가 물리 주소 프레임 1의 0번째 위치로 변환되었다는 말이다. 결론적으로 페이징 기법의 주소 변환은 다음과 같이 정의할 수 있다.

VA=<P,D> -> PA=<F,D>

위의 그림은 페이징 기법의 정형화된 주소 변환 과정을 보여준다. VA=<P,D>가 PA=<F,D>로 변환될 때 페이지 테이블을 사용하여 P는 F로 바꾸고, D는 변경없이 그대로 쓴다. D를 변경하지 않은 이유는 페이지와 프레임의 크기를 똑같이 나누었기 때문이다.

페이지 테이블을 이용하면 간단하게 가상 주소를 물리 주소로 변환할 수 있다. 페이지 테이블에서 페이지 번호를 찾아 해당 프레임 번호를 쫒아가면 된다. 페이지 테이블은 페이지 번호, 프레임 번호로 구성되며, 각각의 한 줄은 페이지 테이블 엔트리(Page Table, Entry, PTE)라고 부른다. 다시 말해 페이지 테이블은 페이지 번호, 프레임 번호로 구성된 페이지 테이블 엔트리의 집합이다. 앞에서 설명했듯이 페이징 기법에서 페이지 테이블 엔트리는 프레임 번호만 가진다. 페이지 테이블에 페이지 번호가 순서대로 0부터 정리되어 있기 때문이다. 굳이 페이지 번호를 표시할 필요가 없는 것이다. 페이지 테이블 엔트리가 페이지 번호, 프레임 번호로 구성된 것은 페이지 번호가 순서대로 저장되지 않은 경우이다.

3.3 16bit CPU의 주소 변환 예

한 페이지를 10byte로 나누면 주소 변환 과정은 그리 어렵지 않다. 예를 들면, 가상 주소 30번지는 VA=<3,0>으로 간단하게 만들 수 있다. 그러나 컴퓨터는 2진법을 사용하므로 한 페이지의 크기는 2의 지수로 분할된다. 가령, 실제로 유닉스 계열의 운영체제인 VAX는 한 페이지의 크기가 2^9 byte이다.

가상 주소를 <P,D>로 변환하는 공식
P = 나눗셈(가상 주소 / 한 페이지의 크기)의 몫
D = 나눗셈(가상 주소 / 한 페이지의 크기)의 나머지

가령, 한 페이지의 크기가 10byte인 가상 메모리 시스템에서 가상 주소 32번지의 P는 32/10의 몫인 3, D는 32/10의 나머지는 2이다. 한 페이지의 크기가 512byte인 시스템에서 가상 주소 2049번지의 P는 2049/512 몫인 4, D는 2049/512의 나머지인 1이다. 따라서, <4,1>로 표현된다.

16bit의 CPU의 컴퓨터에서 한 페이지의 크기가 2^10 byte일 때 페이징 시스템의 구성을 살펴보자. 16bit CPU의 컴퓨터에서 한 프로세스가 사용할 수 있는 가상 메모리의 크기는 2^16(65,536 byte)이다. 사용자는 0번지부터 65535번지까지 가상 주소 공간을 사용할 수 있다. 한 페이지의 크기가 2^10(1024) byte이기 때문에 가상 주소로 사용할 수 있는 16bit 중 6bit는 페이지 번호로, 10bit는 페이지의 처음 위치에서 해당 주소까지의 거리로 사용한다. 왜냐하면 2^16 / 2^10 = 2^6으로 6bit말한다. 즉, 페이지 개수는 6bit으로 표현된다는 것이고, 나머지 2^10이 바로, 페이지 거리로 사용된다.

위의 그림은 16bit CPU에서 한 페이지의 크기가 2^10 byte인 페이징 시스템을 나타낸 것이다. CPU가 16bit이므로 가상 주소는 시작 주소 0번지부터 맨 마지막 주소 65535번지까지이다. 한 페이지의 크기가 2^10이므로 전체 페이지의 수는 2^6, 즉 64개이고, 페지는 0번부터 63번까지 존재한다. 한 페이지의 크기가 2^10이므로 1024byte를 가진다. 가상 주소 페이지 0은 0~1023번지, 페이지 1은 1024~2047번지 ... 페이지 63은 64512~65535번지로 구성된다.

페이지와 프레임의 크기는 같기 때문에 물리 주소도 마찬가지로, 2^10으로 나눈다.

위의 그림에서 물리 주소에는 프레임 0~31까지만 있다. 즉, 메모리는 2^15 byte로 구성된 것이다. 이론적으로 16bit CPU는 최대 2^16 byte 메모리를 가질 수 있지만, 위에서는 물리 메모리의 크기를 32KB (2^15)로 도식화했다. 이는 32bit CPU는 최대 4GB의 물리 메모리를 가질 수 있지만, 2GB의 물리 메모리에서도 잘 작동한다. 이처럼 실제 메모리가 최대가 아니더라도 잘 작동한다는 것을 보여주기 위해 일부러 물리 메모리의 크기를 작게 잡아 도식화했다. 이 경우 부족한 물리 메모리는 스왑으로 처리하면 된다. 따라서, 물리 주소의 부족한 부분은 페이징 시스템에서 문제가 되지 않는다.

가성 주소의 각 페이지가 어떤 프레임에 있는지는 페이지 테이블을 보면 알 수 있다. 위의 그림에서 페이지 테이블은 페이지 테이블 엔트리가 0~63으로 총 64개이다. 페이지 테이블의 크기는 물리 주소의 크기가 아니라 프로세스의 크기에 비례한다. 물리 주소의 크기와 상관없이 가상 주소를 많이 사용하면 페이지 테이블의 크기가 늘어나고, 적게 사용하면 페이지 테이블의 크기가 줄어든다. 위의 그림에서는 프로세스가 65535번지까지 다 사용하고 있기 때문에 페이지 테이블의 페이지 테이블 엔트리가 64개이다.

위의 그림에서 프로세스가 980번지에 저장된 데이터를 요청했을 대 가상 주소가 물리 주소로 바뀌는 과정은 다음과 같다.

1. 가상 주소 980번지의 페이지 P와 거리 D를 구한다. P는 0 ( 980 / 1024의 몫)이고, 거리는 980 ( 980 % 1024의 나머지)이므로 VA=<0,980> 이다.
2. 페이지 테이블로 가서 페이지 0이 프레임 2에 저장되어 있다는 것을 확인한다.
3. 물리 메모리의 프레임 2 시작 지점으로부터 980 번지 떨어진 곳에 접근하여 데이터를 가져온다.

같은 방법으로 가상 주소 1364번지를 물리 주소로 변환하면 VA=<1,340>, PA=<3,340>이 되어 프레임 3의 340번지에 있는 데이터를 가져온다.

4. 페이지 테이블 관리

페이지 테이블 관리가 복잡한 이유는 시스템에 여러 개의 프로세스가 존재하고, 프로세스 마다 페이지 테이블이 하나 씩 있기 때문이다.

위 사진에서는 프로세스 1, 2가 하나의 물리 메모리를 사용하고있다. 프로세스는 메모리에 올라와야 실행 가능하므로 모든 프로세스의 일부 페이지가 물리 메모리의 프레임에 올라와 있고, 어떤 페이지가 어떤 프레임에 있는 지 관리하기 위해 프로세스마다 페이지 테이블을 운영 중이다. 프로세스 1의 페이지 0은 프레임 1에, 프로세스 2의 페이지 0은 프레임 3 맵핑된다고 가정할 수 있다. 메모리 관리자는 특정 프로세스가 실행될 때마다 해당 페이지 테이블을 참조하여 가상 주소를 물리 주소로 변환하는 작업을 반복한다.

페이지 테이블은 메모리 관리자가 자주 사용하는 자료 구조이므로 필요시 빨리 접근할 수 있어야 한다. 따라서 페이지 테이블은 물리 메모리 영역 중 운영체제 영역의 일부분에 모아놓는다. 시스템 내에는 여러 개의 프로세스가 존재하고, 프로세스마다 하나의 페이지 테이블이 있기 때문에 전체 페이지 테이블의 크기는 프로세스의 수에 비례해서 커진다. 한 번에 실행하는 프로세스의 수가 많아지면 페이지 테이블의 크기가 같이 커지고, 이에 따라 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어든다.

페이지 테이블 관리의 가장 큰 문제는 페이지 테이블의 크기가 작지 않다는 것이다. 32Bit CPU에 한 페이지가 4KB인 페이징 시스템이 있다고 하자. 이 시스템이 가질 수 있는 물리 메모리의 최대 크기는 4GB이다. 4KB로 페이지를 나눈 이 시스템에서 페이지 테이블의 최대 크기는 약 4MB이다. 즉, 4MB는 페이지 테이블 하나의 크기가 된다. 만약 프로세스가 100개라면 페이지 테이블의 최대 크기는 400MB에 육박한다.

위의 말을 정리해보면, CPU가 32bit 주소 체계를 사용한다면, 주소를 만들 수 있는 경우의 수는 2^32개 이다. 페이징 시스템에서 한 페이지가 4KB라고 한다면, 4KB = 4 x 2^10 = 2^12 Byte이다. 그렇다면, 한 페이지 테이블이 최대로 가질 수 있는 페이지 개수는 2^32 / 2^12 = 2^20이 된다. 그리고 한 페이지 당 주소를 갖는데 4byte크기를 갖는다. 따라서, 2^20 x 2^2 = 4MB가 된다. 즉 앞의 2^20은 페이지 테이블이 내부적으로 가지고 있는 size이고, page table을 저장하기 위한 크기는 4byte라는 것이다. 포인터가 내부적으로 1차원 배열일 때 전체 size가 1024byte이고, 포인터를 저장하기위한 변수의 size는 4byte인 것처럼 여기도 마찬가지 인 것이다.

따라서, 페이지 테이블의 크기를 적정하게 유지하는 것은 페이지 테이블 관리의 핵심이다.

위의 그림은 물리 메모리 내의 페이지 테이블 구조를 나타낸 것이다. 페이지 테이블 영역에 프로세스 별로 페이지 테이블이 배열되어 있는데 프로세스 A의 페이지 테이블은 상단에, 프로세스 B의 페이지 테이블은 하단에 있다. 페이지 테이블의 수가 늘어나거나 페이지 테이블의 크기가 늘어나면 운영체제 영역이 늘어나 그만큼 사용자 영역이 줄어든다. 물리 메모리의 크기가 작을 때는 프로세스만 스왑 영역으로 옮겨지는 것이 아니라, 페이지 테이블의 일부도 스왑 영역으로 옮겨진다.

주의 깊게 살펴볼 점이 하나 더 있는데, 페이지 테이블에 빠르게 접근하기 위해 레지스터가 존재한다는 것이다. 각 프로세스가 메모리에 접근하려고 할 때 메모리 관리자는 페이지 테이블의 위치를 재빨리 파악할 필요가 있다. 그래서 각 페이지 테이블의 시작 주소를 페이지 테이블 기준 레지스터(Page Table Base Register, PTBR)에 보관한다. 페이지 테이블 기준 레지스터(PTBR)는 각 프로세스의 프로세스 제어 블록(PCB)에 저장되는 데이터로 메모리 내에 페이지 테이블의 시작 주소를 가지고 있다.

5. 페이지 테이블 맵핑 방식

시스템 내에는 여러 개의 프로세스가 존재하고, 각 프로세스는 하나의 페이지 테이블을 가지며 페이지 테이블은 운영체제 영역에 있다. 따라서 페이지 테이블의 크기가 너무 커지면 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어든다. 사용할 수 있는 물리 메모리 영역이 적을 경우 프로세스만 스왑 영역으로 옮겨지는 것이 아니라, 페이지 테이블의 일부도 스왑 영역으로 옮겨진다. 따라서 테이블 전체를 메모리에서 관리하느냐, 일부를 스왑 영역에서 관리하느냐에 따라 가상 주소를 물리 주소로 변환하는 방법이 달라지므로 페이지 테이블이 위한 곳에 따른 다양한 페이지 테이블 매핑 방식을 살펴보자.

페잊 테이블 매핑 방식에는 직접 매핑, 연관 매핑, 집합-연관 매핑, 역매핑이 있다.

5.1 직접 매핑(direct mapping)

직접 매핑은 페이지 테이블 전체가 물리 메모리의 운영체제 영역에 존재하는 방식이다. 별다른 부가 작업 없이 바로 주소 변환이 가능하기 때문에 직접 매핑이라고 부른다. 직접 매핑은 모든 페이지 테이블을 물리 메모리에 가지고 있는 가장 단순한 방식이다. 물리 메모리가 충분할 때 사용할 수 있으며, 모든 페이지를 물리 메모리에 가지고 있기 때문에 주소 변환 속도가 빠르다. 직접 매핑 방식의 구조는 다음과 같다.

직접 매핑에서는 페이지 테이블 전체가 물리 메모리에 저장되기 때문에 가상 주소 VA=<P,D>를 물리 주소 PA=<F,D>로 변환하려면 페이지 테이블의 P번째 위치(PTE P)에서 원하는 프레임 값을 얻을 수 있다. 페이지 테이블의 시작 주소는 페이지 테이블 기준 레지스터(PTBR)가 가지고 있으며, 물리 메모리 상 페이지 테이블의 P번째 주소가 시작 주소(PTBR)로 부터 P번째 위치에 존재한다.

5.2 연관 매핑(associative mapping)

연관 매핑은 페이지 테이블 전체를 스왑 영역에서 관리하는 방식이다. 물리 메모리의 여유 공간이 작을 때 사용하는 방식으로 모든 페이지 테이블을 저장장치의 스왑 영역에 저장하고 그 중 일부만 물리 메모리에 가지고 있다. 위에서 보듯이 연관 매핑은 페이지 테이블의 일부만 무작위로 가져온다. 일부 내용만 무작위로 배치하기 때문에 페이지 번호와 프레임 번호 둘 다 표시한다. 따라서, 페이지 테이블의 열은 직접 매핑이 1개, 연관 매핑이 2개가 되는 것이다.

주소 변환 시 직접 매핑은 원하는 프레임 번호를 한 번에 바로 얻을 수 있지만, 연관 매핑은 물리 메모리 내의 페이지 테이블을 다 검색해야한다. 왜냐하면 직접 매핑은 페이지 테이블 번호와 인덱스 번호가 직접 매핑되어 바로 프레임 번호를 찾을 수 있지만, 연관 매핑은 그렇게 저장하지않고, 무작위 순서로 페이지 번호와 프레임 번호를 매핑한 테이블을 저장하기 때문에 어디에 페이지 번호가 있는 지 한 번 순회를 해야한다. 또한, 일부만 물리 메모리에 올려놓고 사용하는 방식이기 때문에 만약 원하는 페이지를 못찾으면 스왑 영역에서 다시 찾아야 하므로 시간을 낭비하게 된다.

정리하자면, 연관 매핑은 전체 페이지 테이블을 스왑 영역에 두고 페이지 테이블 일부를 물리 메모리에 가져오는 방식이다. 그러므로 물리 메모리에는 일부 페이지만 무작위로 저장되어 있고, 그 일부분의 테이블을 변환 색인 버퍼(Translation Look-aside Buffer, TLB) 또는 연관 레지스터(Associate Register)라고 부른다. 변환 색인 버퍼(TLB)는 페이지 번호와 페이지 번호로 구성된 작은 크기의 테이블이다. 연관 매핑 방식의 구조는 다음과 같다.

연관 매핑 방식에서는 물리 메모리에 일부 테이블만 가지고 있기 때문에 작동 방식도 캐시 시스템과 유사하다. 캐시 시스템에서 원하는 데이터가 캐시에 있는 경우 캐시 히트, 없는 경우 캐시 미스라고 하는데, 연관 매핑도 마찬가지이다. 연관 매핑에서는 메모리에 접근하기 위해 먼저 변환 색인 버퍼를 먼저 찾아본다. 원하는 페이지 번호가 변환 색인 버퍼에 있는 경우는 TLB 히트라고 하며, 곧바로 물리 주소로 변환된다. 원하는 페이지 번호가 변환 색인 버퍼에 없는 경우는 TLB 미스라고 하며, 스왑 영역에 저장된 직접 매핑 테이블을 사용하여 프레임 번호로 변환한다.

연관 매핑 방식은 전체 페이지 테이블을 물리 메모리에 보관하지 않아 메모리를 절약할 수 있다는 것이 장점이다. 그러난 TLB 미스가 빈번하게 발생하는 경우 시스템 성능이 떨어지는 단점도 있다. 또한 변환 색인 버퍼는 페이지 테이블의 일부를 무작위로 가지고 있기 때문에 모든 변환 색인 버퍼를 검색한 후에야 원하는 페이지가 메모리에 없다는 것을 알 수 있다. 즉, TLB 미스를 알게되는 시점이 변환 색인 버퍼를 모두 검색하고 난 후이다. 따라서 TBL 미스가 발생하면 주소 변환이 느려진다.

5.3 집합-연관 매핑 (set-associative mapping)

집합-연관 매핑은 연관 매핑의 문제를 개선한 방식이다. 모든 페이지 테이블을 스왕 영역에서 관리하고 일부만 메모리로 가져온다는 것은 연관 매핑과 동일하다. 다만 연관 매핑에서는 물리 메모리에 있는 데이터가 무작위로 올라오기 때문에 원하는 프레임 번호를 얻기 위해 모든 테이블을 검색해야 하는 문제가 있었다. 그러나 집합-연관 매핑에서는 페이지 테이블을 일정한 집합으로 자르고, 자른 덩어리 단위로 물리 메모리에 가져온다.

위의 그림에서 집합-연관 매핑에서는 페이지 테이블을 5개씩 자르고, 이를 관리하는 페이지 테이블을 하나 더 생성했다. 새로 생성한 집합 테이블(set table)에는 일정하게 자른 페이지 테이블이 물리 메모리에 있는지, 스왑 영역에 있는지에 대한 위치 정보를 표시한다. 그림에서 I (Invalid)로 표시된 것은 스왑 양약에 있다는 의미이고, 집합 2에 속한 페이지(페이지 테이블 엔트리 10~14)는 물리 메모리의 180번지에 있다는 의미이다.

연관 매핑과 비교했을 때 이 방식은 집합 테이블을 통해 원하는 페이티 테이블 엔트리가 스왑 영역에 있는 지, 물리 메모리에 있는 지 간단하게 파악할 수 있다. 그러므로 연관 매핑에서처럼 물리 메모리의 모든 페이지 테이블을 검사할 필요가 없어 주소 변환 시간이 단축된다.

즉, 정리하자면 연관 매핑에서 모든 변환 색인 버퍼를 검색한 후에야 TLB 미스가 있다는 사실을 알게되고 스왑 영역에서 프레임을 요구하므로, 전체 시스템의 성능이 떨어지는 단점을 개선한 것이 바로 집합-연관 매핑이다. 일반적으로 컴퓨터를 사용할 때 파일이 많으면 디렉터리를 사용하여 일정한 묶음으로 모아놓는다. 이를 비유해 디렉터리 매핑(directory mapping)이라고도 하는 집합-연관 매핑은 관련있는 테이블을 덩어리로 모아 놓은 형태이다.

집합-연관 매핑 방식에서는 페이지 테이블을 같은 크기의 여러 묶음으로 나누고, 그 묶음의 시작 주소를 가진 디텍터리 테이블을 새로 만들어 관리한다. 전체 페이지 테이블은 연관 매핑과 마찬가지로 스왑 영역에 있으며, 일부 테이블은 묶음 단위로 메모리 옮긴다. 따라서 이 방식에서는 해당 묶음이 현재 메모리에 있는 지, 스왑 영역에 있는지를 표시하는 디엑터리 테이블을 새로 만든다. 디렉터리 테이블을 살펴보면 원하는 테이블 묶음이 어디에 있는 지 알 수 있으므로 전체 테이블을 찾아보지 않아도 TLB 미스를 바로 알 수 있다.

집합-연관 매핑 방식에서는 페이지 테이블이 일정 크기의 묶음으로 나뉘기 때문에 가상 주소를 VA=<P,D>가 아니라, VA=<P1,P2,D>로 바꾸어 표시한다. 여기서 P1은 디렉터리 테이블에서의 위치 정보를 P2는 묶음 내에서의 위치 정보를 나타낸다. 집합-연관 매핑 방식에서는 직접 매핑 방식처럼 한 번에 물리 주소로 변환되는 것이 아니라 두 단계를 거쳐 물리 주소로 변환된다.

가령, 집합-연관 매핑 방식에서 페이지 테이블을 10개씩 한 묶음으로 나누었다고 가정해보자, 주의할 것은 페이지 10개를 한 개의 묶음으로 묶겠다는 것이 아니라, 10개의 페이지 테이블을 한 개의 묶음으로 보겠다는 것이다. 즉, 한 개의 페이지 테이블에 10개의 페이지가 있다면, 10개의 페이지 테이블은 100개의 페이지가 있는 것이다. 0~9번 테이블은 0번 디렉터리에 10~19번 테이블은 1번 디렉터리에 속한다. 이 경우 가상 주소 32번지는 직접 매핑에서는 <3,2>로 변환되지만, 집합-연관 매핑에서는 <0,3,2>로 변환된다. 같은 방법으로 가상 주소 127번지는 직접 매핑에서는 <12,7>로 변환되지만 집합-연관 매핑에서는 <1,2,7>로 변환된다. 또한 1784번지는 집합-연관 매핑에서 <17,8,4>로 변환된다.

결론적으로 집합-연관 매핑 방식은 페이지 주소를 세분화한다. 예를 들어 페이지 번호 3은 0과 3으로 12는 1과 2로 178은 17과 8로 나뉜다. 집합-연관 매핑의 가상 주소 VA=<P1,P2,D>에서 P1은 디렉터리 테이블 번호를, P2는 묶음 페이지 번호를 가리킨다. 여기서 P1은 P2 테이블 덩어리가 메모리 영역에 있는 지, 스왑 영역에 있는 지에 대한 위치 정보를 나타낸다. 이러한 특징 때문에 집합-연관 매핑을 멀티페이지 매핑(multi-page mapping)이라고도 일컫는다.

집힙-연관 매핑 방식의 구조는 위와 같다. 직접 매핑 방식과 마찬가지로 디렉터리 페이지 테이블의 시작 주소는 페이지 테이블 기준 레지스터(PTBR)가 가지고 있다. 프로세스가 특정 주소를 요구하면 VA=<P1,P2,D>로 변환되고, P1을 사용하여 디렉터리 테이블에서 주소를 찾는다. 만약 I(Invalid)라고 적혀있다면 TLB미스가 발생할 것이다. 반대로 원하는 테이블이 물리 메모리에 있으면 묶음 테이블의 시작 주소가 명시되어 있다. 위에서는 묶음 테이블의 시작 주소가 b이다. 따라서 P2를 이용하여 묶음 테이블에서 원하는 프레임 번호를 얻게 된다.

집합-연관 매핑은 직접 매핑과 연관 매핑의 장점을 합한 방식으로 크기가 큰 페이지를 같은 크기의 묶음으로 나누어 관리함으로써 효율적이다. 연관 매핑의 경우 변환 색인 퍼버에 여러 테이블이 섞여 있기 때문에 주소 변환을 위해 변환 색인 버퍼의 모든 테이블을 검색해야 하지만, 집합-연관 매핑에서는 디렉터리 테이블을 이용하여 묶음 테이블 위치를 바로 확인할 수 있다. 연관 매핑은 TLB 미스가 발생할 경우 변환 색인 버퍼 전체를 검색하는 데 시간을 낭비하지만 집합-연관 매핑은 이러한 낭비가 발생하지 않는다. 또한, 집합-연관 매핑은 직접 매핑과 달리 일부 페이지 테이블만 메모리에서 관리하여 물리 메모리를 낭비하지 않는다.

5.4 역매핑(invert mapping)

역매핑은 앞의 세 가지 매핑과 반대로 페이지 테이블을 구성하는 방식이다. 직접 매핑, 연관 매핑, 집합-연관 매핑에서는 페이지 번호를 기준으로 테이블을 구성하지만, 역매핑에서는 물리 메모리의 프레임 번호를 기준으로 테이블을 구성한다. 다시 말해 물리 메모리의 프레임에 어떤 프로세스의 어떤 페이지가 올라와 있는 지를 표시한다.

위 그림에서 직접 매핑의 페이지 0은 프레임 1에 있지만, 역매핑에서는 반대로 프레임 1이 프로세스 1의 페이지 0에 있다. (역매핑에서는 테이블이 프레임을 기준으로 프로세스 아이디(PID)와 페이지 번호로 구성되며, 물리 메모리 상의 프레임 수와 테이블의 열거 수가 같다.)

역매핑의 가장 큰 특징은 프로세스의 수와 상관없이 테이블이 하나만 존재한다는 것이다 다른 방식에서는 프로세스마다 페이지 테이블을 만들지만, 역매핑에서는 물리 메모리를 기준으로 프레임 테이블을 만들기 때문에 전체 시스템에서 테이블의 수가 단 1개이다. 따라서 테이블의 크기가 매우 작다는 것이 장점이다.

역매핑은 테이블 크기가 작지만 프로세스가 가상 메모리에 접근할 때 프로세스 아이디와 페이지 번호를 모두 찾아야 하는 단점이 있다. 가령 프로세스 1의 페이지 10이 메모리에 있는지 확인하려면 <PID 1, page10>을 모든 테이블에서 찾아야만 그 결과를 알 수 있다. 또한, 모든 페이지를 검색한 후에야 해당 페이지가 스왑 영역에 있다는 것을 알게되므로 속도가 아주 느리다.

정리하자면, 지금까지 살펴본 매핑 방식은 가상 주소의 페이지를 기준으로 프레임 번호를 매핑했다. 이러한 방식은 프로세스마다 페이지 테이블이 필요하고 그 크기도 작지 않기 때문에 물리 메모리 공간을 낭비하는 것이 문제다. 역매핑은 이와 달리 메모리의 프레임 번호를 기준으로 테이블을 작성한다. 즉, 물리 메모리가 어떤 프로세스의 어떤 페이지를 가지고 있는지를 테이블 형태로 구성한다. 역매핑 방식의 구조는 다음과 같다.

역매핑 방식에서는 테이블이 <프레임 번호, 프로세스 아이디(PID), 페이지 번호>로 구성되고, 페이지 테이블 행 수는 실제 실제 프레임의 수와 같다. 그러므로 프로세스의 수와 상관없이 항상 일정 크기의 페이지 테이블을 유지하여 테이블의 크기가 매우 작다.

역매핑 방식에서 주소 변환 시 메모리 관리자는 주소 변환을 해야하는 프로세스의 아이디와 페이지 번호가 물리 메모리에 있는 지 역매핑 테이블에서 검색한다. 현재 테이블에 원하는 데이터가 없으면 스왑 영역에서 가져온다. 역매핑은 연관 매핑과 마찬가지로 페이지 테이블을 다 검사한 후에야 저장장치에 접근하기 때문에 검색 시간을 낭비하는 단점이 있다.