Skip to content

Files

Latest commit

9d05414 ยท Apr 13, 2022

History

History
547 lines (309 loc) ยท 24.6 KB

VirtualMemory2.md

File metadata and controls

547 lines (309 loc) ยท 24.6 KB

Virtual Memory

Page Replacement
Page Replacement Algorithm
Page Frame์˜ ํ• ๋‹น
Page Size์˜ ๊ฒฐ์ •


"๋ฌผ๋ฆฌ์ ์ธ ๋ฉ”๋ชจ๋ฆฌ์˜ ์ฃผ์†Œ ๋ณ€ํ™˜์€ ์šด์˜์ฒด์ œ๊ฐ€ ๊ด€์—ฌํ•˜์ง€ ์•Š๋Š”๋‹ค.ํ•˜์ง€๋งŒ ๊ฐ€์ƒ ๋ฉ”๋ชจ๋ฆฌ์˜ ๊ฒฝ์šฐ์—๋Š” ์šด์˜์ฒด์ œ๊ฐ€ ์ „์ ์œผ๋กœ ๊ด€๋ฆฌํ•œ๋‹ค"

Page Replacement

page fault๊ฐ€ ๋ฐœ์ƒํ–ˆ์„ ๋•Œ disk์— ์žˆ๋Š” page๋ฅผ ๋ฌผ๋ฆฌ์  ๋ฉ”๋ชจ๋ฆฌ(page frame)์— ์ ์žฌํ•ด์•ผํ•œ๋‹ค. ๋งŒ์•ฝ ๋ฌผ๋ฆฌ์  ๋ฉ”๋ชจ๋ฆฌ์— ๋นˆ page frame ๊ณต๊ฐ„์ด ์—†๋‹ค๋ฉด, ๋ฉ”๋ชจ๋ฆฌ์— ์ ์žฌ๋œ page frame๋“ค ์ค‘ ํ•˜๋‚˜๋ฅผ ๊ณจ๋ผ disk๋กœ swap outํ•˜์—ฌ ๋ฉ”๋ชจ๋ฆฌ์— ๋นˆ page frame ๊ณต๊ฐ„์„ ํ™•๋ณดํ•˜๋Š” ๊ฒƒ์„ page replacement ๋ผ๊ณ  ํ•œ๋‹ค.

  • page replacement๋Š” ์šด์˜์ฒด์ œ๊ฐ€ ๋‹ด๋‹นํ•˜๊ณ  ์žˆ๋‹ค.
  • page replacement๋ฅผ ํ•  ๋•Œ, ๊ณง๋ฐ”๋กœ ์‚ฌ์šฉ๋˜์ง€ ์•Š์€ page๋ฅผ swap outํ•˜๋Š” ๊ฒƒ์ด ๋ฐ”๋žŒ์งํ•˜๋‹ค.

Untitled.png

  1. swap outํ•  page frame์ธ victim์„ ๊ฒฐ์ •ํ•˜๊ณ  disk๋กœ swap outํ•œ๋‹ค.
    • ๋งŒ์•ฝ victim์œผ๋กœ ์„ ํƒ๋œ page frame์˜ ๋‚ด์šฉ์ด ๋ณ€๊ฒฝ๋˜์—ˆ๋‹ค๋ฉด, ๋ณ€๊ฒฝ๋œ ๋‚ด์šฉ์„ ๋ฉ”๋ชจ๋ฆฌ์—์„œ backing store(swap area)์— ๋ฐ˜์˜(write)ํ•ด์•ผํ•œ๋‹ค.
    • ๋ณ€๊ฒฝ๋œ ๋‚ด์šฉ์ด ์—†๋‹ค๋ฉด victim์„ swap out๋งŒ ํ•ด์ค€๋‹ค.
  2. swap out๋œ victim page frame์˜ page table entry์˜ bit๋ฅผ invalid๋กœ ๋ณ€๊ฒฝํ•œ๋‹ค.
  3. empty page frame์— ์ƒˆ๋กœ์šด page๋ฅผ ์ ์žฌํ•œ๋‹ค.
  4. ์ƒˆ๋กญ๊ฒŒ ๋ฉ”๋ชจ๋ฆฌ์— ์ ์žฌ๋œ page์— ๋Œ€ํ•ด page frame number๋ฅผ page table์— ์ž‘์„ฑํ•˜๊ณ  bit๋ฅผ valid ๋กœ ๋ณ€๊ฒฝํ•œ๋‹ค.

Page Replacement Algorithm

Page Replacement Algorithm(ํŽ˜์ด์ง€ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜)์ด๋ž€ page replacement๋ฅผ ์ˆ˜ํ–‰ํ•  ๋•Œ, page fault rate์„ ์ตœ์†Œํ™”ํ•  ์ˆ˜ ์žˆ๋Š” victim page๋ฅผ ์„ ํƒํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.


Replacement ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์„ฑ๋Šฅ

page reference string์„ ๋ณด๊ณ  ์„ ํƒํ•œ replacement ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ page fault rate์„ ๊ตฌํ•˜์—ฌ ์„ฑ๋Šฅ์„ ํ‰๊ฐ€ํ•œ๋‹ค.


Page Reference String ์ด๋ž€?

page reference string์ด๋ž€ ์‹œ๊ฐ„ ์ˆœ์„œ์— ๋”ฐ๋ผ ์ฐธ์กฐ๋œ page ๋ฒˆํ˜ธ๋“ค์˜ ๋‚˜์—ด์„ ์˜๋ฏธํ•œ๋‹ค.

Untitled


๐Ÿ“Œ Optimal Algorithm

๋ฏธ๋ž˜์— ์ฐธ์กฐ๋  page ๋ฒˆํ˜ธ(page reference string)๋ฅผ ๋ฏธ๋ฆฌ ์•Œ๊ณ  ์žˆ๋‹ค๋Š” ๊ฐ€์ •์ด ์ „์ œ๋œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ๊ฐ€์žฅ ๋จผ ๋ฏธ๋ž˜์— ์ฐธ์กฐ๋  page๋ฅผ ๊ต์ฒดํ•œ๋‹ค.

  • page fault rate์ด ๊ฐ€์žฅ ์ž‘์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.
  • ์‹ค์ œ ์‹œ์Šคํ…œ์—์„œ ์‚ฌ์šฉ๋  ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์— Offline Optimal Algorithm์œผ๋กœ ๋ถ€๋ฅธ๋‹ค. (Beladyโ€™s optimal algorithm, MIN, OPT ๋ผ๊ณ ๋„ ๋ถˆ๋ฆฐ๋‹ค)

๋™์ž‘ ๋ฐฉ์‹

Untitled

  1. 1, 2, 3, 4๋ฒˆ ํŽ˜์ด์ง€๋ฅผ ์ฐธ์กฐํ•  ๊ฒฝ์šฐ page fault๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค. (๋นจ๊ฐ„์ƒ‰์€ page fault๊ฐ€ ๋‚ฌ์Œ์„ ์˜๋ฏธํ•œ๋‹ค)

  2. 1, 2๋ฒˆ์ด ๋‹ค์‹œ ์ฐธ์กฐ๋œ๋‹ค โ†’ hit! (์—ฐ๋ณด๋ผ์ƒ‰์€ ์ฐธ์กฐํ•  page๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ์— ์žˆ์Œ์„ ์˜๋ฏธํ•œ๋‹ค)

  3. 5๋ฒˆ์ด ์ฐธ์กฐ๋˜์ง€๋งŒ ๋ฉ”๋ชจ๋ฆฌ์— ์—†๊ณ (page fault), ๋น„์–ด์žˆ๋Š” page frame์ด ์—†๋‹ค

    ํ˜„์žฌ ์‹œ์  ์ดํ›„ ๋ฏธ๋ž˜์˜ page reference string (1 2 3 4 )์„ ์ฐธ๊ณ ํ•˜์—ฌ ๊ฐ€์žฅ ๋จผ ๋ฏธ๋ž˜์— ์ฐธ์กฐ๋  page๋ฅผ ๊ต์ฒดํ•œ๋‹ค . โ†’ 1, 2, 3, 4 ์ค‘ ๊ฐ€์žฅ ๋จผ ๋ฏธ๋ž˜์— ์ฐธ์กฐ๋˜๋Š” 4๋ฒˆ page๋ฅผ swap outํ•˜๊ณ  ๊ทธ ์ž๋ฆฌ์— 5๋ฒˆ page๋ฅผ ์ ์žฌํ•œ๋‹ค.


Optimal ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํŽ˜์ด์ง€ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ฑ๋Šฅ์˜ upper bound๋ฅผ ์ œ๊ณตํ•œ๋‹ค.

Optimal ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๊ฒฝ์šฐ ์ฃผ์–ด์ง„ page reference string์— ๋Œ€ํ•ด ์ด 6๋ฒˆ์˜ page fault๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค. ๋™์ผํ•œ page referene string์— ๋Œ€ํ•ด ๋ชจ๋“  ํŽ˜์ด์ง€ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•ด๋„ page fault๊ฐ€ 6๋ฒˆ ๋ณด๋‹ค ๋งŽ์ด ๋ฐœ์ƒํ•œ๋‹ค

  • Optimal ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋‹ค๋ฅธ ํŽ˜์ด์ง€ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค์˜ ์„ฑ๋Šฅ์— ๋Œ€ํ•œ upper bound ๋ฅผ ์ œ๊ณตํ•œ๋‹ค. (Optimal ์•Œ๊ณ ๋ฆฌ์ฆ˜๋ณด๋‹ค ์„ฑ๋Šฅ์ด ์ข‹์€ ํŽ˜์ด์ง€ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋งŒ๋“ค ์ˆ˜ ์—†๋‹ค๋Š” ์˜๋ฏธ)

๐Ÿ“Œ FIFO(First In First Out) Algorithm

๋จผ์ € swap in๋œ page๋ฅผ ๋จผ์ € swap outํ•˜๋Š” page ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.


๋™์ž‘ ๋ฐฉ์‹

Untitled


FIFO Anomaly : More Frames โ‰  Less Page Fault

page frame์„ ๋Š˜๋ ค์ฃผ๋ฉด ๋ณดํ†ต์˜ ํŽ˜์ด์ง€ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์„ฑ๋Šฅ์€ ์ข‹์•„์ง€๋งŒ FIFO ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์˜คํžˆ๋ ค ์„ฑ๋Šฅ์ด ์ €ํ•˜๋œ๋‹ค (9 page fault โ†’ 10 page fault). ์ด๋Ÿฌํ•œ ๊ธฐ์ดํ•œ ํ˜„์ƒ์„ FIFO Anomaly(Belady's Anomaly)๋ผ๊ณ  ํ•œ๋‹ค.


๐Ÿ“Œ LRU(Least Recently Used) Algorithm

๊ฐ€์žฅ ๋œ ์ตœ๊ทผ์— ์‚ฌ์šฉ๋œ(=๊ฐ€์žฅ ์˜ค๋ž˜ ์ „์— ์ฐธ์กฐ๋œ) page๋ฅผ ๋จผ์ € swap outํ•˜๋Š” page ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

  • ๊ฐ€์žฅ ์ตœ๊ทผ์— ์ฐธ์กฐ๋œ ํŽ˜์ด์ง€๊ฐ€ ๊ฐ€๊นŒ์šด ๋ฏธ๋ž˜์— ์ฐธ์กฐ๋  ๊ฐ€๋Šฅ์„ฑ์ด ๋†’๋‹ค๊ณ  ํŒ๋‹จํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

FIFO ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ LRU ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์ฐจ์ด์ 

FIFO๋Š” ๊ฐ€์žฅ ๋จผ์ € ๋“ค์–ด์˜จ page๋ฅผ ๋จผ์ € swap outํ•œ๋‹ค. 1๋ฒˆ์งธ๋กœ ๋“ค์–ด์˜จ page๋Š” ์ตœ๊ทผ๊นŒ์ง€ ์ฐธ์กฐํ–ˆ์Œ์—๋„ ๋ถˆ๊ตฌํ•˜๊ณ  swap out ๋Œ€์ƒ์ด ๋œ๋‹ค.

LRU๋Š” ๊ฐ€์žฅ ์˜ค๋ž˜์ „์— ์‚ฌ์šฉ๋œ page๋ฅผ swap outํ•œ๋‹ค. 1๋ฒˆ์งธ๋กœ ๋“ค์–ด์˜จ page๋ฅผ ๊ฐ€์žฅ ์ตœ๊ทผ์— ์ฐธ์กฐํ–ˆ๋‹ค๋ฉด swap out ๋Œ€์ƒ์—์„œ ์ œ์™ธ๋œ๋‹ค(๋ฉ€์–ด์ง„๋‹ค)


๋™์ž‘ ๋ฐฉ์‹

Untitled

  1. 1, 2, 3, 4๋ฒˆ ํŽ˜์ด์ง€๋ฅผ ์ฐธ์กฐํ•  ๊ฒฝ์šฐ page fault๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค.

  2. 1, 2๋ฒˆ ํŽ˜์ด์ง€๋ฅผ ๋‹ค์‹œ ์ฐธ์กฐํ•œ๋‹ค โ†’ ์ด๋ฏธ ๋ฉ”๋ชจ๋ฆฌ์— ์ ์žฌ๋˜์–ด ์žˆ๋‹ค!(hit)

  3. 5๋ฒˆ ํŽ˜์ด์ง€๋ฅผ ์ฐธ์กฐํ•œ๋‹ค โ†’ page fault ๋ฐœ์ƒ โ†’ victim page๋ฅผ ์„ ํƒํ•ด์•ผ ํ•œ๋‹ค.

    OPT ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ ๋‹ค๋ฅด๊ฒŒ LRU๋Š” Online Replacement Algorithm์ด๋ฏ€๋กœ ๊ณผ๊ฑฐ page reference string(3 4 1 2)์„ ์ฐธ๊ณ ํ•˜์—ฌ vicim page๋ฅผ ์„ ํƒํ•ด์•ผํ•œ๋‹ค.

    ๊ฐ€์žฅ ์ตœ๊ทผ์— ์‚ฌ์šฉ๋œ ์ˆœ์„œ๋Š” 2 โ†’ 1 โ†’ 4 โ†’ 3 ์ด๋ฏ€๋กœ victim page๋Š” 3๋ฒˆ ํŽ˜์ด์ง€์ด๋‹ค. (FIFO ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๊ฒฝ์šฐ ๊ฐ€์žฅ ๋จผ์ € ๋“ค์–ด์˜จ 1๋ฒˆ ํŽ˜์ด์ง€๊ฐ€ victim์ด ๋œ๋‹ค.)


๐Ÿ“Œ LFU(Least Frequently Used) Algorithm

์ฐธ์กฐ ํšŸ์ˆ˜(reference count)๊ฐ€ ๊ฐ€์žฅ ์ ์€ page๋ฅผ swap outํ•˜๋Š” page ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

  • ๊ณผ๊ฑฐ์— ์ฐธ์กฐ ํšŸ์ˆ˜๊ฐ€ ๋งŽ์€ ํŽ˜์ด์ง€๋Š” ๋ฏธ๋ž˜์—๋„ ์ฐธ์กฐ๋  ๊ฐ€๋Šฅ์„ฑ์ด ๋†’๋‹ค๊ณ  ํŒ๋‹จํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

์ตœ์ € ์ฐธ์กฐ ํšŸ์ˆ˜๋ฅผ ๊ฐ€์ง„ page๊ฐ€ ์—ฌ๋Ÿฌ๊ฐœ ์žˆ๋‹ค๋ฉด?

LFU ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž์ฒด๋Š” ์ตœ์ € ์ฐธ์กฐ ํšŸ์ˆ˜๋ฅผ ๊ฐ€์ง„ ์—ฌ๋Ÿฌ page๋“ค ์ค‘ ์ž„์˜๋กœ victim page๋ฅผ ์„ ์ •ํ•œ๋‹ค.

  • ์„ฑ๋Šฅ ํ–ฅ์ƒ์„ ์œ„ํ•ด ์ตœ์ € ์ฐธ์กฐ ํšŸ์ˆ˜์˜ page๋“ค ์ค‘ ๊ฐ€์žฅ ์˜ค๋ž˜์ „์— ์ฐธ์กฐ๋œ page๋ฅผ victim์œผ๋กœ ์„ ์ •ํ•˜๋„๋ก ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค.

์žฅ๋‹จ์ 

์žฅ์ 

  • LRU ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ง์ „์˜ ์ฐธ์กฐ ์‹œ์ ๋งŒ ํ™•์ธํ•˜์ง€๋งŒ LFU๋Š” ์žฅ๊ธฐ์ ์ธ ์‹œ๊ฐ„ ๊ทœ๋ชจ๋ฅผ ํ™•์ธํ•˜์—ฌ victim์„ ์„ ์ •ํ•˜๊ธฐ ๋•Œ๋ฌธ์— page์˜ ์ธ๊ธฐ๋„(์ฐธ์กฐ ํšŸ์ˆ˜)๋ฅผ ์ •ํ™•ํžˆ ๋ฐ˜์˜ํ•  ์ˆ˜ ์žˆ๋‹ค.

๋‹จ์ 

  • LFU๋Š” ์ฐธ์กฐ ์‹œ์ ์˜ ์ตœ๊ทผ์„ฑ์„ ๋ฐ˜์˜ํ•˜์ง€ ๋ชปํ•œ๋‹ค. (๊ฐ€๊นŒ์šด ํ˜„์žฌ์—๋Š” ๊ฑฐ์˜ ์ฐธ์กฐ๋˜์ง€ ์•Š๋Š” page์ผ ์ง€๋ผ๋„ ๊ณผ๊ฑฐ์— ๋งŽ์ด ์ฐธ์กฐ๋˜์—ˆ๋‹ค๋ฉด victim์œผ๋กœ ์„ ์ •๋  ๊ฐ€๋Šฅ์„ฑ์ด ์ ๋‹ค)
  • LFU์•Œ๊ณ ๋ฆฌ์ฆ˜์€ LRU์•Œ๊ณ ๋ฆฌ์ฆ˜๋ณด๋‹ค ๊ตฌํ˜„์ด ๋ณต์žกํ•˜๋‹ค.

LRU vs LFU

Untitled.png

page frame์€ 4๊ฐœ๊ฐ€ ์žˆ๊ณ , page reference string์€ 1 1 1 1 2 2 3 3 2 4 5 ์ด๋‹ค. ์ด๋•Œ 1,2,3,4๋ฒˆ ํŽ˜์ด์ง€์—์„œ victim์„ ์„ ํƒํ•ด์•ผํ•œ๋‹ค.

  • LRU : 1๋ฒˆ ํŽ˜์ด์ง€๋ฅผ swap outํ•œ๋‹ค

    ํ˜„์žฌ ์‹œ์ ์„ ๊ธฐ์ค€์œผ๋กœ ๊ฐ€์žฅ ์ตœ๊ทผ์— ์‚ฌ์šฉ๋œ ํŽ˜์ด์ง€์˜ ์ˆœ์„œ๋Š” **4 โ†’ 2 โ†’ 3 โ†’ 1** ์ด๋ฏ€๋กœ 1๋ฒˆ ํŽ˜์ด์ง€๋ฅผ swap out ํ•œ๋‹ค.

    • ๋‹จ์  : LRU๋Š” ๊ฐ€์žฅ ๋งˆ์ง€๋ง‰ ์ฐธ์กฐ ์‹œ์ ๋งŒ ๊ณ ๋ คํ•˜๊ธฐ ๋•Œ๋ฌธ์— ํŽ˜์ด์ง€์˜ ์ด ์ฐธ์กฐ ํšŸ์ˆ˜๋ฅผ ๊ณ ๋ คํ•˜์ง€ ๋ชปํ•œ๋‹ค.
  • LFU : 4๋ฒˆ ํŽ˜์ด์ง€๋ฅผ swap outํ•œ๋‹ค

    1, 2, 3, 4๋ฒˆ ํŽ˜์ด์ง€์˜ ์ฐธ์กฐ ํšŸ์ˆ˜๋Š” ๊ฐ๊ฐ 4, 3, 2, 1๋ฒˆ์ด๋‹ค. ๋”ฐ๋ผ์„œ ๊ฐ€์žฅ ์ฐธ์กฐ ํšŸ์ˆ˜๊ฐ€ ์ ์€ 4๋ฒˆ ํŽ˜์ด์ง€๋ฅผ swap outํ•œ๋‹ค.

    • ๋‹จ์  : ์ฐธ์กฐ ํšŸ์ˆ˜๋งŒ ๊ณ ๋ คํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋ฏธ๋ž˜์— ์ฐธ์กฐ๋  ๊ฐ€๋Šฅ์„ฑ์„ ๊ณ ๋ คํ•˜์ง€ ๋ชปํ•œ๋‹ค.

LRU์™€ LFU ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๊ตฌํ˜„

Untitled.png

  • LRU โ†’ LinkedList : O(1)

    ํŽ˜์ด์ง€๋“ค์„ ์ฐธ์กฐ ์‹œ๊ฐ„ ์ˆœ์„œ์— ๋”ฐ๋ผ LinkedList ํ˜•ํƒœ๋กœ ์ค„์„ ์„ธ์šด๋‹ค. (์œ„์—์„œ ์•„๋ž˜๋กœ ๊ฐˆ ์ˆ˜๋ก ์ฐธ์กฐ ์‹œ์ ์ด ์ตœ๊ทผ์ด๋‹ค.)

    • page๊ฐ€ ์žฌ์ฐธ์กฐ๋œ๋‹ค๋ฉด

      ์ฐธ์กฐ ์‹œ์ ์ด ๊ฐ€์žฅ ์ตœ๊ทผ์ด ๋˜๋ฏ€๋กœ ํ•ด๋‹น page๋ฅผ LinkedList์˜ ๋งจ ๋์œผ๋กœ ์ด๋™์‹œํ‚จ๋‹ค. โ†’ O(1)

    • victim page๋ฅผ ์„ ํƒํ•œ๋‹ค๋ฉด

      LinkedList์˜ ๊ฐ€์žฅ ์œ„์— ์œ„์น˜ํ•œ page๋ฅผ ์„ ํƒํ•˜๋ฉด ๋œ๋‹ค. โ†’ O(1) (LRU ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ victim page๋ฅผ ์„ ํƒํ•  ๋•Œ ๋น„๊ต ์—ฐ์‚ฐ์ด ํ•„์š”์—†๋‹ค)

  • LFU โ†’ Heap : O(logN)

    LFU ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ LinkedList๋กœ ๊ตฌํ˜„ํ•  ์ˆ˜ ์—†๋‹ค.

    • page๊ฐ€ ์žฌ์ฐธ์กฐ ๋œ๋‹ค๋ฉด

      Untitled

      ์ฐธ์กฐ ํšŸ์ˆ˜๊ฐ€ 1 ์ฆ๊ฐ€๋œ๋‹ค. ์ดํ›„ ๋‚˜๋จธ์ง€ page๋“ค๊ณผ ๊ฐ๊ฐ ๋น„๊ตํ•˜์—ฌ LinkedList๋ฅผ ์žฌ์ •๋ ฌํ•ด์•ผํ•˜๊ธฐ ๋•Œ๋ฌธ์— ์ตœ์•…์˜ ๊ฒฝ์šฐ O(N) ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.

    ๋”ฐ๋ผ์„œ LFU ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ Heap์œผ๋กœ ๊ตฌํ˜„ํ•œ๋‹ค. (์ฐธ์กฐ ํšŸ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ์ ์€ page๊ฐ€ root ๋…ธ๋“œ์— ์œ„์น˜ํ•œ๋‹ค.)

    • page๊ฐ€ ์žฌ์ฐธ์กฐ๋œ๋‹ค๋ฉด

      ์ฐธ์กฐ ํšŸ์ˆ˜๊ฐ€ 1 ์ฆ๊ฐ€๋œ๋‹ค. ์ดํ›„ heapify๋ฅผ ํ†ตํ•ด Heap์„ ์žฌ๊ตฌ์„ฑํ•œ๋‹ค โ†’ O(logN)

    • victim page๋ฅผ ์„ ํƒํ•œ๋‹ค๋ฉด

      root ๋…ธ๋“œ์— ์œ„์น˜ํ•œ page๋ฅผ ์„ ํƒํ•˜๋ฉด ๋œ๋‹ค. โ†’ O(1)

      ๊ทธ๋ฆฌ๊ณ  heapify๋ฅผ ํ†ตํ•ด Heap์„ ์žฌ๊ตฌ์„ฑํ•œ๋‹ค โ†’ O(logN)


๐ŸคจํŽ˜์ด์ง• ์‹œ์Šคํ…œ์—์„œ LRU, LFU ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ ์šฉํ•  ์ˆ˜ ์žˆ์„๊นŒ?

์บ์‹ฑ ๊ธฐ๋ฒ•์ด๋ž€?

์บ์‹ฑ ๊ธฐ๋ฒ• ์ด๋ž€ ํ•œ์ •๋œ ๋น ๋ฅธ ๊ณต๊ฐ„(์บ์‹œ)์— ์š”์ฒญ๋œ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•ด ๋‘์—ˆ๋‹ค๊ฐ€ ํ›„์† ์š”์ฒญ์‹œ ์บ์‹œ์— ์ €์žฅ๋œ ๋ฐ์ดํ„ฐ๋ฅผ ์„œ๋น„์Šคํ•˜๋Š” ๊ธฐ๋ฒ•์ด๋‹ค.

์บ์‹ฑ ๊ธฐ๋ฒ•์€ paging ์‹œ์Šคํ…œ, cache memory, buffer caching, web caching ๋“ฑ ๋‹ค์–‘ํ•œ ๋ถ„์•ผ์—์„œ ์‚ฌ์šฉ๋œ๋‹ค.

  • CPU - cache memory - ๋ฉ”์ธ๋ฉ”๋ชจ๋ฆฌ : CPU์™€ ๋ฉ”์ธ๋ฉ”๋ชจ๋ฆฌ ์‚ฌ์ด์— ์กด์žฌํ•˜๋Š” ๊ณ„์ธต์œผ๋กœ CPU๊ฐ€ ๋ฉ”์ธ๋ฉ”๋ชจ๋ฆฌ์— ์ง์ ‘ ์š”์ฒญํ•˜๊ธฐ ์ „์— cache memory์— ์š”์ฒญํ•œ ๋ฐ์ดํ„ฐ๊ฐ€ ์กด์žฌํ•˜๋Š”์ง€ ํ™•์ธํ•œ๋‹ค.
  • ํŒŒ์ผ์‹œ์Šคํ…œ - buffer caching - Disk : ํŒŒ์ผ์‹œ์Šคํ…œ์—์„œ Read, Write ์š”์ฒญ์„ ๋น ๋ฅด๊ฒŒ ์ œ๊ณตํ•˜๊ธฐ ์œ„ํ•œ ์บ์‹ฑ ๊ธฐ๋ฒ•์ด๋‹ค.(paging ์‹œ์Šคํ…œ๊ณผ ๋™์ผํ•˜๊ฒŒ ๋น ๋ฅธ ๋งค์ฒด๋ฅผ cache๋กœ ์—ฌ๊ธฐ๊ณ , ๋А๋ฆฐ ๋งค์ฒด๋ฅผ disk๋กœ ์—ฌ๊ธด๋‹ค)
  • ์›น ํด๋ผ์ด์–ธํŠธ- web caching - ์›น ์„œ๋ฒ„: ์›น ํŽ˜์ด์ง€์— ๋Œ€ํ•œ ์š”์ฒญ์„ web cache์— ์ €์žฅํ•ด ๋‘์–ด ๋™์ผํ•œ ์š”์ฒญ์„ ํ•˜๋ฉด ์ €์žฅํ•œ ๊ฒฐ๊ณผ๋ฅผ ์ œ๊ณตํ•œ๋‹ค.

์บ์‹œ ์šด์˜์— ์‹œ๊ฐ„ ์ œ์•ฝ์ด ์žˆ๋‹ค.

paging ์‹œ์Šคํ…œ์€ ๋ฉ”๋ชจ๋ฆฌ๋ผ๋Š” ํ•œ์ •๋˜๊ณ  ๋น ๋ฅธ ๊ณต๊ฐ„์— ์š”์ฒญ๋œ page๋ฅผ ์ €์žฅํ•ด๋‘๊ณ , ๋ฉ”๋ชจ๋ฆฌ๊ฐ€ ๊ฐ€๋“์ฐผ๋‹ค๋ฉด Replacement ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ํ†ตํ•ด page๋ฅผ ๊ต์ฒดํ•œ๋‹ค.

Replacement ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” ๊ณง ์บ์‹œ ์šด์˜ ์‹œ๊ฐ„์„ ๊ฒฐ์ •ํ•˜๊ณ  ์บ์‹œ ์šด์˜์—๋Š” ์‹œ๊ฐ„์  ์ œ์•ฝ์ด ์žˆ๋‹ค. ๋‹ค์‹œ๋งํ•ด, Replacement ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ ์‚ญ์ œํ•  ํ•ญ๋ชฉ์„ ๊ฒฐ์ •ํ•˜๋Š” ์ž‘์—…์ด ์˜ค๋ž˜ ๊ฑธ๋ฆฐ๋‹ค๋ฉด ์‹ค์ œ ์‹œ์Šคํ…œ์—์„œ ์‚ฌ์šฉํ•  ์ˆ˜ ์—†๋‹ค.

  • buffer caching, web caching์˜ ๊ฒฝ์šฐ O(1) ~ O(logN) ๋ฒ”์œ„์˜ ์‹œ๊ฐ„๋ณต์žก๋„๊นŒ์ง€ ํ—ˆ์šฉํ•œ๋‹ค.

paging ์‹œ์Šคํ…œ์—์„œ LRU, LFU ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ ์šฉํ•  ์ˆ˜ ์žˆ์„๊นŒ? โ†’ NO

Untitled.png

CPU๊ฐ€ ๋งค์ˆœ๊ฐ„๋งˆ๋‹ค ํ”„๋กœ์„ธ์ŠคA์˜ ๋ช…๋ น์–ด์„ ์ˆ˜ํ–‰ํ•˜๊ธฐ ์œ„ํ•ด ๋…ผ๋ฆฌ์  ์ฃผ์†Œ๋ฅผ ๋ฌผ๋ฆฌ์  ์ฃผ์†Œ๋กœ ๋ณ€ํ™˜ํ•ด์•ผ ํ•œ๋‹ค.

  1. page table์—์„œ ๋ช…๋ น์–ด๊ฐ€ ํฌํ•จ๋œ page๊ฐ€ valid/invalidํ•œ์ง€ ํ™•์ธํ•œ๋‹ค.
  2. validํ•˜๋ฉด ๋ฌผ๋ฆฌ์  ๋ฉ”๋ชจ๋ฆฌ์— ์žˆ๋Š” page frame์˜ ์ •๋ณด๋ฅผ CPU๋กœ ์ฝ์–ด ๋“ค์ธ๋‹ค. (์ด ๋•Œ ์ฃผ์†Œ๋ณ€ํ™˜์€ ์šด์˜์ฒด์ œ๊ฐ€ ๊ด€์—ฌํ•˜์ง€ ์•Š๊ณ  ์˜ค๋กœ์ง€ ํ•˜๋“œ์›จ์–ด์ ์œผ๋กœ ์ผ์–ด๋‚œ๋‹ค.)
  3. invalidํ•˜๋ฉด page fault๋กœ ์ธํ•ด trap์ด ๋ฐœ์ƒํ•œ๋‹ค. CPU ์ œ์–ด๊ถŒ์ด ํ”„๋กœ์„ธ์Šค์—์„œ ์šด์˜์ฒด์ œ๋กœ ๋„˜์–ด๊ฐ€๊ณ , disk IO๋ฅผ ํ†ตํ•ด disk์— ์žˆ๋Š” page๋ฅผ ๋ฌผ๋ฆฌ์  ๋ฉ”๋ชจ๋ฆฌ์— ์ ์žฌํ•œ ๋’ค, ํ•„์š”์— ๋”ฐ๋ผ replacement ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ˆ˜ํ–‰๋˜๊ณ  page frame์˜ ์ •๋ณด๋ฅผ CPU๋กœ ์ฝ์–ด ๋“ค์ธ๋‹ค.

์—ฌ๊ธฐ์„œ replacement ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ˆ˜ํ–‰ํ•˜๋Š” ์ฃผ์ฒด๋Š” ์šด์˜์ฒด์ œ์ด๋‹ค

  • LRU ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•œ๋‹ค๋ฉด ์šด์˜์ฒด์ œ๋Š” page๋“ค์˜ ์ฐธ์กฐ ์‹œ์ ๋ฅผ ๊ธฐ๋ฐ˜์œผ๋กœ victim page๋ฅผ ์„ ํƒํ•ด์•ผํ•œ๋‹ค.
  • LFU ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•œ๋‹ค๋ฉด ์šด์˜์ฒด์ œ๋Š” page๋“ค์˜ ์ฐธ์กฐ ํšŸ์ˆ˜๋ฅผ ๊ธฐ๋ฐ˜์œผ๋กœ victim page๋ฅผ ์„ ํƒํ•ด์•ผํ•œ๋‹ค.

์ด ๋•Œ, ๋ฌธ์ œ์ ์€ ์šด์˜์ฒด์ œ๊ฐ€ page์˜ ์ฐธ์กฐ ์‹œ์ ์ด๋‚˜ ์ฐธ์กฐ ํšŸ์ˆ˜๋ฅผ ์™„๋ฒฝํ•˜๊ฒŒ ์•Œ ์ˆ˜ ์—†๋‹ค๋Š” ๊ฒƒ์ด๋‹ค.

  • page fault๊ฐ€ ๋ฐœ์ƒํ•˜๋ฉด

    CPU ์ œ์–ด๊ถŒ์ด ์šด์˜์ฒด์ œ๋กœ ๋„˜์–ด๊ฐ€๊ธฐ ๋•Œ๋ฌธ์— disk์—์„œ page๋ฅผ ๋ฉ”๋ชจ๋ฆฌ๋กœ swap inํ•˜๊ธฐ ๋•Œ๋ฌธ์— page์˜ ์ ‘๊ทผ ์‹œ์ ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

  • ๋ฐ˜๋ฉด์— ์ฐธ์กฐํ•˜๋ ค๋Š” page๊ฐ€ validํ•œ ๊ฒฝ์šฐ์—๋Š”

    CPU ์ œ์–ด๊ถŒ์ด ์šด์˜์ฒด์ œ๋กœ ๋„˜์–ด๊ฐ€์ง€ ์•Š๊ณ  ํ•˜๋“œ์›จ์–ด์ ์œผ๋กœ๋งŒ ์ฃผ์†Œ ๋ณ€ํ™˜์ด ์ด๋ฃจ์–ด์ง€๊ธฐ ๋•Œ๋ฌธ์— ํ•ด๋‹น page์— ๋Œ€ํ•œ ์ ‘๊ทผ ์‹œ์ ์„ ์šด์˜์ฒด์ œ๊ฐ€ ์•Œ ์ˆ˜ ์—†๋‹ค.


์ฆ‰, paging ์‹œ์Šคํ…œ(virtual memory ์‹œ์Šคํ…œ)์—์„œ ์šด์˜์ฒด์ œ๋Š” page์— ๋Œ€ํ•ด ๋ฐ˜์ชฝ์งœ๋ฆฌ ์ •๋ณด๋งŒ ์•Œ๊ธฐ ๋•Œ๋ฌธ์— LRU, LFU ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‹ค์ œ paging ์‹œ์Šคํ…œ์—์„œ ์‚ฌ์šฉํ•  ์ˆ˜ ์—†๋‹ค. (buffer caching, web caching์—์„œ๋Š” ์‚ฌ์šฉ ๊ฐ€๋Šฅ)

๊ทธ๋ž˜์„œ ์‹ค์ œ paging ์‹œ์Šคํ…œ์—์„œ๋Š” LRU, LFU๋Œ€์‹  Clock ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•œ๋‹ค.


๐Ÿ“Œ Clock Algorithm

Untitled

Clock ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ reference bit๊ฐ€ 0์ธ page๋ฅผ ์ฐพ์„ ๋•Œ๊นŒ์ง€ ํฌ์ธํ„ฐ๋ฅผ ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ํ•œ์นธ์”ฉ ์ด๋™ํ•˜์—ฌ ๊ต์ฒดํ•  page๋ฅผ ๊ณ ๋ฅด๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. (LRU์˜ ๊ทผ์‚ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ์„œ Second chance ์•Œ๊ณ ๋ฆฌ์ฆ˜, NUR(Not Used Recently), NRU(Not Recently Used) ๋“ฑ์œผ๋กœ ๋ถˆ๋ฆฐ๋‹ค.)

  • ํฌ์ธํ„ฐ๋ฅผ ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ์ด๋™ํ•˜๋ฉด์„œ reference bit๊ฐ€ 1์ธ ๊ฒƒ์„ ๋ชจ๋‘ 0์œผ๋กœ ๋ฐ”๊พผ๋‹ค.
    • page์˜ reference bit๋ฅผ ์ˆ˜์ •ํ•˜๋Š” ์ž‘์—…์€ ์šด์˜์ฒด์ œ๊ฐ€ ์•„๋‹Œ ํ•˜๋“œ์›จ์–ด๋กœ ์ˆ˜ํ–‰๋œ๋‹ค.
  • ํ•œ ๋ฐ”ํ€ด๋ฅผ ๋˜๋Œ์•„์™€์„œ๋„(second chance) ํ•ด๋‹น page์˜ reference bit๊ฐ€ 0์ด๋ฉด ๊ต์ฒด๋œ๋‹ค.

Clock ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๊ฐœ์„ ๋ฐฉ์‹ : reference bit์™€ modified bit(dirty bit)

  • reference bit = 1 : ์ตœ๊ทผ์— ์ฐธ์กฐ๋œ(Read๋œ) ํŽ˜์ด์ง€๋ผ๋Š” ์˜๋ฏธ์ด๋‹ค.
  • modified bit = 1 : ์ตœ๊ทผ์— ๋ณ€๊ฒฝ๋œ(Write๋œ) ํŽ˜์ด์ง€๋ผ๋Š” ์˜๋ฏธ์ด๋‹ค.

reference bit๊ฐ€ 0์ธ ํŽ˜์ด์ง€๋ฅผ swap outํ•  ๋•Œ, ๋งŒ์•ฝ modified bit๊ฐ€ 1์ด๋ฉด backing store(swap area)์— ๋ณ€๊ฒฝ๋œ ๋‚ด์šฉ์„ ๋ฐ˜์˜ํ•ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— Disk IO๊ฐ€ ๋™๋ฐ˜๋œ๋‹ค.

๋”ฐ๋ผ์„œ reference bit๊ฐ€ 0์ด๋ฉด์„œ modified bit๊ฐ€ 0์ธ ํŽ˜์ด์ง€๋ฅผ ์šฐ์„ ์ ์œผ๋กœ swap outํ•˜๋Š”๊ฒŒ ํšจ์œจ์ ์ด๋‹ค.


๋™์ž‘ ๋ฐฉ์‹

Untitled

  • ๊ฐ ์‚ฌ๊ฐํ˜•์€ ๋ฌผ๋ฆฌ์  ๋ฉ”๋ชจ๋ฆฌ์— ์ ์žฌ๋œ page frame์ด๋‹ค
  • CPU๊ฐ€ ํŠน์ • page๋ฅผ ์ฐธ์กฐํ•˜๊ฒŒ ๋˜๋ฉด ํ•˜๋“œ์›จ์–ด์— ์˜ํ•ด ํ•ด๋‹น page์˜ reference bit๊ฐ€ 1๋กœ ์„ธํŒ…๋œ๋‹ค.
  • ์šด์˜์ฒด์ œ๋Š” ํฌ์ธํ„ฐ๋ฅผ ์ด๋™ํ•˜๋ฉด์„œ page์˜ reference bit๋ฅผ ํ™•์ธํ•œ๋‹ค.
    • reference bit = 1์ด๋ฉด, reference bit๋ฅผ 0์œผ๋กœ ์„ธํŒ…ํ•˜๊ณ  ๋‹ค์Œ page์˜ reference bit๋ฅผ ๊ฒ€์‚ฌํ•œ๋‹ค.

    • second chance์˜ ๊ฒฝ์šฐ (ํ•œ ๋ฐ”ํ€ด ๋˜๋Œ์•„์˜จ ๊ฒฝ์šฐ) reference bit = 0์ด๋ฉด, ํ•ด๋‹น page๋ฅผ swap outํ•œ๋‹ค.

      ์ด ๋•Œ, modified bit๊ฐ€ 0์ด๋ฉด ๊ทธ๋ƒฅ swap out ํ•˜์ง€๋งŒ, 1์ด๋ฉด ๋ณ€๊ฒฝ๋œ ๋‚ด์šฉ์„ backing store์— ๋ฐ˜์˜ํ•ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— Disk IO๊ฐ€ ๋™๋ฐ˜๋˜์–ด ์˜ค๋ฒ„ํ—ค๋“œ๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค. ๋”ฐ๋ผ์„œ modified bit๊ฐ€ 1์ด๋ฉด ํ•ด๋‹น page๋ฅผ swap outํ•˜์ง€ ์•Š๊ณ  modified bit๋ฅผ 0์œผ๋กœ ๋ณ€๊ฒฝํ•œ๋‹ค.


Page Frame์˜ ํ• ๋‹น

ํ”„๋กœ๊ทธ๋žจ์„ ์›ํ™œํ•˜๊ฒŒ ์‹คํ–‰ํ•˜๊ธฐ ์œ„ํ•ด์„œ page fault๋ฅผ ์ ๊ฒŒ ๋ฐœ์ƒํ•˜๋ฉด์„œ ์ผ๋ จ์˜ ํŽ˜์ด์ง€๋“ค์„ ๋ฉ”๋ชจ๋ฆฌ์— ๋™์‹œ์— ์ ์žฌ๋˜๋Š”๊ฒŒ ์ค‘์š”ํ•˜๋‹ค. ๊ฒฐ๊ตญ ๊ฐ ํ”„๋กœ์„ธ์Šค์— ํ• ๋‹น๋˜๋Š” page frame์˜ ์ˆ˜๊ฐ€ ์›ํ™œํ•œ ํ™˜๊ฒฝ์„ ๊ฒฐ์ •์ง“๋Š”๋‹ค.

์ด ๋•Œ ํ”„๋กœ์„ธ์Šค์—๊ฒŒ page frame์„ ์–ผ๋งˆ๋งŒํผ ํ• ๋‹นํ•  ๊ฒƒ์ธ์ง€์— ๋Œ€ํ•œ ๋ฌธ์ œ๋ฅผ Allocation Problem ์ด๋ผ๊ณ  ํ•œ๋‹ค.


Allocation(ํ• ๋‹น)์ด ์™œ ํ•„์š”ํ• ๊นŒ?

CPU๋Š” ํ•˜๋‚˜์˜ ๋ช…๋ น์„ ์‹คํ–‰ํ•  ๋•Œ ํ”„๋กœ์„ธ์Šค์˜ ์ฃผ์†Œ ๊ณต๊ฐ„ ์ค‘ code, data, stack์ด๋ผ๋Š” ๊ฐ๊ธฐ ๋‹ค๋ฅธ ์˜์—ญ์„ ์ฐธ์กฐํ•œ๋‹ค. ๋‹ค์‹œ ๋งํ•ด, CPU๋Š” ๋ช…๋ น์„ ์‹คํ–‰ํ•  ๋•Œ ์—ฌ๋Ÿฌ ํŽ˜์ด์ง€๋ฅผ ๋™์‹œ์— ์ฐธ์กฐํ•œ๋‹ค. ๊ทธ๋ ‡๊ธฐ ๋•Œ๋ฌธ์— ์›ํ™œํ•œ ๋ช…๋ น์–ด ์ˆ˜ํ–‰์„ ์œ„ํ•ด ํ• ๋‹น๋˜์–ด์•ผ ํ•  ์ตœ์†Œ page frame ์ˆ˜๊ฐ€ ์กด์žฌํ•œ๋‹ค.

  • ์˜ˆ๋ฅผ ๋“ค์–ด, ๋ฐ˜๋ณต๋ฌธ์„ ๊ตฌ์„ฑํ•˜๋Š” ํŽ˜์ด์ง€๋“ค์„ ํ•˜๋‚˜์˜ ์ตœ์†Œ ํ• ๋‹น๋Ÿ‰์œผ๋กœ ๊ฐ„์ฃผํ•˜์—ฌ ํ•œ๊บผ๋ฒˆ์— ๋ฉ”๋ชจ๋ฆฌ์— ํ• ๋‹น๋˜๋Š” ๊ฒƒ์ด ์œ ๋ฆฌํ•˜๋‹ค. ๋งŒ์•ฝ ์ตœ์†Œํ•œ์˜ ํ• ๋‹น๋Ÿ‰์ด ์ •ํ•ด์ง€์ง€ ์•Š๋Š”๋‹ค๋ฉด, ๋งค loop๋งˆ๋‹ค page fault๊ฐ€ ๋ฐœ์ƒํ•  ์ˆ˜ ์žˆ๋‹ค.

    for ๋ฌธ์„ ๊ตฌ์„ฑํ•˜๋Š” ํŽ˜์ด์ง€๊ฐ€ 3๊ฐœ์ผ ๋•Œ, page frame์„ 3๊ฐœ ํ• ๋‹นํ•˜๋ฉด ๋ฐ˜๋ณต๋ฌธ์ด ์‹คํ–‰๋˜๋Š” ๋™์•ˆ page fault๊ฐ€ ๋ฐœ์ƒํ•˜์ง€ ์•Š๋Š”๋‹ค. ํ•˜์ง€๋งŒ 2๊ฐœ์˜ page frame์„ ํ• ๋‹นํ•˜๋ฉด ์‹คํ–‰๋  ๋•Œ๋งˆ๋‹ค page fault๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค.


Page Frame Allocation Algorithm

  1. Equal Allocation(๊ท ๋“ฑ ํ• ๋‹น) : ๋ชจ๋“  ํ”„๋กœ์„ธ์Šค์—๊ฒŒ page frame์„ ๊ท ์ผํ•˜๊ฒŒ ํ• ๋‹นํ•œ๋‹ค
  2. Proportional Allocation(๋น„๋ก€ ํ• ๋‹น) : ํ”„๋กœ์„ธ์Šค ํฌ๊ธฐ์— ๋น„๋ก€ํ•˜์—ฌ page frame์„ ํ• ๋‹นํ•œ๋‹ค
  3. Priority Allocation(์šฐ์„ ์ˆœ์œ„ ํ• ๋‹น) : ํ”„๋กœ์„ธ์Šค์˜ ์šฐ์„ ์ˆœ์œ„์— ๋”ฐ๋ผ page frame์„ ๋‹ค๋ฅด๊ฒŒ ํ• ๋‹นํ•œ๋‹ค(๋‹น์žฅ CPU์—์„œ ์‹คํ–‰๋  ํ”„๋กœ์„ธ์Šค์™€ ๊ทธ๋ ‡์ง€ ์•Š์€ ํ”„๋กœ์„ธ์Šค๋กœ ๊ตฌ๋ถ„ํ•œ๋‹ค)

์œ„์™€ ๊ฐ™์€ page frame ํ• ๋‹น ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ page fault ๋ฐœ์ƒ๋ฅ ์ด ์ตœ์†Œํ™” ๋  ์ˆ˜ ์žˆ๋„๋ก page frame์„ ํ• ๋‹นํ•ด์•ผ ํ•œ๋‹ค. ํ•˜์ง€๋งŒ Replacement ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜๋‹ค ๋ณด๋ฉด ์ €์ ˆ๋กœ page fault๋ฅผ ์ตœ์†Œํ™”ํ•˜๋Š” ๋ฐฉํ–ฅ์œผ๋กœ page frame์ด ํ• ๋‹น๋˜๋Š” ํšจ๊ณผ๊ฐ€ ์žˆ๋‹ค.

Global Replacement vs Local Replacement

  • Global Replacement : ํŽ˜์ด์ง€ ๊ต์ฒด ์‹œ ๋‹ค๋ฅธ ํ”„๋กœ์„ธ์Šค์—๊ฒŒ ํ• ๋‹น๋œ page frame์„ swap outํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.
    • ์—ฌ๋Ÿฌ ํ”„๋กœ์„ธ์Šค๋“ค๊ณผ ๊ฒฝ์Ÿํ•˜์—ฌ page frame์„ ๋งŽ์ด ๊ฐ€์งˆ ๋•Œ๋„ ์žˆ๊ณ , ์ ๊ฒŒ ๊ฐ€์งˆ ๋•Œ๋„ ์žˆ๋‹ค.
    • FIFO, LRU, LFU, Working Set, PFF ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜๋ฉด Global Replacement ๋ฐฉ์‹์œผ๋กœ ๋™์ž‘ํ•œ๋‹ค.
  • Local Replacement : ํŽ˜์ด์ง€ ๊ต์ฒด ์‹œ ํ”„๋กœ์„ธ์Šค์—๊ฒŒ ํ• ๋‹น๋œ page frame ๋‚ด์—์„œ victim page๋ฅผ ๊ณจ๋ผ swap outํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.
    • ํ”„๋กœ์„ธ์Šค์— page frame์ด ๊ณ ์ •์ ์œผ๋กœ ํ• ๋‹น๋œ๋‹ค.
    • FIFO, LRU, LFU ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ํ”„๋กœ์„ธ์Šค ๋ณ„๋กœ ์šด์˜ํ•  ๋•Œ Local Replacement ๋ฐฉ์‹์œผ๋กœ ๋™์ž‘ํ•œ๋‹ค.

๐Ÿงฉ Thrashing

ํ”„๋กœ์„ธ์Šค์˜ ์›ํ™œํ•œ ์ˆ˜ํ–‰์— ํ•„์š”ํ•œ ์ตœ์†Œํ•œ์˜ page frame์„ ํ• ๋‹น ๋ฐ›์ง€ ๋ชปํ•œ ๊ฒฝ์šฐ Thrashing ์ด ๋ฐœ์ƒํ•œ๋‹ค.

Untitled

X์ถ•์€ ๋ฉ”๋ชจ๋ฆฌ์— ๋™์‹œ ์˜ฌ๋ผ์™€ ์žˆ๋Š” ํ”„๋กœ๊ทธ๋žจ์˜ ๊ฐœ์ˆ˜(degree of multiprogramming)์ด๊ณ , Y์ถ•์€ CPU ์ด์šฉ๋ฅ (CPU utilization)์ด๋‹ค.

  1. ๋ฉ”๋ชจ๋ฆฌ์— ํ”„๋กœ๊ทธ๋žจ ํ•˜๋‚˜๋งŒ ์˜ฌ๋ผ์™€ ์žˆ์œผ๋ฉด CPU ์ด์šฉ๋ฅ ์ด ๋Œ€๋‹จํžˆ ๋‚ฎ๋‹ค.

    ํ”„๋กœ๊ทธ๋žจ์ด CPU๋ฅผ ์‚ฌ์šฉํ•˜๋‹ค๊ฐ€ IO ์ž‘์—…์„ ํ•˜๋ฉด blocked ์ƒํƒœ๊ฐ€ ๋˜์–ด CPU ์ž์›์€ ์ž‰์—ฌ ์ƒํƒœ๊ฐ€ ๋˜๊ธฐ ๋•Œ๋ฌธ์— CPU ์ด์šฉ๋ฅ ์ด ๋‚ฎ๋‹ค.

  2. ๋ฉ”๋ชจ๋ฆฌ์— ํ”„๋กœ๊ทธ๋žจ์ด ์—ฌ๋Ÿฌ ๊ฐœ ์˜ฌ๋ผ์™€ ์žˆ๋‹ค๋ฉด CPU ์ด์šฉ๋ฅ ์ด ๋†’๋‹ค.

    ์ผ๋ฐ˜์ ์œผ๋กœ ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ผ์™€ ์žˆ๋Š” ํ”„๋กœ๊ทธ๋žจ์˜ ์ˆ˜์— ๋”ฐ๋ผ CPU ์ด์šฉ๋ฅ ์ด ์ฆ๊ฐ€ํ•œ๋‹ค.

  3. ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ผ์™€ ์žˆ๋Š” ํ”„๋กœ๊ทธ๋žจ์˜ ์ˆ˜๊ฐ€ ์–ด๋А ์ง€์ ์„ ๋„˜๊ธฐ๋ฉด Thrashing์ด ๋ฐœ์ƒํ•˜์—ฌ CPU ์ด์šฉ๋ฅ ์ด ๋–จ์–ด์ง„๋‹ค.


Thrashing์˜ ๊ตด๋ ˆ

๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ผ์™€ ์žˆ๋Š” ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋งŽ์•„์ง€๋ฉด

โ†’ ๊ฐ ํ”„๋กœ์„ธ์Šค์—๊ฒŒ page frame์ด ์ ๊ฒŒ ํ• ๋‹น๋˜์–ด page fault๊ฐ€ ๋นˆ๋ฒˆํžˆ ๋ฐœ์ƒํ•œ๋‹ค

โ†’ ์ด๋Š” CPU ์ด์šฉ๋ฅ ์„ ๋‚ฎ์ถ”๊ณ 

โ†’ ์šด์˜์ฒด์ œ๋Š” ๋‚ฎ์€ CPU ์ด์šฉ๋ฅ ์„ ๋ณด๊ณ  MPD(Multiprogramming Degree)๋ฅผ ๋†’ํžˆ๊ธฐ ์œ„ํ•ด ๋ฉ”๋ชจ๋ฆฌ์— ๋” ๋งŽ์€ ํ”„๋กœ๊ทธ๋žจ์„ ์˜ฌ๋ฆฌ๊ฒŒ ๋œ๋‹ค.

โ†’ ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ผ์˜จ ํ”„๋กœ๊ทธ๋žจ์ด ๋” ๋งŽ์•„์ง€๊ณ 

โ†’ ํ”„๋กœ์„ธ์Šค ๋งˆ๋‹ค ํ• ๋‹น๋œ page frame ์ˆ˜๊ฐ€ ๋”์šฑ ๊ฐ์†Œํ•˜์—ฌ

โ†’ page fault๊ฐ€ ๋งค์šฐ ๋นˆ๋ฒˆํ•ด์ง€๊ณ  swap in/swap out์ด ๋งŽ์•„์ง„๋‹ค (IO์ž‘์—…์ด ๋งŽ์•„์ง„๋‹ค)

โ†’ ๊ฒฐ๊ตญ CPU ์ด์šฉ๋ฅ ์ด ๋‚ฎ์•„์ง€๊ณ 

โ†’ low throughput์„ ์•ผ๊ธฐํ•œ๋‹ค.

์œ„์™€ ๊ฐ™์€ ์•…์ˆœํ™˜์„ Thrashing ์ด๋ผ๊ณ  ํ•œ๋‹ค.


Thrashing ์˜ˆ๋ฐฉ๋ฒ• โ†’ Working-Set Algorithm, PFF(Page-Fault Frequency) Algorithm

MPD(Multiprogramming Degree)๋ฅผ ์กฐ์ ˆํ•˜์—ฌ ๊ฐ ํ”„๋กœ๊ทธ๋žจ์ด ์›ํ™œํ•œ ์ˆ˜ํ–‰์„ ์œ„ํ•œ ์ตœ์†Œํ•œ์˜ page frame์„ ํ™•๋ณดํ•  ์ˆ˜ ์žˆ๋„๋ก ํ•ด์ค˜์•ผ ํ•œ๋‹ค. ์ด๋ฅผ ์œ„ํ•ด Working-Set Algorithm ๋˜๋Š” PFF Algorithm ์ด ํ•„์š”ํ•˜๋‹ค.


๐Ÿงฉ Working-Set Algorithm

Locality of Reference (์ฐธ์กฐ์˜ ์ง€์—ญ์„ฑ)

์ฐธ์กฐ์˜ ์ง€์—ญ์„ฑ์ด๋ž€ ํ”„๋กœ๊ทธ๋žจ์ด ํŠน์ • ์‹œ๊ฐ„ ๋™์•ˆ ๋ฉ”๋ชจ๋ฆฌ์˜ ์ผ์ • ์˜์—ญ๋งŒ ์ง‘์ค‘์ ์œผ๋กœ ์ฐธ์กฐํ•œ๋‹ค๋Š” ํŠน์„ฑ์ด๋‹ค.

  • loop๋ฅผ ์‹คํ–‰ํ•  ๋•Œ, loop๋ฅผ ๊ตฌ์„ฑํ•˜๋Š” page๋งŒ ์ง‘์ค‘์ ์œผ๋กœ ์ฐธ์กฐ๋˜๊ณ  function์„ ์‹คํ–‰ํ•  ๋•Œ, function์„ ๊ตฌ์„ฑํ•˜๋Š” page๋งŒ ์ง‘์ค‘์ ์œผ๋กœ ์ฐธ์กฐ ๋œ๋‹ค.

Locality Set, Working Set

ํŠน์ • ์‹œ๊ฐ„์— ์ง‘์ค‘์ ์œผ๋กœ ์ฐธ์กฐ๋˜๋Š” page๋“ค์˜ ์ง‘ํ•ฉ์„ Locality Set ์ด๋ผ๊ณ  ํ•˜๊ณ , Working-Set Algorithm์—์„œ Locality Set์„ Working Set ์ด๋ผ๊ณ  ๋ถ€๋ฅธ๋‹ค. (์ผ๋ฐ˜์ ์œผ๋กœ Working Set์ด๋ผ๋Š” ์šฉ์–ด๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค)


Working-Set Model

Working Set ๋ชจ๋ธ์—์„œ๋Š” ํ”„๋กœ์„ธ์Šค์˜ Working Set ์ „์ฒด๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ผ์™€ ์žˆ์–ด์•ผ ์ˆ˜ํ–‰๋˜๊ณ , ๊ทธ๋ ‡์ง€ ์•Š์„ ๊ฒฝ์šฐ ๋ชจ๋“  page ์„ ๋ฐ˜๋‚ฉํ•œ ํ›„ swap out(suspended)ํ•˜์—ฌ Thrashing์„ ๋ฐฉ์ง€ํ•œ๋‹ค.

  • ํŠน์ • ํ”„๋กœ๊ทธ๋žจ์˜ Working Set์ด 5๊ฐœ์˜ page์œผ๋กœ ๊ตฌ์„ฑ๋˜๋Š” ๊ฒฝ์šฐ์— ํ• ๋‹น ๊ฐ€๋Šฅํ•œ page์ด 3๊ฐœ ๋ฟ์ด๋ผ๋ฉด, ํ•ด๋‹น ํ”„๋กœ์„ธ์Šค๋Š” ์ „์ฒด page๋ฅผ ๋ฐ˜๋‚ฉํ•˜๊ณ  disk๋กœ swap out๋œ๋‹ค.

Working-Set Algorithm

Untitled

ํŠน์ • ํ”„๋กœ์„ธ์Šค์˜ Working Set์€ ๊ณผ๊ฑฐ๋ฅผ ํ†ตํ•ด ์ถ”์ •ํ•ด์•ผ ํ•œ๋‹ค.

  • ์‹œ๊ฐ Ti์—์„œ์˜ Working Set : WS(Ti) = Time interval [Ti - ฮ”, Ti] ์‚ฌ์ด์— ์ฐธ์กฐ๋œ ์„œ๋กœ ๋‹ค๋ฅธ page๋“ค์˜ ์ง‘ํ•ฉ

    ํ”„๋กœ์„ธ์Šค๊ฐ€ ฮ” (window size)๋งŒํผ์˜ ๊ณผ๊ฑฐ ์‹œ๊ฐ„๋™์•ˆ ์ฐธ์กฐํ•œ page๋“ค์„ Working Set์ด๋ผ ๊ฐ„์ฃผํ•˜์—ฌ Working Set์— ํฌํ•จ๋œ page๋“ค์„ ๋ฉ”๋ชจ๋ฆฌ์—์„œ ์œ ์ง€ํ•˜๊ณ  ํฌํ•จ๋˜์ง€ ์•Š์€ page๋“ค์€ swap out์‹œํ‚จ๋‹ค.

  • Working Set์˜ ํฌ๊ธฐ๋Š” ๋งค๋ฒˆ ๋ฐ”๋€๋‹ค (WS(t1) = {1, 2, 5, 6, 7} โ†’ WS(t2) = {3, 4})

    ๋‹ค์‹œ ๋งํ•ด, ์ฐธ์กฐ๋œ page๋ฅผ ฮ”์‹œ๊ฐ„ ๋งŒํผ๋งŒ ์œ ์ง€ํ•˜๊ณ  swap out ์‹œํ‚จ๋‹ค.

ํ”„๋กœ์„ธ์Šค๋“ค์˜ Working Set size์˜ ํ•ฉ์ด page frame์˜ ์ˆ˜๋ณด๋‹ค ํด ๊ฒฝ์šฐ

  • ์ผ๋ถ€ ํ”„๋กœ์„ธ์Šค๋ฅผ swap out์‹œ์ผœ(MPD๋ฅผ ์ค„์—ฌ์„œ) ๋‚จ์€ ํ”„๋กœ์„ธ์Šค์˜ Working Set์„ ์šฐ์„ ์ ์œผ๋กœ ์ถฉ์กฑ์‹œ์ผœ์ค€๋‹ค.

Working Set์— ํฌํ•จ๋œ page๋“ค์„ ๋‹ค ํ• ๋‹นํ•˜๊ณ ๋„ page frame์ด ๋‚จ๋Š”๋‹ค๋ฉด

  • swap out ๋˜์—ˆ๋˜ ํ”„๋กœ์„ธ์Šค๋“ค์—๊ฒŒ Working Set์„ ํ• ๋‹นํ•˜์—ฌ MPD๋ฅผ ๋†’ํžŒ๋‹ค.

๐Ÿงฉ PFF(Page-Fault Frequency) Algorithm

Untitled

ํŠน์ • ํ”„๋กœ๊ทธ๋žจ์˜ Page Fault Rate์„ ์กฐ์‚ฌํ•˜์—ฌ page frame์„ ๋™์ ์œผ๋กœ ํ• ๋‹นํ•ด์ฃผ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

  • ํ”„๋กœ์„ธ์Šค์˜ page fault rate์ด ๋†’๋‹ค๋ฉด ํ•ด๋‹น ํ”„๋กœ์„ธ์Šค์˜ Working Set์ด ๋ฉ”๋ชจ๋ฆฌ์— ๋ณด์žฅ๋˜์–ด์žˆ์ง€ ์•Š๋‹ค๊ณ  ๊ฐ„์ฃผํ•˜์—ฌ page frame์„ ๋” ํ• ๋‹นํ•ด์ค€๋‹ค.

page fault rate์— ๋Œ€ํ•ด ์ƒํ•œ๊ฐ’(upper bound), ํ•˜ํ•œ๊ฐ’(lower bound)๋ฅผ ๋‘”๋‹ค.

  • ํ•ด๋‹น ํ”„๋กœ์„ธ์Šค์˜ page fault rate์ด ์ƒํ•œ๊ฐ’์„ ๋„˜๊ธฐ๋ฉด page frame์„ ๋” ๋งŽ์ด ํ• ๋‹นํ•ด ์ค€๋‹ค.
  • ํ•ด๋‹น ํ”„๋กœ์„ธ์Šค์˜ page fault rate์ด ํ•˜ํ•œ๊ฐ’ ๋ณด๋‹ค ์ž‘์œผ๋ฉด page frame ์ˆ˜๋ฅผ ์ค„์ธ๋‹ค.

๋ฉ”๋ชจ๋ฆฌ์— ๋นˆ page frame์ด ์—†๋‹ค๋ฉด ์ผ๋ถ€ ํ”„๋กœ์„ธ์Šค๋ฅผ disk๋กœ swap out ์‹œํ‚จ๋‹ค.


Page Size์˜ ๊ฒฐ์ •

paging ์‹œ์Šคํ…œ์—์„œ ํ”„๋กœ์„ธ์Šค์˜ ์ฃผ์†Œ ๊ณต๊ฐ„์„ ๋™์ผํ•œ ํฌ๊ธฐ์˜ page ๋‹จ์œ„๋กœ ์ž๋ฅด๊ณ , ๋ฌผ๋ฆฌ์  ๋ฉ”๋ชจ๋ฆฌ๋„ page์™€ ๋™์ผํ•œ ํฌ๊ธฐ์˜ page frame์œผ๋กœ ์ž๋ฅธ๋‹ค.

page size๊ฐ€ ์ž‘์œผ๋ฉด?

  • page์˜ ๊ฐœ์ˆ˜๊ฐ€ ๋งŽ์•„์ง€๊ณ , page table์˜ ํฌ๊ธฐ๊ฐ€ ์ปค์ง„๋‹ค
  • ๋‚ด๋ถ€ ์กฐ๊ฐ์˜ ๊ฐœ์ˆ˜๊ฐ€ ๊ฐ์†Œํ•œ๋‹ค.
  • ํ•„์š”ํ•œ ์ •๋ณด๋งŒ ๋ฉ”๋ชจ๋ฆฌ์— ์˜ฌ๋ผ๊ฐ€๊ธฐ ๋•Œ๋ฌธ์— ๋ฉ”๋ชจ๋ฆฌ ์ด์šฉ์ด ํšจ์œจ์ ์ด๋‹ค

page size๊ฐ€ ํฌ๋ฉด?

  • Locality ํ™œ์šฉ ์ธก๋ฉด์—์„œ๋Š” page size๊ฐ€ ํด์ˆ˜๋ก ์ข‹๋‹ค.

  • Disk Transfer์˜ ํšจ์œจ์„ฑ ์ธก๋ฉด์—์„œ page size๊ฐ€ ํด์ˆ˜๋ก ์ข‹๋‹ค.

    ํ•œ ๋ฒˆ์˜ ๋””์Šคํฌ ํ—ค๋” ์›€์ง์ž„์œผ๋กœ ๋งŽ์€ ์–‘์˜ ๋‚ด์šฉ์„ ์ฝ์–ด์˜ค๋Š” ๊ฒƒ์ด ์ข‹๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.


์ฐธ๊ณ 

๋ฐ˜ํšจ๊ฒฝ ๊ต์ˆ˜๋‹˜ ์šด์˜์ฒด์ œ ๊ฐ•์˜


๋ฉด์ ‘ ์˜ˆ์ƒ ์งˆ๋ฌธ

ํŽ˜์ด์ง€ ๊ต์ฒด๊ฐ€ ์™œ ํ•„์š”ํ•œ๊ฐ€์š”?

ํŽ˜์ด์ง€ ๊ต์ฒด ์•Œ๊ณ ๋ฆฌ์ฆ˜์—๋Š” ๋ฌด์—‡์ด ์žˆ๋‚˜์š”? ๊ฐ๊ฐ์˜ ํŠน์ง•์€?

FIFO์™€ LRU์˜ ์ฐจ์ด์ ์€ ๋ฌด์—‡์ธ๊ฐ€์š”?

LRU์™€ LFU์„ ๋น„๊ตํ•ด๋ณด์„ธ์š”. LRU์™€ LFU ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์–ด๋–ป๊ฒŒ ๊ตฌํ˜„๋˜์—ˆ๋Š”์ง€ ์•„์‹œ๋‚˜์š”? ๊ฐ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๋งํ•ด๋ณด์„ธ์š”

ํŽ˜์ด์ง• ์‹œ์Šคํ…œ์—์„œ LRU, LFU ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ ์šฉํ•  ์ˆ˜ ์žˆ๋‚˜์š”? ๊ทธ ์ด์œ ๋Š”? ๊ทธ๋Ÿผ ์–ด๋–ค ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ํŽ˜์ด์ง• ์‹œ์Šคํ…œ์— ์ ์šฉํ• ๊นŒ์š”?

Clock ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๋™์ž‘๋ฐฉ์‹์„ ๋งํ•ด์ฃผ์„ธ์š”

Thrashing์ด ๋ฌด์—‡์ธ๊ฐ€์š”? ์ด๋ฅผ ์˜ˆ๋ฐฉํ•˜๋Š” ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด ์„ค๋ช…ํ•ด์ฃผ์„ธ์š”

Page ์‚ฌ์ด์ฆˆ๊ฐ€ ์ž‘์œผ๋ฉด ์–ด๋–ป๊ฒŒ ๋ ๊นŒ์š”? ํฌ๋ฉด ์–ด๋–ป๊ฒŒ ๋ ๊นŒ์š”?