์ฐ์ ์์ ์ค์ผ์ค๋ง
Assignment Overview
์ฐ์ ์์๋ฅผ ๊ณ ๋ คํด ์ค๋ ๋๋ฅผ ์ค์ผ์ค๋งํด๋ผ. ํฌ๊ฒ ๋ ๊ฐ์ง step์ด ์๋ค. ์ฒซ ๋ฒ์งธ๋ ๋จ์ํ ์ค๋น ํ๋ฅผ ์ ๋ ฌํ๊ณ , ์ฆ์ CPU๋ฅผ ์๋ํ๋ฉด ํด๊ฒฐ๋๋ค. ๋ ๋ฒ์งธ๋ ๋๊ธฐํ (synchronization)์ ๊ด๋ จ๋ ๋ฌธ์ ๋ก, ์ฌ๋ฌ ๊ฐ์ง ๋๊ธฐํ ๋ฉ์ปค๋์ฆ์์๋ ์ฐ์ ์์๋๋ก ์ค๋ ๋๊ฐ ์คํ๋ ์ ์๊ฒ ์ฒ๋ฆฌํด์ฃผ๋ฉด ๋๋ค. ์ด๋ฅผ ์ํ ๋ฐฉ๋ฒ์ด ์ฐ์ ์์ ๊ธฐ์ฆ (priority donation)์ด๋ค.
- ๋ฌธ์ 1: ์ฃผ์ด์ง ์ฐ์ ์์๋๋ก ์ค๋ ๋๊ฐ ์คํ๋๋๋ก ๋ง๋ค์ด๋ผ
- ์ค๋ ๋๋ ์ค๋น ํ์์ ์ฐ์ ์์ ์์๋๋ก ๋์์ผ ํ๋ค.
- ํ์ฌ ์ค๋ ๋๋ณด๋ค ์ฐ์ ์์๊ฐ ๋์ ์ค๋ ๋๊ฐ ์ค๋น ํ์ ๋ค์ด์ค๋ฉด, ์ฆ์ CPU๋ฅผ ์๋ณดํด์ผ ํ๋ค.
- ํ์ฌ ์ค๋ ๋์ ์ฐ์ ์์๊ฐ ๋ณ๊ฒฝ๋๋ฉด, ์ค๋น ํ์ ์ค๋ ๋์ ์ฐ์ ์์๋ฅผ ๋น๊ตํด์ ์ ์ ํ ์คํํด์ผ ํ๋ค.
- ๋ฌธ์ 2: ์ฐ์ ์์ ์ญ์ (Priority Inversion)์ ํด๊ฒฐํด๋ผ.
- ํ์ฌ ์ค๋ ๋๊ฐ ์์ ๋ณด๋ค ์ฐ์ ์์๊ฐ ๋ฎ์ ์ค๋ ๋์ ์ํด ๋งํ ์คํ์ด ๋์ง ๋ชปํ๊ณ ์๋ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํด๋ผ
- ์ฌ๊ธฐ์ '๋งํ ์คํ์ด ๋์ง ๋ชปํ๊ณ ์๋' ์ํ๋ ๊ตฌ์ฒด์ ์ผ๋ก lock, semaphore, conditional variable ๋ฑ์ ๋๊ธฐํ ๋ฉ์ปค๋์ฆ์ ์ํด blocked ๋ ์ํ๋ฅผ ๋งํ๋ค.
- ์ด๋ฌํ ๊ฒฝ์ฐ, ํ์ฌ ์ค๋ ๋๊ฐ ์์ ์ ๋ง๊ณ ์๋ ์ค๋ ๋์๊ฒ ์์ ์ ์ฐ์ ์์๋ฅผ ๊ธฐ์ฆ(donation)ํด์ lock์ ๋นจ๋ฆฌ ํด์ ํ๋๋ก ํด์ผ ํ๋ค.
- ์ค๋ ๋๊ฐ lock์ ํ๊ณ ๋์ฌ ๋, ๋ง์ฝ ๊ธฐ์ฆ๋ฐ์ ์ฐ์ ์์๊ฐ ์์ผ๋ฉด ๋ชจ๋ ๋ฐํํ์ฌ, ์ค์ ๋ ๋์ ์ฐ์ ์์๋ฅผ ๊ฐ์ง๊ณ ์๋ ์ค๋ ๋์๊ฒ ์ฆ์ CPU๋ฅผ ์๋ํ์ฌ์ผ ํ๋ค.
- ํ๋์ ์ค๋ ๋๋ ์ฌ๋ฌ ๊ฐ์ lock์ ๊ฐ์ง๊ณ ์์ ์ ์๊ณ (multiple), ์ ๊ทผํ๋ ค๊ณ ํ๋ lock์ ๊ฐ์ง ์ค๋ ๋๊ฐ ๋ค๋ฅธ lock์ ์ ๊ทผํ๊ธฐ ์ํด ๋๊ธฐํ๊ณ ์์ ์ ๋ ์๋ค. (nested)
Implementation
01) ๋ฌธ์ 1
1) ์ค๋น ํ๋ฅผ ์ฐ์ ์์์์ผ๋ก ์ ๋ ฌํด์ผ ํ๋ค.
์ด๋ ์ค๋น ํ์ ์ค๋ ๋๋ฅผ ๋ฃ์ ๋ ์ฝ์ ์ ๋ ฌ์ ํ๊ฑฐ๋, ๋บ ๋ ๋ฆฌ์คํธ๋ฅผ ๊ฒ์ํ์ฌ ์ต๋ ์ฐ์ ์์๋ถํฐ ์ค์ผ์ค๋งํ๋ ๊ฒ์ผ๋ก ํด๊ฒฐํ ์ ์๋ค. ์ฐ๋ฆฌ ํ์ ์ฝ์ ์ ๋ ฌ ๋ฐฉ์์ผ๋ก ์งํํ๋ค.
void thread_unblock(struct thread* t) {
...
list_insert_ordered(&ready_list, &t->elem, high_priority, NULL);
...
}
/* compare function */
bool high_priority(struct list_elem* _a, struct list_elem* _b, void* aux) {
struct thread* a = list_entry(_a, struct thread, elem);
struct thread* b = list_entry(_b, struct thread, elem);
return a->priority > b->priority;
}
2) ํ์ฌ ์ค๋ ๋๋ณด๋ค ์ฐ์ ์์๊ฐ ๋์ ์ค๋ ๋๊ฐ ์ค๋ฉด CPU๋ฅผ ์ฆ์ ์๋ณดํด์ผ ํ๋ค.
์ฐ์ ์์๊ฐ ๋ณ๊ฒฝ๋๋ฉด ์ด์ ๋ง๊ฒ ์ฒ๋ฆฌํด์ผ ํ๋ค. (๋ด๊ฐ ๋ฎ์์ก์ผ๋ฉด ์๋ณดํด์ผ ํ ์ํฉ์ด ์๊ธธ ์ ์์)
void thread_create(...) {
...
thread_unblock(t); /* ready_list์ ์ฝ์
์ ๋ ฌ */
thread_yield(); /* ํ ๋ฒ yield๋ฅผ ์คํํฉ๋๋ค. */
intr_enable(); /* yield๋ก CPU๋ฅผ ์ ์ ํ๊ฒ ๋ ์ค๋ ๋๊ฐ ์ธํฐ๋ฝํธ๋ฅผ ํ์ฉ */
}
void thread_set_priority(int new_priority) {
thread_current()->priority = new_priority;
thread_yield(); /* ํ ๋ฒ yield๋ฅผ ์คํํฉ๋๋ค. */
}
์ด ๋ ๊ฐ์ง ์กฐ๊ฑด์ ์ค๋ ๋๊ฐ ์์ฑ๋ ๋, ๊ทธ๋ฆฌ๊ณ ์ฐ์ ์์๊ฐ ๋ณ๊ฒฝ๋ ๋ thread_yield()
๋ฅผ ํ ๋ฒ์ฉ ์คํํด ์ค์ผ๋ก์ ํด๊ฒฐํ ์ ์๋ค. ์ค๋น ํ๊ฐ ๋ ์ฐ์ ์์ ๋์์์ผ๋ก ์ ์ง๋๊ธฐ ๋๋ฌธ์ด๋ค. thread_yield()
๋ฅผ ์คํํ๋ฉด, ํ์ฌ ์คํ์ค์ด๋ ์ค๋ ๋๋ฅผ ์ค๋น ํ์ (์ฝ์
์ ๋ ฌ์ผ๋ก) ๋ฃ๊ณ schedule()
์ ํธ์ถํ์ฌ ๋ค์์ ์คํ๋ ์ค๋ ๋๋ฅผ ํ์์ ๋ฝ๋๋ค. ์ด ๋ ํ์ฌ ์ค๋ ๋์ ๋ค์ ์ค๋ ๋๊ฐ ๋ค๋ฅด๋ฉด thread_launch()
๋ฅผ ํธ์ถํด (ํ์ฌ ๋ ์ง์คํฐ ์ํ๋ฅผ ์ ์ฅํ๊ณ , ๋ค์ ์ค๋ ๋์ context๋ฅผ ์ฌ๋ฆฌ๋) ์ค์ง์ ์ธ context switching์ด ์ผ์ด๋๊ฒ ๋๋ค. ์ด ์กฐ๊ฑด๋ฌธ (if(curr != next)
)์ด ์ด๋ฏธ ๊ฑธ๋ ค ์์ผ๋ฏ๋ก, thread_create()
๋ thread_set_priority()
์์ ๋ฐ๋ก ์ฐ์ ์์๋ฅผ ๋น๊ตํ๋ ์กฐ๊ฑด๋ฌธ์ ๊ฑธ์ง ์๊ณ , thread_yield
๋ฅผ ๋ฐ๋ก ํธ์ถํด๋ ๋๋ค.
๋ฌธ์ 2) Donation
๋๊ธฐํ๊ฐ ๊ฐ์ ๋๋ฉด์ ๋ฌธ์ ๊ฐ ๋ณต์กํด์ง๋ค. ๋ด๊ฐ ์ฝ๋๋ฅผ ์ง๋ฉด์ ์ด๋ ค์ ๋ ์ง์ ์ด ๋ช ๊ฐ์ง ์์๋ค.
- ํจ์์ ์คํ์ด ํ๋์ ์ค๋ ๋์์ ์์์ ์ผ๋ก ์ผ์ด๋์ง ์๋๋ค. ์ฝ๋์ ๊ฐ ๋ผ์ธ์ด ์ด๋ ์ค๋ ๋์์ ์ด๋๊น์ง ์คํ๋๊ณ ๋์ด๊ฐ๋์ง๋ฅผ ๋จธ๋ฆฟ์์ผ๋ก ๋ฐ๋ผ๊ฐ๋ ๊ฒ์ด ํท๊ฐ๋ ธ๋ค.
- donate๋ฅผ ํ ์ค๋ ๋์ donate๋ฅผ ๋ฐ์ ์ค๋ ๋๋ฅผ ๊ตฌ์ฒด์ ์ผ๋ก ์ด๋ป๊ฒ ๊ด๋ฆฌํ ๊ฒ์ธ๊ฐ?
- lock์ด multipleํ๊ฒ ๊ฑธ๋ฆฐ ๊ฒฝ์ฐ์ nestedํ๊ฒ ๊ฑธ๋ฆฐ ๊ฒฝ์ฐ, lock_acquire์ lock_release์์ ์ด๋ค ์ฒ๋ฆฌ๋ฅผ ํด ์ค์ผ ํ ๊น?
1) ์ค๋ ๋ ์ํ ๋ณํ๋ฅผ ์ ์ถ์ ํ์
1๋ฒ ๋ฌธ์ ์ ๊ฐ์ ๊ฒฝ์ฐ๊ฐ ๋ค์์ ์ํฉ์ด๋ค. ์ฐ์ ์์๊ฐ ๋ฎ์ low ์ค๋ ๋๊ฐ lock์ holder์ธ ์ํฉ์์ current_thread์ธ high๊ฐ lock_acquire๋ฅผ ์๋ํ๋ค๊ณ ํ์.
void lock_acquire(struct lock* lock) {
... // ๊ธฐํ๋ฑ๋ฑ..
struct thread* curr = thread_current();
struct thread* holder = lock->holder;
/* donation */
if(holder && curr->priority > holder->priority) {
holder->priority = curr->priority;
}
sema_down(...);
lock->holder = thread_current();
/* ๋๋ sema์ ์ฃผ์ธ์ด ๋์๋ค! ์ฌ๊ธฐ์ ๊ธฐ์ฆํ๋ ๊ฒ์ ๋ฐํ๋ฐ์ผ๋ฉด ์ ๋ ๊น? */
/* ์๋ฅผ ๋ค์ด ์ด์ holder๋ฅผ ์ ์ฅํด๋๊ณ , holder->priority = old_priority */
...
}
์ฝ๋ฉํธ์ ๋ฌ๋ฆฐ ๋ถ๋ถ์ ๊ธฐ์ฆ์ ๋ฐํ ๋ก์ง์ ์ง๋ฉด ์ ๋๋ค. ์๋ํ๋ฉด, holder์ ์ฐ์ ์์๋ฅผ ์๋ฉ ์ฌ๋ ค ๋์ ์ํ์์ lock์ ํ๋ํ ํ ๋ฐํ์ ํ๊ณ ์ ํ๋ค, holder์ ์คํ์ ๋งํ ์ ์ ์ง์ง ์ฐ์ ์์๊ฐ ๋์๋ ๋(ํ์ฌ ์คํ์ค์ธ ์ค๋ ๋)๋ ์คํ์ด ์ ๋๊ณ holder๊ฐ ๋๋ ๋ ๊น์ง ready_list์๋ง ๋จ์์๊ฒ ๋๊ธฐ ๋๋ฌธ์ด๋ค. ์ฆ, sema_down ๋ผ์ธ์ ๋ค์ ์ฝ๋๊ฐ ๋ฐ๋ก ์คํ๋์ง ์๋๋ค.
๊ทธ๋์ acquireํ ๋๋ ๋๋ฅผ ๋ง๊ณ ์๋ ์ค๋ ๋ (lock->holder)์ ์ฐ์ ์์๋ฅผ ๋์ฌ์ฃผ์ด์ผ ํ๊ณ , lock_release๋ฅผ ํ ๋๋ (์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋ฎ์ ์ ์ฅ์์) ๋์ lockํด์ ๋ฅผ ๊ธฐ๋ค๋ฆฌ๊ณ ์๋ ์ค๋ ๋๋ค์ด ๊ธฐ์ฆํ ์ฐ์ ์์๋ฅผ ๋ชจ๋ ๋ฐํํด์ผ ํ๋ค. ๋ค๋ฅธ ๋ง๋ก ํ๋ฉด, acquire์์๋ higer thread, release์์๋ lower thread์ ์ ์ฅ์์ ๋ก์ง์ ์ง์ผ ํ๋ค.
๋๊ธฐํ ๋ฌธ์ ๋ฟ๋ง ์๋๋ผ, ์ค๋ ๋๋ฅผ ๋ค๋ฃจ๋ฉด์๋ ์ฝ๋ ๊ฐ ๋ผ์ธ์ ์ค์ ๋ก ์ด๋ค ์ค๋ ๋๊ฐ ์คํํ๊ฒ ๋๋์ง๋ฅผ ์ ์๊ฐํด์ผ ํ๋ค.
2) donation ์ ๋ณด๋ฅผ ๊ฐ๋ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ ์ค๊ณํ์
donation์ ๊ด๊ณ๋ฅผ ์ ์๊ฐํด ๋ด์ผ ํ๋ค. donate๋ฅผ ํ๋ ์ค๋ ๋์, donate๋ฅผ ๋ฐ๋ ์ค๋ ๋์ ๊ด๊ณ๋ ์ผ๋ ๋ค ๊ด๊ณ์ด๋ค. ์ด๋ค ์ค๋ ๋ t๊ฐ donate๋ฅผ ํ๋ค๋ฉด, t๋ lock์ ๋งํ waiters์ ๋ฆฌ์คํธ์ blocked๋ ์ํ๋ก ๋ค์ด๊ฐ ์์ ๊ฒ์ด๋ค. ๋ฐ๋ผ์, ํ ์ค๋ ๋๋ ์ฌ๋ฌ ๊ฐ์ lock์ waitingํ๋ ์ํ๊ฐ ๋ ์ ์๋ค.
ํ์ง๋ง donate์ ๋ฐ๋ ์ ์ฅ์์๋, ์ฌ๋ฌ ์ค๋ ๋๋ก๋ถํฐ ์ฐ์ ์์๋ฅผ donate๋ฅผ ๋ฐ์ ์ ์๋ค. ๋ฐ๋ผ์ ์ด๋ ๋ฆฌ์คํธ ๋๋ ๋ฐฐ์ด๋ก ๊ด๋ฆฌํด์ผ ํ๋ค. ์ฐ๋ฆฌ ์กฐ์์๋ ๋จผ์ ๋ฐฐ์ด์ ์์ด๋์ด๋ฅผ ๋ ์ฌ๋ ธ๋ค.
struct thread {
...
int donate_list[64]; /* ๋ด๊ฐ ๋ฐ์ donation */
struct thread* holder; /* ๋ด๊ฐ donateํ ์ */
...
}
/* donate์ ๋ฐ๋ ์ํฉ์์๋ */
lock->holder->donate_list[curr_priority]++;
/* donate์ ํ์ํ๋ ์ํฉ์์๋ */
curr_thread->donate_list[donator_priority]--;
์ด๋ฐ ์์ผ๋ก ๊ธฐ์ฆ๋ฐ์ ์ฐ์ ์์๋ฅผ ๊ด๋ฆฌํ๋ค. ์ฐ์ ์์๊ฐ donation์ผ๋ก ์ธํด ๋ณ๊ฒฝ๋ ์ ์์ผ๋ฏ๋ก, ์ฐ์ ์์๋ฅผ ๋ฐํํ๊ฑฐ๋ ๋น๊ตํ๋ ํจ์๋ ๋ชจ๋ ๋ฐ๊พธ์ด์ค๋ค.
๋ด๊ฐ donateํ ์ค๋ ๋๋ฅผ ์๋ฏธํ๋ holder์ ์ ๋ณด๋, nested donation์ ์ํด ํ์ํ๋ค. ๋ด๊ฐ lock a์ ์ ๊ทผํ๋๋ฐ, lock a์ holder๊ฐ lock b์ waiters์ ๋ค์ด๊ฐ ์๋ค๋ฉด, lock->holder->holder
์ ๊ฐ์ ์์ผ๋ก holder๋ฅผ ๊ฒ์ํด์ lock b์ holder์๊ฒ ๋์ ์ฐ์ ์์๋ฅผ ๊ธฐ์ฆํด์ผ ํ๋ค.
/* donate์ ๊ณ ๋ คํ์ฌ ํน์ ์ค๋ ๋์ ์ต๊ณ ์ฐ์ ์์๋ฅผ ๋ฐํํ๋ ค๋ฉด */
int thread_max_priority(struct thread* t) {
int i = 0;
int max_priority = t->priority;
for(; i < 64; i++) {
if(t->donate_list[i] > 0 && i > max_priority) {
max_priority = i;
}
}
return max_priority;
}
/* ํ์ฌ ์ค๋ ๋์ ์ฐ์ ์์ ๊ตฌํ๋ ํจ์ ๊ฐฑ์ ! */
int thread_get_priority(void) {
return thread_max_priority(thread_current());
}
/* ordered list insert์ ๋น๊ตํจ์๋ ๊ฐฑ์ ! */
bool high_priority(...) {
...
return thread_max_priority(a) > thread_max_priority(b);
}
๋ง์ง๋ง์ผ๋ก, ์ค๋น ํ์ ์๋ ์ค๋ ๋์ ์ฐ์ ์์๊ฐ donation์ผ๋ก ์ธํด ๋ฐ๋ ์ ์์์ ๊ณ ๋ คํด์ผ ํ๋ค. ๋๋ถ๋ถ์ test case์์ donate์ ๋ฐ๋ ์ค๋ ๋๊ฐ main์ผ๋ก ํ๋๋ผ์ ์ ํต๊ณผ๋์์ง๋ง, ๋ง์ฝ ์ค๋น ํ์์ ๋๊ธฐํ๊ณ ์๋ ์ฌ๋ฌ ์ค๋ ๋๊ฐ donate์ ๋ฐ์๋ค๋ฉด, ์ค๋น ํ๊ฐ ์ฌ์ ๋ ฌ๋ ํ์์ฑ์ด ์๊ธด๋ค. ์ด ๋๋ ๋ฌผ๋ก thread_next_to_run
์์ ์ต๊ณ ์ฐ์ ์์๋ฅผ ๊ฒ์ํ์ฌ ๋ฝ์ ์ ์์ง๋ง, ์ฐ๋ฆฌ ์กฐ์์๋ ํ๋ฒ reorder(?) ํด์ฃผ๊ธฐ๋ก ํ๋ค.
// sync.c
void lock_acquire(struct lock* lock) {
...
/* ์ฌ๊ธฐ์ lock->holder์๊ฒ donation์ ํ๋ค๋ฉด */
/* ready_list์์ ํ๋ฒ ๋ฝ์๋ค๊ฐ ๋ค์ ์ฝ์
์ ๋ ฌํ๋ค. */
if(lock->holder->statuc == THREAD_READY) {
thread_reorder(lock->holder);
}
sema_down(&lock->semaphore);
...
}
// thread.c
void thread_reorder(struct thread* t) {
ASSERT(t->status == THREAD_READY);
list_remove(&t->elem);
list_insert_ordered(&ready_list, &t->elem, high_priority, NULL);
}
donate ๊ด๋ จ ์ ๋ณด๋ฅผ ๊ด๋ฆฌํ๋ ๋ฐฉ๋ฒ์๋ ์ด์ธ์๋ ์ฌ๋ฌ ๊ฐ์ง๊ฐ ์์ ์ ์๋๋ฐ, ์ด๋ฅผํ ๋ฉด donate์ ์ค ์ค๋ ๋๋ฅผ ๋ฆฌ์คํธ๋ก ๊ด๋ฆฌํ ์๋ ์๋ค.
struct thread {
...
struct list donate_list;
struct list_elem d_elem; // ์๋ผ๋ฆฌ ์ฐ๊ฒฐ
}
thread ๊ตฌ์กฐ์ฒด ๋ด๋ถ์ ์๋ struct list_elem
๊ฐ ์ฐ๊ฒฐํ๋ ๊ฒ์ด๊ธฐ ๋๋ฌธ์, ํ๋์ ์ค๋ ๋๊ฐ ์ฌ๋ฌ ์ค๋ ๋์ donate_list์ ๋ค์ด๊ฐ๊ฒ ๋๋ ์ํฉ์ ๊ฒฝ๊ณํด์ผ ํ๋ค.
๋ ๋ค๋ฅธ ๋ฐฉ๋ฒ์ lock๋ง๋ค ์์ ์ waiters์ ์๋ ์ค๋ ๋ ์ค max ์ฐ์ ์์๋ฅผ ๊ด๋ฆฌํด ์ฃผ๋ ๊ฒ์ด๋ค. ๊ทธ๋ฆฌ๊ณ ์ค๋ ๋๊ฐ ์์ ์ด ์์ ํ lock์ ๋ฆฌ์คํธ๋ฅผ ๊ฐ์ง๊ณ ์์ผ๋ฉด, lock์ releaseํ ๋ ๋ง๋ค lock์ ๋ฆฌ์คํธ์์ ์ญ์ ํ๋ ์์ผ๋ก ๊ตฌํํ ์๋ ์๊ฒ ๋ค. (์์ง ์๊ฐ์ผ ๋ฟ ๊ตฌํ์ ์ ํ๋ค.) ์ด ๊ฒฝ์ฐ, lock์ waiters์ max ์ฐ์ ์์๋ฅผ ์ ๊ฐฑ์ ํด ์ฃผ๋ ๊ฒ์ด ๊ด๊ฑด์ด ๋ ๊ฒ ๊ฐ๋ค.
๊ตฌํ์ ๋ฐฉ๋ฒ์ด ๋งค์ฐ ๋ค์ํ๋ค. ๊ทธ ์ค์์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๋ ์ก์๋จน๊ณ , (์ค๋ ๋ ๊ตฌ์กฐ์ฒด์ ํฌ๊ธฐ๋ ์ฝ 1KB๋ก ์ ํ๋๋ค. ์คํ์ ํฌ๊ธฐ๋ ์์์ ๋ฐฐ์ด ๋ง์ด ๋ฃ์ผ๋ฉด stack overflow ๋๋ค.) ๋ฆฌ์คํธ์ ๊ฒ์ ์๊ฐ์ ์ค์ผ ์ ์๋ ๋ฐฉ๋ฒ์ผ๋ก.. ์ ๊ท ํ์ ์ก์์ผ ํ๋ค. ๊ทธ๋ฆฌ๊ณ ๋๋ถ๋ถ์ ๊ฒฝ์ฐ ์ปค๋ ์ค๋ ๋๋ ๋ง์ด ์์ฑ๋์ง ์๋๋ค๋ ๊ฒ์ ๊ณ ๋ คํ๋ฉด ์ข๋ค.
3) multiple, nested donation ์ํฉ์ ๊ณ ๋ คํ์
multiple donation ์ํฉ์ ํ ์ค๋ ๋๊ฐ ์ฌ๋ฌ ๊ฐ์ lock์ ๋ค๊ณ ์๋ ์ํฉ์ด๋ค.
thread 0 = low
thread 1 = mid
thread 2 = high
thread 0 ์ด lock a๋ฅผ ๊ฐ๋๋ค.
thread 0 ์ด lock b๋ฅผ ๊ฐ๋๋ค.
thread 1 ์ด ์์ฑ๋์ด lock a์ ์ ๊ทผํ๋ค.
thread 2 ๊ฐ ์์ฑ๋์ด lock b์ ์ ๊ทผํ๋ค.
thread 0 ์ด lock a๋ฅผ ํผ๋ค.
thread 0 ์ด lock b๋ฅผ ํผ๋ค.
์ด ๊ฒฝ์ฐ, thread 0์ ์ฐ์ ์์๋ low โ mid โ high ๋ก ๋์์ง๋ค. ๊ทธ๋ฆฌ๊ณ lock a๋ฅผ ํ ๋, ์ฐ์ ์์๊ฐ high๋ก ์ ์ง๋์ด์ผ ํ๋ค. ์? lock b์ waiters๋ก thread 2(high)๊ฐ ์๊ธฐ ๋๋ฌธ์ด๋ค. ์ฐ์ ์์๋ฅผ ๊ธฐ์ฆํ๊ณ .. ํ์ํ๊ณ ์ด ๋๋ฆฌ๋ฅผ ์ ์น๋์ง๋ฅผ ์๊ฐํด ๋ณด์. ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์ ์์ ์ ๋นจ๋ฆฌ ์ฒ๋ฆฌํ๊ธฐ ์ํด์์ด๋ค. ์ฆ, thread 0์ ์ฐ์ ์์๊ฐ high๋ก ๋์์ง ์ด์ ๋, thread 2(high)๋ฅผ waiters์์ ๋นจ๋ฆฌ ๋ด๋ณด๋ด๊ธฐ ์ํจ์ด๋ฏ๋ก, lock a๋ฅผ ํ์๋ค๊ณ ํด์ thread 1(mid)๋ฅผ ๋จผ์ ์คํํ๋ ๊ฒ ์๋๋ผ lock b๋ฅผ ๋นจ๋ฆฌ ํ์ด์ค์ผ ํ๋ ๊ฒ์ด๋ค.
๋ฐ๋ผ์ thread 0๋ lock a๋ฅผ ํ๊ณ , thread 1๋ก๋ถํฐ ๊ธฐ์ฆ๋ฐ์๋ ์ฐ์ ์์ mid๋ฅผ ๋ฐํํ๋ค. (donate_list์์ ์ญ์ ํ๋ค.) ๊ทธ๋ฆฌ๊ณ ๊ธฐ์ฆ๋ฐ์ ์ฐ์ ์์ high๋ฅผ ์ ์งํ๋ค. ๊ทธ๋ฌ๋ฉด thread 2(mid)๋ ready_list๋ก ๋ค์ด๊ฐ๊ณ , current thread๋ ์ฌ์ ํ thread 0์ด๋ฏ๋ก ๋ค์ ๋ผ์ธ์ผ๋ก ๊ฐ์ lock b๋ฅผ ํผ๋ค. ์ด ๋ thread 2๋ก๋ถํฐ ๊ธฐ์ฆ๋ฐ์๋ high๋ฅผ ๋ฐํํ๊ณ , ์ฐ์ ์์๊ฐ low๋ก ๋ฎ์์ ธ ready_list๋ก ๋ค์ด๊ฐ๋ค. ๋ฐํ์ด ๋ชจ๋ ๋๋ฌ์ผ๋ฏ๋ก thread 2(high)๊ฐ ๋จผ์ ์คํ๋๊ณ , thread 1(mid)๊ฐ ์คํ, ๋ง์ง๋ง์ผ๋ก thread 0(low)๊ฐ ์คํ๋๋ค.
์ด์ ๋ฐ๋ผ ์ฝ๋๋ฅผ ์ง๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
/* lock acquire ํ ๋ ๊ธฐ์ฆ์ ํ๋ค */
void lock_acquire(struct lock* lock) {
struct thread* curr = thread_current();
struct thread* holder = lock->holder;
if(thread_max_priority(curr) > thread_max_priority(holder)) {
holder->donate_list[curr->priority]++;
}
sema_down(lock->semaphore);
lock->holder = thread_current();
}
/* sema์ waiters๋ฅผ ์ฐ์ ์์์์ผ๋ก ๋บธ๋ค */
void sema_up(struct semaphore *sema) {
...
/* ํ์ฌ ์ค๋ ๋ ๋ค์์ผ๋ก sema๋ฅผ ์ก์ ์ */
struct list_elem* next_elem;
struct thread* next;
if(!list_empty(&sema->waiters)) {
next_elem = min(&sema->waiters, high_priority, NULL); // less func์ด๋ฏ๋ก min
next = list_entry(next_elem, struct thread, elem);
list_remove(next);
thread_unblock(next);
}
sema->value++;
intr_enable();
}
/* donate ํ์ */
void lock_release(struct lock* lock) {
struct list_elem* curr_elem;
struct thread* curr;
struct list* waiters = &lock->semaphore->waiters;
if(!list_empty(waiters)) {
for(curr_elem = list_begin(waiters);
curr_elem != list_end(waiters);
curr_elem = list_next(curr_elem);) {
curr = list_entry(curr_elem, struct thread, elem);
lock->holder->donate_list[curr->priority]--;
}
}
lock->holder = NULL;
sema_up(&lock->semaphore);
}
nested donation์ ํ๋์ ์ค๋ ๋๊ฐ lock a์ ์ ๊ทผํ์ ๋, lock a์ holder๊ฐ lock b๊ฐ ํ๋ฆฌ๊ธฐ๋ฅผ ๋๊ธฐํ๊ณ ์๋ ์ํฉ์ด๋ค. nested๊ฐ ์ฐ์์ ์ผ๋ก ๋ํ๋๋ฉด chain์ผ๋ก ๋ณผ ์ ์๋ค. (๊ผฌ๋ฆฌ๋ฌผ๊ธฐ..)
thread 0 = 3 priority
thread 1 = 6 priority
thread 2 = 9 priority // ํด์๋ก ๋์
thread 0 ์ด lock a๋ฅผ ๊ฐ๋๋ค.
thread 1 ์ด ์์ฑ๋์ด lock b๋ฅผ ๊ฐ๋๋ค.
thread 1 ์ด lock a์ ์ ๊ทผํ๋ค. waiters๋ก ๋ค์ด๊ฐ ๋๊ธฐ.
thread 2 ๊ฐ ์์ฑ๋์ด lock b์ ์ ๊ทผํ๋ค.
์ด ๊ฒฝ์ฐ thread 2๋ lock b์ holder์ธ thread 1์ด ๋นจ๋ฆฌ lock a๋ฅผ ํ๋ํ๊ณ , ์คํ๋์ด lock b๋ฅผ ํ์ด์ค ์ ์๋๋ก ์์ ์ ์ฐ์ ์์์ธ 9๋ฅผ thread 1์๊ฒ ๊ธฐ์ฆํ๋ค. ๊ทธ๋ฆฌ๊ณ thread 1์ด ์ ๊ทผํ๊ณ ์ ํ๋ lock a์ holder์ธ thread 0์๊ฒ๋ 9๋ฅผ ๊ธฐ์ฆํ๋ค. ๊ทธ๋์ผ thread 0์ด lock a๋ฅผ ๋นจ๋ฆฌ releaseํ ์ ์๊ธฐ ๋๋ฌธ์ด๋ค.
ํ์ฌ ์ผ์ด์ค์์๋ thread 0๋ง ์๊ธฐ ๋๋ฌธ์ ์ ์ฐ์ ์์ 9๊ฐ thread 0์๊ฒ๊น์ง ๊ธฐ์ฆ๋์ด์ผ ํ๋์ง ํ์์ฑ์ด ๋๊ปด์ง์ง ์์ ์ ์์ง๋ง, ๋ง์ฝ thread 3์ด 8์ ์ฐ์ ์์๋ฅผ ๊ฐ์ง๊ณ ๋๊ณ ์๋ค๊ณ ์๊ฐํด๋ณด์. thread 2๋ 8๋ณด๋ค ๋์ ์ฐ์ ์์๋ฅผ ๊ฐ์ง๊ณ ์์์๋ ๋ถ๊ตฌํ๊ณ , thread 0์ด lock a๋ฅผ ๊ฐ์ง๊ณ ์์ผ๋ฏ๋ก ๋จผ์ ์คํ๋์ง ๋ชปํ๋ค. ๋ฐ๋ผ์, thread 2๋ ์์ ์ ์ฐ์ ์์๋ฅผ nested lock์ ์ต์ข ์ ์ผ๋ก ๊ฐ๊ณ ์๋ thread 0์ผ๋ก ๊ธฐ์ฆํ์ฌ ๋น ๋ฅด๊ฒ lock์ ํด์ํ ์ ์๋๋ก ํด์ผ ํ๋ค.
์ด๋ฅผ ๊ตฌํํ๊ธฐ ์ํด thread ๊ตฌ์กฐ์ฒด ๋ด์ holder (์ด ์ค๋ ๋๊ฐ ์ฐ์ ์์๋ฅผ ๊ธฐ์ฆํ ์ค๋ ๋) ํ๋๊ฐ ์ฌ์ฉ๋๋ค. ๊ธฐ์ฆ์ while๋ฌธ์ ๋๋ฉด์ ํ๊ณ , ๋ฐํ ์ญ์ ์ด์ค for๋ฌธ์ ๋๋ฉด์ ํ๋ค.
void lock_acquire(struct lock *lock) {
/* nested priority donation */
struct thread *holder = lock->holder;
struct thread *curr = thread_current();
while (holder) {
if (thread_max_priority(curr) > thread_max_priority(holder)) {
holder->donate_list[thread_max_priority(curr)]++;
holder = holder->holder;
} else
break;
}
/* lock holder๊ฐ ready list์ ์์๋ค๋ฉด */
if (lock->holder && lock->holder->status == THREAD_READY) {
thread_reorder(lock->holder);
}
/* ๋์ ํ๋๋ฅผ ํ์ฌ lock->holder๋ก ์ค์ */
thread_current()->holder = lock->holder;
sema_down(&lock->semaphore);
lock->holder = thread_current();
}
void lock_release(struct lock *lock) {
if (!list_empty(&lock->semaphore.waiters)) {
struct list_elem *curr;
struct thread *donator;
/* ๋ค์์ผ๋ก holder๊ฐ ๋ ์ค๋ ๋ */
struct list_elem *next_elem =
list_min(&lock->semaphore.waiters, high_prio, NULL);
struct thread *next = thread_entry(next_elem);
for (curr = list_begin(&lock->semaphore.waiters);
curr != list_end(&lock->semaphore.waiters); curr = list_next(curr)) {
donator = thread_entry(curr);
/* waiter๊ฐ ๊ธฐ์ฆ๋ฐ์๋ ์ฐ์ ์์ ๋ฐํ for nested */
for (int i = 0; i < 64; i++) {
if (donator->donate_list[i] > 0) {
thread_current()->donate_list[i]--;
}
}
/* waiter์๊ฒ์ ๊ธฐ์ฆ๋ฐ์ ์ฐ์ ์์ ๋ฐํ */
thread_current()->donate_list[donator->priority]--;
donator->holder = next;
}
/* ๋์ holder๋ NULL */
thread_current()->holder = NULL;
}
lock->holder = NULL;
sema_up(&lock->semaphore);
thread_yield(); /* ์์์ unblock๋ ์ ๊ฐ ์ฐ์ ์์๊ฐ ๋ ๋์ผ๋ฉด ์ค์ผ์ค */
}
๊ธฐ์ฆ๊ณผ ๋ฐํ์ ์ ์ํํ๊ณ , ์๋ ์๋ thread ์ ๋ณด ์ธ์ ์๋ก ์๊ธด donate_list, holder ์ ๋ณด๋ฅผ ์ ๊ด๋ฆฌํด์ฃผ๋ฉด ๋๋ค. ์ด์ธ์๋ semaphore, conditional variable์์๋ ์ฐ์ ์์๋๋ก down, wake ํ ์ ์๋๋ก thread_yield๋ฅผ ์ ์ ํ ์คํํด์ค๋ค.
๋๊ธฐํ์ ๊ดํ ๋ฌธ์ ๋ ์ฌ๋ฌ ์ค๋ ๋์ ์คํ ์์๋ฅผ ๋จธ๋ฆฟ์์ผ๋ก ๋ฐ๋ผ๊ฐ๊ธฐ ํ๋ค๋ค๋ ์ ์์ ์ด๋ ต๊ฒ ๋๊ปด์ง๋ ๊ฒ ๊ฐ๋ค. ๊ฐ ํจ์๋ง๋ค printf๋ฅผ ์ฌ์ด ๋๊ณ ์ ์ฒด ์ฝ๋ ํ๋ฆ์ด ์ด๋ป๊ฒ ๋๋์ง๋ฅผ ๋จผ์ ์ดํดํด๋ณด๋ ๊ฒ์ด ๋์์ด ๋์๋ค. ๋, donation๊ด๋ จ ์ ๋ณด๋ฅผ ์ด๋ป๊ฒ ๊ด๋ฆฌํ ์ง ๊ทธ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ง๋ ๊ฒ์ด ๊ต์ฅํ ๋ค์ํ ์ ์๊ฒ ๋ค๋ ์๊ฐ์ด ๋ ๋ค. lock์ releaseํ ๋ ์ด์ค for๋ฌธ์ ๋์ง ์๊ธฐ ์ํด, ํ๋์ lock์ผ๋ก ์ธํด ๊ธฐ์ฆ๋ฐ์ ์ต๋์ ์ฐ์ ์์๋ง์ ์ ์ฅํด๋์ด๋ ์ข์ ๊ฒ ๊ฐ๋ค. donate๊ฐ ์ด๋ฃจ์ด์ง๋๋ง๋ค ์ต๋๊ฐ์ ๊ฐฑ์ ํ๋ฉด์. ์ฌ๋ฌ ๊ฐ์ง ๋ฐฉ๋ฒ์ด ์์์ ์๊ณ , ๊ฐ ๋ฐฉ๋ฒ์ ๋จ์ ๊ณผ ์ฅ์ ์ ์๊ณ ํด์ ๊ท ํ ์กํ ๊ตฌํ๋ฐฉ๋ฒ์ ํํ ์ ์๋๋ก ํ๊ณ ์ถ๋ค. ์ผ๋จ์ ํ์ฌ ์ฝ๋๊ฐ ์ ๋ง๋ก (test case ๋ฟ๋ง ์๋๋ผ) ๋ชจ๋ donation ์ํฉ์์ ์๋๋๋ก ๋์ํ๋ ๊ฒ์ด ๋ง๋์ง ๋ฐ๋ก๋ฅผ ์กฐ๊ธ ๋ ์๊ฐํด๋ด์ผ๊ฒ ๋ค.
์ฝ๋๋์ ์ ์๋ฐ ํ ๋ผ์ธ ์น๋๋ฐ ํ์๊ฐ์ฉ ๊ฑธ๋ฆฐ๋ฏ
2023.10.03 ์์ : ํ์ฌ ์ฝ๋์ ๋ฐ๋ก๋ฅผ ๋ฐ๊ฒฌ. test code์์ ์ฒ๋ฆฌ๋์ง ์์ ๋ฐ๋ก๊ฐ ์์.
'DevLog ๐จ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[DevLog][PintOS] PRJ1 Threads/PintOS ์ค๋ ๋๋ ์ด๋ป๊ฒ ๋์๊ฐ๊น? (0) | 2023.10.03 |
---|---|
[DevLog][PintOS] PRJ1 Threads/Scheduling Algorithms (0) | 2023.10.03 |
[DevLog][CSAPP] 10์ฅ ์์คํ ์์ค ์ ์ถ๋ ฅ (10.1~10.5) (0) | 2023.09.24 |
[DevLog][CSAPP] 9์ฅ 9.9 malloc lab ๋์ ํ ๋น๊ธฐ ๊ตฌํ (0) | 2023.09.24 |
[DevLog][CSAPP] 9์ฅ ๊ฐ์๋ฉ๋ชจ๋ฆฌ (9.1~9.4) (0) | 2023.09.10 |