알아야 할 개념들

메모리 단편화, 메모리 할당 정책, 시스템 콜, sbrk/mmap

컴퓨터 시스템 9.9장을 읽으며 알아야 할 필요성을 느낀 개념들

묵시적 / 명시적 동적 메모리 할당기
sbrk, padding
할당기 요구사항과 목표
내부/외부 단편화
묵시적 가용 리스트 - 힙 블록
할당한 블록 배치
즉시 연결/지연 연결
경계 태그
묵시적 / 명시적 가용 리스트

순서대로 정리해 보겠다.

묵시적/명시적 할당기

우리가 이번 주에 만들어야 할 동적 메모리 할당기가 바로 명시적 동적 메모리 할당기이다. malloc 함수를 통해 heap영역 내에 메모리를 할당하며, free 함수를 통해 할당했던 메모리를 반환한다. 이 때 할당한 메모리를 반환하지 않으면 heap영역내 메모리가 계속 남아있게 되어 메모리 누수를 일으킨다.
묵시적 동적 메모리 할당기는 반대로 할당된 블록들이 더 이상 사용되지 않는다는 것을 할당기가 검출하여 알아서 반환한다. 가비지 콜렉터라고도 부르며 자동으로 사용이 끝난 블록을 반환하는 작업을 가비지 컬렉션이라고 부른다.

sbrk

가상메모리 영역 내의 heap영역은 heap의 시작 주소부터 brk 포인트의 주소까지 정의된다. 즉 brk는 heap영역이 여기까지임을 나타내주는 포인트이다. sbrk라는 함수는 이 brk 포인트의 위치를 밀거나 당길 수 있게 해주는 함수인데, 인수로 heap을 얼마나 늘릴지를 나타내는 incr를 받는다. sbrk를 이용해 heap영역 내에 더 이상 할당가능한 빈 공간이 없을 때 heap영역 자체를 늘려서 동적 메모리 할당이 가능하다. 단 줄이는 것은 늘이는 것보다 훨씬 까다로우며 컴퓨터 시스템에 나와있는 묵시적 가용 리스트 방식에서는 다루지 않는다.

mmap

mmap함수는 munmap과 쌍을 이루는 함수이다.(마치 malloc과 free처럼)
역할은 커널에 새 가상메모리 영역을 생성해줄 것을 요청하는 함수이다. 가상메모리의 영역은 mmap함수와 munmap함수를 이용해서도 생성하고 삭제할 수는 있지만 동적 메모리 할당기를 이용하는 것이 더 편리하다.

시스템 콜

시스템 콜은 여기서 어느정도 정리 했으므로 여기서는 메모리 할당에 시스템 콜이 필요한 이유만 정리하겠다.
응용프로그램은 직접 하드웨어를 건드릴 수 없으며 반드시 운영체제(커널)를 거쳐서 하드웨어를 조작해야한다. 메모리를 할당하는 것 역시 하드웨어를 조작하는 일이기 때문에 응용프로그램은 시스템 콜을 통해서 제어를 커널 모드로 넘긴 후에 메모리 할당을 할 수 있게 된다.

할당기의 요구사항과 목표

요구사항

1. 임의의 요청 순서 처리하기.
   요청 순서에 상관없이 어떤 요청이 오더라도 할당과 반환이 가능해야 한다.
   데이터 객체 a -> b -> c 순서로 왔을 땐 할당에 성공했지만, b -> c -> a 순서로 왔을 땐 할당에 실패하면 안 된다고 이해했다.

2. 요청에 즉시 응답하기
   어떤 종류의 데이터 객체라도 저장할 수 있도록 하는 방식으로 정렬해야 한다.
   사실 메모리를 가장 효율적으로 쓰려면 동적 메모리 할당 요청들을 크기 순서대로 정렬한 후 할당하는 것이 제일 좋다. 하지만 그렇게 하지 않고 요청이 들어오는대로 메모리를 할당하는 방식으로 이루어져야 한다.

3. 힙만 사용하기
   힙 자체에만 저장되어야 한다.
   힙을 넘어선 다른 영역을 이용하면 안 된다고 이해했다. 이를 위해 힙 영역 내 단편화를 줄이고, sbrk 함수를 사용해 힙 영역의 크기를 관리해야 한다.

4. 블록 정렬하기
   어떤 종류의 데이터 객체라도 저장할 수 있는 방식으로 정렬해야 한다.
   CPU의 구성과도 연관된 문제인데, 64bit CPU는 한 클럭에 64bit, 8바이트씩 정보를 처리할 수 있다. 그렇기 때문에 64bit CPU에서는 데이터를 한 블록에 8바이트씩 정렬해서 내부 단편화를 감수하더라도 더 빠르게 데이터를 처리할 수 있기 때문에 블록을 알맞게 정렬하는 것이 중요해진다.

5. 할당된 블록을 수정하지 않기
   할당기는 가용블록을 조작하거나 변경할수만 있다. (데이터 자체에는 손댈 수 없다.)

목표

할당기의 목표는 처리량 극대화와 메모리 이용도 최대화 인데 이 둘은 서로 상충하는 성격을 가지고 있다.
처리량 극대화는 일정 시간 안에 최대한 많은 할당요청과 반환요청을 처리할 수 있는가인데, 이는 단순히 생각하면 매우 큰 저장공간 안에 데이터를 들어오는 대로 할당하고, 반환하는 식으로 할당기를 작성한다면 극대화 할 수 있지만 메모리는 매우 낭비될 것이다.
반대로 메모리 이용도 최대화는 최대한 낭비되는 메모리 없이 데이터를 할당하고 반환하면 이룰 수 있는 목표지만 이를 위해 메모리를 탐색하고 연결하는 작업에 시간이 소요될 것이다.

단편화

가용 메모리가 할당 요청을 만족시킬 정도로 가용되지 않았을 때 일어나는 현상이다.
1. 내부 단편화
할당된 블록이 데이터 자체보다 더 클 때 일어난다. 내부 단편화는 정량화하기 간단하다. 오히려 할당기의 정렬 방식 때문에 패딩이라고 부르는 내부 단편화를 일부러 발생시키는 경우도 있는데 이는 외부 단편화를 극복하기 위한 방법일 수 있다.
2. 외부 단편화
할당요청을 만족시킬 수 있는 메모리 공간이 전체적으로는 충분하지만, 이 요청을 처리할 수 있는 단일한 가용블록은 없는 경우 발생한다.

이를 측정하기 어려운 이유는 외부 단편화는 미래의 요청 패턴에 의해서도 발생할 수 있기 때문이다.
외부 단편화가 측정하기 어렵고 예측 불가능하기 때문에 할당기들은 많은 수의 작은 가용블록보다 더 적은 수의 더 큰 가용블록들을 유지하려는 방법을 채택하고 있다. (외부 단편화가 더 까다롭기 때문에)

묵시적 가용 리스트 (implicit)

동적 데이터 할당을 위해 할당된 블록과 가용 블록을 구분하는 데이터 구조이다.
하나의 블록은 1워드 크기의 헤더, 데이터, 패딩으로 구성된다.
헤더에는 블록의 크기와 블록이 할당되었는지 가용상태인지를 인코딩한다.
정렬 제한 조건이 더블워드인 경우에는 블록의 크기는 항상 8의 배수 바이트이다. 이 때문에 블록 크기를 나타내는 값의 아래 3자리는 항상 0이 되는데 여기에 이 비트의 할당 상태를 표시한다.
예시로, 더블워드 정렬 조건하에서 2바이트 만큼의 데이터를 위하 할당한 공간의 크기는 8바이트가 된다. (헤더 1블록(4바이트) + 데이터 2바이트 + 정렬을 위한 패딩 2바이트) = 8바이트

묵시적 가용 리스트 방식의 장점은 단순성이다. 힙 영역 내를 순서대로 탐색하여 할당 영역과 가용 영역을 탐색할 수 있다. 단점으로는 가용 리스트를 탐색하는 비용이 힙이 커질수록 같이 커진다는 것이다.

할당한 블록을 배치하는 방법

first fit

가용 리스트를 처음부터 순서대로 탐색하다가 할당해야 하는 데이터보다 더 큰 가용 블록을 만났을 때 거기에 데이터를 할당하는 방법이다.
이 방법의 장점은 리스트의 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있다는 것이다.
반대로 단점은 리스트의 앞 부분에 작은 크기의 가용 블록이 (반환되어) 생기는 경향이 있어서 큰 블록을 찾는 경우에 검색 시간이 늘어난다.

next fit

가용 리스트를 처음부터 탐색하는 것이 아니라 이전 탐색에서 할당한 블록 다음부터 탐색을 시작하는 방식이다.
장점은 first fit보다 훨씬 빠르지만, 단점으로 메모리 이용도가 나쁠 수 있다.

best fit

힙 영역을 전부 탐색하고 할당해야 하는 데이터가 들어갈 수 있는 가용 블록 중 가장 작은 것을 찾아 할당하는 방식이다.
장점으로는 최고의 메모리 이용도를 가질 수 있지만, 단점으로는 할당할 때 마다 힙을 완전히 탐색해야 한다는 것이다.

각각의 방식은 전부 장단점을 가지고 있고 그 단점을 어느정도 보완하기 위한 방식 역시 연구되었다. 예를 들어 first fit의 가용 리스트를 처음부터 순서대로 탐색해야 한다는 단점은 explicit list 방식에서 리스트 내의 가용 영역만 처음부터 탐색하는 방식으로 어느정도 해결할 수 있다.

즉시 연결과 지연 연결

할당기가 할당했던 블록을 반환할 때, 블록에 인접한 다른 가용 블록들이 있을 수 있다. 이러한 가용 블록들은 정렬과 헤더 때문에 전체적으로는 충분한 크기임에도 불구하고 메모리 할당이 불가능한 현상을 발생시키는데 이를 false fragmentation이라고 부른다.
이러한 현상을 극복하기 위해 연결이라는 과정으로 인접 가용 블록들을 통합해야 할 필요가 있다.
연결에는 블록이 반환될 때 마다 인접 블록을 통합하는 즉시 연결 방식과 일정 시간 후에 가용 블록을 연결하는 지연 연결 방식이 존재한다. 빠른 처리를 위해선 즉시 연결이 요구되지만 가령 3바이트 크기의 데이터 할당과 반환을 연속적으로 실시하는 경우, 지연 연결 방식에서는 적당한 크기의 블록 안에 데이터의 할당과 반환을 반복하면 되지만 즉시 연결만 사용하는 방식에서는 반환 후 가용 블록을 연결하고, 다시 3바이트 데이터를 할당해 분할이 일어나는 불필요한 과정이 추가된다.
즉 처리량 극대화를 위해선 두 가지 방식을 선택적으로 사용할 수 있어야 한다.

경계 태그

데이터가 할당되었던 블록을 반환할 때, 그 블록의 주위에 가용상태인 블록이 있다면 이를 연결해야 한다. 그러나 이러한 연결을 할 때, 주위에 가용상태인 블록이 있는지를 알려면 각 블록의 헤더를 참조해야 한다. 하지만 헤더를 참조하기 위해 가용 블록의 헤더가 나올 때 까지 힙 영역을 계속 탐색하는 것은 데이터 처리량 극대화에 도움이 되지 않는다. (탐색 시간이 힙 영역의 크기에 비례하므로 O(N)의 시간 복잡도를 가진다.)
이를 방지하기 위해 각 블록의 끝에 footer 라는 이름으로 헤더의 내용을 복사한 블록을 하나 추가하는 방식을 경계 태그라고 부른다. 이런식으로 블록의 끝에서도 헤더의 내용을 알 수 있는 footer를 달아놓으면 주위 블록이 가용상태인지 아닌지를 현재 블록의 헤더에서 딱 한 워드만 움직여도 알 수 있게 된다.
하지만 이러한 방식에도 단점이 있는데 각 블록이 헤더와 풋터에 공간을 할당해야 하므로 작은 크기의 블록을 여러개를 할당하는 경우에는 메모리의 오버헤드, 배보다 배꼽이 더 큰 경우가 발생할 수 있다.

명시적 가용 리스트와의 차이점

명시적 가용 리스트는 가용 블록 내부에 이전 가용 블록의 주소와 이후 가용블록의 주소를 담고 있다는 점이 가장 큰 특징이다. 이러한 점으로 인해서 힙 내부의 영역을 순서대로 탐색하여 가용 영역에 메모리를 할당하는 묵시적 가용 리스트와는 달리 가용영역만을 탐색하여 더 빠르게 메모리를 할당할 수 있다.