ํ์ด์ง ๋ถ์ฌ ๋ฐ์ โ ์๋ก์ด ํ์ด์ง๋ฅผ ํ ๋นํด์ผ ํจ โ ํ์ฌ ํ ๋น๋ ํ์ด์ง ์ค ์ด๋ค ๊ฒ ๊ต์ฒดํ ์ง ๊ฒฐ์ ํ๋ ๋ฐฉ๋ฒ
- ์ข ๋ ์์ธํ๊ฒ ์๊ฐํด๋ณด๋ฉด?
๊ฐ์ ๋ฉ๋ชจ๋ฆฌ๋ ์๊ตฌ ํ์ด์ง ๊ธฐ๋ฒ
์ ํตํด ํ์ํ ํ์ด์ง๋ง ๋ฉ๋ชจ๋ฆฌ์ ์ ์ฌํ๊ณ ์ฌ์ฉํ์ง ์๋ ๋ถ๋ถ์ ๊ทธ๋๋ก ๋
ํ์ง๋ง ํ์ํ ํ์ด์ง๋ง ์ฌ๋ ค๋ ๋ฉ๋ชจ๋ฆฌ๋ ๊ฒฐ๊ตญ ๊ฐ๋ ์ฐจ๊ฒ ๋๊ณ , ์ฌ๋ผ์์๋ ํ์ด์ง๊ฐ ์ฌ์ฉ์ด ๋ค ๋ ํ์๋ ์๋ฆฌ๋ง ์ฐจ์งํ๊ณ ์์ ์ ์์
๋ฐ๋ผ์ ๋ฉ๋ชจ๋ฆฌ๊ฐ ๊ฐ๋ ์ฐจ๋ฉด, ์ถ๊ฐ๋ก ํ์ด์ง๋ฅผ ๊ฐ์ ธ์ค๊ธฐ ์ํด์ ์์ฐ๋ ํ์ด์ง๋ outํ๊ณ , ํด๋น ๊ณต๊ฐ์ ํ์ฌ ํ์ํ ํ์ด์ง๋ฅผ in ์์ผ์ผ ํจ
์ฌ๊ธฐ์ ์ด๋ค ํ์ด์ง๋ฅผ out ์์ผ์ผํ ์ง ์ ํด์ผ ํจ. (์ด๋ out ๋๋ ํ์ด์ง๋ฅผ victim page๋ผ๊ณ ๋ถ๋ฆ)
๊ธฐ์์ด๋ฉด ์์ ์ด ๋์ง ์๋ ํ์ด์ง๋ฅผ ์ ํํด์ผ ์ข์ (Why? : ๋ง์ฝ ์์ ๋๋ฉด ๋ฉ์ธ ๋ฉ๋ชจ๋ฆฌ์์ ๋ด๋ณด๋ผ ๋, ํ๋๋์คํฌ์์ ๋ ์์ ์ ์งํํด์ผ ํ๋ฏ๋ก ์๊ฐ์ด ์ค๋ ๊ฑธ๋ฆผ)
์ด์ ๊ฐ์ ์ํฉ์์ ์ํฉ์ ๋ง๋ ํ์ด์ง ๊ต์ฒด๋ฅผ ์งํํ๊ธฐ ์ํด ํ์ด์ง ๊ต์ฒด ์๊ณ ๋ฆฌ์ฆ์ด ์กด์ฌํ๋ ๊ฒ!
CPU๋ ๋ ผ๋ฆฌ ์ฃผ์๋ฅผ ํตํด ํน์ ์ฃผ์๋ฅผ ์๊ตฌํจ
๋ฉ์ธ ๋ฉ๋ชจ๋ฆฌ์ ์ฌ๋ผ์ ์๋ ์ฃผ์๋ค์ ํ์ด์ง์ ๋จ์๋ก ๊ฐ์ ธ์ค๊ธฐ ๋๋ฌธ์ ํ์ด์ง ๋ฒํธ๊ฐ ์ฐ์๋์ด ๋ํ๋๊ฒ ๋๋ฉด ํ์ด์ง ๊ฒฐํจ ๋ฐ์ X
๋ฐ๋ผ์ CPU์ ์ฃผ์ ์๊ตฌ์ ๋ฐ๋ผ ํ์ด์ง ๊ฒฐํจ์ด ์ผ์ด๋์ง ์๋ ๋ถ๋ถ์ ์๋ตํ์ฌ ํ์ํ๋ ๋ฐฉ๋ฒ์ด ๋ฐ๋ก
Page Reference String
-
First-in First-out, ๋ฉ๋ชจ๋ฆฌ์ ๋จผ์ ์ฌ๋ผ์จ ํ์ด์ง๋ฅผ ๋จผ์ ๋ด๋ณด๋ด๋ ์๊ณ ๋ฆฌ์ฆ
victim page : out ๋๋ ํ์ด์ง๋, ๊ฐ์ฅ ๋จผ์ ๋ฉ๋ชจ๋ฆฌ์ ์ฌ๋ผ์จ ํ์ด์ง
๊ฐ์ฅ ๊ฐ๋จํ ๋ฐฉ๋ฒ์ผ๋ก, ํนํ ์ด๊ธฐํ ์ฝ๋์์ ์ ์ ํ ๋ฐฉ๋ฒ์
์ด๊ธฐํ ์ฝ๋
: ์ฒ์ ํ๋ก์ธ์ค ์คํ๋ ๋ ์ต์ด ์ด๊ธฐํ๋ฅผ ์ํค๋ ์ญํ ๋ง ์งํํ๊ณ ๋ค๋ฅธ ์ญํ ์ ์ํํ์ง ์์ผ๋ฏ๋ก, ๋ฉ์ธ ๋ฉ๋ชจ๋ฆฌ์์ ๋นผ๋ ๊ด์ฐฎ์ํ์ง๋ง ์ฒ์ ํ๋ก์ธ์ค ์คํ์์๋ ๋ฌด์กฐ๊ฑด ํ์ํ ์ฝ๋์ด๋ฏ๋ก, FIFO ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋ฉด ์ด๊ธฐํ๋ฅผ ์์ผ์ค ํ ๊ฐ์ฅ ๋จผ์ ๋ด๋ณด๋ด๋ ๊ฒ์ด ๊ฐ๋ฅํจ
-
Optimal Page Replacement ์๊ณ ๋ฆฌ์ฆ, ์์ผ๋ก ๊ฐ์ฅ ์ฌ์ฉํ์ง ์์ ํ์ด์ง๋ฅผ ๊ฐ์ฅ ์ฐ์ ์ ์ผ๋ก ๋ด๋ณด๋
FIFO์ ๋นํด ํ์ด์ง ๊ฒฐํจ์ ํ์๋ฅผ ๋ง์ด ๊ฐ์์ํฌ ์ ์์
ํ์ง๋ง, ์ค์ง์ ์ผ๋ก ํ์ด์ง๊ฐ ์์ผ๋ก ์ ์ฌ์ฉ๋์ง ์์ ๊ฒ์ด๋ผ๋ ๋ณด์ฅ์ด ์๊ธฐ ๋๋ฌธ์ ์ํํ๊ธฐ ์ด๋ ค์ด ์๊ณ ๋ฆฌ์ฆ์
-
Least-Recently-Used, ์ต๊ทผ์ ์ฌ์ฉํ์ง ์์ ํ์ด์ง๋ฅผ ๊ฐ์ฅ ๋จผ์ ๋ด๋ ค๋ณด๋ด๋ ์๊ณ ๋ฆฌ์ฆ
์ต๊ทผ์ ์ฌ์ฉํ์ง ์์์ผ๋ฉด, ๋์ค์๋ ์ฌ์ฉ๋์ง ์์ ๊ฒ์ด๋ผ๋ ์์ด๋์ด์์ ๋์ด
OPT์ ๊ฒฝ์ฐ ๋ฏธ๋ ์์ธก์ด์ง๋ง, LRU์ ๊ฒฝ์ฐ๋ ๊ณผ๊ฑฐ๋ฅผ ๋ณด๊ณ ํ๋จํ๋ฏ๋ก ์ค์ง์ ์ผ๋ก ์ฌ์ฉ์ด ๊ฐ๋ฅํ ์๊ณ ๋ฆฌ์ฆ
(์ค์ ๋ก๋ ์ต๊ทผ์ ์ฌ์ฉํ์ง ์์ ํ์ด์ง๋ ์์ผ๋ก๋ ์ฌ์ฉํ์ง ์์ ํ๋ฅ ์ด ๋๋ค)
OPT๋ณด๋ค๋ ํ์ด์ง ๊ฒฐํจ์ด ๋ ์ผ์ด๋ ์ ์์ง๋ง, ์ค์ ๋ก ์ฌ์ฉํ ์ ์๋ ํ์ด์ง ๊ต์ฒด ์๊ณ ๋ฆฌ์ฆ์์๋ ๊ฐ์ฅ ์ข์ ๋ฐฉ๋ฒ ์ค ํ๋์
-
Global ๊ต์ฒด
๋ฉ๋ชจ๋ฆฌ ์์ ๋ชจ๋ ํ๋ก์ธ์ค ํ์ด์ง์ ๋ํด ๊ต์ฒดํ๋ ๋ฐฉ์
-
Local ๊ต์ฒด
๋ฉ๋ชจ๋ฆฌ ์์ ์๊ธฐ ํ๋ก์ธ์ค ํ์ด์ง์์๋ง ๊ต์ฒดํ๋ ๋ฐฉ์
๋ค์ค ํ๋ก๊ทธ๋๋ฐ์ ๊ฒฝ์ฐ, ๋ฉ์ธ ๋ฉ๋ชจ๋ฆฌ์ ๋ค์ํ ํ๋ก์ธ์ค๊ฐ ๋์์ ์ฌ๋ผ์ฌ ์ ์์
๋ฐ๋ผ์, ๋ค์ํ ํ๋ก์ธ์ค์ ํ์ด์ง๊ฐ ๋ฉ๋ชจ๋ฆฌ์ ์กด์ฌํจ
ํ์ด์ง ๊ต์ฒด ์, ๋ค์ํ ํ์ด์ง ๊ต์ฒด ์๊ณ ๋ฆฌ์ฆ์ ํ์ฉํด victim page๋ฅผ ์ ์ ํ๋๋ฐ, ์ ์ ๊ธฐ์ค์ Global๋ก ํ๋๋, Local๋ก ํ๋๋์ ๋ํ ์ฐจ์ด
โ ์ค์ ๋ก๋ ์ ์ฒด๋ฅผ ๊ธฐ์ค์ผ๋ก ํ์ด์ง๋ฅผ ๊ต์ฒดํ๋ ๊ฒ์ด ๋ ํจ์จ์ ์ด๋ผ๊ณ ํจ. ์๊ธฐ ํ๋ก์ธ์ค ํ์ด์ง์์๋ง ๊ต์ฒด๋ฅผ ํ๋ฉด, ๊ต์ฒด๋ฅผ ํด์ผํ ๋ ๊ฐ๊ฐ ๋ชจ๋ ๊ต์ฒด๋ฅผ ์งํํด์ผ ํ๋ฏ๋ก ๋นํจ์จ์