μΌ | μ | ν | μ | λͺ© | κΈ | ν |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 4κΈ°
- νμ΄μ¬
- μ°κ²°λ¦¬μ€νΈ
- λ°±μ€
- μκ³ λ¦¬μ¦μμ -λλΉμ°μ νμ2
- c#
- ν¬λνν€μ κΈ4κΈ°
- μ΄λ²€νΈ ν¨μ μ€ν μμ
- μ μ-μ ν¬
- TiL
- μ λν°
- KRAFTON JUNGLE
- ν¬λνν€μ κΈ
- μΆμν΄λμ€μμΈν°νμ΄μ€
- λ€νΈμν¬
- ν¬λνν€ μ κΈ 4κΈ°
- μκ³ λ¦¬μ¦
- Unity
- C
- pintos
- kraftonjungle
- λ€μ΅μ€νΈλΌ
- project3
- anonymous page
- ν¬λνν€ μ κΈ
- User Stack
- νν μ€
- ν°μ€ν 리μ±λ¦°μ§
- BFS
- μ€λΈμ
- Today
- Total
λ§κ°λ‘κ·Έ
ν¬λνν€ μ κΈ WEEK5 Day 40 - implict list/explict free list/malloc λ³Έλ¬Έ
ν¬λνν€ μ κΈ WEEK5 Day 40 - implict list/explict free list/malloc
habbn 2024. 2. 17. 01:00π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)))
- μ΄μ λΈλ‘μ λΈλ‘ ν¬μΈν° 리ν΄
'Krafton jungle' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
ν¬λνν€ μ κΈ WEEK5 Day 43 - ν΄μ¦ 리뷰 / implict list(best fit, realloc κ°μ μ½λ) (1) | 2024.02.20 |
---|---|
ν¬λνν€ μ κΈ WEEK5 Day42 - Counter λͺ¨λ / malloc lab ꡬν / ν μ λ ¬ (0) | 2024.02.20 |
ν¬λνν€ μ κΈ WEEK5 Day 39 - κ°μλ©λͺ¨λ¦¬ (0) | 2024.02.15 |
ν¬λνν€ μ κΈ WEEK5 Day 38 -BST (0) | 2024.02.15 |
ν¬λνν€ μ κΈ WEEK5 Day37 - Binary Tree (1) | 2024.02.14 |