์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
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 |
- Java
- ์ด์์ฒด์
- binary search
- IP ํ๋กํ ์ฝ
- Java๋ฒ์
- ์ ๋ขฐ์ ๋ฐ์ดํฐ ์ ์ก
- DP
- github
- Eclipse
- algorhtim
- java๋ฒ์ ๋ณ๊ฒฝ
- congestion control
- ํ๋ก์ธ์ค ๋๊ธฐํ
- Algorithm
- ์คํฐ๋
- SWEA
- ๋น ๋ฅธ ์ฌ์ ์ก
- ๋ฉ๋ชจ๋ฆฌ ๋ฐฐ์น ๊ธฐ๋ฒ
- ์๊ณ ๋ฆฌ์ฆ
- Linux
- ๋ฐฑ์ค
- ๋์ ํ๋ก๊ทธ๋๋ฐ
- VMware
- OS
- ํผ๋๋ฐฑ
- ๋ชจ์๋ฉด์
- C++
- ํ๊ณ
- oxboxes
- Floyd-Warshall
์ฒด๋ฑ๋ก๊ทธ
[์ด์์ฒด์ 3๊ธฐ] 5์ฃผ์ฐจ ์คํฐ๋ ์ ๋ฆฌ ๋ณธ๋ฌธ
๐น์ ๋ ์ฃผ์ ์ง์ vs ์๋ ์ฃผ์ ์ง์
์ ๋ ์ฃผ์
- ํ์ผ ๋๋ ๋๋ ํ ๋ฆฌ์ ์ ์ฒด ๊ฒฝ๋ก๋ฅผ ๋ํ๋
- ๋ฉ๋ชจ๋ฆฌ ํน์ ์์น๋ฅผ ์ง์ ์ฐธ์กฐํ๋ ๋ฐฉ์
- ๋ช ๋ น์ด ์คํ ์์น์ ๋ฌด๊ดํ๊ฒ ํญ์ ๋์ผํ ๋ฉ๋ชจ๋ฆฌ ์์น ๊ฐ๋ฆฌํด
- "C:\Users\Username\Documents\file.txt"๋ Windows ์ด์์ฒด์ ์์ ํ์ผ "file.txt"์ ๋ํ ์ ๋ ์ฃผ์
์ฅ์ : ์์ฑ ์ค์ธ ํ์ผ ์์น๊ฐ ๋ณ๊ฒฝ๋์ด๋ ์ํฅ๋ฐ์ง ์์
๋จ์ : ์ ์ฒด ์ฃผ์๋ฅผ ์์ฑํด์ผํ๋ฏ๋ก ๋ฒ๊ฑฐ๋ก์
์๋ ์ฃผ์
- ํ์ฌ ๋ช ๋ น์ด ์์น๋ฅผ ๊ธฐ์ค์ผ๋ก ๋ฉ๋ชจ๋ฆฌ ์์น๋ฅผ ์ฐธ์กฐํ๋ ๋ฐฉ์
- ๋ช
๋ น์ด ์คํ ์์น์ ๋ฐ๋ผ ์ฐธ์กฐํ๋ ๋ฉ๋ชจ๋ฆฌ ์์น๊ฐ ๋ฌ๋ผ์ง
์ฅ์ : ํ๋ก๊ทธ๋จ์ด ๋ฉ๋ชจ๋ฆฌ์ ์ด๋ ์์น๋ก๋ ์ด๋ ๊ฐ๋ฅ, ๋น๊ต์ ๊ฐ๊ฒฐํ ์์ฑ ๊ฐ๋ฅ
๋จ์ : ์ฐธ์กฐํ๋ ์์น๊ฐ ๋ช ๋ ์ด ์์น์ ์๋์ ์ด๊ธฐ ๋๋ฌธ์ ํ์ผ ์์น ๋ณ๊ฒฝ ์ ์ง์ ํ ์ฃผ์์ ์์ ํ์
๐น๋ด๋ถ ๋จํธํ(Internal Fragmentation)
๋ด๋ถ ๋จํธํ๋ ํ ๋น๋ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ๋นํด ํ๋ก์ธ์ค๊ฐ ์ฌ์ฉํ๋ ๋ฉ๋ชจ๋ฆฌ๊ฐ ์ ์ด์ ๋น ๊ณต๊ฐ์ด ๋ฐ์ํ๋ ํ์์ ๋งํ๋ค.
๋น ๊ณต๊ฐ์ ๋ค๋ฅธ ํ๋ก์ธ์ค์ ์ํด ์ฌ์ฉ๋ ์ ์์ด ๊ทธ๋๋ก ์ฌ์ฉ๋์ง ์์ ์ฑ ๋จ๊ฒจ์ง๋ค.
๐น์ธ๋ถ ๋จํธํ(External Fragmentation)
์ธ๋ถ ๋จํธํ๋ ๋ฉ๋ชจ๋ฆฌ ์์ ํ๋ก์ธ์ค๊ฐ ์ฌ์ฉํ ์ ์๋ ์ถฉ๋ถํ ํฌ๊ธฐ์ ๋ฉ๋ชจ๋ฆฌ๊ฐ ์กด์ฌํ๋, ๊ทธ ๋จ์ ๋ฉ๋ชจ๋ฆฌ์ ๊ณต๊ฐ๋ค์ด ๋น์ฐ์์ ์ผ๋ก ์กด์ฌํ์ฌ ํ๋ก์ธ์ค๋ฅผ ์ ์ฌํ ์ ์๋ ํ์์ ๋งํ๋ค.
๐น๋ฉ๋ชจ๋ฆฌ ๊ด๋ฆฌ(Memory Management)
๋ฉ๋ชจ๋ฆฌ ๊ด๋ฆฌ๋ ํ๋ก์ธ์ค๋ค์ ์ํด ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋น, ํ์, ๋ณดํธํ๋ ํ๋์ด๋ค.
๋ฉ๋ชจ๋ฆฌ ๊ด๋ฆฌ์๋ ๋ฉ๋ชจ๋ฆฌ์ ๊ด๋ จ๋ ์ฌ๋ฌ ๊ด๋ฆฌ ์ ์ฑ ์ ์๋ฆฝํ์ฌ ์ด์ ๋ฐ๋ผ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๊ด๋ฆฌํด์ผ ํ๋ค.
๋ฉ๋ชจ๋ฆฌ ๊ด๋ฆฌ ๊ธฐ๋ฒ ์ข ๋ฅ๋ ๋ค์๊ณผ ๊ฐ๋ค.
โช๏ธ ๋ฐ์ ๊ธฐ๋ฒ(When)
: ํ๋ก์ธ์ค๋ฅผ ๋์คํฌ์์ ๋ฉ๋ชจ๋ฆฌ๋ก ๋ฐ์ ํ ์๊ธฐ๋ฅผ ๊ฒฐ์ ํ๋ค.
โช๏ธ ๋ฐฐ์น ๊ธฐ๋ฒ(Where)
: ๋์คํฌ์์ ๋ฐ์ ํ ํ๋ก์ธ์ค๋ฅผ ๋ฉ๋ชจ๋ฆฌ ์ด๋ ์์น์ ์ ์ฅํ ๊ฒ์ธ์ง ๊ฒฐ์ ํ๋ค.
โช๏ธ ํ ๋น ๊ธฐ๋ฒ(How)
: ์คํํด์ผ ํ ํ๋ก์ธ์ค๋ฅผ ๋ฉ๋ชจ๋ฆฌ์ ์ด๋ค ๋ฐฉ๋ฒ์ผ๋ก ํ ๋นํ ๊ฒ์ธ์ง ๊ฒฐ์ ํ๋ค.
โช๏ธ ๊ต์ฒด ๊ธฐ๋ฒ(Who)
: ๋ฉ๋ชจ๋ฆฌ๊ฐ ์ถฉ๋ถํ์ง ์์ ๊ฒฝ์ฐ ํ์ฌ ๋ฉ๋ชจ๋ฆฌ์ ์ ์ฌ๋ ํ๋ก์ธ์ค ์ค ์ด๋ค ํ๋ก์ธ์ค๋ฅผ ์ ๊ฑฐํ ๊ฒ์ธ์ง ๊ฒฐ์ ํ๋ค.
๐น๋ฐ์ ๊ธฐ๋ฒ
๋ฐ์ ๊ธฐ๋ฒ์๋ ๋ค์ ๋ ๊ฐ์ง ๊ธฐ๋ฒ์ด ์๋ค.
์๊ตฌ ๋ฐ์ | ์คํ ์ค์ธ ํ๋ก๊ทธ๋จ์ด ํน์ ํ๋ก๊ทธ๋จ์ด๋ ๋ฐ์ดํฐ ๋ฑ์ ์ฐธ์กฐ๋ฅผ ์๊ตฌํ ๋ ์ ์ฌํ๋ ๋ฐฉ๋ฒ ์ฆ, ๋ฉ๋ชจ๋ฆฌ์ ์ฌ๋ผ๊ฐ์ผํ ๋ ์์ฒญํ๋ ๋ฐฉ์ |
์์ ๋ฐ์ | ์คํ ์ค์ธ ํ๋ก๊ทธ๋จ์ ์ํด ์ฐธ์กฐ๋ ํ๋ก๊ทธ๋จ์ด๋ ๋ฐ์ดํฐ ๋ฑ์ ๋ฏธ๋ฆฌ ์์ํ์ฌ ์ ์ฌํ๋ ๋ฐฉ๋ฒ ์ฆ, ์ฐธ์กฐ ๊ฐ๋ฅ์ฑ์ด ๋์ ํ๋ก๊ทธ๋จ์ ๋ฉ๋ชจ๋ฆฌ์ ๋ฏธ๋ฆฌ ์ฌ๋ฆฌ๋ ๋ฐฉ์ |
๐น๋ฉ๋ชจ๋ฆฌ ๋ฐฐ์น ๊ธฐ๋ฒ
๋ฉ๋ชจ๋ฆฌ ๋ฐฐ์น ๊ธฐ๋ฒ์๋ ์ต์ด ์ ํฉ, ์ต์ ์ ํฉ, ์ต์ ์ ํฉ์ด ์๋ค.
์ต์ด ์ ํฉ (First-Fit) |
- ํ๋ก๊ทธ๋จ์ด๋ ๋ฐ์ดํฐ๊ฐ ๋ค์ด๊ฐ ์ ์๋ ํฌ๊ธฐ์ ๋น ์์ญ ์ค ์ฒซ ๋ฒ์งธ ๋ถํ ์์ญ์ ๋ฐฐ์น์ํค๋ ๋ฐฉ๋ฒ - ๋ค๋ฅธ ๋ฐฐ์น ๋ฐฉ๋ฒ์ ๋นํด ๋น ๋ฆ - ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ ํ์ฉ๋ ์ ํ๋ ๊ฐ๋ฅ์ฑ ์์ |
์ต์ ์ ํฉ (Best-Fit) |
- ํ๋ก๊ทธ๋จ์ด๋ ๋ฐ์ดํฐ๊ฐ ๋ค์ด๊ฐ ์ ์๋ ํฌ๊ธฐ์ ๋น ์์ญ ์ค ๋จํธํ๋ฅผ ๊ฐ์ฅ ์ ๊ฒ ๋จ๊ธฐ๋ ๋ถํ ์์ญ์ ๋ฐฐ์น์ํค๋ ๋ฐฉ๋ฒ - ๋ฉ๋ชจ๋ฆฌ ๋จํธํ๊ฐ ๊ฐ์ฅ ์์ผ๋, ๊ทธ๋งํผ์ ํ์ ๋น์ฉ ๋ฐ์ |
์ต์
์ ํฉ (Worst-Fit) |
- ํ๋ก๊ทธ๋จ์ด๋ ๋ฐ์ดํฐ๊ฐ ๋ค์ด๊ฐ ์ ์๋ ํฌ๊ธฐ์ ๋น ์์ญ ์ค ๋จํธํ๋ฅผ ๊ฐ์ฅ ๋ง์ด ๋จ๊ธฐ๋ ๋ถํ ์์ญ์ ๋ฐฐ์น์ํค๋ ๋ฐฉ๋ฒ - ์ต์ ์ ํฉ(Best-Fit)๊ณผ ๋์ผํ๊ฒ ํ์ ๋น์ฉ ๋ฐ์ |
๐น๋ฉ๋ชจ๋ฆฌ ํ ๋น ๊ธฐ๋ฒ
๐น์ฐ์ ํ ๋น ๊ธฐ๋ฒ(Contiguous Memory Allocation)
: ๊ฐ ํ๋ก์ธ์ค์ ๊ตฌ์ฑ์์๊ฐ ๋ฉ๋ชจ๋ฆฌ์ ์ฐ์๋ ์ฃผ์๋ก ์ ์ฅ๋๋ ๋ฐฉ์
โช๏ธ ์ค๋ฒ๋ ์ด(Overlay) - ๋จ์ผ ํ๋ก๊ทธ๋๋ฐ
: ๋ณด์กฐ๊ธฐ์ต์ฅ์น์ ์ ์ฅ๋ ํ๋์ ํ๋ก๊ทธ๋จ์ ์ฌ๋ฌ ๊ฐ์ ์์ ์กฐ๊ฐ(๋ชจ๋ ๋จ์)์ผ๋ก ๋ถํ ํ ํ ํ์ํ ์กฐ๊ฐ์ ์ฐจ๋ก๋๋ก ์ฃผ๊ธฐ์ต์ฅ์น์ ํ ๋นํ๋ ๋ฐฉ์
: ์ฃผ๋ก ๋ฉ๋ชจ๋ฆฌ๊ฐ ์ ํ์ ์ธ ํ๊ฒฝ์์ ๋ณดํต ํฐ ํ๋ก๊ทธ๋จ์ ์คํํ ๋ ์ฌ์ฉ
์ค๋ฒ๋ ์ด ๊ณผ์
- ๋ณด์กฐ๊ธฐ์ต์ฅ์น์ ์ ์ฅ๋ ํ๋์ ํ๋ก๊ทธ๋จ์ ์ฌ๋ฌ ์กฐ๊ฐ์ผ๋ก ๋ถํ
- ํ๋ก๊ทธ๋จ์ ๋ถํ ํ๋ ์์ ์ ํ๋ก๊ทธ๋๋จธ๊ฐ ์ํํด์ผ ํ๋ฏ๋ก ์์คํ ์ด๋ ํ๋ก๊ทธ๋จ ๊ตฌ์กฐ์ ๋ํด ์์์ผ ํจ
- ์์ ์ด ํ์ํ ์กฐ๊ฐ๋ค์ ์ฃผ๊ธฐ์ต์ฅ์น์ ์ ์ฌ
- ์คํ ์ค์ ์ฃผ๊ธฐ์ต์ฅ์น๊ฐ ๊ฝ ์ฐฌ ๊ฒฝ์ฐ ํ์ ์๋ ์กฐ๊ฐ ์์ ์๋ก์ด ์กฐ๊ฐ์ผ๋ก ์ค์ฒฉํ์ฌ ๊ต์ฒด(์ค๋ฒ๋ ์ด ์ ํ, Overlay Swapping)
์ค๋ฒ๋ ์ด ์ฅ์
- ์ ํ๋ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์์ ํฐ ํ๋ก๊ทธ๋จ์ ์คํํ ์ ์์
- ์ค๋ฒ๋ ์ด ์ ํ์ ํตํด ๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ๋ ์ต์ ํ (์์ ๋ญ๋น ์ต์ํ)
์ค๋ฒ๋ ์ด ๋จ์
- ์ค๋ฒ๋ ์ด ์ ํ์ ๋ํ Overhead ↑
- ์ค๋ฒ๋ ์ด ์ ํ ๊ณผ์ ์์ ์ฑ๋ฅ ์ ํ ๋ฐ์ (์์คํ ์ฒ๋ฆฌ ์๋๋ ์๋ต ์๊ฐ ๋ฑ)
โช๏ธ ์ค์ํ(Swapping) - ๋จ์ผ ํ๋ก๊ทธ๋๋ฐ
: ํ๋์ ํ๋ก๊ทธ๋จ ์ ์ฒด๋ฅผ ์ฃผ๊ธฐ์ต์ฅ์น์ ํ ๋นํ์ฌ ํ์์ ๋ฐ๋ผ ๋ค๋ฅธ ํ๋ก๊ทธ๋จ๊ณผ ๊ต์ฒดํ๋ ๋ฐฉ๋ฒ
: ์ฆ, ํ๋ก๊ทธ๋จ์ ๋ถํ ํ๋ ๊ฒ์ด ์๋ ํ๋ก๊ทธ๋จ ๋จ์๋ก ๊ต์ฒด
์ค์ํ ๊ณผ์
- ๋ฉ๋ชจ๋ฆฌ ๋ถ์กฑ ํ์ ๋ฐ์
- ์ด๋ค ํ๋ก์ธ์ค๋ฅผ ์ค์ํํ์ฌ ๋ณด์กฐ๊ธฐ์ต์ฅ์น๋ก ์ฎ๊ธธ์ง ๊ฒฐ์
- Swap-Out: ์ฃผ๊ธฐ์ต์ฅ์น → ๋ณด์กฐ๊ธฐ์ต์ฅ์น
- Swap-In: ๋ณด์กฐ๊ธฐ์ต์ฅ์น → ์ฃผ๊ธฐ์ต์ฅ์น
- ํ๋ก์ธ์ค ์ฌ๊ฐ: ์ค์ํ๋ ํ๋ก์ธ์ค๊ฐ ๋ชจ๋ ๋ฉ๋ชจ๋ฆฌ๋ก ๋ก๋๋๋ฉด ํด๋น ํ๋ก์ธ์ค ๋ค์ ์คํ
์ค์ํ ์ฅ์
- ํ๋ก์ธ์ค๋ฅผ ๋ณด์กฐ๊ธฐ์ต์ฅ์น๋ก Swap-Out ํจ์ผ๋ก์จ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํจ์จ์ ์ผ๋ก ํ์ฉ ๊ฐ๋ฅ
- ์ ํ๋ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์์ ๋ค์์ ํ๋ก์ธ์ค ์คํ ๊ฐ๋ฅ
์ค์ํ ๋จ์
- ํ๋์ ํ๋ก๊ทธ๋จ๋ง ์ฌ๋ผ๊ฐ ์ ์์ → ๊ฐ์ : ๋ค์ค ๋ถํ ํ ๋น ๊ธฐ๋ฒ(๋ค์ค ํ๋ก๊ทธ๋๋ฐ ๊ธฐ๋ฒ)
- ์ค์ํ์ ๋ฐ๋ฅธ Overhead ๋ฐ์
- ์ค์ํ์ด ๋น๋ฒํ๊ฒ ๋ฐ์ํ ๊ฒฝ์ฐ ํ๋ก์ธ์ค ์คํ ์๋ ์ ํ
โช๏ธ ๊ณ ์ ๋ถํ (Fixed Partitioning) - ๋ค์ค ํ๋ก๊ทธ๋๋ฐ
: ์์คํ ์์ฑ ์ ์ฃผ๊ธฐ์ต์ฅ์น๊ฐ ์ด๋ฏธ ํน์ ํฌ๊ธฐ๋ก ๊ณ ์ ๋ ํํฐ์ ๋ค๋ก ์๊ตฌ์ ์ธ ๋ถํ ์ ํ๊ณ ๊ฐ ๋ถํ ์ ํ๋์ ํ๋ก์ธ์ค๋ฅผ ์ ์ฌํ๋ ๋ฐฉ์
๊ณ ์ ๋ถํ ์ข ๋ฅ
- ๊ท ๋ฑ ๋ถํ : ๋ชจ๋ ํํฐ์ ์ ํฌ๊ธฐ๊ฐ ์ผ์ ํจ
- ํ๋ก๊ทธ๋จ์ ํฌ๊ธฐ๊ฐ ํํฐ์
์ ํฌ๊ธฐ๋ณด๋ค ํด ์ ์์
- ํด๊ฒฐ ๋ฐฉ๋ฒ) ์ค๋ฒ๋ ์ด(Overlay), ์ค์ํ(Swapping) - ๋ด๋ถ ๋จํธํ ๋ฌธ์ ๋ฐ์
- ๋งค์ฐ ์์ ํฌ๊ธฐ์ ํ๋ก์ธ์ค๋ผ๋ ์ ์ฒด ํํฐ์ ์ ์ฐจ์งํ๊ธฐ ๋๋ฌธ
- ๋น๊ท ๋ฑ ๋ถํ : ๋ชจ๋ ํํฐ์ ์ ํฌ๊ธฐ๊ฐ ์ผ์ ํ์ง ์์
๊ณ ์ ๋ถํ ์ฅ์
- ๊ตฌํ์ด ๊ฐ๋จ
- ์ด์์ฒด์ Overhead๊ฐ ๊ฑฐ์ ์์ (์์คํ ์์ฑ ์ ์ฃผ๊ธฐ์ต์ฅ์น๊ฐ ๋ฏธ๋ฆฌ ๋ถํ ๋จ)
๊ณ ์ ๋ถํ ๋จ์
- ํํฐ์ ์์ ๋ฐ๋ผ ์ต๋ ํ์ฑํ๋๋ ํ๋ก์ธ์ค ์๊ฐ ์ ํ๋จ
- ์ํ ๊ฐ๋ฅํ ํ๋ก์ธ์ค ์ต๋ ํฌ๊ธฐ ๊ณ ์ → ๋ด๋ถ ๋ฐ ์ธ๋ถ ๋จํธํ ๋ฌธ์ ๋ฐ์
- ๋ด๋ถ ๋จํธํ ๋ฌธ์ ๋ฐ์: ์์ ํ๋ก์ธ์ค ์ ์ฌ ์ ํํฐ์ ์ ๋น ๊ณต๊ฐ ๋ญ๋น
- ์ธ๋ถ ๋จํธํ ๋ฌธ์ ๋ฐ์: ํด๋น ํ๋ก์ธ์ค ๋ฉ๋ชจ๋ฆฌ์ ๋ํ์ฌ ์ ์ฒด ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ์ถฉ๋ถํ๋, ํด๋น ํ๋ก์ธ์ค๋ฅผ ์ ์ฌํ ์ ์๋ ํํฐ์ ์ด ์์
โช๏ธ ๊ฐ๋ณ ๋ถํ (Variable Partitioning) - ๋ค์ค ํ๋ก๊ทธ๋๋ฐ
: ํ๋ก์ธ์ค๊ฐ ์ฃผ๊ธฐ์ต์ฅ์น๋ก ์ ์ฌ๋ ๋ ์ ํํ ํ์ํ ํฌ๊ธฐ๋งํผ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋นํ๋ ๋ฐฉ์
๊ฐ๋ณ ๋ถํ ์ฅ์
- ๋ด๋ถ ๋จํธํ ๋ฌธ์ ๋ฐ์ํ์ง ์์ (ํ๋ก์ธ์ค์ ํฌ๊ธฐ์ ๋ฑ ๋ง๊ฒ ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ ์ฌ์ฉํ๊ธฐ ๋๋ฌธ)
๊ฐ๋ณ ๋ถํ ๋จ์
- ์ธ๋ถ ๋จํธํ ๋ฌธ์ ๋ฐ์
- ๋ฉ๋ชจ๋ฆฌ ํ ๋น ๋ฐ ํด์ ๋ก ์ธํด ๋ฉ๋ชจ๋ฆฌ ๊ณต๊ฐ์ด ์กฐ๊ฐ๋๊ณ , ์ด ์กฐ๊ฐ๋ ์์ ๊ณต๊ฐ๋ค์ ํฌ๊ธฐ๋ณด๋ค ๋ฉ๋ชจ๋ฆฌ ํฌ๊ธฐ๊ฐ ํฐ ์๋ก์ด ํ๋ก์ธ์ค๊ฐ ๋ค์ด์์ ๋ ํฌ๊ธฐ๊ฐ ๋ง์ง ์์ ์ฌ์ฉ๋์ง ๋ชปํ๋ ๊ฒฝ์ฐ
- ๋ฉ๋ชจ๋ฆฌ ํตํฉ(Coalescing) ๋๋ ๋ฉ๋ชจ๋ฆฌ ์์ถ(Compaction) ๊ธฐ๋ฒ์ ํตํด ํด๊ฒฐ ๊ฐ๋ฅ
๐น๋ถ์ฐ์/๋ถ์ฐ ํ ๋น ๊ธฐ๋ฒ(Non-contiguous Memory Allocation)
: ํ๋์ ํ๋ก์ธ์ค๊ฐ ๋ฉ๋ชจ๋ฆฌ์ ์ฌ๋ฌ ์์ญ์ ๋ถ์ฐ๋์ด ํ ๋น๋ ์ ์๋ ๋ฐฉ์
: ์ฃผ๋ก ๊ฐ์๋ฉ๋ชจ๋ฆฌ์์ ์ฌ์ฉ
โช๏ธ ํ์ด์ง(Paging) - ๊ณ ์ ๋ถํ
: ํ์ด์ง์ ๊ฐ์ ๋ฉ๋ชจ๋ฆฌ(logical, ๊ฐ์ ์ฃผ์ ๊ณต๊ฐ)๋ฅผ ๊ณ ์ ํฌ๊ธฐ์ ๋ธ๋ก์ธ 'ํ์ด์ง' ๋จ์๋ก ๋๋๊ณ , ๋ฌผ๋ฆฌ ๋ฉ๋ชจ๋ฆฌ(physical, ์ค์ ๊ธฐ์ต ๊ณต๊ฐ)๋ฅผ ํ์ด์ง์ ๊ฐ์ ํฌ๊ธฐ์ ํ๋ ์์ผ๋ก ๋๋์ด ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๊ด๋ฆฌํ๋ ๊ฒ์ ๋งํ๋ค.
- ํ์ด์ง(Page): ๊ฐ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ผ์ ํ ํฌ๊ธฐ๋ก ๋๋ ๋ธ๋ก
- ํ๋ ์(Frame): ๋ฌผ๋ฆฌ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ผ์ ํ ํฌ๊ธฐ๋ก ๋๋ ๋ธ๋ก
- ํ์ด์ง ํ ์ด๋ธ(Page Table): ํ๋ก์ธ์ค์ ํ์ด์ง ๋ฒํธ์ ๋ฌผ๋ฆฌ ๋ฉ๋ชจ๋ฆฌ(frame)์ ์์ ์ฃผ์(offset)์ ์์ผ๋ก ์ด๋ฃจ์ด์ง
์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ๋ฌผ๋ฆฌ ์ฃผ์ ๊ณต๊ฐ์ด ์ฐ์์ ์ผ ํ์๋ ์๋ค. (๋ถ์ฐ ํ ๋น ๊ธฐ๋ฒ ํน์ง)
โช๏ธ ์ธ๊ทธ๋ฉํ ์ด์ (Segmentation) - ๊ฐ๋ณ ๋ถํ
: ์ธ๊ทธ๋ฉํ ์ด์ ์ ๊ฐ์ ์ฃผ์ ๊ณต๊ฐ์ ๋ ผ๋ฆฌ์ ์ธ ๋จ์์ธ ์ธ๊ทธ๋จผํธ๋ก ๋๋์ด ๊ด๋ฆฌํ๋ค.
๊ฐ ์ธ๊ทธ๋จผํธ๋ ๋ ผ๋ฆฌ์ ์ธ ์๋ฏธ๋ฅผ ๊ฐ์ง ํ๋ก๊ทธ๋จ์ ๋ถ๋ถ์ ๋ํ๋ด๋ฉฐ ์๋ก ๋ค๋ฅธ ํฌ๊ธฐ๋ฅผ ๊ฐ์ง ์ ์๋ค.
- ์ธ๊ทธ๋ฉํ ์ด์ ํ ์ด๋ธ(Segmentation Table): ์ธ๊ทธ๋ฉํ ์ด์ ํฌ๊ธฐ(limit)์ ๋ฌผ๋ฆฌ ๋ฉ๋ชจ๋ฆฌ์ ์์ ์ฃผ์(address, offset)๋ก ๊ตฌ์ฑ
์ธ๊ทธ๋ฉํ ์ด์ ๊ธฐ๋ฒ๋ ๋ง์ฐฌ๊ฐ์ง๋ก ๋ฌผ๋ฆฌ ์ฃผ์ ๊ณต๊ฐ์ด ์ฐ์์ ์ผ ํ์๋ ์๋ค. (๋ถ์ฐ ํ ๋น ๊ธฐ๋ฒ ํน์ง)
๐น์ธ๋ถ ๋จํธํ ํด๊ฒฐ ๋ฐฉ๋ฒ
โช๏ธ ๋ฉ๋ชจ๋ฆฌ ํตํฉ (Coalescing)
: ์ธ์ ํ ๋จํธํ ์์ญ์ ์ฐพ์๋ด์ด ํ๋๋ก ํตํฉํ๋ ๊ธฐ๋ฒ
: ํ๋ก๊ทธ๋จ ์ฌ๋ฐฐ์น ํ์ X
โช๏ธ ๋ฉ๋ชจ๋ฆฌ ์์ถ (Compaction)
: ๋ฉ๋ชจ๋ฆฌ์ ๋ชจ๋ ๋จํธํ ์์ญ์ ํ๋๋ก ์์ถํ๋ ๊ธฐ๋ฒ
: ํ๋ก๊ทธ๋จ ์ฌ๋ฐฐ์น ํ์ O
โช๏ธ ๋ฒ๋ ์์คํ / ๋ฒ๋ ๋ฉ๋ชจ๋ฆฌ ํ ๋น (Buddy System/Buddy Memory Allocation)
: ์์ฒญํ ํ๋ก์ธ์ค ํฌ๊ธฐ์ ๊ฐ์ฅ ์๋ง์ ํฌ๊ธฐ๋ฅผ ํ ๋นํ๊ธฐ ์ํด ๋ฉ๋ชจ๋ฆฌ๋ฅผ 2^n์ ํฌ๊ธฐ๋ก ๋ถํ ํ์ฌ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋นํ๋ ๊ธฐ๋ฒ
- ๋ฉ๋ชจ๋ฆฌ๋ฅผ 1/2๋ก ๊ณ์ ๋ถํ ํ์ฌ ์์ฒญํ ๋ฉ๋ชจ๋ฆฌ๋ณด๋ค ํฐ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ ๋นํ๋ค.
- ๋ง์ฝ, 31KB๋ฅผ ์์ฒญํ์ ๋, 256KB๋ฅผ 3๋ฒ ๋ถํ ํ์ฌ 32KB๋ฅผ ํ ๋นํ๋ค.
- 31KB์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ํ์ํ ๊ฒฝ์ฐ, ์ธ์ ํ 32KB์ ํฉ์น๊ณ ๋ค์ 64KB, 128KB๋ฅผ ํฉ์ณ ์๋์ 256KB๋ก ๋ง๋ ๋ค.
๐น๊ฐ์ ๋ฉ๋ชจ๋ฆฌ(Virtual Memory)
๊ฐ์ ๋ฉ๋ชจ๋ฆฌ(Virtual Memory)๋ ์ปดํจํฐ ์์คํ ์์ ์ฌ์ฉํ๋ ๋ฉ๋ชจ๋ฆฌ ๊ด๋ฆฌ ๊ธฐ๋ฒ ์ค ํ๋๋ก, ํ๋ก๊ทธ๋จ์๊ฒ ์ค์ ๋ฉ๋ชจ๋ฆฌ ์ฉ๋์ ์ด๊ณผํ๋ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์ฌ์ฉํ๋ ๊ฒ์ฒ๋ผ ๋๋ผ๊ฒ ํด์ฃผ๋ ๊ธฐ์ ์ด๋ค. ์ด ๊ฐ๋ ์ ๋ฌผ๋ฆฌ์ ๋ฉ๋ชจ๋ฆฌ์ ๋ณด์กฐ ์ ์ฅ ์ฅ์น(e.g, SSD, ํ๋ ๋๋ผ์ด๋ธ ๋ฑ)๋ฅผ ํจ๊ป ์ฌ์ฉํ์ฌ ์์คํ ์ด ๋ ๋ง์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๊ฐ์ง ๊ฒ์ฒ๋ผ ์๋ํ๋๋ก ๋์์ค๋ค.
๊ฐ์ ๋ฉ๋ชจ๋ฆฌ๋ ํ์ด์ง(Paging)๊ณผ ์ธ๊ทธ๋ฉํ ์ด์ (Segmentation) ๊ฐ์ ๊ธฐ๋ฒ์ ์ฌ์ฉํ์ฌ ๊ตฌํ๋๋ค.
๐น๊ฐ์ ์ฃผ์์ ๋ฌผ๋ฆฌ ์ฃผ์
๊ฐ์ ์ฃผ์(Virtual Address)์ ๋ฌผ๋ฆฌ ์ฃผ์(Physical Address)๋ ์ปดํจํฐ ์์คํ ์์ ๋ฉ๋ชจ๋ฆฌ ์ฃผ์๋ฅผ ์ฐธ์กฐํ๋ ๋ ๊ฐ์ง ๋ฐฉ์์ด๋ค. ์ด ๋ ์ฃผ์ ์ฒด๊ณ๋ ๊ฐ์ ๋ฉ๋ชจ๋ฆฌ ์์คํ ์์ ํนํ ์ค์ํ ์ญํ ์ ํ๋ค.
โช๏ธ ๊ฐ์ ์ฃผ์(Virtual Address)
: ๋ฌผ๋ฆฌ์ ๋ฉ๋ชจ๋ฆฌ ํฌ๊ธฐ์๋ ๋ ๋ฆฝ์ ์ด๋ฉฐ ํ๋ก์ธ์ค๊ฐ ๋ฉ๋ชจ๋ฆฌ ์ ๊ทผ ์ ์ฌ์ฉํ๋ ์ฃผ์์ด๋ค.
: ํ๋ก๊ทธ๋จ ์คํ ์, ์ด์์ฒด์ ๋ ๊ฐ ํ๋ก์ธ์ค์๊ฒ ๋ ๋ฆฝ๋ ๊ฐ์ ์ฃผ์ ๊ณต๊ฐ์ ์ ๊ณตํ๋ค.
: ๊ฐ์ ์ฃผ์ ๊ณต๊ฐ์ 'ํ์ด์ง'๋ผ๊ณ ๋ถ๋ฆฌ๋ ๋ธ๋ก์ผ๋ก ๋๋๋ค.
โช๏ธ ๋ฌผ๋ฆฌ ์ฃผ์(Physical Address)
: ์ค์ ๋ฉ๋ชจ๋ฆฌ ํ๋์จ์ด(RAM)์ ์กด์ฌํ๋ ์ฃผ์์ด๋ค.
โช๏ธ ๊ฐ์ ์ฃผ์๋ฅผ ๋ฌผ๋ฆฌ ์ฃผ์๋ก ๋ณํํ๋ ๊ณผ์ (ํ์ด์ง ๊ธฐ๋ฒ)
: ์ด์์ฒด์ ๋ฉ๋ชจ๋ฆฌ ๊ด๋ฆฌ ๋จ์๋ ๊ฐ์ ์ฃผ์๋ฅผ ๋ฌผ๋ฆฌ ์ฃผ์๋ก ๋ณํํ๋ ๊ณผ์ ์ ํตํด ์ค์ ๋ฉ๋ชจ๋ฆฌ์ ์ ๊ทผํ๋ค.
1. ๊ฐ์ ์ฃผ์ ์์ฑ
- ํ๋ก์ธ์ค๊ฐ ๋ฉ๋ชจ๋ฆฌ ์ ๊ทผ์ ์ํด ์์ฑํ ์ฃผ์๋ฅผ ๊ฐ์์ฃผ์๋ผ๊ณ ํจ
2. ํ์ด์ง ๋ฒํธ ์ถ์ถ
- ๊ฐ์ ์ฃผ์์์ ํ์ด์ง ๋ฒํธ ์ถ์ถ
- ํ์ด์ง ๋ฒํธ๋ ํ์ด์ง ํ ์ด๋ธ์์ ๋งคํ ์ ๋ณด๋ฅผ ์ฐพ๋ ๋ฐ ์ฌ์ฉ
3. ํ์ด์ง ํ ์ด๋ธ ์กฐํ
- ํ์ด์ง ๋ฒํธ๋ฅผ ์ฌ์ฉํด ํ์ด์ง ํ ์ด๋ธ ์กฐํ
- ํ์ด์ง ํ ์ด๋ธ์ ๊ฐ์ ์ฃผ์ ๊ณต๊ฐ์์ ๋ฌผ๋ฆฌ ์ฃผ์ ๊ณต๊ฐ์ผ๋ก์ ๋งคํ ์ ๋ณด๋ฅผ ๊ฐ์ง๊ณ ์์
4. ํ์ด์ง ์คํ์ ์ถ์ถ
- ๊ฐ์ ์ฃผ์์์ ํ์ด์ง ์คํ์ ์ถ์ถ
- ํ์ด์ง ์คํ์ ์ ํ์ด์ง ์ฒ์ ์์น์์ ํด๋น ์ฃผ์๊น์ง์ ๊ฑฐ๋ฆฌ๋ฅผ ๋ํ๋
- ํ์ด์ง ์คํ์ ์ ๋ฌผ๋ฆฌ ๋ฉ๋ชจ๋ฆฌ ๋ด์์์ ์ค์ ์ฃผ์ ๊ณ์ฐ์ ์ฌ์ฉ๋จ
5. ๋ฌผ๋ฆฌ ์ฃผ์ ๊ณ์ฐ
- ํ์ด์ง ํ ์ด๋ธ์์ ์กฐํํ ํ๋ ์ ๋ฒํธ์ ํ์ด์ง ์คํ์ ์ ๊ฒฐํฉํ์ฌ ๋ฌผ๋ฆฌ ์ฃผ์ ๊ณ์ฐ
6. ๋ฉ๋ชจ๋ฆฌ ์ ๊ทผ
- ๊ณ์ฐ๋ ๋ฌผ๋ฆฌ ์ฃผ์๋ฅผ ์ฌ์ฉํด ๋ฉ๋ชจ๋ฆฌ์ ์ ๊ทผํ๊ณ ๋ฐ์ดํฐ๋ฅผ ์ฝ๊ฑฐ๋ ์ฐ๋ ์์ ์ ์ํ
โช๏ธ TLB(Translation Lookaside Buffer)
: ๊ฐ์ ์ฃผ์์ ํด๋นํ๋ ๋ฌผ๋ฆฌ ์ฃผ์ ์ฌ์ด์ ๋งคํ ์ ๋ณด๋ฅผ ์์๋ก ์ ์ฅํ๋ ์์ ๊ณ ์ ์บ์
TLB ์ฌ์ฉ ์ด์
: ๊ฐ์ ๋ฉ๋ชจ๋ฆฌ ์์คํ ์์ ๊ฐ์ ์ฃผ์๋ฅผ ๋ฌผ๋ฆฌ ์ฃผ์๋ก ๋ณํํ ๋ ํ์ด์ง ํ ์ด๋ธ์ ํตํด ์ด๋ฃจ์ด์ง๋๋ฐ, ์ด๋ ์ ๊ทผํ๋ ๋ฐ ์๊ฐ์ด ์ค๋ ๊ฑธ๋ฆด ์ ์๋ค. ๋ฐ๋ผ์ ์ด๋ฌํ ๋๋ฆฐ ์ ๊ทผ ์๊ฐ์ ์ค์ด๊ธฐ ์ํด TLB๊ฐ ์ฌ์ฉ๋๋ค.
TLB ์ฌ์ฉ ์๋ฆฌ
: TLB๋ ๊ฐ์ ์ฃผ์๋ฅผ ์ ๋ ฅ ๋ฐ์ ๋ฌผ๋ฆฌ ์ฃผ์๋ฅผ ์ถ๋ ฅ์ผ๋ก ๋ฐํํ๋ค.
: ๋ง์ฝ TLB์ ๊ฐ์ ์ฃผ์์ ๋งคํ ์ ๋ณด๊ฐ ์กด์ฌํ์ง ์์ ๊ฒฝ์ฐ, ์ด ์ ๋ณด๋ฅผ ํ์ด์ง ํ ์ด๋ธ์์ ๊ฐ์ ธ์ TLB์ ์ ์ฅํ๋ค.
TLB ์ฅ์
: ๊ฐ์ ์ฃผ์์ ๋ฌผ๋ฆฌ ์ฃผ์ ๊ฐ์ ๋ณํ ์๋๋ฅผ ๋์
: ๊ฐ์ ๋ฉ๋ชจ๋ฆฌ ์์คํ ์ฑ๋ฅ ํฅ์
TLB ๋จ์
: TLB ํฌ๊ธฐ๊ฐ ์ ํ์ ์ด๊ธฐ ๋๋ฌธ์ ๋งคํ ์ ๋ณด๊ฐ TLB์ ์บ์๋ ์ ์๋ ํ๊ณ๊ฐ ์์ (TLB miss)
: TLB miss๊ฐ ๋ฐ์ํ๋ฉด ํ์ด์ง ํ ์ด๋ธ์ ์ง์ ์ ๊ทผํ์ฌ ๋งคํ ์ ๋ณด๋ฅผ ์ฐพ์์์ผํ๋ฏ๋ก ์ถ๊ฐ ์ง์ฐ ๋ฐ์ ๊ฐ๋ฅ
๐นํ์ด์ง ๊ต์ฒด ๊ธฐ๋ฒ
ํ์ด์ง ๊ต์ฒด ๊ธฐ๋ฒ์ด๋ ์ฃผ๊ธฐ์ต์ฅ์น์ ์๋ ํ๋ก์ธ์ค ์ค ์ด๋ค ํ๋ก์ธ์ค๋ฅผ ์ ๊ฑฐํ ๊ฒ์ธ์ง๋ฅผ ๊ฒฐ์ ํ๋ ๊ธฐ๋ฒ์ด๋ค.
*. ํ์ด์ง ๋ถ์ฌ(Page fault): ์ฃผ๊ธฐ์ต์ฅ์น์ ์ ์ฌ๋ ํ์ด์ง ์ค ์ฌ์ฉ ํ์ด์ง๊ฐ ์์ ๋๋ฅผ ์๋ฏธํ๋ค.
ํ์ด์ง ๋ถ์ฌ๊ฐ ๋ฐ์ํ๊ฒ ๋๋ฉด, ์ํ๋ ํ์ด์ง๋ฅผ ๋ณด์กฐ๊ธฐ์ต์ฅ์น์์ ๊ฐ์ ธ์ ์ ์ฌํด์ผ ํ๋๋ฐ ์ฃผ๊ธฐ์ต์ฅ์น๊ฐ ๊ฝ ์ฐจ์ ํ์ด์ง๋ฅผ ์ ์ฌํ ๊ณต๊ฐ์ด ๋ถ์กฑํ๋ค๋ฉด ์ฃผ๊ธฐ์ต์ฅ์น์ ์กด์ฌํ๋ ํ์ด์ง์ ์ํ๋ ํ์ด์ง๋ฅผ ๊ต์ฒดํด์ผํ๋ค.
์ด๋ ํ์ด์ง ๋ถ์ฌ๋ฅผ ์ต์ํํ๊ธฐ ์ํด ์๊ตฌ ํ์ด์ง(Demand Paging)์ด๋ผ๋ ์ ๋ต์ ์ํํ๋ค.
์๊ตฌ ํ์ด์ง ์ํ ๊ณผ์
1. ํ๋ก๊ทธ๋จ ์คํ ๋ฐ ํ์ด์ง ํ ์ด๋ธ ์ด๊ธฐํ
- ํ์ด์ง ํ ์ด๋ธ์ ๊ฐ ํญ๋ชฉ์ ํด๋น ํ์ด์ง๊ฐ ๋ฉ๋ชจ๋ฆฌ์ ์กด์ฌํ๋์ง, ์กด์ฌํ๋ค๋ฉด ์ด๋์ ์๋์ง๋ฅผ ๋ํ๋ด๋ ์ ๋ณด๋ฅผ ํฌํจ
- ํ์ด์ง ํ ์ด๋ธ์ ์๋ ํ์ด์ง๋ ์ค์ ๋ก ๋ฉ๋ชจ๋ฆฌ์ ๋ก๋๋์ง ์์ ์ํ
2. ํ์ด์ง ์์ฒญ
- ํ๋ก์ธ์ค๊ฐ ํน์ ํ์ด์ง์ ์ ๊ทผํ๋ ค๊ณ ํ ๋, ๋จผ์ ํ์ด์ง ํ ์ด๋ธ์ ์ฐธ์กฐํ์ฌ ํด๋น ํ์ด์ง๊ฐ ๋ฉ๋ชจ๋ฆฌ์ ์๋์ง ํ์ธ
- ํ์ด์ง๊ฐ ๋ฉ๋ชจ๋ฆฌ์ ์๋ค๋ฉด ํ๋ก์ธ์ค๋ ๊ทธ ํ์ด์ง์ ์ ๊ทผํ์ฌ ์์ ์ํ
3. ํ์ด์ง ๋ถ์ฌ
- ๋ง์ฝ ์์ฒญํ ํ์ด์ง๊ฐ ๋ฉ๋ชจ๋ฆฌ์ ์๋ค๋ฉด ํ์ด์ง ๋ถ์ฌ ๋ฐ์
- ์ด๋ ์ด์์ฒด์ ๋ ํด๋น ํ์ด์ง๋ฅผ ๋์คํฌ์์ ์ฐพ์ ๋ฉ๋ชจ๋ฆฌ๋ก ๋ก๋
- ํ์ด์ง ๋ก๋ ํ ํ์ด์ง ํ ์ด๋ธ์ ์ ๋ฐ์ดํธํ์ฌ ํด๋น ํ์ด์ง ์์น๋ฅผ ํ์
4. ํ์ด์ง ๊ต์ฒด
- ๋ง์ฝ ๋ฉ๋ชจ๋ฆฌ๊ฐ ๊ฐ๋์ฐจ์ ์๋ก์ด ํ์ด์ง๋ฅผ ๋ก๋ํ ์ ์์ ๊ฒฝ์ฐ, ์ด์์ฒด์ ๋ ํ์ด์ง ๊ต์ฒด ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด ๋ฉ๋ชจ๋ฆฌ์์ ์ ๊ฑฐํ ํ์ด์ง๋ฅผ ์ ํ
- ์ ํ๋ ํ์ด์ง๋ ๋์คํฌ๋ก ์ด๋๋๊ณ ๊ทธ ์๋ฆฌ์ ์๋ก์ด ํ์ด์ง๊ฐ ๋ก๋๋จ. ์ดํ ํ์ด์ง ํ ์ด๋ธ ์ ๋ฐ์ดํธ
์ด๋ 4๋ฒ ํ์ด์ง ๊ต์ฒด ๊ณผ์ ์์ ํ์ด์ง ๊ต์ฒด ์๊ณ ๋ฆฌ์ฆ์ด ์ฌ์ฉ๋๋ค.
ํ์ด์ง ๊ต์ฒด ๊ธฐ๋ฒ์ ๋ํ์ ์ธ ์๊ณ ๋ฆฌ์ฆ์ FIFO, LRU, LFU, OPT, NUR, SCR ๋ฑ์ด ์๋ค.
๐นFIFO(First-In-First-Out: ์ ์ ์ ์ถ)
FIFO๋ ๊ฐ์ฅ ๋จผ์ ๋ค์ด์จ ํ์ด์ง๋ถํฐ ๊ต์ฒดํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
์ฅ์ : ์ดํดํ๊ธฐ ์ฌ์ ์ค๊ณ ๋ฐ ๊ตฌํ์ด ๊ฐ๋จ
๋จ์ : ์ค๋๋ ํ์ด์ง๊ฐ ๋ฌด์กฐ๊ฑด ๋ถํ์ํ ํ์ด์ง๊ฐ ์๋ ์ ์๊ธฐ ๋๋ฌธ์ ์คํ๋ ค ํ์ด์ง ๋ถ์ฌ์จ์ ๋์ผ ์ ์์
๐นLRU(Least Recently Used)
LRU๋ ์ฌ์ฉ๋ ์๊ฐ์ ํ์ธํ์ฌ ๊ฐ์ฅ ์ค๋ซ๋์ ์ฌ์ฉ๋์ง ์์ ํ์ด์ง๋ฅผ ์ ํํ์ฌ ๊ต์ฒดํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
๋จ์ : ์ฐธ์กฐํ ๋๋ง๋ค ์๊ฐ์ ๊ธฐ๋กํด์ผํจ(Overhead)
๐นLFU(Least Frequently Used)
LFU๋ ์ฌ์ฉ๋ ํ์๋ฅผ ํ์ธํ์ฌ ์ฐธ์กฐ ํ์๊ฐ ๊ฐ์ฅ ์ ์ ํ์ด์ง๋ฅผ ์ ํํ์ฌ ๊ต์ฒดํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
๋จ์ : ์ต๊ทผ ์ ์ฌ๋ ํ์ด์ง ์ค ์์ผ๋ก ์ฐธ์กฐ๋ ๊ฐ๋ฅ์ฑ์ด ๋์ ํ์ด์ง๊ฐ ๊ต์ฒด๋ ๊ฐ๋ฅ์ฑ์ด ์์
๐นClock Algorithm
Clock์ ์ค๋ซ๋์ ์ฐธ์กฐ๋์ง ์์ ํ์ด์ง๋ฅผ ๊ต์ฒดํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
LRU์ ๋น์ทํ์ง๋ง "๊ฐ์ฅ ์ค๋๋ ํ์ด์ง ๊ต์ฒด"๋ฅผ ๋ณด์ฅํ์ง ์๋๋ค๋ ์ ์์ ๋ค๋ฅด๋ค.
๊ฐ ํ์ด์ง๋ค์ ์ฐธ์กฐ ๋นํธ(Reference Bit)๋ฅผ ๊ฐ์ง๊ณ ์๋๋ฐ, ์ด๋ ํ์ด์ง๋ค์ ์์ฐจ์ ์ผ๋ก ๊ฐ๋ฆฌํค๋ Pointer(์๊ณ๋ฐ๋)๋ฅผ ์ฌ์ฉํ์ฌ ๊ฐ ํ์ด์ง์ ์ฐธ์กฐ ๋นํธ์ ๋ฐ๋ผ ๊ต์ฒด๋ ํ์ด์ง๋ฅผ ๊ฒฐ์ ํ๋ค.
1. ํ์ฌ Pointer๊ฐ ๊ฐ๋ฆฌํค๊ณ ์๋ ํ์ด์ง์ ์ฐธ์กฐ๋นํธ(r) ํ์ธ2. r = 0 ์ธ ๊ฒฝ์ฐ, ๊ต์ฒด ํ์ด์ง๋ก ๊ฒฐ์ , ํ์ด์ง ๊ต์ฒด ํ r์ 1๋ก ๋ณ๊ฒฝ3. r = 1 ์ธ ๊ฒฝ์ฐ, r์ 0์ผ๋ก ์ด๊ธฐํ ํ Pointer๋ฅผ ๋ค์์ผ๋ก ์ด๋
๊ฐ์ ๋ Clock Algorithm == Second Chance Algorithm
- Update bit(m)๋ ์ถ๊ฐ๋ก ๊ณ ๋ คํจ
- Reference bit(r) = 1 : ์ต๊ทผ์ ์ฐธ์กฐ๋ ํ์ด์ง
- Update bit(m) = 1 : ์ต๊ทผ์ ๋ณ๊ฒฝ๋ ํ์ด์ง (I/O๋ฅผ ๋๋ฐํ๋ ํ์ด์ง)
- ํ์ฌ ๊ฐ๋ฆฌํค๊ณ ์๋ ํ์ด์ง์ (r, m)์ ํ์ธ
- (0, 0): ๊ต์ฒด ํ์ด์ง๋ก ๊ฒฐ์
- (0, 1): (0, 0)์ผ๋ก ๋ณ๊ฒฝ, write-back (cleaning) list์ ์ถ๊ฐ ํ ์ด๋
- (1, 0): (0, 0)์ผ๋ก ๋ณ๊ฒฝ ํ ์ด๋
- (1, 1): (0, 1)์ผ๋ก ๋ณ๊ฒฝ ํ ์ด๋
๐น์ฐ๋ ์ฑ(Thrashing) - ๋ฌธ์ ์
์ฐ๋ ์ฑ(Thrashing)์ด๋ ํ๋ก์ธ์ค์ ์ฒ๋ฆฌ์๊ฐ๋ณด๋ค ํ์ด์ง ๊ต์ฒด ์๊ฐ์ด ๋ ๋ง์์ ธ์(Page fault ์ฆ๊ฐ) CPU ์ด์ฉ๋ฅ ์ด ์ ํ๋๋ ํ์์ ๋งํ๋ค.
์ฆ, ๋ค์ค ํ๋ก๊ทธ๋๋ฐ์ ์ ๋๊ฐ ๋์์๋ก ์ฐ๋ ์ฑ์ ๋ฐ์ ๋น๋๋ ๋์์ง๋ค.
์ฐ๋ ์ฑ ํด๊ฒฐ ๋ฐฉ๋ฒ
- ๋ค์ค ํ๋ก๊ทธ๋๋ฐ ์ ๋ ↓
- CPU ์ด์ฉ ↑
- Working Set ๋ฐฉ๋ฒ ์ฌ์ฉ
๐น์ํน ์ (Working Set) - ์ฐ๋ ์ฑ ํด๊ฒฐ ๋ฐฉ์ 1
์ํน ์ (Working Set)์ด๋ ํ๋ก์ธ์ค๊ฐ ์ผ์ ์๊ฐ ๋์ ์์ฃผ ์ฐธ์กฐํ๋ ํ์ด์ง๋ค์ ์งํฉ์ด๋ผ๋ ๋ป์ผ๋ก, ์ง์ญ์ฑ์ ๊ธฐ๋ฐ์ผ๋ก ์์ฃผ ์ฐธ์กฐ๋๋ ํ๋ก์ธ์ค์ ์ํน ์ ์ ๋ฉ๋ชจ๋ฆฌ์ ํญ์ ์์ฃผ์ํด์ผ๋ก์จ ํ์ด์ง ๋ถ์ฌ(Page fault) ํ์์ ์ค์ด๋ ๊ฒ์ ๋งํ๋ค.
์๊ฐ์ด ์ง๋จ์ ๋ฐ๋ผ ์ํน ์ ์ ๋ณ๊ฒฝ์ด ๋๋ค.
*. ์ง์ญ์ฑ: ํ๋ก์ธ์ค๊ฐ ์คํ๋๋ ๋์ ์ฃผ๊ธฐ์ต์ฅ์น๋ฅผ ์ฐธ์กฐํ ๋ ์ผ๋ถ ํ์ด์ง๋ง ์ง์ค์ ์ผ๋ก ์ฐธ์กฐํ๋ ํน์ฑ
๐นํ์ด์ง ๋ถ์ฌ ๋น๋(PFF, Page Fault Frequency) - ์ฐ๋ ์ฑ ํด๊ฒฐ ๋ฐฉ์ 2
ํ์ด์ง ๋ถ์ฌ ๋น๋(Page Fault Frequency)๋ ํ์ด์ง ๋ถ์ฌ์จ์ ์ํ๊ณผ ํํ์ ์ ํ์ฌ ์ง์ ์ ์ผ๋ก ํ์ด์ง ๋ถ์ฌ์จ์ ์์ธกํ๊ณ ์กฐ์ ํ๋ ๊ธฐ๋ฒ์ด๋ค.
- ํ๋ก์ธ์ค์ ๋ฉ๋ชจ๋ฆฌ ์ ๊ทผ ํจํด, ์ฆ ์ง์ญ์ฑ(Locality)์ ๋ํ ์ ๋ณด๋ฅผ ๋ฐํ์ผ๋ก ์๋ํ๋ค.
- ํ์ด์ง ๋ถ์ฌ์จ์ ๋ฐ๋ผ ํ์ด์ง ํ๋ ์ ๊ฐ์๋ฅผ ์กฐ์ ํ๋ค.
- ์ฆ, ํ์ด์ง ๋ถ์ฌ์จ์ด ์์คํ ์ด ๋ฏธ๋ฆฌ ์ ํด ๋์ ์ํ๊ฐ(upper bound)์ ๋์ด๊ฐ๊ฑฐ๋ ํํ๊ฐ(lower bound)์ดํ๋ก ๋จ์ด์ง๊ฒ ๋๋ฉด ์ด์์ฒด์ ๊ฐ ๋ฉ๋ชจ๋ฆฌ์ ์ฌ๋ผ๊ฐ ์๋ ํ๋ก์ธ์ค์ ์๋ฅผ ์กฐ์ ํ๋ค.
์ฅ์
- ํ์ด์ง ๋ถ์ฌ ๋ฐ์ ์์ ์คํํ๊ธฐ ๋๋ฌธ์ ๋ถํ๊ฐ ์ ๋ค.
- ์ง์ ์ ์ผ๋ก ํ์ด์ง ๋ถ์ฌ์จ ์กฐ์ ์ด ๊ฐ๋ฅํ๋ค.
๋จ์
- ํ๋ก์ธ์ค๋ฅผ ์ค์ง์ํค๋ ๊ณผ์ ์ด ๋ฐ์ํ์ฌ ํ๋ก์ธ์ค์ ์คํ ์๊ฐ์ ์ง์ฐ์ํฌ ๊ฐ๋ฅ์ฑ์ด ์๋ค.
- ํ์ด์ง ์ฐธ์กฐ๊ฐ ์๋ก์ด ์ง์ญ์ฑ์ผ๋ก ์ด๋ํ ์ ์์ด, ํ๋ก์ธ์ค์ ๋ฉ๋ชจ๋ฆฌ ์ ๊ทผ ํจํด์ด ๊ธ๊ฒฉํ๊ฒ ๋ณํ์ฌ ํ์ด์ง ๋ถ์ฌ์จ ์์ธก์ ์ด๋ ต๊ฒ ๋ง๋ค๊ณ , ๋ฐ๋ผ์ ๋ฉ๋ชจ๋ฆฌ ๊ด๋ฆฌ์ ํจ์จ์ฑ์ด ์ ํ๋ ์ ์๋ค.
https://limqoh.tistory.com/entry/html02
https://lordofkangs.tistory.com/203
https://lordofkangs.tistory.com/211
https://zangzangs.tistory.com/133
https://yeol-study-history.tistory.com/73
https://gooweon.tistory.com/183
https://sorjfkrh5078.tistory.com/49
https://sorjfkrh5078.tistory.com/48
https://sorjfkrh5078.tistory.com/53
https://blackjellybear.tistory.com/47
https://scottxchoo.xyz/cs-os-012/
https://kangsu-2ji.tistory.com/175
https://zangzangs.tistory.com/144
http://www.jidum.com/jidums/view.do?jidumId=484
https://blog.naver.com/klp0712/220883220425
https://hpckoreatech.notion.site/Operating-System-CSE132-2023-b8aa98fe69cc4a8cb950051a04bc35ca
https://m.blog.naver.com/qbxlvnf11/221367174686
https://www.ilsangeasy.com/tag/%ED%8E%98%EC%9D%B4%EC%A7%95-%EA%B8%B0%EB%B2%95/
'CS > JSCODE' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์ด์์ฒด์ 3๊ธฐ] 5์ฃผ์ฐจ ํผ๋๋ฐฑ (0) | 2024.02.09 |
---|---|
[์ด์์ฒด์ 3๊ธฐ] 4์ฃผ์ฐจ ํผ๋๋ฐฑ (0) | 2024.02.02 |
[์ด์์ฒด์ 3๊ธฐ] 4์ฃผ์ฐจ ์คํฐ๋ ์ ๋ฆฌ (0) | 2024.01.31 |
[์ด์์ฒด์ 3๊ธฐ] 3์ฃผ์ฐจ ํผ๋๋ฐฑ (0) | 2024.01.26 |
[์ด์์ฒด์ 3๊ธฐ] 3์ฃผ์ฐจ ์คํฐ๋ ์ ๋ฆฌ (0) | 2024.01.22 |