[OSTEP] CH20 페이징 - 더 작은 테이블

발표 일자 2024.11.11 MON 2시p.m. 

CH20 페이징 - 더 작은 테이블 

페이징의 두 번째 문제점은 페이지 테이블의 크기이다 (첫 번째 문제점은 성능 저하) 

페이지 테이블이 크면 많은 메모리 공간을 차지하고, 각 프로세스는 자기 자신의 페이지 테이블을 갖는다 

핵심 질문 - 페이지 테이블을 어떻게 더 작게 만들까
단순한 배열 기반의 페이지 테이블은 (흔히 선형 페이지 테이블이라고 불림) 크기가 크며 일반적인 시스템에서 메모리를 과도하게 차지한다, 어떻게 페이지 테이블의 크기를 줄일 수 있을까? 새로운 자료 구조들은 어떤 비효율성을 갖는가? 

20.1 간단한 해법 - 더 큰 페이지 

페이지 테이블의 크기를 줄일 수 있는 간단한 방법은 페이지 크기를 증가시키는 것이다 

🐣 페이지 테이블은 가상 주소를 물리 주소로 변환하기 위한 각 가상 페이지에 대해 물리 메모리 상의 페이지 번호를 기록하는데

페이지 크기가 커지면, 더 적은 수의 페이지로 전체 가상 메모리 영역을 커버할 수 있기 때문에 페이지 테이블 엔트리 수가 줄어든다 🐣 

하지만 페이지 크기가 커지면, 페이지 내부의 낭비 공간이 증가하는, 내부 단편화 Internal Fragmentation 가 발생하여

컴퓨터 시스템의 메모리가 금방 고갈되는 현상이 발생할 수 있다

20.2 하이브리드 접근 방법 - 페이징과 세그먼트 

두 가지 방법을 조합하는 것을 하이브리드 Hybrid 라고 한다

Dennis 는 페이징과 세그멘테이션을 결합하여 페이지 테이블 크기를 줄이는 아이디어를 내었다 

프로세스의 전체 주소 공간을 위해 하나의 페이지 테이블을 두는 결합 방식 대신,

논리 세그먼트 - 코드, 힙, 스택 - 마다 따로 페이지 테이블을 둘 수 있다 

 

세그멘테이션에서는 세그먼트의 물리 주소 시작 위치를 나타내는 베이스 Base 레지스터와

크기를 나타내는 바운드 Bound 또는 리미트 Limit 레지스터가 있다 

베이스 레지스터는 세그먼트 시작 주소가 아니라, 세그먼트의 페이지 테이블의 시작 주소를 갖고

바운드 레지스터는 페이지 테이블의 끝을 나타내기 위해 사용한다  

 

가상 주소를 아래와 같이 표현했을 때, 소속 세그먼트를 나타내기 위해 상위 두 비트를 사용할 수 있다

00 은 미사용, 01 는 코드, 10 은 힙, 11 은 스택을 나타낸다고 가정한다 

이 시스템에서 모든 프로세스들은 세 개의 페이지 테이블을 갖게 되고, 각 세그먼트에서 베이스 레지스터는 각 세그먼트의 시작 물리 주소를 가지게 되어, 문맥 교환 시, 이 레지스터들은 새로 실행되는 프로세스의 페이지 테이블의 위치값으로 변경된다 🐣 간단하게 얘기하면, 프로세스가 바뀔 때마다 각 페이지 테이블의 위치값과 각 세그먼트의 베이스 레지스터 값을 참조하여 메모리 주소 정보를 설정할 수 있다 🐣

 

하이브리드 기법의 핵심은 세그먼트마다 바운드 레지스터가 따로 존재한다는 것이고, 각 바운드 레지스터의 값은 세그먼트의 최대 유효 페이지 개수를 나타낸다, 해당 세그먼트의 범위를 넘어가는 곳으로 메모리 접근을 할 경우 예외가 발생하고, 해당 프로세스는 종료된다

이 방식으로, 선형 페이지 테이블에 비해 메모리 사용을 개선시킬 수 있다 

🐣 바운드 레지스터 값이 세그먼트 내의 메모리 범위를 제한하여 (메모리 사용에 대해 제한을 두기 때문에) 메모리 사용을 개선시킨다 🐣 

+ 세그먼트 범위를 넘어가는 곳으로 접근할 경우 예외 발생하는 것이 세그멘테이션 폴트 

 

하지만, 1) 세그멘테이션 방법을 사용하여 페이지 테이블의 낭비를 면치 못할 수 있고

2) 하이브리드 기법은 외부 단편화를 발생한다는 문제점이 존재한다 

20.3 멀티 레벨 페이지 테이블 

세그멘테이션을 사용하지 않고 페이지 테이블 크기를 줄이는 기법으로 멀티 레벨 페이지 테이블이 있다 

멀티 레벨 페이지 테이블에서는 선형 페이지 테이블을 트리 구조로 표현한다 

+ 페이지 테이블을 페이지 크기로 나눈다 (물리 메모리 크기와 동일하게) 그 안에는 PTE 들이 많이 존재한다 

페이지 테이블이 너무 크니까, 페이지 중에 PTE 가 하나라도 1이면 메모리에 적재한다, 0이면 안 올린다

PDE (Page Directory Entry) 에 여러 개의 PTE 가 들어간다 

페이지 디렉토리는 페이지 테이블의 페이지 테이블 개념으로 이해했대 

멀티 레벨 페이지 테이블은 페이지 테이블을 페이지 크기의 단위로 나눈다 

그 다음 페이지 테이블의 페이지가 유효하지 않은 항목만 있으면 해당 페이지를 할당하지 않는다 

페이지 디렉토리 Page Directory 를 사용하여 페이지 테이블 각 페이지의 할당 여부와 위치를 파악한다 

 

페이지 디렉토리의 각 항목은 페이지 테이블의 한 페이지를 나타내고, 

페이지 디렉토리는 페이지 디렉토리 항목 Pager Directory Entries, PDE 들로 구성된다 

PDE 는 유효 Valid 비트와 페이지 프레임 번호 Page Frame Number, PFN 를 갖고 있다 

PDE 가 유효하다는 것은 PFN 을 통해서 그 항목이 가리키고 있는 페이지들 중 최소 하나가 유효하다는 의미이다 

PDE 가 가리키고 있는 페이지 내의 최소한 하나의 PTE 의 Valid bit 가 1로 설정되어 있다 

만약 PDE 가 유효하지 않다면 (0이라면) PDE 는 실제 페이지가 할당되어 있지 않은 것이다 

멀티 레벨 페이지 테이블의 장점

1) 멀티 레벨 테이블은 사용한 주소 공간의 크기에 비례하여 페이지 테이블 공간이 할당된다

보다 작은 크기의 페이지 테이블로 주소 공간을 표현할 수 있다

2) 페이지 테이블을 페이지 크기로 분할해서 메모리 관리가 매우 용이하다 

페이지 테이블을 할당하거나 확장할 때, 운영체제는 free 페이지 풀에 있는 빈 페이지를 가져다 쓰면 된다 

선형 페이지 테이블은 연속된 물리 메모리 공간을 찾기 힘들지만, 멀티 레벨 페이징에서는 페이지 디렉토리를 사용하여 각 페이지 테이블 페이지들의 위치를 파악할 수 있기 때문에 공간 할당이 유연하다 

멀티 레벨 페이지 테이블의 단점 

1) 추가 비용이 발생한다, TLB 미스 시, 주소 변환을 위해 두 번의 메모리 로드가 발생한다

페이지 디렉토리와 PTE 접근을 위해 각각 한번씩 필요하다 

(선형 페이지 테이블에서는 한번의 접근만으로 주소 정보를 TLB 로 탑재할 수 있음)

대부분 메모리 접근은 TLB 히트이고 그런 경우 성능은 동일하지만, TLB 미스 시에는 두 배의 시간이 소요된다 

2) 페이지 테이블 검색이 단순 선형 페이지 테이블의 경우보다 더 복잡하다 

20.4 역 페이지 테이블 

역 페이지 테이블 Inverted Page Table 방법은 여러 개의 페이지 테이블 대신 시스템에 한 하나의 페이지 테이블만 둔다 

페이지 테이블은 물리 페이지를 가상 주소 상의 페이지로 변환하고, 역 페이지 테이블의 각 항목은

해당 물리 페이지를 사용 중인 프로세스 번호, 해당 가상 페이지 번호를 가지고 있다 

역 페이지 테이블에서는 주소 변환을 위해 전체 테이블을 검색하는데 순차 탐색은 느리기 때문에 

탐색 속도 향상을 위해 주로 해시 테이블을 사용한다 

20.5 페이지 테이블을 디스크로 스와핑하기 

모든 페이지 테이블을 메모리에 상주시키기에 메모리 요구량이 너무 클 수 있기 때문에

어떤 시스템들은 페이지 테이블들을 커널 가상 메모리에 위치시키고 

메모리가 부족할 경우 페이지 테이블들을 디스크로 스왑 Swap 한다 

이 부분은 페이지를 메모리에 탑재/ 제거하는 방법을 이해한 후에 다룬다 

+ 우리가 아는 가상 메모리이다 

20.6 요약

공간을 많이 소모하는 테이블 구조를 사용할수록 TLB 미스의 처리 속도가 빨라지고

공간을 작게 차지하는 테이블 구조를 사용하면 상황이 반대가 된다

주어진 제약 조건들을 적절히 고려하여 적합한 자료 구조를 결정해야 한다 

어떤 새로운 자료 구조가 있을까? 그 새로운 구조는 어떤 문제를 해결할까?