핵심 목표 역량

1. malloc, free 이해하기
2. CSAPP 9장 다 읽기 (가상 메모리)
3. c로 implicit list AI 도움 없이 구현

핵심 목표 평가

1. CSAPP 9.9장을 읽고 이해하고 다른 팀원들이 이해하기 쉽도록 설명이 가능함

• 달성률 100%

2. CSAPP 9.9장은 책으로 deep-dive 하며 읽고 9.1 ~ 9.3 장은 top-down 방식으로 요약본 pdf로 공부함.

• 9.1 ~ 9.3장의 핵심 내용인 VA(virtual address)를 PA(Physical Address)로 변환하는 과정을 이해하기 쉽게 설명이 가능함
• 9장 나머지 부분도 top - down 방식으로 학습하려고 하였지만 하지 못함
• 달성률 40%

3. CSAPP 9.9장에 나와있는 코드를 보고 이해한 후 책의 코드를 참고하며 직접 구현

• 책에 나온 코드가 비효율적이라고 생각하거나 내가 이해한 바와 다르다면 내가 이해한 코드를 직접 작성
• 개념을 이해하고 내가 처음부터 직접 구현한 것이 아니라 책의 코드를 참고하면서 코드를 작성
• 달성률 70%

WEEK7 주요 개념 정리

1. malloc과 free

#include <stdlib.h>

// 리턴값은 void* (void 포인터)
void * malloc(size_t size) :
							returns : pointer to allocated block if OK, NULL on error

malloc 함수는 블록 내에 포함될 수 있는 어떤 종류의 데이터 객체에 대해서 적절히 정렬된 최소 size 바이트를 갖는 메모리 블록의 포인터를 리턴한다. 실제 구현에서 정렬은 코드가 32bit 모드 (gcc -m32) 또는 64비트 모드(기본설정)에서 동작하도록 컴파일되었는지 여부에 따라 다르다. 32비트 모드에서 malloc은 주소가 항상 8의 배수인 블록을 리턴한다. 64비트 모드에서 주소는 항상 16의 배수다.

만일 malloc이 문제를 만난다면 (프로그램이 가용한 가상메모리보다 더 큰 크기의 메모리 블록을 요청하는 경우) null을 리턴하고 errno를 설정한다.

• errno : 마지막 에러 이유를 담는 전역변수
• errno는 자동으로 초기화 되지 않아서 이런식으로 쓰는 경우가 많다.

errno = 0;
malloc(...);

if (errno != 0) {
    // 에러 발생
}

malloc 같은 동적 메모리 할당기는 mmap과 munmap 함수를 사용해서 명시적으로 힙 메모리를 할당하거나 반환하며 또는 sbrk 함수를 사용할 수 있다.

• 즉, malloc은 내부적으로 heap 공간 자체를 늘릴 수도, 기존 heap 이외의 메모리 공간을 사용할 수 있다는 것이다.

#include <unistd.h>

void * sbrk(intptr_t incr);
						Returns : old brk pointer on success, -1 on error

sbrk 함수는 커널의 brk 포인터에 incr을 더해서 힙을 늘리거나 줄인다. 성공한다면 이전의 brk 값을 리턴하고 아니면 -1을 리턴하고 errno를 ENOMEM으로 설정한다. 만일 incr이 0이면, sbrk는 현재의 brk 값을 리턴한다.

sbrk를 음수 incr로 호출하면 합법적이기는 하지만, 리턴값(이전의 brk 값)이 새로운 힙의 탑을 지나서 abs(incr)바이트를 가리키기 때문에 복잡해진다

free 함수는 힙 블록을 반환한다..

2. sbrk vs mmap

Sbrk는 프로세스의 힙 끝(brk)을 늘리거나 줄이는 방식

힙이 한 덩어리처럼 커짐

[ code | data | heap........ ]
                    ↑
                 힙 끝을 늘림

mmap은

[ code | data | heap ]     [ 새로 매핑된 영역 ]

즉 mmap은 꼭 기존 힙 끝에 붙지 않아도 된다.

필요한 별도 가상 메모리 영역을 직접 매핑 가능

3. 단편화

단편화에는 두가지 종류가 있다. 내부 단편화, 외부 단편화

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

• 내부 단편화는 정량화하기가 쉽다. 이것은 단순히 할당된 블록의 크기와 이들의 데이터 사이의 차이의 합이다.
• 그래서 시간상 어디서든 내부 단편화의 양은 이전에 요청한 패턴과 할당기 구현에만 의존한다.

외부 단편화 : 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 공간을 모았을 때는 충분한 크기가 존재하지만, 이 요청을 처리할 수 있는 단일한 가용블록은 없는 경우에 발생한다.

• free 한 공간은 충분한데 한 덩이리로 없어서 못쓰는 상태

4. 묵시적 할당 (Implicit Free List)

묵시적 할당은 힙에 있는 모든 블록을 처음부터 끝까지 순차적으로 탐색하면서 가용 블록을 찾는 방식이다.

즉, 가용 블록들만 따로 연결해서 관리하지 않고, 전체 블록 리스트 안에서 “이 블록이 할당 상태인지, 가용 상태인지”를 헤더를 통해 확인한다.

특징

1. 구현이 가장 단순하다.
2. 모든 블록을 순차적으로 봐야 하므로 탐색 속도가 느리다.
3. 블록 수가 많아질수록 성능이 떨어진다.

장점

1. 구조가 단순해서 이해하고 구현하기 쉽다.
2. 초기 malloc lab에서 기본 개념을 익히기에 좋다.

단점

1. 할당된 블록까지 전부 검사해야 해서 비효율적이다.
2. 탐색 비용이 크다.

5. 명시적 할당 (Explicit Free List)

명시적 할당은 가용 블록들만 따로 연결 리스트로 관리하는 방식이다.
즉, free block 내부에 prev, next 포인터를 두어서 가용 블록끼리만 연결한다.
그래서 블록을 찾을 때는 전체 힙을 다 보는 것이 아니라 free list만 순회하면 된다.

특징

1. 가용 블록만 탐색하므로 묵시적 할당보다 빠르다.
2. free block 내부에 포인터를 저장해야 한다.
3. 최소 블록 크기가 커질 수 있다.

장점

1. 묵시적 할당보다 탐색 효율이 좋다.
2. 전체 블록이 아니라 free block만 보면 된다.

단점

1. 구현이 더 복잡하다.
2. prev, next 포인터 공간이 필요해서 오버헤드가 생긴다.
3. 작은 블록에서는 내부 단편화가 더 커질 수 있다.

6. Segregated Free List (Seglist)

Seglist는 명시적 할당을 더 발전시킨 방식이다.
가용 블록을 하나의 리스트로 관리하는 것이 아니라,크기별로 여러 개의 free list를 나누어서 관리한다.

ex)
작은 블록 리스트
중간 블록 리스트
큰 블록 리스트

이런 식으로 크기 구간마다 따로 관리한다.

특징

1. 요청 크기에 맞는 리스트부터 탐색할 수 있다.
2. 명시적 할당보다 더 빠르게 적절한 블록을 찾을 수 있다.
3. 실제 allocator에서 많이 사용하는 방식이다.

장점

1. 탐색 속도가 더 빠르다.
2. 요청 크기에 맞는 free block을 찾기 쉽다.
3. 메모리 이용 효율도 좋아질 수 있다.

단점

1. 구현이 가장 복잡하다.
2. 크기 클래스(class)를 어떻게 나눌지 설계가 필요하다.