[운영체제] Free space

 malloc 과 free 는 명시적 메모리 할당과 해제이고, 할당할 수 있는 크기에 제한이 없기 때문에 다음 두 가지 문제를 해결해야 한다.

1. 페이지 단위로 할당하지 않을 경우 메모리 관리가 힘들다. -> 외부 단편화 문제
2. free 의 인자로 포인터밖에 들어가지 않는데, 몇 바이트인지 알 수 있는 방법이 필요하다.

 malloc 과 free 를 구현하기 위해서는 사용중인 메모리의 상태와 크기를 유지해야 한다. 성능도 O(n) 가 걸리는 방법이 아닌 O(1) 에 처리할 수 있는 방법이 존재한다.

heap fragmentation : 일반적으로 외부 단편화를 말한다.
free list : 힙 영역에서 사용가능한 영역에 대한 list 를 나타내는 자료구조

 연결 리스트를 만들어서 빈 공간에 대한 정보를 갖고 있는다. 메모리의 할당, 해제가 이루어지면서 리스트의 원소 개수가 늘어난다. 리스트의 순서는 메모리 주소의 순서이다. 할당된 메모리의 크기에 대한 정보는 header 가 갖고 있고, list 의 node 는 빈 공간 메모리에 대한 크기를 갖고 있는다. 예를 들어 100바이트를 할당하면 100바이트라는 정보를 갖고 있는 헤더(4바이트)를 할당하고 list 의 head 위치를 바꿔 준다. 할당된 메모리 100 바이트와 header 의 크기 4 바이트가 할당되어 총 104 바이트를 사용하게 된다.

연결 리스트 문제 : 힙을 관리하기 위한 list 를 힙에 구현해야 한다.

typedef struct node_t {
    int size;
    struct node_t *next;
} node;

typedef struct header_t {
    int size;
} header;

 순차적으로 3 개의 메모리가 할당되었다고 가정해 보자. 메모리를 해제할 때는 해제한 메모리가 free list 의 head 보다 주소가 빠르면, 해제한 메모리의 시작 주소를 free list 의 head 로 바꿔주고 원래 원래 head 를 next node 로 연결해 준다. 이렇게 모든 메모리를 해제하고 나면, 사실은 하나의 연속적으로 사용가능한 메모리인데 메모리 영역이 나눠진다. 이 메모링 영역을 합쳐야 한다. 그리고 노드의 각각의 포인터들은 free 를 했지만 사용자가 막 쓸 수 있다는 게 문제라고 하셨는데, free 했으면 원래 막 쓸 수 있어야 하는 거 아닌가? 아니면 free 는 사실 상관 없는 얘기고 list 를 heap 영역에서 관리하는 게 문제라는 걸까...?

 free 문제

리스트를 찾아가며 연속된 두 개의 노드가 비어 있다면 합쳐줘야 한다. sorted list 라면 O(n), 정렬되지 않은 list 라면 O(n^2) 이 걸린다.

malloc 문제

 쪼개진 여러 개의 공간이 있을 경우 어느 곳에 할당하는 것이 좋은가?

first-fit : 할당 가능한 첫 번째 노드에 할당한다. O(1) -> 외부 단편화 문제
best-fit : 할당 가능한 가장 작은 크기의 노드에 할당한다. O(n)

 어떻게 하면 단편화 문제를 해결하며 O(1) 로 만들 것인가?

next-fit

free list 를 circular list 로 바꾼다. first-fit 을 사용하지만 할당 이후 head 의 위치를 바꿔준다. 항상 좋은 것은 아니고 확률적으로 좋아진다.

free

 free list 를 double linked list 로 변경한다. node 에 free(사실 size 의 MSB 에 넣으면 된다.), prev 를 추가해 준다. header 에서 free 를 추가하고, footer 를 새로 만들어 준다. header 위치에서 위치를 살짝 변경해서 이전 노드의 footer 를 찾을 수 있는데, 여기의 size 값을 보고 이전 노드의 header 를 찾을 수 있다.

Coalescing

 next 가 free 라면 합쳐준다. prev 가 free 라면 합쳐준다. O(1). 맨 처음이나 맨 마지막 노드라면 그거에 대한 처리를 따로 해 줘야 한다.

malloc

next-fit 도 여전히 fragmentation 문제가 있다. 두 가지 문제로 해결할 수 있다.

1. 2의 제곱으로 할당한다.
2. 미리 메모리 풀을 만들어 놓고 그것을 반환해 준다.

1. 2의 제곱으로 할당

 만약 2048보다 크면 그냥 페이지 단위로 할당한다. 128 바이트보다 작다면 32바이트의 배수로 할당한다. 메모리 문제는 해결되지만 속도는 개선되지 않는다. 이것을 두 번째 방법과 같이 사용한다.

2. Binning

 각 사이즈별로 free list 를 미리 만들어 둔다. 만약 개수가 부족하다면 더 큰 것을 나누어서 만들어 준다. free 할 때는 원래 상태로 반납한다.

병행성

 malloc 은 list 로 메모리를 관리하기 때문에 병행성 문제가 발생할 수 있다. 병행성 문제는 락을 사용하여 해결할 수 있지만 락을 사용하면 성능이 크게 떨어진다. 그러면 어떻게 해야하는가?

arena : 각 스레드마다 힙을 나눠준다. 각 스레드가 malloc 을 위한 별도의 힙을 사용한다.

 몇 개의 arena 를 미리 만들어 둔다. 스레드 수가 더 많아지면 안 되기 때문에 적절한 수의 스레드를 유지해야 한다.

 일반적으로 malloc 을 직접 구현할 일은 없지만, 만약 malloc 에 이런 내용이 구현되어 있지 않다면 직접 구현하여 사용해야 한다. slab allocation 기법 사용 (object cache) C++ 로 구현하기 쉽다. 슬랩 메모리를 만들고 스택에 push 한다. new 대신 alloc 을 사용한다. 할당은 pop 을 하고 free 는 push 한다. 메모리 누수 문제에 신경써야 한다. free 를 했는데 사용하거나 free 를 두 번 사용하면 안 된다.