목차
Dynamic Memory Allocation
힙 메모리
Dynamic Memory Allocation
Dynamic memory allocation은 프로그램이 수행되는 중에 메모리가 할당되는 것을 말한다. 런타임 중에 할당되는 메모리의 종류로는 스택과 힙이 있다. 스택은 함수 호출 및 수행할 때 필요한 정보들을 담기 때문에 형식이 정해져 있어서 매우 제한적이다. 반면 힙은 제한이 없기 때문에 쓰기는 편하나 힙을 잘 관리하기가 매우 어렵다.
그렇다면 dynamic memory allocation은 왜 필요할까? 실행 중에는 예측 불가능한 상황이 나타나기 때문이다. 예측 불가능한 상황은 1) 런타임 중 변할 수 있는 메모리 영역(함수 실행, malloc, 등)과 2) 런타임 중 변할 수 있는 데이터 구조 개수이다. 2의 예로는 운영 체제가 PCB를 관리하기 위해서 linked list로 관리하는데, 이 PCB의 개수는 계속 변한다.
힙 메모리
힙 메모리(heap memory)는 메모리 할당(allocation)과 해제(free)를 지원하는 하나의 big chunk memory이다. 사용자는 힙 메모리 할당을 요청했을 시에 연속된 공간을 할당받는다.
Free list
힙 메모리에 어떠한 것도 할당되지 않았을 때 힙 영역에는 하나의 큰 free list만 존재한다. free list는 힙 메모리에서 사용 가능한 공간들을 연결한 리스트이다. 리스트이기 때문에 연속된 free 공간이 시작되는 곳을 prev 포인터가 가리키고 있고, 다음 연속된 free 공간의 시작 주소를 next 포인터가 가리키고 있다. free list는 최대한 연속된 free 영역을 가지기 위해 인접한 영역이 free가 되면 두 영역을 병합(merge)한다.
Fragmentation
힙 메모리를 allocation과 free를 반복하면서 생기는 중요한 문제는
fragmentation이다. Fragmentation은 프로세스의 연속된 free 공간 각각이 너무 작아서 메모리에 hole이 많이 생성된 상태이다. 이는 사용할 수 있는 연속된 free 공간들이 프로세스가 요구하는 (연속된) 크기보다 작기 때문에 어떠한 요구도 만족시킬 수 없고 사용되지 않은 상태로 남아 있는다. 예를 들어서 사용자가 20K 만큼의 힙 메모리 영역을 요청했다고 하자. free 공간을 전부 합치면 힙 메모리의 사이즈가 30K이지만 free list에 연결된 연속된 공간들은 모두 20K보다 작다. 이런 경우 운영 체제는 사용자에게 힙 영역을 할당해줄 수 없다.
Fragmentation이 일어나는 근본적인 이유는 뭘까? 사용자가 요구하는 메모리 사이즈와 가용 공간의 사이즈가 다르기 때문이다. 이를 해결하기 위해서 현대 운영 체제는 다양한 방법들을 지원한다. 그 중 매우 유명한 방법이
paging 기법이다. Paging 기법을 사용하면 메모리를 모두 같은 크기의 블럭(페이지)으로 관리하기 때문에 fragmentation 문제를 거의 해결해준다. 또 다른 방법으로는
memory pool이 있다. 이 방법은 사용자가 메모리를 요청할 시 unit 사이즈로만 요청할 수 있게 하는 것이다. 이 때 unit의 사이즈는 다양하다. 이 경우도 fragmentation이 거의 발생하지 않는다. 그러나 단점은 특정 사이즈의 unit 요청만 계속 들어오면 메모리 불균형 문제가 생길 수 있다.
Heap management : buddy allocator
힙의 fragmentation 문제를 해결하는 여러 방법 중 buddy allocator를 알아보자. Buddy allocator는 힙 메모리 할당시 2의 지수승 크기만큼 할당하는 방법이다. 예를 들어 사용자가 17만큼의 메모리를 요청했다면 16 < 17 < 32 이므로 32만큼의 힙 영역(buddy)을 할당해준다. 이와 같은 방법은 인접한 buddy들이 가용 상태면 이들을 병합 함으로써 쉽게 큰 크기의 메모리 공간을 확보할 수 있다.
Heap management : Free list
사용자가 메모리 요청을 했을 때 free list에 연결된 공간 중 어떠한 공간을 내줘야할까?
- Best-fit : free list를 살펴보면서(O(n)) 가장 fit한 것을 내줌
- First-fit : free list의 가장 첫번째(O(1))를 내줌
- Worst-fit : free list를 살펴보면서(O(n)) 가장 fit하지 않은 것을 내줌
위의 세 가지 방법 중 무엇이 가장 효과적일까? 정답은 모른다이다. Best-fit이라고 항상 좋은 결과를 내주지는 않는다. Best-fit은 시간이 지남에 따라 first-fit과 worst-fit에 비해 작은 크기의 hole이 생성되어 fragmentation 문제가 매우 심각해질 수 있다. 그렇다고 first-fit과 worst-fit이 좋다고는 말할 수 없다.
위 내용은 서울대학교 평생 교육원에서 제공하는 운영체제의 기초 강의를 정리한 것입니다.