[운영체제 OS] first-fit 최초적합, best-fit 최적적합, worst-fit 최악적합에 대해 알아보자!

[운영체제 완전정복 목차]

안녕하세요 

양햄찌 블로거입니다. 오늘 오랜만에 운영체제 글을 다시 들고 찾아왔어요.

 

저번 시간에 External fragmentation (외부 메모리 단편화)에 대해 알아봤는데 그 내용의 연장선상입니다.

그러므로 이 글을 읽기전에 External Fragmentation에 대한 내용은 머리속에 입력되어 있어야 한다는거!

 

기억이 나지 않을 경우, 아래 포스팅 링크를 참조해주세요!

https://jhnyang.tistory.com/264

[운영체제 OS] Fragmentation 메모리 단편화란 무엇인가? External fragmentation(외부 단편화)이란? 초 쉬운

자, 프로세스가 실행되고 종료되면서 두 개 빈 공간이 아래처럼 남았다고 가정해봅시다. 

아래 상황처럼, 두 공간에 충분히 들어갈 PROCESS가 왔을 경우 '어디다가 집어넣는게 효율적일까?' 즉 fit ! 알맞게! 넣으려면 어떤 방법이 좋을까?를 고민하게 됩니다.

FIT 하게 넣는 방법을 생각해보자

빨간색 프로세스를 A와 B중 어디에 넣는게 좋을까요? 이것만 보고서는 잘 모르겠죠.

똑똑한 우리들은 이를 결정할 성능 평가를 위한 알고리즘을 생각하게 됩니다.

 

알고리즘 성능평가를 할 때 직접 구현하는 방법, 수학적으로 하는 방법, 시뮬레이션으로 하는 방법이 있는데,

수학적으로 하려면 제약이 많고 직접 구현하려면 너무 overhead가 크고 그래서 시뮬레이션을 많이 합니다.

현재 컴퓨터 프로그램에서 프로그램을 실행했다 종료됐다하는 것들을 하루치를 관찰을 했더니 어떤 크기에 프로세스가 실행이 됐다가 종료되고 이런 걸 실제 시스템에서 얻을 수 있어요. 이를 trace data (추적 데이터)라고 합니다.  

말그대로 내 상황 데이터를 수집에서 이에 대한거에 맞는 방향성을 찾는 시뮬레이션인거죠!

암튼 이런 trace data를 만들어서 시뮬레이션 프로그램을 돌려 성능을 측정 할 수 있는데, 방법을 first-fit, best-fit, worst-fit 세가지로 했어요.

 

There are many solutions to this problem. The first-fit, best-fit,
and worst-fit strategies are the ones most commonly used to select a free hole from the set of available holes.

이 문제를 해결하기 위해 많은 방법이 있는데, '최초적합, 최적적합, 최악적합'은 가능한 hole들중에서 하나의 남는 공간을 셀렉하는데 사용되는 가장 흔한 방법입니다. 

first-fit(최초적합), best-fit(최적적합), worst-fit(최악적합)이란?

고럼 이 세 개가 어떤 차이가 있는지 살펴보도록 합시다.

이렇게 있다고 가정!

■ first fit 최초적합

최초적합은 가장 최초로 발견되는 hole에다가 할당하는거 

남은 메모리를 순차적으로 앞에서부터 탐색하게 되는데, 이 프로세스가 들어갈 수 있는 hole들 중 최초에 발견된 hole에다가 배치하는게 최초적합니다.

first fit

■ best fit 최적적합

여기다 넣을지 여기다 넣을지를 다 대보는 겁니다. 가장 잘 맞는데에 넣는 것. 어차피 자투리가 생기는데 가급적이면 자투리를 조그맣게 만들겠다! 

B에 넣는게 외부단편화가 가장 작게 생김! A랑 C는 빨간프로세스가 들어가기 쓸데없이 커!

■ worst fit 최악적합

가장 큰 공간, 즉 가장 남는 공간에다가 넣는게 worst fit입니다. 왜 worst냐?

딱 맞는 공간이 있어도 거기에 안넣고 큰데 넣겠다는거죠.

이 아이디어는 무슨 뜻이 있는걸까요? 자투리를 크게 만들어야 다른 프로세스가 또 거기 들어갈 확률이 있는 것 아니냐~! (best fit이랑 완전히 반대 사고인거죠) 이렇게 프로세스를 넣어도 공간이 충분히 남아서 동일한 빨간 프로세스가 더 들어갈 수 있겠다! 반면 A랑 B에 넣으면 자투리공간이 넘 작아서 쓸데도없어! 이 사고방식이 worst fit입니다.

 

이해 다 됐죠? 요 그림으로 정리하고 넘어갑시다.

세 가지 방법에 대한 효율성 비교

Simulations have shown that both first fit and best fit are better than worst fit in terms of decreasing time and storage utilization.

first fit하고 best fit은 속도나 메모리사용률 측면에서 worst fit보다 좋은것으로 시뮬레이션에 나타났다.

 

지금 현재 실제 일반 사용자가 프로세스를 만들고 없애고 만들고 없애고 할 때 그 만드는 프로세스의 크기를 조사해서

시뮬레이션을 해봤더니 first-fit하고 best fit이 worst fit보다는 성능이 좋더라.

 

Neither first fit nor best fit is clearly better than the other in terms of storage utilization, but first fit is generally faster.

그럼 탈락한 worst fit은 빼고 first fit하고 best fit하고 비교를 해봤겠죠, 단순하게 생각하면 최적에 넣는게 제일 좋을 것 같지만 연구결과에 의하면 first fit이나 best fit이나 메모리 효율에 그렇게 차이가 없다고 나왔습니다.

 

그러니까 그냥 랜덤하게 집어 넣는거나 크기를 재면서 집어 넣는거나 크게 차이가 없다라고 얘기 할 수 있습니다.

 

그런데 알고리즘의 complexity를 생각해 볼 때 만약에 hole이 많다라고 가정하면, hole이 만약에 100개였다!

쭉 재다가 첫 번째꺼를 딱 선택을 하는게 first fit이겠죠? 그런데 best-fit, worst-fit은 hole이 100개면 100번을 다 비교해봐야 해요. 알고리즘적으로는 당연히 first-fit의 성능이 우수합니다.

 

물론 시스템 trace data에 따라 즉 시뮬레이션 결과에 따라 first fit이 더 적합할 수도 있고 best fit이 더 적합할 수도 있죠~ 이건 대게 그렇더라 입니다.

그래도 이러나 저러나 문제다 - 50퍼센트룰

그런데 fisrt fit이던 best fit이던 어떤 알고리즘을 쓰던, 결국 외부단편화는 발생합니다. A에 넣던 B에 넣던 C에 넣던 결국 완전 딱 맞는 크기 아니면 hole이 발생하잖아요. 일단 값비싼 메모리를 낭비한다는거 자체가 문제...

 

In the worst case, we could have a block of free (or wasted) memory between every two processes. If all
these small pieces of memory were in one big free block instead, we might be able to run several more processes.

가장 최악의 경우에는, 두개의 프로세스 사이사이에 hole이 발생할 수도 있어요. 이런 조그만한 작은 조각들을 다 뭉쳐보면 여러 프로세스를 돌릴 수 있는 꽤 큰 메모리일 수도 있겠죠.

 

물론 메모리 자투리가 남았을 경우 compaction으로 합치는 방법도 있지만 이 방법은, I/O problem을 야기한다고 했죠~

 

Statistical analysis of first fit, for instance, reveals that, even with some optimization, given N allocated blocks,

another 0.5 N blocks will be lost to fragmentation. That is, one-third of memory may be unusable! This property is known as the 50-percent rule.

first-fit 기준으로 한 통계에 의하면, N개의 블럭이 할당되었을 때 0.5개의 블록이 단편화때문에 손실될 수 있다고 합니다. 이건 기억장치의 3분의 1이 쓸 수 없게 된다는 거고(총 1.5중에 0.5가 손실), 이러한 현상을 50퍼센트 규칙이라 불러요. (할당된게 N 못쓰는게 0,5 비율은 50프로)

마무리

External fragmentation 문제 때문에 자투리 공간이 생겨서 쓸데없는 공간이 너무 많다 이거는 운영체제 하는 사람으로서 용납 할 수 없다. 왜? 메모리는 엄청나게 비싼 자원이니까. 그래서 새로운 방법을 만듭니다. 그 새로운 방법은 paging이예요.

 

지금까지 보여준 방법은 프로세스 크기별로 메모리를 할당하죠. 그래서 이를 가변분할이라고 합니다. 모든 프로세스 크기가 동일한게 아니니까요! 어떻게 집어넣던 프로세스 크기가 제각각일 경우 외부단편화 발생을 막을 수 없다는걸 깨달은거죠. 그것도 많이 발생해 메모리를 낭비할 확률이 높은 ! 

 

그래서 나온게 paging으로 메모리를 고정된 크기로 할당시키는 겁니다. 이러한 방법을 고정분할이라고 불러요! 

 

단편화는 외부단편화 내부단편화 두 가지로 나눌 수 있는데, 내부단편화는 고정분할로 인해 발생하게 됩니다. 아직 paging이 뭔지 몰라서 잘 안들어올 수 있는데 그렇구나 정도로 알아두면 돼요.

다음 포스팅에서는 paging에 대해 본격적으로 들어가도록 할게요 :) 

 

오늘도 고생하셨습니다. 도움이 되는 포스팅이였으면 공감/댓글/광고보답 중 하나는 어떤가요?!

정보공유 힘쓰는데 하나의 보람이 된답니다 :)