OS · MEMORY

연속 할당 배치 전략 비교

First Fit, Best Fit, Worst Fit은 모두 연속 공간을 찾지만 탐색 비용과 남는 조각의 성격이 다릅니다.

요청 18K 빈 공간 목록 12K · 20K · 36K · 24K를 같은 순서로 본다.

First

12K 20K 36K 24K

남음 2K

Best

12K 20K 36K 24K

가장 작게 남김

Worst

12K 20K 36K 24K

남음 18K

first/best/worst-fit trade-off

trade-off

탐색 시간빈 공간 목록을 얼마나 오래 훑는지가 할당 지연을 만듭니다.

남는 조각너무 작은 조각은 외부 단편화를 빠르게 악화시킵니다.

placement

First처음 맞는 공간에 넣어 빠르지만 앞쪽에 작은 구멍이 쌓입니다.일반 목적 시스템에서 구현 비용이 낮고 최근 접근을 반영해 평균 페이지 폴트를 줄입니다.

Best가장 딱 맞는 공간을 찾지만 전체 탐색이나 정렬 구조가 필요합니다.남는 공간이 작아 tiny fragment가 많아질 수 있습니다.

Worst가장 큰 공간을 쪼개 남는 조각을 크게 유지하려 합니다.큰 요청을 받을 공간을 먼저 쪼개 이후 큰 할당 실패 가능성을 키웁니다.

escape

압축프로세스를 이동시켜 큰 빈 공간을 만들지만 복사 비용이 큽니다.

버디 시스템2의 거듭제곱 블록으로 쪼개고 합쳐 관리 비용을 낮춥니다.

페이징연속 배치 제약을 제거해 외부 단편화 문제를 근본적으로 줄입니다.