ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [OS] ํŽ˜์ด์ง€ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜ - FIFO/LRU/LFU/MFU/NUR
    CS 2021. 7. 18. 05:19

    ๐Ÿ’ก  ํŽ˜์ด์ง€ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜

    ์šด์˜์ฒด์ œ๋Š” ์ฃผ๊ธฐ์–ต์žฅ์น˜๋ณด๋‹ค ๋” ํฐ ์šฉ๋Ÿ‰์˜ ํ”„๋กœ๊ทธ๋žจ์„ ์‹คํ–‰ํ•˜๊ธฐ ์œ„ํ•ด ํ”„๋กœ๊ทธ๋žจ์˜ ์ผ๋ถ€๋งŒ ์ฃผ๊ธฐ์–ต์žฅ์น˜์— ์ ์žฌํ•˜์—ฌ ์‚ฌ์šฉํ•œ๋‹ค. ์ด๋ฅผ ๊ฐ€์ƒ๋ฉ”๋ชจ๋ฆฌ ๊ธฐ๋ฒ•์ด๋ผ ํ•œ๋‹ค.
    ํŽ˜์ด์ง• ๊ธฐ๋ฒ•์œผ๋กœ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ๊ด€๋ฆฌํ•˜๋Š” ์šด์˜์ฒด์ œ์—์„œ ํ•„์š”ํ•œ ํŽ˜์ด์ง€๊ฐ€ ์ฃผ๊ธฐ์–ต์žฅ์น˜์— ์ ์žฌ๋˜์ง€ ์•Š์•˜์„ ์‹œ(ํŽ˜์ด์ง€ ๋ถ€์žฌ) ์–ด๋–ค ํŽ˜์ด์ง€ ํ”„๋ ˆ์ž„์„ ์„ ํƒํ•˜์—ฌ ๊ต์ฒดํ•  ๊ฒƒ์ธ์ง€ ๊ฒฐ์ •ํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ํŽ˜์ด์ง€ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ผ๊ณ  ํ•œ๋‹ค.

     

    * ํ”„๋ ˆ์ž„: ๋ฌผ๋ฆฌ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ผ์ •ํ•œ ํฌ๊ธฐ๋กœ ๋‚˜๋ˆˆ ๋ธ”๋ก
    * ํŽ˜์ด์ง€: ๊ฐ€์ƒ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์ผ์ •ํ•œ ํฌ๊ธฐ๋กœ ๋‚˜๋ˆˆ ๋ธ”๋ก


    โœ… ํŽ˜์ด์ง€ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ข…๋ฅ˜

    1. OPT - Optimal : ์•ž์œผ๋กœ ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉ๋˜์ง€ ์•Š์„ ํŽ˜์ด์ง€ ๊ต์ฒด
    2. FIFO - First In First Out
    3. LRU - Least Recently Used : ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉ๋˜์ง€ ์•Š์€ ํŽ˜์ด์ง€ ๊ต์ฒด
    4. LFU - Least Frequently Used : ์ฐธ์กฐ ํšŸ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ์ž‘์€ ํŽ˜์ด์ง€ ๊ต์ฒด
    5. MFU - Most Frequently used : ์ฐธ์กฐ ํšŸ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ๋งŽ์€ ํŽ˜์ด์ง€ ๊ต์ฒด
    6. NUR - Not Used Recently : ์ตœ๊ทผ์— ์‚ฌ์šฉํ•˜์ง€ ์•Š์€ ํŽ˜์ด์ง€ ๊ต์ฒด

     

    ๐Ÿ“Œ OPT(Optimal) - ์•ž์œผ๋กœ ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉ๋˜์ง€ ์•Š์„ ํŽ˜์ด์ง€ ๊ต์ฒด

    • ๊ฐ€์žฅ ์ด์ƒ์ ์ž„
    • ํ”„๋กœ์„ธ์Šค๊ฐ€ ์•ž์œผ๋กœ ์‚ฌ์šฉํ•  ํŽ˜์ด์ง€๋ฅผ ๋ฏธ๋ฆฌ ์•Œ์•„์•ผ ํ•จ -> ๋ถˆ๊ฐ€๋Šฅ
    • ๋น„๊ต ์—ฐ๊ตฌ ๋ชฉ์ ์„ ์œ„ํ•ด ์‚ฌ์šฉ๋จ

     

    ๐Ÿ“Œ FIFO(First in First out) - ๊ฐ€์žฅ ๋จผ์ € ๋“ค์–ด์˜จ ํŽ˜์ด์ง€๋ฅผ ๊ต์ฒด

    • ๋ฉ”๋ชจ๋ฆฌ์— ๊ฐ€์žฅ ๋จผ์ € ์˜ฌ๋ผ์˜จ ํŽ˜์ด์ง€๋ฅผ ๋จผ์ € ๋‚ด๋ณด๋ƒ„.
    • ๊ฐ„๋‹จํ•˜๊ณ , ์ดˆ๊ธฐํ™” ์ฝ”๋“œ์— ๋Œ€ํ•ด ์ ์ ˆํ•œ ๋ฐฉ๋ฒ•
    • ๋“ค์–ด์˜จ ์‹œ๊ฐ„์„ ์ €์žฅํ•˜๊ฑฐ๋‚˜ ์˜ฌ๋ผ์˜จ ์ˆœ์„œ๋ฅผ ํ์— ์ €์žฅ.
    • ์ง๊ด€์ ์œผ๋กœ ์ƒ๊ฐํ•  ๋•Œ ํ”„๋ ˆ์ž„์˜ ์ˆ˜๊ฐ€ ๋งŽ์•„์งˆ์ˆ˜๋ก ํŽ˜์ด์ง€ ๊ฒฐํ•จ์˜ ํšŸ์ˆ˜๋Š” ๊ฐ์†Œํ•จ
    • Belady's Anomaly(FIFO anomaly)
      ์‹ค์ œ๋กœ ๊ทธ๋ ‡์ง€ ์•Š๊ฒŒ ๋˜๋Š” ํ˜„์ƒ์ด ๋‚˜ํƒ€๋‚  ์ˆ˜ ์žˆ๋‹ค.

     

     

    ๐Ÿ“ŒLRU(Least Recently Used) - ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉํ•˜์ง€ ์•Š์€ ํŽ˜์ด์ง€๋ฅผ ๊ต์ฒด

    • ๊ฐ€์ •: ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์‚ฌ์šฉํ•˜์ง€ ์•Š์•˜๋˜ ๋ฐ์ดํ„ฐ๋ผ๋ฉด ์•ž์œผ๋กœ๋„ ์‚ฌ์šฉํ•  ํ™•๋ฅ ์ด ์ ์„ ๊ฒƒ์ด๋‹ค.
      ์‹œ๊ฐ„ ์ง€์—ญ์„ฑ(temporal locality)์„ฑ์งˆ ๊ณ ๋ คํ•จ.(์ตœ๊ทผ์— ์ฐธ์กฐ๋œ ํŽ˜์ด์ง€๊ฐ€ ๊ฐ€๊นŒ์šด ๋ฏธ๋ž˜์— ๋‹ค์‹œ ์ฐธ์กฐ๋  ๊ฐ€๋Šฅ์„ฑ์ด ๋†’์€ ์„ฑ์งˆ)
    • ์‚ฌ์šฉ๋œ ์‹œ๊ฐ„์„ ์•Œ์ˆ˜์žˆ๋Š” ๋ถ€๋ถ„์„ ์ €์žฅํ•˜์—ฌ ๊ฐ€์žฅ ์˜ค๋žซ๋™์•ˆ ์ฐธ์กฐ๋˜์ง€ ์•Š๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์ œ๊ฑฐ(ํŽ˜์ด์ง€๋งˆ๋‹ค ์นด์šดํ„ฐ ํ•„์š”)
    • ํ๋กœ ๊ตฌํ˜„๊ฐ€๋Šฅ. ์‚ฌ์šฉํ•œ ๋ฐ์ดํ„ฐ๋ฅผ ํ์—์„œ ์ œ๊ฑฐํ•˜์—ฌ ๋งจ ์œ„๋กœ๋‹ค์‹œ ์˜ฌ๋ฆฌ๊ณ , ํ”„๋ ˆ์ž„์ด ๋ชจ์ž๋ž„ ๊ฒฝ์šฐ ๋งจ ์•„๋ž˜์— ์žˆ๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์‚ญ์ œ
    • ๋‹จ์ : ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ฃผ๊ธฐ์–ต์žฅ์น˜์— ์ ‘๊ทผํ• ๋•Œ๋งˆ๋‹ค ์ฐธ์กฐ๋œ ํŽ˜์ด์ง€ ์‹œ๊ฐ„์„ ๊ธฐ๋กํ•ด์•ผ ํ•˜๋ฏ€๋กœ ๋ง‰๋Œ€ํ•œ ์˜ค๋ฒ„ํ—ค๋“œ๊ฐ€ ๋ฐœ์ƒ
      ์นด์šดํ„ฐ๋‚˜ ํ, ์Šคํƒ๊ณผ ๊ฐ™์€ ๋ณ„๋„์˜ ํ•˜๋“œ์›จ์–ด๊ฐ€ ํ•„์š”

    * ์นด์šดํ„ฐ : ๊ฐ ํŽ˜์ด์ง€๋ณ„๋กœ ์กด์žฌํ•˜๋Š” ๋…ผ๋ฆฌ์ ์ธ ์‹œ๊ณ„(Logical Clock)๋กœ, ํ•ด๋‹น ํŽ˜์ด์ง€๊ฐ€ ์‚ฌ์šฉ๋ ๋•Œ๋งˆ๋‹ค 0์œผ๋กœ ํด๋ฆฌ์–ด ์‹œํ‚จ ํ›„ ์‹œ๊ฐ„์„ ์ฆ๊ฐ€์‹œ์ผœ ์‹œ๊ฐ„์ด ๊ฐ€์žฅ ์˜ค๋ž˜๋œ ํŽ˜์ด์ง€๋ฅผ ๊ต์ฒด

     

     

    ๐Ÿ“Œ LFU(Least Frequently Used) - ์ฐธ์กฐ ํšŸ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ๋‚ฎ์€ ํŽ˜์ด์ง€๋ฅผ ๊ต์ฒด

    • ํŽ˜์ด์ง€์˜ ์ฐธ์กฐ ํšŸ์ˆ˜๋กœ ๊ต์ฒดํ•  ํŽ˜์ด์ง€ ๊ฒฐ์ •
    • LRU๋Š” ์ง์ „ ์ฐธ์กฐ๋œ ์‹œ์ ๋งŒ์„ ๋ฐ˜์˜ํ•˜์ง€๋งŒ, LFU๋Š” ์ฐธ์กฐํšŸ์ˆ˜๋ฅผ ํ†ตํ•ด ์žฅ๊ธฐ์  ์‹œ๊ฐ„๊ทœ๋ชจ์—์„œ์˜ ์ฐธ์กฐ์„ฑํ–ฅ ๊ณ ๋ คํ•  ์ˆ˜ ์žˆ์Œ
    • ๋‹จ์ : ๊ฐ€์žฅ ์ตœ๊ทผ์— ๋ถˆ๋Ÿฌ์˜จ ํŽ˜์ด์ง€๊ฐ€ ๊ต์ฒด๋  ์ˆ˜ ์žˆ์Œ, ๊ตฌํ˜„ ๋” ๋ณต์žก, ๋ง‰๋Œ€ํ•œ ์˜ค๋ฒ„ํ—ค๋“œ

     

    ๐Ÿ“Œ MFU(Most Frequently used) - ์ฐธ์กฐ ํšŸ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ๋งŽ์€ ํŽ˜์ด์ง€ ๊ต์ฒด

    • ๊ฐ€์ •: ๊ฐ€์žฅ ๋งŽ์ด ์‚ฌ์šฉ๋œ ํŽ˜์ด์ง€๊ฐ€ ์•ž์œผ๋กœ๋Š” ์‚ฌ์šฉ๋˜์ง€ ์•Š์„ ๊ฒƒ์ด๋‹ค

     

    ๐Ÿ“ŒNUR = NRU(Not Used Recently, Not Recently Used), ํด๋Ÿญ ์•Œ๊ณ ๋ฆฌ์ฆ˜

    • ์ตœ๊ทผ์— ์‚ฌ์šฉํ•˜์ง€ ์•Š์€ ํŽ˜์ด์ง€ ๊ต์ฒด (LRU๋ฅผ ๊ทผ์‚ฌํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜)
    • ๊ต์ฒด๋˜๋Š” ํŽ˜์ด์ง€์˜ ์ฐธ์กฐ ์‹œ์ ์ด ๊ฐ€์žฅ ์˜ค๋ž˜๋˜์—ˆ๋‹ค๋Š” ๊ฒƒ์„ ๋ณด์žฅํ•˜์ง€๋Š” ๋ชปํ•จ
    • ์ ์€ ์˜ค๋ฒ„ํ—ค๋“œ๋กœ ์ ์ ˆํ•œ ์„ฑ๋Šฅ
    • ๋™์ผ ๊ทธ๋ฃน ๋‚ด์—์„œ ์„ ํƒ ๋ฌด์ž‘์œ„
    • ๊ฐ ํŽ˜์ด์ง€๋งˆ๋‹ค ๋‘๊ฐœ์˜ ๋น„ํŠธ ์ฐธ์กฐ ๋น„ํŠธ(Reference Bit)์™€ ๋ณ€ํ˜• ๋น„ํŠธ(Modified Bit, Birty Bit)๊ฐ€ ์‚ฌ์šฉ๋จ
      • ์ฐธ์กฐ ๋น„ํŠธ: ํŽ˜์ด์ง€๊ฐ€ ์ฐธ์กฐ๋˜์ง€ ์•Š์•˜์„ ๋•Œ 0, ํ˜ธ์ถœ๋˜์—ˆ์„ ๋•Œ 1 (๋ชจ๋“  ์ฐธ์กฐ๋น„ํŠธ๋ฅผ ์ฃผ๊ธฐ์ ์œผ๋กœ 0์œผ๋กœ ๋ณ€๊ฒฝ)
      • ๋ณ€ํ˜• ๋น„ํŠธ: ํŽ˜์ด์ง€ ๋‚ด์šฉ์ด ๋ณ€๊ฒฝ๋˜์ง€ ์•Š์•˜์„ ๋•Œ๋Š” 0, ๋ณ€๊ฒฝ๋˜์—ˆ์„ ๋•Œ 1
    • ์šฐ์„ ์ˆœ์œ„: ์ฐธ์กฐ๋น„ํŠธ > ๋ณ€ํ˜•๋น„ํŠธ

     

     

    ์ฐธ๊ณ 
    https://liveyourit.tistory.com/235
    https://medium.com/pocs/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-page-replacement-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-650d58ae266b
    NUR
    https://j2wooooo.tistory.com/121
    https://eunhyejung.github.io/os/2018/07/24/operatingsystem-study15.html

    ๋Œ“๊ธ€

Maybe a whole cake ? ๐ŸŽ‚ HAHA!