연속 메모리 할당 - 메모리단편화, 최초적합, 최적적합, 최악적합

1. 다중 프로그래밍 환경

다중 프로그래밍 환경이란 하나의 메인메모리에 여러 개의 프로세스가 실행될 수 있다.

- 부팅 직후 메모리 상태 : O/S + big single hole

- 프로세스 생성 & 종료 반복 →  scattered holes

 

부팅 직후 메인메모리에는 어떠한 프로세스도 아직 올라와있지 않기 때문에 하나의 빈 공간(hole)만이 있다.

여기서 프로세스가 생성되고 종료되는 것을 반복하면 프로세스가 빠져나간 자리는 빈 공간으로 남는다.

scattered holes가 만들어지는 과정

2. 메모리 단편화 (Memory fragmentation)

프로세스 실행과 종료를 반복하고 나면 Hole들이 불연속하게 흩어져 있기 때문에 프로세스 적재가 불가능한 상태가 된다.

프로세스가 들어갈 공간이 충분한데도 불구하고 hole들이 흩어져있어 적재를 못하는 현상을 외부 단편화(external fragmentation)라 한다.

 

예를들어 100, 50, 80byte 공간의 hole들이 있다고 하자. 이때 110byte의 프로세스를 적재하려고 한다면 프로세스 내에 이미 충분한 공간이 있음에도 적재를 못하는 상황이 발생한다.

이러한 외부단편화 현상을 최소화하려면 메모리를 프로세스에게 어떻게 할당할지가 중요하다.

3. 연속 메모리 할당 방식

- First-fit (최초적합) : 메모리를 위에서부터 순차적으로 서치

- Best-fit (최적적합) : 메모리 크기가 제일 비슷한 Hole 선택

- Worst-fit (최악적합) : 메모리 크기가 제일 크게 차이는 Hole 선택

 

할당 방식 성능 비교 : 속도 및 메모리 이용률

- 속도 : first-fit

- 이용률 : first-fit, best-fit

4. 문제점

외부 단편화로 인한 메모리 낭비 : 1/3수준 (사용불가)

=> 900MB의 메모리의 경우 보통 300MB는 외부단편화로 인해 사용할 수 없게 된다.

5. 해결방법

Compaction : 흩어져 있는 홀들을 한곳으로 모은다.

=> 최적 알고리즘 없음; 프로세스 크기, 홀 크기에 따라 흩어져있는 홀을 모으는 방법은 매우 복잡해진다.

       고부담; 메모리를 움직여야 하기 때문에 부담이 크다.

 

외부 단편화를 완전히 해결하는 방법으로 페이징(Paging)이 있다.