WEEK06 - 탐험준비 Malloc Lab
이번 주차는 동적 메모리를 할당하는 Malloc과 free를 구현하면서 가상메모리와 동적할당에 관해 공부했다.
간단하게 정리하면, 각 프로세스마다 독립된 가상메모리를 갖는데 이 안에는 실행할 code가 들어있는 .text 영역과 초기화된 전연변수가 들어있는 .data, 초기화되지 않은 전역변수가 들어있는 .bss, 함수의 매개변수와 지역변수 등을 저장하는 user stack, 그리고 런타임에 생성되는 변수나 구조체 등이 저장되는 heap 영역 등으로 구성된다. 이 영역들 중에서 heap영역을 확장하고 필요한 만큼 메모리를 할당해주는 함수가 바로 malloc 이다.
malloc은 힙의 영역 상태와 인자로 들어온 사이즈에 따라 필요하다면 시스템콜 함수를 호출하여 힙을 확장하고 메모리를 할당하여 해당 메모리의 첫번째 포인터를 void *형으로 반환해준다. 프로그래머는 malloc을 통해 메모리를 할당받아 사용하고, free를 호출하여 메모리를 반납함으로써 불필요한 메모리 낭비를 피할 수 있으며, 특히 프로그램을 짤 때는 크기를 알 수 없으나 런타임에야 알 수 있는 경우 (예를 들면 배열 길이) malloc을 사용함으로써 쉽게 해결할 수 있다.
주의할 점은, (1) 메모리 누수를 막기 위해 할당받은 메모리 사용이 완료된 경우 반드시 free로 반납해주어야하며, (2) 반납한 메모리영역을 저장하고 있는 변수는 잘못된 접근을 방지하기 위해 NULL값으로 변경해주어야한다.
malloc의 구현방식에는 여러가지가 있는데, 이들은 가용리스트를 관리하는 방식에 따라 나뉜다. 여기서 가용리스트란, 시스템콜을 통해 확장한 힙 영역 중 할당하지 않은 영역을 의미한다. 메모리 할당을 관리할 때에는 두가지 인자를 중요하게 여기는데, 한가지는 Throughput(할당완료까지 걸리는 시간이 짧아야함)이고 다른 한가지는 utilization(메모리 활용도: 내부단편화와 외부단편화가 적어야함)이다. 가용리스트를 관리하는 방식에 따라 이 두가지 인자가 달라지게 된다.
이번 구현에서 고려한 방식들은 아래와 같다.
implicit free list : 묵시적 가용 리스트. 메모리 블럭의 header와 footer에 해당 블럭의 사이즈와 할당여부를 표현하는 bit를 넣고, 모든 블럭을 탐색하면서 할당가능한 영역을 찾는 방식. 가용리스트를 따로 만들지 않고 전체를 탐색하면서 확인하기 때문에 묵시적 리스트임.
explicit free list : 명시적 가용 리스트. 가용한 블럭들에 대해서 predeccesor와 succesor를 가리키는 포인터를 저장하여 연결리스트로 만들고, 메모리 할당 요청시 이 연결리스트를 탐색하여 가능한 블럭을 찾는 방식.
segregated free list : 가용 블럭들의 사이즈에 따라 클래스를 나누고 각 클래스마다 오름차순으로 정렬된 연결리스트로 관리하여, 메모리 할당 요청시 필요한 사이즈 클래스부터 큰 사이즈 클래스 순으로 탐색함으로써 first fit으로 best fit이 가능하도록 구현한 방식.
buddy system : 외부단편화를 해결하기 위한 방식으로, 모든 블럭은 2의 k승의 사이즈로 할당함. 따라서 사이즈 클래스 또한 2의 k승인 사이즈로 나누어짐.
회고
이번 주차는 시간이 부족하여 모든 과제를 완료하지는 못하였다. 가장 간단한 implicit은 교재를 참고하고, 이후에 explicit과 segregated는 내용을 이해하고 코드는 직접 고민해서 작성하였는데, 이 과정에서 디버깅이 꽤 오래 걸리기도 하였고, 내용을 완전히 파악하지 않은 상태에서 구현하였는데 점수가 생각보다 낮아서 보니 코드를 바꿔야 하는 부분도 생겨서 시간이 더 걸렸다. 그래서 결국 buddy system까지는 구현해내지 못했다.
buddy system을 구현하지 못한 점은 아쉬웠지만, segregated 방식을 스스로 이해하고 구현했다는 점에서 뿌듯함을 느꼈다. 특히 throughput이 잘 나오지 않아 연산을 줄이기 위해 비트연산을 사용하는 방식을 생각해내고 구현했는데 눈에 띌 정도로 결과가 나아져서 정말 기분이 좋았다.
