1차 시도 (Implicit, Next-Fit)

• 1차 시도 코드

<aside> 💡

문제점 분석

</aside>

1. 4, 7, 8, 9, 10번 케이스 점수 50%대 혹은 그 이하
   • 4 : coalescing-bal.rep
   • 7 : binary-bal.rep
   • 8 : binary2-bal.rep
   • 9 : realloc-bal.rep
   • 10 : realloc2-bal.rep
2. 테스트케이스의 분석이 필요해보임

테스트 케이스 분석

형태

19656100   ← suggested heap size (제안 힙 크기, 드라이버가 사실상 무시)
7200       ← ID 개수(num_ids): ptr_<id> 슬롯의 최대 개수
14400      ← 작업 개수(num_ops): 아래에 이어질 총 요청 라인 수
1          ← weight (가중치, 사실상 무시)ㅁ

a X   4095   ← 작은 블록 #1 할당
a X+1 4095   ← 작은 블록 #2 할당 (대개 #1 바로 뒤에 배치됨)
f X          ← #1 해제  →  인접 자유블록(아직 #2는 alloc)
f X+1        ← #2 해제  →  이제 #1·#2가 서로 인접한 자유블록 → 병합되어야 함
a X+2 8190   ← 방금 병합된 큰 자유블록을 써서 더 큰 블록 할당
f X+2        ← 큰 블록 해제

binary-bal.rep

• 형태
  • 연산 : 총 8000
    • allocate : 6000
    • free : 2000
    • realloc : 0
  • 요청 크기 : 64, 448, 512
  • Power of Two (64, 512) / Power of Two 주변 (448) 섞여있는 형태
• 시험 목적

  • 클래스 경계 / 분할 품질: 448은 512에 가깝다 → 512를 잡아 **남기는 조각(512-448=64)**이 이후 64 요청에 쓸만한가?

  • 스플린터(splinter) 발생 / 재사용성, **배치 정책(첫/넥스트/베스트)**의 적합성, 탐색 비용을 동시에 건드림.

    Splinter : 할당을 위해 큰 가용 블록을 쪼갤 때 남는, 너무 작아서 제대로 쓰기 힘든 조각

binary2-bal.rep

• 형태
  • 연산 : 총 24000
    • allocate : 12000
    • free : 12000
    • realloc : 0
  • 요청 크기 : 16, 112, 128
  • 소형 블록 군집(16 / 112)과 그 상위 Power of Two(128)의 체계적 조합
• 시험 목적
  • 소형 전용 분리 리스트 / 경계 정밀도와 분할 임계치를 탄탄히 다졌는지 확인
  • 128에서 112를 뽑을 때 잔여 8B(128-120(asize))처럼 분할 금지 조건이 맞게 작동하는지(“최소 블록 미만이면 분할 금지”)
  • 16 요청의 실제 asize(=24B) 때문에 자투리 블록을 어떻게 처리하는지, 그리고 탐색 비용

coalescing-bal.rep

• 형태

  • 연산 : 총 14400

  a X   4095   ← 작은 블록 #1 할당
  a X+1 4095   ← 작은 블록 #2 할당 (대개 #1 바로 뒤에 배치됨)
  f X          ← #1 해제  →  인접 자유블록(아직 #2는 alloc)
  f X+1        ← #2 해제  →  이제 #1·#2가 서로 인접한 자유블록 → 병합되어야 함
  a X+2 8190   ← 방금 병합된 큰 자유블록을 써서 더 큰 블록 할당
  f X+2        ← 큰 블록 해제
  

  • 요청 크기 : 4095(4800회), 8190(2400회) 두 종류