간단한 메모리 관리자

문제 개요

지금껏 여러 언어들을 토대로 프로그래밍을 해오면서, 메모리 관리 메커니즘에 의하여 메모리 중 사용 가능한 부분, 즉 가용 공간에서 요청된 크기만큼을 사용할 수 있도록 작업을 수행한 뒤 그 시작 주소를 반환값으로 돌려주는 함수 malloc을 자주 접해왔다. 이 같은 기능과 유사하게, 실제 운영체제에서 이루어지는 메모리 관리 메커니즘의 축소된 버전이라고 볼 수 있는 보다 간단한 메모리 관리자를 프로그램으로 구현해보았다.
두 가지 방법으로 메모리 관리자를 구현한 후 각 방법으로 구현했을 시의 결과 및 장단점을 비교해볼 것이다. 두 가지 방법은 다음과 같다.

(1) first-fit : 메모리 할당 시 헤더에 해당하는 가용 공간 메모리 청크에서부터 할당하는 방법

(2) best-fit: 메모리 할당 시 할당하고자 하는 메모리의 크기와 가장 비슷한 가용 공간 메모리 청크에 할당하는 방법

위의 그림에서 볼 수 있듯이 메모리를 할당 및 반환 할 때, 두 방법 모두 공통적으로 할당 시에는 할당된 메모리 상에서의 시작 주소를 반환해야 하며 반환 시에는 가용 공간을 의미하는 연결리스트 상에 반환하는 주소 및 크기를 나타내는 새로운 청크가 삽입되어야 한다. 메모리의 할당 순서와 반환 순서는 동일하지 않다. 만약 메모리 상에서 서로 연결된 공간을 갖지만 반환 순서 상의 이유로 분리된 청크로 가용 공간 상에 연결되어있다면, 이론상으로는 할당이 가능한 메모리임에도 불구하고 할당되지 않을 수 있다. 이러한 문제를 해결하고자 반환 시 메모리 상에서 연결된 청크가 존재할 경우 이러한 청크들끼리 합병해주는 작업 또한 알고리즘으로 구현해야 한다. 심층적으로, 각 방법의 장단점을 비교하기 위하여 할당 성공률 또한 기록해두었다가 화면에 결과와 함께 출력하여 비교가 용이하도록 알고리즘을 설계하면 좋을 것이다.

위 문제에 대해 Visual Studio에서 C언어를 사용하여 구현하며, 자료구조의 연결리스트 개념을 이용하여 본 문제를 해결해본다.

자료구조 및 알고리즘 설계

연결리스트를 구현하기 위하여 청크 구조체를 다음과 같이 정의한다.

define MAX 100
typedef struct chunk {
	int start;
    int size;
    struct chunk* link;
} Chunk
Chunk* head

청크의 구조에서 start는 가용 공간에서의 시작 위치를 의미하고 size는 start 위치에서부터 가용 가능한 메모리 크기를 의미한다. link는 연결리스트를 사용하여 다음 청크를 가리키는 포인터를 의미한다. head는 가용 공간을 의미하는 연결리스트의 헤더 포인터를 의미한다.

아래의 내용은 알고리즘 설계와 관련된 내용이다.

main에서 초기에 선언한 가용 공간 연결리스트 available은 위의 그림과 같다. start는 0을 가리키며 size또한 앞서 자료구조 설계에서 언급했듯 define MAX 100을 선언하였기 때문에 이에 맞게 100으로 지정되어있다. 이 상황에서 메모리가 할당될 경우, 할당했던 메모리가 반환되기 전까지는 새로운 청크를 만드는 것이 아닌 위의 청크에서 start와 size의 정보를 수정하게 된다. 이에 대한 예시는 아래의 그림과 같다.

앞서 언급했듯, 새로운 청크가 생기지 않고 기존에 있던 청크에서 start와 size 내용만 변경되었다. 변경된 청크에 대해서는 연한 파란색으로 나타내었다.

위의 그림과 같이 기존에 할당됐던 메모리 중 임의의 메모리가 다시 반환되기 전까지는 계속 초기에 선언했던 청크의 내용만 변경된다. 이제, 처음으로 메모리를 반환해보면 available 연결리스트는 다음 그림과 같이 구성된다.

위의 그림에서 알 수 있듯이, 이제는 새로운 청크가 생성되었고 기존에 있던 청크의 link가 새로 생긴 청크를 가리키고 있다. 초기에 a를 메모리 상에서 0의 위치에 10만큼 할당하였기 때문에, available 연결리스트에 새로 생긴 청크를 보면 a가 가지고 있던 메모리에서의 정보를 그대로 가지고 있는 것을 확인할 수 있다. 여기까지는 first-fit과 best-fit 모두 동일하게 진행된다. 다음의 상황을 살펴보면, 두 할당 방법에서 보여지는 차이를 알 수 있다.

위의 그림은 first-fit 방법에 대한 그림이다. 그림의 두 번째 줄에서 10만큼의 크기를 가지는 메모리 c를 할당하고자 할 때, available 헤더가 가리키는 청크에서 메모리가 할당되었음을 볼 수 있다. 이름 그대로, 가장 첫 번째에 있는 청크에 메모리를 할당하는 것을 우선으로 삼는다는 것을 알 수 있다. 이제, best-fit 방법은 어떻게 진행하는지 살펴보도록 하겠다.

앞선 first-fit과 달리, 그림의 두 번째 줄을 보면 available의 헤더가 가리키는 청크가 아닌, 10이라는 가용공간을 가졌던 첫 번째 줄에서의 두 번째 청크, 즉 시작 위치 0이였던 청크에 메모리가 할당되어 available 연결리스트 상에서는 해당 청크가 없어지고 시작 위치 30인 청크가 시작 위치 70인 청크와 연결되었음을 확인할 수 있다. 이처럼, best-fit 방법에서는 할당하고자 하는 메모리 크기와 가장 유사한 크기를 갖는 가용 공간 청크에 메모리를 할당하는 것을 우선으로 둔다는 것을 알 수 있다. 두 방법에 대한 큰 차이를 시각적으로 알게 되었으니, 다음은 두 방법에서 모두 할당하지 못하는 경우에 대해 알아보도록 한다..

위 그림의 상황을 설명해보면, available 연결리스트 상의 그 어떤 청크도 d에서 할당하고자 하는 메모리 크기인 40을 충족시키지 못하기 때문에 결과적으로 d에는 할당 실패를 의미하는 -1이 반환되었고, available 연결리스트도 d 할당 전과 동일함을 알 수 있다. 마지막으로 available 연결리스트 상의 메모리 공간 합병 과정에 대해 살펴보도록 하겠다.

위 그림의 두 번째 줄에서 시작위치 10에 20만큼의 크기를 차지하고 있던 b가 동적 해제되었다. 전형적인 알고리즘상으로는 available 연결리스트의 가장 마지막 청크의 link에 연결되어 새로운 청크로 연결되어야 한다. 하지만 이론적으로 접근할 때, b를 할당 해제하게 될 경우 시작위치 0부터 크기 40만큼이 가용 공간이기 때문에 이를 알고리즘 상으로도 풀어낼 수 있어야 한다. 이를 적용한 것이 바로 위의 그림과 같은 경우이다. 첫 번째 줄에서 새로운 청크를 추가하여 4개의 청크로 나타내지 않고, 두 번째 줄 처럼 가용 공간 청크를 합병하여 총 2개의 청크로 나타내었다.

이제 본격적으로 연결리스트를 활용하여 두 가지 방법에 대한 메모리 관리 과정에 대해 서술해볼텐데, 우선 추후에 두 방법의 장단점을 비교해보기 위하여 할당 성공률을 매 할당마다 available 연결리스트와 함께 출력해야 한다. 이를 위해 할당 시도 횟수와 실패 횟수를 변수에 저장해두었다가 이를 출력한다. 메모리 할당 시 first-fit에서는 헤더 청크의 사이즈가 할당을 요청하는 메모리의 사이즈보다 작지 않은 이상 헤더에 할당한다. 그렇지 않을 경우엔, 헤더의 link를 따라 이동하며 가장 먼저 사이즈 조건을 충족하는 청크에 메모리를 할당한다. best-fit에서는 메모리 할당 전, available 연결리스트를 헤더부터 마지막 청크까지 이동하면서 할당하고자하는 메모리 크기와 가장 유사한 크기를 갖는 청크를 찾아 기록해둔 후, 할당 시 해당 청크로 이동하여 할당하게 된다. 두 방법에서 모두 동일한 메모리 반환 시에는 요청한 메모리를 반환할 때 만약 available 연결리스트의 청크들끼리 합병될 수 있는 상황이라면 합병이 진행될 수 있도록 알고리즘을 작성한다.

아래의 알고리즘은 first-fit 방법에서의 메모리 할당을 위한 과정을 가상코드로 기술한 알고리즘이다.

1. Algorithm myalloc(available, request_size)
2. Input: 가용 메모리 연결리스트(available), 할당하고자하는 메모리 크기(request_size)
3. Output: 할당된 메모리의 시작 위치
4. total <- total + 1
5. temp <- 0
6. before, current <- head
7. while(1) do {
8.	if (current.size >= request_size) {
9.		temp <- current.start
10.		current.start <- current.start + request_size
11.		current.size <- current.size - request_size
12.		if (current.size = request_size) {
13.			before.link <- current.link
14.			current <- current.link }
15.		if (head.start = 100) {
16.			head <- head.link }
17.	else {
18.		before <- current
19.		current <- current.link
20.		if (current = NULL) {
21.			fail <- fail + 1
22.			return -1
23.			break} } }
24. return temp
25. end

알고리즘에서 입력은 가용 메모리를 나타내는 연결리스트 available를 포인터로 받은 것과 할당하고자하는 메모리 크기인 request_size이다. 출력은 할당된 메모리의 시작 위치이다. 4번 줄에서 전역 변수로 선언해준 total의 값을 1 증가시킨다. 5번 줄에서는 시작 위치를 저장해두기 위한 변수 temp를 0으로 초기화해준다. 6번 줄에서 후에 available 연결리스트를 구현하기 위해 선언한 before, current 청크에 헤더 값을 넣어준다. 8~14번 줄은 current 청크가 가리키는 노드의 사이즈가 할당을 요청하는 메모리 사이즈보다 크거나 같을 경우, 즉 할당 가능할 경우 실행되는 조건문이다. 이 경우, 먼저 temp변수에 가용 공간 상에서의 시작 위치를 저장해두고, 해당 청크의 시작 위치를 할당한 메모리 크기 만큼 더해 변경한다. 사이즈의 경우 할당한 사이즈만큼 기존의 청크 사이즈에서 빼준다. 만약 이 과정에서 해당 청크의 사이즈가 0이 된다면 available 연결리스트 상에 청크가 나타날 필요가 없기 때문에, 이 때 앞서 선언해둔 before와 current를 이용하여 해당 청크를 연결리스트 상에서 제거한다. 15~16번 줄은 만약 헤더 청크에서 사이즈가 0이 될 경우 헤더를 현재 헤더의 link로 연결되어 있는 청크로 이동시키는 작업을 코드로 보여주고 있다. 17~23번 줄은 if 조건을 만족 못할 경우, 즉 할당하고자 하는 메모리 사이즈보다 청크의 사이즈가 작을 때 실행되는 조건문이다. 이 경우 link를 이용하여 현재의 before와 current가 가리키는 청크를 각각 다음 청크로 바꿔준다. 이렇게 available 연결리스트의 끝까지 진행했음에도 메모리를 할당할 수 있는 청크가 존재하지 않을 땐, 실패 횟수를 의미하는 전역 변수 fail의 값을 1만큼 증가시켜준 후, 시작 위치에는 -1을 반환할 수 있도록 하여 while문을 빠져나온다. while문이 끝나면 시작 위치인 temp값을 반환한다.

아래의 알고리즘은 best-fit 방법에서의 메모리 할당을 위한 과정을 가상코드로 기술한 알고리즘이다.

1. Algorithm myalloc(available, request_size)
2. Input: 가용 메모리 연결리스트(available), 할당하고자하는 메모리 크기(request_size)
3. Output: 할당된 메모리의 시작 위치
4. total <- total + 1
5. temp <- 0
6. before, current <- head
7. index, best <- 0
8. min <- MAX
9. while (current != NULL) do {
10.	if (((current.size - request_size) < min) && (current.size >= request_size)) {
11.		temp <- current.start
12.		min <- current.size - request_size
13.		best <- index
14.		current <- current.link }
15.	else {
16.		if (current.link = NULL && before.size < request_size) {
17.			fail <- fail + 1
18.			return -1
19.			break }
20.		current <- current.link }
21.	index <- index + 1 }
22. before, current <- head
23. for i <- 0 to i < best do {
24.	before <- current
25.	current <- current.link }
26. if (min = 0) {
27.	before.link <- current.link
28.	current <- current.link
29.	if (head.size = request_size) {
30.		head <- head.link } }
31. else {
32.	temp <- current.start
33.	current.start <- current.start + request_size
34.	current.size <- current.size - request_size }
35. return temp
36. end

알고리즘에서 6번 줄까지는 first-fit과 동일하므로 설명은 생략하도록 하겠다. 7~8번 줄에서는 메모리를 할당하기에 최적인 청크를 찾기 위해 필요한 정보들을 기록해둘 index와 best 변수를 선언하고 min 변수에는 define으로 선언한 MAX 값을 넣어준다. 10~14번 줄은 current에 해당하는 청크의 사이즈가 할당 요청 메모리 사이즈보다 크거나 같으며, current청크의 사이즈와 할당 요청 메모리 사이즈의 차가 현재의 min 값보다 작을 때 새로 최적의 청크 정보를 갱신하는 내용에 대한 조건문이다. 그리하여 temp와 min, best에 대한 정보를 갱신하고 current를 다음 청크로 이동시킨다. 15~20번 줄은 앞선 if 조건에 해당하지 않을 때, 만약 available 연결리스트의 그 어떤 청크에도 메모리를 할당할 수 없다면, first-fit에서와 마찬가지로 fail 변수의 값을 1 증가시킨 후 시작 위치 반환 값으로는 -1을 반환하게 하며 그 즉시 while문을 빠져나온다. 다음 청크가 존재할 경우에는 current를 다음 청크로 이동시켜주면 된다. 이렇게 하나의 청크를 지나칠 때마다 index 값을 1씩 증가시켜준다. 이것을 나타내는 줄이 21번 줄이다. 다음은, 앞서 9~21번 줄에서 찾은 최적의 청크 정보를 토대로 해당 청크까지 before와 current를 사용하여 이동한 후 메모리 할당 작업을 실행하는 것에 대한 알고리즘이다. 22번 줄에서 다시 before와 current를 available 연결리스트의 헤더 값으로 지정해준다. 23~25번 줄은 앞선 while문에서 구했던 최적의 청크까지 찾아가기 위해 index를 저장해둔 best만큼 for 반복문을 돌려 이동한다. 이때 만약 min의 값이 0일 경우 해당 청크는 available 연결리스트에서 나타날 필요가 없기 때문에 이를 제거하는 과정을 보여주는 것이 26~30번 줄이다. 만약, 이 때 min값이 0이면서 가용 공간상에서 할당을 받는 청크가 헤더에 해당할 경우, available 연결리스트의 헤더를 변경해주는 작업을 해주어야 하므로 이를 이중 조건문을 이용하여 처리한다. 31~34번 줄은 min 값이 0이 아닐 경우, 단순히 해당 청크의 시작 위치를 temp에 넘겨주고, 시작 위치와 사이즈를 변경해주는 작업을 수행하는 것을 보여준다. 34번 줄에서 temp를 반환하게 되고, 이로써 위 알고리즘은 종료된다.

아래의 알고리즘은 best-fit, first-fit 두 방법에서의 메모리 반환을 위한 과정을 가상코드로 기술한 알고리즘이다.

1. Algorithm myfree(available, start_address, return_size)
2. Input: 가용 메모리 연결리스트(available), 메모리상의 시작 주소(start_address), 반환하는 메모리 크기(return_size)
3. Output: 메모리 해제 후 재정렬된 가용 메모리 연결리스트
4. newchunk <- memory_alloc(sizeof(Chunk))
5. newchunk.start <- start_address
6. newchunk.size <- return_size
7. temp, temp2 <- available
8. next, next2 <- temp.link
9. case_num, case_num2 <- 0
10. if (next = NULL) {
11.	case_num, case_num2 <- 1 }
12. switch (case_num) {
13. case 0 :
14.	while (1) do {
15.		if (next = NULL || (next.start > newchunk.start)) {
16.			newchunk.link <- temp.link
17.			temp.link <- newchunk
18.			break }
19.		else {
20.			temp <- next
21.			next <- next.link } } break
22. case 1 :
23.	temp.link <- newchunk
24.	newchunk.link <- NULL
25.	break
26. switch (case_num2)
27. case 0 :
28.	while (next2 != NULL) do {
29.		if (temp2.start + temp2.size = next2.start) {
30.			temp2.link <- next2.link
31.			temp2.size <- temp2.size + next2.size
32.			next2 <- next2.link }
33.		else {
34.			temp2 <- next2
35.			next2 <- next2.link } } break
36. case 1 : break
37. end

알고리즘에서 입력은 가용 메모리를 나타내는 연결리스트 available를 포인터로 받은 것과 메모리 상의 시작 주소인 start_address, 반환하는 메모리 크기인 return_size이다. 출력은 메모리 해제 후 재정렬된 가용 메모리 연결리스트 available이다. 4~6번 줄에서는 반환하고자 하는 메모리를 연결리스트 상에서 청크로 구현하기 위한 작업들이다. newchunk를 할당해주고 이것의 start와 size 정보에 Input으로 입력받은 정보를 넘겨준다. 후에 자세히 서술하겠지만, 이 알고리즘에서는 총 두 개의 switch문이 사용되는 이 작업을 위하여 7~9번 줄에서 각각 temp, next, case_num 변수를 2개씩 선언해준다. 10~11번 줄에서는 만약 next청크가 NULL 일 경우엔 switch문에 들어갈 case_num변수를 1로 지정해주는 작업을 수행한다. 12~25번 줄은 첫 번째 switch문에 관한 내용인데, 이 switch문은 시작 위치를 기준으로 청크들을 오름차순으로 정렬해주는 작업을 수행한다. case 0일 경우, 가장 초기에 선언했던 available 연결리스트의 헤더를 제외하고 이후에 반환되는 메모리들에 대하여 헤더 뒤에서 오름차순으로 청크들끼리 연결될 수 있도록 if문과 else문을 이용하여 처리한다. next 청크가 없는 case 1에서는 단순히 현재의 헤더 청크의 link에 새로 반환되는 newchunk를 이어주면 된다. 26~36번 줄은 두 번째 switch 문으로, 합병 과정에 대한 작업을 수행하게 된다. 앞서 첫 번째 switch문을 이용하여 오름차순으로 정렬하였다면, 이를 가지고 헤더 청크부터 순차적으로 방문한다. case 0에서 만약 이론상 청크들끼리 합병될 수 있는 조건이라면, 청크의 시작 위치와 사이즈를 바꿔주고 합병 마무리된 청크를 연결리스트 상에서 삭제하는 작업을 수행하게 된다. case 1의 경우 합병할 메모리가 존재하지 않기 때문에 그대로 switch문을 빠져나올 수 있도록 break를 걸어주면 된다.

프로그램 구현 및 실행 결과

프로그램 구현 및 실행 결과는 다음과 같다. 앞서 문제 개요, 자료 구조 및 알고리즘 설계에서 선보였던 예시와는 다른 3개의 예문을 가지고 프로그램을 실행했다. 3가지 시나리오에 대하여 해당 내용과 콘솔창 출력 결과, 이를 도식화한 그림들을 차례대로 첨부하였다.

1) 첫 번째 시나리오

(1) 할당 및 반환 내용

(2) 콘솔창 출력 결과(왼쪽: first-fit / 오른쪽: best-fit)

(3) 도식화 (위: first-fit / 아래: best-fit)

2) 두 번째 시나리오

(1) 할당 및 반환 내용

(2) 콘솔창 출력 결과(왼쪽: first-fit / 오른쪽: best-fit)

(3) 도식화 (위: first-fit / 아래: best-fit)

3) 세 번째 시나리오

(1) 할당 및 반환 내용

(2) 콘솔창 출력 결과(왼쪽: first-fit / 오른쪽: best-fit)

(3) 도식화 (위: first-fit / 아래: best-fit)

논의 사항

메모리 관리 메커니즘의 축소된 버전인 간단한 메모리 관리자에 대하여 first-fit과 best-fit 두 가지 방법으로 알고리즘을 구상해보았다. 두 방법 모두 연결리스트를 이용하여 구현해 낼 수 있었다. first-fit 방법은 가용 공간을 검색해서 사이즈가 할당하고자하는 메모리의 사이즈보다 크거나 갖다는 가정 하에 첫 번째로 찾아낸 청크에 할당하는 방식이다. 할당할 공간을 찾으면 알고리즘이 끝나기 때문에 비교적 구현이 간단하고 수행시간 또한 빠르다는 장점을 가지고 있다. 하지만 계속 앞쪽의 가용 공간만 사용하게 된다는 단점이 있어 할당 성공률을 가지고 비교해볼 때, best-fit 방법보다 성능이 떨어진다고 생각하게 될 수도 있다. best-fit 방법은 가용 공간을 검색해서 할당하고자 하는 메모리의 사이즈와 가장 유사한 사이즈를 갖는 메모리 공간을 선택하여 해당 청크에 할당하는 방식이다. 할당 성공률 측면에서보면 best-fit이 매우 효율적이라는 장점이 있다. 하지만, 할당할 가용 공간을 선택하기 위해 처음부터 끝까지 최적인 곳을 찾아 검색을 해야 하므로 비교를 하는데에 수행 시간이 오래 소요된다는 치명적인 단점이 있다. 단순히 할당 성공률만 놓고 비교했을 땐 best-fit이 더 좋은 방법처럼 여겨지지만, 수행시간에 조금 더 주목하여 할당 시 발생하는 약간의 낭비를 무시할 경우에는 검색 시간이 적은 first-fit이 더 효율이 높다고 여겨질 것이다. 이는 단지 무엇에 더 초점을 두는가에 따라 다르게 받아들일 수 있는 부분인 것 같다.

코드

자세한 코드는 Github에서 확인할 수 있다.