TIL 011 동적 할당 메모리 (malloc lab)

CMU 카네기멜론의 malloc lab: http://csapp.cs.cmu.edu/3e/labs.html

구현 깃헙: github 링크

메모리 관리는 정답이 없다. general 몇 가지 방법이 있지만, 다양한 메모리 관리 기술은 다른 결과를 가진다. 개발자로서 적절한 메모리 관리 기법을 이해하는 것은 언젠가 큰 도움이 될 것 같다.

📕 Malloc

malloc이란 c의 동적 메모리할당, dynamic memory allocation을 의미하며, 컴퓨터의 가상메모리 (virtual memory),즉 heap을 관리한다. 메모리를 할당시키고 프리(free)시키며 메모리를 정확하고, 효율적이고, 빠르게 관리하는 것이 핵심이다.

Check for correctness, efficiency and performance.

동적 할당이 필요한 이유는 프로그램이 얼마만큼의 메모리가 필요한지 모르기 때문이다. 처음부터 프로그램이 필요한 메모리를 너무 많이 할당하면 효율성이 떨어질 것이고, 너무 적은 메모리를 할당한다면 프로그램에 에러가 난다.

👉 Fragmentation

메모리 단편화는 메모리 조각이 효율적으로 사용되지 못하고 낭비되는 상황을 말한다.

• Internal fragmentation
  할당 된 메모리 블록 안에서 낭비가 일어나고 있음을 말한다. 프로세스에서 요구한 메모리보다 더 큰 메모리를 할당했을 때 일어난다.
  

• External fragmentation
  할당 된 메모리 블록 사이에서 낭비가 일어나고 있음을 말한다. 할당 된 메모리들 사이에 빈 메모리 공간이 남아있을 때 일어난다.
  

👉 Header, Footer

메모리 할당 시에 블록 양 끝의 블록에 Allocated 여부와 블록의 size를 담아둔다. 정확한 메모리를 할당시키고 프리시키는 것은 프로세스가 제대로 돌아가는데에도 중요하지만 메모리 관리 측면에서도 중요하다. 메모리를 빈 공간에 할당시키거나, 프리시킬 때, 헤더와 푸터를 통해 정확한 양을 알 수 있고, 메모리들 사이에서 적절한 공간을 찾을 때도 유용하다.

메모리 블록의 1 word 는 8byte이기 때문에, 메모리의 사이즈는 8의 배수로 이루어진다. 이를 2진법으로 표기하면 8byte는 1000, 16byte는 10000, 24byte는 11000으로 뒤의 3자리가 비는 것을 알 수 있다. 이곳에 allocated,tag 등의 정보를 담을 수 있기 때문에 헤더와 푸터가 size와 allocated 정보를 담는데 1블록으로 충분하다.

👉 Implicit, Explicit, Segreagated

• Implicit은 모든 block을 연결시킨다.
  그래서 탐색하는데 블록 갯수만큼의 연산이 필요하다.
  

• Explicit은 모든 free block을 연결시킨다.
  그래서 탐색하는데 프리 블록의 갯수만큼의 연산이 필요하다. 이 때 프리 블록들은 이중리스트로 연결되어있어야한다. 메모리는 최소 4word, 16[byte]의 크기를 갖는데, 이는 헤더와 푸터 그리고 전 블록 주소, 다음 블록 주소를 이중리스트로 담기 위함이다. 할당된 블록은 연결을 끊음으로 전 블록 주소, 다음 블록 주소를 담을 필요도 담을 공간도 필요가 없다.
  새로운 블록을 stack처럼 맨 앞으로 LIFO 구조로 연결 시킬 수 있고, 블록의 주소값 순서로 정렬시켜 연결시키는 방법이 있다.
  

• Segregated는 size 별로 따른 free list를 만들어서 각 메모리 사이즈 별로 관리한다.
  그래서 가장 빠른 탐색속도를 가진다. buddy list 방법이 가장 대표적으로 2의 승수별로 블록 사이즈를 나누어 각각 연결해준다. 탐색시에는 들어가 블록이 속해 있는 클라스부터 탐색하기 시작해서 더 큰 사이즈 클라스쪽으로 전부 탐색하면 된다.
  

• 블록을 size로 sort시키거나, B트리를 사용하는 방법도 있다.

👉 First fit, Next fit, Best fit, Good fit

• First fit은 처음부터 출발해, 적절한 블록을 만나면 그 블록을 선택한다.
  탐색은 가장 빠르지만, 최적의 메모리 사용은 아닐 확률이 있다.
  

• Next fit은 저번 탐색 지점을 기억해, 그곳에서 출발해 충분한 블록을 만나면 그 블록을 선택한다.
  최근 사용한 메모리를 위주로 비할당시킬 확률이 높다면 유리할 수 있다. 최적의 메모리 사용은 아닐 확률이 있다.

• Best fit은 처음부터 출발해 모든 블록을 탐색한 뒤, 가장 적절한 블록을 선택한다.
  완전 탐색을 해야하지만, external fragementation은 줄일 수 있다.
  

• Good fit은 처음부터 출발해 일정 블록을 탐색한 뒤, 가장 적절한 블록을 선택한다.
  완전탐색하기에는 메모리가 너무 클 때, 적절선의 합의점을 찾을 수 있다.
  

👉 Coalescing

헤더와 푸터의 정보를 이용해서, 블록이 프리되었을 때 양 옆의 블록을 체크해서 합쳐준다. (더 큰 메모리의 빈 메모리는 활용도가 높다). 다만, 사용되는 메모리 사이즈들이 모두 작다면 헤더,푸터의 존재로 인해 internal fragmentation이 늘어나는 역효과가 날 수 있다.

Coalescing은 다음 네 가지 case를 가진다. 이에 따른 결과도 다르고, explicit list을 합쳐질 블록이 다른 블록과 링크되어 있음으로 구현할 때 신경 써줘야한다.

• case1: 앞 뒤 모두 할당 되었을 때 -> 그냥 독립적인 블록
• case2: 앞은 프리 뒤는 할당 -> 앞에 블록과 합쳐준다.
• case3: 앞은 할당 뒤는 프리 -> 뒤에 블록과 합쳐준다.
• case4: 앞 뒤 모두 프리 -> 앞뒤 블록과 합쳐준다.

👉 Splitting

메모리 할당 시에 남은 파편을 다시 할당되지 않은 블록으로 사용한다. 이를 통해 internal fragmentation을 방지한다.

👉 Reallocate

이미 할당 된 메모리를 다른 곳에 옮긴다. 이를 통해 다양한 중간에 작은 메모리로 인해 나뉘어져 있던 메모리를 하나의 큰 메모리로 활용시킬 수 있다. 또한 프로세스가 기존 메모리보다 많은 메모리를 필요로 할때 기존 데이터를 옮기고 추가 메모리를 붙여서 할당시킬 수 있다.

하지만, 이를 위해 새로운 힙을 할당 받아야 할 수도 있다. 이를 방지하기 위해 만약 뒤에 빈 메모리의 크기가 충분하다면 새로운 곳으로 옮기지 않고 뒤의 메모리를 할당 시킬 수도 있다. 그러나 이럴 때 메모리가 점점 작아지면서 external fragmentation이 더 일어날 수도 있다.

👉 구현

github 링크

• Implicit
  implicit를 구현할 때는 헤더와 푸터를 통해 다음 블록을 바로바로 방문한다. 헤더의 size를 활용해서 바로 다음 블록으로 접근하고 헤더의 allocated를 통해 프리 블록인지 판단한다.
  그리고, coalesce를 해줄 때 네 가지 케이스를 고려해 블록의 주소와 사이즈를 변경시킨다.
  first fit을 적용하였다.
  

• Explicit
  explicit은 LIFO로 구현하였다. 앞뒤 이중을 연결을 끊고 블록을 독립적으로 만드는 함수 하나와(앞뒤 블록은 서로 연결시켜준다.), 새로운 블록을 맨앞으로 보내는 하나는 함수로 구현하였다. 이때 다음 연결이 없을때와 root일 때를 예외 처리 해주어야 한다.
  best fit을 적용하면 속도 점수가 떨어져서, first fit으로 구현하였다. LIFO로 구현했기 때문에 Next fit의 효과도 있다고 생각한다.
  

• Segregated
  segregated는 32개의 주소를 담는 배열을 할당 받는다. 2의 32승을 승수로 나누기 위함이고, 32비트의 시스템이기 때문이다.
  메모리를 할당할 적절한 프리 블록을 찾을 때, 새로운 프리 블록을 할당 시킬 때, 이 때 적절한 segregated list를 찾아야 한다.
  메모리를 할당할 적절한 프리 블록을 찾을 때는 내 size에 맞는 주소부터 시작해서, 모든 segreagated list를 훑어야 한다. 그 때도 없다면 새로운 heap을 할당받는다.
  Segreagted는 속도가 가장 빠르기 때문에 best fit을 적용해도 높은 속도를 얻을 수 있었다.
  하지만, best fit이 무조건적으로 util 올려주지는 않는다. 오히려 딱 맞는거에 가까운 메모리를 사용함으로써 작은 메모리들을 split해 external framentation을 일으킬 수 있다. best fit은 generally 메모리 효율을 향상시킨다.