운영체제 7.2 메모리 분할

메모리분할기법에 대해 이야기해보자.

분할은 메인 메모리를 쪼개는 것인데 그 쪼갠 곳에 프로세스가 올라간다.

분할은 여러가지 방법이 있다. 

 

1. 고정분할

고정된 경계를 가진 메모리영역으로 메인 메모리를 쪼개는 방법이다.

 

고정 분할시 분할하는 것의 크기를 어떻게 할까?

1)균등분할 : 각분할이 모두 같은 크기를 가지게 하는 방법. 

한 프로세스의 크기가 분할의 크기보다 작거나 같다면, 사용가능한 파티션중 하나에 적재된다.

모든 파티션이 사용중이지만 준비상태거나 실행상태의 프로세스가 없다면?! 운영체제는 어느 한 파티션의 프로세스를 스왑아웃 시키고 다른 프로세스를 적재하여 프로세서가 쉬지 않도록 한다. 

균등분할의 문제점:

1)프로그램이 파티션보다 크다면 오버레이를 사용하는 프로그램을 설계하여 어느 순간에는 프로그램의 필요한 부분만 주 기억장치에 있도록 해야한다. 현재 적재되어있지 않은 모듈이 필요하다면 사용자프로그램은 해당 프로그램의 파티션에 어떤 프로그램이나 데이터가 있든 간에 덮어써서 원하는 모듈을 적재시킨다.

2) 주 기억장치 이용이 매우 비효율적이다. 매우 작은 크기의 프로그램이라도 전체의 파티션을 차지한다. 

2MB보다 작은 프로그램이 있다고 하자. 만약 8MB크기의 파티션으로 프로그램을 나눴다면 전체 8MB를 차지하므로 비효율적이다.

이처럼 파티션 내부공간의 낭비가 발생하는걸 interner fragmentation이라고 한다.

 

 

배치 알고리즘(placement algorithm)

균등분할한 메모리 내의 프로세스 배치 과정에 대해서 알아보자. 

사용가능한 파티션이 존재하기만 하면 프로세스는 해당 파티션으로 적재가 가능하다. 

왜냐하면 모든 파티션들은 같은 크기이므로 어떤 파티션을 사용하던지 차이가 없다. 

준비상태에 있지 않은 프로세스가 모든 파티션을 차지하고 있다면, 새로운 프로세스를 위한 공간을 만드기 위해 이 프로세스들중 하나가 스왑아웃 되어야 한다. 

어떤것을 스왑아웃 할것인가?(scheduling 을 통해 결정된다.)

 

비균등분할

비균등분할에서는 프로세스를 파티션에 할당하기 위해 두가지 방법이 가능하다.

1. 각 프로세스의 용량에 맞는 가장 작은 파티션을 할당하는 방법.

->각 파티션에 할당될 예정인 스왑아웃된 프로세스들을 유지하는 스케줄링 큐가 필요하다. 

이 방법의 장점은 internal fragmentation을 최소화 시킬 파티션에 적재된다는 것이다.

이방법은 각각의 파티션의 관점에서 보면 최적으로 보이겠지만 전체적인 시스템의 관점에서 보면 그렇지 않다. 엄청 큰 파티션이 크다는 이유로 작은 프로세스를 적재할 수 있음에도 쓰이지 않은 채로 방치될 수 있기 때문이다. 

그래서 하나의 큐로 모든 프로세스를 처리하는 방법이 더 자주 사용된다. 

2.하나의 큐로 모든 프로세스를 처리하는 방법.

프로세스를 메모리에 적재할 시점에서 사용가능한 파티션중에서 프로세스를 적재할 수 있는 가장 작은 크기의 파티션이 선택된다. 

모든 파티션이 사용중이라면 스와핑이 이루어져야 한다. 새로운 프로세스를 적재할 수 있는 가장 작은 크기의 파티션을 사용중인 프로세스를 스왑아웃 시킬 수 있다.

또한 우선순위와 같은 다른 요소를 고려하거나 준비상태보다는 블록상태의 프로세스를 먼저 스왑아웃 하는것도 가능하다. 

비균등 분할방법을 사용하면 고정분할 기법도 어느정도 융통성을 가진다. 

그리고 고정분할기법은 비교적 간단하고 운영체제 소프트웨어의 기능을 최소로 하고 처리 오버헤드 역시 최소로 한다고 할 수 있다.

비균등분할방법의 단점

->시스템 생성시간에 미리 정해진 파티션의 수에 의해 시스템내에서 활성화된 프로세스들의 개수가 제한을 받는다.

->시스템 생성시간에 파티션의 사이즈가 미리 정해지기 때문에 크기가 작은 작업들의 경우 파티션 공간을 효율적으로 활용할 수 없다.  

 

 

동적분할

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

동적분할에서 파티션의 크기와 개수는 가변적이다. 한 프로세스가 main memory로 적재될때 정확히 요구된 크기의 메모리만 할당받는다. 

64MB의 메인메모리를 사용하는 경우를 생각해보면, 처음3개의 프로세스는 운영체제가 끝난곳으로부터 적재된다. 그 프로세스들은 각 프로세스에 딱 맞는 공간을 차지한다.

그렇게되면, 프로세스 4를 배정하기에는 너무 작은 메모리가 하나 남게 된다. 구멍(hole)처럼 생겼다.

어느순간 main memory에 준비된 프로세스가 하나도 없다면, 운영체제는 프로세스2를 스왑아웃하여 메모리를 확보한다.(프로세스 4의 크기보다 큰거중 가장 작은거를 스왑아웃 하는듯?) 

프로세스4가 프로세스2보다 작기때문에 또 하나의 작은 구멍이 형성된다. 

이후 다시 주기억장치 내의 모든 프로세스가 준비상태가 아니고, 프로세스 2가 ready-block상태로 수행가능한 시점이 되면, 운영체제는 프로세스2를위한 충분한 공간이 없기때문에 플세스 1을 스왑아웃하고, 2번프로세스를 그 자리로 불러들인다.

 

그림이 없어서 설명이 매우 부족했지만, 말하고자 하는것은

이러한 방법은 처음에는 잘 동작하지만 결국은 main memory에 작은 구멍들이 다수 만들어진다. 

시간이 지날수록 external fragmentation이 발생하게 된다. 

external fragment : 파티션영역 이외의 메모리가 점차 사용할 수 없는 조각으로 변하는 현상. 

external fragment를 극복하는 방법: compaction(메모리 집약) 

compaction: 디스크 조각모음처럼, 프로세스가 사용하는 파티션을 이동시켜 각 파티션이 연속적이 되도록 인접하게 만들고, 메모리의 모든 빈 공간이 하나의 블록이 되는것. 파티션을 탁탁 모아줘서 빈공간 크게 해주는것!

compaction은 시간이 많이 걸리며, 처리기 시간을 낭비한다는 단점이 있다.

 

 

배치 알고리즘

compaction은 많은 시간이 소모되는 작업이기 때문에, 운영체제를 설계하는 사람은 프로세스에게 메모리를 할당하는 (구멍을 어떻게 막을 것인가) 하는 방법을 현명하게 결정해야 한다. 

프로세스를 주기억장치로 적재하거나 swap-in하려고 할 때, 충분한 크기의 사용가능한 프로세스 블록이 2개 이상 있다면, 운영체제는 어떤 블록에 프로세스를 할당해야 할것인가? 를 고민해보자.

고려가능한 배치 알고리즘은 

best-fit,   first-fit,   next-fit 3가지가 있다. 

1. best-fit: 요청된 크기와 가장 근접한 크기의 메모리를 선택한다. best이지만 가장 성능이 나쁘다. 요구를 만족시키는 가장 작은 블록을 찾아 배정하기 때문에 엄청 작은 hole이 많이 생긴다. 그러므로 compaction이 다른 알고리즘보다 더욱 많이 수행되어야한다.

2.first-fit: 메모리의 처음부터 검사해서 크기가 충분한 '첫번째' 사용가능한 메모리블록을 선택한다. ->가장 간단하고, 대부분의 경우의 최적이며, 가장 빠르다. 하지만 메모리의 앞부분에 여러개의 작은 자유메모리를 만들어내는데, 최초적합 조사를 할때마다 이들이 매번 검사되어야한다. 

3.next-fit: 가장 최근에 배치되었던 메모리의 위치에서부터 검사를 시작해 크기가 충분한 다음위치의 사용가능한 메모리 블록을 선택한다.

-> 최초적합보다는 약간 나쁘다. 메모리의 마지막 부분에 있는 사용가능한 블록으로부터의 배정이 자주 일어난다. 그 결과, 보통 메모리 공간의 끝에있는 가장 큰 크기의 메모리를 짧은시간 내에 작은 크기로 조각낸다. 그러므로 더 자주 compaction이 필요하다. 

 

 

교체 알고리즘

동적할당을 사용하는 멀티프로그래밍 시스템에서는 main memory의 모든 프로세스가 대기상태이고 compaction이후에도 추가의 프로세스를 생성하기 위한 충분한 메모리가 없을 경우가 있다. 

대기중인 프로세스가 대기상테에서 해제되기를 기다리며 처리기시간을 낭비하는 것을 방지하기 위하여 운영체제는 main memory에 있는 프로세스중 하나를 스왑아웃시켜 준비상태의 새로운 프로세스나 준비-정지 상태의 프로세스가 들어올 공간을 만든다. 그것은 가상메모리 기법때 이야기해보자.

 

Buddy System

고정분할이나 동적분할 모두 결점을 가진다. 

고정분할: 활성프로세스 수가 제한됨,

동적할당: 유지하기 복잡, compaction 해야함.

그래서 버디 시스템이라는 방식을 이용한다. 

버디시스템은 1MB의 블록을 사용한다면 

계속 2개씩 나눈다.

100kb크기를 요구하는 블록을 넣고싶다면

(512,512) ->(512,256,256)-> (500,256,128,128)이렇게 해서128짜리에 할당시킨다. 

다음요청 을 256kb크기를 요구한다면, 이미 256짜리 있으니까 바로 할당된다.

100kb짜리의 요청이 해제되면 다시 128 두개는 256하나로 합쳐지고, 

256kb요청도 해제된다면 다시 1MB로 다시 합쳐진다. 

 

 

재배치 

 

분할기법의 단점을 해결하는 방법을 고려하기 전에, 메모리상의 프로세스 배치에 관한 사항을 마무리지어야한다.

고정분할기법을 사용할 경우, 특정프로세스는 항상 같은 파티션에 할당될 것이라는 걸 예상할 수있다. 

->새로운 프로세스가 적재될 때 선택된 파티션이 그 프로세스가 스왑 아웃되었다가 다시 적재된 파티션과 똑같다. (재배치가 간단하다는 뜻)

프로세스가 처음 적재되어질때 코드안에 있던 메모리를 참조하기 위해 있는 상대적인 주소들은 적재된 프로세스의 시작주소를 기준으로 결정되는 main memory내의 절대주소로 바뀌게 된다. 

균등분할이나 단일큐를 쓰는 비균등분할의 경우에는 프로세스는 생존기간동안 다른 파티션에 적재될 수 있다. 처음 프로세스의 이미지가 만들어지면 mainmemory에 있는 한 파티션으로 적재된다. 

나중에 그 프로세스가 swap-out되고 그후에 다시 swap-in 될때, 마지막으로 적재되었던 파티션과는 다른 파티션에 적재될 수 있다. 

동적할당의 경우도 마찬가지이다. 

compaction할때도 옮겨질 수 있다. 

->프로세스에 의해 참조된 위치는 고정이 아니라는말!