[Operating System] Swapping System Examples: First Fit / Best Fit / Worst Fit / Next Fit

First Fit / Best Fit / Worst Fit / Next Fit Examples

---

포스트 난이도: HOO_Middle

[Notice] 포스트 난이도에 대한 설명

---

 

# Example 1

Question)

Consider a swapping system in which memory consists of the following hole sizes in memory order: 10MB, 4MB, 20MB, 18MB, 7MB, 9MB, 12MB and 15MB. Which hole is taken for successive segment requests of 12MB, 10MB, 9MB for first fit, best fit, worst fit and next fit?

Answer)

First fit: 20MB 10MB 18MB

Best fit: 12MB 10MB 9MB

Worst fit: 20MB 18MB 15MB

Next fit: 20MB 18MB 9MB

---

Swapping system에서 4가지 종류별 fit을 사용했을 때 나오는 결과가 어떻게 다른지를 살펴보는 문제이다.

우선 memory order를 시각적으로 표현해보면 아래와 같다.

Fig01. Memory order

---

First fit을 먼저 살펴보면, 12MB를 10MB과 4MB에 할당할 수가 없기 때문에 그다음 20MB가 선택된다.

다음으로 10MB는 첫번째 10MB를 선택할 수 있고 마지막 9MB는 4MB에 넣을 수 없기 때문에 18MB가 선택된다.

따라서 결과적으로 12MB, 10MB, 9MB의 First fit은 20MB, 10MB, 18MB가 된다.

---

Best fit은 말 그대로 최고의 효율성 또는 최적화된 사이즈를 순서에 상관없이 찾아주면 된다.

따라서 결과는 12MB, 10MB, 9MB가 된다.

---

Worst fit은 사이즈 차이가 많이 나는 순서대로 선택해주면 된다.

따라서 12MB는 제일 큰 20MB가 되며, 10MB는 다음 사이즈인 18MB가 되고 9MB는 15MB를 선택하게 된다.

---

마지막으로 Next fit은 첫 번째 fit을 한 기준으로 다음 블록을 확인해준다고 이해하면 된다.

20MB는 10MB와 4MB가 될 수 없고 그 다음인 20MB가 선택된다.

다음으로 10MB는 20MB가 fit된 기준에서 다음으로 확인해나가면 선택한다.

따라서 최종 결과는 20MB, 18MB, 9MB가 선택된다.

---