--
Cache Hit
๋ฉ๋ชจ๋ฆฌ๊ฐ ์บ์์ ์กด์ฌํ๊ณ ์์ ๊ฒฝ์ฐ Cache Hit
๋ผ๊ณ ํ๋ค.
Cache Miss
๋ฉ๋ชจ๋ฆฌ๊ฐ ์บ์์ ์กด์ฌํ์ง ์์ ๋ Cache Miss
๋ผ๊ณ ํ๋ค.
Least Recently Used
๊ฐ์ฅ ์ค๋ซ๋์ "์ฐธ์กฐ"๋์ง ์์ ํ์ด์ง๋ฅผ ๊ต์ฒดํ๋ ๋ฐฉ์์ด๋ค. ์บ์๊ฐ ๊ฐ๋ ์ฐผ์๋, ๊ฐ์ฅ ์ค๋ซ๋์ ์ฐธ์กฐ๋์ง ์์ ํ์ด์ง๋ฅผ ์ฐพ์์ ์์ ๋ ๊ณผ์ ์ด ํ์ํ๋ค.
์ฌ์ฉ๋์ง ๊ฐ์ฅ ์ค๋๋ ํ์ด์ง๋ ์์ผ๋ก๋ ์ฌ์ฉ๋ ํ๋ฅ ์ด ๋ฎ๋ค๋ ๊ฐ์ค์ ์ํด ๋ง๋ค์ด์ง ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
๊ฐ์ฅ ์ค๋ซ๋์ ์ฐธ์กฐ๋์ง ์์ ํ์ด์ง๋ฅผ ์ฐพ์์ ์์ ๋ ๊ณผ์
ํ์ด์ง๋ฅผ ์๋ก ์ฐธ์กฐํ ๋๋ง๋ค ์ฐ๊ฒฐ๋ฆฌ์คํธ์ ๋งจ ์์ ํ์ด์ง๋ฒํธ๋ฅผ ์ถ๊ฐํ๋ค.
๊ทธ๋ฌ๋ฉด ๋งจ ๋ค์ ์๋ ํ์ด์ง๋ฒํธ๊ฐ ๊ฐ์ฅ ์ค๋ซ๋์ ์ฐธ์กฐ๋์ง ์์ ํ์ด์ง๋ฒํธ๊ฐ ๋๋ค.
Doubly Linked List
๋ฅผ ์ฌ์ฉํ๊ณ head
์ ๊ฐ๊น์ด node
์ผ์๋ก ๊ฐ์ฅ ์ต๊ทผ์ ์ฐธ์กฐ๋ ํ์ด์ง, tail
์ ๊ฐ๊น์ด node
์ผ์๋ก ๊ฐ์ฅ ์ค๋ซ๋์ ์ฐธ์กฐ๋์ง ์๋ ํ์ด์ง์ด๋ค.
hit
์ผ ๋ : ๊ธฐ์กด ํ์ด์ง ์ญ์ ํ ๋งจ ์์ ๋ค์ ์ถ๊ฐmiss
์ผ ๋ : ๋งจ ์์ ์ถ๊ฐcache size
๋ฅผ ๋์ด์๊ฒ ๋ ๋ : tail
์ ๊ฐ์ฅ ๊ฐ๊น์ด ํ์ด์ง ์ญ์ ํ ๋งจ ์์ ๋ค์ ์ถ๊ฐ์บ์์ ํฌ๊ธฐ๋ 3์ด๋ค.
์๋ก์ด ์ฐธ์กฐ๊ฐ์ ๋งจ ์์ ์ถ๊ฐํ๋ค.
์ด๋ฏธ 3๊ฐ์ ์ฐธ์กฐ๊ฐ์ด ์บ์์ ๋ค์ด์๋ค๋ฉด ๋งจ ๋ค์ ์๋ ์ฐธ์กฐ๊ฐ์ ์ ๊ฑฐํ๊ณ ์๋ก์ด ์ฐธ์กฐ๊ฐ์ ๋งจ ์์ ์ถ๊ฐํ๋ค.
์๋ก์ด ์ฐธ์กฐ๊ฐ์ด ์ด๋ฏธ ์บ์์ ๋ค์ด์๋ ๊ฐ์ด๋ผ๋ฉด ๊ธฐ์กด ์์น์์ ์ ๊ฑฐํ๊ณ ๋ค์ ๋งจ ์์ ์ถ๊ฐํ๋ค.
- ์บ์ ๋ฆฌ์คํธ์ ํฌ๊ธฐ๋
3
์ด๋ค.
์ฐธ์กฐ๊ฐ 1
์ด ์บ์ ๋ฆฌ์คํธ์ ๋งจ ์์ ์ถ๊ฐ๋๋ค.
โณmiss
,์ฐธ์กฐ๊ฐ 1
์ ์บ์๋ฆฌ์คํธ์ ์๋ ๊ฐ์ด๋ฏ๋ก.
์ฐธ์กฐ๊ฐ 2
๊ฐ ์บ์ ๋ฆฌ์คํธ์ ๋งจ ์์ ์ถ๊ฐ๋๋ค.
โณmiss
,์ฐธ์กฐ๊ฐ 2
๋ ์บ์๋ฆฌ์คํธ์ ์๋ ๊ฐ์ด๋ฏ๋ก.
์ฐธ์กฐ๊ฐ 1
์ด ์บ์ ๋ฆฌ์คํธ์ ๋งจ ์์ ์ถ๊ฐ๋๋ค.
โณhit
,์ฐธ์กฐ๊ฐ 1
์ ์บ์๋ฆฌ์คํธ์ ์๋ ๊ฐ์ด๋ฏ๋ก ๊ธฐ์กด ์์น์์ ์ง์์ง๊ณ ๋ค์ ๋งจ ์์ ์ถ๊ฐ ๋๋ค.`
์ฐธ์กฐ๊ฐ 3
์ด ์บ์ ๋ฆฌ์คํธ์ ๋งจ ์์ ์ถ๊ฐ๋๋ค.
โณmiss
,์ฐธ์กฐ๊ฐ 3
๋ ์บ์๋ฆฌ์คํธ์ ์๋ ๊ฐ์ด๋ฏ๋ก.
์ฐธ์กฐ๊ฐ 4
๊ฐ ์บ์ ๋ฆฌ์คํธ์ ๋งจ ์์ ์ถ๊ฐ๋๋ค.
โณmiss
,์ฐธ์กฐ๊ฐ 4
๋ ์บ์๋ฆฌ์คํธ์ ์๋ ๊ฐ์ด๋ฏ๋ก.
: ์บ์๋ฆฌ์คํธ๊ฐ ๊ฐ๋ ์ฐผ์ผ๋ฏ๋ก ๋ฆฌ์คํธ์ ๋งจ ๋ค์ ์๋ = ๊ฐ์ฅ ์ค๋ซ๋์ ์ฐธ์กฐ๋์ง ์์์ฐธ์กฐ๊ฐ 2
๊ฐ ์ญ์ ๋๊ณ ,์ฐธ์กฐ๊ฐ 4
๊ฐ ์บ์๋ฆฌ์คํธ์ ๋งจ ์์ ์ถ๊ฐ๋๋ค.
์ฐธ์กฐ๊ฐ 1
์ด ์บ์ ๋ฆฌ์คํธ์ ๋งจ ์์ ์ถ๊ฐ๋๋ค.
โณhit
,์ฐธ์กฐ๊ฐ 1
์ ์บ์๋ฆฌ์คํธ์ ์๋ ๊ฐ์ด๋ฏ๋ก ๊ธฐ์กด ์์น์์ ์ง์์ง๊ณ ๋ค์ ๋งจ ์์ ์ถ๊ฐ ๋๋ค.
์ฐธ์กฐ๊ฐ 5
๊ฐ ์บ์ ๋ฆฌ์คํธ์ ๋งจ ์์ ์ถ๊ฐ๋๋ค.
โณmiss
,์ฐธ์กฐ๊ฐ 5
๋ ์บ์๋ฆฌ์คํธ์ ์๋ ๊ฐ์ด๋ฏ๋ก.
: ์บ์๋ฆฌ์คํธ๊ฐ ๊ฐ๋ ์ฐผ์ผ๋ฏ๋ก ๋ฆฌ์คํธ์ ๋งจ ๋ค์ ์๋ = ๊ฐ์ฅ ์ค๋ซ๋์ ์ฐธ์กฐ๋์ง ์์์ฐธ์กฐ๊ฐ 3
์ด ์ญ์ ๋๊ณ ,์ฐธ์กฐ๊ฐ 5
๊ฐ ์บ์๋ฆฌ์คํธ์ ๋งจ ์์ ์ถ๊ฐ๋๋ค.
์ฐธ์กฐ๊ฐ 4
๊ฐ ์บ์ ๋ฆฌ์คํธ์ ๋งจ ์์ ์ถ๊ฐ๋๋ค.
โณhit
,์ฐธ์กฐ๊ฐ 4
๋ ์บ์๋ฆฌ์คํธ์ ์๋ ๊ฐ์ด๋ฏ๋ก ๊ธฐ์กด ์์น์์ ์ง์์ง๊ณ ๋ค์ ๋งจ ์์ ์ถ๊ฐ ๋๋ค.
์ฌ๊ณผ๊ฐ๋ฐ์์ ์ผ์
๋ธ๋ก๊ทธ์ LRU ์๊ณ ๋ฆฌ์ฆ (Least Recentely Used) ๊ฐ๋
๋ฐ ๊ตฌํ๋ฐฉ๋ฒ
๊ฒ์๋ฌผ์์ ๊ฐ์ ธ์จ ๊ฒ์
๋๋ค.: ํฐ์คํ ๋ฆฌ
์ฌ์ดํธ์ daily_D
๋์ ์ฌ๊ณผ๊ฐ๋ฐ์์ ์ผ์
๋ธ๋ก๊ทธ์ LRU ์๊ณ ๋ฆฌ์ฆ (Least Recentely Used) ๊ฐ๋
๋ฐ ๊ตฌํ๋ฐฉ๋ฒ
๊ฒ์๋ฌผ