๐Ÿฆ• ๊ณต๋ฃก์ฑ…์œผ๋กœ ์ •๋ฆฌํ•˜๋Š” ์šด์˜์ฒด์ œ Ch.7

Deadlocks

Operating System Concepts Ch.7 Deadlocks

Ch.6 Synchronization์—์„œ ์ž ์‹œ ์–ธ๊ธ‰ํ–ˆ๋“ฏ์ด ๋ฐ๋“œ๋ฝ์€ ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋ฆฌ์†Œ์Šค๋ฅผ ์ ์œ ํ•˜๊ณ  ๋†“์•„์ฃผ์ง€ ์•Š๊ฑฐ๋‚˜, ์–ด๋– ํ•œ ํ”„๋กœ์„ธ์Šค๋„ ๋ฆฌ์†Œ์Šค๋ฅผ ์ ์œ ํ•˜์ง€ ๋ชปํ•˜๋Š” ์ƒํƒœ๊ฐ€ ๋˜์–ด ํ”„๋กœ๊ทธ๋žจ์ด ๋ฉˆ์ถ”๋Š” ํ˜„์ƒ์„ ๋งํ•œ๋‹ค.

System Model

ํ”„๋กœ์„ธ์Šค๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ํ๋ฆ„์œผ๋กœ ๋ฆฌ์†Œ์Šค๋ฅผ ์ด์šฉํ•œ๋‹ค.

  1. Request: ๋ฆฌ์†Œ์Šค๋ฅผ ์š”์ฒญํ•œ๋‹ค. ๋งŒ์•ฝ ๋‹ค๋ฅธ ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋ฆฌ์†Œ์Šค๋ฅผ ์‚ฌ์šฉ์ค‘์ด๋ผ์„œ ๋ฆฌ์†Œ์Šค๋ฅผ ๋ฐ›์„ ์ˆ˜ ์—†๋‹ค๋ฉด ๋Œ€๊ธฐํ•œ๋‹ค.
  2. Use: ํ”„๋กœ์„ธ์Šค๋Š” ๋ฆฌ์†Œ์Šค ์œ„์—์„œ ์ˆ˜ํ–‰๋œ๋‹ค.
  3. Release: ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋ฆฌ์†Œ์Šค๋ฅผ ๋†“์•„์ค€๋‹ค.

Deadlock Characterization

๋ฐ๋“œ๋ฝ์€ ๋‹ค์Œ 4๊ฐ€์ง€ ์ƒํ™ฉ์„ ๋งŒ์กฑํ•ด์•ผ ๋ฐœ์ƒํ•œ๋‹ค.

  • Mutual exclusion: ์—ฌ๋Ÿฌ ํ”„๋กœ์„ธ์Šค ์ค‘ ํ•˜๋‚˜๋งŒ critical section์— ์ง„์ž…ํ•  ์ˆ˜ ์žˆ์„ ๋•Œ.
  • Hold and wait: ํ”„๋กœ์„ธ์Šค ํ•˜๋‚˜๊ฐ€ ๋ฆฌ์†Œ์Šค๋ฅผ ์žก๊ณ  ์žˆ๊ณ , ๋‹ค๋ฅธ ๊ฒƒ์€ ๋Œ€๊ธฐ์ค‘์ผ ๋•Œ.
  • No preemption: OS๊ฐ€ ์ž‘๋™์ค‘์ธ ํ”„๋กœ์„ธ์Šค๋ฅผ ์ž„์˜๋กœ ์ค‘๋‹จ์‹œํ‚ฌ ์ˆ˜ ์—†์„ ๋•Œ.
  • Circular wait: ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ˆœํ™˜์ ์œผ๋กœ ์„œ๋กœ๋ฅผ ๊ธฐ๋‹ค๋ฆด ๋•Œ.

๋งŒ์•ฝ ์œ„ ์กฐ๊ฑด ์ค‘ ํ•˜๋‚˜๋งŒ ๋งŒ์กฑ๋˜์ง€ ์•Š์•„๋„ ๋ฐ๋“œ๋ฝ์€ ๋ฐœ์ƒํ•˜์ง€ ์•Š๋Š”๋‹ค.

Resource Allocation Graph

ํ”„๋กœ์„ธ์Šค ๊ฐ„์˜ ๊ด€๊ณ„๋ฅผ ๊ทธ๋ž˜ํ”„๋กœ ๋„์‹ํ™”ํ•ด ๋ณด๋ฉด ๋ฐ๋“œ๋ฝ์ด ๋ฐœ์ƒํ• ์ง€ ์˜ˆ์ƒํ•  ์ˆ˜ ์žˆ๋‹ค. ๋งŒ์•ฝ ๊ทธ๋ž˜ํ”„์— ์ˆœํ™˜ ๊ณ ๋ฆฌ๊ฐ€ ์žˆ๋‹ค๋ฉด ๋ฐ๋“œ๋ฝ ์œ„ํ—˜์ด ์žˆ๋‹ค๋Š” ์˜๋ฏธ๊ฐ€ ๋œ๋‹ค. ์ˆœํ™˜ ๊ณ ๋ฆฌ๊ฐ€ ์žˆ๋‹ค๊ณ  ๋ฌด์กฐ๊ฑด ๋ฐ๋“œ๋ฝ์ด ๋ฐœ์ƒํ•˜๋Š” ๊ฒƒ์€ ์•„๋‹ˆ์ง€๋งŒ, ์ˆœํ™˜ ๊ณ ๋ฆฌ๊ฐ€ ์—†์œผ๋ฉด ์ ˆ๋Œ€๋กœ ๋ฐ๋“œ๋ฝ์ด ๋ฐœ์ƒํ•˜์ง€ ์•Š๋Š”๋‹ค.

Methods for Handling Deadlocks

๋ฐ๋“œ๋ฝ์„ ์ œ์–ดํ•˜๋Š” ๋ฐ๋Š” ํฌ๊ฒŒ ๋‘๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด ์žˆ๋Š”๋ฐ, ํ•˜๋‚˜๋Š” ๋ฐ๋“œ๋ฝ์„ ๋ฐฉ์ง€ํ•˜๋Š” ๊ฒƒ์ด๊ณ , ๋˜ ๋‹ค๋ฅธ ํ•˜๋‚˜๋Š” ๋ฐ๋“œ๋ฝ์„ ํ”ผํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

Deadlock Prevention

๋ฐ๋“œ๋ฝ์„ ๋ฐฉ์ง€ํ•œ๋‹ค๋Š” ๊ฒƒ์€ ๋ฐ๋“œ๋ฝ ๋ฐœ์ƒ ์กฐ๊ฑด ์ค‘ ํ•˜๋‚˜๋ฅผ ๋งŒ์กฑ์‹œํ‚ค์ง€ ์•Š์Œ์œผ๋กœ์จ ๋ฐ๋“œ๋ฝ์ด ๋ฐœ์ƒํ•˜์ง€ ์•Š๋„๋ก ํ•˜๋Š” ๊ฒƒ์ด๋‹ค.

  • Mutual Exclusion: critical section problem์„ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ์ด ์กฐ๊ฑด์„ ๋งŒ์กฑํ•ด์•ผ ํ•˜๋ฏ€๋กœ, ๊ณต์œ ๋˜๋Š” ์ž์›์ด ์žˆ๋‹ค๋ฉด ์ด ์กฐ๊ฑด์„ ๋งŒ์กฑ์‹œํ‚ฌ ์ˆ˜ ๋ฐ–์— ์—†๋‹ค.
  • Hold and wait: ํ•œ ํ”„๋กœ์„ธ์Šค๊ฐ€ ์‹คํ–‰๋˜๊ธฐ ์ „ ๋ชจ๋“  ์ž์›์„ ํ• ๋‹น์‹œํ‚ค๊ณ , ์ดํ›„์—๋Š” ๋‹ค๋ฅธ ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ž์›์„ ์š”๊ตฌํ•˜๋„๋ก ํ•œ๋‹ค. starvation ๋ฌธ์ œ๊ฐ€ ์ƒ๊ธธ ์ˆ˜ ์žˆ๋‹ค.
  • No preemption: ๋ฆฌ์†Œ์Šค๋ฅผ ์ ์œ ํ•˜๊ณ  ์žˆ๋Š” ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋‹ค๋ฅธ ๋ฆฌ์†Œ์Šค๋ฅผ ์š”์ฒญํ–ˆ์„ ๋•Œ ์ฆ‰์‹œ ๋ฆฌ์†Œ์Šค๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์—†๋‹ค๋ฉด ์ ์œ ํ•˜๊ณ  ์žˆ๋˜ ๋ฆฌ์†Œ์Šค๋ฅผ releaseํ•œ๋‹ค.
  • Circular wait: ๋ฆฌ์†Œ์Šค์˜ ํƒ€์ž…์— ๋”ฐ๋ผ ํ”„๋กœ์„ธ์Šค๋งˆ๋‹ค ์ผ๋Œ€์ผ ํ•จ์ˆ˜๋กœ ์ˆœ์„œ๋ฅผ ์ง€์ •ํ•ด์ค€๋‹ค.

๋ฐ๋“œ๋ฝ์„ ๋ฐฉ์ง€ํ•˜๋Š” ๊ฒƒ์€ ์žฅ์น˜ ํšจ์œจ๊ณผ ์‹œ์Šคํ…œ ์„ฑ๋Šฅ์„ ๋–จ์–ดํŠธ๋ฆฌ๋Š” ๋ฌธ์ œ๊ฐ€ ์žˆ๋‹ค.

Deadlock Avoidance

๋ฐ๋“œ๋ฝ์„ ํ”ผํ•˜๋Š” ๊ฒƒ์€ ๋ฐ๋“œ๋ฝ์ด ๋ฐœ์ƒํ•  ๊ฒƒ ๊ฐ™์„ ๋•Œ๋Š” ์•„์˜ˆ ๋ฆฌ์†Œ์Šค๋ฅผ ํ• ๋‹นํ•˜์ง€ ์•Š๋Š” ๊ฒƒ์ด๋‹ค. ์—ฌ๊ธฐ์„œ๋Š” ์‹œ์Šคํ…œ์ด unsafe ์ƒํƒœ๊ฐ€ ๋˜์ง€ ์•Š๋„๋ก ํ•ด์•ผ ํ•˜๋ฉฐ, ๋งŒ์•ฝ unsafe ์ƒํƒœ๊ฐ€ ๋˜๋ฉด ์ตœ๋Œ€ํ•œ ๋นจ๋ฆฌ safe ์ƒํƒœ๋กœ ๋ณต๊ตฌํ•œ๋‹ค. ๋ฐ๋“œ๋ฝ ๊ฐ€๋Šฅ์„ฑ์€ ํฌ์ธํ„ฐ๋กœ ์ž์› ํ• ๋‹น ๊ทธ๋ž˜ํ”„(Resource allocation graph)๋ฅผ ๊ตฌํ˜„ํ•ด ํŒ๋‹จํ•œ๋‹ค. ๋งŒ์•ฝ ๋ฆฌ์†Œ์Šค ํƒ€์ž…์ด ์—ฌ๋Ÿฌ ๊ฐœ๋ผ๋ฉด bankerโ€™s algorithm์„ ์‚ฌ์šฉํ•œ๋‹ค.

Bankerโ€™s Algorithm

bankerโ€™s algorithm์€ Dijkstra๊ฐ€ ๊ณ ์•ˆํ•œ ๋ฐ๋“œ๋ฝ ํšŒํ”ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ์ด๋Š” ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋ฆฌ์†Œ์Šค๋ฅผ ์š”์ฒญํ•  ๋•Œ๋งˆ๋‹ค ์ˆ˜ํ–‰๋˜๋ฉฐ, ๋งŒ์•ฝ ๋ฆฌ์†Œ์Šค๋ฅผ ํ• ๋‹นํ–ˆ์„ ๋•Œ ๋ฐ๋“œ๋ฝ์ด ๋ฐœ์ƒํ•˜๋Š”์ง€ ์‹œ๋ฎฌ๋ ˆ์ด์…˜ํ•œ๋‹ค.

Recovery from Deadlock

๋งŒ์•ฝ ์‹œ์Šคํ…œ์ด ๋ฐ๋“œ๋ฝ์„ ๋ฐฉ์ง€ํ•˜๊ฑฐ๋‚˜ ํšŒํ”ผํ•˜์ง€ ๋ชปํ–ˆ๊ณ , ๋ฐ๋“œ๋ฝ์ด ๋ฐœ์ƒํ–ˆ๋‹ค๋ฉด ๋ฐ๋“œ๋ฝ์œผ๋กœ๋ถ€ํ„ฐ ๋ณต๊ตฌ๋˜์–ด์•ผ ํ•œ๋‹ค. ์ด๋•Œ๋Š” ์–ด๋–ค ํ”„๋กœ์„ธ์Šค๋ฅผ ์ข…๋ฃŒ์‹œํ‚ฌ์ง€ ์ •ํ•˜๋Š” ๊ฒƒ์ด ์ค‘์š”ํ•ด์ง„๋‹ค. ์—ฌ๊ธฐ์—๋Š” ๋ช‡๊ฐ€์ง€ ํŒ๋‹จ ๊ธฐ์ค€์ด ์žˆ๋‹ค:

  1. ํ”„๋กœ์„ธ์Šค์˜ ์ค‘์š”๋„
  2. ํ”„๋กœ์„ธ์Šค๊ฐ€ ์–ผ๋งˆ๋‚˜ ์˜ค๋ž˜ ์‹คํ–‰๋๋Š”๊ฐ€
  3. ์–ผ๋งˆ๋‚˜ ๋งŽ์€ ๋ฆฌ์†Œ์Šค๋ฅผ ์‚ฌ์šฉํ–ˆ๋Š”๊ฐ€
  4. ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ž‘์—…์„ ๋งˆ์น˜๊ธฐ ์œ„ํ•ด ์–ผ๋งˆ๋‚˜ ๋งŽ์€ ๋ฆฌ์†Œ์Šค๊ฐ€ ํ•„์š”ํ•œ๊ฐ€
  5. ํ”„๋กœ์„ธ์Šค๊ฐ€ ์ข…๋ฃŒ๋˜๊ธฐ ์œ„ํ•ด ์–ผ๋งˆ๋‚˜ ๋งŽ์€ ๋ฆฌ์†Œ์Šค๊ฐ€ ํ•„์š”ํ•œ๊ฐ€
  6. ํ”„๋กœ์„ธ์Šค๊ฐ€ batch์ธ๊ฐ€ interactiveํ•œ๊ฐ€

Resource Preemption

๋ฐ๋“œ๋ฝ์„ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ๋ฆฌ์†Œ์Šค ์„ ์ (Preemption) ๋ฐฉ์‹์„ ์‚ฌ์šฉํ•  ๋•Œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ด์Šˆ๊ฐ€ ์žˆ๋‹ค.

  1. Selecting a victim: ์–ด๋–ค ํ”„๋กœ์„ธ์Šค๋ฅผ ์ข…๋ฃŒ์‹œํ‚ฌ ์ง€ ๊ฒฐ์ •ํ•œ๋‹ค.
  2. Rollback: ๋ฐ๋“œ๋ฝ์ด ๋ฐœ์ƒํ•˜๊ธฐ ์ „ ์ƒํƒœ๋กœ ๋˜๋Œ๋ฆฐ๋‹ค.
  3. Starvation: ๊ณ„์† ๊ฐ™์€ ํ”„๋กœ์„ธ์Šค๊ฐ€ victim์ด ๋  ์ˆ˜ ์žˆ๋‹ค. ์ด ๊ฒฝ์šฐ ๊ธฐ์•„(Starvation) ๋ฌธ์ œ๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค.