메모리 할당 방식에는 여러 가지가 있으며, 그 중 implicit(암시적), explicit(명시적), segregated list(분리된 리스트)는 메모리 블록을 관리하는 데 사용되는 대표적인 방법들이다. 각 방식은 메모리를 할당하고 해제하는 방법, 그리고 가용 메모리 블록을 추적하는 방법에서 차이를 보인다.
Fist Fit은 사용 가능한 메모리 블록 리스트를 처음부터 탐색해 요청된 크기를 수용할 수 있는 첫 번째 블록을 할당한다. 탐색 과정이 단순하며 때로 빠르다. 하지만 메모리 앞부분에 작은 블록들이 많이 남게 되어 큰 메모리 요청을 처리할 때 효율이 떨어질 수 있다. 이는 외부 단편화로 이어진다.
Next Fit은 Last Fit과 유사하되, 마지막으로 메모리를 할당한 위치부터 탐색을 시작해 전체 리스트를 순환한다. 마지막 할당 위치에서 시작하기 때문에 전체 메모리 공간의 사용이 더 균일해질 수 있다. 하지만 탐색 효율성이 낮아질 수 있으며, 큰 블록 요청 시 외부 단편화 문제가 발생할 수 있다.
Best Fit은 요청된 크기를 수용할 수 있으면서 가장 작은 블록을 선택해 할당한다. 메모리 낭비를 최소화하여 외부 단편화의 가능성을 줄인다. 하지만 전체 리스트를 탐색해야 하므로 탐색 시간이 길어질 수 있으며, 빈번한 작은 블록 할당으로 인해 내부 단편화가 발생할 수 있다.
implicit(암시적) 메모리 할당 방식은 free list를 사용하여 가용 메모리 블록을 추적한다. 이 리스트는 메모리 내의 가용 블록들을 순차적으로 연결한다. 메모리 할당 요청이 들어오면, 할당자는 리스트를 처음부터 탐색하여, 요청된 크기를 수용할 수 있는 첫 번째 블록을 할당한다. 이 과정을 "first-fit" 탐색이라고도 한다.
이 포스팅에는 implicit을 더 효율적인 next-fit으로 변형한 코드만 다루고 있다.
mm_init 함수는 메모리 관리 시스템을 초기화하는 데 사용된다. 이 함수는 동적 메모리 할당자를 초기화하고, 필요한 초기 메모리 구조를 설정하여 사용자가 요청하는 메모리 할당 및 해제 요청을 처리할 준비를 한다.
int mm_init(void)
{
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1) // 초기 힙 메모리를 할당
return -1;
PUT(heap_listp, 0); // 힙의 시작 부분에 0을 저장하여 패딩으로 사용
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); // 프롤로그 블럭의 헤더에 할당된 상태로 표시하기 위해 사이즈와 할당 비트를 설정하여 값을 저장
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); // 프롤로그 블록의 풋터에도 마찬가지로 사이즈와 할당 비트를 설정하여 값을 저장
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); // 에필로그 블록의 헤더를 설정하여 힙의 끝을 나타내는 데 사용
heap_listp += (2 * WSIZE); // 프롤로그 블록 다음의 첫 번째 바이트를 가리키도록 포인터 조정
find_nextp = heap_listp; // nextfit을 위한 변수
if (extend_heap(CHUNKSIZE / WSIZE) == NULL) // 초기 힙을 확장하여 충분한 양의 메모리가 사용 가능하도록 chunksize를 단어 단위로 변환하여 힙 확장
return -1;
if (extend_heap(4) == NULL) //자주 사용되는 작은 블럭이 잘 처리되어 점수가 오름
return -1;
return 0;
}
mm_malloc 함수의 구현은 메모리 관리 시스템의 일부로, 요청된 크기의 메모리 블록을 동적으로 할당하는 기능을 제공한다. 이 함수는 요청된 크기를 조정하여 오버헤드와 정렬 요구 사항을 충족시키고, 적절한 크기의 블록을 찾거나 힙을 확장하여 메모리를 할당한다.
void *mm_malloc(size_t size)
{
size_t asize; /* Adjusted block size */
size_t extendsize; /* Amount to extend heap if no fit */
char *bp;
/* Ignore spurious requests */
if (size == 0)
return NULL;
/* Adjust block size to include overhead and alignment reqs. */
if (size <= DSIZE)
asize = 2 * DSIZE;
else
asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL)
{
place(bp, asize);
return bp;
}
/* No fit found. Get more memory and place the block */
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}
아래는 동적 메모리 할당기의 일부로 사용되는 find_fit 함수의 구현 예시이며, "Next Fit" 메모리 할당 전략을 사용한다. 이 함수의 목적은 요청된 크기(asize) 이상의 가용 메모리 블록을 찾는 것이다.
static void *find_fit(size_t asize)
{
/* Next-fit search */
void *bp;
bp = find_nextp;
// 현재 블록이 에필로그 블록이 아닌 동안 계속 순회, 블록의 헤더 크기가 0보다 크지 않으면 에필로그 블럭
for (; GET_SIZE(HDRP(find_nextp)) > 0; find_nextp = NEXT_BLKP(find_nextp))
{
// 가용 블럭의 헤더가 할당되어 있지 않고 요청된 크기보다 크거나 같은 경우 해당 가용 블록을 반환
if (!GET_ALLOC(HDRP(find_nextp)) && (asize <= GET_SIZE(HDRP(find_nextp))))
{
return find_nextp;
}
}
// 위의 for루프에서 가용 블럭을 찾지 못한 경우, 다시 순회
for (find_nextp = heap_listp; find_nextp != bp; find_nextp = NEXT_BLKP(find_nextp))
{ // 이전에 탐색했던 find_nextp 위치에서부터 다시 가용 블록을 찾아서 반환
if (!GET_ALLOC(HDRP(find_nextp)) && (asize <= GET_SIZE(HDRP(find_nextp))))
{
return find_nextp;
}
}
return NULL;
}
place 함수는 메모리 할당 과정에서 효율성을 높이기 위해 설계되었다. 할당 요청에 따라 메모리 블록을 최적으로 사용할 수 있도록 하며, 할당 후 남은 공간이 충분히 크면 이를 다시 가용 블록으로 반환하여 메모리 낭비를 줄인다. 이 과정은 메모리 단편화를 방지하고 메모리 사용 효율을 높이는 데 중요하다.
static void place(void *bp, size_t asize)
{
size_t csize = GET_SIZE(HDRP(bp)); // 현재 블록의 크기를 알아냄
// 남은 공간이 충분히 클 경우, 즉 요청한 크기(asize)와 현재 크기(csize)의 차이가
// 두 배의 더블 사이즈(DSIZE)보다 크거나 같으면 블록을 나눔
if ((csize - asize) >= (2 * DSIZE))
{
PUT(HDRP(bp), PACK(asize, 1)); // 사용할 블록의 헤더에 크기와 할당된 상태 저장
PUT(FTRP(bp), PACK(asize, 1)); // 사용할 블록의 푸터에도 똑같이 저장
bp = NEXT_BLKP(bp); // 나머지 블록으로 포인터 이동
PUT(HDRP(bp), PACK(csize - asize, 0)); // 나머지 블록의 헤더에 크기와 빈 상태 저장
PUT(FTRP(bp), PACK(csize - asize, 0)); // 나머지 블록의 푸터에도 똑같이 저장
}
else // 남은 공간이 충분히 크지 않으면 현재 블록 전체 사용
{
PUT(HDRP(bp), PACK(csize, 1)); // 현재 블록의 헤더에 크기와 할당된 상태 저장
PUT(FTRP(bp), PACK(csize, 1)); // 현재 블록의 푸터에도 똑같이 저장
}
}
coalesce 함수는 메모리 해제 또는 메모리 할당 과정 중에 인접한 가용 블록들을 하나의 큰 블록으로 합치는 역할을 한다. 이 과정은 메모리 단편화를 줄이고, 효율적인 메모리 사용을 가능하게 한다. 병합 방식은 주변 블록들의 할당 상태에 따라 달라진다.
static void *coalesce(void *bp)
{
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
if (prev_alloc && next_alloc) /* Case 1 */
{
return bp;
}
if (prev_alloc && !next_alloc) /* Case 2 */
{
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
}
else if (!prev_alloc && next_alloc) /* Case 3 */
{
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
else /* Case 4 */
{
size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
find_nextp = bp;
return bp;
}
realloc 함수는 주어진 포인터 ptr에 할당된 메모리 블록의 크기를 변경하기 위해 사용된다. 요청된 새 크기(size)에 따라 메모리 블록을 확장하거나 축소한다. 이 과정에서 필요하다면, 새로운 메모리 위치로 데이터를 복사하고 원래 메모리를 해제한다.
void *mm_realloc(void *ptr, size_t size)
{
void *oldptr = ptr;
void *newptr;
size_t copySize;
// 새로운 메모리 블록 할당
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
// 이전 블록의 데이터 크기를 가져옴
copySize = GET_SIZE(HDRP(oldptr));
// 실제 복사할 데이터 크기는 이전 블록 크기와 요청된 새 블록 크기 중 작은 값
if (size < copySize)
copySize = size;
// 데이터를 새 블록으로 복사
memcpy(newptr, oldptr, copySize);
// 이전 블록 해제
mm_free(oldptr);
return newptr;
}
implicit 리스트를 사용한 메모리 할당에서는 가용 블록을 찾기 위해 리스트의 시작부터 순차적으로 탐색해야 한다. 큰 메모리 풀에서 적합한 블록을 찾는 데 시간이 오래 걸릴 수 있으며, 이는 메모리 할당과 해제 작업의 효율성을 떨어뜨린다. 메 모리 할당과 해제가 빈번하게 이루어질 경우, 암시적 방식은 빠르게 메모리 단편화를 야기하고, 이는 시간이 지남에 따라 전반적인 시스템 성능에 부정적인 영향을 미칠 수 있다.
위 구현된 implicit 외의 explicit(명시적) 메모리 할당 방식에서는 가용 메모리 블록을 관리하기 위해 별도의 자료 구조(예: 이중 연결 리스트)를 사용한다. 각 가용 블록은 다음과 이전의 가용 블록을 가리키는 포인터를 포함한다. 이를 통해 할당과 해제가 훨씬 유연하게 이루어질 수 있다.
segregated list(분리된 리스트) 메모리 할당 방식에서는 다양한 크기 범위에 따라 여러 개의 가용 리스트를 유지한다. 각 리스트는 특정 크기 범위의 블록들만을 포함한다. 메모리 할당 요청이 들어오면, 해당 크기 범위에 맞는 리스트를 선택하여 가용 블록을 탐색한다.
buddy system은 가변 크기의 메모리 할당을 지원하며, 특히 시스템 프로그래밍이나 운영 체제에서 자주 사용된다. Buddy System의 핵심 아이디어는 메모리를 고정된 크기의 블록으로 분할하고, 이 블록들을 필요에 따라 합치거나 분할하여 메모리를 할당하는 것이다. 이 과정에서 각 메모리 블록의 "buddy" 또는 짝을 이용해 효율적으로 메모리를 관리한다.
buddy system의 메모리는 2의 거듭제곱 크기의 블록으로 분할된다. 예를 들어, 메모리 크기가 2^N인 경우, 가능한 블록 크기는 2^0, 2^1, 2^2, ..., 2^N까지 다양하다. 그리고 할당을 할 때에는 요청된 메모리 크기에 가장 잘 맞는 블록 크기를 찾는다. 이는 요청 크기보다 크거나 같은 가장 작은 2의 거듭제곱 크기의 블록을 의미한다. 만약 해당 크기의 블록이 없다면, 더 큰 블록을 분할하여 요구를 충족시킨다.
각 블록은 고유한 buddy 또는 짝을 가지며, 이는 같은 크기의 인접한 블록을 의미한다. Buddy는 블록의 주소와 크기를 이용하여 계산할 수 있다. 메모리 블록이 해제될 때, 해당 블록의 buddy가 현재 사용 가능한지 확인한다. 만약 buddy도 사용 가능하다면, 두 블록을 합쳐서 더 큰 블록을 만든다. 이 과정을 반복하여 가능한 한 큰 블록을 유지한다.
https://github.com/yunsejin/Malloc-lab
GitHub - yunsejin/Malloc-lab: 4교육장 5주차 (2024.2.8(목) ~ 2024.2.21(수)) 2조 공부 기록
4교육장 5주차 (2024.2.8(목) ~ 2024.2.21(수)) 2조 공부 기록. Contribute to yunsejin/Malloc-lab development by creating an account on GitHub.
github.com
'CS > 메모리 관리' 카테고리의 다른 글
| Register, RAM, ROM, Disk (0) | 2024.03.26 |
|---|---|
| Call by Value vs Call by Reference, Garbage Collection (1) | 2024.03.23 |
| 동적 메모리 할당(malloc, calloc, realloc) (1) | 2024.03.23 |
| 힙과 스택, 프로세스와 스레드 (1) | 2024.03.23 |
| 버퍼, DMA(Direct Memory Access) (2) | 2024.03.23 |