[운영체제론] Dynamic Memory Allocation

੯∙̀͡u\  운영체제론 강의 수강하면서 일부분 정리한 내용입니다 ૮₍ •̀ᴥ•́ ₎ა

목차

1. get_header() 함수 분해
2. First-fit 탐색 알고리즘
3. 헤더 구조와 비트 연산
4. addblock() - 할당 및 분할

---

get_header() 함수 분해

코드

static inline word_t get_header(void *bp) {
    return *((word_t *)bp - 1);
}
```

### 1. static inline
- **static**: 같은 파일 안에서만 사용 가능한 지역 함수
- **inline**: 함수 호출 대신 코드를 그 자리에 직접 치환 (오버헤드 감소)
- 의미: "이 파일 안에서만 쓰는, 빠른 내부 헬퍼 함수"

### 2. word_t get_header(void *bp)
- `word_t`: typedef uint32_t word_t (4바이트 정수)
- `void *bp`: 타입이 없는 포인터 (어떤 자료형이든 받을 수 있음)
- 기능: payload 포인터(bp)를 받아서 그 앞의 header 값을 반환

### 3. (word_t *)bp - 형 변환
- void 포인터를 word_t(4바이트 단위) 포인터로 변환
- 이제부터 4바이트 단위로 인덱싱 가능

### 4. (word_t *)bp - 1 - 핵심 포인터 연산
포인터 연산에서 -1은 "바이트 단위"가 아니라 **해당 타입의 크기 단위**로 이동
```
주소 (16진수)
0x1000 ─ header (4B)
0x1004 ─ payload 시작

bp = 0x1004일 때
(word_t *)bp - 1
= 0x1004 - (1 × 4바이트)
= 0x1000 (header 주소 도착)
```

### 5. *((word_t *)bp - 1) - 역참조
- `*`을 붙이면 "그 주소에 들어있는 값"을 읽음
- 결과: header에 들어있는 값(블록 크기 + alloc bit) 반환

### 동작 전체 흐름
```
get_header(bp)
↓ (bp는 payload 시작주소)
(1) bp를 word_t*로 변환 → word 단위 인덱싱 가능
(2) -1 → header(4B) 쪽으로 이동
(3) * → header 안의 값을 읽음
(4) return → header값 반환
```

### 메모리 그림
```
주소
┌──────────┬──────────────────┐
│  Header  │  Payload (사용자)│
└──────────┴──────────────────┘
↑          ↑
│          └─── bp (malloc이 준 포인터)
└─────────────── (word_t*)bp - 1
                 get_header(bp)가 읽는 위치

---

First-fit 탐색 알고리즘

전제

• 암시적 리스트: 각 블록 앞에 1워드 헤더가 있음
• 헤더 구조: [블록의 총 크기 | 할당여부 1비트]
• p: 현재 블록의 헤더 주소를 가리키는 포인터

코드

p = heap_start;
while (p < heap_end) {
    if ((*p & 1) == 0 && (*p >= 요청크기))
        return p;                 // free block found
    p = p + (*p & -2);            // 다음 블록으로 이동
}

1. 루프 구조

while (p < heap_end)

• 힙의 모든 블록을 처음부터 끝까지 순회
• 암시적 리스트의 특징: 포인터로 연결 안 함, 선형 스캔

2. (*p & 1) == 0 - free 블록 확인

if ((*p & 1) == 0 && (*p >= 요청크기))

헤더의 맨 아래 1비트(LSB)가 할당 여부:

• ...xxx1 → alloc=1 (사용 중)
• ...xxx0 → alloc=0 (free)

(*p & 1)은 맨 아래 비트만 추출:

• 0이면 free
• 1이면 allocated

3. (*p >= 요청크기) - 크기 확인

• 헤더 *p에는 블록의 전체 크기가 들어있음
• 요청크기는 정렬/오버헤드가 반영된 최종 필요 크기(asize)
• 조건: "현재 free 블록 사이즈 >= 요청 크기?"

4. p = p + (*p & -2) - 다음 블록으로 점프

핵심: 다음 블록 주소 = 현재 블록 시작주소 + 현재 블록 크기

왜 & -2인가?

• 현재 블록의 "순수 크기"만 뽑으려면 LSB(alloc 비트)를 0으로 만들어야 함
• -2의 비트: ...1110 (맨 아래만 0, 나머지는 1)
• X & -2: 맨 아래 비트만 0으로, 나머지는 그대로 → 순수 블록 크기

 

size = (*p & -2);  // alloc 비트 제거한 순수 블록 크기
p = p + size;      // 현재 헤더에서 size만큼 건너뛰면 다음 블록 헤더

주의: p가 word_t* 타입이면, p + size는 size × 4바이트만큼 이동

전체 해석

p = heap_start;              // 힙의 첫 블록 헤더
while (p < heap_end) {       // 끝까지 반복
    if ( (*p & 1) == 0       // 1) free 블록이고
      && (*p >= 요청크기) ) { // 2) 크기도 충분하면
        return p;            // 이 블록에 할당
    }
    p = p + (*p & -2);       // alloc 비트 제거한 크기만큼 점프
}
```

### 작동 예시
```
주소    값(헤더)    해석
1000:   16|1       크기 16, alloc=1 (사용중)
1016:   32|0       크기 32, alloc=0 (free)
1048:   8|1        크기 8, alloc=1
1056:   40|0       크기 40, alloc=0

요청: 24바이트 할당

1. p=1000
   *p & 1 = 1 (alloc) → 패스
   p = 1000 + (16 & -2) = 1000 + 16 = 1016

2. p=1016
   *p & 1 = 0 (free) && *p >= 24 → 32 >= 24
   return 1016 (성공)
```

### 비트 연산 팁
- `& 1`: 맨 아래 1비트만 확인 (할당/빈칸 플래그)
- `& -2`: 맨 아래 1비트만 0으로 (크기만 추출)
- `& ~1`: `-2`와 동일 (더 직관적)

---

## 헤더 구조와 비트 연산

### 헤더는 4바이트(32비트) 정수
```
총 32비트 중
├── 상위 31비트: 블록 크기
└── 하위 1비트: 할당 여부 (alloc bit)
```

### 비트 구조
```
bit31 ... bit1 | bit0
[ size ...     | alloc ]

필드비트 수설명

size	31 bits	블록 전체 크기 (바이트 단위)
alloc	1 bit	1 = allocated / 0 = free

왜 31비트로도 충분한가?

• 2^31 = 2,147,483,648 bytes ≈ 2 GB
• 하나의 힙 블록이 2GB를 넘는 경우는 거의 없음
• 따라서 1비트를 alloc flag로 사용해도 손해 없음

실제 메모리 예시

헤더값 (16진수)2진수size (상위 31비트)alloc (하위 1비트)의미

0x11	0001 0001	0001 0000 → 16	1	크기 16, 사용중
0x18	0001 1000	0001 1000 → 24	0	크기 24, free
0x19	0001 1001	0001 1000 → 24	1	크기 24, alloc

비트 분리 코드

 

 

c

#define ALLOC_MASK 0x1      // 맨 아래 1비트만 1
#define SIZE_MASK (~0x1)    // 맨 아래 비트만 0

unsigned int header = *p;   // 현재 블록 헤더 읽기
unsigned int alloc = header & ALLOC_MASK;  // 할당 여부
unsigned int size = header & SIZE_MASK;    // 순수 크기

예시: header = 0x19

• alloc = 0x19 & 0x1 = 1
• size = 0x19 & 0xFFFFFFFE = 0x18 (24)

---

addblock() - 할당 및 분할

전제

• 이미 찾아낸 free 블록 p에 len만큼 할당
• 필요하면 남는 나머지를 새로운 free 블록으로 분할(split)

코드

void addblock(ptr p, int len) {
    int newsize = ((len + 1) >> 1) << 1;  // round up to even
    int oldsize = *p & -2;                // mask out low bit
    *p = newsize | 1;                     // set new length
    if (newsize < oldsize)
        *(p+newsize) = oldsize - newsize; // remainder
}

1. 정렬 반올림

int newsize = ((len + 1) >> 1) << 1;

목적: 요청한 len을 짝수(2의 배수)로 올림
동작:

1. len + 1: 반올림 준비
2. >> 1: 2로 나눔 (아래쪽 버림)
3. << 1: 다시 2 곱함 → 짝수로 올림

예시:

• len=5 → (5+1)=6 → 6>>1=3 → 3<<1=6 (5를 6으로 올림)
• len=8 → (8+1)=9 → 9>>1=4 → 4<<1=8 (이미 짝수)

2. 기존 블록 크기 추출

int oldsize = *p & -2;

• *p: 현재 free 블록의 헤더 값 = [size|alloc]
• & -2: alloc 비트(LSB) 제거 → 순수 크기만 추출
• 예: *p=0x19(=24|1) → oldsize=0x18(=24)

3. 할당 상태로 표기

*p = newsize | 1;

• 헤더에 최종 크기와 alloc=1 기록
• 이제 p가 가리키는 블록은 "크기=newsize, 할당됨" 상태

4. 분할(split)

if (newsize < oldsize)
    *(p + newsize) = oldsize - newsize;
```

**조건**: 요청(newsize) < 기존(oldsize) → 남는 공간 발생

**p + newsize**:
- p는 워드 포인터이므로 newsize 워드만큼 이동
- 즉, 잔여 free 블록의 헤더 주소

***(p + newsize) = oldsize - newsize**:
- 잔여 블록 헤더에 "잔여 크기" 기록
- 값이 짝수(LSB=0)로 들어가므로 자동으로 free 표시

### 메모리 변화 (워드 단위)
```
Before:
[p: oldsize|0 ][ x x x x x x x x x ] ← 총 10워드 free

After (newsize=4):
[p: 4|1 ][ x x x ] [ (p+4): 6|0 ][ x x x x x ]
↑ 할당됨(4워드)    ↑ 잔여 free 블록(6워드)
```

### 숫자 예제
- 현재 free 블록: `*p = 10|0` → `oldsize = 10`
- 요청: `len = 4` → `newsize = 4`

**실행 흐름**:
1. `oldsize = *p & -2 = 10`
2. `*p = newsize | 1` → `*p = 4 | 1 = 5` (크기 4, alloc=1)
3. `newsize < oldsize` → `4 < 10` (참)
4. `*(p + 4) = 6` (잔여 free 블록 헤더)

**결과**:
```
Before: [10|0] [x x x x x x x x x x]
After:  [4|1]  [x x x] [6|0] [x x x x x]

주의사항

실제 구현에서는 "잔여 블록이 최소 헤더 크기를 담을 만큼 충분히 큰가?"를 체크해야 함. 너무 작으면 split을 건너뛰고 통째로 할당.

---

요약

get_header()

• payload 포인터에서 -1 워드만큼 뒤로 가서 헤더 값을 읽는 함수
• 포인터 연산의 핵심: 타입 크기 단위로 이동

First-fit

• 힙을 처음부터 순회하며 첫 번째로 맞는 free 블록 찾기
• *p & 1: 할당 여부 확인
• *p & -2: 순수 크기 추출
• p = p + size: 다음 블록으로 점프

헤더 구조

• 4바이트 정수로 크기(31비트) + 할당(1비트) 정보 저장
• 비트 연산으로 효율적 관리

addblock()

• 찾은 free 블록에 할당하고 남으면 분할
• 정렬, 크기 추출, 할당 표시, 분할의 4단계 과정