[OS] 7. 페이징 (Paging)

페이징 (Paging) : 프로그램과 메모리를 일정한 크기로 나눔

페이징은 프로그램과 메모리를 일정한 크기로 나누는 기법이다. 프로그램이 가상 메모리에서 참조하는 주소를 가상 주소(Virtual address)라고 한다. 가상 메모리가 있다면, 각 프로그램은 자신의 고유한 가상 주소 공간을 가진다. 가상 메모리를 사용할 때는 가상 주소가 그대로 메모리 버스에 실려 물리 주소가 되지만, 가상 메모리를 사용하지 않을 때는 가상 주소가 MMU에 의해 물리 주소로 매핑된다.

가상 주소 공간과 물리 주소 공간은 고정된 크기 단위의 유닛들로 동일하게 나뉜다. 가상 페이지(Virtual Page)는 가상 주소 공간을 나눈 조각으로, 각 페이지는 연속된 주소를 가진다. 페이지 프레임(Page Frame)은 물리 메모리를 나눈 조각이다.

가상 주소 공간과 물리 주소 공간은 고정된 크기 단위의 유닛들로 동일하게 나뉜다. 가상 페이지(Virtual Page)는 가상 주소 공간을 나눈 조각으로, 각 페이지는 연속된 주소를 가진다. 페이지 프레임(Page Frame)은 물리 메모리를 나눈 조각이다.

다음 그림에서는 가상 주소 공간을 64KB, 물리 메모리 공간을 32KB, 유닛 크기는 4KB로 가정하고 있다.

논리 주소(logical address)는 세그먼트(segment)와 오프셋(offset)으로 구성된다. 세그먼트는 고정된 길이와 시작 위치로 구성되며, 오프셋은 세그먼트의 시작 지점에서 실제 주소까지의 거리를 나타낸다. 가상 주소(virtual address)는 32비트의 단일 정수로 표현되며, 물리 주소(physical address)는 물리 메모리에서 각각의 셀(cell)의 주소를 나타낸다. 페이지 프레임은 가상 페이지가 매핑되는 물리 메모리의 일부분이다.

명령어 MOV REG, 0을 수행한다고 가정해보자.

• 이 명령어에서 접근하는 가상 주소 0은 MMU로 전달된다.
• MMU는 해당 가상 주소가 가상 페이지 0에 속한 것임을 확인한다.
• MMU는 가상 페이지 0에 매핑된 물리 주소의 페이지 프레임이 2임을 계산한다.
• 가상 주소 0은 물리 주소 8192로 변환되고, 이 물리 주소가 메모리 버스에 실린다.

그러나 가상 페이지를 페이지 프레임에 매핑하는 것만으로는, 가상 주소 공간이 물리 주소 공간보다 큰 문제를 해결하지 못한다.

페이지 폴트 (Page Fault)

페이지 폴트는 페이지가 메모리에 매핑되어 있지 않음을 파악하면 CPU에서 트랩을 발생시키는 현상이다. present 비트는 어떤 페이지가 실제 메모리에 존재하는지를 표현하는 비트로, 가상 페이지에 X로 표시된다. 페이지가 메모리에 매핑되어 있지 않으면, CPU에서 트랩을 발생시켜 운영체제에 이를 알린다.

페이지 폴트가 발생하면, 운영체제는 적게 사용되고 있는 페이지 프레임을 하나 선택한다. 선택한 페이지가 수정되었다면 (dirty 상태) 이를 디스크에 기록하고, 수정되지 않았다면 (clean 상태) 디스크에 존재하는 것과 동일하므로 기록하지 않는다. 선택한 기존 페이지의 내용을 지우고, 참조하려는 페이지의 내용을 페이지 프레임에 적재한 후, 선택한 기존 페이지 프레임을 X로, 참조한 페이지 프레임을 숫자로 매핑시켜 가상 페이지 맵을 수정한다. 마지막으로 트랩이 발생한 명령어를 다시 실행한다.

명령어 MOV REG, 24576을 수행할 때 페이지 폴트가 발생해 OS에서 페이지 프레임 1을 교체한다고 가정해보자.

• 가상 페이지 1이 더 이상 매핑되지 않음을 X로 표시한다.
• 가상 페이지 7이 페이지 프레임 1에 매핑되었음을 표시한다.

페이징 테이블 (Page Table)

페이징 테이블은 가상 페이지 번호(VPN)를 페이지 프레임 번호(PFN)로 매핑하는 구조이다.

위의 매핑 정보를 바탕으로 가상 주소 8196를 물리 주소 24580로 변환하는 과정을 가정해 살펴보자.

16비트 크기를 갖는 가상 주소는 VPN와 오프셋으로 구분된다. 페이지 번호는 페이지 테이블의 인덱스로 사용된다. 페이지 테이블에는 VPN에 대응되는 PFN이 기록되어 있다. present 비트가 1이면, 페이지 테이블의 PFN 3과 가상 주소의 오프셋 12가 결합해 물리 주소가 된다. 물리 주소를 주소 출력 레지스터를 통해 메모리 버스로 전달해 참조한다.

페이지 테이블에는 디스크에 존재하는 페이지의 디스크 주소에 대한 정보가 없다. 페이지 폴트(Page Fault)는 운영체제 내부에서 처리되며, 페이지 테이블에는 메모리에 존재하는 페이지 주소에 대한 정보만 있다. 하드웨어는 이를 사용해 가상 주소를 물리 주소로 변경한다.

페이지 테이블의 각 엔트리에는 다음과 같은 정보가 포함된다:

• 페이지 프레임 번호 (PFN) : 가상 주소를 물리 주소로 매핑하며, 해당 페이지가 매핑된 물리 주소를 결정한다. 이 번호는 가상 페이지가 실제 물리 메모리의 어느 페이지 프레임에 위치하는지를 나타낸다.
• Present 비트 : PFN이 유효한지 아닌지를 결정하는 비트이다. 가상 주소가 사용될 때마다 이 비트가 확인되며, 0 (X)이면 해당 엔트리에 대응되는 페이지가 물리 메모리에 존재하지 않는 상태를 의미하여 트랩이 발생한다. 1이면 해당 페이지가 물리 메모리에 존재하는 상태를 의미한다.
• Protection 비트 : 페이지에 대한 접근 권한을 표시한다. 이 비트는 해당 페이지에 어떤 접근이 허용되는지를 나타내며, 보통 write, read, execute 권한으로 구분된다. 각 비트가 설정되어 있으면 그 권한이 허용됨을 의미한다.
• Modify 비트 (Dirty 비트) : 페이지가 수정되었는지 아닌지를 나타낸다. 페이지의 내용이 write되면 하드웨어가 자동으로 이 비트를 1로 설정한다. Modify 비트가 1 (dirty)인 경우, 페이지 프레임이 교체될 때 디스크에 기록되어야 한다. Modify 비트가 0 (clean)인 경우, 페이지 프레임이 교체될 때 새로운 내용으로 덮어씌워도 된다.
• Reference 비트 : 해당 페이지가 접근되었는지를 나타낸다. 페이지가 write 또는 read로 접근될 때 설정되며, 운영체제가 Page Fault의 처리를 위해 교체할 페이지 프레임을 선택할 때 사용된다. 이 비트를 통해 운영체제는 페이지의 사용 빈도를 추적하고, 적절한 교체 알고리즘을 적용할 수 있다.
• Caching Disabled 비트 : 해당 페이지가 캐싱될 수 있는지 여부를 나타낸다. 이 비트가 설정되어 있으면 해당 페이지는 캐시되지 않으며, 주로 페이지가 메모리가 아닌 장치 레지스터에 매핑되어 있을 때 사용된다. 캐시를 비활성화하면 일관성을 보장할 수 있다.

64비트 주소를 사용하는 컴퓨터는 가상 주소 공간이 2^64 byte이다. 가상 주소 공간의 한 페이지가 4KB = 2^12 byte이면, 페이지 테이블의 엔트리 개수는 전체 공간을 한 페이지로 나눈 2^52 개이다. 엔트리 하나당 4 byte의 크기를 가진다면, 페이지 테이블의 크기는 2^52 * 4 byte가 된다.

페이징은 다음 두 가지 문제를 해결해야 한다.

• 가상 주소 공간이 커지면 페이지 테이블의 크기, 즉 페이지 테이블 엔트리의 개수 또한 증가한다. 그러므로 페이지 테이블을 유지하기 위해서 필요한 메모리의 크기가 클 수 있다.
• 가상 주소에서 물리 주소로의 변환이 빠르게 이루어져야 한다. 메모리를 참조하는 오버헤드가 작아야 한다.

TLBs (Translation Lookaside Buffers)

TLB는 페이지 테이블의 참조 없이 가상 주소를 물리 주소로 매핑할 수 있는 작은 크기의 메모리이다. 이는 MMU 내부에 존재하며, 적은 개수의 엔트리를 가진다. 각각의 TLB 엔트리는 한 페이지에 대한 정보를 포함하고 있다. TLBs는 페이징의 속도를 높이고, 큰 가상 주소 공간을 지원하는 기법을 말한다.

1. MMU는 주소 변환을 할 때 요청된 가상 페이지가 TLB에 있는지 검색한다.
2. 가상 페이지가 존재하고 보호 코드를 위반하지 않으면, 대응되는 페이지 프레임을 사용하여 주소 변환을 실행한다.
3. TLB에 존재하지 않으면, TLB miss가 발생한다. MMU는 페이지 테이블에서 해당 페이지 테이블 엔트리를 검색한다.
4. 그리고 TLB 엔트리 중 하나를 선택해 그 내용을 교체한다. 페이지 테이블에 없는 수정 비트는 페이지 테이블에 기록된다.
5. 찾은 페이지 테이블 엔트리를 TLB 엔트리에 기록한다. 이때 다시 참조하면 TLB hit로 처리된다.
6. 새로운 정보가 적재될 때는 페이지 테이블 엔트리에 있는 내용이 적재된다.

메모리 계층 구조에서 발생할 수 있는 miss의 경우의 수는 2^3가지이지만, 실제 발생 가능한 경우의 수는 5가지이다.

Cache	TLB	Virtual Memory	발생 가능 여부	설명
hit	hit	hit	가능 (최선)	(1) TLB가 hit이므로, 페이지 테이블을 확인할 필요 없이 가상 주소를 물리 주소로 변환 (메인 메모리 접근 X) (2) Cache가 hit이므로, 변환한 물리적 주소로 캐시에 접근하면 데이터를 가져올 수 있음
miss	hit	hit	가능	(1) TLB가 hit이므로, 페이지 테이블을 확인할 필요 없이 가상 주소를 물리 주소로 변환 (메인 메모리 접근 X) (2) Cache가 miss이므로, 변환한 물리적 주소로 캐시에 접근하면 데이터를 가져올 수 없음 (3) Virtual Memory가 hit이므로, 캐시에 데이터를 불러오기 위해 메모리에 접근하면 데이터를 가져올 수 있음 (4) 메모리에서 캐시로 가져온 데이터를 CPU에 전달
hit	miss	hit	가능	(1) TLB가 miss이므로, 페이지 테이블에 접근 (메인 메모리 접근 O) (2) Virtual Memory가 hit이므로, 가상 주소를 물리 주소로 변환 (3) Cache가 hit이므로, 변환한 물리 주소로 캐시에 접근해 캐시에 있는 데이터를 CPU에 전달
miss	miss	hit	가능	(1) TLB가 miss이므로, 페이지 테이블에 접근 (메인 메모리 접근 O) (2) Virtual Memory가 hit이므로, 가상 주소를 물리 주소로 변환 (3) Cache가 miss이므로, 변환한 물리 주소로 캐시에 접근하면 캐시 내에 데이터가 없음 (4) 메인 메모리에서 해당 데이터를 캐시로 가져와 CPU에 전달
miss	miss	miss	가능 (최악)	(1) TLB가 miss이므로, 페이지 테이블에 접근 (메인 메모리 접근 O) (2) Virtual Memory가 miss이므로 (Page fault), 하드 디스크에서 데이터를 직접 가져와 페이지 테이블을 업데이트 (3) 이제 TLB가 miss > hit이므로, 가상 주소를 물리 주소로 변환 가능. (4) Cache가 miss이므로, 변환한 물리 주소로 캐시에 접근하면 캐시 내에 데이터가 없음 (5) 메인 메모리에서 해당 데이터를 캐시로 가져와 CPU에 전달
miss	hit	miss	불가능	메모리 계층 구조 위반 : Page fault인데 TLB가 hit일 수 없음
hit	hit	miss	불가능	메모리 계층 구조 위반 : Page fault인데 TLB가 hit일 수 없음
hit	miss	miss	불가능	메모리 계층 구조 위반 : Page fault인데 Cache가 hit일 수 없음 (캐시에 데이터가 있을 수 없음)

• TLB miss인 경우 : 페이지 테이블에는 정보가 있지만, TLB에 그 정보가 들어있지 않을 때
  • 해결책 : 페이지 테이블의 페이지 엔트리 내 데이터를 가져와 TLB에 넣는다.
• Page fault인 경우 : TLB에도 정보가 없고, 페이지 테이블에도 그 정보가 없을 때
  • 운영체제는 권한을 받아 하드 디스크의 데이터를 페이지 테이블에 가져오고, TLB에 가져온 데이터를 넣는다.

다단계 페이지 테이블 (Multi-level Page Table)

다단계 페이지 테이블은 페이지 테이블을 페이지 프레임 크기로 나누어, 해당 페이지 테이블의 페이지가 invalid하면 메모리에 할당하지 않고 기존의 단일한 페이지 테이블을 트리 구조로 연결한다. 페이지 디렉토리(Page Dictionary)는 페이지 프레임의 유무를 확인하는 자료구조로, 적어도 하나의 PFN이 valid하다면 페이지 디렉토리의 해당 엔트리는 존재하게 된다.

기존의 페이지 테이블에서는 가운데에 위치한 페이지가 메모리에 할당되어 있지만, 다단계 페이지 테이블에서는 가운데에 위치한 페이지가 메모리에 할당되어 있지 않다. 다단계 페이지 테이블의 모든 페이지 테이블은 항상 메모리에 유지될 필요가 없다.

다단계 페이지 테이블은 필요한 페이지 테이블만 메모리에 할당해 메모리 사용을 절약할 수 있다. 페이지 디렉토리를 통해 물리 메모리의 빈 공간에 페이지 테이블 엔트리를 생성할 수 있다. 하지만, 기존의 TLB Miss가 2번 늘어나 주소 변환이 2번 필요하고, TLB Miss를 처리해 메모리를 최적화하는 로직이 복잡해진다.

역 페이지 테이블 (Inverted Page Table)

역 페이지 테이블은 빠른 하드웨어 레지스터로 구성된 단일한 페이지 테이블을 사용한다. 페이지 테이블의 각 엔트리는 하나의 메모리 프레임에 대응된다. 크기가 고정된 페이지 테이블에 프로세스를 맵핑하며, 프로세스 실행 시 운영체제는 메모리에 존재하는 프로세스의 페이지 테이블 전체를 하드웨어 레지스터 배열에 적재한다. 논리 주소는 PID, PFN, offset으로 구성되고, 물리 주소는 MFN와 offset으로 구성된다.

논리 주소의 PID와 PFN 정보를 바탕으로 페이지 테이블에서 동일한 엔트리를 탐색하고, 페이지 테이블에서 PID와 PFN이 일치하는 MFN 번째 항목을 발견한다. 이후, MFN과 Offset 정보를 바탕으로 확인된 메모리 주소에 접근한다.

예를 들어, 64bit를 사용하는 컴퓨터에서 256MB의 물리 메모리가 4KB 페이지 프레임 2^18개로 구성되었다면, 페이지 테이블을 사용할 때의 페이지 테이블의 엔트리는 가상 주소 공간 2^64byte를 한 페이지 프레임의 크기 4KB = 2^12byte로 나눈 2^52개가 된다. 반면, 역 페이지 테이블을 사용하는 페이지 테이블의 엔트리는 물리 메모리의 페이지 프레임의 개수와 같으므로, 물리 메모리 256MB = 2^28byte를 한 페이지 프레임의 크기 4KB = 2^12byte로 나눈 2^16개가 된다.

프로세스 실행 중에는 페이지 테이블을 위한 추가적인 메모리 참조가 필요 없으며, 프로세스 확장이 페이지 테이블과 무관하다. 그러나 페이지 테이블이 커질수록 구현을 위한 비용이 증가하고, 최악의 경우 페이지 테이블 전체를 적재해야 하는 경우가 발생할 수 있다. 예를 들어, 문맥 교환 시 이러한 문제가 발생할 수 있다.