Daily Heap #10

juuun0·2022년 4월 19일
0

Heap-A-to-Z

목록 보기
10/10
post-thumbnail

Unsorted Bin

Unsorted Bin은 정확하게 size로 구분할 수는 없습니다. Unsorted Bin의 사용 목적은 cache memory와 같이 중간에서 잠시 정보를 저장하여 처리 속도를 증가할 수 있도록 도와줍니다. 따라서 fastbin을 제외한 smallbin과 largebin size의 freed chunk는 먼저 unsorted bin에 저장됩니다.

새로운 chunk를 할당하고자 할 때 unsorted bin에 적합한 chunk가 존재할 경우 해당 chunk를 재사용 합니다. 여기서 '적합함' 의 기준에는 두 가지가 있습니다.

  1. 요청된 크기와 일치하는 크기의 chunk
  2. 요청된 크기보다 더 큰 크기의 chunk

1번 기준의 경우 다른 heap을 할당할 때도 해당되는 조건이기 때문에 별도의 설명이 필요하지 않습니다. 그러나 2번 조건을 이해하기 위해서는 'remainder chunk'의 개념에 대해 이해할 필요가 있습니다.

Remainder Chunk

Remainder chunk가 발생하는 이유는 2번의 이유 때문이기도 합니다. 만약 요청된 size보다 큰 chunk를 반환할 경우 이 과정에서 여분의 크기가 생기게 됩니다. 따라서 실제로 반환되는 chunk의 영역은 요청된 크기와 동일한 만큼만 반환하고 나머지 크기는 쪼개서 다른 chunk로 생성합니다. 이때 쪼개져 남은 chunk를 remainder chunk 라고 합니다.

추가로 가장 최근에 생성된 remainder chunk를 지칭하는 'last remainder chunk' 라는 용어도 존재합니다.

사실 이러한 개념이 왜 존재하는지 궁금증이 생길 수 있습니다. 무엇보다 인터넷에 remainder chunk의 개념에 대해 찾아보면 종종 접할 수 있는 설명이 있습니다.

작은 사이즈의 할당 요청이 들어왔을 때, Free chunk가 쪼개지고 남은 chunk* 연속된 작은 사이즈의 할당 요청이 들어왔을 때 비슷한 주소에 heap chunk가 할당되는 할당의 지역성을 유지하기 위해 사용된다.

위 내용에서 집중해야 할 내용은 '지역성' 입니다. 해당 개념은 heap에 한정되는 내용이 아니기 때문에 컴퓨터 공학의 개념에서 참고할 수 있습니다. 관련된 내용은 링크에서 참고할 수 있으며 이를 요약하자면 다음과 같습니다.

이전에 사용하였던 메모리 공간을 최대한 재활용하여 처리 속도를 단축시킨다.

How it works

Unsorted bin은 size로 구분된 것이 아니기 때문에 smallbin, largebin size 모두 존재할 수 있습니다. 그러나 계속 unsorted bin에 계속 보관할 수 없기에 1회 이상 검색된 후에는 원래 해당되는 bin으로 이동하는 과정을 거칩니다.

이때 검색이라고 함은 해당 chunk가 적합한지 비교하는 과정을 거쳤는가를 기준으로 합니다. 즉, 1번부터 10번까지 chunk가 존재할 경우 1번부터 시작하여 순차적으로 검사할 때 4번 chunk가 적합하다면 이를 user에게 반환하고 1번부터 3번까지의 chunk는 smallbin 혹은 largebin으로 반환됩니다.


마치며

"Daily Heap" 시리즈는 우선 여기서 마무리 할 예정입니다. 본업에 투자할 시간이 더 필요하기도 하며 코드를 모두 분석하기보다 'How to heap' 과 같이 이미 정리되어 있는 자료를 참조하며 예제를 푸는 편이 더 적합하다고 생각되었기 때문입니다.

profile
To be

0개의 댓글