2025.04.29

TIL(TODAY I LEARN)

---

• 오늘한 내용 : C - 명시적 가용 리스트(Explict Free List) 구현 - first-fit

• WEEK07: 시스템 콜, 데이터 세그먼트, 메모리 단편화, sbrk/mmap

---

명시적 가용 리스트 방식(explicit free list)

• 자유(가용) 블록들만 별도로 연결 리스트로 관리
• 각 자유 블록의 payload 영역에 prev, next 포인터를 저장하여 가용 블록 간의 이중 연결 리스트를 구성

  전략	설명	장점	단점
  LIFO (Last In First Out)	새 블록을 가용 리스트 맨 앞에 삽입	- 구현 가장 쉬움- 삽입 속도 매우 빠름 (O(1))	- 블록 분할 후 생긴 작은 블록이 계속 재사용돼 조각화 증가 가능성
  주소 순 정렬	주소 기준 오름차순으로 삽입	- coalesce 구현이 더 쉬움- 조각화 방지에 도움	- 구현 복잡- insert_node 비용 ↑ (O(n))

• 할당 시: 전체 블록을 순회하지 않고, 가용 리스트만 탐색하므로 O(#free) 탐색 시간 확보 가능
  
• 해제 시:
  • 블록을 free 상태로 표시한 후
  • 인접 블록들과 coalesce(병합) 하고
  • 가용 리스트에 삽입 (insert) 또는 삭제(remove) 등 포인터 조작 수행

LIFO 방식으로 구현

함수명	수정 이유
mm_init	free_listp 초기화 필요 (가용 리스트의 시작 포인터)
extend_heap()	새 블록을 가용 리스트에 추가 (insert_node) ⇒ coalesce()에서 해주므로 그대로 사용 가능
coalesce	병합 후 가용 리스트 내에서 노드 연결 및 삭제/삽입 작업 필요
mm_free	블록을 가용 상태로 만든 후, 가용 리스트에 삽입 필요 (insert_node) ⇒ coalesce()에서 해주므로 그대로 사용 가능
mm_malloc	할당 성공 시 가용 리스트에서 해당 블록 제거 (remove_node) ⇒ place() 내부에서 remove_node() 해주므로 그대로 사용 가능 * 64비트에서 최소크기 32 비트 설정
place	분할 발생 시, 남은 조각을 가용 리스트에 삽입 필요 * 64비트에서 최소크기 32 비트 설정
realloc	내부적으로 mm_malloc, mm_free를 호출하므로 간접 영향 있음
추가되는 함수
insert_node(bp)	가용 블록을 가용 리스트에 삽입
remove_node(bp)	가용 블록을 가용 리스트에서 제거

• 가용 매크로

#define PRED(bp) (*(char **)(bp))         // payload 안에서 0~4바이트까지 저장된 주소 반환
#define SUCC(bp) (*(char **)(bp + DSIZE)) // payload 안에서 4바이트 부터 8바이트까지 저장된 주소 반환
																					// 64비트 컴파일 환경에서 포인터의 크기 8비트임
static char *free_listp;

• mm_init()
  • free_listp = NULL;
  • free_listp == 가용 리스트의 헤더
  • SUCC(bp)를 따라 뒤쪽으로 쭉 이어진 가용 블록 리스트가 됨
• extend_heap()
  • coalesce()에서 insert_node(bp)하므로 그대로 사용가능
• coalesce()

  Case	이전	다음	동작 요약	추가되는 일
  1	할당	할당	병합 X	insert_node(bp)
  2	할당	가용	bp + 다음 블록 병합	remove_node(next) → insert_node(bp)
  3	가용	할당	이전 블록 + bp 병합	remove_node(prev) → insert_node(prev)
  4	가용	가용	이전 + bp + 다음 병합	remove_node(prev) + remove_node(next) → insert_node(prev)

• mm_molloc()
  • 할당했으니 remove_node(bp); 추가
  • place()에서 remove_node(bp) 하므로 그대로 사용가능
• find_fit() → first fit의 변형

for (bp = free_listp; bp != NULL; bp = SUCC(bp)){
        if (asize <= GET_SIZE(HDRP(bp))){
            return bp;
        }
    }

• place()
  • remove_node() → 분할시 insert_node() / 분할X시 끝
• free()
  • coalesce()에서 해주므로 그대로 사용 가능
• insert_node()

  • 가용 리스트의 맨 앞에 끼워 넣는다.

    static void insert_node(void *bp)
    {
        SUCC(bp) = free_listp; //bp의 next = 현재 가용 리스트 헤드
        PRED(bp) = NULL;       //bp의 prev = NIULL
    
        if (free_listp != NULL) //가용리스트가 비어있지 않다면 
        {
            PRED(free_listp) = bp; // 기존 헤드의 prev = bp
        }
    
        free_listp = bp; // 가용 리스트의 헤더 갱신
    }

• remove_node()

  static void remove_node(void *bp)
  {
      if (PRED(bp) != NULL) // 중간 노드
          SUCC(PRED(bp)) = SUCC(bp);
      else // 헤더노드
          free_listp = SUCC(bp);
  
      if (SUCC(bp) != NULL) // 마지막 노드
          PRED(SUCC(bp)) = PRED(bp);
  }

• 64비트 컴파일 환경 세팅
  • SUCC 매크로

    // 기존: (bp + WSIZE)
    #define SUCC(bp) (*(char **)((char *)(bp) + DSIZE))

    → 포인터(8B)를 bp+8에 저장하도록 변경.
    
  • mm_malloc의 최소 블록 크기 보장

    if (size <= DSIZE)
        asize = 4 * DSIZE;  // 32바이트 최소
    else {
        asize = DSIZE * ((size + DSIZE + (DSIZE-1)) / DSIZE);
        if (asize < 4*DSIZE)
            asize = 4*DSIZE;
    

    → 헤더·풋터(8B) + PRED(8B) + SUCC(8B) + 최소 여유(8B) = 32B 보장.
    
  • place()의 분할 조건

    #define MIN_BLOCK_SIZE (4*DSIZE)  // 32바이트
    
    if ((csize - asize) >= MIN_BLOCK_SIZE) {
        /* split + insert_node */
    } else {
        /* 통째로 할당 */
    }

    → 남는 블록이 최소 32B 이상일 때만 쪼개도록 해서, PRED/SUCC 필드와 헤더·풋터가 안전하게 들어가게 함