[시스템 프로그래밍] 동적 메모리 할당(Implicit, Explicit List)

 

 

메모리에 대한 진실

 

🔲 메모리는 무한의 자원이 아닌 할당되고 관리되는 자원이다.

 

🔲 메모리 참조 버그는 치명적이다.

 

🔲 메모리의 성능은 일정하지 않다. 캐시와 가상 메모리는 프로그램 성능에 영향을 준다.

 

 

 

 

 

 

동적 메모리 할당기

 

 

🔶 직접 할당(Explicit)

응용 프로그램이  할당하고, 반환한다. (malloc, free)

 

🔶 간접 할당(Implicit)

응용 프로그램이 할당하지만, 반환하지 않는다. 예를 들어 자바는 가비지 컬렉션 기능이 있다.

 

 

메모리는 블록 단위로 제공되며, 응용 프로그램에 free 메모리 블록을 나눠준다.

 

 

 

 

 

 

 

 

 

메모리 구조

 

출처 : 교수님 자료

 

🔲 할당기는 sbrk 함수를 통해 추가적인 힙 메모리를 운영체제로부터 요청한다.

 

🔲 stack, kernel virtual memory가 유저 코드에서 볼 수 있는 메모리이다.

 

🔲 uninitialized data : 초기화되지 않은 글로벌 변수

 

🔲 heap : malloc을 통해 공간이 점점 키워진다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

malloc, free, realloc

 

 

 

🔶 void *malloc(size_t size)

 

size 바이트의 메모리 블록의 포인터. 대개 8바이트에 맞춘다.

 

 

 

🔶 void free(void *p)

 

가용 메모리 풀을 가리키는 블록 포인터 p를 리턴한다.

 

 

🔶 void realloc(void *p, size_t size)

 

블록 p의 크기를 변경하고, 새 블록 포인터를 리턴한다.

 

 

 

 

 

 

우수한 malloc/free 프로그램의 목표

 

1️⃣ 처리량 Throughput 향상

 

Throughput은 단위 시간당 처리한 요청의 수를 말한다.

즉, malloc과 free의 평균 처리 시간을 줄이면 Throughput을 향상시킬 수 있다.

 

 

 

2️⃣ 최대 메모리 이용률 Utilization 향상

 

사용가능한 메모리에서 실제로 사용하는 메모리의 비율을 늘리는 것이다. 즉, 단편화를 해결해야한다.

 

 

 

 

 

 

제한 사항

 

 

🔶 응용 프로그램

 

무순의 할당과 요청이 발생되며, 할당된 블록에 대응되어야 한다.

 

 

 

🔶 할당 프로그램

 

🔲 할당된 블록의 갯수와 크기를 조정할 수 없다.

 

🔲 모든 할당 요청에 즉시 반응하며, 그렇기에 순서를 변경하거나 버퍼를 사용할 수 없다.

 

🔲 블록은 프리메모리에서 할당하여야 한다.

 

🔲 블록들은 주소 맞춤 요건을 맞추어야 한다.

 

🔲 일단할당된 블록은 이동할 수 없다.

 

 

 

 

 

 

 

 

 

 

메모리 단편화

 

 

나쁜 메모리 사용률은 단편화로 인해 발생한다. 이러한 단편화는 내부 단편화와 외부 단편화로 구분할 수 있다.

 

 

🔶 내부 메모리 단편화

 

내부 메모리 단편화는 블록 크기와 데이터 크기간의 차이로 인해 일어난다. 이는 힙 자료구조를 유지하고, 정렬을 위해 바이트를 추가하거나 할당 정책에 인한 오버헤드로 인해 발생한다. 또한 이전 패턴에 의해서만 영향을 받으므로 측정에는 용이하다.

 

 

 

 

 

 

🔶 외부 메모리 단편화

 

힙 전체 메모리를 합쳐보면, 수용이 가능하지만 가용(free) 블록 하나의 크기가 더 작은 경우 발생한다. 이러한 외부 메모리 단편화는 미래의 요청 패턴에 의해 결정되므로 측정하기 어렵다.

 

 

 

 

 

 

 

 

 

가용 블록(free) 관리 방법

 

 

1️⃣ 간접 리스트 크기 정보를 이용하여 모든 블록을 연결한다.

 

블록 앞에 헤더(1 Word)에 사이즈와 할당 여부를 입력하여 각 블록을 구분한다.

 

 

 

2️⃣ 직접 리스트를 사용하여 가용 블록 내에서 포인터를 이용한다.

 

 

 

 

3️⃣ 구분 가용 리스트 (segregated free list)

 

크기 클래스 마다 가용 리스트를 유지하는 방법이다.

 

 

 

 

4️⃣ 크기로 정렬된 블록을 이용한다.

 

크기를 키로 사용하며, 균형 트리를 이용한다.

 

 

 

 

 

 

 

 

간접 리스트 방식(Implicit List)

 

 

헤더 정보에 각 블록이 할당 되었는 지의 정보와 사이즈 정보가 포함된다.

 

 

 

 

 

🔲 a = 1(할당), a = 0(프리) 블록

 

🔲 size는 블록의 크기 정보

 

🔲 payload : 실제 데이터

 

🔲 optional padding : 정렬을 위해 사용한다.(즉, 블록의 크기를 일관되게 하기 위해 사용)

 

 

 

 

예를 들어, malloc(1)을 한다고 해보자. 그러면 이때의 1 Word가 4바이트라고 하면 Header는 4바이트만큼 차지될 것이고, Payload는 1만큼 차지될 것이다. 그런데 우리는 정렬 조건을 만족시켜주어야 한다. 즉, 8바이트를 맞춰주기 위해서 3바이트 만큼의 Padding을 주어야 한다.

 

 

 

그러면 size와 a는 어떻게 저장될 것인가?

 

 

 

size는 총 8바이트 만큼의 크기를 차지하고 있으므로 0x08과 같이 될 것이고, a는 할당을 이제 한 것이므로 0x01이 된다. 즉, OR 연산을 통해 이를 합쳐주면 0x09가 될 것이다.

 

 

 

 

 

 

 

가용 블록 찾기

 

 

1️⃣ 최초 할당(First Fit)

 

처음부터 시작하여 맨 처음 크기에 맞는 블록을 할당한다. 그렇기 때문에 모든 블록 수 만큼 비례해서 시간이 소요된다. 

 

 

p = start;

while((p < end) && ((*p & 1) || (*p <= len))) {
	p = p + (*p & -2);
}

 

🔲 p < end : 아직 마지막 가용 블록이 아님

 

🔲 *p & 1 : 할당 정보를 뽑아내기 위함

 

🔲 *p < len : 할당하려는 크기보다 작을 경우 제외

 

🔲 p = p + (*p & -2) : -2는 1111...110이므로 p와 & 연산을 하면, size 값만 나온다. 즉, 현재 주소에서 size만큼 더한 다음 블록을 의미한다.

 

 

 

 

2️⃣ 다음 할당(Next fit)

 

first fit과 유사하나, 이전 검색이 종료된 위치에서 검색을 다시 시작한다. (단편화 성능은 나쁘다고 한다.)

 

 

 

3️⃣ 최적 할당(Best fit)

 

리스트를 검색해서 가장 근접한 크기의 블록을 선택한다. 즉, 단편화 성능을 개선할 수 있으나, 최초할당보다는 느리다.

 

 

 

 

 

 

 

 

가용 블록 할당하기

 

 

만약 할당하고자 하는 사이즈보다 가용한 공간의 사이즈가 더 크다면, 공간이 남는 셈이 된다. 앞서 말했듯 블록의 할당 상태를 Header에 저장한다고 했다. 남는 공간인데 할당되었다고 인지된다면 이는 굉장히 공간이 낭비되는 것이다.

 

 

 

즉, 남는 공간에 대해서는 할당 블록이 아니라 가용블록으로 만들어 줄 필요가 있다. 코드를 통해 살펴보자.

 

void addblock(ptr p, int len) {
    // 짝수로 만들어주는 코드
    int newsize = ((len + 1) >> 1) << 1;
    
    // 가용 영역의 사이즈 추출
    int oldsize = *p & -2;
    
    // 새로운 사이즈로 설정
    *p = newsize | 1;
    
    // 남는 공간이 있다면,
    if (newsize < oldsize) {
    	// 남는 사이즈만큼 Header를 만들어줌(할당은 어짜피 0)
    	*p(p + newsize) = oldsize - newsize;
    }
}

 

 

 

 

 

 

 

할당한 블록 Free하기

 

 

void free_block(ptr p) {
    *p = *p & -2;
}

 

 

위와 같은 방식으로 간단하게 Free해줄 수 있지만, 이렇게 한다면 단편화 문제가 생길 수 있다. Implicit List는 애초에 사이즈를 기반으로 탐색한다. 즉, Free를 해도 아직 Header에는 이전 사이즈 정보만이 남아있기 때문에 할당기는 할당할 블록을 찾지 못한다.

 

 

 

즉, 다음, 이전 블록이 Free하면 이를 연결하여 더 큰 사이즈로 초기화된 Free 블록을 만들어야 한다. 이를 Colesce(결합)이라고 한다.

 

 

void free_block(ptr p) {
    // 할당 여부 0으로 만들어줌
	*p = *p & -2;
    // 현재 블록에서 size만큼 더해줌(즉, 다음 블록)
    next = p + *p;
    // 다음 블록이 할당되지 않았다면, 현재 블록의 사이즈와 더해 현재 블록 사이즈 갱신
    if ((*next & 1) == 0) {
        *p = *p + *next;
    }
}

 

 

 

물론 이 경우는 다음 블록과 Colesce하는 예시일 뿐이다. 실제로는 이전 블록, 이후 블록과 각각 Colesce하는 경우도 생각해 보아야 한다.

 

 

 

하지만, 우리는 사이즈 정보를 헤더에서만 가지고 있어 이전 블록과 Colesce하는 것은 생각해내기 어렵다. 이전 블록을 알아내기 위해서 리스트를 거꾸로 따라갈 수 있어야 하기 때문이다. 그래서 "경계 태그(Boundary Tags)"라는 것을 사용해야 한다.

 

 

 

 

 

 

양방향 연결(경계 태그)

 

 

Free한 블록의 마지막에 똑같이 Header를 복사해서 사용한다. 즉, 리스트를 거꾸로 가기 위해서 사용하는 것이다.

 

출처 : 교수님 자료

 

Footer라고 부르기도 한다.

 

 

 

 

 

 

 

 

직접 리스트(explicit list)

 

직접리스트는 가용 블록내에서 포인터를 통해 앞뒤로 이동할 수 있다고 하였다. 또한 모든 블록 리스트를 관리하는 것이 아니라 가용 블록 리스트만 관리한다. 뭔가 블록 할당을 위해 가용블록을 찾을 때도 훨씬 좋아보인다.

 

 

 

간접 리스트와 달리 직접리스트는 크기로 관리하지 않는다. 그 대신 "포인터"를 사용하여 리스트 요소들을 연결한다.

 

 

 

물론, Colesce(병합)을 위해서 앞뒤 사이즈는 항상 명시되어야 하므로 Header와 Footer(경계태그)는 항상 존재한다.

 

 

 

출처 : 교수님 자료

 

 

Header(4바이트), Footer(4바이트), pred(이전 가용블록을 가리키는 포인터, 8바이트), succ(다음 가용블록을 가리키는 포인터, 8바이트)로 구성되어 있다.

 

 

 

물론 당연하게도 메모리 블록의 순서는 실제 연결된 순서와는 무관하다. 어짜피 포인터로 연결되어 있어 앞뒤 관계를 파악할 수 있기 때문이다.(이중 연결 리스트를 생각하면 편하다)

 

 

 

 

 

 

 

 

 

직접 리스트(explicit list)의 할당

 

 

만약 가용 리스트에서 블록을 할당하면, 포인터가 가리키는 블록을 바꾸어주어야 하기 때문에 포인터를 4개 바꾸어야한다. 

 

 

 

 

 

 

 

 

 

직접 리스트(explicit list)의 Free

 

이전의 간접 리스트는 반환 시 그 위치가 그대로 고정되어 있어서 굳이 가용 블록에 대한 처리를 해주지 않아도 되었다. 하지만, 직접 리스트는 반환 시에 가용 블록이 어느 위치에 삽입 되냐에 따라 그 성능이 달라진다.

 

 

 

 

🔶 LIFO(Last-in-first-out) 정책

 

🔲 반환된 블록을 가용리스트 맨 앞에 삽입한다.

 

🔲 간단하며 상수 시간이 소요된다.

 

🔲 단편화 성능이 주소 정렬 방식보다 나빠진다.

 

 

 

 

🔶 주소 정렬 정책

 

🔲 가용 블록 리스트가 블록의 순서를 유지하도록 삽입한다.

 

🔲 대신 리스트를 탐색해야하기 때문에 최악의 경우 LogN만큼의 시간이 소요된다.(Binary Search)

 

🔲 연구에 의하면 단편화 성능이 LIFO보다 우수하다.

 

 

 

 

 

🤔 간접 리스트와의 비교

 

🔲 할당 시간이 전체 블록 수가 아니라 가용 블록 수에 비례한다. 즉, 메모리가 거의 다 차있는 경우에는 매우 빠른 할당 성능을 가진다.



🔲 할당과 반환 과정이 간접리스트보다 복잡하다. 포인터를 4개나 바꾸기 때문이다.



🔲 링크 포인터 저장을 위해서 2워드(16바이트)의 추가 저장 공간이 필요하다.



🔲 구분 가용 리스트는 여러 크기 클래스 별로 직접 연결 리스트를 만든다.