메모리 할당 기법 (Memory Allocation: First Fit, Best Fit, Worst Fit)

메모리 할당 기법 (Memory Allocation: First Fit, Best Fit, Worst Fit)

가변 크기 메모리 요청을 빈 공간 목록(Free List)에서 어떤 블록에 할당할지 결정하는 알고리즘으로, First Fit, Best Fit, Worst Fit이 대표적

목적: 메모리 효율적 할당, 단편화 최소화, 할당 속도 최적화

특징: Free List 기반, 가변 크기, 단편화 특성 상이, 성능 트레이드오프

First Fit (최초 적합)

• •방법: Free List를 처음부터 탐색, 첫 번째 충분한 블록에 할당
• •장점: 빠른 탐색(평균적으로 절반만 탐색), 구현 간단
• •단점: 앞쪽에 작은 단편 축적, 외부 단편화
• •시간: O(n) 최악, 평균 O(n/2)

Best Fit (최적 적합)

• •방법: 전체 Free List 탐색, 요청 크기에 가장 근접한 블록에 할당
• •장점: 남는 공간 최소화, 큰 블록 보존
• •단점: 전체 탐색 필요(느림), 아주 작은 단편 생성
• •시간: O(n), 정렬 시 O(log n)

Worst Fit (최악 적합)

• •방법: 가장 큰 빈 블록에 할당
• •장점: 남은 공간이 크므로 재사용 가능
• •단점: 큰 블록 빨리 소진, 대형 요청 실패
• •시간: O(n), 정렬 시 O(1)

Next Fit: First Fit 변형, 마지막 할당 위치부터 탐색

성능 비교

• •속도: First > Next > Worst > Best
• •공간 효율: Best ≈ First > Worst
• •실무: First Fit 또는 Segregated Free List 사용

장점: 단순한 알고리즘, 다양한 선택지

단점: 모두 외부 단편화 발생, 완벽한 해결 아님

적용사례: 힙 메모리 할당, 연속 메모리 할당, 파일 시스템

비교: First(빠름/적당) vs Best(작은잔편/느림) vs Worst(큰블록소진)

연관: 외부 단편화, Free List, 힙 관리, 버디 시스템