VPM : Variable Partition Multiprogramming
🔔 Internal Fragmentation을 없애는 기법
✔ Partition의 상태가 계속 변화할 수 있는 멀티프로그래밍 기법이다.
✔ 초기에는 모든 파티션이 하나의 큰 블록이다.
✔ 프로세스가 들어오고 나가는 과정에서 파티션은 dynamically 변화한다.
📌 Example
a) 초기상태: 하나의 큰 파티션 (120MB)
b) process a 적재 : 20mb partition 1 생성
b) process a 적재 : 20mb partition 1 생성
c) process b 적재 : 10mb partition 2 생성
c) process b 적재 : 10mb partition 2 생성
d) process c 적재 : 25mb partition 3 생성
d) process c 적재 : 25mb partition 3 생성
e) process d 적재 : 20mb partition 4 생성
e) process d 적재 : 20mb partition 4 생성
f) process b : exits or swap-out
memory를 뺏기고 나가거나 종료되어 나가는 상황. 10mb는 빈 공간이 된다.
f) process b : exits or swap-out
g) process e 진입 : 15mb인데 10mb 공간은 부족하므로, 5번 partition 중 할당 받는다.
g) process e 적재: 15mb
h) process d : exits or swap-out
D가 종료되거나 swap-out 되어서 나가므로 20mb 빈공간이 된다.
👇 VPM과 FPM의 비교
FPM은 파티션수가 고정이지만 VPM은 파티션수가 동적으로 변화한다.
따라서 필요한 공간만 할당해주므로 Internal fragmentation 사라지고 파티션내 낭비되는 공간이 사라진다.
External Fragmentaion은 존재한다.
파티션 빈공간이 10, 20, 30MB인 상황에서 만약 35mb 프로세스가 들어오면면 이때 10, 20, 30을 합칠수없으니 프로세스가 들어오지 못한다.
✅ VPM의 Placement Strategies
프로세스 a가 진입하려고 하는데, 사이즈가 S라고 가정해 보자.
빈 파티션 공간을 찾으면서 동시에 사이즈가 S 이상인 곳을 찾아야 하는데, 어떻게 찾을 수 있을까?!
1) First Fit = 최초 적합
파티션의 처음부터 탐색한다. (Sequential Search)
빈 공간이면서 사이즈가 S 이상인 첫 번째 파티션을 찾을 때까지 하나 하나 탐색한다.
단순하고 낮은 오버헤드의 장점이 있다.
진입하려는 프로세스의 크기가 20mb일 때, 시스템의 빈 공간들이 순차적으로 30, 50, 22, 26mb라고 생각해 보자.
First Fit은 바로 30mb인 공간에 할당할 것이다.
2) Best Fit = 최적 적합
전체 프로세스 a를 수행할 수 있는 파티션 중 가장 작은 공간(Minimum)에 할당한다. 더 큰 파티션은 추후 나중에 더 큰 프로세스가 들어오는 것에 대비하여 남겨둔다.
진입하려는 프로세스의 크기가 20mb일 때, 시스템의 빈 공간들이 순차적으로 30, 50, 22, 26mb라고 생각해 보자.
Best Fit은 전체를 탐색한 후, 22mb에 할당할 것이다.
탐색 시간이 길다.
큰 사이즈의 파티션을 reserve할 수 있다.
다만 매우 작은 파티션들이 많이 생성되는 문제가 있다.(22mb에서 20mb를 빼면 2mb인데, 이 정도의 크기는 거의 사용하기 어렵다)
이로 인해 External Fragmentation 문제가 있다.
3) Worst-Fit
전체 프로세스 a를 수행할 수 있는 파티션 중 가장 큰 공간(Minimum)에 할당한다.
아주 작은 사이즈의 파티션들의 개수를 줄일 수 있다.
그러나 아주 큰 공간을 reserve하는 장점은 사라진다.
진입하려는 프로세스의 크기가 20mb일 때, 시스템의 빈 공간들이 순차적으로 30, 50, 22, 26mb라고 생각해 보자.
Best Fit은 전체를 탐색한 후, 50mb에 할당할 것이다.
이 경우 20mb를 제외한 30mb에 다른 프로세스가 할당될 수 있다.
4) Next-Fit
First-Fit은 처음부터 탐색을 하는 기법인데, Next Fit 기법은 이전 탐색이 끝난 지점부터 탐색을 다시 재개하는 기법이다.
오버헤드가 적은 기법이다.
Circular Search the State Table, Uniform Use for the Memory Partitions
💨 어떤 기법이 좋은 기법일까?
어떤 기법이 가장 좋은 방법인지 찾는 것도 중요하지만, Best Fit과 Worst Fit은 오버헤드가 크면서 각각 단점도 갖고 있기 때문에 First Fit과 Next Fit이 많이 사용된다.
📌 Coalescing Holes
VPM기법에서 무조건 사용해야 하는 기법
두개의 인접한 연속된 파티션을 하나로 묶어주는 작업
(a) 상태에서 프로세스 A가 나가면 (b) 상태가 된다.
이 때 25MB 프로세스가 진입하려고 할 때, First Fit은 마지막 30MB 파티션을 선택할 것이다.
그러나 꼭 이것이 옳은 방법일까?
맨 앞의 20MB, 10MB를 합칠 수 있다! 그리고 여기에 20MB 프로세스를 할당하자.
Coalescing Holes를 하지 않으면 파티션의 개수가 계속 늘어나기 때문에 머지를 해주어야 한다. 이 작업은 테이블 조작만으로 가능하기 때문에 오버헤드도 적다!
위와 같이 3개의 연속적인 공간 역시 Coalescing Holes 작업을 수행할 수 있다.
📌 Storage Compaction
모든 Free Memory를 큰 하나의 블록으로 몰아 넣는다.
오버헤드가 크며, 시스템 자원을 많이 소비한다.
CPU 타임을 많이 소비하므로 Storage Compaction은 함부로 할 수 있는 것이 아니다!
(a)와 같은 상태에서 새로운 프로세스 40mb가 진입을 시도한다고 가정하자. 이 때 빈 공간은 10mb, 20mb, 30mb 뿐이므로 진입가능한 공간이 없다.
프로세스 E가 중요하지 않은 프로세스라면, 이 프로세스를 Swap-out시키고 colaescing holes를 통해 해당 파티션을 60MB로 만들어서 프로세스를 할당할 수 있다.
다른 방법은 Storage Compaction이다.
빈공간을 한 군데로 몰아 넣고, A, C, E를 반대쪽 끝으로 몰아 넣는다.
그러나 이것은 굉장한 오버헤드를 수반한다.
C를 옮겨야 하는데 메모리에서 바로 메모리로 이동될 수 없기 때문에 CPU로 읽어서 다시 메모리에 갖다 써야 한다.
이 동안 CPU는 다른 일을 할 수 없다.
