운영체제의 메모리 할당 알고리즘

여러 개의 남는 공간 중 가장 좋은 자리를 고르는 것을 Fit이라고 한다.

 

프로세스가 생성되고 종료되는 과정에서 Scattered Holes가 만들어지는데,

여러 개의 holes 중 프로세스를 적재할 메모리를 찾아 할당한다.

 

다음은 메모리를 할당하는데 사용되는 대표적인 알고리즘 세 가지이다.

 

First-fit, Best-fit, Worst-fit

---

Example

이 메모리에다가 저 노란색 크기 만큼의 데이터를 저장하려고 한다.

Scattered Holes가 있는 메모리

메모리 할당 알고리즘마다 어떻게 데이터를 저장하는지 보자.

---

 

First-fit (최초적합)

First-fit은 가장 최초로 발견되는 곳에 데이터를 저장한다.

메모리를 순차적으로 탐색하다가 가장 먼저 발견한 곳에 데이터를 저장하는 방법이다.

 

Example의 데이터를 다음과 같이 저장할 것이다.

 

---

Best-fit (최적적합)

Best-fit은 데이터가 저장되기에 가장 적절한 곳에 데이터를 저장한다.

메모리를 탐색해서 가장 먼저 발견한 가장 적절한 곳을 찾아 데이터를 저장하는 방법이다.

 

Example의 데이터를 다음과 같이 저장할 것이다.

이렇게 가장 딱 맞는 곳에 데이터를 저장하기 때문에 메모리의 낭비가 가장 적다.

Best-fit이 가장 좋아보이지만 그만큼 Scanning을 처음부터 끝까지 모두 해봐야한다는 단점이 있다.

비교를 많이 해야되고 그렇기 때문에 시간이 오래걸린다는 단점이 있다.

---

Worst-fit (최악적합)

Worst-fit은 프로세스를 적재하는데 가장 크기가 안 맞는 곳에 프로세스를 적재하는 방법이다.

딱 맞는 공간이 있는데도 데이터의 크기와 가장 안맞는 메모리에 저장을 하기 때문에 Worst이다.

물론 데이터의 크기보다 큰 메모리에 저장한다.

 

Example의 데이터를 다음과 같이 저장할 것이다.

 

Worst-fit도 Best-fit처럼 하나하나 Scanning을 해야한다.

메모리 낭비까지 발생하기 때문에 다른 방법에 비해서 선호도가 낮다.