First Fit, Best Fit, Worst Fit

실행 대기중인 프로세스가 있다.
그리고 메모리에 대기중인 프로세스가 실행될만한 충분한 공간이 여러군데 있다.
그렇다면, 대기중인 프로세스를 실행시킬 때, 어느 부분의 메모리 공간에 할당해 줄 것인가?

First Fit (최초 적합)

---

가장 최초로 발견되는 메모리 공간에 할당한다.

Best Fit (최적 적합)

---

모든 빈 공간을 계산해서, 프로세스를 할당했을 때 가장 남는 공간이 적은(외부 단편화가 가장 적게 생길 확률이 높은) 곳에 할당한다.

Worst Fit (최악 적합)

---

가장 큰 공간에 할당한다.

남는 공간을 가장 크게 남겨야, 다른 프로세스가 그곳에 할당될 확률이 크다. Best Fit과 완전한 반대의 사고.

효율성 비교

---

속도와 메모리 효율 측면에서 First Fit과 Best Fit이 Worst Fit보다 좋은 것으로 나타났다.

메모리 효율 측면에서 First Fit과 Best Fit은 차이가 별로 없다.

하지만, 당연히 First Fit이 Best Fit보다 속도가 빠르다.

First Fit은 가장 최초로 빈 공간이 발생하자마자 할당하고,

Best Fit은 모든 빈 공간을 계산해서, 프로세스를 할당했을 때 가장 남는 공간이 적은 곳을 찾아내야 하기 때문이다.

속도와 메모리 효율 측면에서 비교했을 때, 결론적으로

First Fit > Best Fit > Worst Fit

순으로 효율성이 좋다.

Paging의 배경

---

First Fit이든 Best Fit이든 결국 외부단편화는 발생한다. 즉, 메모리가 낭비된다.

First Fit을 기준으로 한 통계에 의하면, N개의 블록이 할당되었을 때, 0.5N개의 블록이 단편화 때문에 손실될 수 있다. 즉 메모리의 1/3(0.5N/1.5N)을 사용할 수 없게 된다. 이를 50퍼센트(0.5N/N) 룰이라고 한다.

이를 방지하기 위해 Compaction으로 합치는 방법도 있다.

Compaction이란, 퍼져있는 프로세스 메모리들을 다시 연속적으로 붙여서 재할당하는 것이다. 하지만 이를 위해서 임시적인 공간에 복사를 했다가, 재할당을 해야 한다. 이 과정에서 I/O가 발생하고, 이는 비용이 크기 때문에 좋은 방법이 아니다.

이 문제점들을 해결하기 위해 Paging이 탄생한다.

참조
https://jhnyang.tistory.com/284?category=815411