말감둜그

ν¬λž˜ν”„ν†€ μ •κΈ€ WEEK5 Day 40 - implict list/explict free list/malloc λ³Έλ¬Έ

Krafton jungle

ν¬λž˜ν”„ν†€ μ •κΈ€ WEEK5 Day 40 - implict list/explict free list/malloc

habbn 2024. 2. 17. 01:00
728x90

πŸ“†2024.2.16

 

CSAPP 6μž₯ λ’· λΆ€λΆ„ 더 읽고 μ •λ¦¬ν•˜μ˜€λ‹€.

λ°±μ€€ μ•”κΈ°μ™• ν’€λ©΄μ„œ 이진 탐색에 λŒ€ν•΄ λ‹€μ‹œ λ³΅μŠ΅ν•˜κ²Œ λ˜μ—ˆκ³  set ν•¨μˆ˜λ„ λΆ„λͺ… λ΄€μ—ˆλŠ”λ° λ‹€μ‹œ 또 κΉŒλ¨Ήμ–΄μ„œ 볡슡..

 

set ν•¨μˆ˜λŠ” μ€‘λ³΅λœ 값을 μ œκ±°ν•˜κ±°λ‚˜, λ°μ΄ν„°μ˜ 유무λ₯Ό ν™•μΈν•˜λŠ” 데 주둜 μ‚¬μš©λœλ‹€. λ˜ν•œ μˆœμ„œκ°€ μ—†λŠ” μžλ£Œν˜•μ΄λ‹€.

in ν‚€μ›Œλ“œλŠ” μ–΄λ–€ 값이 νŠΉμ • μ‹œν€€μŠ€(리슀트, νŠœν”Œ, λ¬Έμžμ—΄ λ“±) ν˜Ήμ€ μ»¬λ ‰μ…˜(λ”•μ…”λ„ˆλ¦¬, 집합 λ“±) μ•ˆμ— μ‘΄μž¬ν•˜λŠ”μ§€ κ²€μ‚¬ν•˜λŠ” μ—°μ‚°μžμ΄λ‹€.

 

λ°±μ€€ 숫자 μΉ΄λ“œ 2λ₯Ό ν’€λ©΄μ„œ 파이썬 collections λͺ¨λ“ˆμ˜ Counterλ₯Ό μ•Œκ²Œ λ˜μ—ˆλ‹€.

from collections import Counter

 

Counter μƒμ„±μžλŠ” μ—¬λŸ¬ ν˜•νƒœμ˜ 데이터λ₯Ό 인자둜 λ°›λŠ”λ‹€. λ¨Όμ € μ€‘λ³΅λœ 데이터가 μ €μž₯된 배열을 인자둜 λ„˜κΈ°λ©΄ 각 μ›μ†Œκ°€ λͺ‡ λ²ˆμ”© λ‚˜μ˜€λŠ”μ§€κ°€ μ €μž₯된 객체λ₯Ό μ–»κ²Œ λœλ‹€.

 

Counter 클래슀λ₯Ό μ΄μš©ν•˜μ—¬ card1 λ¦¬μŠ€νŠΈμ— μžˆλŠ” 각 숫자의 개수λ₯Ό μ„Έμ–΄ λ”•μ…”λ„ˆλ¦¬ ν˜•νƒœλ‘œ μ €μž₯ν•œλ‹€. 

그리고 card2 λ¦¬μŠ€νŠΈμ— μžˆλŠ” μˆ«μžλ“€μ΄ counter λ”•μ…”λ„ˆλ¦¬μ— λͺ‡ 개 μžˆλŠ”μ§€λ₯Ό 좜λ ₯ν•œλ‹€.

 

μ½”μ–΄νƒ€μž„μœΌλ‘œ 동적 λ©”λͺ¨λ¦¬ ν• λ‹Ή(sbrk), implict list / explict free list 듀은 것 정리

 


 

malloc / free

 

 

동적 λ©”λͺ¨λ¦¬ ν• λ‹ΉκΈ°λŠ” νž™μ΄λΌκ³  ν•˜λŠ” ν”„λ‘œμ„ΈμŠ€μ˜ 가상메λͺ¨λ¦¬ μ˜μ—­μ„ κ΄€λ¦¬ν•œλ‹€.

 

νž™μ˜ κΌ­λŒ€κΈ°λ₯Ό κ°€λ¦¬ν‚€λŠ” λ³€μˆ˜ brk

sbrk ν•¨μˆ˜λŠ” brk 포인터에 incr을 λ”ν•΄μ„œ νž™μ„ λŠ˜λ¦¬κ±°λ‚˜ 쀄인닀

#include <unistd.h>

void *sbrk(intptr_t incr);

 

 

λͺ…μ‹œμ  ν• λ‹ΉκΈ° ->  ν”„λ‘œκ·Έλž˜λ¨Έ  malloc & free

λ¬΅μ‹œμ  ν• λ‹ΉκΈ° -> 컴퓨터    가비지 컬렉터

-> λͺ…μ‹œμ  ν• λ‹ΉκΈ°λ₯Ό μ•Œμ•„λ³΄μž

 

ν• λ‹ΉκΈ° μˆ˜ν–‰ 쑰건

1. μž„μ˜μ˜ μš”μ²­μ— λŒ€ν•΄ μˆœμ„œμ²˜λ¦¬

   - free()ν•˜κ³  또 free()ν•˜λ©΄ μ•ˆλ¨

2. μš”μ²­μ— λŒ€ν•œ 즉각적인 응닡

   - malloc() ν•˜κ³  free() μˆœμ„œλŒ€λ‘œ

3. heap만 μ‚¬μš©

4. μ–΄λ–€ νƒ€μž…μ˜ 객체든 μ €μž₯

5. μ••μΆ• ν—ˆμš© X

 

λͺ©ν‘œ

1. μ²˜λ¦¬λŸ‰ μ΅œλŒ€ν™”

 - μ–Όλ§ˆλ‚˜ λ§Žμ€ μ‹œκ°„ μ•ˆμ— ν• λ‹Ήν•˜κ³  ν•΄μ œ ν•  수 μžˆλŠλƒ

2. λ©”λͺ¨λ¦¬ μ΄μš©λ„ μ΅œλŒ€ν™”

- μ–Όλ§ˆλ‚˜ 효율적으둜 μ‚¬μš©ν•˜λŠλƒ(λ‚­λΉ„X)

 

κ°€μš© 블둝 μ–΄λ–»κ²Œ ꡬ성?   -> λ¬΅μ‹œμ  κ°€μš© 리슀트 / λͺ…μ‹œμ  κ°€μš© 리슀트

블둝 배치 μ–΄λ–»κ²Œ ? -> fit  (best fit, first fit, next fit)

κ°€μš© 블둝 λΆ„ν•  μ–΄λ–»κ²Œ ? -> 뢄리 κ°€μš© 리슀트 (크기 λ³„λ‘œ 뢄리)

ν•΄μ œλ˜μ—ˆμ„ λ•Œ μƒκΈ°λŠ” κ°€μš© 블둝 μ–΄λ–»κ²Œ μ—°κ²°? - > 경계 νƒœκ·Έλ‘œ μ—°κ²°

 

1. λ¬΅μ‹œμ  κ°€μš© 리슀트 ( μ‚¬μ΄μ¦ˆλ§Œ μ•Œλ €μ€Œ, 직접 계산해야 함)

- κ°€μš© 블둝이 헀더 λ‚΄ ν•„λ“œμ— μ˜ν•΄μ„œ λ¬΅μ‹œμ μœΌλ‘œ μ—°κ²°. 

- κ°„μ ‘μ μœΌλ‘œ κ°€μš© 블둝 전체 집합을 νž™ λ‚΄μ˜ 전체 블둝을 λ‹€λ‹ˆλ©΄μ„œ λ°©λ¬Έν•  수 μžˆλ‹€.

- 더블 μ›Œλ“œ μ •λ ¬ μš”κ΅¬ 쑰건을 κ°€μ •ν•œλ‹€λ©΄, 각 λΈ”λ‘μ˜ ν¬κΈ°λŠ” 2μ›Œλ“œ(8λ°”μ΄νŠΈ)의 λ°°μˆ˜μ—¬μ•Ό ν•œλ‹€. (μ΅œμ†Œ 블둝 크기 κ²°μ •)                                                                                                                                                                           

νž™ 블둝

 

2. λͺ…μ‹œμ  κ°€μš©λ¦¬μŠ€νŠΈ (κ°€μš©λœ λΈ”λŸ­λ§Œ 보자, ν¬μΈν„°λ‘œ μ•Œλ €μ€Œ)    

 

각 κ°€μš© 블둝 내에 pred(predeccseor)와 succ(successor) 포인터λ₯Ό ν¬ν•¨ν•˜λŠ” 이쀑 μ—°κ²° κ°€μš© 리슀트둜 ꡬ성.

이쀑 μ—°κ²° 리슀트λ₯Ό μ‚¬μš©ν•˜λ©΄ first fit ν• λ‹Ή μ‹œκ°„μ„ 전체 블둝 μˆ˜μ— λΉ„λ‘€ν•˜λŠ” κ²ƒμ—μ„œ κ°€μš© λΈ”λ‘μ˜μˆ˜μ— λΉ„λ‘€ν•˜λŠ” κ²ƒμœΌλ‘œ 쀄일 수 μžˆλ‹€. κ·Έλ ‡μ§€λ§Œ 블둝을 λ°˜ν™˜ν•˜λŠ” μ‹œκ°„μ€ κ°€μš© 리슀트 λ‚΄μ—μ„œ 블둝을 μ •λ ¬ν•˜λŠ” 정책을 μ–΄λ–€ 것을 μ„ νƒν•˜λŠ”κ°€μ— 따라 λΉ„λ‘€ν•™λ‚˜ μƒμˆ˜ μ‹œκ°„μ„ κ°€μ§ˆ 수 μžˆλ‹€.

       allocated                               free    ->  ν• λ‹Ήλ˜λ©΄ 포인터 μ—†μ• κ³  데이터 μž…λ ₯                                                                                            

 

1. LIFOμˆœμ„œμ™€ first fit 배치 정책을 μ‚¬μš©ν•˜λ©΄ μ΅œκ·Όμ— μ‚¬μš©λœ 블둝듀을 λ¨Όμ € μ‘°μ‚¬ν•œλ‹€.

2. 리슀트λ₯Ό μ£Όμ†Œ 순으둜 관리. (LIFO μˆœμ„œλ₯Ό ν•˜λŠ” κ²½μš°λ³΄λ‹€ best fit의 μ΄μš©λ„μ— κ·Όμ ‘ν•˜λŠ” 더 쒋은 λ©”λͺ¨λ¦¬ μ΄μš©λ„λ₯Ό 가짐)

 

9.9.12 κ°„λ‹¨ν•œ ν• λ‹ΉκΈ°μ˜ κ΅¬ν˜„

λ¬΅μ‹œμ  κ°€μš© λ¦¬μŠ€νŠΈμ— κΈ°μ΄ˆν•œ κ°„λ‹¨ν•œ ν• λ‹ΉκΈ°μ˜ κ΅¬ν˜„μ„ λ”°λΌν•΄λ³΄μž

μ΅œλŒ€ 블둝 ν¬κΈ°λŠ” 2^32  = 4GB 이닀. μ½”λ“œλŠ” 32λΉ„νŠΈ(gcc -m32) λ˜λŠ” 64λΉ„νŠΈ(gcc -m64)이며, ν”„λ‘œμ„ΈμŠ€μ—μ„œ μˆ˜μ • 없이 돌 수 μžˆλŠ” 것은 64λΉ„νŠΈμ΄λ‹€.

 

 

κ°€μš© 리슀트 μ‘°μž‘μ„ μœ„ν•œ κΈ°λ³Έ μƒμˆ˜μ™€ 맀크

/* Basic constants and macros */
#define	WSIZE   4   /*Word and header/footer size (bytes)*/
#define DSIZE   8   /*Double word size (bytes)*/
#define CHUNKSIZE (1<<12) /*Extend heap by this amount (bytes)*/

#define MAX(x,y) ((x) > (y) ? (x) : (y))

/*Pack a size and allocated bit into a word*/
#define PACK(size, alloc)   ((size) | (alloc))

/*Read and write a word at address p*/
#define GET(p)      (*(unsigned int *)(p))
#define PUT(p,val)  (*(unsigned int *)(p) = (val)) 

/*Read the size and allocated fields from address p*/
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)

/*Given blovk ptr bp, compute address of its header and footer*/
#define HDRP(bp)    ((char *)(bp) -WSIZE)
#define FTRP(bp)    ((char *)(bp) +GET_SIZE(HDRP(bp))-DSIZE)

/*Given block ptr bp, compute address of next and previous blocks*/
#define NEXT_BLKP(bp)   ((char *)(bp) + GET_SIZE(((char *)(bp) -WSIZE)))
#define PREV_BLKP(bp)   ((char *)(bp) - GET_SIZE(((char *)(bp) -DSIZE)))

 

#define WSIZE 4

  • μ›Œλ“œμ™€ 헀더/ν’‹ν„° μ‚¬μ΄μ¦ˆ

#define DSIZE 8

  • λ”λΈ”μ›Œλ“œ μ‚¬μ΄μ¦ˆ

#define CHUNKSIZE (1<<12) 

  • CHNKSIZE λ§€ν¬λ‘œλŠ” 2의 12승인 4096 값을 가지도둝 μ •μ˜ν•œ 것
  • 주둜 λ©”λͺ¨λ¦¬ 블둝 크기λ₯Ό μ •μ˜ ν•œ 것, 4096λ°”μ΄νŠΈ = 4KB

#define MAX(x,y) ((x) > (y) ? (x) : (y))

  • max μ •μ˜

#define PACK(size, alloc)   ((size) | (alloc))

  • 크기와 ν• λ‹Ή λΉ„νŠΈλ₯Ό ν†΅ν•©ν•΄μ„œ 헀더와 풋터에 μ €μž₯ν•  수 μžˆλŠ” 값을 리턴

#define GET(p)      (*(unsigned int *)(p))

  • 인자 pκ°€ μ°Έμ‘°ν•˜λŠ” μ›Œλ“œ μ½μ–΄μ„œ 리턴

#define PUT(p,val)  (*(unsigned int *)(p) = (val)) 

  • 인자 pκ°€ κ°€λ¦¬ν‚€λŠ” μ›Œλ“œμ— val μ €μž₯

#define GET_SIZE(p) (GET(p) & ~0x7)

  • μ£Όμ†Œ p에 μžˆλŠ” 헀더 λ˜λŠ” ν’‹ν„°μ˜ size 리턴

#define GET_ALLOC(p) (GET(p) & 0x1)

  • μ£Όμ†Œ p에 μžˆλŠ” 헀더 λ˜λŠ” ν’‹ν„°μ˜ ν• λ‹Ή λΉ„νŠΈ 리턴

#define HDRP(bp)    ((char *)(bp) - WSIZE)   

  • 블둝 헀더λ₯Ό κ°€λ¦¬ν‚€λŠ” 포인터 리턴

#define FTRP(bp)    ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

  • 블둝 ν’‹ν„°λ₯Ό κ°€λ¦¬ν‚€λŠ” 포인터 리턴

 

#define NEXT_BLKP(bp)   ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))

  • λ‹€μŒ λΈ”λ‘μ˜ 블둝 포인터 리턴

#define PREV_BLKP(bp)   ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

  • 이전 λΈ”λ‘μ˜ 블둝 포인터 리턴

 

 

728x90