Memory Management #2 - 메모리의 분할, 고정분할/동적분할

※Memory Management

메모리 관리의 주된 작업은

처리기(프로세서)에 의해 실행될

프로세스(프로세스 이미지)를 메인 메모리로 가져오는것이다.

모든 멀티프로그래밍 시스템에서는 가상 메모리라는 기법을 사용하는데,

이 가상 메모리는 세그멘테이션과 페이징이라는 기법을 기반으로 설계되었다.

가상 메모리는 하나의 기법을 이용하거나 둘의 기법을 다 사용할 수 있다.

우선 가상 메모리를 사용하기 전에 사용된 여러 기법들이 있다. 

그 기법들을 먼저 알아보고자 한다.

※Memory Partitioning ( Fixed Partitioning / Dynamic Partitioning )

운영체제는 메인메모리의 일부 고정된 부분을 차지하고 나머지 부분은 다수의 프로세스들의 사용을 위해 남겨준다. 이 사용가능한 메인 메모리를 관리하는 가장 단순한 기법은고정된 경계를 갖는 메모리 영역으로 구분하는것이다.

분할의 방법은 고정 분할과 동적 분할이 있다. 배열로 예를 들어 볼 수 있다. 

예를 들어, 아래 2개의 명령어는 같은 크기의 메모리 공간을 가지겠지만, 생각과 개념이 다르다. 

1) int arr[10]; 

2) int *arr = (int*)malloc(sizeof(int) * 10);    

먼저 고정 분할부터 알아보겠다.

고정분할은 균등 분할 / 비균등 분할 로 나누어진다.

※균등 분할

각 분할이 모두 같은,균등한 크기를 갖도록 함.

프로세스가 사용가능한 메모리가 30MB가 있다고 가정하자. 

그렇다면 10MB / 10MB / 10MB 혹은 15MB/15MB 로 균등하게 나뉘어 질것이다.

이 경우 한 프로세스의 크기가 분할의 크기보다 작거나 같다면 load된다.

모든 파티션이 사용 중이고, 준비 또는 실행 상태의 프로세스가 없다면,

운영체제는 어느 한 파티션의 프로세스를 스왑아웃시키고, 다른 프로세스를 load 한다.

그리고 프로세서가 스왑인 된 프로세스에게 할 일을 공급한다.

TIP : 

Disk에서 메인 메모리로 가져오는 역할은 OS가 하고, 할 일의 공급은 프로세서가 한다.

※균등 분할의 단점(Disadvantage)

1.

프로그램이 파티션보다 크면, 

프로그래머는 오버레이를 사용하는 프로그램을 설계하여,

어느 순간에는 프로그램의 필요한 부분만 메인메모리에 있도록 해야한다.

현재 load되어 있지 않은 모듈이 필요하다면,

사용자 프로그램은 해당 프로그램의 파티션에 어떤 프로그램이나 데이터가 있든간에 덮어 써서 원하는 모듈을 load한다.

2. 

메인메모리 이용률이 적어진다. 

작은 크기의 프로그램이라도 전체의 파티션을 차지한다.

예를들어 2MB 프로그램을 실행하는 각 파티션이 8MB라면,

2MB 프로그램은 8MB 공간을 전체를 잡고 있고, 6MB는 낭비가 된다.

이처럼 load 되는 데이터가 파티션보다 작을때,

파티션의 내부 공간의 낭비가 발생하는 현상을 내부 단편화라고 한다.(internal fragmentation)

※OS는 균등분할의 경우 어떻게 메인 메모리로 배치 시킬까? How to Assign Memory?

균등 분할의 방식의 경우, 프로세서가 사용가능한 메모리가, 균등한 크기, 즉 동일한 크기로 나누어져 있기때문에 비어있는 파티션만 있다면 바로 load가 가능하다.

준비상태가 아닌 프로세스가 모든 파티션을 차지하고 있다면 프로세스들 중 하나가 스왑아웃되어야한다. 어느것을 스왑아웃 시킬지는 스케줄링 정책에 따라서 결정된다.

※비균등 분할

비균등 분할이란 프로세스를 위해 남겨진 메인 메모리의 영역을 비균등하게, 다른 크기로 파티션하는것이다.

※OS는 어떤 방식으로 메인 메모리를 배치 시킬까? How to Assign Memory?

비균등 분할의 경우, 2가지 방법이 가능하다

1) 각 프로세스의 용량에 맞는 가장 작은 파티션을 할당한다, 이경우 각 파티션에 할당될 예정인 스왑아웃된 프로세스들을 유지하는 스케줄링 큐가 필요하다.

2) 프로세스를 메모리에 load 할 시점에 사용가능한 파티션 중에서 프로세스를 load할 수 있는 가장 작은 크기의 파티션이 선택된다. 만약 모든 파티션이 사용 중이면, 스와핑(스왑아웃/스왑인)이 이루어진다.

한개의 큐 vs 여러개의 큐

예를 들면, 어느 시점에 12M보다 크고, 16M보다 작은 크기를 가진 프로세스가 없을 경우, 16M 파티션은 그보다 작은 프로세스들이 적재될수 있음에도 불구하고, 사용되지 않은 채로 방치 될수 있다. 그러므로 하나의 큐로 모든 프로세스를 처리하는 방법이 더 좋다. 조금 더 상세하게 이야기 하자면 예를 들어 한 메모리공간이 16MB이고 (그림으로 봤을때 한곳의 메모리 공간이 16MB고 나머지는 10MB보다 작다고 가정해보자.) 현재 큐에 10MB, 12MB, 13MB, 14MB, 15MB 의 용량을 가진 프로세스들이 있다고 가정해본다. 

1) 하나의 큐가 있다면 15MB의 우선순위에 따라 15MB짜리 프로세스를 pop하여 메인 메모리로 load할 것이다. 그리고 그 프로세스가 수행을 끝내고 디스크로 스왑아웃되면 그 다음으로 큰 14MB가 들어가고 나오고 이렇게 반복될것이다.

2) 하지만 5개의 큐로 나뉘어져 있고, 위의 그림 처럼 순서대로 큐에 들어가져있다면, 10MB, 10MB, 12MB, 13MB, 14MB 는 큐에 있어도 메인 메모리로 load 되지 못할 것이고 계속 큐에 남겨져있다.

장점 :

내부 단편화 감소. 프로세스들이 항상 메모리의 낭비를 최소화시키는 파티션에 적재된다.

단점 : 

미리 정해진 파티션의 수에 따라 시스템 내에서 활성화된 프로세스의 수가 제한을 받는다.

예를들면 30M 의 공간이 있는데 20M랑 10M로 비균등 분할로 나누었다. 그렇다면 최대 프로세스가 2개가 준비 상태이거나 동작상태 일것이다.

추가적으로 파티션의 크기가 미리 정해져 있기때문에 크기가 작은 프로그램의 경우 파티션 공간을 효율적으로 활용이 불가능하다.

현재 고정 분할 기법을 체택한 운영체제는 거의 없다.

※동적 분할

고정 분할 기법의 발생하는 몇가지 문제점을 해결 하기 위해 동적 분할 기법이 개발 되었다.

동적 분할에서 파티션의 크기와 개수는 가변적이다. 한 프로세스가 OS에 의해 메인 메모리로 load되었을때, 정확한 크기 만큼만의 메모리만 할당받는다. 예를 들면 10MB짜리 프로세스가 업로드 될때 , 프로세스를 위한 메모리 30MB중 10MB만 분할하여 해당 프로세스에게 공간을 준다.

위의 그림을 참고해보자. 현재 메인 메모리의 용량은 64M이다. 그리고 OS가 8M의 메모리를 가지고 있다. 그래서 프로세스가 할당에게 할당할 수 있는 용량은 최대 56M이다. OS가 disk로 부터 20M 짜리 프로세스를 불러올 예정이다. 메인 메모리에서 20M만 동적으로 분할하려 프로세스1에게 할당해주었다. 프로세스2가 들어오면서 14M을 주었다. 프로세스3이 들어오면서 18M을 주었다. 그리고 프로세스4가 들어온다.그런데 프로세스4는 8M짜리인데 공간이 없다. 이때 확인해보니 메인 메모리의 프로세스2가 수행 혹은 준비 상태가 아니다. 그러므로 프로세스2를 스왑아웃했다.(프로세스2는 보류 상태가 된다.) 그리고 그 공간에 프로세스4가 8M 크기만큼만 할당받고 load되었다. 이때 6M짜리 '구멍'이 생겼다. 이때 프로세스1이 준비상태가 아니여서 스왑아웃되었고, 프로세스2는 준비-보류상태가 되었다. 그래서 프로세스2가 프로세스1 자리에 들어갔다. 이때, 프로세스2는 14M이기때문에 또 그 공간에 6M짜리 '구멍'이 생겼다. 

이렇게 진행을 반복하다가 보면 결국 메인 메모리에는 다수의 '구멍'들만 만들어 질 것이다. 메모리 단편화는 점점 심해지고 메모리 이용률은 감소된다. 모든 파티션 영역 이외의 메모리가 점차 사용할수 없는 조각으로 변하는 현상을 외부 단편화 (External Fragmentation)이라고 부른다.

외부 단편화를 위해서 메모리 집약(compaction) 이라는 기법이 개발 되었다. 메모리 집약이란, 프로세스가 사용하는 파티션을 이동시켜 각 파티션이 연속적이 되도록 인접하게 만들고, 메모리의 빈공간을 모으고 모아 하나의 분할된 메모리 공간으로 만든다는것이다.

위의 그림 (h)에서 본다면 6M + 6M + 4M 의 구멍 메모리들을 모아 16M의 메모리 공간을 만든다는 것이다.

하지만 이는 엄청난 시간을 낭비한다. 메모리 집약을 진행하려면 동적 재배치(Dynamic re-location) 기능이 필요하다. 예를 들어 보면 그림(h)에서 본다면 일단 프로세스4와 프로세스3을 스왑아웃 시켜 임시적으로 보관한다. 그렇다면 현재 사용 가능한 메모리는 42M이 될 것 이고(프로세스2만 남기때문에) 거기서 다시 프로세스4와 프로세스3을 프로세스2와 연속적으로 하기 위하여 동적으로 재배치를 하게 될것이다.

결국, 내부 단편화를 초래하는 고정 분할을 위해 동적 분할을 개발했더니, 외부 단편화 라는 문제점을 초래했다.

TIP )

메모리의 단편화 : 사용 할 수 있는 메모리를 점점 더 적게 만든다.

참고 : 운영체제 내부구조 및 설계원리 제6판 (William Stallings 지음)