JUNGLE 240425 (W06)

in Study #Jungle

KRAFTON JUNGLE Week 06

9.9 동적 메모리 할당

동적 메모리 할당기

  • 힙이라고 하는 프로세스의 가상 메모리 영역을 관리
  • 저수준의 mmap, munmap 함수를 사용해 가상 메모리 영역을 생성하거나 삭제할 수 있지만,
  • 이것보다 동적 메모리 할당기를 사용하는 게 조금 더 편리하고 호환성이 좋음


️⭐️ 힙(heap)이란?

  • 초기화되지 않은 데이터 영역 직후에 시작해서 위쪽으로 커지는 무요구 메모리 영역
  • 힙의 꼭대기를 가리키는 변수는 brk이며 커널은 각각의 프로세스에 대해 이를 사용

✔ 할당기는 힙을 다양한 크기의 블록들의 집합으로 관리

  • 각 블록은 할당되었거나(allocated), 사용 가능한(free) 가상 메모리의 연속적인 묶음
  • 가용 블록은 명시적으로 application이 할당할 때까지 가용된 상태
  • 할당된 블록은 application에 의해 명시적으로 혹은 메모리 할당기에 의해 묵시적으로 반환될 때까지 할당된 채로 남아있음
할당기의 종류
  1. 명시적 할당기 (explicit allocator)
    • application이 할당된 블록을 명시적으로 반환해주길 요구
    • ex. C 표준 라이브러리의 malloc, free 함수를 직접 호출
  2. 묵시적 할당기 (implicit allocator)
    • 할당기가 언제 할당된 블록이 더 이상 프로그램에 의해 사용되지 않고 블록을 반환하는지를 검출하도록 요구
    • garbage collection: 자동으로 사용되지 않은, 할당된 블록을 반환시켜주는 작업
    • ex. List, ML, JAVA 등의 언어

malloc & free 함수

malloc 함수
void *malloc(size_t size);
  • 프로그램은 malloc 함수를 호출해 힙으로부터 블록들을 할당 받음
  • 리턴값은 어떤 종류의 데이터 객체에 대해 적절히 정렬된, 최소 size 바이트를 가지는 메모리 블록의 포인터 값
free 함수
void free(void *ptr);
  • 할당된 힙 블록은 free 함수를 호출해서 반환함
  • ptr은 malloc, calloc, realloc에서 반환된 할당 블록의 시작 주소를 가리켜야 함
  • free 함수는 포인터의 값을 따로 초기화하지 않기 때문에 ptr = NULL 작업을 해주면 더 안전

할당기 요구사항과 목표

명시적 할당기의 요구사항
  1. 임의의 요청 순서 처리하기
  2. 요청에 즉시 응답하기
  3. 힙만 사용하기
  4. 블록 정렬하기 (정렬 요건)
  5. 할당된 블록 수정하지 않기
명시적 할당기의 목표

처리량, 메모리 이용도를 최대화하려는 성능 목표

  1. 처리량 극대화 하기
    • 처리량: 단위 시간당 완료되는 요청의 수
  2. 메모리 이용도 최대화 하기
    • 가상 메모리의 양은 디스크 내의 스왑 공간의 양에 의해 제한되기 때문에 유한함

단편화

가용 메모리가 어떤 이유들로 인해 할당 요청을 만족시킬 수 없을 때 나타나는 현상

내부 단편화
  • 할당된 블록이 데이터 자체보다 더 클 때 발생하는 단편화
  • 할당된 블록의 크기와 이들의 데이터 사이의 차이의 합
  • 어디서든 내부 단편화의 양은 이전에 요청한 패턴과 할당기 구현에만 의존
    외부 단편화
  • 할당 요청을 만족시킬 수 있는 메모리 공간이 전체적으로 봤을 때는 충분하지만, 이 요청을 처리할 수 있는 단일한 가용 블록이 없는 경우에 발생하는 단편화
  • 미래의 요청 패턴에 따라 외부 단편화가 일어날지 여부가 갈리기 때문에 측정하기 어려움
  • 따라서, 더 적은 수의 더 큰 가용 블록들을 유지하려는 방법을 채택하고 있음

구현 이슈

  • 가용 블록 구성: 어떻게 가용 블록들을 지속적으로 추적하는가?
  • 배치: 새롭게 할당된 블록을 배치하기 위한 가용 블록을 어떻게 선택하는가?
  • 분할: 새롭게 할당된 블록을 배치한 후 가용 블록의 나머지 부분들로 무엇을 할 것인가?
  • 연결: 막 반환된 블록으로 무엇을 할 것인가?

묵시적 가용 리스트

  • 실용적인 할당기는 블록의 경계를 구분하고, 할당된 블록/가용 블록을 구분하는 데이터 구조를 필요로 함
  • 대부분의 할당기는 이 정보를 블록 내에 저장
  • 블록은 1워드 헤더, 데이터(payload), 추가적인 패딩으로 구성
  1. 헤더 (Header)
    • 블록 크기 (헤더, 패딩 포함) + 블록 할당 여부 인코딩
    • 따라서 헤더에서는 블록 크기의 상위 29비트만 저장할 필요가 있고, 나머지 3비트는 다른 정보를 인코드하기 위해 남겨둔다.
    • 최소 중요 비트(할당된 비트)를 사용해 정보 나타냄
  2. 데이터 (Payload)
    • 데이터는 application이 malloc을 불렀을 때 요구한 데이터가 따라옴
  3. 패딩 (Padding)
    • 패딩의 크기는 가변적 (더블 워드 정렬 요구조건 -> 블록은 8배수 크기여야 하므로 이를 채우기 위함)
    • 외부 단편화 극복을 위한 전략의 일부분
    • 정렬 요구사항을 만족하기 위해 필요

️⭐️ 묵시적 가용 리스트

  • 가용 블록이 헤더 내 필드에 의해 묵시적으로 연결됨
  • 단순하다는 장점이 있지만, 가용 리스트를 탐색하는 연산 비용이 힙에 있는 전체 할당된 블록과 가용 블록 수에 비례한다는 단점이 있음
  • 시스템의 정렬 요구조건 & 할당기의 블록 포맷 선택이 최소 블록 크기를 결정
  • 할당되거나 반환된 블록 모두는 이 최솟값보다 더 작을 수 없음

할당된 블록의 배치

application이 k 바이트의 블록을 요청할 때의 상황

  • 할당기는 k 바이트 블록을 저장하기에 충분히 큰 가용 블록을 리스트에서 검색
  • 이 검색을 수행하는 방법은 배치 정책(Placement Policy)에 의해 결정
  1. First Fit
    • 가용 리스트를 처음부터 검색해 크기가 맞는 첫번째 가용 블록 선택
    • 장점: 리스트 마지막에 가장 큰 가용 블록들을 남겨두는 경향이 있음
    • 단점: 리스트의 앞부분에 작은 가용 블록들을 남겨두는 경향이 있어 큰 블록을 찾는 경우 검색 시간이 늘어남
  2. Next Fit
    • First Fit과 비슷하지만 검색을 리스트의 처음에서 시작하는 대신, 이전 검색이 종료된 지점에서 검색 시작
    • 힙의 끝 지점(Epilogue Block)까지 적당한 블록을 못찾으면 시작 지점(Prologue Block)부터 마지막 할당 블록까지 다시 탐색
    • First Fit에 비해 매우 빠르지만 최악의 메모리 이용도를 가짐
  3. Best Fit
    • 모든 가용 블록을 검사하여 크기가 맞는 가장 작은 블록 선택
    • 메모리 이용도가 가장 좋지만 힙을 완전히 다 검색해야 하기 때문에 느림
    • 이를 극복하기 위해 만든 복잡한 다단 가용 리스트 조직(Segregated Free List)이 있음

✔ 할당기가 요청한 블록을 찾을 수 없다면?

  • 메모리에서 물리적으로 인접한 가용 블록들을 연결해 더 큰 가용 블록을 만들어보고,
  • 그래도 충분히 큰 블록이 만들어지지 않거나, 이미 최대로 연결된 상태라면,
  • 그 때는 할당기가 커널에게 sork 함수를 호출해 추가적인 힙 메모리를 요청
  • 할당기는 추가 메모리를 한 개의 더 큰 가용 블록으로 변환하고, 이를 가용 리스트에 삽입한 후에 요청한 블록을 이 새로운 가용 블록에 배치

경계 태그로 연결하기

  • 현재 블록의 헤더를 통해 다음 블록의 헤더의 위치를 알 수 있기에 다음 블록이 free 상태인지 확인할 수 있음
  • 현재 블록(current block) : free 시키려고 하는 블록
    • 다음 블록의 크기가 현재 블록의 헤더에 있는 block size에 더해짐
    • 따라서, 블록은 상수 시간 내에 연결할 수 있음
  • 그렇다면 어떻게 이전 블록을 연결할까?
    1. 현재 블록에 도달할 때까지 전체 리스트를 서치해서 이전 블록의 위치를 기억하는 것 -> O(n)
    2. 각 블록의 끝 부분에 “경계 태그(boundary tag)”, 즉 footer를 추가하는 것
경계 태그 (Boundary Tag)
  • footer는 헤더를 복사한 것으로, 항상 현재 블록의 끝 부분에서 1워드 떨어진 곳에 위치함
  • footer에는 헤더와 똑같이 블록 크기와 allocated/free 상태 정보를 담음
  • 할당기는 시작 위치와 이전 블록의 상태를 자신의 footer를 조사해서 결정할 수 있게 됨
경계 태그가 있을 떄 연결의 모든 경우의 수

현재 블록을 allocated -> free 할 때의 상황

  1. 이전, 다음 블록이 모두 allocated 상태일 때
    • 현재 블록의 상태가 allocated -> free
  2. 이전 블록은 allocated, 다음 블록은 free
    • 현재 블록은 다음 블록과 통합됨 (현재 블록의 footer가 f이고, 다음 블록의 header가 f이므로)
  3. 이전 블록은 free, 다음 블록은 allocated
    • 현재 블록은 이전 블록과 통합됨 (현재 블록의 header가 f이고, 이전 블록의 footer가 f이므로)
  4. 이전, 다음 블록 모두 free
    • 세 블록이 모두 하나의 free 블록으로 통합됨
    • 이전 블록의 헤더와 다음 블록의 footer가 세 블록의 크기를 합한 것으로 갱신됨