[OS] Main Memory(2) - Memory Allocation

Process를 Memory에 할당하는 방식은 

Contiguous Allocation과 Non-Contiguous Allocation방식으로 나눌 수 있다.

 

 

Contiguous Allocation

"Contiguous Allocation"이란,

Process를 Memory의 한 곳에 연속적으로 Load하는 방식이다. 

 

Memory Protection

OS와 User 모두 Memory를 사용할 수 있기 때문에,

Main Memory는 OS를 위한 공간과 User Process를 위한 공간으로 나눈다.

 

따라서 User Process를 OS를 위한 Kernel Space를 침범하면 안되며, 

다른 Process의 영역도 침범해서는 안된다. 

 

즉, Process가 자신이 소유한 범위를 넘지 않도록 할 필요가 있다. 

 

따라서, 이는 Runtime Binding과 함께 쓰이는 기법인 "Memory Protection"이 사용되며,

Memory Protection은 MMU 내부의 Limit Register와 Relocation Register가 담당한다. 

Contiguous Allocation의 RunTime Binding

Limit Register는 Logical Address의 범위에 대한 정보를 가지고 있다. 

Relocation Register는 Logical Address에 Base Address값을 더해 Physical Address로 변환해 준다. 

 

Memory Allocation

연속할당 기법은 크게 2가지로 나뉜다. 

• 고정분할 방식
• 가변분할 방식 

 

고정 분할 방식

"고정 분할 방식"이란, 

물리적 Memory를 정해진 개수만큼 분할하여, 

각 Partition에 하나의 Process를 Load하는 방식이다.

하나의 Partition에는 하나의 Process만 Load될 수 있기 때문에,

Partition이 Process크기보다 큰 경우 남는 공간이 생기게 된다. 

이러한 빈공간을 "Internel Fragmentation"이라 부른다.

 

또한, Process B의 경우 전체 Memory 측면에서 보자면 할당될 수 있지만, 

맞는 사이즈의 Partition이 없기 때문에 할당할 수 없다. 

이렇게 맞는 사이즈의 Partition을 찾을때까지 생기는 빈공간을 "Externel Fragmentation"이라 부른다.

예를 들어, Process B가 2, 3번 Partition에 맞지 않아 건너 뛰게 되고, 

4번 Partition에 공간이 맞아 할당된다면, 

2, 3번은 빈 Partition이 되고 이것이 Externel Fragmentation이다.

 

가변 분할 방식

Program의 크기를 고려하여 Partition의 갯수와 크기가 동적으로 변한다. 

메모리에서 사용 가능한 공간을 "Hole"이라 하는데,

새로운 Process가 생성되면 Hole 중 가능한 공간에 들어가게 된다. 

따라서, OS는 Process가 이미 할당된 Partition의 정보와 Free Partition(Hole)에 대한 정보를 알고 있어야 한다.

 

가변분할 방식에선 가장 적절한 Hole을 찾을 필요가 있는데, 

이러한 Hole을 찾는 문제를 Dynamic Storage-Allocation problem이라 부른다. 

 

Dynamic Storage-Allocation Problem에는 3가지가 존재한다. (Process의 size를 n이라 가정하자)

• First Fit : size가 n이상인 Hole 중 가장 첫 번째 Hole에 할당
• Best Fit : size가 n이상인 Hole 중 가장 작은 Hole에 할당
• Worst Fit : size가 n이상인 Hole 중 가장 큰 Hole에 할당

 

가변분할 방식에선 Partition을 프로그램의 사이즈에 따라 가변적으로 할당하기 때문에,

Internal Framentation은 발생하지 않는다.

 

반면, 총 Hole의 크기는 충분하지만, 연속적이지 않기 때문에 생성된 Process가 할당되지 못하는 경우,

Externel Framentation이 발생한다.

 

Externel Fragmentation의 경우, Compaction을 통해 해결이 가능하다.

"Compaction"이란, Hole들을 모아 하나의 큰 Block으로 만드는 방법이다. 

하지만, 이는 Cost가 비싼 작업이다.

 

 

Uncontiguous Allocation - Paging

"Paging"은 Uncontiguous Allocation 중 하나로,

Process가 메모리에 연속적으로 할당되지 않고, 분산되어 할당될 수 있다.

 

Paging에선, Process Image를 "Page"라는 고정된 크기로 자른다.
또한, Memory도 Page와 같은 크기로 자르며, 각 조각을 "Page Frame"이라 부른다.

 

모든 Page는 Disk에 위치하고 있다가, 

Program이 시작되면 하나 이상의 Page가 Memory로 Load되고,

이후 필요한 Page는 Disk에서 Memory로 Load된다. 

 

Address Translation Scheme

Logical Address를 Physical Address로 변환할 때, Page단위로 변환이 된다. 

따라서, 특정 Process에 몇 번째 Page인지에 대한 정보와 

각 Page의 주소 변환 정보를 포함해야 한다. 

 

Paging에선 Logical Address를 "Page Number"와 "Page Offset"로 나눈다.

• Page Number : 몇 번째 Page인지에 대한 정보
• Page Offset : Memory상에서 Offset 

 

Page Table

Page는 Main Memory에 연속된 공간이 아닌 아무 곳이나 할당될 수 있다. 

따라서, CPU는 해당 Page의 Physical Address을 알기 위해 Page Table을 사용한다.

 

Page Table은 Process마다 고유하게 할당되며,

Process내의 Page 개수만큼 Entry를 가지고 있다.

 

Logical Address의 "Page Number"는 Page Table상의 index를 의미하며,

해당 index에는 Physical Memory상의 Base Address에 대한 정보를 가지고 있다. 

변환 작업은 Page Number를 통해 Page Table에 접근하여 Base Address값을 가져오고, 

Base Address와 Page Offset을 더해 실제 메모리에 접근하게 된다.

 

Page Table은 Memory에 위치하며, 
"Page-Table Base Register(PTBR)"가 Page Table을 가리킨다. 

따라서, Page Table은 CPU만 접근이 가능하기 때문에

Paging 기법은 Runtime Address Binding만 가능하다.

즉, MMU는 전환 시 Page Table에 접근해야 한다.

 

 

TLB

앞서 말했듯, Page Table은 Main Memory에 위치한다.

따라서, Page Table의 정보를 확인하기 위해 Memory에 접근하고, 

실제 데이터를 가져오기 위해 Memory에 접근한다. 

즉, 두 번 메모리에 접근하는 Overhead가 생기게 된다.

 

이를 해결하기 위해 "TLB(Translation Look-aside Buffer)"라는 Cache Memory를 사용한다.

TLB에 해당 Page Number에 대한 Frame Number(Base Address정보)가 존재한다면, 

이를 TLB Hit이라 부른다. 

없는 경우 Page Table에 접근하여 가져오게 되며, 

이를 TLB Miss라 부른다.

 

예를 들어 Memory Access Time을 1, TLB에서 검색하는 시간을 $\epsilon$, Hit Ratio를 $\alpha$라 가정하자. 

Hit ratio란 TLB Hit 확률을 의미한다. 

 

만약, TLB에서 원하는 데이터를 찾았을 때, 이를 가지고 메모리에 접근한다. 

따라서 TLB에 접근하는 시간과 메모리접근 시간을 더해 줘야 한다. 

(1 + $\epsilon$) $\alpha$

 

또한, TLB Miss의 경우 Page Table의 접근 시간, TLB의 접근 시간, Memory 접근 시간을 더해 주어야 한다. 

(1 + 1 + $\epsilon$) (1 - $\alpha$)

 

따라서, 최종 Effective Access Time은 다음과 같다.

(1 + $\epsilon$) $\alpha$ + (2 + $\epsilon$) (1 - $\alpha$) = 2 + $\epsilon$ - $\alpha$

 

N-Level Page Table

만약 32bit Processor라면 4GB의 Address Space를 갖는 Process를 만들 수 있다. 

이때, 각 Page가 4KB의 사이즈라면, 1M개의 Page Table Entry가 필요하다.

Entry의 Size가 4B라면, Process 하다 당 4MB의 Page Table이 생성된다.

 

Page Table의 사이즈가 점점 커질수록 메모리에 다 올리기는 힘들어지기 때문에,

Page Table의 사이즈를 줄일 필요가 있다.

 

N-Level Page Table은

Page Table의 사이즈를 줄이는 방법 중 하나로, 

Page Table을 Page로 단위로 자른 뒤,

유효한 Entry가 없다면 Memory에서 제거하는 방식이다.

 

따라서, Page단위로 잘린 Page Table들을 관리할 수 있는 또 다른 Page Table이 존재해야 하며, 

이를 "Outer Page Table"이라 한다.

 

즉, Inner Page Table과 Outer Page Table로 나눠 계층 구조를 통해 관리한다.

2-Level Page Table은 Outer와 Inner Page Table로 관리하고, 

3-Level Page Table은 2개의 Outer와 하나의 Inner Page Table로 관리한다.

Outer Page Table은 조각난 Page Table의 위치를 가리키며, 

해당 Page Table의 Entry가 사용되지 않는다면 Null값을 통해 Memory에서 제거할 수도 있다.

 

Level이 많아질수록,

더 적은 Page Table Size로 관리할 수 있게 되지만, 

접근하는 데 있어서의 Overhead는 점점 커지게 된다.

 

Hased Paged Table

Hash Page Table은 다음과 같이 수행된다. 

• Logical Address의 Page Number(p)는 Hash Function을 거치게 된다. 
• Hash Function의 결과물인 p'은 Hash Table에서 offset을 의미한다. 
• 각 Hash Table의 Entry는 Linkined List를 가지고 있다.
• Linked List에서 Page Number(p)와 일치하는 값을 찾을 때까지 탐색한다.
• 일치하는 값을 찾으면 Frame Number를 Physical Address로 매핑한다.
• Physical Address를 통해 Memory에 접근한다.

 

Inverted Page Table

Process마다 하나의 Page Table을 가지고 있기 때문에.

Process의 갯수에 따라 Page Table 갯수가 늘어난다. 

이는 Memory 공간의 부족으로 이어질 수 있다. 

 

"Inverted Page Table"은 이를 해결하기 위한 방법으로,

시스템 전체에 하나의 Page Table만을 둔다.

"Memory의 Page Frame"과 "Page Table의 Entry"를 1:1로 매핑한다.

즉, Logical Address에 대한 Page Table이 아닌, 

Physical Address에 대한 Page Table이다.

 

Logical Address는 Process ID(pid)과 Page Number, Page Offset에 대한 정보를 포함하고 있으며, 

Page Table의 Entry는 pid와 Page Number를 소유하고 있다. 

 

Inverted Page Table은 다음과 같이 수행된다. 

• Page Table에서 pid와 Page Number가 같은 Entry가 나올 때까지 탐색한다. 
• i번째 Page에서 Entry를 찾았다면, Frame Number는 i가 된다.

Inverted Page Table은 하나의 Page Table만 존재하면 되기 때문에, 

Memory 공간 측면에서 장점이 있다. 

 

하지만, Memory 공유가 불가능하다.

Process ID와 Page Number는 각 Page마다 고유한 정보이기 때문에, 

Page Table Entry로 1:1로 매핑이 된다. 

따라서, 각 Frame은 같은 Process라 할지라도 공유가 불가능하다.

또한, Inverted Page Table에선 모든 Page Table을 탐색해야 하기 때문에,

시간적 손해를 보게 된다.

 

Shared Pages

"Shared Page"란 공유 코드를 담고 있는 Page들을 의미한다.

여러 Process에서 공유할 수 있는 Page이기 때문에, 메모리에 한 번만 Load된다.

이를 통해 Memory를 효율적으로 사용할 수 있다.

 

Memory Protection

Page Table의 각 Entry는 Frame Number만 가지고 있는 것이 아닌, 

Protection Bit와 Valid-Invalid Bit를 가지고 있다.

• Protection Bit : Page에 대한 접근 권한 (Read-Only, Read-Write, Execute-Only)
• Valid-Invalid Bit : 해당 Page의 내용이 유효한지 (Valid의 경우, Memory에 해당 Page 존재함을 의미)

 

Pros & Cons

Pros

Process는 Page단위로 잘리게 되고, 

Memory 역시 Page단위로 나뉘게 되므로,

External Fragmentation이 생기지 않는다.

 

또한, Paging이 요구될 때 Memory에 Load하기 때문에 효율적이다.

 

Cons

Program의 사이즈가 Page의 크기의 배수가 아닐 경우, 

마지막 Page에선 Internal Fragmentation이 생길 수도 있다.

그렇다고 너무 작게 Page를 가져가면, Page Table의 Entry가 많아질 수 있다.

 

 

Uncontiguous Allocation - Segmentation

"Segmentation"은 Uncontiguous Allocation 중 하나로, 

Process Image를 의미 단위의 Segment로 나누어 Physical Memory에 Load하는 방식이다.

 

Segment는 논리적 단위이기 때문에,

Process Image 전체가 Segment가 될 수도 있고, 

각 의미 있는 단위(Data, Stack, Heap...)가 Segment가 될 수도 있다. 

즉, Segment의 크기가 균일하지 않다.

 

Segment Table 

Segmentation에선, 주소 변환을 위한 Segment Table이 존재한다. 

하나의 Segment는 Memory에 연속적으로 할당이 되기 때문에, 

메모리 보호를 위해 Segment Table의 각 Entry는 base를 가지고 있다.

• base : Physical Memory에서 Segment 시작 위치
• limit : Segment의 길이

Segment의 크기가 균일하지 않기 때문에, Segment의 길이에 대한 정보도 포함해야 한다.

 

또한, Logical Address는 Offset과 Segment Number로 구성되는데, 

Segment Number는 Page Number와 같이 Segment Table상의 index가 된다.

Segment Table 역시 Memory상에 위치하기 때문에, 

Segment Table의 Memory상의 위치를 가리키는 "STBR(Segment-Table Base Register)"와,

Program에서 얼마큼의 Segment가 있는지에 대한 정보를 저장하는 "STLR(Segment-Table Length Register)"가 필요하다.

 

Address Translation

우선, Logical Address의 Segment Number이 STLR 미만의 값인지 확인한다. 

아니라면 Exception을 통해 메모리 접근을 방지한다. 

 

다음으로, Logical Address의 값의 Offset값이 Limit(Segment의 길이)보다 작은 값인지 확인한다.

만약 크다면, (Segment의 길이보다 Offset이 크다면)

이는 잘못된 접근이므로 Exception을 통해 메모리 접근을 방지한다.

STLR : Segment 갯수에 대한 Register 
Limit : 하나의 Segment의 크기 (Segment는 크기가 다를 수 있기 때문에, 각 Segment마다 있는 정보)

Pros & Cons

의미 단위인 Segment로 공유되기 때문에, 공유 측면에서 효율적이다. 

또한 Segment를 의미단위로 나누어져 있기 때문에

Protection 측면에서도 효율적이다.

 

하지만, Segmentation에서 Segment크기가 균일하지 않기 때문에, 

External Framentation 문제가 발생하며,

Dynamic Storage Allocation Problem(first fir, worst fit...)이 존재한다.

 

 

References

Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』