Fragmentation

• External Fragmentation
  → 할당 가능 메모리 크기가 제각각인 경우 발생 (Without Paging)
  ⠀⠀
• Internal Fragmentation
  → Paging을 위해 설정한 단위 크기보다 작은 크기의 프로세스가 할당될 때 그 차이만큼의 메모리가 낭비되는 경우 발생 (With Paging)

Allocating Mechanisms

• 분해와 결합
  • 30 Byte 크기의 Heap 가정
    

1. 10 Byte 크기의 할당 요청

2. 5 Byte 크기의 할당 요청 → 10 Byte의 메모리 페이지(블록)를 반으로 나눈 뒤 메모리 할당

3. 5 Byte 크기의 메모리 할당 해제 → 5 Byte 크기의 메모리 페이지 두 개를 원래대로 결합

Growing The Heap

⠀⠀

• 대부분의 할당은 작은 크기의 힙으로 시작하고, 메모리가 부족해지는 경우 OS에 더 많은 메모리를 요청 (OS가 실제 메모리를 관리하기 때문에 가능)
  • UNIX System의 sbrk(or brk) System Call
  • 할당된 메모리의 주소를 반환

• 원래 총 공간: 20 Byte → OS에 요청 → 메모리 추가 할당 가능

  

Details Of Allocating Mechanisms

Header Block (Free)

• Free Space 내부에 Free List를 생성
• Head: Free List의 시작 주소
• Next Field: 다음 Free Space의 주소

Header Block (Used)

• 할당 영역의 크기를 추적
• hptr: 할당 해제를 위해 헤더를 가리키는 포인터
• ptr: 할당된 블록을 가리키는 포인터 (malloc의 반환값)
• Magic Field: Sanity Test를 위한 값, 일종의 보증서

Embedding A Free List: Allocation

• 메모리 공간이 요청되면 라이브러리는 요청을 수용할 수 있는 여유 공간를 찾는다.
• 라이브러리의 역할
  • 해당하는 여유 공간을 둘로 나눈다.
    • 하나는 요청을 위해, 다른 하나는 사용 가능한 공간이다.
  • 목록에서 사용 가능한 공간의 크기를 줄인다.

Example

• ptr = malloc(100)을 통한 100 Byte 공간 요청
  • 4KB Heap Size & 32 Bit Architecture 가정
  • malloc(N)의 실제 공간 크기 = N + Header의 크기

Allocating

• $3764$ (Size of Free Space) $= 4096$ (Whole Size of Memory) $-$ $8$ (Header Size of Whole Memory) $- 108 * 3$ (Sum of Three Allocated Chunk)

Free

• $16708$ (Address of Next Free Space) $= 16384$ (Starting Size of Virtual Address) $+ 108 * 3$ (Sum of Three Allocated Chunk)

Managing Free Space: Basic Strategies

Best Fit

• 할당 요청보다 큰 크기의 공간을 찾는다.
• 찾은 후보 중 가장 작은 크기의 공간을 반환한다.

Worst Fit

• 가장 큰 크기의 공간을 찾아 요청 공간을 할당한다.
• 나머지 공간은 사용 가능 목록에 유지한다.

First Fit

• 여유 공간 탐색 시 가장 먼저 나오는 요청 크기 이상의 공간을 찾는다.
• 찾은 공간을 반환하고 나머지 공간은 유지한다.

Next Fit

• 여유 공간 탐색 시 가장 먼저 나오는 요청 크기 이상의 공간을 찾는다.
• 가장 마지막에 탐색한 주소 다음부터 탐색을 시작한다.

Example

• Assume 1: 10, 30, 20, 40의 네 가지 여유 공간
• Assume 2: 15 크기의 할당 요청

원 안의 숫자는 공간의 남은 크기