

์ธํธ๋ก
์ฐ์ ์์ ์ค์ผ์ค๋ง์์ ์ค์ํ ๋ ๋ค๋ฅธ ๊ฐ๋ ์ ์ฐ์ ์์ ์ญ์ (inversion)/๊ธฐ๋ถ(donation)์ ๋๋ค. ๋ฎ์ ์ฐ์ ์์ ์ค๋ ๋๊ฐ ๋์ ์ฐ์ ์์ ์ค๋ ๋๊ฐ ํ์๋ก ํ๋ ๋ฎคํ ์ค๋ฅผ ํ๋ํ๊ณ ์ค๋ซ๋์ ๋์ง ์์ผ๋ฉด, ๋์ ์ฐ์ ์์ ์ค๋ ๋๋ ๊ณ์ ๊ธฐ๋ค๋ ค์ผ ํ๋ ์ฐ์ ์์ ์ญ์ ๋ฌธ์ ๊ฐ ๋ฐ์ํฉ๋๋ค.
์ด๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ฐ์ ์์ ์์ ๋ฉ์ปค๋์ฆ์ด ์ฌ์ฉ๋ ์ ์์ต๋๋ค. ๋ฎคํ ์ค๋ฅผ ํ๋ํ ๋ฎ์ ์ฐ์ ์์ ์ค๋ ๋๋ ๊ทธ ๋ฎคํ ์ค๋ฅผ ๊ธฐ๋ค๋ฆฌ๋ ๊ฐ์ฅ ๋์ ์ฐ์ ์์ ์ค๋ ๋์ ์ฐ์ ์์๋ฅผ ์ผ์์ ์ผ๋ก ์์๋ฐ์ ์คํ๋ฉ๋๋ค. ๋ฎคํ ์ค๋ฅผ ํด์ ํ๋ฉด ์๋์ ์ฐ์ ์์๋ก ๋์๊ฐ๋๋ค.
๋ค์ด๊ฐ๊ธฐ์ ์์ mutex์ semaphore, condition variable์ ๋ํ ํฌ์คํธ๋ฅผ ์ฝ๊ณ ์์ฃผ์๊ธฐ๋ฅผ ๊ถํด ๋๋ฆฝ๋๋ค.
์ฐ์ ์์ ์ญ์
์๋์ ๊ฐ์ ์ํฉ์ ๊ฐ์ ํฉ์๋ค.

์ฑ๊ธ์ฝ์ด ํ๊ฒฝ์ ๊ธฐ๋ณธ์ ์ธ ์ฐ์ ์์ ์ค์ผ์ค๋ง ์ ์ฑ ์ ์ ์ฉํ๋ OS์์ ์ค๋ ๋ H, M, L์ด๋ผ๋ 3๊ฐ์ ์ค๋ ๋๊ฐ ์๋ค๊ณ ๊ฐ์ ํฉ๋๋ค. ๊ฐ๊ฐ ๋์, ์ค๊ฐ, ๋ฎ์ ์ฐ์ ์์๋ฅผ ๊ฐ์ง๊ณ ์์ต๋๋ค. ์ค๋ ๋ H์ L์ ๋ ๋ค A๋ผ๋ ๊ณต์ ์์์ ์จ์ผ ํฉ๋๋ค (M์ ํด๋น ์์๊ณผ๋ ๋ฌด๊ด).
- ๋จผ์ L์ด ready list์ ๋ค์ด์์ต๋๋ค. ๊ณต์ ์์ A๋ฅผ ์ ๊ทธ๊ณ ์คํ๋ฉ๋๋ค.
- ์ดํ H๊ฐ ready list์ ๋ค์ด์์ต๋๋ค. ์ํ๊น๊ฒ๋ ๊ณต์ ์์ A๋ ์ด๋ฏธ ์ ๊ฒจ ์์ผ๋ฏ๋ก, H๋ block๋ ์ํ๊ฐ ๋ฉ๋๋ค.
- ๊ทธ ๋ค์ M์ด ready list์ ๋ค์ด์์ต๋๋ค. OS ์ค์ผ์ค๋ฌ๋ ๊ทธ ์ฆ์ ์ฐ์ ์์์ ๋ฐ๋ผ CPU ์ ์ด๊ถ์ M์๊ฒ ๋๊น๋๋ค.
- L์ ๋ฏธ์ฒ ์์ ์ ์๋ฃํ์ง ๋ชปํ ์ฑ ๊ณต์ ์์ A๋ฅผ ์ ๊ฐ๋์ ์ํ๊ฐ ๋ฉ๋๋ค.
- H๋ ํ์ํ ๊ณต์ ์์์ ๊ณ์ ์ป์ง ๋ชปํ๋ฏ๋ก ์คํ๋ ์ ์์ต๋๋ค.
- ์ด์ฝ๊ณ M์ ์์ ์ด ์๋ฃ๋ฉ๋๋ค. OS ์ค์ผ์ค๋ฌ๋ CPU ์ ์ด๊ถ์ ๊ณต์ ์์ A๋ฅผ ์๋ ์ ์ ํ๋ L์๊ฒ ๋๊น๋๋ค.
- ์ด์ฝ๊ณ L์ ์์ ์ด ์๋ฃ๋ฉ๋๋ค.
- M๊ณผ L์ด ์๋ฃ๋ ๋ค์์์์ผ ๋น๋ก์ H์ ์์ ์ด ์คํ๋ฉ๋๋ค.
๊ฒฐ๊ณผ์ ์ผ๋ก ์ฐ์ ์์๊ฐ ๊ฑฐ๊พธ๋ก ๋์๊ฐ๋ฒ๋ฆฌ๋ ๋ชจ์์๊ฐ ๋ ๊ฒ์ ๋๋ค. ์ด๋ฌํ ํ์์ ๋ฐ๋ก ์ฐ์ ์์ ์ญ์ ์ด๋ผ๊ณ ํฉ๋๋ค.
์ฐ์ ์์ ๊ธฐ๋ถ
์์ ๊ฐ์ ์ํฉ์ ์ด๋ป๊ฒ ํด๊ฒฐํ ์ ์์๊น์? ๋ฐ๋ก ์ค๋ ๋ H์ ์ฐ์ ์์๋ฅผ ์ค๋ ๋ L์๊ฒ ํ๋ฉํ๋, ๋ง ๊ทธ๋๋ก '์ฐ์ ์์ ๊ธฐ๋ถ'๋ฅผ ํตํด ํด๊ฒฐ ๊ฐ๋ฅํฉ๋๋ค. ์ฐ์ ์์ ๊ธฐ๋ถ๋, ๋ฎคํ ์ค๋ฅผ ํ๋ํ ๋ฎ์ ์ฐ์ ์์ ์ค๋ ๋๋, ๊ทธ ๋ฎคํ ์ค๋ฅผ ๊ธฐ๋ค๋ฆฌ๋ ๊ฐ์ฅ ๋์ ์ฐ์ ์์ ์ค๋ ๋์ ์ฐ์ ์์๋ฅผ ์์๋ก ์์๋ฐ์ ์คํ๋ฉ๋๋ค. ๋ฎคํ ์ค๋ฅผ ํด์ ํ๋ฉด ์๋์ ์ฐ์ ์์๋ก ๋์๊ฐ๋๋ค.
์ ์๋๋ฆฌ์ค๋ก ๋ค์ ์ค๋ช ๋๋ฆฌ๊ฒ ์ต๋๋ค.

- ๋จผ์ L์ด ready list์ ๋ค์ด์์ต๋๋ค. ๊ณต์ ์์ A๋ฅผ ์ ๊ทธ๊ณ ์คํ๋ฉ๋๋ค.
- ์ดํ H๊ฐ ready list์ ๋ค์ด์์ต๋๋ค. ์ํ๊น๊ฒ๋ ๊ณต์ ์์ A๋ ์ด๋ฏธ ์ ๊ฒจ ์์ผ๋ฏ๋ก, H๋ block๋ ์ํ๊ฐ ๋ฉ๋๋ค.
- ๊ทธ ๋ค์ M์ด ready list์ ๋ค์ด์์ต๋๋ค. OS ์ค์ผ์ค๋ฌ๋ ๊ทธ ์ฆ์ ์ค๋ ๋ H์ ์ฐ์ ์์๋ฅผ ์ค๋ ๋ L์ ์ ์ฉ์ํต๋๋ค.
- L์ ๊ณต์ ์์ A๋ฅผ ํ์๋ก ํ๋ ์ค๋ ๋๋ค ์ค ์ต์ฐ์ ์ผ๋ก ์คํ๋์ด, ์ด์ฝ๊ณ ์๋ฃ๋ฉ๋๋ค.
- H๋ ํ์ํ ๊ณต์ ์์์ ํ๋ํ ๋ค ์คํ๋์ด, ์ด์ฝ๊ณ ์๋ฃ๋ฉ๋๋ค.
- ์ด์ฝ๊ณ M์ ์์ ์ด ์๋ฃ๋ฉ๋๋ค.
๋ค์ค ๊ธฐ๋ถ / ์ค์ฒฉ ๊ธฐ๋ถ
์ ์์๋ ๊ณต์ ์์ A ํ๋๋ง ๋๊ณ ๋ณด๊ธฐ์ ๋น๊ต์ ๋จ์ํ์ง๋ง ์ค์ ๋ก๋ ์ฌ๋ฌ ๊ณต์ ์์์ด ์ฝํ๊ณ ์์์ด ๋ค๋จ๊ณ๋ก ์ด๋ฃจ์ด์ง๋๋ค. ์ด๋ฅผ ๊ฐ๊ฐ ๋ค์ค ๊ธฐ๋ถ (multiple donation) ๋ฐ ์ค์ฒฉ ๊ธฐ๋ถ (nested donation)์ด๋ผ๊ณ ํฉ๋๋ค.
์๋์ ๊ฐ์ ์๋๋ฆฌ์ค๋ฅผ ๊ฐ์ ํฉ๋๋ค.
์ค๋ ๋ | ์ฐ์ ์์ | ๋๊ธฐ ์์ |
H | 3 (๋์) | lock A |
M | 2 (์ค๊ฐ) | lock B |
L | 1 (๋ฎ์) | ์์ (A์ B ๋ชจ๋ ๋ณด์ ์ค) |
- ์ค๋ ๋ L์ด ์คํ๋์ด ๋จผ์ lock A์ lock B๋ฅผ ๋ชจ๋ ํ๋ํ๊ณ , ์์ ์ค์ ๋๋ค.
- ์ด๋ ์ค๋ ๋ M์ด ๋ฑ์ฅํฉ๋๋ค. M์ ์์ ์ ์ํด lock B๊ฐ ํ์ํฉ๋๋ค. ํ์ง๋ง lock B๋ ์ด๋ฏธ L์ด ๋ณด์ ํ๊ณ ์์ผ๋ฏ๋ก, M์ block ์ํ๊ฐ ๋ฉ๋๋ค.
- ์ด์ด์ ์ค๋ ๋ H๊ฐ ready list์ ๋ค์ด์ต๋๋ค. H๋ lock A๊ฐ ํ์ํ์ง๋ง, ์ด ๋ํ ํ์ฌ L์ด ๋ณด์ ํ๊ณ ์์ต๋๋ค. ๊ทธ๋์ H๋ block ์ํ๊ฐ ๋ฉ๋๋ค.
์ด์ ์ค์ผ์ค๋ฌ๋ ready ์ํ์ธ ์ค๋ ๋๊ฐ ์์ผ๋ฏ๋ก, block ์ํ์ธ ์ค๋ ๋๋ค์ด ๊ธฐ๋ค๋ฆฌ๋ ์์ ๋ณด์ ์(L)์๊ฒ ์ฐ์ ์์๋ฅผ ๊ธฐ๋ถํ๊ฒ ๋ฉ๋๋ค.
- H๊ฐ L์๊ฒ ์ฐ์ ์์ 3์ ๊ธฐ๋ถํ๊ณ ์ถ์ง๋ง, ๊ทธ ์ ์ L์ด H์๊ฒ ์์์ ๋ฐ๋ก ๋๊ฒจ์ค ์ ์๋ ์ํ๊ฐ ์๋๋๋ค. ์๋ํ๋ฉด L์ ๋จผ์ lock B๋ก ์ธํด M์๊ฒ๋ ๋๊ธฐ๋ฅผ ๋ฐ์์ํค๊ณ ์์ผ๋ฏ๋ก, L์ด ์งํ๋๊ธฐ ์ํด์ ๋จผ์ M์ด ์งํ๋์ด์ผ ํฉ๋๋ค.
- ๊ทธ๋ฐ๋ฐ M ์ญ์ block ์ํ์ด๋ฏ๋ก, ๊ฒฐ๊ตญ H โ M โ L๋ก ์ด์ด์ง๋ ๊ธฐ๋ถ์ ์ฐ์๊ฐ ๋ฐ์ํฉ๋๋ค.
๊ฒฐ๊ณผ์ ์ผ๋ก:
- H๊ฐ M์ ์ฐ์ ์์ 3์ ๊ธฐ๋ถํ๊ณ ,
- M๊ฐ L์ ์ฐ์ ์์ 3์ ๊ธฐ๋ถํฉ๋๋ค.
- ๋ฐ๋ผ์ L์ ์์๋ก ์ฐ์ ์์ 3์ ๋ถ์ฌ๋ฐ๊ณ , lock A์ B ๋ชจ๋๋ฅผ ๋น ๋ฅด๊ฒ ํด์ ํ ์ ์๊ฒ ๋ฉ๋๋ค.
Pintos ์ฝ๋ ์์ ๋ฐ ๊ตฌํ ํฌ์ธํธ
์ด์ ์ฐ์ ์์ ์ค์ผ์ค๋ง์ ์ํด Pintos์ ์ค๋ ๋(threads/thread.c ๋ฐ thread.h) ๋ฐ ๋๊ธฐํ (threads/synch.c ๋ฐ synch.h) ๋ถ๋ถ์ ์์ ํด์ผ ํฉ๋๋ค.
(์์ฑ ์ค)
ํ ์คํธ ๊ฒฐ๊ณผ
์ฌ๊ธฐ๊น์ง ๊ตฌํํ ๋ค ํ ์คํธ ๊ฒฐ๊ณผ๋ ์๋์ ๊ฐ์ต๋๋ค. Priority scheduling์ ๋ชจ๋ ํํธ๊ฐ ํต๊ณผ๋ ์ค ์์๊ฑด๋ง... priority-condvar๋ ๋ญ๊น์? ์ ์คํจ์ธ๊ฐ์? ํ ์คํธ๋ ํ๋์ง๋ง ๋ค๋ฃจ์ด์ผ ํ ๊ฐ๋ ์ด ์ข ์๋ ๋ถ๋ถ์ ๋๋ค. ์ด๋ ๋ค์ ํฌ์คํธ์์ ๋ค๋ฃจ์ด ๋ณด๊ฒ ์ต๋๋ค.

'IT > ์ปดํจํ ์ ์ฌ๊ณ ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
Pintos Project 1-4. Priority Scheduling w/ Priority Condition Variable (0) | 2025.05.13 |
---|---|
Pintos Project 1-2. Priority Scheduling (0) | 2025.05.12 |
Pintos Project 1-1. Busy Waiting vs. Sleep/Wakeup (0) | 2025.05.12 |
๋ ๋-๋ธ๋ ํธ๋ฆฌ (Red-Black Tree) (1) | 2025.04.18 |
C์ธ์ด์ ํฌ์ธํฐ (๊ธฐ์ด) (0) | 2025.04.17 |
C์ธ์ด์ ๋ฐฐ์ด๊ณผ ํฌ์ธํฐ (0) | 2025.04.17 |
C์ธ์ด์ ํฌ์ธํฐ ์ดํด: ์๋ฃํ์ผ๋ก์์ *์ ์ญ์ฐธ์กฐ ์ฐ์ฐ์๋ก์์ * (2) | 2025.04.14 |
์๋ ํ์ธ์.
ํฌ์คํ ์ด ์ข์๋ค๋ฉด "์ข์์โค๏ธ" ๋๋ "๊ตฌ๋ ๐๐ป" ํด์ฃผ์ธ์!