budy system
๐๊ฐ๋
- ํฐ ๋ฒํผ๋ค์ ๋ฐ๋ณต์ ์ผ๋ก 2๋ฑ๋ถํ์ฌ, ์์ ๋ฒํผ๋ค์ ๋ง๋ค๋ฉฐ, ๊ฐ๋ฅํ ๋๋ง๋ค ์ธ์ ํ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํฉ์น๋ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ ๊ธฐ๋ฒ
๐๋ฒ๋ ๋ฉ๋ชจ๋ฆฌ ํ ๋น ํน์ง
- 2์ ๋ฉฑ์น : ๋ฉ๋ชจ๋ฆฌ์ ํ ๋น๊ณผ ํ์๋ฅผ 2์ ๋ฉฑ์น ๋จ์๋ก ์ํ
- ํฉ๋ณ : ์๋ก ์ธ์ ํ ๋ฒ๋๋ค์ด ์์ฝ๊ฒ ํฐ ์ธ๊ทธ๋จผํธ๋ก ๋ณํฉ
๐๋ฒ๋ ์์คํ ์๋ฆฌ
- ๋ฉ๋ชจ๋ฆฌ๋ฅผ 1/2๋ก ๊ณ์ ๋๋์ด ์์ฒญํ ๋ฉ๋ชจ๋ฆฌ๋ณด๋ค ํฐ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋นํ๋ค.
- ์๋ฅผ๋ค์ด 31๋ฅผ ์์ฒญํ๋ค๋ฉด 256์ 3๋ฒ๋๋์ด 32๋ฃฐ ํ ๋น
- 31์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ์ํ ๊ฒฝ์ฐ ์ธ์ ํ 32์ ํฉ์น๊ณ ๋ค์ 64kb, 128kb๋ฅผ ํฉ์ณ์ ์๋์ 256kb๋ก ๋ง๋ ๋ค.
๐๋ฒ๋ ๋ฉ๋ชจ๋ฆฌ ํ ๋น ์์
๐ก1024k์ ๋ฉ๋ชจ๋ฆฌ์์ ์์ฒญ์ ๋์ํ๋ ๊ณผ์
1) ํ๋ก๊ทธ๋จ A๊ฐ 64K ํฌ๊ธฐ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์์ฒญ
-> A ํ ๋น
2) ํ๋ก๊ทธ๋จ B๊ฐ 128K ํฌ๊ธฐ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์์ฒญ
-> B ํ ๋น
3) ํ๋ก๊ทธ๋จ C๊ฐ 64K ํฌ๊ธฐ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์์ฒญ
-> C ํ ๋น
4) ํ๋ก๊ทธ๋จ D๊ฐ 128K ํฌ๊ธฐ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์์ฒญ
-> D ํ ๋น
5) ํ๋ก๊ทธ๋จ C๊ฐ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํด์
-> C ํด์
6) ํ๋ก๊ทธ๋จ A๊ฐ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํด์
-> A ํด์ ํ 64+64 ํฉ์ณ์ 128 ๋ง๋ฌ
7) ํ๋ก๊ทธ๋จ B๊ฐ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํด์
-> B ํด์ ํ 128+128 ํฉ์ณ์ 256 ๋ง๋ฌ
8) ํ๋ก๊ทธ๋จ D๊ฐ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํด์
-> D ํด์ ํ ๋ชจ๋ ํฉ์ณ์ 1024 ๋ง๋ฌ
๐๋ฒ๋๋ฅผ ์ฐพ์์ฃผ๋ ๊ณผ์
- ํฌ๊ธฐ๊ฐ 128์ธ heap์ด ์๊ณ , ์ฒ์ ์ฌ๊ธฐ 32 ํฌ๊ธฐ์ ํ ๋น ์์ฒญ์ด ๋ค์ด์๋ค๊ณ ๊ฐ์ ํด๋ณด์
- ๊ฐ์ฉ ๋ธ๋ญ์ด ํฌ๊ธฐ๊ฐ 128์ง๋ฆฌ ํ๋๊ฐ ์์ผ๋ฏ๋ก ์ด ๋ธ๋ก์ ํ ๋น ํด์ค ๊ฒ์ด๋ค.
- ์ด๋, ๋ธ๋ก์ ํฌ๊ธฐ๊ฐ ํ์ํ ํฌ๊ธฐ์ ๋๋ฐฐ ์ด์์ด๋ฏ๋ก ๋ฐ์ผ๋ก ์๋ผ์ฃผ๋ ์์ ์ ์งํํ๋ค.
- ๋ฐ์ผ๋ก ์๋ผ์ฃผ๊ณ ๋๋ฉด ํ์ฌ ๋ธ๋ก์ ์ฌ์ด์ฆ๋ 64์ด๊ณ , bp์ ์ฌ์ด์ฆ๋ฅผ ๋ํ๋ฉด ๋ฒ๋์ bp๋ฅผ ๊ตฌํ ์ ์๋ค.
- ํ์ฌ ํฌ๊ธฐ๊ฐ ๋๋ฌด ์ปค์ ๋ฐ์ผ๋ก ์๋ผ์ฃผ๋ ์์ ์ ์งํ ์ค์ด๋ฏ๋ก, ๋ฒ๋๋ free list์ ์ถ๊ฐ๋๋ค.
- ์์ง ๋ธ๋ก์ ํฌ๊ธฐ๊ฐ ํ์ํ ํฌ๊ธฐ์ ๋ ๋ฐฐ ์ด์์ด๋ฏ๋ก ํ ๋ฒ ๋ ์๋ผ์ฃผ๊ณ ๋ ๋ค ํ ๋น์ ์งํํ๋ฉด ๊ฒฐ๊ณผ๋ ๋ค์๊ณผ ๊ฐ๋ค.
- ์ด์ ํ ๋น์ ๋ช๋ฒ ๋ ์งํํ๊ณ , ๋ฐํ๋ ๋ช๋ฒ ์งํํ ๊ฒฝ์ฐ๋ฅผ ์๊ฐ ํด๋ณด์.
- ์ฌ๊ธฐ์ 96๋ฒ์ ์๋ ๋ธ๋ก์ ๋ฐํํ๋ค๊ณ ๊ฐ์ ํ์.
- ์ด๋, ํ์ฌ bp์ ๋ธ๋ก์ ์ฌ์ด์ฆ๋ฅผ ์ด์ง์๋ก ๋ํ๋ด๋ฉด ๋ค์ ๊ทธ๋ฆผ๊ณผ ๊ฐ๋ค, ๋ฒ๋ ์์คํ ์์ ํต์ฌ์ ๋ฒ๋์ bp๋ ํ์ฌ ๋ธ๋ก์ bp์ ๋ฑ ์ฌ์ด์ฆ์์ 1์ ๊ฐ์ ๊ฐ๋ ์๋ฆฌ๋ง ๋ค๋ฅด๋ค๋ ์ ์ด๋ค. ๋ฐ๋ผ์ ํ์ฌ bp์ ์ฌ์ด์ฆ bit๋ 0 ์ด๋ฏ๋ก, ๋ฒ๋์ ์ฃผ์๋ ํ์ฌ bp์์ ์ฌ์ด์ฆ ์๋ฆฌ์ bit๋ง 1๋ก ๋ฐ๊ฟ์ฃผ๋ฉด, ์ฆ ํ์ฌ bp์์ size๋ฅผ ๋ํ๋ฉด ๊ตฌํ ์ ์๋ฐ.
- ๋ฒ๋๊ฐ free ๋ธ๋ก์ด๊ณ , ๋ฒ๋์ ํฌ๊ธฐ๊ฐ ํ์ฌ ๋ธ๋ก์ ํฌ๊ธฐ์ ๊ฐ๊ธฐ ๋๋ฌธ์ ์ฐ๊ฒฐ์ด ๊ฐ๋ฅํ ๊ฒ์ด๋ค.
- ์ด๋ฒ์๋ ์ฌ์ด์ฆ์ ์๋ฆฌ๊ฐ ๋นํธ 1์ด๊ธฐ ๋๋ฌธ์, ํ์ฌ bp์์ ์ฌ์ด์ฆ๋ฅผ ๋บด๋ฉด ๋ฒ๋์ ์ฃผ์๊ฐ ๋์ฌ ๊ฒ์ด๋ค.
- ๋ง์ฐฌ๊ฐ์ง๋ก ๋ฒ๋์ ํฌ๊ธฐ์ ํ์ฌ ๋ธ๋ก์ ํฌ๊ธฐ๊ฐ ๊ฐ๊ณ free ๋ธ๋ก์ด๊ธฐ ๋๋ฌธ์ ์ฐ๊ฒฐ์ด ๊ฐ๋ฅํ ๊ฒ์ด๋ค. ์ด๋ฒ์๋ ๋ฒ๋๊ฐ ๋๋ณด๋ค ์ฃผ์๊ฐ์ด ์๊ธฐ ๋๋ฌธ์, bp๊ฐ ๋ฒ๋์ bp๋ก ์ด๋ํ๋ค.
- ์ด๋ฒ์๋ ๋ง์ฐฌ๊ฐ์ง๋ก size ์๋ฆฌ์ bit๊ฐ 1์ด๊ธฐ ๋๋ฌธ์ buddy์ ์ฃผ์๋ bp์์ size๋ฅผ ๋บ ๊ฐ์ด ๋๋ค. ํ์ง๋ง ์ด๋ฒ์๋ buddy์ ํฌ๊ธฐ๋ ๋ค๋ฅด๊ณ , ์ด๋ฏธ ํ ๋น๋ block ์ด๋ฏ๋ก ๋ ์ด์ ์ฐ๊ฒฐ์ด ๋ถ๊ฐ๋ฅํ๋ค. ์ด๋ฌํ ์ํฉ์ด ๋ฐ์ํ๋ฉด ์ฐ๊ฒฐ์ ์ข ๋ฃํ๋ค.
- ๊ทธ๋ฆผ์ ๋ณด๋ฉด ์ ์ ์๋ฏ์ด buddy system์ ํ์ฌ block์ ์ผ์ชฝ์ 32 ํฌ๊ธฐ์ free block์ด ์์์๋ ๋ถ๊ตฌํ๊ณ ์ฐ๊ฒฐ์ ์งํํ์ง ์๋๋ค. ์ด๋ ๋ชจ๋ block๋ค์ ํฌ๊ธฐ๊ฐ 2^n ํํ๋ฅผ ์ ์งํด์ผ ํ๋ค๋ ์ ์ ์ถฉ์กฑ์ํค๊ธฐ ์ํด์์ด๋ค.
- ๋น์ฅ ์์ ๊ทธ๋ฆผ์์ ๋ง์ฝ ์ผ์ชฝ block๊ณผ ์ฐ๊ฒฐ์ ์งํํ๋ค๋ฉด ๊ทธ ๊ฒฐ๊ณผ ํฉ์ณ์ง block์ ํฌ๊ธฐ๋ ๋์ด์ 2^n์ ์ ์งํ์ง ๋ชปํ ๊ฒ์์ ์ ์ ์๋ค.
- ์ด๋ ๊ฒ block์ size ๊ฐ๊ณผ ์ฃผ์๊ฐ์ ํตํด buddy์ ์ ๋ณด๋ฅผ ์ ์ ์๋ค. ์ ์๊ฐ์ ํด๋ณด๋ฉด ์์์ ์งํํ๋ ๋ฐฉ์๋ค๊ณผ๋ ๋ฌ๋ฆฌ buddy system์์๋ block์ footer ์ ๋ณด๋ฅผ ์ฌ์ฉํ์ง ์๋๋ค๋ ๊ฒ์ ์ ์ ์๋ค.
'SWjungle > #malloc' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[malloc] segregated free list ๋ฐฉ์ - ๊ตฌํ (0) | 2023.09.13 |
---|---|
[malloc] Explicit Free List ๋ฐฉ์ - ๊ตฌํ (0) | 2023.09.12 |
[Malloc] Implicit Free List๋ฐฉ์-๊ตฌํ (1) | 2023.09.11 |
[malloc] ๋์ ๋ฉ๋ชจ๋ฆฌ ํ ๋น (0) | 2023.09.08 |