Malloc-lab 구현하기

0. 서론

Malloc-lab은 C언어에서 사용되는 malloc, free, realloc을 직접 구현해 보는 과제이다.

이는 메모리 할당자와 가상 메모리에 대한 이해를 필요로 하는데, 컴퓨터시스템 9장을 읽어가며 진행했다.

과제를 통해 얻어가야 할 내용은 다음과 같다.

  • 가상 메모리의 개념과 중요성 이해하기
  • 메모리 할당자의 개념과 할당 방식, 구현 형태 이해하기
  • 패딩, 단편화 등과 같이 메모리 할당자를 구현하면서 만날 수 있는 이슈들에 대해 이해하기

1. 주소 공간

모든 프로그램은 메모리에 적재되어 프로세스가 될 때 자신만의 주소공간을 가진다. 주소공간은 해당 프로세스가 사용하는 격리된 메모리 공간을 의미하며, 일반적으로 한 프로세스가 다른 프로세스의 주소 공간을 건드릴 수 없다. 이를 통해 프로세스 간에 데이터를 보호할 수 있게 된다.

주소 공간은 실제 물리 메모리에 위치한 물리 주소 공간과 가상 메모리에 위치한 가상 주소 공간으로 구분되는데, 둘은 서로 다른 크기일 수 있으며, 어느 하나가 반드시 큰 크기를 가지지도 않는다. 즉, 물리 주소 공간보다 가상 주소 공간이 더 클 수도 있으며 그 반대도 가능하다. 그러나 중요한 것은 가상 메모리 상의 가상 주소 공간과 물리 주소 공간이 서로 대응(mapping)된다는 점이다.

가상 주소 공간은 항상 0부터 시작하게 되며, 크게 코드(Code)/데이터(Data)/스택(Stack)/힙(Heap) 영역으로 나뉠 수 있다. 따라서 프로세스들은 서로 같은 가상 주소상에 데이터를 저장할 수 있으며, 이 때 가상 주소가 같더라도 실제 물리 주소는 프로세스마다 서로 다르게 매핑되어 있다.

2. 가상 메모리

시분할 시스템(Time sharing system) 하에서 여러 프로세스는 실행을 위해 메모리에 적재되어 있어야 한다. 그러나 이 때 프로세스가 실행되기 위해 모든 정보가 메모리에 존재해야만 하는 것은 아닌데, 현재 실행 중인 작업에 연관된 정보들만 메모리에 올라와 있으면 되기 때문이다. 따라서 프로세스들의 모든 정보를 메모리에 올리는 것 보다 각 프로세스 별로 필요한 정보들 만을 메모리에 올리게 되면 한 번에 수행할 수 있는 프로세스의 수가 많아질 뿐만 아니라 필요 시 특정 프로세스에 충분한 크기의 메모리를 할당해 줄 수 있기 때문에 효율적인 자원 사용이 가능해진다.

OS는 프로세스의 특정 메모리들만을 가져오기 위해 주소공간을 분할해 저장하는데, 이 때 주소공간을 일정한 크기로 분할하는 것을 페이징(Paging), 가변적인 크기로(정확히는 세그먼트별로) 분할하는 것을 세그먼테이션(Segmentation)기법이라 한다.

분할된 정보들은 사용될 경우 메모리에 적재되며, 미사용될 경우 보조 기억 장치의 특정 영역에 저장되게 된다. 이후 필요할 때마다 메모리로 적재하게 되는데 이를 스왑 인(Swap in)이라 하고 반대로 메모리의 정보를 보조 기억 장치로 내리는 것을 스왑 아웃(Swap out)이라 한다.

3. 동적 메모리 할당과 구현 목표

주소공간 안의 세그먼트 중 힙 영역은 사용자가 런타임에 원하는 만큼의 크기를 할당할 수 있는 세그먼트이다. 이처럼 런타임에 메모리를 할당받는 것을 동적 메모리 할당(Dynamic Memory Allocation)이라 하는데, Malloc-lab은 동적 메모리 할당을 수행하는 할당기를 구현하는 과제이다.

Malloc-lab은 다음과 같은 명세를 가진다.

  • 임의의 요청 순서 처리하기

    할당과 해제가 반복될 때, 임의의 순서로 할당/해제 요청이 들어 오더라도 처리할 수 있어야 한다.

  • 요청에 즉시 응답하기

    할당/해제 요청이 들어올 시 바로 해당 작업을 수행해야 한다.

  • 힙만 사용하기

    확장성을 위해 할당기가 사용하는 비확장성 자료 구조들은 모두 힙에 저장되어야 한다.

  • 블록 정렬하기

    할당기는 블록들을 이들이 어떤 종류의 데이터 객체라도 저장될 수 있도록 정렬해야 한다.

  • 할당된 블록을 보존하기(수정하지 않기)

    한 번 할당된 블록은 별도의 해제 요청이 있기 전까지 할당기가 직접 블록 안의 정보를 수정/이동하거나 해제해선 안 된다.

Malloc-lab은 구현 이후 테스트를 통해 할당기의 효율성과 처리량을 측정할 수 있다. 만약 $n$번의 할당과 반환 요청이 주어졌을 때 이들을 1초만에 완료한다면 해당 할당기의 처리량은 $n$이 되는 것이다. 반면 효율성은 메모리를 얼마나 덜 낭비하는지를 나타내는 척도이다.

메모리를 덜 낭비한다는 것은 단편화를 최소화한다는 뜻과 동일하다. 이를 위해서 할당 블록 배치 시 몇 가지 정책을 적용할 수 있는데 이는 다음과 같다.

  • First fit

    가장 주소가 낮은 가용 블록부터 순서대로 탐색하며 할당을 원하는 크기보다 더 큰 첫 번째 가용 블록에 메모리를 할당하는 방법

  • Next fit

    First Fit과 비슷하나 마지막으로 작업한 블록 이후부터 탐색을 수행하는 방법

  • Best fit

    모든 가용 블록을 조사한 후 할당하고자 하는 크기와 가장 잘 맞는(Fittest) 블록을 할당하는 방법

이러한 정책들과 함께 외부 단편화를 최소화하기 위해 인접한 가용 블록들을 연결(Coalesing)하는 과정이 추가적으로 필요한데, 이 때 임의의 가용 블록 앞에 존재하는 블록에 접근하기 위해 각 가용 블록의 끝에 Footer를 추가한다.

반대로 너무 큰 블록을 작은 할당 요청에 대응해 할당해 줄 경우에는 내부 단편화가 발생하게 된다. 이를 막기 위해 특정 블록의 나머지 영역을 할당된 영역과 분할함으로써 새로운 가용 블록을 생성해 주어야 한다.

또, 최대한 단편화를 해결한다 하더라도 할당할 수 있는 블록이 충분히 존재하지 않을 수도 있는데, 이 경우는 추가적인 힙 메모리를 획득해서 할당해 주어야 한다. 이는 커널에게 sork함수를 호출함으로써 달성할 수 있다.

앞서 설명한 Footer와 함께 각 블록들을 연결하기 위해 별도의 경계 태그를 삽입할 수 있다. Footer 역시 경계 태그의 구성 요소이며, Footer와 구분되어 블록의 앞에 붙는 경계 태그를 Header라 한다.

경계 태그를 포함한 블록의 형식은 아래와 같다.

지금까지 살펴본 정보들을 이용해 할당기를 구현할 수 있다.

구현 코드는 링크를 참조하자.