[OS] Concurrency: Deadlock & Starvation

seunghyunยท2023๋…„ 3์›” 7์ผ
0

๐Ÿ’ป

๋ชฉ๋ก ๋ณด๊ธฐ
4/16

concurrency (๋™์‹œ์„ฑ)

2๊ฐœ ์ด์ƒ์˜ ์Šค๋ ˆ๋“œ (ํ˜น์€ ํ”„๋กœ์„ธ์Šค)๊ฐ€ ๋™์‹œ์— ์‹คํ–‰๋˜๋Š” ์ƒํƒœ์ด๋‹ค.
1๊ฐœ์˜ CPU๊ฐ€ ์—ฌ๋Ÿฌ ์Šค๋ ˆ๋“œ๋ฅผ ๋ฒˆ๊ฐˆ์•„ ์‹คํ–‰ํ•  ๋•Œ ๋‚˜ํƒ€๋‚œ๋‹ค.

parallelism (๋ณ‘๋ ฌ์„ฑ)

2๊ฐœ ์ด์ƒ์˜ ์Šค๋ ˆ๋“œ๊ฐ€ ์„œ๋กœ ๋‹ค๋ฅธ CPU ์ƒ์—์„œ ๊ฐ™์€ ์‹œ๊ฐ„์— ๋™์‹œ์— ์‹คํ–‰๋˜๋Š” ๋ณ‘๋ ฌ์„ฑ์ด๋‹ค.


Deadlock

๐Ÿ’ก a set of processes is deadlocked when each process in the set is blocked awaiting an event (or a recource) that can only be triggered (released) by another blocked process in the set

Two general categories of resources

โœ”๏ธ Reusable resource

  • Can be safely used by only one process at a time and is not depleted by that use
  • ex) processors, memorym I/O devices, files, database and semaphores

โœ”๏ธ Consumable resource

  • Can be created (produced) and destroyed (consumed)
  • Typically, there is no limit on the number of consumable resources
  • ex) interrupts, signals, messages, data in I/O buffers

Conditions or Deadlock

๋ฐ๋“œ๋ฝ์ด ๋ฐœ์ƒํ•˜๋Š” ์กฐ๊ฑด!

The first three conditions are necessary but not sufficient conditions for a deadlock.

The fourth condition is actually a consequence of the first three.

Given that the first three condition exist, a sequence of events may occur that lead to an unresolvable circular wait.

โœ”๏ธ Mutual exclusion

  • Only one process may use a resource at a time

โœ”๏ธ Hold and wait

  • A process may hold allocated resources when waiting for the other resources
    • Nothing or All

โœ”๏ธ No preemption

  • No resource can be forcibly removed from a process holding it ๊ฐ•์ œ๋กœ ๋บ์„ ์ˆ˜ ์—†์„ ๋•Œ

โœ”๏ธ Circular wait

  • A closed chain of processes exists such that each process holds at least one resource needed by the next process in the chain

Three Approaches for Deadlocks

๋ฐ๋“œ๋ฝ์„ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•œ 3๊ฐ€์ง€ ๋ฐฉ์•ˆ

โœ”๏ธ Deadlock prevention

  • ๊ฐ€์žฅ ๋ณด์ˆ˜์ ์ด๊ณ  ๋น„ํšจ์œจ์ ์ธ ๋ฐฉ๋ฒ•
  • Adopt a policy that eliminated one of the conditions 1 through 4

โœ”๏ธ Deadlock avoidance

  • ์ค‘๋„
  • Make the appropriate choices dynamically based on the current state of resource allocation

โœ”๏ธ Deadlock detection

  • ๋‚ด๋ฒ„๋ ค๋‘ฌ~ ์ฃผ๊ธฐ์ ์œผ๋กœ ๊ฐ์ง€ํ•˜๊ธฐ
  • Allow the deadlock to occur, attempt to detect the presence of deadlock, and recover if a deadlock is detected

๐Ÿ”— Reference

[KUOCW] ์ตœ๋ฆฐ ๊ต์ˆ˜๋‹˜์˜ ์šด์˜์ฒด์ œ ๊ฐ•์˜๋ฅผ ์ˆ˜๊ฐ•ํ•˜๊ณ  ์ •๋ฆฌํ•œ ๋‚ด์šฉ์ž…๋‹ˆ๋‹ค. ์ž˜๋ชป๋œ ๋‚ด์šฉ์ด ์žˆ๋‹ค๋ฉด ๋Œ“๊ธ€๋กœ ์•Œ๋ ค์ฃผ์‹œ๋ฉด ๊ฐ์‚ฌํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค ๐Ÿ˜Š

profile
๐Ÿ‘ฉ๐Ÿปโ€๐Ÿ’ป๐ŸŽฎ

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