[SW정글][Malloc Lab] 동적 메모리 할당

JST·2023년 9월 8일
0

C

목록 보기
6/6

1.동적 메모리 할당

동적 메모리 할당기는 힙 영역을 관리한다.
각각의 프로세스에 대해서 커널은 힙의 꼭대기를 가리키는 변수 brk (break)를 사용한다.
할당기는 힙을 다양한 크기의 블록들의 집합으로 관리한다.
각 블록 => 할당/가용의 가상 메모리의 연속적인 묶음.
할당된 블록은 응용하기 위해 명시적으로 보존됨.

명시적인 할당기 vs 묵시적인 할당기

  • 명시적인 할당기

    응용프로그램이 할당하고 반환한다.
    C 표준 라이브러리는 malloc 패키지라고 하는 명시적 할당기를 제공한다.
    malloc 호출해서 블록 할당 / free 호출해서 블록 반환

  • 묵시적 할당

    응용 프로그램이 할당하지만, 직접 반환하지는 않는다.
    이를 위해서는 더 이상 프로그램에 의해 사용되지 않는 블록을 검출할 수 있어야 한다.
    예시로는 자바의 가비지 컬렉터가 있다.

2. malloc 과 free 함수

malloc 함수는 적절히 정렬된 최소 size 바이트를 갖는 메모리 블록의 포인터를 리턴함.
정렬은 64비트에서 항상 16의 배수인 블록을 리턴한다. (32비트는 8의 배수)

프로그램들은 할당된 힙 블록을 free 함수를 호출해서 반환한다.
free()의 인자로는 malloc에서 획득한 블록의 시작을 가리켜야 한다.

2.1 brk / sbrk

malloc 같은 동적 메모리 할당기는 sbrk 함수를 사용할 수 있다.

#include <unistd.h>

void *sbrk(intptr_t incr);

sbrk 함수는 커널의 brk 포인터에 incr을 더해서 힙을 늘리거나 줄인다.

자세한 내용 클릭

2.2 malloc & free 동작 원리

아래 그림은 c프로그램에서 16워드의 매우 작은 힙을 malloc 과 free가 어떻게 관리할 수 있는지 보여준다.

(b) 에서 malloc은 가용 블록의 앞부분에서 6워드 블록을 할당한다.
이 예제에서 malloc은 가용 블록이 더블 워드 경계에 정렬되도록 하기 위해 블록에 추가적인 워드를 패딩하였다.

32비트 CPU에서 1워드는 4 바이트(32비트) 이고, 64비트 CPU에서는 8바이트(64비트) 이다.

Malloc lab 프로젝트에서는 gcc가 32비트 모드이기 때문에 1 워드는 4 바이트이고, 더블 워드는 8 바이트 객체라고 가정한다.

3. 할당기 요구사항과 목표

요구사항

  • 임의의 요청 순서 처리하기
    - 할당기는 할당과 free가 서로 대응되며 쌍을 이루는지 알지 못한다.
  • 요청에 즉시 응답하기
  • 힙만 사용하기
  • 블록 정렬하기
  • 할당된 블록을 수정하지 않기

목표

  • 처리량 극대화 하기
  • 메모리 이용도를 최대화하기

4. 단편화

메모리 할당 요청을 만족시킬 수 없을 때 일어나는 현상.(나쁜 힙 이용도)

내부 단편화

내부 단편화는 할당된 블록이 데이터 자체보다 더 클 때 일어난다.

위 그림에서 p2는 int 사이즈 5칸을 요청했지만, (malloc lab 프로젝트의 gcc가 32비트 모드이기 때문에) 할당기의 주소가 8바이트(더블워드)의 배수에 맞게 배치되어야 하고, 따라서 1칸(4바이트)을 더 할당하게 된다. (20이 아닌 24 바이트)

외부 단편화

외부 단편화는 할당 요청을 충족하기에 충분한 총 빈 메모리가 있지만, 정렬 문제로 메모리에 할당하지 못 하는 경우 발생한다.

위의 그림을 보면 가용 가능한 블록은 6개가 있다. 즉 총 24바이트의 여유 메모리가 있지만, 4, 2로 나뉘어 있기 때문에 24바이트의 블록을 할당할 수 없다.

외부 단편화는 미래의 요청 패턴의 영향을 받는다. 그렇기에 외부 단편화는 내부 단편화보다 측정하기 어렵고 예측하기가 불가능하다.
이로 인해 할당기들은 많은 수의 더 작은 가용 블록들보다는 더 적은 수의 더 큰 가용 블록들을 유지하려는 방법들을 채택하고 있다.

5. 구현 이슈

처리량과 이용도 사이에 좋은 균형을 갖는 실용적인 할당기는 다음 이슈들을 고려해야 한다.

  • 가용 블록 구성: 어떻게 가용 블록을 지속적으로 추적하는가?
  • 배치: 새롭게 할당된 블록을 배치하기 위한 가용 블록을 어떻게 선택하는가?
  • 분할: 새롭게 할당한 블록을 가용 블록에 배치한 후 가용 블록의 나머지 부분들로 무어을 할 것인가?
  • 연결: 방금 반환된 블록으로 무엇을 할 것인가?

6. 묵시적 가용 리스트

실용적인 할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하는 데이터 구조를 필요로 한다. 대부분의 할당자는 이 정보를 블록 자체에 내장한다.

위 그림은 한 힙 블록의 포멧이다.
한 블록은 1워드의 헤더, 페이로드(데이터), 그리고 추가적인 패딩을 포함한다.

시스템의 정렬 요구 사항과 할당기의 블록 형식 선택이 할당기에게 최소 블록 크기를 부과한다는 것을 이해하는 것이 중요하다. 어떤 할당된 또는 빈 블록도 이 최소 크기보다 작을 수 없다. 예를 들어, 더블 워드 정렬 요구 사항을 가정한다면 각 블록의 크기는 2 워드(8바이트)의 배수여야 한다. 따라서 위 그림의 블록 형식은 최소 블록 크기를 2 워드로 지정한다: 헤더에 1 워드와 정렬 요구 사항을 유지하기 위해 또 다른 워드가 필요하다. 심지어 애플리케이션이 한 바이트를 요청하더라도 할당기는 여전히 2 워드 블록을 생성할 것이다.

헤더

헤더는 블록 크기(헤더와 패딩 포함)와 블록이 할당되었는지 빈 상태인지를 인코딩한다. 더블 워드 정렬 제약 조건을 적용하면 블록 크기는 항상 8의 배수이며 블록 크기의 3개의 최하위 비트는 항상 0이다. 따라서 블록 크기의 29개의 최상위 비트만 저장하면 나머지 3개의 비트를 다른 정보를 인코딩하는 데 사용할 수 있다. 이 경우 이러한 비트 중 가장 덜 중요한 비트(할당된 비트)를 사용하여 블록이 할당되었는지 여부를 나타낸다.(a =1 : allocated, a = 0 : free)

예를 들어, 블록 크기가 24(0x18)바이트인 할당된 블록이 있다고 가정해 보자. 그러면 해당 헤더는 다음과 같을 것이다.

0x00000018 | 0x1 = 0x00000019  (할당 되어서 1 => 0x1)

마찬가지로, 블록 크기가 40(0x28)바이트인 빈 블록은 다음과 같은 헤더를 가질 것입니다.

0x00000028 | 0x0 = 0x00000028  (빈 블록이라 0 => 0x0)

페이로드 & padding

헤더 다음에는 malloc을 호출할 때 애플리케이션이 요청한 페이로드가 있다. 페이로드 다음에는 정렬 요구 사항을 충족하기 위해 필요한 크기의 패딩이 있을 수 있다. 패딩이 필요한 이유는 여러 가지가 있다. 예를 들어, 패딩은 외부 단편화를 해결하기 위한 할당자의 전략의 일부로 사용될 수 있다. 또는 정렬 요구 사항을 충족하기 위해 필요할 수도 있다.

묵시적 가용 리스트(Implicit list)

위 그림과 같은 블록 형식을 갖춘 경우, 힙을 연속된 할당 혹은 연속된 가용 블록의 배열로 아래 그림처럼 구성할 수 있으며, 이를 묵시적 리스트(Implicit list) 라고 부른다.

가용 블록이 헤더 내 필드에 의해서 묵시적으로 연결되기 때문이다.
즉 implicit 방법은 할당된 블록과 가용한 블록이 모두 연결되어 있다.
할당기는 헤더의 크기 필드를 통해 빈 블록의 전체 집합을 간접적으로 탐색할 수 있다.
주의할 점은 특별히 표시된 종료 블록이 필요하다는 것이다.
위 예제에서 종료하는 블록의 헤더는 할당 비트가 설정되어있고, 크기는 0을 갖는다.(맨 마지막 블록)

암시적 빈 리스트의 장점은 간단함이다. 중요한 단점은 빈 리스트를 검색하는 모든 작업의 비용(예: 할당된 블록 배치)이 힙에 있는 할당된 및 빈 블록의 총 수에 선형적으로 비례한다는 것이다.

명시적 가용 리스트(Explicit list)

ecplicit 방법은 가용 가능한 블록끼리만 연결되어 있다.

더보기

7. 할당한 블록의 배치

프로그램이 malloc(k)를 통해 k 바이트의 블록을 요철할 때 할당기는 요청한 블록을 저장하기에 충분히 큰 가용 블록을 리스트에서 검색한다. 검색을 수행할 때 수행하는 정책에 따라 first fit, next fit, best fit 등이 있다.

first fit

가용 free 리스트를 처음부터 탐색하면서 크기가 맞는 첫 번째 가용 블록을 선택한다.

  • 장점 : 리스트의 끝부분에 가장 큰 가용 블록을 남겨두는 경향이 있다.
  • 단점 : 리스트의 앞부분에 작은 가용 블록들을 남겨두는 경향이 있어서 큰 블록을 찾는 경우에 검색 시간이 늘어난다.


static void *first_fit(size_t asize)
{
    void *bp;
    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
    {
        if (GET_SIZE(HDRP(bp)) >= asize && (!GET_ALLOC(HDRP(bp))))
        {
            return bp;
        }
    }
    return NULL;
}

-> 힙의 시작부터, 크기가 > 0일때동안, 즉 에필로그 헤더가 나오기 전까지 다음 블록으로 이동하면서 원하는 크기 이상의 가용 블록을 찾는다. 가장 먼저 찾은 (원하는 크기 이상의 가용)블록을 선택한다.

next fit

first fit과 비슷하지만 검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점에서 검색을 시작한다.
즉, 이전 검색에서 발견한 가용 블록을 발견한 위치에서 탐색을 시작하고 조건에 만족하는 블록이 있으면 해당 블록을 할당한다.

  • 장점 : first fit에 비해 매우 빠른 속도를 갖는다.(특히 앞부분이 많은 작은 크기의 조각들로 구성되었을때.)
  • 단점 : 일부 연구에 의하면 next fit 이 first fit보다 최악의 메모리 이용도를 갖는 것으로 밝혀졌다.


(next-fit은 pointp, 즉 탐색 포인터를 변경해줘야 하기 때문에 find_fit 뿐만 아니라 다른 함수의 코드도 수정해야 한다.)

static void *next_fit(size_t asize)
{
    void *bp;
    void *old_pointp = pointp;
    for (bp = pointp; GET_SIZE(HDRP(bp)); bp = NEXT_BLKP(bp))
    {
        if (!GET_ALLOC(HDRP(bp)) && GET_SIZE(HDRP(bp)) >= asize)
        {
            pointp = NEXT_BLKP(bp);
            return bp;
        }
    }
    for (bp = heap_listp; bp < old_pointp; bp = NEXT_BLKP(bp))
    {
        if ((!GET_ALLOC(HDRP(bp))) && GET_SIZE(HDRP(bp)) >= asize)
        {
            pointp = NEXT_BLKP(bp);
            return bp;
        }
    }
    return NULL;
}
  • 이전 탐색의 종료지점부터, 크기가 0이 아닐 동안, 즉 에필로그 헤더가 나오기 전까지, 다음 블록으로 이동하면서 원하는 크기 이상의 가용 블록을 선택한다.
    탐색 포인터를 현재 선택된 가용 블록 다음으로 설정한다.
  • 이전 탐색의 종료지점부터 찾았는데 사용할 수 있는 블록이 없다면, 다시 앞에서부터 이전 탐색의 종료지점 전까지 이동하면서 선택한다.
    탐색 포인터를 현재 선택된 가용 블록 다음으로 설정한다.

best fit

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

  • 장점 : 일반적으로 first fir이나 next fit 보다는 더 좋은 메모리 이용도를 갖는다.
  • 단점 : (묵시적 가용 리스트 같은) 단순한 가용 리스트 구성을 사용해서는 힙을 완전히 다 탐색해야 한다. (segregated free list 사용하면 해결)


static void *best_fit(size_t asize)
{
    void *bp;
    void *best = NULL;
    for (bp = free_listp; GET_ALLOC(HDRP(bp)) != 1; bp = GET_NEXT(bp))
    {
        if (asize <= GET_SIZE(HDRP(bp)))
        {
            if (best == NULL)
            {
                best = bp;
            }
            else if (GET_SIZE(HDRP(bp)) <= GET_SIZE(HDRP(best)))
            {
                best = bp;
            }
        }
    }
    if (best != NULL)
    {
        return best;
    }
    return NULL;
}

가용리스트 시작부터 마지막 블록까지 다음 블록으로 이동하면서 원하는 크기 이상인 블록 중 가장 작은 블록을 찾아서 선택한다.

8. 가용 블록의 분할

  • 할당기가 크기가 맞는 가용 블럭을 찾은 후에 가용 블록의 어느 정도를 할당할지에 대해 정책적 결정을 내려야한다.
  • 가용 블록 전체를 사용할 수 도 있지만 내부 단편화가 생긴다.
  • 따라서 가용 블록을 두 부분으로 나누어 요청한 크기의 블록에는 메모리를 할당하고 나머지는 새로운 가용 블록을 만든다.

9. 추가적인 힙 메모리 획득하기

  • 할당기가 가용 리스트를 탐색했지만 요청한 크기의 블럭을 찾을 수 없는 경우
    • 메모리에서 물리적으로 인접한 가용 블록들을 합쳐서(연결해서) 더 큰 가용 블록을 만들어 본다.
    • 그래도 충분히 큰 블록이 만들어지지 않는다면
      • 할당기는 커널에게 sbrk() 를 호출 (시스템콜) 추가적인 힙 메모리를 할당한다.
      • 할당기는 추가 메모리를 한 개의 큰 가용 블록으로 만들고, 이 블록을 가용 리스트에 삽입한 뒤, 요청한 블록을 새로운 가용 블록에 배치한다.

10. 가용 블록 연결하기(오류 단편화)

할당기가 할당한 블록을 free 할 때 반환되는 블록에 인접한 다른 가용 블록들이 있을 수 있다.
추가적으로 할당할 때 인접한 블록을 연결하면 사용할 수 있지만, 현재는 나눠져 사용할 수 없는 상태의 블록이 되고 이것을 오류 단편화(false fragmentation)이라고 한다.


위 그림에서 할당된 블록을 반환한 결과는 아래 그림과 같다.

위 그림을 보면 중간에 3워드 블록이 2개가 인접해있다. 이 때 4워드만큼 할당을 요청하면 가용한 메모리의 크기는 충분하지만 가용 블록이 2개로 나뉘어 있어 요청을 만족시키지 못한다.

이런 오류 단편화를 극복하기 위해 인접한 가용 블록을 하나로 병합하는 과정이 필요하다 (Coalesce).
=> 언제 연결을 수행할지가 중요.

  • 블록이 반환 될 때 마다.(즉시 연결)
    • 간단하며 상수 시간 O(1) 내에 수행.
    • 일부 요청 패턴에 대해서는 블록이 연결되고 잠시 후 다시 분해되는 비효율 형태(쓰래싱).
  • 일정 시간 후에 가용 블록들을 연결하기 위해 기다림.(지연 연결)
    • 일부 할당 요청이 실패할 때 까지 연결을 지연. 그 후 전체 힙을 검색해서 모든 가용 블록 연결.

11. 경계 태그 (연결 구현)

경계태그는 할당기가 연결을 구현할 때 사용된다.
블록이 Header만 있을 때는 다음 블록과 연결할 때는 상관이 없다.
그러나 이전 블록과 (상수 시간으로 효율적으로) 연결하기 위해서는 경계 태그(footer) 가 필요하다.

현재 블록과 다음 블록 연결하기

  • 현재 블록 다음 블록은 현재 블록의 헤더를 통해 쉽게 크기와 할당 여부를 확인할 수 있다.
    • 현재 블록의 헤더는 다음 블록의 헤더를 가리키고 있으며, 이를 통해 다음 블록이 가용한지 체크
    • 다음 블록의 크기는 현재 헤더의 크기에 더해짐
    • 블록은 상수 시간 O(1)내에 연결 됨.

현재 블록과 이전 블록 연결하기

  • Knuth의 경계 태그(footer)를 이용하면 이전 블록도 상수 시간 내에 연결이 가능하다.
  • 각 블록에 끝 부분에 footer를 추가해준다. 이 footer는 헤더(블록의 크기, 할당 여부)를 복사한 것이다.
  • 할당기는 시작 위치와 이전 블록의 상태를 자신의 footer를 조사해서 알 수 있다.
  • 풋터는 항상 현재 블록의 시작 부분에서 1 워드 떨어진 곳에 있다.
  • footer는 4byte 크기이다.

즉, 경계 태그(footer)를 사용해 이전 블록의 정보를 쉽게 알 수 있다.

모든 경우들

  1. 이전과 다음 블록이 모두 할당되어 있을 때.

  2. 이전 블록은 할당상태, 다음 블록은 가용상태일때.

  3. 이전 블록은 가용상태, 다음 블록은 할당상태일때

  4. 이전 블록과 다음 블록 모두 가용상태일때.

단점과 개선방안

단점

  • 결국 새로운 메모리를 header와 footer에 할당해야하므로, 메모리 오버헤드가 발생한다.
    (특히 많은 작은 크기의 블록을 다룰 때)
    (오버헤드 : 어떤 처리를 하기 위해 들어가는 간접적인 시간 & 메모리)
    개선 방안
  • 메모리 오버헤드 단점을 극복하기 위해 이전 블록이 가용한 경우에만 (이전 블록에) footer를 사용하는 것이 좋다.
  • 현재 블록의 남은 하위 비트 중 하나에 이전 블록의 할당/빈 상태를 저장한다면 할당된 블록은 footer가 필요하지 않으며 그 추가 공간을 페이로드로 사용할 수 있다. 그러나 빈 블록은 여전히 푸터가 필요하다.

12. 프롤로그 / 에필로그 블록

malloc 함수를 구현할 때 프롤로그 블록(Prologue Block)과 에필로그 블록(Epilogue Block)은 힙(heap) 메모리 내의 관리 블록을 나타낸다. 이러한 블록은 할당 및 해제된 메모리 블록 사이의 메타데이터를 관리하고 힙의 구조를 유지하기 위해 사용된다.

  • 프롤로그 블록
    프롤로그 블록은 힙의 시작 부분에 위치하며, 힙에 대한 정보를 포함한다. 일반적으로 프롤로그 블록은 힙의 크기와 할당 여부 등의 정보를 저장하며, 힙의 시작 지점을 나타낸다. 프롤로그 블록은 헤더와 풋터로만 구성된 8바이트 할당 블록이다. 프롤로그 블록은 할당되지 않은 상태로 남아 있으며, 실제 사용자 데이터를 저장하지 않는다.

  • 에필로그 블록
    에필로그 블록 (Epilogue Block): 에필로그 블록은 힙의 끝 부분에 위치하며, 할당 가능한 빈 공간의 크기를 나타낸다. 에필로그 블록은 헤더만으로 구성된 크기가 0으로 할당된 블록이다. 에필로그 블록은 힙의 끝을 나타내는 역할을 하며, 실제 사용자 데이터를 저장하지 않는다. 이 블록은 힙 확장 및 축소 작업에서 유용하게 사용된다.

할당기는 기본적으로 항상 프롤로그 블록을 가리킨다.

(위 그림에서 첫 번째 워드는 더블 워드 경계로 정렬된 미사용 패딩 워드이다.)

13. expand_heap() & coalesce()

extend_heap()에서 기존 에필로그 헤더를 할당 해제 시키고 새로운 에필로그 헤더를 만드는 방법

extend_heap에서 mem_sbrk를 통해 새로운 블록을 생선한다고 해도 리턴되는 값은 old_brk이다.
이 old_brk는 이전 에필로그 헤더를 가리키고 있다.
이때 PUT(HDRP(bp), PACK(size,0)); 를 통해 이 헤더는 0으로 초기화되면서 새로운 블록의 헤더가 되고, 이 헤더부터 chunksize 만큼의 뒤는 footer가 된다.
그리고 그 다음 블록은 새로운 에필로그 헤더가 된다.
이렇게 기존 에필로그 헤더를 할당 해제 시키고 새로운 에필로그 헤더를 만든다.

profile
JST
이전 포스트

[SW정글][Malloc Lab] Explicit Free Lists

0개의 댓글