Table of Contents
Operating System Concepts Ch.7 Deadlocks
Ch.6 Synchronization์์ ์ ์ ์ธ๊ธํ๋ฏ์ด ๋ฐ๋๋ฝ์ ํ๋ก์ธ์ค๊ฐ ๋ฆฌ์์ค๋ฅผ ์ ์ ํ๊ณ ๋์์ฃผ์ง ์๊ฑฐ๋, ์ด๋ ํ ํ๋ก์ธ์ค๋ ๋ฆฌ์์ค๋ฅผ ์ ์ ํ์ง ๋ชปํ๋ ์ํ๊ฐ ๋์ด ํ๋ก๊ทธ๋จ์ด ๋ฉ์ถ๋ ํ์์ ๋งํ๋ค.
System Model
ํ๋ก์ธ์ค๋ ๋ค์๊ณผ ๊ฐ์ ํ๋ฆ์ผ๋ก ๋ฆฌ์์ค๋ฅผ ์ด์ฉํ๋ค.
- Request: ๋ฆฌ์์ค๋ฅผ ์์ฒญํ๋ค. ๋ง์ฝ ๋ค๋ฅธ ํ๋ก์ธ์ค๊ฐ ๋ฆฌ์์ค๋ฅผ ์ฌ์ฉ์ค์ด๋ผ์ ๋ฆฌ์์ค๋ฅผ ๋ฐ์ ์ ์๋ค๋ฉด ๋๊ธฐํ๋ค.
- Use: ํ๋ก์ธ์ค๋ ๋ฆฌ์์ค ์์์ ์ํ๋๋ค.
- 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
๋ง์ฝ ์์คํ ์ด ๋ฐ๋๋ฝ์ ๋ฐฉ์งํ๊ฑฐ๋ ํํผํ์ง ๋ชปํ๊ณ , ๋ฐ๋๋ฝ์ด ๋ฐ์ํ๋ค๋ฉด ๋ฐ๋๋ฝ์ผ๋ก๋ถํฐ ๋ณต๊ตฌ๋์ด์ผ ํ๋ค. ์ด๋๋ ์ด๋ค ํ๋ก์ธ์ค๋ฅผ ์ข ๋ฃ์ํฌ์ง ์ ํ๋ ๊ฒ์ด ์ค์ํด์ง๋ค. ์ฌ๊ธฐ์๋ ๋ช๊ฐ์ง ํ๋จ ๊ธฐ์ค์ด ์๋ค:
- ํ๋ก์ธ์ค์ ์ค์๋
- ํ๋ก์ธ์ค๊ฐ ์ผ๋ง๋ ์ค๋ ์คํ๋๋๊ฐ
- ์ผ๋ง๋ ๋ง์ ๋ฆฌ์์ค๋ฅผ ์ฌ์ฉํ๋๊ฐ
- ํ๋ก์ธ์ค๊ฐ ์์ ์ ๋ง์น๊ธฐ ์ํด ์ผ๋ง๋ ๋ง์ ๋ฆฌ์์ค๊ฐ ํ์ํ๊ฐ
- ํ๋ก์ธ์ค๊ฐ ์ข ๋ฃ๋๊ธฐ ์ํด ์ผ๋ง๋ ๋ง์ ๋ฆฌ์์ค๊ฐ ํ์ํ๊ฐ
- ํ๋ก์ธ์ค๊ฐ batch์ธ๊ฐ interactiveํ๊ฐ
Resource Preemption
๋ฐ๋๋ฝ์ ํด๊ฒฐํ๊ธฐ ์ํด ๋ฆฌ์์ค ์ ์ (Preemption) ๋ฐฉ์์ ์ฌ์ฉํ ๋๋ ๋ค์๊ณผ ๊ฐ์ ์ด์๊ฐ ์๋ค.
- Selecting a victim: ์ด๋ค ํ๋ก์ธ์ค๋ฅผ ์ข ๋ฃ์ํฌ ์ง ๊ฒฐ์ ํ๋ค.
- Rollback: ๋ฐ๋๋ฝ์ด ๋ฐ์ํ๊ธฐ ์ ์ํ๋ก ๋๋๋ฆฐ๋ค.
- Starvation: ๊ณ์ ๊ฐ์ ํ๋ก์ธ์ค๊ฐ victim์ด ๋ ์ ์๋ค. ์ด ๊ฒฝ์ฐ ๊ธฐ์(Starvation) ๋ฌธ์ ๊ฐ ๋ฐ์ํ๋ค.