[시스템프로그래밍] 메모리2

직접리스트

직접 가용 리스트 방식은 가용 블록들의 리스트만 관리하며, 모든 블록을 관리하지는 않는 방식이다.

이 방식을 사용하면, 다음 가용 블럭을 단순히 사이즈로는 접근이 불가하므로, 포인터를 저장한다.

왼쪽은 할당된 블럭의 구조이다. 이 방식은 이전의 간접리스트와 같다.

오른쪽은 가용블록이다. 이전에 데이터를 넣어두는 공간으로 썼던 payload를 이전, 다음 가용블럭을 나타내는데 사용한다.

논리적으로 위 a,b,c 블럭들은 모두 순서대로 연결되어있다.

하지만 실제로 연결되어있는 링크는 메모리 블럭의 순서와 무관하게 정렬되어있다.(C가 B보다 앞에있는게 가능하다.)

위 그림은 직접할당방식에서 malloc을 통해서 가용블럭이 할당되었을때의 결과이다.

이 경우, malloc 후 남은 공간을 쪼개 새로운 가용블록으로 만들었으므로, 이전 가용블럭과 다음 가용블럭의 포인터들을 갱신한다.

따라서 업데이트 해야 할 데이터 수는 총 4개이다.

그렇다면, 특정 블럭이 가용 블럭이 되었을 때 리스트에 이 블럭을 어떻게 추가해야할까

위와 같이 LIFO와 주소정렬정책이 있다.

LIFO는 빠르게 삽입이 가능하지만, 단편화의 위험이 있고, 주소정렬정책은 리스트를 탐색해야하지만, 이 방식은 단편화 성능이 우수하다.

LIFO 방식은 리스트의 가장 앞에 free 블럭을 넣는다.

따라서 리스트의 가장 앞인 root가 현재 free 된 블럭의 맨 앞 주소를 가지도록 하고, 생성된 블럭의 다음주소를 원래 맨 앞에 있던 블럭의 주소로 설정한다.

또한 원래 맨 앞에 있던 블럭의 이전 블럭을 나타내는 영역은 이번에 새로 가용블럭이 된 블럭의 주소를 가지로독 한다.

이번에 free된 블럭의 앞 블럭은 없으므로, 새 블럭의 앞 블럭을 나타내는 부분은 null로 둔다.

이 경우는 free 한 지점의 앞 블럭도 가용블럭이라 병합되었을 경우이다.

병합이 되었을 경우, 이 블럭도 새로운 블럭으로 취급해 맨 앞으로 옮긴다.

또한 원래 병합되기 전 블럭의 앞, 뒤를 연결했던 노드는 서로 연결하여 잇는다.

이 방식은 free 한 지점의 뒷 블럭도 가용블럭이라 병합되었을 경우이다.

이 경우에도 마찬가지로 새로운 블럭으로 취급해 맨 앞으로 옮긴 후, 병합되기 전 블럭의 앞, 뒤를 연결했던 노드는 서로 이어준다.

이번에는 free한 블록의 앞, 뒤 모두 가용블록일 경우이다.

여기서도 마찬가지로, 합병한 후의 블럭을 새로운 블록으로 취급해서 맨 앞으로 옮긴 후, 원래 앞, 뒤 블럭을 연결했던 블럭들을 서로 잇는다.

직접리스트의 경우, 가용블럭만 관리하기 때문에, 할당을 위해서 모든 블럭들을 탐색할 필요가 없다. 특히 메모리가 거의 차있는 경우에 매우 빠른 할당속도를 가진다.

다만 할당과 반환 과정이 리스트에서 제거, 추가 하는 과정이 필요하기 때문에 약간 더 복잡하다. 또한 링크포인터(다음, 이전 가용블럭) 저장을 위해 추가적인 공간이 필요하다는 점도 다르다.

구분가용리스트는 크기 클래스마다 각각 별도의 가용 리스트를 유지하는 방식이다.

이와 같이 가용블럭들을 크기별로 클래스로 관리하여 필요한 크기의 블럭에 접근을 상수시간에 가능하도록 한다.

보통 작은 크기들은 크기마다 클래스가 존재하지만, 크기가 큰 경우 2의 제곱마다 클래스가 존재한다.

만약 크기 n인 블록을 할당해야한다면, 일단 n이 포함된 클래스를 탐색한다. 만약 해당 클래스가 비어있지 않다면 가장 첫 블럭을 할당한다.

하지만, 해당 클래스가 비어있다면, 운영체제한테 sbrk()를 요청하여 힙의 크기를 늘린다. 이후, 늘어난 free 블럭을 포함한 새로운 클래스를 생성하고, (n에 맞는) 이 클래스의 첫 블록을 할당한다.

블록이 free를 통해서 다시 가용블럭이 되면, 크기에 맞는 클래스의 가용리스트에 바로 추가되거나, 앞 뒤 블럭과 연결된 후 가용리스트에 추가된다.

이러한 방식은 매우 빠른 처리시간과 최적할당시와 유사한 우수한 메모리 이용율을 가질 수 있다. ( 만약 클래스가 모든 크기별로 있다면 메모리 이용율은 bestfit 방식과 동일하다.)

드디어 끝!

출처

충남대 김형신교수님 시스템프로그래밍 강의자료

ESLAB | Home

eslab.cnu.ac.kr