CS_운영체제_Paging: Smaller Table

Paging: Smaller Table이란?

Paging: Smaller Table은 프로세스가 필요한 페이지 수가 TLB의 용량을 초과하는 경우에도 효율적으로 메모리를 관리하기 위한 기술이다. 페이지 테이블을 더욱 효율적으로 관리하여 메모리 공간을 절약하고 성능을 향상시키는 다양한 방법을 포함한다. 이 방법은 특히 대규모 주소 공간을 사용하는 시스템에서 중요한 역할을 한다.

Paging: Smaller Table에 대한 비유

페이지 테이블을 대형 도서관의 도서 목록이라고 생각해보자. 만약 도서관이 너무 커서 단일 목록으로 관리하기 어렵다면, 도서 목록을 여러 작은 목록으로 나누는 방식을 사용할 수 있다.

 

대형 도서관: 전체 페이지 테이블

작은 목록: 더 작은 페이지 테이블 또는 다중 레벨 페이지 테이블

도서관 사서: 메모리 관리 유닛(MMU)

자주 찾는 책의 위치를 기억하는 단골 독자: TLB

 

페이지 테이블과 TLB

페이지 테이블은 가상 주소를 물리 주소로 변환하는 데 사용되는 데이터 구조로, 모든 페이지의 매핑 정보를 가지고 있다.

TLB(Translation Lookaside Buffer)는 자주 사용되는 페이지 테이블 항목을 캐싱하여 주소 변환을 가속화하는 고속 캐시 메모리이다. TLB가 관리할 수 있는 페이지보다 많은 페이지를 사용하는 경우, 페이지 테이블이 필요하며, 페이지 테이블의 크기를 효율적으로 줄이는 다양한 기법이 도입된다.

 

 

페이지 테이블의 크기를 줄이는 법

 

큰 페이지 사용:

Page table이 너무 클 경우를 대비해서 Page table의 크기를 줄여 메모리를 절약하는 방법이다. 페이지의 크기를 늘리면, 페이지 테이블 항목 수를 줄일 수 있다.

더 큰 페이지 크기를 사용하면, 페이지 테이블 항목 수를 줄일 수 있다. 예를 들어, 4KB 페이지 대신 2MB 또는 1GB 페이지를 사용하면 테이블 항목 수가 줄어든다. 이는 페이지 테이블의 크기를 줄이고 메모리 사용량을 효율화하는 데 도움이 된다.

 

희소 페이지 테이블 (Sparse Page Table):

희소 페이지 테이블은 실제로 사용되는 페이지에 대해서만 테이블 항목을 유지하여 메모리를 절약한다.

 

압축 페이지 테이블:

페이지 테이블을 압축하여 저장 공간을 줄인다. 압축된 형태로 저장된 페이지 테이블은 필요 시 압축 해제하여 사용된다.

 

다중 레벨 페이지 테이블 (Multi-level Page Tables):

페이지 테이블을 여러 레벨로 나누어 관리함으로써 메모리 사용량을 줄이는 방법이다. 이는 매우 큰 주소 공간을 효과적으로 관리할 수 있게 한다.

 

Paging 기법과 Segmentation 같이 사용

각 프로세스의 주소 공간을 더 효율적으로 관리할 수 있다. Segmentation은 메모리를 논리적인 단위로 나누고, 각 세그먼트는 고유한 크기를 가지며, 이는 프로세스가 사용하는 실제 메모리 공간과 일치한다. 이와 함께 Paging을 사용하면, 각 세그먼트를 페이지로 나누어 물리적 메모리에 매핑할 수 있다. 이 방법은 메모리 단편화를 줄이고, 메모리 관리의 유연성을 증가시킨다.

 

 

 

 

Multi-level Page Tables

Multi-level Page Tables는 페이지 테이블을 여러 레벨로 나누어 계층 구조로 관리하는 방식이다. 각 레벨은 이전 레벨의 페이지 디렉터리를 참조하며, 최종 레벨이 실제 물리 주소를 가리킨다.

 

개념:

Linear Page Table을 Tree로 변환:

전통적인 선형 페이지 테이블(Linear Page Table)을 트리(Tree) 구조로 바꾸어 관리한다. 트리 구조는 계층적이며, 각 노드가 다음 레벨의 페이지 테이블을 가리키는 방식이다.

 

페이지 단위로 나누기:

페이지 테이블을 페이지 크기의 단위로 잘라서 관리한다. 이는 각 페이지 테이블이 페이지 크기의 메모리 블록으로 나누어지는 것을 의미한다.

 

유효하지 않은 페이지 테이블 할당 방지:

페이지 테이블 엔트리 전체가 유효하지 않은 경우, 즉 하나라도 유효한 엔트리가 없다면 해당 페이지 테이블을 할당하지 않는다. 이는 메모리 낭비를 방지하고 효율성을 높인다.

 

Page Directory 사용:

페이지 테이블의 유효성을 추적하기 위해 Page Directory라는 새로운 구조를 사용한다. 페이지 디렉터리는 각 페이지 테이블 페이지의 유효성을 관리하며, 필요한 경우에만 페이지 테이블 페이지를 할당한다.

 

예시:

 

레벨 1:

최상위 페이지 디렉터리로, 다음 레벨의 페이지 테이블을 가리킨다. 이 디렉터리는 전체 가상 주소 공간을 관리하는 시작점이다.

예를 들어, 32비트 주소 공간에서는 상위 10비트를 사용해 첫 번째 레벨 디렉터리 엔트리를 선택한다.

 

레벨 2, 3, ...:

중간 레벨 페이지 테이블로, 이 레벨들은 하위 레벨의 페이지 테이블을 가리킨다. 각 중간 레벨은 자신보다 한 단계 낮은 레벨의 페이지 테이블에 대한 포인터를 포함한다.

예를 들어, 두 번째 레벨 페이지 테이블은 주소의 중간 10비트를 사용해 선택된다.

 

최종 레벨:

실제 물리 주소를 가리키는 페이지 테이블 항목을 포함한다. 이 레벨은 실제 데이터가 저장된 물리적 메모리 페이지를 가리킨다.

예를 들어, 주소의 하위 12비트를 사용해 실제 물리 페이지 내의 오프셋을 결정한다.

 

 

장점:

메모리 절약:

필요한 부분만 저장: 사용되지 않는 주소 공간에 대한 페이지 테이블 항목을 유지하지 않아 메모리를 절약할 수 있다.

즉, 실제로 사용되는 주소 공간만 페이지 테이블을 통해 관리한다.

예를 들어, 4GB 주소 공간 중 일부만 사용된다면, 그 부분에 대한 테이블 항목만 생성된다.

 

확장성:

대규모 주소 공간 관리: 매우 큰 주소 공간을 효율적으로 관리할 수 있다. 계층 구조 덕분에 각 레벨이 관리하는 주소 공간이 늘어나도, 전체 페이지 테이블의 크기가 급격히 커지지 않는다.

 

예를 들어, 64비트 주소 공간을 다루는 시스템에서도 같은 방식으로 확장할 수 있다.

 

 

관리 용이성: 

 

계층적 구조: 계층 구조를 통해 페이지 테이블을 관리하기 쉬워진다. 각 레벨이 독립적으로 관리되므로, 특정 부분의 주소 공간을 추가하거나 수정할 때 다른 부분에 영향을 주지 않는다.

예를 들어, 특정 범위의 주소를 재할당하거나 업데이트하는 작업이 용이하다.

 

 

단점:

추가 접근 시간: 다중 레벨을 탐색하는 데 시간이 더 걸릴 수 있다.(단일 레벨 페이지 테이블보다 접근 시간이 길어진다)

예를 들어, 3레벨 페이지 테이블을 사용하면, 최종 주소를 찾기 위해 3번의 메모리 접근이 필요하다.

 

복잡성 증가: 구조가 복잡해지므로 구현과 관리가 어려울 수 있다. 여러 레벨의 페이지 테이블을 유지하고 업데이트하는 과정이 복잡해진다.

예를 들어, 페이지 테이블 엔트리의 추가, 삭제, 갱신 등이 다중 레벨에 걸쳐 이루어져야 한다.

 

 

페이지 디렉터리:

페이지 디렉터리는 다중 레벨 페이지 테이블의 각 레벨에서 다음 레벨을 가리키는 테이블이다. 최상위 페이지 디렉터리는 전체 가상 주소 공간을 커버하는 엔트리를 가지고 있으며, 각 엔트리는 하위 레벨 페이지 테이블을 가리킨다.

 

페이지 테이블의 저장

페이지 테이블의 저장은 메모리에 저장되거나 스와핑을 통해 디스크에 저장될 수 있다.

 

메모리에 저장:

페이지 테이블은 주로 메모리에 저장되어 빠른 접근이 가능하도록 한다. 그러나 메모리 용량이 제한된 경우, 페이지 테이블의 크기를 줄이기 위한 다양한 기법이 필요하다.

 

스와핑(디스크에 저장):

메모리가 부족할 때, 페이지 테이블의 일부를 디스크에 저장하고 필요할 때 다시 메모리로 로드하는 방식이다. 스와핑은 메모리 사용을 효율적으로 관리할 수 있지만, 디스크 접근 속도는 메모리보다 느리기 때문에 성능 저하가 발생할 수 있다.

Summary

Paging: Smaller Table은 페이지 테이블의 크기를 줄여 메모리 사용을 효율적으로 관리하는 방법이다. Multi-level Page Tables와 같은 기법을 통해 대규모 주소 공간을 효과적으로 관리할 수 있다. 페이지 테이블은 주로 메모리에 저장되지만, 필요한 경우 스와핑을 통해 디스크에 저장될 수 있다. 이러한 기술들은 메모리 관리의 효율성을 높여 시스템 성능을 향상시킨다.

 

 

 

 

https://github.com/devSquad-study/2023-CS-Study/blob/main/OS/os_smaller_table.md