[운영체제] 세그멘테이션(Segmentation) | Segment, External Fragmentation, Free Space management

낭비되는 공간을 줄이는 법

지난 기록에서 우리는 Base and Bounds(동적 재배치) 기법을 다뤘다. 이 방식은 단순하면서도 효과적이었지만, 치명적인 비효율성을 안고 있었다. 바로 내부 단편화(Internal Fragmentation) 문제다. 사용하지도 않는 힙(Heap)과 스택(Stack) 사이의 넓은 빈 공간까지 통째로 물리 메모리에 할당해야 했기 때문이다.

Internal Fragmentation

마치 혼자 사는 사람에게 방 10개짜리 대저택을 강제로 배정하고 관리비를 받는 격이다.
"왜 주소 공간을 통째로만 다뤄야 하지?"라는 의문으로부터, 오늘은 그 의문에 대한 답, 즉 메모리를 논리적인 단위(Logical Segments)로 쪼개어 관리하는 세그멘테이션(Segmentation)에 대해 정리해 본다.

1. 세그멘테이션: Contiguous Portion

세그멘테이션의 핵심 아이디어는 간단하다. 프로세스의 주소 공간을 통째로 물리 메모리에 올리는 대신, 의미 있는 단위인 세그먼트(Segment)별로 나누어 관리하는 것이다.

코드(Code): 명령어가 저장된 곳
힙(Heap): 동적 데이터가 저장된 곳
스택(Stack): 지역 변수와 함수 정보가 저장된 곳

Segment in Physical Memory

이제 우리는 이 세 가지 논리적 영역에 대해 각각 독립적인 Base와 Bounds 레지스터 쌍을 가진다. 이렇게 하면 힙과 스택 사이의 사용되지 않는 공간(Free space)은 물리 메모리에 할당할 필요가 없어진다. 낭비가 사라지는 것이다.

2. 하드웨어의 지원: 주소 변환의 진화

세그멘테이션을 적용하면 주소 변환 과정이 조금 더 정교해진다. 가상 주소(Virtual Address) 자체를 쪼개어 어떤 세그먼트를 가리키는지 파악해야 하기 때문이다.

명시적 접근법 (Explicit Approach)

가상 주소의 상위 몇 비트(Top bits)를 세그먼트 식별자로 사용한다.

\text{Virtual Address} = \underbrace{\text{Segment bits}}_{\text{Which Segment?}} + \underbrace{\text{Offset bits}}_{\text{Where inside?}}

예를 들어 14비트 주소 체계에서 상위 2비트를 세그먼트용으로 쓴다면:

Explicit Approach

00: Code
01: Heap
10: (Not used)
11: Stack

변환은 다음과 같이 이루어진다.

상위 비트를 읽어 세그먼트를 파악한다.
해당 세그먼트의 Base 레지스터 값을 가져온다.
Physical Address = Base + Offset
동시에 Protection Check를 수행한다: Offset < Size (Bounds)

Explicit Approach
Process

Explicit Approach
Example

3. 세그멘테이션이 가져온 기능들

단순히 메모리를 아끼는 것을 넘어, 세그멘테이션은 OS에 몇 가지 유용한 기능을 부여했다.

1) 스택의 역방향 성장 지원 (Support for Stack Growth)

스택은 힙과 달리 메모리 주소가 높은 곳에서 낮은 곳으로 자라난다(Grows backward). 이를 지원하기 위해 하드웨어는 세그먼트가 어느 방향으로 자라는지 알려주는 비트(1: 양의 방향, 0: 음의 방향)를 추가로 관리한다.

Growing direction check

2) 공유와 보호 (Sharing and Protection)

메모리 절약을 위해 여러 프로세스가 코드 세그먼트(Code Segment)를 공유할 수 있다. 이때 중요한 것은 보호(Protection)다. 코드는 읽고 실행할 수만 있어야지(Read-Execute), 쓰기(Write)가 가능하면 안 된다. 세그먼트 테이블에 권한 비트(Read/Write/Execute)를 추가함으로써, 잘못된 접근 시 Segmentation Fault를 발생시켜 시스템을 보호한다.

Protection bit

4. 새로운 고민: 외부 단편화 (External Fragmentation)

세그멘테이션은 내부 단편화 문제를 훌륭하게 해결했다. 하지만 외부 단편화(External Fragmentation)라는 새로운, 그리고 더 골치 아픈 문제가 등장했다.

문제 상황: 세그먼트들의 크기가 제각각(Variable-sized)이다 보니, 메모리를 할당하고 해제하는 과정에서 물리 메모리 곳곳에 작은 구멍(Hole)들이 생긴다.
결과: 전체 빈 공간을 합치면 충분한데도, 연속된 공간이 없어서 새 세그먼트를 할당하지 못하는 상황이 발생한다.

External Fragmentation & Compaction

물리 메모리를 한쪽으로 밀어서 정리하는 압축(Compaction) 기법이 있지만, 이는 메모리 복사 비용이 너무 커서 실시간 시스템에서는 사용하기 어렵다.

5. 빈 공간 관리 (Free-Space Management)

외부 단편화를 최소화하기 위해 OS나 malloc 라이브러리는 Free List를 정교하게 관리해야 한다.
Compaction을 통한 메모리 재배치가 일어나지 않는다고 가정하고, 아래 매커니즘을 살펴보자.

1) 할당의 기술: Splitting

사용자가 15바이트를 요청했는데 30바이트짜리 빈 청크(Chunk)만 있다면? 30바이트를 15바이트 두 개로 쪼개어(Split), 하나는 주고 나머지는 다시 Free List에 남겨둔다.

Splitting은 기본적으로 메모리 요청의 크기가 free chunk의 크기보다 작을 때 동작한다.

Splitting example

2) 해제의 기술: Coalescing

free() 호출을 통해 메모리가 해제되어 돌아올 때, 바로 옆에 빈 청크가 있다면 하나로 합친다(Coalesce). 이렇게 해야 나중에 큰 메모리 요청이 왔을 때 대응할 수 있다.

Coalescing example

3) 헤더(Header)의 비밀

free(ptr)을 호출할 때 우리는 크기를 알려주지 않는다. 그래도 라이브러리가 알아서 해제하는 비결은? 바로 할당된 메모리 바로 앞부분에 헤더(Header)라는 비밀 공간을 숨겨두고 거기에 크기(Size)와 무결성 검사용 매직 넘버(Magic number)를 적어두기 때문이다.

라이브러리는 사용자 요청에 헤더의 크기를 더한 Free chunk를 찾아 메모리를 할당한다.

Size tracking

3) 자유 공간(free space)의 비밀

우리는 지금까지 개념상으로 free list를 만들어 자유 공간을 정의해왔다. 그렇다면 free list를 만들기 위해서도 메모리 할당이 필요하지 않을까? 내부적으로 어떻게 구현될까?

할당자는 자유 공간을 관리하기 위해 자유 공간 덩어리(free chunk) 자체를 리스트 노드로 활용한다.

A. 리스트 노드의 정의

자유 리스트의 노드(node)는 일반적으로 다음과 같은 구조체로 정의된다:

Node

B. 힙의 구축 및 초기화

자유 공간 리스트를 구축하고 관리하는 과정은 다음과 같다:

1. 메모리 확보 (Create a heap): 커널로부터 메모리를 빌려와서 힙(Heap)을 생성한다. 이는 보통 mmap() 시스템 호출 등을 통해 이루어진다.

2. 초기 자유 덩어리 할당: 확보된 힙 공간 전체를 하나의 큰 단일 자유 덩어리로 설정한다.

3. 리스트 초기화: 이 단일 자유 덩어리의 시작 부분에 리스트 노드 구조체(node_t)를 위치시키고 이를 자유 리스트의 헤드(head)로 지정한다.

예를 들어, 4KB(4096 바이트)의 메모리를 확보했다면, 이 공간의 시작 부분에 node_t 구조체(예: 크기가 8바이트라고 가정)가 헤더로 배치되고, 나머지 공간(4096 - 8 = 4088 바이트)이 실제 자유 공간이 된다.

Heap with one free chunk

이때 할당 요청을 만족시키기 위해 어떤 자유 덩어리를 선택할지 결정하는 여러 전략이 있다.

전략	설명	특징
Best Fit (최적 적합)	요청 크기보다 크거나 같은 자유 덩어리 중 가장 작은 덩어리를 찾아 반환한다.	자유 공간 전체를 탐색해야 한다 (Full search required)
Worst Fit (최악 적합)	가장 큰 자유 덩어리를 찾아 요청을 할당하고, 남은 덩어리를 자유 리스트에 유지한다.	자유 공간 전체를 탐색해야 한다 (Full search required)
First Fit (최초 적합)	요청 크기보다 충분히 큰 첫 번째 덩어리를 찾아 할당한다.	전체 탐색이 필요하지 않다 (No exhaustive search required)
Next Fit (다음 적합)	First Fit과 유사하게 충분히 큰 첫 번째 덩어리를 찾지만, 목록의 시작이 아닌 이전에 탐색을 멈췄던 위치에서 검색을 시작한다.	자유 공간 검색을 리스트 전체에 더 균일하게 분산시키며, 전체 탐색이 필요하지 않다.

마치며

세그멘테이션은 "사용하지 않는 공간은 할당하지 않는다"는 철학으로 메모리 효율성을 비약적으로 높였다. 하지만 가변 크기(Variable size) 할당이 필연적으로 야기하는 외부 단편화 문제는 여전히 숙제로 남았다.

OS 설계자들은 생각했다. "그렇다면 아예 모든 메모리를 고정된 크기(Fixed size)로 잘게 썰어서 관리하면 어떨까?"

이 아이디어가 바로 현대 OS 메모리 관리의 꽃, 페이징(Paging)의 시작이다.

다음 포스팅에서는 외부 단편화조차 허용하지 않는 페이징 기법이 어떻게 동작하는지, 그리고 그 과정에서 발생하는 또 다른 트레이드오프는 무엇인지 깊이 파고들어 보겠다.

[운영체제] CPU 가상화 | Logical Control Flow에서 Context Switch까지

[운영체제] Operating System 전체 포스팅 모음집

[운영체제] 가상 메모리(Virtual Memory) | 운영체제는 어떻게 프로세스에게 독점 공간을 제공할까?