[운영체제론] Constant Time Coalescing (Case 1-4) 정리

2025-2 운영체제론 dynamic memory allocation 일부

 

Case 1: 양쪽 블록 모두 할당됨

Constant Time Coalescing (Case 1)

m1 1
m1 1
n 1
n 1
m2 1
m2 1

상수 시간 병합 – 경우 1 (Case 1)

표기

m1	이전 블록의 크기 (size of previous block)
n	현재 해제되는 블록의 크기 (size of block being freed)
m2	다음 블록의 크기 (size of next block)
1	할당 상태 (allocated bit = 1)
0	free 상태 (free bit = 0)

즉, "m1 1"은 "크기 = m1, 할당됨(1)"이란 뜻입니다. 각 블록은 [크기 / 할당여부] 구조의 헤더(혹은 푸터)로 표현됩니다.

Case 1의 의미

양 옆 블록(이전, 다음) 모두 할당된 상태에서, 현재 블록을 free 하는 경우

 

[ Alloc (m1) ][ Free(n) ][ Alloc (m2) ]

• 이전 블록: 사용 중 (allocated)
• 현재 블록: 이제 막 free됨
• 다음 블록: 사용 중 (allocated)

수행 과정

1단계: free_block(p) 호출

현재 블록 헤더의 "할당 비트"만 0으로 변경

 

*p = *p & -2;

2단계: 이전/다음 블록 상태 확인

• 이전 = 1 (할당됨)
• 다음 = 1 (할당됨)

3단계: 병합 조건 불만족

• 병합 수행 안 함

4단계: 결과

• 이 블록 혼자 free 상태로 남음
• 주변 블록들은 그대로 유지

shell

Before:
[ m1 / 1 ] [ n / 1 ] [ m2 / 1 ]
          ↑ 현재 free 시도

After:
[ m1 / 1 ] [ n / 0 ] [ m2 / 1 ]

• 가운데 블록만 free 표시됨
• coalescing 없음
• 즉, 단순히 "할당비트만 0으로 바꾸는" 경우

시간 복잡도

단계설명복잡도

비트 변경	*p & -2 연산	O(1)
이전/다음 상태 확인	각각 한 번씩 확인	O(1)

전체 free 연산 시간은 여전히 상수 시간 (O(1))

정리 요약

항목설명

Case 번호	1
이전 블록	Allocated
다음 블록	Allocated
병합 여부	없음
동작 내용	할당 비트만 0으로 변경
결과	해당 블록만 free 상태로 유지
시간 복잡도	O(1)

한 줄 요약

Case 1: 양쪽 블록이 모두 사용 중이면, free는 단순히 "현재 블록의 할당 비트만 0으로 만드는 작업"이다. 병합(coalescing)은 발생하지 않으며, 시간 복잡도는 O(1).

---

Case 2: 다음 블록만 Free

Constant Time Coalescing (Case 2)

 

m1 1
m1 1
n 1
n 1
m2 0
m2 0
m1 1
m1 1
n+m2 0
n+m2 0

 

상수 시간 병합

m1 1          ← 이전 블록: 할당됨 (Allocated)
n 1           ← 현재 블록: 해제 중 (Free로 바꿀 예정)
m2 0          ← 다음 블록: 비어 있음 (Free)

병합 결과:

m1 1          ← 이전 블록 그대로 유지
n+m2 0        ← 현재 블록과 다음 블록 병합됨 (Free)

Case 2의 의미

현재 free된 블록(p)의 다음 블록(next)이 비어있을 때, 두 블록을 하나로 합쳐서 더 큰 free 블록으로 만든다.

Before:
[ Alloc (m1) ][ Free (n) ][ Free (m2) ]

After:
[ Alloc (m1) ][ Free (n+m2) ]

코드 동작 흐름

void free_block(ptr p) {
    *p = *p & -2;        // 현재 블록을 free로 표시
    next = p + *p;       // 다음 블록 주소 계산
    if ((*next & 1) == 0) // 다음 블록이 free라면
        *p = *p + *next;  // 크기 합쳐서 병합
}

한 줄씩 해석

1단계: *p = *p & -2;

• 현재 블록의 "할당 비트(1)"를 0으로 변경
• free 상태로 표시됨

2단계: next = p + *p;

• 현재 블록의 총 크기만큼 이동
• 다음 블록 헤더 위치 계산

3단계: if ((*next & 1) == 0)

• 다음 블록이 free인지 검사 (LSB=0이면 free)

4단계: *p = *p + *next;

• 두 블록의 크기를 합쳐 하나의 블록으로 만듦

결과 그림으로 이해하기

Before:
[  m1 / 1  ][  n / 0  ][  m2 / 0  ]
                 ↑ free(p)
After:
[  m1 / 1  ][  n+m2 / 0  ]

• 가운데 n 블록과 바로 뒤의 m2 블록이 병합되어 하나의 큰 free 블록 (n + m2)이 된다.
• 다음 블록(m2)의 헤더는 이제 "논리적으로 사라짐(logically gone)" (이 블록은 병합되었기 때문)

시간 복잡도

할당 플래그 제거	& -2	O(1)
다음 블록 검사	(*next & 1)	O(1)
병합 시 크기 합산	*p = *p + *next	O(1)

즉, Case 2도 O(1) - 루프나 탐색 없음. 단순한 포인터 계산과 덧셈만 수행.

병합 시 변경되는 정보

항목변경 내용

현재 블록 헤더	크기를 (n + m2)로 업데이트
병합된 블록 푸터	푸터도 동일하게 업데이트
다음 블록 헤더	사용되지 않음 (삭제된 셈)

직관적으로 이해하기

free된 블록은 혼자 있으면 작은 조각에 불과하지만, 바로 뒤가 빈 공간이라면 그 둘을 하나로 합쳐 더 큰 free 블록으로 만들어야 나중에 malloc이 큰 요청을 처리할 수 있습니다.

즉, Case 2는 "뒤쪽 확장" (extend backward)의 개념입니다.

한 줄 요약

Case 2: 해제된 블록의 다음 블록이 비어 있으면, 두 블록을 합쳐 하나의 큰 free 블록 (n + m2)으로 만든다. boundary tag 덕분에 이 연산은 상수 시간(O(1))에 수행된다.

---

Case 3: 이전 블록만 Free

Constant Time Coalescing (Case 3)

 

m1 0
m1 0
n 1
n 1
m2 1
m2 1
n+m1 0
n+m1 0
m2 1
m2 1

\상수 시간 병합

m1 0          ← 이전 블록: 비어 있음 (Free)
n 1           ← 현재 블록: 이제 막 해제되는 중
m2 1          ← 다음 블록: 사용 중 (Allocated)

병합 결과:

n+m1 0        ← 이전 블록과 현재 블록 병합 (Free)
m2 1          ← 다음 블록 그대로 유지

Case 3의 의미

현재 해제 중인 블록의 이전 블록(previous)이 비어 있을 때, 두 블록을 하나의 큰 free 블록으로 합칩니다.

Before:
[ Free (m1) ][ Free (n) ][ Alloc (m2) ]

After:
[ Free (m1 + n) ][ Alloc (m2) ]

코드 동작 흐름

free_block(p) 함수가 boundary tag를 이용해 이전 블록을 찾아 병합합니다.

1단계: *p = *p & -2;

• 현재 블록을 free로 표시

2단계: 이전 블록 상태 확인

• 이전 블록의 푸터(footer)를 읽으면 크기와 상태 알 수 있음
• 즉, prev_footer = p - 1
• if ((*prev_footer & 1) == 0) - 이전 블록도 free

3단계: 이전 블록의 헤더 주소 계산

• prev = p - (*prev_footer & -2)
• (푸터에 저장된 크기만큼 뒤로 이동)

4단계: 병합 수행

• *prev = *prev + *p; (크기 합치기)
• footer(prev) 도 동일하게 업데이트

결과 그림으로 보기

Before:
[  m1 / 0  ][  n / 0  ][  m2 / 1  ]
                 ↑ free(p)
After:
[  m1+n / 0  ][  m2 / 1  ]

• 이전 블록의 크기(m1)와 현재 블록의 크기(n)을 합침
• 이전 블록의 헤더와 푸터 둘 다 업데이트
• 현재 블록의 헤더는 더 이상 필요 없음 (논리적으로 병합됨)

시간 복잡도

현재 블록 free 표시	& -2	O(1)
이전 블록 상태 확인 (푸터)	1회 읽기	O(1)
병합 크기 합산	*prev = *prev + *p	O(1)

전체 O(1) - 여전히 상수 시간에 병합 완료. boundary tag 덕분에 이전 블록을 빠르게 찾을 수 있어서 탐색이 필요 없음.

병합 시 업데이트되는 정보

이전 블록 헤더	새 크기 = m1 + n
이전 블록 푸터	새 크기 = m1 + n
현재 블록 헤더	논리적으로 삭제됨
다음 블록	그대로 유지 (할당됨)

직관적 이해

이전 블록이 비어 있고, 현재 블록을 free할 때 두 블록을 하나로 합쳐야 "쪼개진 작은 빈 공간들"이 하나로 커집니다. 즉, Case 3은 "앞쪽 병합(merge backward)" 상황입니다.

한 줄 요약

Case 3: 이전 블록이 free이고, 다음 블록은 사용 중이면, 현재 free되는 블록을 이전 블록과 병합한다. boundary tag를 통해 이전 블록 크기를 즉시 알아내므로 병합은 상수 시간(O(1)) 안에 끝난다.

---

Case 4: 양쪽 블록 모두 Free

Constant Time Coalescing (Case 4)

m1 0
m1 0
n 1
n 1
m2 0
m2 0
n+m1+m2 0
n+m1+m2 0

상수 시간 병합

m1 0          ← 이전 블록: 비어 있음 (Free)
n 1           ← 현재 블록: 이제 막 해제되는 중
m2 0          ← 다음 블록: 비어 있음 (Free)

병합 결과:

n+m1+m2 0     ← 이전, 현재, 다음 블록 전부 병합됨 (Free)

Case 4의 의미

현재 해제되는 블록의 이전 블록과 다음 블록이 모두 free 상태일 때, 세 블록을 하나의 큰 free 블록으로 병합(coalesce)합니다.

Before:
[ Free (m1) ][ Free (n) ][ Free (m2) ]

After:
[ Free (m1 + n + m2) ]

이전 + 현재 + 다음 블록이 전부 합쳐져서 하나의 거대한 free block이 됩니다.

코드 동작 (개념 단계별)

Case 4에서는 Case 2, Case 3 로직을 둘 다 수행합니다. 즉, "이전"과 "다음"을 각각 확인하고 합치는 과정을 동시에 하는 것과 같습니다.

 

동작 흐름 (의사코드 기준)

void free_block(ptr p) {
    *p = *p & -2;             // 현재 블록 free로 표시

    next = p + (*p & -2);     // 다음 블록 헤더 위치
    prev_footer = p - 1;      // 이전 블록 푸터 위치

    prev_free = ((*prev_footer & 1) == 0);
    next_free = ((*next & 1) == 0);

    if (prev_free && next_free) {
        prev = p - (*prev_footer & -2);      // 이전 블록 헤더 위치 계산
        *prev = *prev + *p + *next;          // 이전 + 현재 + 다음 합치기
        footer(prev) = *prev;                // 푸터도 업데이트
    }
}

결과 그림으로 보기

Before:
[  m1 / 0  ][  n / 0  ][  m2 / 0  ]
                 ↑ free(p)
After:
[  m1+n+m2 / 0  ]

• 세 블록이 완전히 하나로 합쳐져서 중간의 헤더 2개(n, m2)는 "논리적으로 삭제됨(logically gone)"
• 이제 이 큰 free 블록이 힙에서 단 하나의 단위로 관리됨

시간 복잡도 분석

현재 블록 free 표시	1회 비트 연산	O(1)
이전 블록 상태 확인	푸터 1회 읽기	O(1)
다음 블록 상태 확인	헤더 1회 읽기	O(1)
병합 수행	단순 덧셈 2회	O(1)

모든 연산이 상수 번수의 메모리 접근으로 끝남 - 상수 시간 (O(1)) coalescing 완성.

병합 시 갱신되는 정보

이전 블록 헤더	새 크기 = m1 + n + m2
이전 블록 푸터	새 크기 동일하게 기록
현재 블록 헤더 / 다음 블록 헤더	논리적으로 사라짐
다음 블록 푸터	새로운 큰 블록의 푸터가 됨

직관적 이해

Case 4는 가장 이상적인 병합입니다. 앞뒤 블록이 모두 비어 있으니까 그 세 개를 한 번에 합치면, 외부 단편화(external fragmentation)를 거의 완전히 줄일 수 있습니다.

즉, "쪼개진 조각들"을 전부 하나로 만드는 단계입니다.

한 줄 요약

Case 4: 이전 블록과 다음 블록이 모두 free일 때, 현재 블록까지 포함해 세 블록을 한꺼번에 병합한다. 헤더/푸터 덕분에 위치 계산이 즉시 가능하므로 이 과정 역시 O(1) 시간 안에 수행된다.

결과: 하나의 커다란 free block 생성, external fragmentation 대폭 감소.