프로세스는 매모리 내의 빈 공간에 적재되어야 한다. 메모리 내에 빈 공간이 여러 개 있다면 프로세스를 어디에 배치해야 할까? 비어 있는 메모리 공간에 프로세스를 연속적으로 할당하는 방식을 알아보자.
여기에는 대표적으로 최초 적합(First-fit), 최적 적합(Best-fit), 최악 적합(Worst-fit)의 세 가지 방식이 있다.
이 메모리에다가 2칸의 공간을 차지하는 데이터를 저장하려고 한다고 가정하자.
이때 메모리 할당 알고리즘마다 어떻게 데이터를 저장하는지 알아보자.
📌 최초 적합 (First-fit)
최초 적합은 가장 최초로 발견되는 곳에 데이터를 저장한다. 메모리를 순차적으로 탐색하다가 가장 먼저 발견한 곳에 데이터를 저장하는 방법이다.
📌 최적 적합 (Best-fit)
최적 적합은 데이터가 저장되기에 가장 적절한 곳에 데이터를 저장한다.
메모리를 탐색해서 가장 먼저 발견한 가장 적절한 곳을 찾아 데이터를 저장하는 방법이다.
즉, 가장 딱 맞는 곳에 데이터를 저장하기 대문에 메모리의 낭비가 가장 적다.
이렇게만 보면 최적 적합이 가장 좋아보이지만 처음부터 끝까지 모두 탐색을 해야한다는 단점이 있다.
그만큼 비교를 많이 해야하고 그렇기 때문에 시간이 오래걸린다.
📌 최악 적합 (Worst-fit)
최악 적합은 프로세스를 적재하는데 가장 크기가 안 맞는 곳에 프로세스를 적재하는 방법이다.
딱 맞는 공간이 있는데도 데이터의 크기와 가장 안맞는 메모리에 저장하기 때문에 Worst이다.
최악 적합도 최적 적합처럼 하나하나 탐색을 해야한다.
메모리 낭비까지 발생하기 때문에 가장 선호도가 낮다.
📌 외부 단편화 (external fragmentation)
프로세스를 메모리에 연속적으로 배치하는 연속 메모리 할당은 당연하게 느껴질 수 있지만, 사실 이는 메모리를 효율적으로 사용하는 방법이 아니다. 왜냐하면 연속 메모리 하랑은 외부 단편화라는 문제를 내포하고 있기 때문이다.
아무런 프로세스도 적재되지 않은 상태의 메모리 전체를 생각해봅시다.
운영체제 영역에는 운영체제가 적재되어 있고, 사용자 영역에는 어떠한 프로세스도 적재되어 있지 않다.
이제 사용자 영역에 하나둘씩 프로세스들이 적재되는 상황을 가정해보자. 이때 사용자 영역의 크기는 200MB라고 하자. 사용자 영역에 크기가 50MB인 프로세스 A, 30MB인 프로세스 B, 100MB인 프로세스 C, 20MB인 프로세스 D를 차례대로 적재해야 한다면 이 프로세스들을 메모리에 어떻게 배치하는 것이 좋을까?
차례대로 적재하면 모두 200MB이기 때문에 저장 공간에 딱 맞게 적재된다.
이제 프로세스 B, D의 실행이 끝났다고 해보자. 이 프로세스들은 실행이 끝났기 때문에 더 이상 메모리에 남아 있는 필요가 없다.
프로세스 B, D가 메모리를 떠나면 메모리에 A,B,C,D 순으로 적재되어 있던 프로세스들이 A(50MB), X(30MB), C(100MB), X(20MB) 와 같은 상태가 되고 'X' 와 같은 총 30MB, 20MB의 빈 공간이 생긴다.
한 가지 질문이 있다. 현재 메모리에 남아 있는 빈 공간의 총합은 몇 MB일까?
당연히 50MB이다.
그렇다면 두번째 질문이 있다. 현재 상황에서 50MB 크기의 프로세스를 적재할 수 있을까?
불가능하다.
빈 공간의 총합은 50MB이지만 빈 공간이 따로 떨어져 있기 때문에 50MB 크기의 프로세스가 적재될 수 없기 때문이다.
프로세스들이 메모리에 연속적으로 할당되는 환경에서는 위와 같이 프로세스들이 실행되고 종료되기를 반복하며 메모리 사이 사이에 빈 공간들이 생긴다. 프로세스 바깥에 생기는 이러한 빈 공간들은 분명 빈 공간이지만 그 공간보다 큰 프로세스를 적재하기 어려운 상황을 초래하고, 결국 메모리 낭비로 이어진다. 이러한 현상이 외부 단편화이다.
⭐️ 메모리 할당 알고리즘 First fit, Next fit, Best fit 결과
메모리 할당 알고리즘 First fit, Next fit, Worst fit 결과
First fit : 메모리의 처음부터 검사해서 크기가 충분한 첫번째 메모리에 할당
Next fit : 마지막으로 참조한 메모리 공간에서부터 탐색을 시작해 공간을 찾음
Worst fit : 프로세스를 적재하는데 가장 크기가 안 맞는 곳에 프로세스를 적재
출처
Tech Interview for developer
혼자 공부하는 컴퓨터 구조 + 운영체제
https://normaldy.tistory.com/13
