[OS] 메모리 할당 알고리즘(최초 적합, 최적 적합, 최악 적합)

메모리 관리 개념

메모리 관리는 프로그램의 실행이 종료될 때까지 메모리를 가용한 상태로 유지 및 관리하는 방법

 

메모리 관리 기법

메모리 관리 기법에는 반입 기법, 배치 기법, 할당 기법, 교체 기법이 있다.

 

메모리 배치 기법

메모리 배치 기법에는 최초 적합, 최적 적합, 최악 적합이 있다.

기법	설명
최초 적합 (First Fit)	- 프로세스가 적재될 수 있는 가용 공간 중에서 첫 번째 분할에 할당하는 방식
최적 적합 (Best Fit)	- 가용 공간 중에서 가장 크기가 비슷한 공간을 선택하여 프로세스를 적재하는 방식 - 공백 최소화 장점이 있음
최악 적합 (Worst Fit)	- 프로세스의 가용 공간 중에서 가장 큰 공간에 할당하는 방식

 

최초 적합(First Fit)

메모리에서 프로세스가 필요로 하는 크기 만큼의 빈 공간을 가장 먼저 발견되는 공간에 할당하는 방식

• 메모리를 처음부터 순차적으로 탐색하여, 프로세스가 요구하는 크기보다 크거나 같은 첫 번째 빈 공간을 찾아 그곳에 할당한다.
• 빈 공간을 발견하면 즉시 할당하므로, 전체 메모리를 다 탐색하지 않아도 되기 때문에 메모리 할당이 빠르다.
• 메모리의 앞부분에 작은 조각들이 남게 되어, 시간이 지남에 따라 외부 단편화가 많이 발생할 수 있다.

 

최적 적합(Best Fit)

프로세스가 요구하는 크기와 가장 비슷한 크기의 빈 공간에 할당하는 방식

• 메모리에서 프로세스가 요구하는 크기보다 크거나 같은 모든 빈 공간을 탐색한 후, 그 중에서 가장 작은 크기의 빈 공간에 할당한다.
• 프로세스 크기에 딱 맞는 공간을 찾기 때문에 메모리 공간의 낭비를 최소화할 수 있다.
• 처음부터 끝까지 모두 탐색을 해야 하므로, 탐색 시간이 오래 걸릴 수 있다.
• 최초 적합과 마찬가지로 외부 단편화가 발생할 수 있다.

 

최악 적합(Worst Fit)

프로세스가 요구하는 크기보다 가장 큰 빈 공간에 할당하는 방식

• 메모리에서 프로세스가 요구하는 크기보다 큰 모든 빈 공간을 탐색한 후, 그 중에서 가장 큰 빈 공간에 할당한다.
• 큰 공간을 먼저 할당하기 때문에, 작은 빈 공간들이 더 적게 남는다.
  • 큰 공간이 작게 쪼개지므로, 큰 프로세스를 나중에 처리할 때 유리할 수 있다.
• 큰 공간을 비효율적으로 사용하게 되면, 큰 프로세스를 할당할 수 있는 공간이 점점 줄어들게 되어 메모리 관리가 어려워질 수 있다.
• 딱 맞는 공간이 있는데도 데이터의 크기와 가장 안 맞는 메모리에 저장하기 때문에 Worst이다.
• 최적 적합과 마찬가지로 하나하나 탐색을 하기 때문에 메모리 낭비까지 발생한다.

---

예제 1

Q. 13K의 작업을 다음 그림의 14K 공백의 작업 공간에 할당했을 경우, 사용된 기억장치 배치전략 기법은?

OS

16K 공백

used

14K 공백

used

5K 공백

used

30K 공백

 

 

A. 최적 적합(Best Fit)

---

예제 2

---

 

참고 자료

[수제비] 2024 정보처리산업기사 실기 교재