Explicit 방식의 malloc 구현에 대해 얘기하기 전에, 시스템 콜에 대해 간단히 정리해볼 생각이다.
시스템 콜
시스템 콜: OS(특히 커널)이 제공하는 서비스에 접근하기 위한 상호작용을 말한다.
- 커널(kernel): 메모리에 상주하고 있는 운영체제 핵심 중 일부를 뜻한다. 응용프로그램이 컴퓨터 시스템에서 수행되기 위해서는 메모리에 프로그램이 올라가 있어야 한다. 운영체제 역시 하나의 프로그램으로, 메모리에 올라가야 하는데 OS는 무겁기 때문에 필요한 핵심만 메모리에 올라가 있다. 이 커널은 메모리 하드웨어 등 중요한 자원을 관리하기 때문에 사용자는 이 부분을 건드릴 수 없도록 막혀있다.
- User 모드: 사용자가 응용프로그램을 실행하는 모드. 유저가 접근 가능한 영역은 제한적으로 두고 메모리/하드웨어 등 자원에 함부로 접근하지 못하게 한다.
- Kernel 모드: 운영체제 코드를 실행하는 모드이다. 모든 지원에 접근이 가능하다. 컴퓨터 환경에 치명적인 영향을 끼칠 수 있는 명령을 특권 명령이라 하는데, 이 특권 명령은 커널 모드에서만 실행이 가능하다. 여기에 접근이 불가능한 User모드에서는 안전하게 사용할 수 있다.
Explicit allocation(명시적 할당)
응용프로그램이 직접 메모리를 할당/반환하는 방식의 할당기이다.
Explicit Free list
핵심 아이디어
가용 블록끼리 포인터로 연결해 다음 블록 위치를 명시적으로 알 수 있다.
개요
가용 블록은 header와 footer 말고는 다른 데이터가 없다. 하지만, 할당하게 되면 payload 자리에서 다음 가용블록(successor block)과 가용 블록(predecessor block)의 주소를 저장한다.
- 하나의 이중 연결 리스트를 만들어서 가용 블록을 연결한다.
- 다음 가용 블록은 Implicit 방식과 달리 메모리 내에서 물리적으로 연속적이지 않아도 된다. 주소 상으로 인접 블록이 아니더라도 포인터 주소를 이용해서 위치를 찾아가는 방식이다. 아래의 그림을 보면 실제 메모리에서 할당이 다르게 되어있는 것을 볼 수 있다.
할당
할당할 가용 리스트를 분할한 다음, 아래 그림처럼 새 가용 블록을 기존 가용 블록과 링크되었던 이전(prev), 다음(next) 블록과 연결한다.
가용
새로 반환된 가용 블록을 free 리스트 어디에 연결해줘야 하는가?
LIFO(Last in First Out) 방안
- free list 처음에 새 반환 블록을 넣는다.
- 간단하고 O(1)의 시간 복잡도를 가지나 단편화 발생 확률이 높다.
Address Ordered 방안 - free list를 주소 순으로 연결한다.
- Fragmentation 확률은 낮아지지만, 탐색 시간이 길어진다.(선형으로 찾아가기 때문에 길어짐.)
- Case1: 반환 블록 양쪽이 할당되어 있을 때
- 해당 블록만 가용 상태로 반환하면 되니 추가 작업이 필요 없다.
-
Case2: 반환 블록 직전이 할당블록, 직후가 가용블록일 때.
- 직후 블록을 Free list에서 떼어낸 다음 현재 반환할 블록 뒤로 연결한다.
- 새로 연결한 블록을 free list의 root와 연결한다.
-
Case3: 반환 블록 직전이 가용블록, 직후가 할당 블록
- 직전 블록을 Free list 에서 떼어낸 다음 반환 블록과 연결한다.
- 새 블록을 Free list의 root와 연결한다.
-
Case4: 반환 블록 직전이 할당 블록, 직후가 가용블록
- 3번 케이스와 동일하다. Free list에서 떼어낸 다음에 반환 블록과 연결한다.
- 새 블록을 Free list의 root와 연결한다.
