[OS] Memory Management III (Paging, Segmentation)

Paging

 지금까지 앞에서 Continous Allocation 기법들에 대해서 살펴보았다. 이제는 본격적으로 현대에서 만이 사용하는 Non-Continous Allocation에 대해서 살펴볼 것이다. Paging과 Segmentation은 기본적으로 Process들을 조각내는 기법이다. Paging은 고정된 사이즈로 나눈 반면에 Segmentation은 가변 사이즈로 Process를 나눈다.

 

 Paging에서의 그 조각이 page이다. 따라서 page는 Process의 chunk라고 할 수 있으며, 일반적으로는 4KB의 크기를 지니고 있다. Paging을 수행하기 위해서는 Main Memory역시 이 page들을 담을 수 있도록 Slot화 해야한다. Memory에서는 이를 page라는 단어를 사용하지 않고 Frame이라는 단어를 사용한다. 따라서 Frame은 Memory Space의 조각이라고 할 수 있는 것이다. 보통의 경우 Page와 Frame의 size는 일치해야한다. 이 크기가 서로 다르면 내부단편화가 매우 커질 수 있기 때문이다. 우리는 이러한 Paging기법을 통해 분산적으로 Process를 Memory상에 적재할 수 있다. 

Page Table (Page Mapping Table)

 Page Table은 page를 관리하기 위한 자료구조 있다. Process가 분산적재 되어 있기 떄문에 우리는 해당 Process의 조각들이 어디에 위치해 있는지 해당 location을 알아야 한다. 기존의 연속할당 방식에서는 relative address를 사용했기 때문에 시작점만 준다면 특정 위치를 targetting할 수 있었다. 그러나 이제는 Memory에 불연적속적으로 올라가 있기 때문에 Page가 어떤 Frame에 Mapping되어 있는지에 대한 정보(순서쌍)을 관리해줘야 하는 필요성이 대두되었다. 당연한 소리일 수도 있겠지만 Process마다 수행하는 작업이 대부분 다르기 때문에 Process마다 1개의 Page Table(이하 PT)가 필요하다. Paging 기법의 장점은 Internal Fragmentation(내부단편화)가 마지막 page의 일부분에만 존재하며 External Fragementation은 존재하지 않다는 것이다. 

 

 위와 같은 그림이 있다고 해보자. 만약 Process A가 16KB, Process B가 8KB, Process C가 16KB, Process D가 20KB를 가지고 있다고 해보자. Process A, B, C가 수행되다가 B가 끝나게 되고, 이제 D가 올라올 차례이다. B는 8KB만 사용하고 있던 것이 나갔으므로 Process D는 빈 자리에 일부 8KB의 Page를 넣고 나머지는 이어 붙이면 된다. 이렇게 한 메모리 상에서 연속적이 아니라 분역속적으로 Memory가 나눠쟈있기 때문에 Process가 Memory에 어디 있는지 관리할 필요성이 생겨야 한다는 것이다. 

Address Translation

 이러한 메모리의 불연속적인 배치 방식으로 인해 전통적인 Base & Bound 방식의 address translation과 다른 방식의 translation 기법이 필요해졌다. 새로운 Memory Translation기법은 page와 frame의 크기가 2의 K승이라는 것에 바탕을 둔다. 이 상황에서 relative address와 logical address (페이지 번호와 offset)이 같아지며 논리주소(상대주소)에서 물리주소(절대주소)로 변환하는 Algorithm이 쉬워진다. 말이 좀 어렵긴 한데 이 논리구조는 아래와 같다. 우선 page의 사이즈를 계산의 편의를 위해서 1KB, 즉 1024 byte라고 두자. 만약 Process에서 2번 페이지의 300번째 offset을 찾아가고 싶다고 해보자. 이러면 page table에 가서 <1, 300> 이 있다. 이때 relative address는 1024 * 2 + 300 = 2348 이 될 것이다. 2번 페이지의 300번째 주소를 접근하는 것이기 때문이다. 그러나 page table을 까보았더니 "어 근데 그거 1번 페이지에 있어"라고 한다면 실제 주소는 1024 * 1 + 300 = 1502가 되어 이를 비교적 쉽게 찾아갈 수 있다. 이해를 위해 아래의 그림을 만들어 보았다. 

 만약 page size가 1KB이면 2의 10승이기에 offset은 총 10bit이 필요하다. 그라나 우리는 이를 2^n에 맞춰야 하니까 n는 6이 되므로 2^6의 page #의 공간이 생긴다. 따라서 총 2^16이 되는 것이다. 주소를 translate시키는 과정을 정리하자면 다음과 같다. 

1. n bit을 추출해서 page #을 추출한다.
2. 이를 index로 여겨 k를 찾는다. 이때 k는 k * 2^10이다. 우리가 방금 본 예시에서는 6 * 2^10, 즉 10번 shift되었다고 생각하면 편하다. 
3. 그 다음에는 나머지 offset을 더한다. 

 이 과정을 HW적으로 빠르게 계산할 수가 있다. 물론 이러한 Paging에는 단점이 존재한다. 먼저 Page Table에 대한 overhead (공간적인 비용)가 발생한다. page table의 크기가 매우 크기도 하며, process당 이를 하나씩 가지고 있어야 하기 떄문이다. 또한 page table에 접근하는 overhead(시간적인 비용)이 발생한다. 

Segmentation 

 Segmentation도 분산적재, 즉 Non-Continous Allocation 중 하나의 기법이다. Paging과의 차이점을 위해서 간단하게 언급했었지만 고정된 크기가 아닌, 논리적인 단위의 가변적인 크기로 Process를 나눈다. 이 논리적인 단위를 Segment라고 부른다. 논리적인 단위라고 하는 것은 code, data, stack, heap, symbol...... 등등 이렇게 비슷한 묶음끼리의 단위로 분리한 것이다. 논리의 단위이기 때문에 각각 고정된 크기는 없으며 항상 가변적이다. 따라라서 이 역시 Segment Table로 관리해아 한다. Paging과는 다르게 index로 관리가 되는 것이 아닌 Segment의 limit 정보가 필요하다. <limit, base> 이렇게 구성이 된다. limit은 말 그대로 Segment가 가질 수 있는 size의 상한이며, base는 Segment의 시작주소이다.  Segmentation의 장점은 Dynamic Patitioning과 같이 내부단편화는 발생하지 않는다는 장점이 있다. 반면, Segment의 크기가 고정되지 않을에 따라 외부 단편화의 문제는 발생한다. 

Address Translation

 Segmentation의 Address Translation은 어떻게 진행되는지 보자. 먼저 16 bit의 Logical Address에서 n = 4, m = 12라고 가정해보자. 물론 이 값은 OS에서 관리를 해준다. 사이즈는 가변적이기 때문에 항상 체크를 해줘야한다. 16bit에서 2^n은 segment의 번호가 된다. 이제 이 Segment 번호를 table에서 읽은 다음 base를 가져와서 base + offset을 통해서 실제 주소를 계산한다. 그러나 이 부분이 limit(length)와 비교해서 넘어가는지 확인하는 작업을 거친다. 이것이 넘어가면 segfault가 발생한다.