๐ ๊ณต๋ถํ ๋ด์ฉ
์ ์ ํ(Preemption)
- ์ ์ ํ์ ํ๋์ ํ๋ก์ธ์ค๊ฐ ๋ค๋ฅธ ํ๋ก์ธ์ค ๋์ ์ ํ๋ก์ธ์๋ฅผ ์ฐจ์งํ ์ ์๋ค๋ ๋ป์ด๋ค.
- ๋น ๋ฅธ ์๋ต์๊ฐ์ ์ํ๋ ๋ํ์ ์๋ถํ ์์คํ ์ ์ ํฉํ๋ฉฐ ๊ธด๊ธํ ํ๋ก์ธ์๋ฅผ ์ ์ด ํ ์ ์๋ค.
์ ์ ํ ๋ฐฉ์์ ์ค์ผ์ฅด๋ง์๋
- Round Robin : ์๊ฐ ๋จ์๊ฐ ์ค์ ๋์ด ๊ฐ ์๊ฐ๋์ ํ๋ก์ธ์ค๋ฅผ ์คํํ๊ณ ์๊ฐ์ด ์ง๋๋ฉด ๋ค์ ํ๋ก์ธ์ค๋ก ์ ํ๋๊ฒ ํ๋ค. ์ ์ฒด์ ์ธ ์๋ต ์๋๊ฐ ๋นจ๋ผ์ง์๋ ์์ผ๋, ์๊ฐ ๋จ์๋ง๋ค ํ๋ก์ธ์ค๋ฅผ ์ ํํ ๋ ๋ฌธ๋งฅ ์ ํ์ ๋ฐ๋ฅธ ์ค๋ฒํค๋๊ฐ ๋ฐ์ํ ์ ์๊ธฐ ๋๋ฌธ์ ์ ๋นํ ์๊ฐ ๋จ์ ์ค์ ์ ํด์ผํ๋ค.
๋น์ ์ ํ(Non-Preemption)
- ๋น์ ์ ํ์ ํ๋์ ํ๋ก์ธ์ค๊ฐ ๋๋์ง ์์ผ๋ฉด ๋ค๋ฅธ ํ๋ก์ธ์ค๋ CPU๋ฅผ ์ฌ์ฉํ ์ ์๋ค.
- ์์๋๋ก ์ฒ๋ฆฌ๋๋ ๊ณต์ ์ฑ์ด ์๊ณ , ๋ค์์ ์ฒ๋ฆฌํด์ผ ํ ํ๋ก์ธ์ค์ ๊ด๊ณ์์ด ์๋ต ์๊ฐ์ ์์ํ ์ ์๋ค.
- ์ผ๊ด ์ฒ๋ฆฌ ์์คํ ์ ์ ํฉํ๋ค.
- CPU์ฌ์ฉ ์๊ฐ์ด ๊ธด ํ๋์ ํ๋ก์ธ์ค๊ฐ CPU ์ฌ์ฉ์๊ฐ์ด ์งง์ ์ฌ๋ฌ ํ๋ก์ธ์ค๋ฅผ ์ค๋ซ๋์ ๋๊ธฐ ์ํฌ ์ ์์ผ๋ฏ๋ก, ์ฒ๋ฆฌ์จ์ด ๋จ์ด์ง ์ ์๋ค.
๋น์ ์ ํ ๋ฐฉ์์ ์ค์ผ์ฅด๋ง์๋
- FIFO : ๋๊ธฐ ํ์ ๋จผ์ ๋ค์ด์จ ์์ ์์ผ๋ก CPU๋ฅผ ํ ๋น
- SJF : ์์์๊ฐ์ด ์งง์ ์์ ์์ผ๋ก ํ ๋น
- HRN : ์ฐ์ ์์์ ๋๊ธฐ ์๊ฐ์ ๋ฐ๋ผ ์์ ์ ํ ๋น
์ธ๋งํฌ์ด
- ๊ณต์ ์์์ ์ ๊ทผํ ์ ์๋ ์ต๋ ํ์ฉ์น๋งํผ ๋์์ ์ฌ์ฉ์ ์ ๊ทผ์ ํ ์ ์๊ฒ ํ๋ ๊ธฐ๋ฒ
- ๊ณต์ ์์์ ์ง์ ํ ์ ์๋ ์ฌ์ฉ์๊ฐ ๊ฝ ์ฐฌ ๊ฒฝ์ฐ ์ฌ์ฉ์๋ ๋๊ธฐ์ํ
- sema_init(struct semaphore *, unsigned value)
- ์ธ๋งํฌ์ด์ value ๊ฐ ์ด๊ธฐํ - sema_down(struct semaphore *)
- ์ธ๋งํฌ์ด์ value๊ฐ 0์ผ ๊ฒฝ์ฐ ํ์ฌ ์ค๋ ๋๋ฅผ THREAD_BLOCK ์ํ๋ก ๋ณ๊ฒฝ ํ schedul() ํธ์ถ - sema_up(struct semaphore *sema)
- ๋๊ธฐ ๋ฆฌ์คํธ์ ์ค๋ ๋๊ฐ ์กด์ฌํ๋ฉด ๋ฆฌ์คํธ ๋งจ ์ฒ์์ ์์นํ ์ค๋ ๋๋ฅผ THREAD_READY ์ํ๋ก ๋ณ๊ฒฝ ํ schedule()ํธ์ถ
๋ฝ(lock)
- ํ ํ๋ก์ธ์ค๊ฐ ์๊ณ ์์ญ์ ํด๋นํ๋ ์ฝ๋๋ฅผ ์คํํ๊ณ ์์ ๋ ๋ค๋ฅธ ํ๋ก์ธ์ค๊ฐ *์๊ณ์์ญ์ผ๋ก ์ง์ ํ์ง ๋ชปํ๋๋ก ํ๋๊ฒ
*์๊ณ์์ญ : ํ ๋ฒ์ ํ๋์ ํ๋ก์ธ์ค๋ง ์ด์ฉํ๋๋ก ๋ค๋ฅธ ํ๋ก์ธ์์ ์ ๊ทผ์ ์ ํํ๋ ์์ญ
- lock_init(struct lock *lock)
- lock ๊ตฌ์กฐ ์ด๊ธฐํ - lock_acquire(struct lock *lock)
- lock ์์ฒญ - lock_release(struct lock *lock)
- lock์ release
์กฐ๊ฑด ๋ณ์(condition variable)
- Condition Variable์ ํน์ ์กฐ๊ฑด์ ๋ง์กฑํ๊ธฐ๋ฅผ ๊ธฐ๋ค๋ฆฌ๋ ๋ณ์๋ผ๋ ์๋ฏธ์ด๋ค. ๋ฐ๋ผ์ ์ด๋ฅผ ์ด์ฉํ์ฌ ์ฃผ๋ก thread๊ฐ์ ์ ํธ ์ ๋ฌ์ ์ํด ์ฌ์ฉํ๋ค. ํ๋์ thread๊ฐ waiting ์ค์ด๋ฉด ์กฐ๊ฑด์ ๋ง์กฑํ thread์์ ๋ณ์๋ฅผ ๋ฐ๊พธ๊ณ signaling์ ํตํด ๊นจ์ฐ๋ ๋ฐฉ์์ด๋ค.
- cond_init(struct condition *cond)
- condition data ์ด๊ธฐํ - cond_wait(struct condition *cond, struct lock *lock)
- ์กฐ๊ฑด ๋ณ์๊ฐ ๋ณด๋ด๋ ์ ํธ ๊ธฐ๋ค๋ฆผ - cond_signal(struct condition *cond, struct lock *lock UNUSED)
- ์กฐ๊ฑด ๋ณ์ ์์์ ๊ฐ์ฅ ํฐ ์ฐ์ ์์๋ฅผ ๊ฐ์ง ์ค๋ ๋์๊ฒ ์ ํธ๋ฅผ ๋ณด๋ - cond-broadcast(struct condition *cond, struct lock *lock)
- ์กฐ๊ฑด๋ณ์ ์์์ ์ ํธ๋ฅผ ๊ธฐ๋ค๋ฆฌ๋ ๋ชจ๋ ์ค๋ ๋์๊ฒ ์ ํธ๋ฅผ ๋ณด๋
Implementation of Priority Scheduling-Synchronization
- ๋ณํํ ํจ์
- ์ฐ์ ์์๋ก waiters_list์ ์ค๋ ๋๋ฅผ ๋ฃ๊ธฐ์ํด ์์ ํ ํจ์๋ค
- sema_down(struct semaphore *sema)
- cond_wait(struct condition *cond, struct lock *lock)
- waiters_list๋ฅผ ์ฐ์ ์์ ์์ผ๋ก ์ ๋ ฌ
- waiters_list ์์ thread์ ์ฐ์ ์์๋ฅผ ๋ฐ๊พธ๋ ๊ฒ์ ๊ณ ๋ ค๋๊ธฐ๋ ํ๋ค.
- sema_up(struct semaphore *sema)
- cond_signal(struct condition *cond, struct lock *lock UNUSED)
- waiters_list ์์ thread์ ์ฐ์ ์์๋ฅผ ๋ฐ๊พธ๋ ๊ฒ์ ๊ณ ๋ ค๋๊ธฐ๋ ํ๋ค.
์ฐ์ ์์ ์ญ์
- ์ฐ์ ์์๊ฐ ๋์ ์ค๋ ๋๊ฐ ๋ฎ์ ์ฐ์ ์์๋ฅผ ๊ฐ์ง ์ค๋ ๋๋ฅผ ๊ธฐ๋ค๋ฆฌ๋ ํ์
์์ ์์ ๋ฅผ ๋ณด๋ฉด ํ์ฌ Thread L์ด ์คํ๋๊ณ ์๋ ์ค๊ฐ์ Thread H๊ฐ key๋ฅผ ์์ฒญํ๋ ๊ฒฝ์ฐ
์ด๋ฏธ L์ด ์คํ์ค์ด๊ธฐ ๋๋ฌธ์ H๋ Blocked ์ํ์ ๋ค์ด๊ฐ๊ฒ ๋๊ณ ๊ทธ ํ์ Thread M์ด ์คํ๋๋ฉด์
์ฐ์ ์์๊ฐ ๋์ H๋ ์คํ๋์ง ๋ชปํ๊ณ ์ฐ์ ์์๊ฐ ๋ฎ์ M๋จผ์ ์คํ๋๋ ๊ฒฝ์ฐ๋ฅผ inversion์ด๋ผ๊ณ ํ๋ค.
Priority Donation
- ์์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด Donation์ ์ฌ์ฉํ๋ค.
- lock holder์๊ฒ ์ฐ์ ๊ถ์ ์์ํ๋ค.
Nested Donation
Multiple Donation
Implementation of Priority Donation
- init_thread(struct thread *t, const char *name, int priority)
- priority donation ์ด๊ธฐํ - lock_acquire(struct lock *lock)
- lock์ด ์ด์ฉ ๋ถ๊ฐ๋ฅํ๋ฉด, lock์ ์ฃผ์ ์ ์ฅ
- ํ์ฌ ์ฐ์ ์์๋ฅผ ์ ์ฅํ๊ณ , ๊ธฐ๋ถ๋ฐ์ ์ค๋ ๋๋ฅผ ๋ฆฌ์คํธ์ ์ ์ฅ
- ์ฐ์ ์์ ๊ธฐ๋ถ
โ ์๊ณ ๋ฆฌ์ฆ
14425 | S3 | ๋ฌธ์ ์ด | ๋ฌธ์์ด ์งํฉ | solved | … |
1543 | S4 | ๋ฌธ์์ด | ๋ฌธ์๊ฒ์ | solved | … |
9996 | S3 | ๋ฌธ์์ด | ํ๊ตญ์ด๊ทธ๋ฆฌ์ธ๋.. | solved | … |
๐ญ ๋๋ ์ & ๋ฐฐ์ด ์
Priority์ ๊ฐ๋ ์ ๋ํ ๋ด์ฉ์ ์ด๋ ์ ๋ ์ดํด๋ฅผ ํ๋๋ฐ, priority donation์ ์ฐ๋ฉด์ ๊ตฌํ์ ํ๋๊ฒ ์ฝ์ง ์์ ๋ณด์ธ๋ค.
์ค๋ ์ ๋ฆฌํ ๋ด์ฉ๋ค๊ณผ ๋ด์ผ ๋ฐ๊ฟ์ผํ ์ฝ๋๋ฅผ ๋น๊ตํด ๋ณด๊ณ ๊ฒช์ผ๋ฉด์ ๋๋ผ๋ ๊ฒ์ด ๊ฐ์ฅ ๋น ๋ฅผ ๊ฒ์ผ๋ก ๋ณด์ธ๋ค.
๐ฅ ๋ด์ผ ๊ณต๋ถํ ๋ด์ฉ
priority ์์
๐๏ธ ํฌ์คํ
ใ ๋๋ ๋จ์ง ์ฝ๊ณ ์ด๋ค๊ณ ํด์, ์ฌ์ง์ด ๋ฐค์๋๋ก ๊ทธ๋ ๊ฒ ๋๋ค๊ณ ํด์ ์๋ค๋ค์ ์ด์ฌํ ํ๋ค๊ณ ํ๊ฐํ ์๋ ์๋ค. ๋ฌด์์ ์ํด ํ๋์ง ์์ง ๋ชปํ๋ ์ด์ ์ฑ์คํ๋ค๊ณ ๋งํ์ง ์๊ฒ ๋ค. (...) ์์ ์ ์ง๋ฐฐ์ ์ธ ๋๋ ์์น์ ์ํด ๊ทธ๊ฒ์ ํ ๋์์ผ ๋น๋ก์ ์์ฐ์ด ์ฐ๋ฆฌ์๊ฒ ์ค ๋ณธ์ฑ๊ณผ ๋์์์ด ์กฐํ๋ฅผ ์ด๋ฃจ๊ณ ์๋ค๊ณ ๋งํ๊ฒ ๋ค. ใ
-์ํฝํ ํ ์ค, ๋ํ๋ก, 4.4.41: 43
์ํ๊น๊ฒ๋ ์ด์์ ํ๋ค ์ถ์ ์ ๋๋ก ๋์ฝ ๋ฐ ์ ์์ด ๋ถ์ฃผํ๊ฒ ์์ง์ด๋ฉด์ ๊ทธ์ ํฉ๋นํ ๋ณด์์ ๋ฐ๋ ๊ฒฝ์ฐ๋ ์ค์ ๋ก ๋ง์ง ์๋ค. ๊ฒ๋ค๊ฐ ์ค์ค๋ก ๋ง์กฑํ๋ ๊ฒฝ์ฐ๋ ๋๋ฌผ๋ค.
'ํ๊ณ ์๋ ์ผ'๋ก ์์ ์ ํ๊ฐํ์ง ๋ง๊ณ , '์ ํ๋๊ฐ?' ๊ทธ๋ฆฌ๊ณ '๋ฌด์์ ์ฑ์ทจํ๋ ค ํ๋๊ฐ?'๋ก ํ๊ฐํ๋ผ. ์ฌ๊ธฐ์ ์ข์ ๋ต์ ํ ์ ์๋ค๋ฉด ๊ทธ ์ผ์ ๊ทธ๋ง๋์ด๋ ์ข๋ค.
์๊ฐ์ ์ฐ๋ ๋งํผ ํจ์จ์ด ๋ง์ด ์๋ ๊ฒ์ ๋ณธ์ธ๊ณผ ๋์ผ ํ ๊ฒ ๊ฐ๋ค. ๋ฌด์์ ์ฑ์ทจํ๊ณ ์ถ์๊ฐ ์ ํ๋๊ฐ ๋ด๊ฐ ๋ฐ๋ผ๋ ๊ฒ์ ๋ฌด์์ธ๊ฐ?
ใ ์ฒ ํ์ ๋ฐ์ผ๋ก ๋๋ฌ๋๋ ๊ฒ์ ๊ด์ฌ์ด ์๋ค. ๋จ์ง ํ์ํ ๊ฒ์ ์ฃผ์๋ฅผ ๊ธฐ์ธ์ด๊ณ , ๋ง์์ ๋ด์๋ ๊ฒ์๋ง ๊ด์ฌ์ ๋๋ค. ใ
-๋ฌด์๋์ฐ์ค ๋ฃจํธ์ค, ๊ฐ์๋ก, 16.75.15-16
์น๋ ค๋ ์น๋ณต์ ์ ๋๋ค. ๊ฐํจ๋ฆญ ์ฌ์ ๋ ๋ก๋ง ์นผ๋ผ๊ฐ ๋ฌ๋ฆฐ ์ ๋ถ๋ณต์ ์ ๋๋ค. ์ํ์์ ๊ฐ๋น์ผ ์๋ณต๊ณผ ์๋ฅ๊ฐ๋ฐฉ์ ๋ค๊ณ ๋ค๋๋ค. ํ์ง๋ง ์คํ ์ ์ฒ ํ์๋ค์ ๋ฒ๋ณต์ด ์์์ผ๋ฉฐ ์ด๋ค์ ๊ท์ ํ ์ ์๋ ์ผ๊ด๋ ์์๋ ์์๋ค. ๋ณด์ด๋ ์ธ์์ผ๋ก ์ด๋ค์ ๊ท์ ํ๊ฑฐ๋ ๊ตฌ๋ณํ ์ ์์๋ค. ๊ทธ๋ ๋ค๋ฉด ์ด๋ค์ ์์๋ณด๋ ์ ์ผํ ๋ฐฉ๋ฒ์ ๋ฌด์์ด์์๊น? ์ค์ง ํ์ฑ๋ฟ์ด๋ค.
๋ง์ ํ์ง ์์๋ ๋ณด์ฌ์ฃผ์ง ์์๋ ์์๋ณผ ์ ์๋๋ก ์ฒ ํ์๊ฐ ์๋์ด๋ ์ฒ ํ์๋ก ์ฐฉ๊ฐํ ์ ์๋๋ก ์ค์ค๋ก๋ฅผ ๊ฐ๊พธ์.