Dynamic Storage Allocations
- available space list(사용가능 공간 테이블)
각 항목: 빈 블록의 시작주소, 크기
paging 기법을 사용한다면 블록 크기에 대한 정보가 없다. 일정하기 때문에 - occupied space list(점유공간 테이블)
각 항목: 블록 이름, 시작주소, 블록크기
paging 기법을 사용한다면 크기 정보가 없다. - secondary-memory directory or list
현재 수행중인 프로그램과 연관된 블록(i가 사용중이면 i+1)들을 포함하는 디렉토리들의 리스트
S1, S2, ..., Sn을 사용가능한 n개의 hole의 크기라 하고 S를 현재 할당을 필요로하는 프로그램 혹은 데이터의 크기라고 하자.
First-Fit Allocation
최초적합
이 알고리즘은 available space list(ASL)가 각 hole들의 시작주소에 대해서 올림차순으로 정렬되어 있다는 전제를 하고 있다. 내려갈수록 주소가 커진다.
ASL을 처음부터 탐색하여 요청크기인 S보다 큰 hole들 중에서 처음 만나는 hole을 찾아 할당하는 방법이다.
즉, ASL이 hole들의 시작 주소에 대해 올림차순으로 정렬되어 있으므로, 탐색을 시작하여 처음 만나는, S보다 같거나 큰 크기의 hole을 찾아 할당하면 된다.
Best-Fit Allocation
최적적합
이 알고리즘은 ASL이 각 hole들의 크기에 대해서 올림차순으로 정렬되어 있다는 전제를 하고 있다. 내려갈 수록 크기가 커진다.
ASL을 처음부터 탐색하여 요청 크기인 S보다 큰 hole들 중에서 가장 작은 hole을 찾아 할당하는 방법이다. 할당하고 남는 공간을 최소화할 수 있는 방법으로 메모리 조각화현상을 최소화시킬 수 있어 메모리 사용 효율이 가장 높으나 메모리 할당할 때마다 ASL을 정렬해야하는 오버헤드가 발생한다.
Worst-Fit Allocation
최악적합
이 알고리즘은 최적적합과 반대로 ASL가 각 hole들의 크기에 대해서 내림차순으로 정렬되어있다는 전제를 하고 있다. 가장 큰것이 맨 위에 있고 메모리 조각화 현상이 가장 크다. 그리고 무조건 ASL의 가장 처음에 있는 hole에 할당하기 때문에 ASL의 탐색을 필요로 하지 않는다. 비효율적으로 보이지만 할당하고 남은 공간이 가장 크게 되는 알고리즘으로, 남은 공간을 또다른 프로그램에 할당할 수 있는 확률이 가장 높다.
