๐Ÿ˜ถโ€๐ŸŒซ๏ธ [์—‰์งง์‹] LRU๋ฅผ ์•Œ์•„๋ณด์•˜๋‹ค

0
post-thumbnail

--

๐ŸŸช 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) ๊ฐœ๋… ๋ฐ ๊ตฌํ˜„๋ฐฉ๋ฒ• ๊ฒŒ์‹œ๋ฌผ

profile
๋ช‡ ๋ฒˆ์„ ๋„˜์–ด์ ธ๋„ ์•ž์œผ๋กœ ๊ณ„์† ๋‚˜์•„๊ฐ€์ž

0๊ฐœ์˜ ๋Œ“๊ธ€