[Operating System] Fit

Fit

fit의 뜻으로는 "모양과 크기가 맞다", "어느 장소에 들어가기에 맞다" 등이 있다. OS에서 말하는 Fit이란 메모리에 프로세스를 배치할 때 어떤 공간에 배치하는게 가장 알맞을지를 말하는 것이다. 다음과 같은 메모리와 프로세스가 있다고 가정해보자. 프로세스를 어디에 Fit해야 할까? 추가로 아직 프로세스가 배치되지 않고 남은 메모리 공간을 hole이라고 한다.

First Fit 최초적합

최초적합은 가장 만난 적합 가능한 메모리 공간에 바로 배치하는 것을 말한다. 남은 메모리를 순차적으로 검사하면서 배치가 가능하다면 바로 배치한다.

 

Best Fit 최적적합

최적적합은 새로운 프로세스를 배치했을 때 hole을 최소화하는 것을 목표한다. 모든 hole에 프로세스를 비교해보면서 새로 발생하는 hole이 가장 작은 곳에 프로세스를 배치한다.

 

Worst Fit 최악적합

최악적합은 최적적합과 완전히 반대되는 방법이다. 즉 hole을 최대로 만드는 곳에 프로세스를 배치하는 것이다. 이 방법은 hole을 최대로 만들어야 다음 프로세스가 들어올 공간을 만들 수 있다는 전략이다.

50% 규칙

그래서 어떤 fit 전략이 가장 좋은 전략일까? 일반적으로 worst fit이 가장 안 좋은 전략이라고 한다. 다음으로 first fit과 best fit은 성능이 비슷하다고 한다. 어떤 전략을 사용하든 결국 외부 단편화는 발생한다. 통계적으로 N개의 블록이 할당할 때 0.5개의 블록이 손실된다고 한다. 즉 할당과 손실의 비율이 1:0.5이다. 이러한 현상을 50% 규칙이라고 한다. 

 

이러한 손실을 막기위해 생겨난 개념이 paging이다. 외부 단편화는 프로세스마다 크기가 달라서 생기는 문제점이다.(가변분할) 따라서 paging은 메모리를 고정된 크기로 할당시킨다.(고정분할)