목차
1. 고정분할식 메모리 할당방법. Fixed Prtitioning
한정된 크기의 메인메모리 공간을 여러 프로세스들에게 분배해주는 방법.
운영체제 개발자들이 가장 먼저 생각해낸 방법이다.
운영체제는 메인 메모리를 미리 일정한 크기의 조각, 파티션으로 분할해놓고, 사용자 프로세스가 생성되면 메모리 조각들 중 빈 것 하나를 프로세스에게 할당한다.
왼쪽 그림처럼 메인메모리가 있는데, 윗부분에 운영체제가 들어있고, 아래로 사용자 프로세스가 사용할 수 있는 메모리 영역을 일정한 크기로 조각나있다. 이 그림에서는 8MB짜리 메모리조각으로 나뉘어있다.
이 방법의 장점은 메모리 관리가 간단하다.
일정한 크기로 잘랐기 때문에 메모리에 들어갈 수 있는 프로그램 개수 파악이 쉽고, 어떤 프로그램이 몇번째 조각에 들어있다, 몇번째 조각은 비어있다 등의 정보를 파악하고만 있으면 되기 때문에 매우 간단한것이다.
하지만 메모리 이용 효율이 나쁘다는 단점이 있다.
예를 들어 1MB짜리 프로그램을 넣고자 할때 이 프로세스가 8MB짜리 조각을 모두 사용하면 나머지 7MB는 할당받았지만 사용하지 않는 빈공간, 즉 fragment가 생긴다.
파티션 하나에는 하나의 프로세스만 들어갈 수 있기 때문에 이런 내부 fragment는 다른 프로세스가 사용할 수 없다.
이처럼 획일적으로 같은 크기의 파티션만 분할해놓으면 메모리를 이용하는데 따르는 융통성이 떨어지며, 내부 fragment의 평균 크기도 커지는 문제점이 생긴다.
이를 해결하기 위해 나온 방법이 오른쪽 그림과 같이 다양한 크기로 파티션을 분할하는 방법이다.
이것은 unequal sized partition이라고 부른다.
위 예시와 같이 1MB짜리 프로그램을 넣고자 할때, 8MB보다 작은 2MB나 4MB 파티션에 넣으면 낭비되는 공간이 줄어든다. 하지만 내부 fragment를 완전히 없앨수는 없다.
이를 개선한 방법이 다이나믹 파티셔닝이다.
2. 가변 동적 메모리 할당 방법 : dynamic partitioning
예를들어 8MB만큼 운영체제가 사용하고, 56MB만큼 사용자 프로그램이 쓸 수 있는 메모리 공간이 있다고 하자.
이 상태에서 20MB짜리 프로세스 1번이 생성되어서, 프로세스 1번에게 20MB를 할당해준다.
이후 14MB짜리 프로세스 2번이 생성되면 할당을 해주고, 18MB짜리 프로세스 3번이 생성되어서 할당해주면 남은 공간은 4MB가 된다.
이후 프로세스 2가 종료되면, 14MB짜리 빈 공간이 생긴다.
그러고나서 8MB짜리 프로세스 4가 생기면, 6MB, 4MB짜리 빈 공간이 최종적으로 생긴다.
이런식으로 필요한 만큼만 할당하는 방법이 가변 동적 메모리 할당 방법이다.
고정 분할 방식에서 생기는 내부 fragment 문제를 해결할 수 있다.
하지만 대신 외부 fragment 문제가 생긴다.
위 예시에서 보면 6MB, 4MB 빈 공간은 크기가 비교적 작으므로 프로세스가 생겼을때 프로세스가 못들어갈 가능성이 높다.
이렇게 작은 빈 메모리 공간이 생겼을때, 빈 공간을 한쪽으로 몰아서 연속된 공간으로 만드는 콤팩션 방법을 사용할 수 있다.
하지만 이 방법을 위해서는 메모리를 읽고, relocation을 위해 쓰는 과정을 반복해야하기 때문에 결국은 시간이 걸리는 동작이므로 좋은 방법이 아니다.
이러한 대가를 치뤄야 하지만 고정분할 방법보다는 메모리 활용도를 높일 수 있다.
가변 동적 할당 방법에서 메모리 관리를 하기 위해서는 운영체제가 메모리 이용 상황을 파악하고 있어야한다. 위 그림처럼 메모리가 몇 바이트부터 얼마만큼 비어있다는 정보를 테이블이나 링크드리스트방법으로 저장해야한다.
위 테이블을 보면, 100byte에서부터 시작해서 2048bytes만큼은 사용하지 않는 빈공간이다.
이와 같은 정보를 바탕으로 새 메모리 요청이 들어오면 메모리를 할당하는 것이다.
이때 할당하는 방법은 4가지가 있다.
1. first-fit 알고리즘
처음에 맞는 공간을 찾는 방법이다.
7000bytes짜리 새 프로세스가 생겼다고 가정하자.
그러면 빈 메모리 리스트의 위에서부터 7000bytes만큼의 프로세스가 들어갈 수 있는 공간을 찾고, 가장 먼저 찾은 공간을 사용하는것이다.
2. best-fit 알고리즘
빈 메모리 리스트를 처음부터 끝까지 일단 조사 후, 지금 필요한 프로세스의 크기와 가장 비슷한 크기의 영역을 찾는 방법이다.
위 리스트에서는 8100byte짜리 크기가 가장 비슷하므로 이 영역이 사용될것이다.
first-fit 알고리즘은 8100byte짜리 공간을 찾은 이후로는 조사하지 않지만,
best-fit 알고리즘은 전부 조사하기 때문에 공간 낭비는 적어지지만 시간이 더 걸린다.
3. wrost-fit 알고리즘
심화임
4. next-fit 알고리즘
심화임
3. Buddy System
내부 fragment를 허용하는 가변 동적 메모리 할당 방법이다.
즉 고정 분할 방법과 가변 분할 방법을 합한것이다.
요즘은 메인 메모리가 값이 싸고 용량이 크기 때문에 버디시스템을 효율적으로 사용할 수 있다.
외부 fragment를 프로세스에게 할당하여 내부 fragment로 만드는 방법이다.
작은 빈 공간들에는 프로세스가 들어갈 확률이 적으므로 빈공간 리스트에서 자리만 차지하고 목록 조사에 시간만 더 걸리므로, 이 공간을 지금 할당되어있는 다른 프로세스 메모리 공간에 합체시키는것이다.
현대는 메인 메모리 공간에 여유가 생겼기 때문에, 이처럼 운영체제 동작을 빨리할 수 있게 하는 것이 더 중요해서 조금의 메모리 낭비를 감수하는것이다.
버디 시스템의 메모리 할당 방법은 다음과 같다.
할당할 메모리 크기를 s라고 하고, 현재 비어있는 메모리 크기를 2의 u제곱승이라고 하자.
버디 시스템에서는 메모리를 2의 제곱단위로 할당한다.
먼저 s가 현재 비어있는 메모리 크기의 반절인 2의 u-1제곱승보다 큰지 비교한다.
만약 그렇다면 2의 u제곱 byte라는 공간을 전부 할당한다. 안에 내부 fragment가 생기더라도 감수하는것이다.
만약 그렇지 않다면 빈 메모리 전체 공간을 2의 u-1제곱승 크기의 조각 두개로 나눈다.
그런다음 조각 하나에 대해 다시 이 조각의 반절크기, 즉 2의 u-2제곱승 크기보다 큰지 비교하고, 위와 같은 과정을 반복한다.
또한 프로세스가 종료되어서 메모리가 회수되고 빈 메모리 조각이 생겼을 때, 옆에 빈 메모리 공간이 있으면 이를 합쳐서 하나로 관리하는 것이 버디시스템의 특징이다.
될수있으면 큰 메모리 조각을 만들어서 작은 메모리 조각이 여러군데 흩어지지 않도록 하는것이다.
작은 메모리 조각이 여러군데 흩어져있으면 외부 fragment도 발생하지만, 빈 메모리 리스트가 길어져서 메모리를 찾는 시간도 오래걸린다.
버디시스템을 사용하면 빈 메모리를 찾을때 리스트를 순차적으로 보면서 sequential하게 찾지 않고 binary tree를 찾아나가는 방식으로 찾기 때문에 좀 더 빨리 찾을 수 있다.
