07. 운영체제 - Memory Virtualization(2)

Segmentation

Base-and-Bounds Approach

앞선 게시글의 base-and-bounds 방법에는 문제점이 있다.

이전에 단순화를 위해 가정했던 "모든 프로세스가 같은 사이즈이다" 라는 가정을 제거해보자.

프로세스의 주소공간을 physical memory에도 연속적으로 올리기 때문에 base와 bound만 알면 되었고, 모든 프로세스가 같은 사이즈라면 다른 프로세스가 종료되어 생긴 free space를 또 다른 프로세스가 그대로 채워줄 수 있기 때문에 문제되지 않았다.

하지만 위의 가정이 없어지면 큰 프로그램을 올릴 때 문제가 생긴다.

그만큼의 연속된 free space가 physical memory에 존재하지 않으면 프로그램을 올리기 힘들어진다.

또한 중간중간 작고 분산된 free space가 생기는 fragmentation 문제가 심각해진다. 조각조각의 free space를 모으면 큰 공간이지만, 연속된 프로그램을 올리기엔 각각이 너무 작아서 사용하지 못하는 external fragmentation이 발생할 수 있다.

 

Segmentation

Segment는 address space의 연속된 부분이다. 

Code, Heap, Stack은 logical하게는 서로 다른 세그먼트이다. 

그리고 각 세그먼트는 physical memory의 다른 부분에 위치할 수 있고, 각 세그먼트마다 base, bound를 두면된다.

이렇게 전체 address space를 연속적으로 저장하기보다는 각 세그먼트만 연속적으로 저장하면 physical memory utilization이 높아진다. 

Segmentation을 적용했을 때 주소 변환은 다음과 같이 이루어진다.

Physical address = offset + base address

이때 offset은 segment 내에서 원하는 주소의 offset으로, virtual address와 다르다.

code segment의 경우에는 address space의 0번째 주소부터 시작하기 때문에 virtual address와 offset이 동일하지만, 다른 segment들의 경우에는 두 개가 같지 않기 때문에 구분하여 사용해야한다.

이것을 physical memory 상에서 segment의 base 주소에 더하면 physical address가 만들어진다.

 

Segmentation Fault 

segment의 범위를 벗어나는 주소값 접근이 이루어지면 OS는 segmentation fault를 생성한다. (주솟값이 범위를 벗어나는 것에 대한 탐지는 하드웨어가 수행함)

Stack Segment

스택은 Heap과 반대 방향으로 쌓인다. 따라서 추가적인 하드웨어의 도움이 필요하다.

하드웨어는 segment가 어떤 방향으로 자라는지를 확인하며, 자라는 방향에 대한 정보를 담고있다. (EX. 0이면 음수방향, 1이면 양수방향으로 증가함)

Segment Sharing

Segment는 주소공간 간에 공유될 수 있다.

예를 들어 하드웨어의 지원 하에 Code 세그먼트가 공유될 수 있다.

또한 세그먼트가 공유되면 권한에 대한 문제를 해결하기 위해 Protection bits이 추가될 필요가 있다.

이 protection bits를 통해 읽기/쓰기/실행 등의 권한을 설정해줄 수 있다.

x86 Segment Registers

Fine-Grained & Coarse-Grained

Fine-Grained Segmentation은 segment를 잘게 쪼개어 physical memory를 남는 부분이 거의 없이 사용하는 것이고,

Coarse-Grained Segmentation은 segment를 적은 수로 굵직굵직하게 나누는 것이다.

• Coarse-Grained segmentation 은 code / heap /  stack 처럼 전체 주소공간을 적은 수의 세그먼트로 크게크게 나누는방법이다. 하드웨어에 부담은 적지만 External fragmentation 문제가 발생할 수 있다. 따라서 실행되는 프로세스가 적고, 오래 실행될 때 좋은 방식이다.
• Fine-Grained segmentation 은 사용할 수 있는 상황이 좀 더 범용적이지만 하드웨어의 지원이 더 많이 필요하다.

이 두 방식은 무엇이 더 좋다기 보다는 상황에 따라 더 나은 것을 선택하여 사용할 수 있다.

External Segmentation

external segmentation은 physical memory에 작은 free space 들이 여기저기 존재하는 것이다. 따라서 전체적으로는 free space가 충분하지만, 이어져 있지 않아 새로운 segment를 할당하기 어려워지는 문제가 발생한다. 

Compaction

physical memory의 segment들을 빈공간 없이 이어붙이는 작업이다. 주기적으로 compaction을 실행하면 남은 free space들이 연속적으로 이어지기 때문에 external fragmentation 문제를 한순간 해소할 수 있지만, 매우 비싼 작업이다.

왜냐하면 모든 프로세스를 멈추고 데이터를 다른 곳에 복사해둔 뒤 모든 segment register 값(base, bound)들을 수정해주어야하기 때문이다. 

 

Free space Management

Splitting

free space list에 요청한 메모리 공간보다 더 큰 free space 조각이 있을 때, 조각을 두개로 splitting 하는 것이다. 

위와 같이 10바이트짜리 free space chunk두개가 있을 때, 1byte만큼의 메모리할당이 필요하다면, 조각 하나를 1바이트와 9바이트로 나누어 1바이트를 할당해준다. 그러면 새로운 9byte짜리 free space chunk가 생긴다.

Coalescing

free space chunk보다 더 큰 메모리에 대한 요청이 들어오면, list에서 알맞은 청크를 찾지 못한다.

그러면 두 free chunk가 이어져있는 경우, 두 chunk를 합쳐 더 큰 chunk를 만든다. 이것이 coalescing이다.

Free

C 에서의 free 인터페이스는 포인터값만 받고 데이터의 사이즈에 대한 정보는 인자로 받지 않는다.

그러면 free가 호출되었을 때 얼마만큼의 사이즈를 free list로 추가할지 어떻게 알 수 있을까?

대부분의 allocator들은 메모리에 header block을 유지하며 헤더 안에 메타데이터들을 저장해둔다.

이 헤더 안에 할당된 메모리 공간의 사이즈가 들어있고, 추가적으로 메모리 해제를 빠르게 하기위한 포인터들과 intergrity check을 위한 magic number를 포함할 수 있다.

free가 호출되었을 때 할당해제되는 사이즈는 유저에게 할당된 메모리의 사이즈에 헤더의 사이즈를 더한 만큼이 된다.

free 함수 내에서 할당 해제할 포인터가 주어졌을 때, 헤더의 포인터를 찾는 방법은 간단하게 다음과 같이 이루어질 수 있다.

• header_t* header_ptr = free_ptr - sizeof(header_t)

header_t는 헤더를 의미하는 구조체이고 free_ptr은 free 함수에 인자로 받는 할당 해제할 포인터이다.

 

Growing the Heap

대부분의 allocator들은 처음에 heap의 공간을 조금만 할당했다가, 할당받은 공간을 다 쓰면 sbrk(), brk() 등의 시스템콜을 이용하여 Heap의 공간을 늘린다. 

 

Managing Free Space

메모리 할당 요청이 들어왔을 때, free list에서 어떤 free space chunk를 사용할 것인지 선택하는 전략에는 다음 방법들이 있다. 

1. Best Fit : 요청보다 크거나 같은 free chunk를 모두 찾고, 그 중에 가장 작은 것을 선택하여 그곳에 할당한다.
2. Worst Fit : 전체 free list 중 가장 큰 free chunk에 새로운 요청을 할당한다.
3. First Fit : free list를 쭉 순회하며 요청보다 큰 free chunk를 찾으면 해당 chunk를 사용한다. 
4. Next Fit : First Fit과 동일하게 요청보다 큰 첫번째 chunk를 찾지만, 처음부터 순회하는 것이 아니라 이전 호출에서 돈 곳부터 시작하여 순회한다. 왜냐하면 이전 호출에서 돈 곳의 전까지는 모두 이전 호출자가 찾은 free chunk보다 작을 것이기 때문이다.

Best Fit의 경우에는 공간을 해제하여 free list에 집어넣을 때는 그냥 아무 곳(ex 맨뒤)에나 넣으면 되기 때문에 O(1) 이지만, free list 에서 적절한 chunk를 선택할 때는 모든 chunk를 살펴야하므로 O(N)이 걸린다.

Worst Fit의 경우에는 free list에 max heap 자료구조를 사용하면, 새로운 chunk를 집어넣을 때 O(log N)이 걸리지만, free list에서 가장 큰 chunk를 선택해 뺄 때는 O(1)이 걸린다.

 

위의 4가지 방법 이외의 또 다른 방법으로는 Segregated List가 있다.

Segregated List

이 방법은 여러 개의 리스트에 비슷한 범위의 사이즈를 갖는 free chunk들을 모아두는 방식이다. 

Slab Allocation

Slab은 동일한 규격의 널빤지와 같은 것으로, 메모리를 동일한 사이즈로 미리 나눠놓은 memory pool을 관리하는 방법이다. 빈번하게 malloc, free가 일어나는 경우 유용하게 사용될 수 있다.

Buddy Allocation

요청을 수용할 수 있는 최소한의 크기가 될때까지 free space를 반으로 나눈 후 결과 사이즈만큼을 할당하는 방식이다.

이렇게되면 메모리가 2의 제곱수만큼씩 할당되기 때문에 coalese가 쉬워진다. 

하지만 만약 예를 들어 33KB의 메모리 요청이 들어오면, 64KB를 할당해주어야하므로 나머지 31KB는 할당된 메모리가 되지만 사용되지 않는 internal fragmentation 문제가 심각해질 수 있다.