[운영체제]Free-Space management

paging : 고정된 크기의 메모리 공간으로 나눠 필요한 공간을 할당하는 방법. => 

 

segmentation : 가변적인 길이의 공간으로 나눠 할당. => 요청하는 사이즈가 다 다르기 때문에 유연하게 대처가능. 구현이 어려움.

fregmentation이 발생. external fragmentation이 발생하면 single contiguous 공간이 발생. 중간에 할당은 불가능. 시간과 공간 오버헤드를 고려해야 한다.

 

malloc 과 free 함수

 

Free List

 free할 리스트들을 관리하는 라이브러리가 관리의 대상이 되는 힙. 힙안에 링크드 리스트 같은 리스트를 만들어 관리.

 

compation

한번 메모리에 전달이 되면 재배치를 하지 않는다. 세그멘테이션과 같이 구현할 경우 compation을 같이 구현 가능.

 

low level mechanisms

분할과 병합 메커니즘을 사용. size tracking을 통해 얼마나 할당했는지 확인. 링크드리스트를 어떻게 구현할 것인가.free와 아님을 어떻게 구분?

 

spliting

자유공간 일부를 malloc으로 할당 할때 사용할 부분과 아닌 부분으로 구분. 

 

coalescing(합치다)

사용하던 공간을 반납하고 이웃한 free space들을 확인해 free space이면 merge를 통해 큰 space로 만든다.

free한 후에 사용이 됨.

 

tracking the size of allocated regions

앞에 두개는 어떤 크기인지, 어떻게 보호할 건지, 등의 정보가 없음. 할당하려는 공간에 헤더를 붙여 링크드리스트 관리하는 방법.

magic을 사용해 버퍼오버플로우를 막을 수 있음. 링크드리스트 블럭을 보호하기 위해서 Magic넘버를 사용함. 버퍼오버플로우로 값을 조정하는걸 막기 위해 magic값이랑 비교를 함. 예를 들어 다른 메모리의 쓰레드를 훔쳐쓸수 있음.

 

헤더의 주소는 어떻게 알아내지?

ptr-8아닌가? => ptr이 void일 경우는 가능하지만 ptr이 header_t 타입으로 형변환 필요.

header_t *hptr = (header_t *)ptr - 1; =>1은 header_t 구조체 포인터의 그 전 주소를 의미함.

(header_t *)(ptr-8)로 해도 됨.

assert()는 magic을 읽어서 비교함.

 

free list를 어떻게 만들까?

 

링크드리스트 만들 듯 구조체 하나 만들고 링크드리스트 구현.

 

 

4096바이트(16kb) 중 8바이트만큼의 헤더를 제외하고 4088만큼의 free space가 있음. 그 중 100byte만큼의 메모리를 할당. 헤더의 크기 8바이트는 예외적으로 들어가서 108바이트만큼 할당해야 됨. 그래서 남은 사이즈는 3980. 링크드리스트의 헤더는 남은 free space의 헤더를 가리킨다.

이 후 free선언을 하면 head는 free 부분으로 올라감.

 

공간이 부족하면?

1. malloc이 null을 리턴한다. -> 결과는 별로임.

2.처음엔 작은 힙을 잡은 후 모자르면 운영체제에게 요청을 보낸다. sbrk라는 함수를 사용해 힙 영역 조정가능.운영체제는 sbrk 함수를 통해 새로운 힙 영역에 할당.

 

가장 좋은 방법이 아닌, 기본적인 방법의 장점과 단점.

1.best fit(smallest fit)

free list를 서치하면서 요청된 사이즈보다 큰 것들 중 가장 작은 것을 할당함.

처음부터 끝까지 free list를 모두 확인하기 때문에 시간 복잡도 증가.

 

2.worst fit

현존하는 가장 큰 청크를 찾아 요청된 사이즈 만큼 리턴하고 나머지는 free list에 반납.

8kb로 나눠진 메모리가 있는데 7kb만큼 씩 요청할 경우 1kb씩 free list에 남게된다. 이렇게 작은 청크만 free list에 남게되고, 탐색 시간이 증가하게 된다.

worst fit에 경우 할당하고 남은 양이 커서 다음 요청에서도 재활용될 수 있기 때문에 조금 더 효율적일 수 있음.

요청하는 양에 따라 best fit worst fit 차이가 있음.

free list를 모두 탐색해야 함.  그렇게 좋은 퍼포먼스를 보이지 않음. 

 

3.first fit

요청을 받은 후 처음으로 크기를 만족하는 free list를 리턴. 시간 복잡도가 낮음. 역시 작은 크기의 free list가 계속 생성될 수 있음. 시간이 지날 수록 시간 복잡도가 낮은 장점이 사라짐.

address based ordering : free space의 주소를 바탕으로 list를 정렬, 통합을 쉽게 함. fregmentation을 줄일 수 있음. -> 단점이 해결될 수 있음.

 

4.next fit

링크드 리스트에서 사용하고 남은 공간에 포인터를 할당, 다음에 요청이 발생 시 포인터 부터 탐색 시작. first fit의 단점을 커버할 수 있음. 

전체 탐색을 다시 하지 않아도 됨.

 

요청에 따라 fit별로 어떤 결과가 나올지 공부해보기.

 

segregated list(개별 리스트)

특정한 크기의 요청을 계속 보내면 크기에 맞는 별도의 리스트를 생성. 특화된 지원+일반적인 요청도 지원.

특정한 크기에 적합하기 때문에 fregmentation이 줄어듬. allocate,free 요청을 빠르게 처리.

 

slab allocator

커널이 부팅했을 경우, object cache를 만들어 커널이 자주사용하는 공간만큼의 공간을 할당함.lock,inode,프로세스 구조체 등 커널에서 자주사용되는 공간을 slab allocator에 저장해둠. 요청되는 크기는 페이지 사이즈의 배수, 오브젝트 크기에 맞춰 할당.

reference count가 0일 경우 slab이 더이상 사용되지 않게 되어 allocator 반납하여 가상 메모리가 사용할 수 있게함.

개별 리스트 보다 훨씬 효율적이다. 부팅 당시에 여러 리스트를 만들어 두기 때문에 할당,반납하면서 생기는 시간 복잡도를 줄여주기 때문에 오버헤드가 줄어듬.

 

buddy allocation

coalescing을 단순하게 해줌.

free memory는 2의n승의 형태로 되어 있음. 요청의 크기에 맞을 때까지 free space를 계속해서 2로 나눔. 중요한 점은 합치는 것을 좀 더 편하게 해준다는 점이다. 크기에 맞춰 나눠 배정을 한 후, 남은 쪽(buddy)이 free한 상태인지 확인. 맞으면 병합. 위에서도 buddy가 free한지 확인. 병합 과정을 재귀적으로 구현. 특정한 비트의 차이만으로 확인 가능.