[OS/OSTEP] 20.vm-smalltables : 더 작은 테이블, 하이브리드 테이블, 멀티레벨페이지 #14

20.vm-smalltables 

# 시작하며

 페이징의 문제점이 하나 더 생겼다. 페이지 테이블이 크면 많은 메모리 공간을 가져야하는데, 그 메모리 공간은 선형 페이지 테이블구조이기때문에 연속된 공간을 가져야한다. 또 많은 프로세스가 존재하기 때문에 페이지 테이블의 크기도 커진다. 이 문제를 이번장에서 해결해 보도록 하자

 

# 더 큰 페이지

 페이지 테이블을 줄이기 위해서 어떻게 해야할까? PTE의 개수를 줄이면 될 것이다. 그걸 줄이기 위해서는 페이지 자체의 크기를 키우면 페이지의 개수가 줄어든다. 당연한 결과이다 가상주소 예를들어 8비트를 사용중이라면 offset을 사용하는 만큼 page를 표현하는 vpn의 몫은 작아진다. 

 그러나 페이지가 커지면 내부 단편화(internal fragmentation)문제가 발생한다. 즉 할당 받은 페이지에서 안쓰는 부분이 많이 생긴다는 는 뜻이다.

 

# 하이브리드 접근법 : 페이징 + 세그먼트

 선형 페이지 테이블의 동작을 면밀히 분석해 보면, 페이징과 세그멘테이션을 효과적으로 결합할 수 있다는 생각을 할 수 있다. 

 페이지의 크기는 1KB이고 가상주소공간은 16KB이다. 총 16개의 페이지로 나눌 수 있다. 현재 가상주소 중간부분부터는 메모리를 사용하지 않고 있다. 16개의 페이지중에서 4개의 페이지만 사용중이다. 기존의 방식의로 페이지테이블을 구성하면 이렇게 쓰지 않는 공간도 페이지 테이블에 올려야 했다.

 이제 세그멘테이션의 개념을 도입한다. 하나의 테이블의 모든 테이블의 정보를 담는 것이 아닌, 페이지 테이블을 논리세그멘트로 한단계 더 나누고 그 세그멘트마다 페이지 테이블을 별도로 구성하는 것이다. 즉 코드, 힙, 스택 세그멘트에 대한 각각의 페이지 테이블을 만드는 것이다.

 그렇다면 다시 가상주소공간의 표현을 위처럼 할 수 있을 것이다. VPN을 다시 Seg로 나누었다. 총 4개의 세그멘트로 나누었다. 00, 01, 10, 11이 세그멘테이션을 표현 할 수 있는데, 00에는 미사용 공간, 01 코드, 10 힙, 11은 스택 으로 구성시킨다. 이제 미사용을 제외한 3개의 세그멘테이션을 사용할 수 있고, 그 세그멘테이션에 대한 base-bound 레지스터쌍이 생성된다. 그리고 해당 base로 이동하게 되면 페이지 테이블이 들어있다. 미사용 공간에 대해서 페이지테이블을 생성하지 않고, 세그멘트의 size를 정의했기에 원하는 크기만큼의 페이지 테이블을 사용할 수 있다. 즉 메모리 사용이 개선된다. 더이상 스택과 힙상이의 할당되지 않은 것들이 페이지 테이블 상에서 공간을 차지하지 않는다. 

아래와 같이 접근 할 수 있다.

국민대학교 "황선태" 교수님의 강의자료 중 일부를 사용했습니다.

 

그러나 이것 역시 문제가 생긴다. 세그멘테이션을 사용하기 때문에 주소공간의 사용에 있어 유연하지 못하다.힙의 경우는 여전히 낭비를 면치 못한다. 또 외부 단편화를 유발한다. 페이지 테이블을 내 마음대로 쪼갤수 있고, 또 작게 쪼개기 위해서 노력한다. 작은 것들이 연속되게 배치 되지 않는 이상 외부 단편화를 유발할 수 밖에없다.

 

# 멀티 레벨 페이지 테이블 ( Multi Level Page Table )

 현대 시스템에서 많이 쓰이는 기법이다. 페이지테이블을 또 페이지로 구성시켜버린다. 처음 보면 조금 헷갈릴 수 도있다.

 먼저 페이지 테이블을 페이지 크기의 단위로 나눈다. 그다음 페이지가 유효하지 않은 항목만 있으면 해당 페이지는 할당하지 않는다여기서 페이지의 갯수가 줄어든다). 페이지 디렉토리라는 자료구조를 새롭게 만들고, 그 페이지 디렉토리안에는 PDE(page directory entries)페이지테이블들의 PFN위치가 있다. 그렇게 접근하여 얻어낸 페이지테이블에서 PTE를 뽑아내고, 그 PTE에서 PFN을 뽑고, offset과 결합하여 실제 물리주소를 얻어낸다. 당연하게도 PTBR이라는 곳에서는 Page Directory의 위치를 알고 있어야 한다. 프로세스간 이동이 일어난다면 이 값 또한 초기화 해줘야 한다.

 PDE에도 PTE와 마찬가지로 Valid bit가 존재한다. PDE의 valid bit가 유효하다는 것은 해당 PDE가 가르키고 있는 Page Table의 페이지들 중 한개라도 유효하다는 것이다.

위 강의에서의 그림도 좋지만, 교수님께서 설명해주신 자료를 보면 한번에 이해 할 수 있다.

국민대학교 "황선태" 교수님의 강의자료 중 일부를 사용했습니다.

1. Page Directory 에는 PDE가 존재한다. 이 PDE의 PFN의 값으로 접근하면 Page Table(페이지 테이블)이 나온다.
2. Page Table(페이지 테이블)에는 PTE가 존재한다. 이 PTE의 PFN 값으로 접근하면 찾고자 하는 주소의 PFN(Page frame number)이 나온다.
3. 얻어낸 PFN과 OFFSET을 결합시켜 최종 주소를 얻어낸다.

 

## 장점

 이렇게 구성한 멀티레벨 페이지는 주소 공간의 크기에 비례하여 페이지 테이블 공간이 할당된다. 그렇기 때문에 사용하는 페이지테이블만 배치 할 수 있다.

 페이지 테이블을 페이지 크기로 분할함으로써 메모리 관리에 매우 용이하다. 페이지 테이블을 할당하거나 확장할때, 빈 페이지를 가져다 사용하면 된다.

 선형 페이지 테이블(연속되게 배치해야하는 페이지 테이블)은 큰 페이지 테이블 공간을 가져야 하고, 이는 연속 되야한다. 이렇게 빈 물리 메모리 공간을 찾는것도 쉬운일은 아니라는 것이다. 멀티레벨 페이지를 사용함으로써 페이지 테이블을 4KB( 페이지의 크기 ) 로 구성시킬 수 있다. 어떤 곳이라든 페이지가 들어갈 수 있으면 구성 할수 있기에 매우 유연하다.

 

## 단점

 TLB 히트시에는 장점이 많지만, TLB 미스시에는 성능이 급격히 하락한다. 페이지 테이블에 접근하는 과정을 한번더 수행해야한다. 즉 메모리 액섹스가 한번 더 일어난다.

두번째는 복잡해진다.

 

# 멀티 레벨 페이징에서의 주소 표현

주소공간이 14비트(2^14, 4KB)일때 한 페이지는 6비트(2^6,64바이트)로 구성된다. 이런 페이지가 VPN의 갯수만큼 존재한다(물리주소말고 가상주소에). 페이지 디렉토리에는 현재 존재하는 페이지 테이블들이 들어가야한다. 결국 페이지 디렉토리도 페이지 안에 구성되기 때문에 한 페이지에 몇개의 PDE가 들어갈 수 있는지 보면, 8비트(2^8, 256) 총 페이지의 갯수는 256개이다 이 256 * PTE(4Byte) = 1KB의 페이지의 총 합이 있다는 것이다. 이 테이블은 몇개의 페이지로 구성시킬 수 있을까? 1KB / 64Byte(한페이지의 크기) 를 하면 16이 나오고,  16개의 페이지로 표현 할 수 있다는 것이다. 그렇다면 페이지 디렉토리에는 16개의 페이즈를 구성시키면 된다.

 

이렇게 2단계 3단계의 방식으로 더 나눌수도 있다.

 

## 멀티 레벨 페이징의 제어 흐름 

 

# 요약

 지금까지 물리 메모리의 공간은 무제한이라는 가정이었다. 그렇기 때문에 물리 메모리 영역에 페이지테이블이 존재했다. 그러나 이러한 방법을 사용하더라도 페이지 테이블을 메모리에 이동시킥기에 양이 너무 클 수 도있고, 시슽쳄 메모리가 부족할때 디스크로 스왑하여 사용하기도 한다. 다음시간에는 이런 스왑과 스왑 정책에대해서 알아보면서 중간고사 대비 운영체제 요약을 마무리하도록 하겠다!