.
.
.
main memory에 어떻게 process를 저장할 수 있을까?
아니 어떻게 '효율적으로' 저장할 수 있을까? 🧐
메모리 할당에는 여러 방법이 있다. 어떤 것을 사용하는 것이 좋을지 고민해부자!
1. Contiguous Allocation
우선, 연속적으로 할당하는 방법이 있다.
같은 주제의 내용이면, 와다다다 같이 붙여 놓는 거다.
예를 들어 하나의 process P1은 끊기지 않게 와다다ㅏ해놓고
또 다른 곳에 process P2를 끊기지 않게 와다다다! 하는 거다.
이렇게 와다다ㅏ하는 방법은 두 가지로 나눌 수 있다.
(아니, 어떻게?)
1) Two Partition Allocation
두가지 분류만 사용하는 방법이다.
OS와 OS가 아닌 것, 즉 사용자 프로그램. 이렇게 나누는 거다.
위에서 부터 low ~ high
이런 식으로. 하지만 요즘은 이렇게 잘 안 쓴다. 이 user program이라는 게 딱 하나를 말하는 것이기 때문!
2) Multiple-partition allocation
사용자 프로그램마다 memory partition을 나누어주는 방법이다.
① fixed size
고정된 크기의 partition으로 나누어주는 것이다.
각 partition은 하나의 프로세스만을 담고 있다.
main memory에 동시에 올릴 수 있는 process 수, 즉 degree of multiprogramming은 이 partiotion의 개수라고 볼 수 있다.
하지만 이 방법도 요즘은 잘 안 쓴다.
고정된 그 size보다 큰 process도 못 올리고, 훨씬 작은 process에 대해서도 남는 공간이 너무 많다. 비효율적이다!
② variable size
process를 넣고 빼고, 넣고 빼고 하면서 분명 지금 현재에 사용하지 않는 공간이 생긴다. 그걸 hole이라고 한다. : blocak of avaliable memory
순간순간마다 이 hole의 크기는 달라질 텐데, 큰 process가 빠지면 큰 hole이 생기고, 작은 process가 빠지면 작은 hole이 생기고!
이런 식이다.
자, 그러면 process가 도착했을 때 어떤 식으로, 여러 hole 중 어떤 hole으로 넣을지 결정하는 algorithm이 필요하다.
*일단 이를 하려고 하면, OS는 지금 할당되어 있는 allocated partition과 비어 있는 free partitions(hole)의 정보를 알고 있어야 한다.
- first-fit
어디 보자, 하고 찾다가 발견한 가장 첫번째 hole에 넣는 거다. 당연히 process가 들어갈만한 size의 hole을 찾는다. - best-fit
어디 보자, 하고 찾다가 들어갈만한 곳 중 가장 작은 hole에 넣는다. 모든 hole을 조사해봐야겠지. - worst-fit
이건 반대로 가장 큰 hole에 넣는다.
(대체 왜?) best fit에서 남는 부분 leftover가 아까워서 재사용하려고 그러는 거다.
하지만 first-fit과 best-fit이 worst-fit보다 속도, strage utilization에서 훨씬 낫다. 패배!
- 50% rule (잘 이해 못함)
N개의 할당된 block이 있다면 0.5N의 block은 넣을 수 없다. fragmentation 발생!
총 남아 있는 공간이 지금 넣으려는 process를 넣기에 충분하더라도, 연속적으로 있지 않아 process를 넣을 수 없다는 거다.
이때 1/3이 unusable이라는데, 이건 ...왜지!
Dynamic Storage Allocation Problem = Fragmentation
자아, 이 fragmentation이라는 것은 process를 할당할 수 없는 문제가 발생한다!는 의미다.
① External Fragmentation
빈공간을 모두 합하면 크기는 충분하지만, 연속적이지 않아 process를 할당할 수 없는 문제이다. 이것의 문제는 제-법 큰데, 결국 이것 때문에 비연속적 할당을 쓴다.
Compaction
줄이려는 시도는 할 수 있다. 어떻게?
shuffle하여, 신나게 흔들어서 한쪽으로 몰면, 제법 큰 공간이 생기니까 그 공간에 넣으면 된다. 하지만 이 신나는 과정이 쉬울까?
아니다. 굉장한 overhead를 낳는다!
또한 I/O problem도 발생한다. process(p1)가 수행 하다가 어떤 새로운 process(p2)를 메모리에 올리려고 자리를 마련하기 위해 shuffle을 한다. 그 후에 실행 중이던 process(p1)가 메모리를 참조하려는 순간..어라 주소가 바뀌었다! 어디갔어! 이렇게 된다.
I/O를 하는 process를 고정시키거나 OS buffer에 넣어서 실행한다거나, 하는 방법으로 이를 해결할 수도 있다. 하지만 이것도 보통 쉬운 일이 아니다..
그러니 비연속적 할당을 하자.
② Internal Fragmentation
process를 할당하고 남은 아쥬 작은 공간, process의 최소 크기보다 더 작은 공간은 참- 아깝지만 쓸 수가 없다. 이를 internal Fragmentation이라고 한다.
자, contiguous allocation은 참 문제가 많다. 그렇다면..! 비연속적 할당, non-cotiguous allocation에 대해 알아보자.
