동적 메모리 할당 | Malloc Lab | (1) Malloc은 어떻게 구현되는가?

명시적 할당기, 묵시적 할당기

메모리 할당기는 명시적 할당기(explicit allocator), 묵시적 할당기(implicit allocator)로 나뉜다.

• 명시적 할당기는 malloc, free
• 묵시적 할당기는 가비지 컬렉터

 

 

명시적 할당기 (malloc)

malloc은 힙으로부터 메모리를 할당받는다.

• 만일 sbrk를 사용한다면, 커널의 brk 포인터에 incr을 더해서 힙 공간을 늘리거나 줄인다. 

힙은 블록들로 구성되어 있고, 블록은 워드 단위로 표시된다. (1 워드 = 4byte, 더블 워드 = 8byte)

• 예를 들어서 '4 워드 블록을 요청한다, 6 워드 블록을 요청한다.' 이런 식으로 표현한다. 

malloc을 활용한 프로그래밍을 할 시에 주의 사항이 있다. 

• 메모리 블록을 반환 해주고 난 다음엔 해당 공간을 가리키고 있던 포인터를 꼭 초기화해줄 것!
• malloc 자체적으로 포인터를 초기화해주지 않는다.
• 잘못하면 사용하지 않는 포인터가 프로그램 내부 어딘가를 가리키고 있고, 이를 통해 보안상 위험한 일이 생길수도 있다. 

 

할당기의 제한사항

할당기는 다음과 같은 제한사항을 충족해야 한다. 

1. 랜덤한 요청 순서를 처리할 수 있어야 함. (어떤 요청이 어떤 순서로 들어올지 미리 알 수 없으므로)
2. 즉시 요청에 응답해야 함
3. 힙 공간만 사용해야 함
4. 블록 정렬 요건을 지님
5. 할당된 블록은 수정하지 말아야 함. 블록 압축 기법 등 x

 

할당기의 목표

1. 처리량 극대화하기
   1. 요청은 1) 할당 요청, 2) 반환 요청이 있음.
   2. 만일 각각 500개의 할당 요청을 1초만에 처리하고 다 반환했다면 초당 1000개의 요청을 처리한 것
2. 메모리 이용도를 최대화하기
   1. 가상 메모리 공간은 무한이 아님. 따라서 힙도 최대한 아껴아껴가며 할당받는게 좋음
   2. 이에 따라, 할당받은 힙을 얼마나 채웠는지, 그 비율로 효율성을 따지게 됨

 

최고 이용도(Peak utilization)

할당기가 목표를 얼마나 잘 달성했는지를 측정하는 지표 중 하나가 최고 이용도이다. 

(가정: 요청 수가 늘어날 수록 Heap 영역도 단조 증가한다.)

이 수식을 풀이해보면, 

• 이용도 = (할당된 블록 데이터의 합/할당받은 힙) 비율로 나타낼 수 있음.
• 요청 수가 늘어날 수록 힙도 점차 커진다는 가정에 따라서 점차 분모는 커짐. 즉 처리량과 이용도는 서로 trade off 관계.
• 2차원 그래프를 통해 가장 마지막 요청이 k라고 하면, k번째 요청까지 오는 동안 U의 곡선을 그릴 수 있음. 그 최고점을 최고 이용도(U)로 정의하여, 이 수치가 높을수록 효율적인 할당기라고 부를 수 있다.

 

이용도가 잘 안나오는 대표적인 원인은 단편화 현상이다. 잠깐 복습하자면, 

• 내부 단편화: 할당된 블록이 데이터 자체보다 더 클 때 발생
• 외부 단편화: 힙에 남는 메모리 공간이 충분하긴 한데, 다들 조각조각나있을 경우. (단일한 free 블록이 없는 경우)

 

할당기의 목표는 힙의 이용도를 높이고 처리량을 극대화하는 것인데, 수식 풀이 과정을 통해 처리량과 이용도는 서로 trade off 관계임을 알게되었다. 따라서 빠르게 할당/반환 요청을 처리하면서도, 동시에 힙을 새로 할당받는 작업을 최대한 줄일 것인가 하는 것이 주요 안건이 되겠다. 

 

 

할당기 구현 전략

구현시 고려할 4가지 요소

1. 가용 블록 포맷: 가용(free) 블록을 지속적으로 추적하기 위해 어떻게 할 것인가?
2. 배치: 어디에 새로운 블록을 할당할 것인가?
3. 분할: 새로 할당한 블록을 배치한 후, 가용 블록의 나머지 부분들로 무엇을 할 것인가?
4. 연결: 방금 반환된 블록으로 무엇을 할 것인가?

 

 

1. 가용 블록 포맷

1. 묵시적 가용 리스트(Implicit Free List)

 

Implicit free list는 할당기를 위해 고안된 자료구조이며, 컴퓨터 시스템 책에서는 해당 가용 블록 형태를 먼저 다루고 있다. 

 

해당 자료구조는 1) 블록 경계를 구분하고, 2) 할당된 블록과 free 블록을 구분할 수 있도록 설계되었다. 

 

묵시적 가용 리스트의 구성

• 1워드의 헤더
  • 블록 크기, 할당 플래그(블록의 할당 여부)
• 데이터 (payload 라고도 함)
• 패딩 (경계를 맞추기 위함)

 

정렬 제한 조건 (alignment)

 

정렬 제한 조건과 블록 포맷을 무엇을 선택했는지에 최소 블록 크기가 결정된다. 

만약 블록 포맷을 묵시적 가용 리스트로 선택하고, 정렬 제한 조건을 더블 워드 크기로 정했다고 해보자. 

-> 그럼 각 블록의 크기는 더블워드(8 byte)의 배수여야 한다.

 

그렇게 되면 해당 포맷에서의 블록에서 나올 수 있는 최소 블록은 더블 워드 크기이다. 

(1 워드 크기의 헤더 + 1 워드 크기의 데이터 또는 패딩)

 

Q. 만약 정렬 조건이 더블 워드 기준이고, 9 바이트의 할당 요청이 있다면 헤더에는 어떤 값이 들어갈까?

A. 헤더에는 0x11가 들어간다.
[요청된 크기 = 9] + [헤더 = 4] = [필요한 크기 13]
 → [더블 워드 경계에 맞추기 = 16] + [할당 플래그 +1] = [필요한 크기 17]

(더블 워드 경계에 맞추기: 블록 크기는 8의 배수가 되어야 함. 만약 9 바이트를 담으려면 16바이트를 할당한다.)
시스템은 (헤더 값%8)이 1 인지 0인지를 확인해서 할당여부를 파악 가능하다. 

 

 

이 자료구조를 하나의 블록으로 구성한다면, 힙 공간을 이 블록들의 배열로 표현할 수 있음.

 

 

2. 분리된 가용 리스트(Segregated Free List)

 

Segregated Free List는 가용 블록을 여러 개의 별도 리스트로 분리하여 관리한다.

배치 전략 중 Best-fit과 함께 사용하면 시너지가 좋다.

 

이를 통해 메모리 할당 요청이 들어올 때 적절한 크기의 블록을 빠르게 찾을 수 있다. 예를 들어, 작은 메모리 요청은 작은 블록들을 관리하는 리스트에서 처리되고, 큰 메모리 요청은 큰 블록들을 관리하는 리스트에서 처리된다. 

 

best fit 전략의 장점을 취하면서도 전체 메모리를 검색하는 데 필요한 시간을 줄이는 방식이다. 일반적으로 Segregated Free List는 외부 단편화와 검색 시간을 모두 감소시켜, 메모리 이용도와 속도의 균형을 잘 맞추는 것으로 알려져 있다.

 

물론, Segregated Free List도 관리 오버헤드와 내부 단편화와 같은 단점이 있을 수 있다.

 

해당 블록 구성은 메모리 할당 패턴이 예측 가능하고, 다양한 크기의 메모리 요청이 일반적인 시스템에서 유용하다.

예를 들어, 운영 시스템이나 임베디드 시스템에서 효율적인 메모리 관리를 위해 사용된다.

 

 

2. 배치 전략

어플리케이션이 k바이트의 블록을 요청 → malloc은 요청한 블록을 저장할만한 free 블록을 검색

검색을 수행하는 방법 → 배치 정책(Placement policy)에 의해 결정됨

 

1. First fit

가용 리스트를 처음부터 검색 → 크기가 맞는 첫번째 가용 블록을 선택한다.

(최악의 경우 O(n))

• 장점: 리스트의 마지막에 가장 큰 free 블록들을 남겨두는 경향이 있다는 점
• 단점: 리스트의 앞부분에 작은 free 블록들을 남겨두는 경향이 있음
  • 큰 블록을 찾는 경우 검색 시간이 늘어난다.
  • 앞부분에 짜잘한 free 블록들로 인해 외부 단편화 문제를 야기할 수 있다.

 

2. Next fit

first fit과 유사하나, 검색 시작지점이 다르다. 이전 검색이 종료된 지점에서 검색을 시작한다.

(최악의 경우 O(n))

• 장점: first fit에 비해 매우 빠른 속도를 갖는다. 특히 리스트의 앞 부분이 다수의 작은 조각들로 구성되면 더 이런 성향을 보인다.
  • 할당 패턴이 일정할 때 더 유리하다.
• 단점: 연구결과에 따르면, 특히 큰 메모리 블록의 할당이 필요할 때는 최악의 메모리 이용도를 갖는다. 

 

3. Best fit

모든 가용 블록을 검사하여, 크기가 맞는 가장 작은 블록을 선택한다.

(무조건 O(n))

• 장점: 메모리 이용도를 극대화할 수 있다.
• 단점: 힙을 다 검색해야 한다는 점.

힙을 모두 검색하지 않는, best fit 정책을 단순화한 segregated free list도 있다.

 

 

 

3. 분할 전략

충분한 크기의 가용 블록을 찾았다 → 얼마나 할당할까?

찾은 가용 블록 전체를 할당해주는 방법도 있으나, 내부 단편화가 생긴다는 단점이 있다. 

 

이를 해소하는 옵션 2는 가용 블록을 두 부분으로 나누는 것이다. 

• 할당한 부분은 할당한 블록으로, 나머지는 새로운 free 블록으로 떨어져나간다.

 

추가적인 힙 메모리 요청 (extend heap)

• 만약, 요청한 정도의 블록을 찾을 수 없다면?
  1. 물리적으로 인접한 free 블록들을 연결해서 더 큰 free 블록으로 만든다.
  2. 그래도 안되면, 커널에게 sbrk 함수를 호출해서 추가적인 힙 메모리를 요청한다.
     1. 추가 메모리를 한 개의 더 큰 free 블록으로 변환 → 이 블록을 가용 리스트에 삽입 → 요청한 블록을 이 free 블록에 배치

 

4. 연결 전략 (Coalescing)

오류 단편화(false fragmentation): 분명 공간은 있는데 여러개로 쪼개져있는, 그래서 각각의 free 블록은 작은 경우이다.

 

위 그림의 경우, 가운데 두 블록은 헤더를 제외하면 데이터를 저장할 공간이 3워드 공간밖에 없다. 그래서 4워드를 요청하면 처리하지 못하는 상황이 되어버렸다.

 

 

연결(coalescing)

 

할당기가 할당한 블록을 반환할 때, 새롭게 반환되는 블록에 인접한 다른 가용 블록들이 있을 수 있다.

연결(coalescing)은 이런 인접한 가용 블록들을 통합하는 과정이다. 크게 1) 즉시 연결, 2) 지연 연결로 나뉜다.

1. 즉시 연결: 블록이 반환될 때마다 인접 블록 통합
   • 장점: 간단하며, 상수 시간내 수행 가능
   • 단점: 특정 요청 패턴에서는, 블록이 연결된 다음 바로 다시 분할되는 경우가 발생할 수 있음
2. 지연 연결: 기다렸다가, 특정 조건에서 free 블록들을 연결
   • (ex: 일부 할당 요청이 실패하면, 그때 전체 힙을 검색해서 모든 free 블록 연결 작업 수행)

 

경계 태그(Boundary Tag, Footer) 활용

 

헤더는 해당 블록의 size와 할당 여부 정보를 담고 있다. 연결 리스트 원리와 비슷하게 현재 블록의 헤더가 다음 블록의 헤더를 가리킨다면, 할당기는 헤더를 따라 블록을 순회하면서 상황을 파악할 수 있을 것이다.

 

연결 작업의 경우에도, 다음 블록의 크기를 확인한 다음에, 현재 블록에 다음 블록의 크기를 더해줌으로써 연결 작업을 수행할 수 있다. 

 

확실한 방법이지만, 만일 즉시 연결을 채택한다면 free 요청이 나올 때마다 힙의 크기에 비례하는 시간을 소모하게 된다. 

이를 줄여볼 순 없을까? 해서 블록 포맷에 추가된 것이 경계 태그(Footer)이다.

 

 

경계 태그(Footer)

• 블록 끝 부분에 footer 추가한다. footer는 헤더를 그대로 복사한 것이다. 
• footer는 항상 현재 블록의 시작 부분에서 한 워드 떨어진 곳에 위치한다.
• 장점: footer를 추가하면 양방향에서 빠른 조사가 가능하다. 

 

 

연결 작업 같은 경우에도, 이전 블록과 이후 블록을 함께 조사하여 앞뒤로 가용 여부 판단 및 연결 작업 수행이 가능하다. 

 

 

 

다음은 Footer를 통한 연결 케이스 4가지이다.