Memory Management #3 Memory 배치 알고리즘(Best-fit , First-fit, Next-fit)

트럭에 짐을 넣는 알고리즘에사용되는 Best-fit , First-fit , Next-fit 이 OS에서도 사용 된다!

프로세스가 메인메모리에 적재되기전

"나의 용량은 99M입니다. 제가 들어갈 수 있을 만큼의 용량을 저에게 주세요."

라고 말할 것이다.

여기서 중요한것 첫째! 

제가 들어갈 수 있을 만큼의 용량을 저에게 주세요.

물론 프로세스보다 크거나  같은 주기억장치의 가용(free) 블록중 하나를 줄것이다.

그리고 두번째!

운영체제는 어떻게,어떠한 방법으로 찾아서 해당 메모리를 프로세스에게 할당해줄것인가?

바로 Best-fit , First-fit , Next-fit 방법을 사용하여 줄것이다. 

위의 그림에서 보자면, 16M의 프로세스가 메인 메모리에 load되려고 한다.

Best - fit : 처음부터 끝까지 탐색하여 요청된 크기와 가장 근접한, 가장 가까운 크기의 메모리를 줄것이다.

왼쪽에서 보면 현재 18M이 가장 16M과 가깝고 근접하다. 그러므로 OS는 18M의 메모리 공간을 줄것이다.

First - fit : 메모리의 처음부터 검사해서 크기가 충분한 첫번째 메모리를 줄것이다.

메인 메모리 첫부분을 가리키는 포인터가 있다고 가정하자. 그 포인터를 사용하여 배열을 탐색하듯이 탐색할 것이다. 첫 가용 블록은 8M이므로 다음을 탐색하고, 그다음은 12M이다. 또 다음을 탐색한다. 그런데 22M은 충분히 16M이 들어갈 수 있다. 그래서 22M의 메모리 공간을 할당해줄것이다.

Next - fit : 가장 마지막에 들어간 공간으로 부터 가장 적합한곳을 줄것이다.

스택처럼, 가장 마지막에 들어간 공간을 가리키는 포인터가 있다고 가정하자. 그 영역부터 탐색을 시작하여 공간을 찾는것이다. 포인터를 증가시키면서 결국 찾은 곳은 36M이다.

First - Fit 알고리즘이 가장 간단할 뿐만 아니라 대부분의 경우 최적이며 가장 빠르다.

Next - Fit 알고리즘은 First - Fit 보다 약간 안좋은데, 마지막 부분에 있는 사용 가능한 블록에 프로세스를 load 하는 경향이 있다. 보통 메모리공간의 끝에 있는 가장 큰 크기의 메모리를 짧은 시간 내에 작은 크기로 조각낸다. 그래서 메모리 직얍작업이 더 필요하게 된다.

Best - Fit 알고리즘은 명칭과 달리 가장 안좋은 알고리즘이다. 이 방법은 가장 작은 블록을 찾아 배정한다. 그래서 가장 작은 단편들을 만든다. 예를 들면 20MB의 프로세스를 22MB에 메모리 블록에 들어가게 되고 2M의 구멍이 생긴다. 외부 단편화를 초래하며 메모리 집약의 횟수도 증가시킨다. 가장 근접한 크기의 메모리 블록을 차지하니 1M~2M의 구멍들을 많이 만들것이다. 가장 최악의 알고리즘!

물론 잘 생각해보면, 동적 분할 알고리즘은 아니겠지? 왜냐면 메모리가 서로 다른 크기의 블록으로 나뉘어진 상태에서 프로세스를 어디에 load 시킬지 정하는 알고리즘이니까^_^

그러므로 이 배치 알고리즘들은 비균등 분할 집합! 에서 사용될 것이다.

참고 : 운영체제 내부구조 및 설계원리 제6판 (William Stallings 지음)