Paging Issues
이전 글에서 다루었던 페이징의 개념에 이어 페이징과 관련된 이슈를 살펴보자.
Frame Size
페이징의 문제점은 internal fragmentation이 생긴다는 것이다. 그럼 internal fragmentation 문제를 최소화하려면 페이지의 크기를 무작정 줄이면 될까? 답은 아니다. 페이지의 크기가 작아질수록 페이지 테이블의 크기가 커진다. 그리고 페이지 테이블은 메모리에 존재하기 때문에 페이지 테이블이 커질수록 메모리도 많이 사용하게 된다. 시간이 지남에 따라 페이지의 크기가 커지고 있지만, 너무 크지도 작지도 않은 적정한 크기를 사용하는 것이 중요하다.
Page Table
페이지 테이블은 메인 메모리엔 존재한다. 따라서 CPU가 메모리에 접근하려고 하면 메모리 접근 과정을 2번 거친다. 한번은 페이지 테이블 접근할 때이고, 다른 한번은 논리적 주소를 물리적 주소로 변환 후 메모리 접근할 때다. CPU는 굉장히 빠르기 때문에 메모리에 한번 접근하는 시간은 CPU의 입장에서 굉장히 길다. 그렇기에 최대한 메모리의 접근을 피해야 한다. 여기서 바로 TLB가 나왔다.
TLB(Translation Look-Aside Buffer)
TLB는 하드웨어 캐시의 일종으로 메모리 계층 구조에서 CPU와 메모리 사이에 존재한다. CPU 레지스터에 두면 속도는 빠르지만 레지스터의 개수가 매우 제한적이라 큰 크기의 페이지 테이블을 담지 못한다. 그리고 위에서 말했듯 메모리에 두면 크기 제한에서는 자유로우나 CPU로부터의 접근 시간이 길다. 따라서 페이지 테이블의 일부를 TLB라는 캐시에 저장한다.
Address Translation with TLB
1. 페이지 번호가 3, 오프셋이 5인 논리적 주소가 있다.
2. TLB에서 페이지 번호가 3인 엔트리를 찾는다.
2-1. 엔트리가 존재한다면, 프레임 번호를 가져와 오프셋을 더한다. (TLB hit)
2-2. 엔트리가 없다면, 메모리에 있는 페이지 테이블에 접근해 해당 페이지 번호와 프레임 번호를 TLB에 넣는다. 곧바로 TLB에 다시 접근한다. (TLB miss)
3. 물리적 주소를 이용해 메모리에 접근한다.
Effective Access Time (EAT)
페이징과 TLB를 사용하여 메모리에 접근하는 시간을 EAT라고 하며 다음 식으로 구할 수 있다.
EAT = cache hit ratio * (TLB lookup + mapped memory access) + cache miss ratio * (TLB lookup + page table memory access + mapped memory access)
Cache hit ratio = 80 %
Time taken for TLB search = 2ns
Time taken for memory access = 100ns
위와 같은 조건이 주어졌을 때 EAT는 0.8 * (2ns + 100ns) + (1 - 0.8) * (2ns + 100ns + 100ns) = 130ns가 된다.
Page Table Structure
Hierarchical Page Table
논리적 주소가 커질수록 페이지 테이블의 크기도 증가해서 메모리에 더 큰 공간이 필요하다. 32비트 주소 공간은 4GB(2^32)를 메모리로 사용할 수 있다. 만약 페이지의 크기가 4KB(2^12)라면 페이지 테이블의 개수는 4GB/4KB = 1,048,576개다. 32비트 주소 공간이므로 페이지 테이블을 저장하기 위해 필요한 메모리는 1,048,576 * 32비트 = 4MB이다. 이 문제는 논리적 주소 공간을 여러 개의 페이지 테이블로 나누어 해결한다. 즉, 페이지 테이블을 페이지화한다. 위의 예제에서 페이지 번호를 나타내는 20비트를 10비트씩 나누어 페이지 테이블을 페이지화하면 테이블을 위한 메모리 공간이 훨씬 줄어든다.
Two-Level Page Table
Address Translation
첫번째 페이지 번호에 해당하는 엔트리는 두번째 테이블를 가리킨다. 그리고 두번째 페이지 번호에 해당하는 엔트리는 프레임 번호를 가진다.
예를 들어 32비트 주소 공간이 있고, 첫번째 페이지 테이블(outer)은 10비트, 두번째 페이지 테이블(inner)은 12비트, 오프셋은 10비트을 사용하고 각각은 3, 7, 10의 값을 가진다고 하자. 첫번째 테이블의 인덱스 3에 F1라는 값이 있다. F1은 두번째 테이블의 위치를 가리킨다. 두번째 테이블 F1에서 인덱스 7에 20이라는 값이 있다. 따라서 최종적인 주소는 10 * 2^10 + 20이 된다.
Hashed Page Table
해싱을 사용한 테이블은 연결 리스트로 이루어져 있으며, 각 엔트리는 가상 페이지 번호, 프레임 번호, 다음 리스트를 가리키는 포인터로 구성된다. 페이지 번호를 해싱하고 해당하는 값을 가진 연결 리스트로 이동하여 연결 요소들의 가상 페이지 번호와 비교하는 작업을 거친다. 해싱은 O(1), 연결 리스트를 검색하는 데는 O(n)의 시간이 걸린다.
Inverted Page Table
보통 프로세스들은 자신에게 할당된 페이지들을 전부 사용하는 경우가 드물다. 그렇기에 한 프로세스마다 하나의 페이지 테이블을 만드는 것이 아니라 메모리 전체에 거대한 페이지 테이블을 만들 수 있다. 논리적 주소는 프로세스에 대한 정보, 가상 주소, 오프셋으로, 페이지 테이블의 엔트리는 그 페이지를 소유하고 있는 프로세스에 대한 정보와 가상 주소로 이루어져 있다. 따라서 거대한 페이지 테이블을 훑으며 프로세스에 대한 정보와 가상 주소가 일치하는 엔트리를 찾으면, 그 엔트리의 인덱스가 프레임 번호가 된다.
페이지 테이블은 물리적 주소에 의해 정렬되어 있고 엔트리를 찾을 때 가상 주소를 사용한다. 이 때문에 페이지 테이블에 저장하는 메모리 공간은 줄일 수 있지만 테이블을 검색하는 시간은 증가한다.
Memory Protection
Protection Bit
모든 메모리 접근은 페이지 테이블을 경유한다. 따라서 페이지 테이블 엔트리마다 protection bit인 r(readable), w(writable), x(executable)을 둔다면 해당 프레임에 대한 접근을 제어할 수 있다.
Valid Bit
페이지 테이블 엔트리마다 valid bit를 두어 해당 프레임에 페이지가 들어 있는지 혹은 유효한 페이지인지 나타낸다.
Memory Sharing
프로세스들 사이에서 공통된 코드를 공유할 수 있다. 페이징에서는 프로세스를 연속적인 주소 공간에 할당하는 것이 아니므로 여러 프로세스가 하나의 페이지에 접근할 수 있다. 하지만 이 코드들은 반드시 읽기 전용(reentrant)이어야 한다. 시분할 시스템에서 유용하다.
Paging vs. Segmentation
| 특징 | 페이징 | 세그멘테이션 |
|---|---|---|
| partition | 고정된 길이 | 가변적인 길이 |
| 프로세스를 자르는 기준 | 비논리적 단위(일정한 크기) | 논리적 단위 |
| 테이블 | 페이징 테이블 | 세그먼트 테이블 |
| 문제 | internal fragmentation | external fragmentation |
세그멘테이션은 논리적 단위로 프로세스를 나누기 때문에 protection과 sharing 측면에서 페이징보다 낫다. 하지만 external fragmentatin의 문제가 있어 둘을 절충하여 paged segmentation을 쓸 수도 있다. 하지만 논리적 주소를 물리적 주소로 바꾸기 위해 세그먼트 테이블과 페이지 테이블을 두번 거쳐 주소 변환에 시간이 다소 소요된다.
