17. Free-Space Management(1)
external fragmentation(외부 단편화)
: 1. when the free space you are managing consists of variable-sized units
: 2. when using segmentation to implement virtual memory.
- 위와 같은 경우처럼, 20 bytes만큼의 free space가 존재하지만, 15 bytes의 연속된 메모리 공간을 요구하는 프로세스는 할당될 수 없는 'wasteful'한 상황
17.1 Assumptions
- 외부 단편화에만 포커싱
- 메모리 공간은 한 번 할당되고 나면, 그 메모리 주소를 옮길 수 없음(cannot be relocated) -> 즉, compaction 불가능
- the allocator manages a coutiguous region of bytes
17.2 Low-level Mechanisms
1. basics of splitting and coalescing(coalesce : (더 큰 덩어리로) 합치다)
2. how one can track the size of allocated regions quickly and with relative ease
3. how to build a simple list inside the free space to keep track of wht is free and wht isn't
Splitting and Coalescing
 |
→ |  |
- 이 상황에서 10byte보다 작은 공간 요청이 들어올 경우(malloc)
- allocator는 splitting 방법을 사용함(밑의 예시는, 1byte짜리 메모리 요청이 들어온 경우 할당 후 모습)
- 즉, [addr:20 / len:10] 이었던 두 번째 노드가 두 부분으로 나뉘어진 후 한 부분은 할당되고, 한 부분은 남겨진다.
- 그렇다면, 다시 처음 상태(free 10, used 10, free 10)로 돌아가서
- used 10에 대한 free가 호출된다면?
 |
 |
| (X) | (O) |
- 왼쪽과 같은 상황에서는, 연속적인 30바이트 만큼의 공간이 있어도, 그 만큼의 공간 할당 불가능
- 오른쪽과 같은 coalescing 과정을 통해 효율적인 공간 할당 가능해짐
Tracking The Size Of Allocated Regions
- free(void *ptr) : size에 대한 정보는 parameter로 받지 않음. 포인터만으로 malloc library가 size를 파악하고 free list에 할당해줄 수 있어야 됨.
- 'header'에 필요한 정보를 저장
- 즉, N바이트에 대한 요청이 들어오면, library는 N바이트만큼의 free 공간을 찾는 것이 아니라, (N+헤더사이즈)만큼의 공간을 할당해야 한다.
Embedding A Free List
- 그렇다면 free list는 어디에..?
- need to build the list inside the free space itself
- ex. mmap() 이라는 시스템 콜로 free space에 힙을 하나 생성
↓
- 이제, 100바이트의 메모리 요청이 들어온다고 가정
- 위 덩어리는 두 개로 쪼개져서 하나는 요청을 처리하고 하나는 남겨짐(헤더는 8바이트라고 가정)
- 이제, 100바이트 짜리 요청에 세 개 들어온다고 가정
- free()를 통한 메모리 반환이 이루어지면 어떤 일이 일어날까?
-출처-
<OPERATING SYSTEMS three easy pieces>
REMZI H. ARPACI-DUSSEAU
ANDREA C. ARPACI-DUSSEAU
UNIVERSITY OF WISCONSIN-MADISON