[운영체제및실습] 11주차 4회차: 메모리 파티셔닝

이번 시간에는 고정 분할식 메모리 할당 방법과 가변 동적 메모리 할당 방법, 버디 시스템 할당 방법에 대해 알아보겠습니다.

 

1. Memory Partitioning : Fixed Partitioning

먼저 고정 할당 방법입니다. Fixed Paritioning은 한정된 크기의 메인 메모리 공간을 여러 프로세스에게 분배해주는 방법으로써 운영체제 개발자들이 제일 먼저 생각해낸 방법입니다. 운영체제는 메인 메모리를 미리 일정한 크기의 조각인 파티션으로 분할해 놓고, 사용자 프로세스가 생성하면(프로그램 실행), 메모리 공간 중 빈 것을 프로세스에게 집어넣는 방법입니다.

 

이 그림을 보면, 왼쪽처럼 메인 메모리가 있는데, 메인 메모리 윗부분에 OS가 들어가 있고, 사용자 프로세스가 들어갈 수 있는 부분을 일정한 크기로 조각을 내는 것입니다. 여기서는 8M바이트 짜리의 메모리 조각으로 나누었습니다. 이렇게 놓고 프로그램이 생기면 프로그램을 빈 파티셔닝에 넣으면 됩니다.

 

이것의 장점은 메모리 관리가 간단하다는 것입니다. 일정한 크기로 잘라서 메모리에 들어갈 수 있는 프로그램의 개수가 나오며, 어떤 프로그램이 몇 번째 조각에 들어가 있고, 빈 공간이 있는지 파악할 수 있어 간단합니다. 

단점으로는 메모리 이용 효율이 나쁘다는 것입니다. 8M 바이트 짜리를 파티셔닝했는데, 예를 들어 프로그램 크기가 1M정도밖에 안되는 프로그램이면, 1MB프로세스가 8M바이트 조각을 모두 사용하는 것입니다. 즉, 8M바이트를 할당받지만, 7B는 사용하지 않고 비게 되어서 fragment가 생깁니다. 프로세스에게 할당된 공간 내부에 있는 fragment를 internal fragment라고 하며, 이 현상을 internal fragmentation이라고 합니다. 프로그램들은 다양한 크기를 요구하는데, 같은 크기로만 파티셔닝해놓으면 융통성이 떨어지게 됩니다. interal fragmentation의 크기도 평균적으로 커지게 되는 문제가 있습니다. 그래서 이것을 개선하기 위해 나온 방법이 오른쪽처럼 하나의 크기가 아니라 다양한 크기로 메모리를 분할해놓는 것입니다. 이것도 fixed partitoning입니다. 하지만, 왼쪽은 똑같은 크기로 자르는 Equal-size partitions이며, 오른쪽은 다른 크기로 자르는 Unequal-size partitions입니다.

 

 

2. Dynamic Partitioning(가변 동적 분할 방법)

(a): 그림을 보면, 메인 메모리가 있다고 할 때, 8M바이트만큼 OS가 차지, 56MB만큼 사용자가 사용할 수 있다고 합시다.

(b): 20M 바이트 짜리 프로세스1번을 할당을 하고 남은 것은 36MB가 됩니다.

(c): 이 상태에서 14MB만큼 프로세스 2에게 할당하면, 남은 것이 22M바이트가 남습니다.

(d): 18MB 프로세스 3번에게 할당되면 남은 공간은 4B입니다.

(e): 프로세스 2가 실행을 끝내고 종료를 하면, 프로세스 2가 차지하던 14MB는 비어있게 됩니다.

(f):  8MB만큼 프로세스 4가 차지하면, 빈공간은 6MB, 4MB가 있습니다.

(g): 프로세스 1이 실행을 끝내고 종료를 하면, 프로세스 1이 차지하던 20MB는 비어있게 됩니다.

(h): 프로세스 2가 프로세스 1이 있던 자리를 일부 차지해 14MB공간을 할당받습니다.

프로세스에게 필요한만큼만 할당하는 방법이 가변동적메모리방법입니다. 즉, 그때그때 프로세스가 필요한 만큼 서로 다른 길이로 가변적으로 메모리를 변화해가며, 할당하는 방법입니다. 이렇게 Dynamic Partitioning은 프로세스 내부에서 안 쓰는 공간이 없어서 Fixed Partitioning에서 어느 부분은 쓰고, 어느 부분은 안 쓰는 부분이 존재하는 internal fragmentation이 없습니다. 그런데 대신, 여기서는 external fragmentation이 생깁니다. 그러니까 프로세스에게 배정되지는 않았지만, (f)에서 6MB, 4MB와 같은 비어있는 메모리 조각은 어느 프로세스에도 속하지 않는 외부 공간입니다. 이런 공간은 프로세스가 생겼을 때 들어갈 수도 있지만, 비교적 크기가 작아서 프로세스들이 크기가 작아 안 들어갈 가능성이 있습니다. 이런 안 쓰는 메모리 조각들이 외부 단편화입니다.  

 

작은 메모리 공간이 생겼을 때 큰 공간을 만드는 방법이 전에 봤던 컴팩션 방법입니다. 컴팩션은 빈 공간들을 한 쪽으로 몰아서 연속된 공간을 만듭니다. (h)에서 프로세스 4를 프로세스 2 바로 밑으로 이사를 보내고, 프로세스 3도 프로세스 4에 연이어지도록 위치를 옮기는 relocation을 하게 되면, 6M+6M+4M=16M바이트라는 큰 공간이 생기며, 여기에는 큰 프로세스도 들어갈 수 있게 됩니다. 이와 같이 컴팩션 방법을 사용할 수 있지만, 메모리를 읽고 쓰는 작업을 반복해 시간이 걸리기 때문에 좋은 방법은 아닙니다.

 

대가를 치루어야 하지만, 고정 분할 방법보다는 메모리 활용도를 높일 수 있습니다.

 

 

이런 가변 동적 할당 방법에서 메모리 관리를 하려면 OS는 메모리 이용 상황을 파악하고 있어야 합니다. 어떤 식으로 파악해야 하냐면, 그림과 같이 비어있는 메모리가 몇 바이트에서부터 얼마만큼이 비어있다라는 것을 테이블이나 linked list로 할당을 해야 합니다.

예에 보이는 것과 같이, 100번지에서 시작해서 2,048바이트만큼은 비어있다라는 것입니다. 비어있는 메모리 조각들의 시작 주소와 바이트 크기들을 목록으로 유지해야 합니다. 이러한 정보를 바탕으로 새로운 메모리 요청이 들어왔을 때 메모리 할당 방법을 알아봆시다.

---

3. Dynamic Partitioning Placement Algorithm

3-1. First-fit algorithm

먼저, 퍼스트핏 알고리즘을 알아봅시다. first-fit은 처음에 맞는 공간을 찾는 방법입니다. 이와 같은 식으로 메모리들이 비어있는 상태에서 크기가 7000B짜리 프로세스가 생겼다라고 하면, 빈 메모리의 리스트에서 index가 적은 순으로 찾아보면, 2,048B는 사용불가능, 5000B사용 불가능, 8,100B는 사용가능하므로 index 2공간을 차지하는 것이 first-fit방법입니다.

3-1. Best-fit algorithm

Best-fit 알고리즘은 처음부터 끝까지 리스트들을 조사해서 지금 필요한 프로세스 크기와 제일 비슷한 영역의 크기를 찾는 방법입니다. 7000B이면, 8,100B가 가장 크기가 비슷해서 이것이 골라질 것이며, 4,000B이면, first-fit인 경우, 위에서부터 찾아서 index 1을 골라서 index 2부터는 탐색을 하지 않지만, Best-fit의 경우에는 처음부터 끝까지 다 조사해서 크기가 비슷한 4,096B가 있으므로 index 4를 고릅니다. Best-fit알고리즘은 낭비가 적어지지만, 목록을 전부 살펴봐야 해서 더 시간이 걸립니다.

3-1. Worst-fit algorithm

Worst-fit방법은 best-fit방법에 정반대됩니다. 

Best-fit은 목록을 전부 조사 후, 가장 비슷한 크기를 찾는 데에 비해, Worst-fit은 목록을 전부 조사 후, 크기가 가장 차이가 나는 것을 골라서 사용하는 방법입니다. 

예를 들어, 4000B라고 하면, Best fit인 경우 index 4번을 고르겠지만, 할당하고 나서 남는 공간의 크기가 가장 차이가 나는 3번(80,000B, 시작 주소는 20,000)을 고릅니다. 그러면 4,000B는 사용 후, 7,600B는 새로 남으므로 목록에 새로 7,600B가 등장할 것이며, index 3은 없어질 것이며, 76,000바이트의 시작 주소는 24,000번지부터 76,000B가 빈다는 목록이 추가되어야 합니다.

 

그런데 왜 이게 생겨났을 까요?

그 이유는 알고리즘 적용 후 남는 공간이 worst-fit이 많이 남기 때문에 남은 공간을 이용할 가능성이 커지기 때문입니다.

만약 best-fit으로 4,096B를 할당했다고 하면 남은 공간이 96B이므로 인덱스 4가 없어지며, 새로 96B와 시작 주소의 항목이 추가될 텐데 96B는 남겨봤자 너무 작은 공간이어서 프로세스가 이용할 가능성이 매우 낮습니다. 반면, 크기 차이가 많이 남는 공간을 할당하면, 남는 공간도 크기 때문에 활용가능성이 높다라는 생각으로 제안된 방법입니다.

3-1. Next-fit algorithm

 

Next-fit은 first-fit과 같은 방법인데, 목록의 처음부터 찾는 것이 아니라 직전 알고리듬 실행 시에 찾았던 위치 그 다음부터 찾는 것입니다. 이것을 그림으로 보겠습니다. 

비어있는 공간은 흰색입니다. first-fit방법은 무조건 목록의 앞에서부터 빈 공간을 찾아냅니다. 

그런데 Next-fit은 찾았던 위치 다음부터 나한테 맞는 충분한 크기의 공간을 찾아나갑니다. Next-fit은 찾는 시간은 비슷한데 비해, 메모리 전체에 비해 골고루 공간을 할당해서 효율이 first-fit보다 더 좋습니다.

 

가변 동적 할당 방법은 요즘 사용되지 않습니다. 그래서 이 4개의 fit방법도 요새 사용되지 않는 방법입니다.

 

사용되지 않는 메모리 방법인데도 설명한 이유는 가변 동적 메모리 할당 방법이 요즘 사용되는 메모리 할당 방법에 base가 되기 때문에 학습합니다.

 

---

4. Buddy System

요즘 사용되는 방법으로써 버디 시스템을 알아봅시다. 

버디 시스템은 internal fragmentation을 허용하는 가변 동적 메모리 할당 방법입니다. 우리가 아까 봤던 Dynamic Partitioning, 가변 동적으로 하되, fixed partitioning에서 발생된 internal fragmentation을 허용하는 방법입니다.

즉, 고정분할방법과 가변분할방법을 합친 것이 이것입니다.

 

요즘에는 메인 메모리들이 값이 싸고, 큰 용량을 쓰기 때문에 버디 시스템에 효율적으로 활용될 수 있는 환경이 되었습니다.

 

이전절에서 살펴본 가변동적메모리 할당보다 개선된 것입니다.

 

가변동적할당 방법을 보면, (f)에서 8M바이트 만큼 프로세스를 사용하면, 6M바이트만큼 빈공간이 생깁니다. 또한, (d)에서 22M 빈공간이 있었는데, 18MB만큼 프로세스를 놓으면 4MB만큼 빈 공간이 남습니다. 프로세스를 할당하기 어려울 정도로 남는 크기가 작은 경우입니다. 즉, external fragment로 놓을 가능성이 많습니다. 

그러다보니 개선된 Buddy system에서는 4MB만큼 빈공간 남기면 목록 테이블에 작은 공간이 들어와서 나중에 테이블 조사 시에 시간만 낭비하기 때문에 아예 이 공간을 프로세스에게 줘버리자 하는 것입니다. 그럼 4M바이트는 external fragmentation에서 internal fragmentation으로 바뀌는 것입니다. 메모리를 좀 더 쓰려고 하다가 운영체제가 늦게 동작하는 것이 안 좋게 되므로 작은 빈 공간은 프로세스에게 줘버리자는 생각으로 Buddy System이 나왔습니다.

 

버디 시스템으로 메모리 할당하고 회수하는 방법을 알아봅시다.

먼저, 메모리 할당 방법입니다.

할당할 메모리 크기를 s라고 합시다. s가 현재 당시 비어있는 메모리 사이즈가 2^U라고 합시다.

s는 남아있는 공간인 2^U보다 같거나 작고, 2^(U-1), 즉 절반보다 크기가 크면, 2^U 내부에서 안 쓰는 공간이 있어도 (internal fragment) 그냥 주는 것입니다.

만약 그게 아니면, 전체 조각을 두 조각인 2^(U-1) 2조각으로 분할을 합니다. 

그 후, 2^(U-1) 조각에서 이 조건을 따져 보고, 반복적으로 수행합니다.

 

 

그림을 통해서 할당하는 알고리즘을 봅시다. 비어있는 메모리가 1M라고 합시다. 이 상태에서 프로세스 A가 100K를 요청하면, 2의 U제곱이 1M입니다. 할당해야 하는 s가 100인데, 1M보다 같거나 작으며 그것의 절반인 512K보다 크지 않기 때문에 512K를 2개로 만들어서 512K로 다시 조건을 따져봅니다. s라는 100은 512보다 같거나 작지만, 그것의 절반인 256보다 크지 않기 때문에 256K 2개로 나누어서 256K 하나에 대해 또 조건을 따져봅니다. 그러면 s라는 100은 256보다 같거나 작지만, 그것의 절반인 128보다 크지 않기 때문에 128K 2개로 나누어서 128K 하나에 대해 또 조건을 따져봅니다. s라는 100은 128K보다 같거나 작지만, 그것의 절반인 64K보다는 크므로 조건을 성립해서 전체 블록인 128K를 통째로 다 줍니다. 그러면 128K에서 실제로 100만 쓰고 28만 남아 internal fragmentation이 생기지만, 그것을 감수하고 쓰겠다는 것입니다. 

 

사실 버디시스템의 특징이 메모리 회수할 때 있습니다. 프로세스가 끝나면 메모리를 회수하는데, 이 그림에서 아래에서 4번째를 봅시다. 직전에 64K가 할당되어서 c가 쓰고 있었는데, c가 끝나면, 하늘색 메모리 공간을 반납하고 회색으로 될 것입니다. 64K만큼의 회색 공간이 생겨서 이 공간의 버디(친구)가 비어있는지를 봅니다. 한 조각에서 두 조각으로 분할 되었던 파트너를 말합니다. 그래서 64K 2개가 합쳐져서 128K라는 큰 공간으로 하나로 관리를 하게 되는 특징을 가집니다.

E가 끝나면 128K가 회수가 될 텐데, 버디가 사용중이 아니므로 합쳐서 256K의 빈공간이 되며, 반복적으로 256K 버디를 조사해서 빈공간이므로 합쳐서 더 큰 512K 빈공간으로 만듭니다. 이 상태에서 d가 다 끝나면, d의 버디인 256K를 합쳐서 512K로 합치고 버디가 비어있으므로 1M로 합칩니다.

합치는 이유는 큰 메모리 조각으로 만들어서 작은 메모리 공간들이 흩어져 있게 되는 것을 방지해 테이블에서 메모리 찾는 시간을 줄일려고 하는 것입니다.

 

 

바이너리 트리로 표현한 그림입니다. 버디 시스템이 되면, 순차적으로 찾지 않고, 바이너리 트리를 찾아가는 방법으로 적용 가능해서 빨리 찾을 수 있어서 요즘 사용합니다.