13. 힙(Heap)

 

이번 포스터에서는 static과 dynamic이 많이 등장하기 때문에 우선 이 단어들이 무엇을 의미하는지 알아보겠습니다. 먼저 static은 pre-runtime, offline과 동의어입니다. static scheduling처럼 앞에 static이 붙은 경우 pre runtime scheduling으로 프로그램 수행에 영향을 받지 않는 스케줄링을 말합니다. (수행되기 전 오프라인에서 스케줄링을 진행) static code analysis의 경우는 실행되기 전에 코드를 분석하는 것으로 컴파일러가 여기에 해당됩니다.

 

반대로 dynamic의 경우 online과 동의어면서 runtime 중에 동작을 진행합니다.

 

 

static allocation과 dynamic allocation에 대해서 알아보겠습니다. 어떤 global array를 선언할 때 static allocation을 통해서 선언하면 프로그램이 메인 메모리에 올라올 때 array들이 모두 할당됩니다. (처음에 할당되고 프로그램이 끝날 때 반환되는 형태)

 

static allocation의 경우 메모리 낭비가 심하기 때문에 dynamic allocation으로 memory object가 필요할 때마다 할당해 주면 메모리 낭비를 줄일 수 있습니다. 

 

 

 

dynamic allocation 중 stack allocation의 경우 이전 포스터에서 다뤘던 적이 있습니다. 이 방법은 stack의 top에서만 allocation이 일어나기 때문에 function call이나 return에 적용하는 것이 유용합니다. 이런 제약 없이 할당받고 싶다면 heap allocation을 사용하면 됩니다. 

 

 

 

heap allocation은 사용자가 지정한 크기의 메모리 안에서 자유롭게 할당과 해제를 진행할 수 있습니다. heap은 내부적으로 사용 가능한 메모리 공간들이 조각조각 존재하는 free list로 볼 수 있습니다. 

 

 

 

heap에서 memory object를 제공 받을 때 이 memory object는 주소 상 연속적인 memory chunk입니다. 메모리를 계속 할당/반환 하게 되면 heap이 점점 쪼개집니다. 계속 할당되어 있거나 해제되어 비어있는 부분도 존재하는데 이때 빈 공간을 링크드 리스트로 엮어 heap의 메인 데이터 구조인 free list를 만듭니다. 

 

allocation 된 공간 사이에 존재하는 free space를 hole이라고 부릅니다. 사용자가 allocation과 free를 반복할 경우 반환되는 hole의 사이즈는 이전에 비해 작아지므로 hole의 개수는 증가하게 됩니다. hole이 작아져서 이전보다 더 작은 메모리 request만 할당이 가능합니다. 이렇게 hole 개수는 증가하고 hole의 크기가 줄어드는 현상을 파편화(fragmentation)이라고 부릅니다.

 

이 파편화는 heap의 효율을 떨어뜨립니다. 아주 작은 hole들만 존재하게 되면 이 hole들은 어떤 memory request도 수용해줄 수 없게 됩니다. 그리고 heap에서 공간을 차지하고 있기 때문에 그 공간은 사용하지 못합니다. 이런 현상을 internal fragmentation이나 fragmentation이라고 부릅니다. 

 

 

 

이렇게 작은 hole들이 heap 메모리 영역에 흩어져 있는 것을 막기 위해서  buddy allocator, slab allocator, paging 등이 등장했지만 이 기법들은 효율적이지 않습니다. hole들을 체계적으로 관리하기 위해서 free-list로 만들어 관리하는 방법에 대해 알아보겠습니다.

 

 

 

free list management를 통한 파편화 방지는 발견했던 초창기에 사용한 방법입니다. heap의 free list가 있고 hole의 크기가 제각각일 때를 생각해 보겠습니다. 사용자가 malloc request를 하면 free list 중 어떤 hole을 주는가에 따라 2가지로 나뉩니다. 첫 번째는 best fit으로 hole들 중에서 가장 크기에 알맞은 것을 찾아주는 방법입니다. 두 번째는 가장 처음에 request를 만족시키는 hole을 주는 것 방법으로 first fit이라고 부릅니다.  

 

 

두 방법은 상황에 따라 달라지기 때문에 일반화 시킬 수 없습니다. best fit의 경우 계속 진행할 시 hole들의 사이즈가 굉장히 작아지기 때문에 fregmentation이 커지는 상황이 생깁니다. 이런 문제를 해결하고자 worst fit이 나왔습니다. 반환되고 남은 크기가 커져서 fregmentation을 줄일 수 있을 것이라는 기대로 만들어졌지만 효과가 좋지 못했습니다.

 

 

 

hole들을 링크드 리스트로 표현했다고 했는데 이러면 적합한 hole을 찾기 위해서 링크드 리스트 서치를 해야하는 시간적 부담이 생깁니다. 그래서 heap의 memory allocatoin의 기본 단위를 만들었습니다. (32kb, 1kb chunk를 한 단위로 만드는 것), 이 chunk가 사용되고 있는지는 한 bit를 통해 알 수 있습니다. 0이면 사용 중인 것이고 1이면 사용가능하다 이렇게 표현합니다.

 

이런 사용 여부를 표현해 주는 bit는 chunk가 많을수록 늘어나는데 이런 bit들을 bitmap, bit vector라고 불렀습니다. 과거에는 malloc을 하기 위해서 링크드 리스트를 확인했지만 이제는 0과 1로 구성된 문장에서 원하는 패턴을 찾는 방식으로 진행됩니다. (5개의 chunk로 구성된 malloc을 원하면 11111 패턴을 찾으면 됩니다, 파일 시스템에서 자주 사용하는 기법)

 

또 다른 data structure는 free list를 정해진 단위의 hole로 재구성하는 방법입니다. 사용자가 malloc을 할 때 자주 사용하는 크기(1kb, 2kb 등)로 hole들을 만들어두고 bitmap으로 표현하는데 이것을 segregated list라고 부릅니다. segregated list를 사용하면 메모리 얼로케이션 단위가 다 일정하기 때문에 fregmentation 문제를 해결할 수 있습니다.

 

단점으로는 1kb, 2kb, 3kb 크기의 hole들을 만들어 뒀는데 특정 크기 hole만 사용되고 나머지는 사용되지 않아 memory utilization이 낮아지는 경향이 있습니다. 이런 fregmentation 문제는 리눅스에서 사용되는 slap allocation, buddy allocation을 통해서 완벽하게 해결할 수 있습니다.