Computer Science
์ด์์ฒด์ ์ ๋ฉ๋ชจ๋ฆฌ ๊ด๋ฆฌ 2 - Dynamic Partitioning
3/19/2025


์์ ์ธ๊ธ๋ ๊ณ ์ ํํฐ์ ๋์ ๋จ์ ์ ๊ทน๋ณตํ๊ธฐ ์ํด, ๋์ ํํฐ์ ๋์ด ๊ณ ์๋์์ต๋๋ค.
Dynamic Partitioning
๊ณ ์ ํํฐ์ ๋์์๋ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฌ์ ์ ์ ์๋ ๋์ผํ๊ฑฐ๋, ๋์ผํ์ง ์์ ํฌ๊ธฐ์ ์์ญ๋ค๋ก ๊ตฌ๋ถํ์ต๋๋ค. ๋์ ํํฐ์ ๋์ ๋ฉ๋ชจ๋ฆฌ ํํฐ์ ์ ์ฌ์ ์ ์ ์ํ์ง ์๊ณ , ํ๋ก์ธ์ค์ ํ์์ ๋ฐ๋ผ ๋์ ์ผ๋ก ํ ๋น์ํค๋ ๋ฐฉ๋ฒ์ ๋๋ค.
๋์ ํํฐ์ ๋์์ ๊ฐ๊ฐ์ ํํฐ์ ์ 'ํํฐ์ ๋ฒํธ'์ '์์ญ์ ํฌ๊ธฐ'๋ก ํํ๋ฉ๋๋ค. ํ๋ก์ธ์ค๊ฐ ๋ฉ์ธ๋ฉ๋ชจ๋ฆฌ์ ํ ๋น๋ ๋, ์ ํํ ๊ทธ ํ๋ก์ธ์ค๊ฐ ํ์ํ ๋งํผ์ ํฌ๊ธฐ๋ง์ ํ ๋นํฉ๋๋ค.
External Fragmentation

์ ์์ ์์๋ ๋์ ํํฐ์ ๋ ๊ตฌ์กฐ์์ ํ๋ก์ธ์ค๋ค์ด ์์ฐจ์ ์ผ๋ก ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋น๋ฐ๋ ๋ชจ์ต์ ๋ณด์ฌ์ค๋๋ค. (b), (c), (d)์์ ๊ฐ ํ๋ก์ธ์ค๋ค์ ๊ณต๊ฐ์ ์์ฐจ์ ์ผ๋ก ๋ถ์ฌ๋ฐ์ต๋๋ค. ํ๋ ํ๋ก์ธ์ค 4๊ฐ ๋ค์ด๊ฐ๊ธฐ์๋, (d)์๋ ๋จ์ ๊ณต๊ฐ์ด ๋๋ฌด ์์ต๋๋ค. ํ๋ก์ธ์ค 4์ ์คํ์ ์ํด ๋ฉ๋ชจ๋ฆฌ์ ์ ํด ๊ณต๊ฐ์ ๋ง๋ค์ด์ผ ํฉ๋๋ค. ์ด ๋ ํ๋ก์ธ์ค 2๊ฐ I/O ๋ฑ์ ์ด์ ๋ก CPU๋ฅผ ์ ์ ํ ์ ์๋ ์ํฉ์ด ๋์ง ์๋๋ค๋ฉด, ์ด์์ฒด์ ๋ ํ๋ก์ธ์ค๋ฅผ ๋์คํฌ๋ก ์ ์ ์ฎ๊ฒจ๋๊ณ , ๊ทธ ์๋ฆฌ์ ํ๋ก์ธ์ค 4๋ฅผ ํ ๋นํฉ๋๋ค. ์ดํ ํ๋ก์ธ์ค 2๊ฐ ๋ค์ ์ํ๋ ์ ์๋ ์ํ๊ฐ ๋๋ค๋ฉด, ๋์ผํ ๊ณผ์ ์ ๊ฑฐ์ณ ํ๋ก์ธ์ค 1์ ๋์คํฌ๋ก ์ฎ๊ธฐ๊ณ ๊ทธ ์๋ฆฌ๋ฅผ ํ๋ก์ธ์ค 2์ ํ ๋นํฉ๋๋ค.
์ด ๊ณผ์ ์์ ๋ณผ ์ ์๋ ๊ฒ์ ๊ฐ๊ฐ์ ํ๋ก์ธ์ค๋ค์ด ์ฐจ์งํ ๊ณต๊ฐ ์ฌ์ด์ฌ์ด์ ์์ ์ ํด ๊ณต๊ฐ์ด ์๊ฒผ๋ค๋ ๊ฒ์ ๋๋ค. (h)์ ์ํฉ์์ ์ ํด ๊ณต๊ฐ์ ๋ชจ๋ ํฉ์น๋ฉด 16M ์ด์ง๋ง, ์ด๋ค์ด ๋ชจ๋ ๋ถ๋ฆฌ๋์ด ์์ผ๋ฏ๋ก 6M๋ณด๋ค ํฐ ํ๋ก์ธ์ค๊ฐ ๋ค์ด๊ฐ๊ธฐ ์ํด์๋ ๋ค๋ฅธ ํ๋ก์ธ์ค๋ฅผ ์ซ์๋ด์ผํฉ๋๋ค. ์ด๋ ๊ฒ ์ ํด ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ด ์ ์ ํํธํ๋๊ณ ํจ์จ์ฑ์ด ๋จ์ด์ง๋ ํ์์ ์ธ๋ถ ํํธํexternal fragmentation์ด๋ผ๊ณ ํฉ๋๋ค.
์ธ๋ถ ํํธํ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํ ๋ฐฉ๋ฒ์ผ๋ก๋ ์์ถcompaction์ด ์์ต๋๋ค. ์์ถ์ด๋ ์ด์์ฒด์ ๊ฐ ์ผ์ ํ ์ฃผ๊ธฐ๋ก ํ๋ก์ธ์ค๋ค์ ์ฐ์์ ์ธ ์์น๋ก ์ฎ๊ฒจ์, ์ ํด ๊ณต๊ฐ์ด ํ๋์ ๊ฑฐ๋ํ ๋ธ๋ก์ผ๋ก ์ ์ง๋๊ฒ ๋ง๋๋ ๋ฐฉ๋ฒ์ ๋๋ค. (h)์์ ์์ถ์ ์ํํ๋ฉด ํ๋จ์ 16MB์ ๊ฑฐ๋ํ ๋ธ๋ก์ด ํ๋ณด๋๋ฏ๋ก 6M ์ด์์ ํ๋ก์ธ์ค๋ ์ค์ํ ์์ด ํ ๋น๋ ์ ์์ต๋๋ค.
Placement Algorithm
ํ์ง๋ง ์์ถ์ ์๋นํ ์๊ฐ์ด ๊ฑธ๋ฆฌ๋ ์์ ์ ๋๋ค. ๋ฐ๋ผ์ ์ด์์ฒด์ ๋ ๋ฉ๋ชจ๋ฆฌ์ ์ ํด ๊ณต๊ฐ ์ค ์ด๋์ ํ๋ก์ธ์ค๋ฅผ ํ ๋นํด์ผํ ์ง๋ฅผ ๋ ์ ๊ฒฝ์จ์ผํฉ๋๋ค. Placement Algorithm์ ํ๋ก์ธ์ค๊ฐ ๋ค์ด๊ฐ ์ ์๋ ์ฌ๋ฌ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ด ์์ ๋, ์ด๋ค ๊ณต๊ฐ์ ํ ๋นํ ์ง๋ฅผ ๊ฒฐ์ ํ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค. ๋ํ์ ์ธ Placement Algorithm์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
1. Best-fit : ํ๋ก์ธ์ค์ ํฌ๊ธฐ์ ๊ฐ์ฅ ๋น์ทํ ํฌ๊ธฐ์ ์์ญ์ ์ ํ
2. First-fit : ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๊ฐ์ฅ ์์์ ํ์ํ๊ธฐ ์์ํ์ฌ ์ด์ฉ๊ฐ๋ฅํ ์ฒซ๋ฒ์งธ ์์ญ์ ์ ํ
3. Next-fit : ์ต๊ทผ์ ํ ๋น๋์๋ ์ฃผ์๋ถํฐ ํ์ํ๊ธฐ ์์ํ์ฌ ์ด์ฉ๊ฐ๋ฅํ ์ฒซ๋ฒ์งธ ์์ญ์ ์ ํ

์ ๊ทธ๋ฆผ์ ์ผ์ชฝ์ ์ํฉ์์ ์๋ก ๋ค๋ฅธ ์๊ณ ๋ฆฌ์ฆ์ ์ํด ํ ๋น๋ ์๋ก์ด ํ๋ก์ธ์ค์ ์์น๋ฅผ ๋ณด์ฌ์ค๋๋ค. First-fit์ 6MB์ ํํธ์, Best-fit์ 2MB์ ํํธ์, Next-fit์ 20MB์ ํํธ์ ๋ง๋ค์์ต๋๋ค.
์ฌ์ค ์ ์์น๋ ๊ธฐ์กด์ ํ๋ก์ธ์ค๊ฐ ์ด๋์ ํ ๋น๋์๋์ ์์กดํฉ๋๋ค. Next-fit์ ์์น๋ ์ํฉ์ ๋ฐ๋ผ ๋ณ๊ฒฝ๋ ์ ์๊ธฐ ๋๋ฌธ์ ๋๋ค. ์์น๋ง ๋ณด๊ณ ํ๋จํ๊ธฐ๋ ์ด๋ ค์ธ์ง๋ ๋ชจ๋ฆ ๋๋ค.
์ด์ ๋ํ ์ผ๋ฐ์ ์ธ ์ฐ๊ตฌ ๊ฒฐ๊ณผ๋ก๋, First-fit์ด ๊ตฌํ์ด ์ฌ์ธ ๋ฟ๋ง ์๋๋ผ ๊ฐ์ฅ ์ต์ ์ด๋ผ๋ ๊ฒ์ ๋๋ค. Next-fit์ First-fit๋ณด๋ค ์ด์ง ๋จ์ด์ง๋ ๊ฒฐ๊ณผ๋ฅผ ๋ณ๋๋ค๊ณ ํฉ๋๋ค. Best-fit์ ์ด๋ฆ๊ณผ ๋ง์ง ์๊ฒ, ๊ฐ์ฅ ์์ข์ ์ฑ๋ฅ์ ๋ณด์ ๋๋ค. Best-fit์ ํญ์ ๋ฉ๋ชจ๋ฆฌ์ ๊ฐ์ฅ ์์ ํํธ์ ๋ง๋๋ ๊ฒ์ ๋ณด์ฅํ๊ธฐ์, ๋ค๋ฅธ ๋ฐฉ์๋ณด๋ค ๋ ์ฆ์ ์์ถ์ด ํ์ํฉ๋๋ค.
๋ค์ ๊ธ์์๋ Relocation์ ๋ํด ์์๋ณด๊ฒ ์ต๋๋ค.
