Malloc 할당 스키마

Question

예, 컴퓨터 시스템 과정을 수강하고 있습니다. malloc을 구현하기위한 다양한 할당 스키마에 대해 몇 가지 질문이있었습니다. 명시 적 목록의 경우 LIFO 형 스택을 사용하여 malloc을 구현하면 이전에 해제 된 메모리에 대한 포인터를 갖는 목적은 무엇입니까? 왜 이중 연결 목록이 필요한지? 단독으로 연결된 목록도 제대로 작동하지 않습니까?

Malloc lecture. 이 링크를 온라인에서 찾았 으면 슬라이드 7에서 내가 무슨 말을하는지 확인할 수 있습니다.

분리 목록 할당 체계를 살펴볼 때 이러한 목록은 단방향입니까? 또한, 합체 메커니즘은 정확히 무엇입니까? 예를 들어, 4 단어가 해제 된 경우, 분리 된 연결된 목록에 다시 삽입하기 전에 주위의 여유 공간이있을 때 먼저 시도하고 결합합니까? 또는 각각의 분리 링크 된 목록의 '4 단어'섹션에 4 단어 블록을 삽입하면됩니까?

감사합니다.

Answer 1

해제 된 블록에는 항상 두 개의 포인터가있는 공간이 있으므로 중복 된 목록을 만들면 안됩니까? 병합 코드를 단순화하여 목록을 탐색하는 동안 후행 포인터를 유지할 필요가 없습니다. 또한 목록의 끝이 검색을 시작하기에 더 가까울 수 있다는 힌트가있는 경우 목록을 어느 방향 으로든 탐색 할 수 있습니다. 한번 보았던 하나의 모호한 시스템은 마지막 활동이 발생한 "중간"에 포인터를 유지했습니다.

블록을 해제 할 때. 오직 네 가지 경우가 있습니다 :

• 무료 블록이 무료 블록 후 인접 해 있습니다.
• 자유 블록은 앞에 있고 자유 블록 앞에 있습니다.
• 빈 블록은 그 전후의 두 자유 블록 사이에 있습니다.
• 빈 블록이 여유 블록과 인접하지 않습니다. 인접한 자유 블록을 병합의

목적은 다음과 같습니다

• 는
• 정확하게 볼 앞서 찾기 위해 할당 부담없이 무료로 블록의 크기를 반영하기 위해 연결리스트의 길이를 줄이기 위해 두 블록이 인접한 경우

빈 블록을 특정 길이의 freelist로 정렬하면 종종 이점이 있지만 대부분의 실제 구현에서는 병합이 우선이므로 alloc() 다른 크기의 여유 블록이 많으면 다른 크기 블록에 대한 요청이 부적절하게 거부되지 않습니다.