Priority Inverstion Problem은 thread가 두 개 이상의 lock보유가능할 때, 높은 priority의 thread가 낮은 priority의 thread보다 늦게 실행될 수 있는 문제점을 말한다. 아래 예시를 보자.
그림 1의 상황은 이렇다. 현재 Priority 31의 thread가 running 중이다. (A)는 lock A의 소유권을 가지고 있다는 뜻이다. Read List와 Blocked List가 모두 비어있다. 이제 여기에 lock A를 원하는 높은 priority의 thread가 들어온다고 해보자. 그렇다면 priority가 높은 thread가 running thread가 될 것이다.
39은 running_thread가 되었으나 lock A를 보유하고 있지 않기 때문에 A의 대기리스트 (Requiring lock A) 로 들어간다(lock을 한번 들고있으면 이 lock을 뺏을 수 있는 방법은 없다. lock을 소유하는 thread가 작업이 끝날 때까지 기다려야 한다.).
그런데 여기서 lock B를 들고있는 priority 32의 thread가 들어온다고 해보자. 그러면 이 thread는 running thread가 될 것이다. 현재 39가 제일 높음에도 불구하고 32가 running thread가 되었다는 것을 기억하자. 심지어 32는 39와 상관없는 lock B를 들고있다.
그러면 이제 계속해서 32(B)를 원하는 33, 34, 35, 36이 들어온다고 해보자. 그 thread들은 lock B를 원하기 때문에 requiring lock B에서 잠들고 있을 것이다.
이제 32(B)가 끝났다고 해보자. 32는 running thread를 반납하기 전에 lock B를 반납하면서 lock B 대기리스트 중 가장 높은 Priority의 thread를
ready list로 보낼 것이다. 여기서 문제는 36이 31보다 우선순위가 높기 때문에 36이 대기리스트의 맨 앞으로 올 것이다.
이제 문제점이 보이는가? 36이 39보다 우선순위가 높음에도 불구하고 먼저 실행되고 있다. 만약 31 < priority < 39 의 스레드가 계속해서 들어오면 39는 thread들 중 우선순위가 가장 높은에도 불구하고 영원히 실행되지 못 할수도 있다(Starvation 문제).
그렇다면 이 문제를 어떻게 해결해야 하는가?
39는 31에게 Priority를 빌려줘서 39보다 낮은 thread보다 먼저 작업이 끝내게 해야한다. 39는 donation을 통해 31의 priority를 일시적으로 39로 만든다. 그렇다면 그림 7에서 32의 작업이 끝나고 lock b를 반납해서 36을 ready list로 올려 보내도, 31의 현재 priority(39)가 36보다 높기 때문에 running thread를 지속할 수 있다.
※ 엄밀히 말하면 39가 들어와서 lock A 대기리스트에 간 시점에 31에게 자신의 priority를 donation함으로써 31의 임시 priority가 39가 되기 때문에, 32가 들어와도 running thread를 뺏기지 않을 것이다.
33, 34, 35, 36 331이 작업이 끝나면 lock A를 반납하고 39는 ready list에 올라가서 다음 running thread를 두고 36과 경쟁한다. 그러나 39가 더 높으므로 36보다 먼저 running thread에 들어갈 수 있을 것이다.
요약하면, lock A를 요구하는 priority가 높은 thread가 lock A를 쥐고있지 않아 running할 수 없을 때, 자신의 priority를 lock A의 주인에게 빌려준다(donation). 그러면 lock A의 주인이 먼저 작업을 끝낼 수 있을 것이고, 다음으로 높은 priority의 thread가 실행될 수 있을 것이다.
이렇게 priority가 높은 thread가 낮은 thread보다 늦게 실행되는 것을 방지할 수 있다. 이제 코드를 살펴보자.
int init_priority;thread의 priority는 donation을 통해 변할 수 있다. 그렇기에 원래 priority를 기억하는 변수를 하나 만들어야한다. 원래 priority를 init_priority에 저장한다.
struct lock *wait_on_lock;thread가 원하는 lock이 이미 다른 thread에 의해 점유 중일 때, lock의 주소를 저장한다.
struct list donations;A thread가 B thread에 의해 priority가 변경되었다면 A thread의 list donations에 B thread를 기억해놓는다. 이는 차후에 쓰일 것이다. (자신에게 기부한 기부자 목록이라고 생각하자.)
struct list_elem donation_elem;또한 B thread는 A thread의 기부자 목록 (list donations)에 자신의 이름을 새겨놓아야한다. 이를 donation_elem을 통해 새겨놓는다.
그러면 thread 구조체의 코드는 다음과 같이 된다.
@/include/threads/thread.h
struct thread {
/* Owned by thread.c. */
tid_t tid; /* Thread identifier. */
enum thread_status status; /* Thread state. */
char name[16]; /* Name (for debugging purposes). */
int priority; /* Priority. */
/* Shared between thread.c and synch.c. */
struct list_elem elem; /* List element. */
// 깨어나야할 tick 저장 (wakeup_tick)
int64_t wakeup_tick;
/*-------------------------- project.1-Priority Donation -----------------------------*/
int init_priority;
struct lock *wait_on_lock;
struct list donations;
struct list_elem donation_elem;
/*-------------------------- project.1-Priority Donation -----------------------------*/
다음은 thread의 구조가 변했으므로, thread를 만들 때, 초기화해줄 항목도 늘어났다. thread가 막 만들어졌으면, priority와 init_priority는 똑같이 인자priority를 받을 것이다.
그리고 wait_on_lock역시 처음에는 아무것도 없을 것이므로 (신생 thread가 lock을 요구한다고 해도, 실제 요구하는 시점은 running_thread가 되어서 처음으로 요구한다. 그 때, wait_on_lock이 갱신된다.) NULL을 요구한다.
donations는 리스트형 구조이므로 리스트 초기화 함수를 사용한다.
@/threads/thread.c
/* Does basic initialization of T as a blocked thread named
NAME. */
static void
init_thread(struct thread *t, const char *name, int priority)
{
ASSERT(t != NULL);
ASSERT(PRI_MIN <= priority && priority <= PRI_MAX);
ASSERT(name != NULL);
memset(t, 0, sizeof *t);
t->status = THREAD_BLOCKED;
strlcpy(t->name, name, sizeof t->name);
t->tf.rsp = (uint64_t)t + PGSIZE - sizeof(void *);
t->priority = priority;
t->magic = THREAD_MAGIC;
/*-------------------------- project.1-Priority Donation -----------------------------*/
t->init_priority = priority;
list_init(&t->donations);
t->wait_on_lock = NULL;
/*-------------------------- project.1-Priority Donation -----------------------------*/
}
어떤 thread가 running_thread가 되었을 때, 어떤 lock이 필요하다면 lock을 요청한다.
만약 lock이 이미 다른 thread에 의해 점유 중이라면 그 thread에게 자신의 priority를 donation하고, 해당 thread의 doantions에 자신의 이름을 새겨놓는다. (※ 해당 thread가 현재 thread보다 priority가 높으면 어떡하죠? 라는 의문이 생길 수 있는데, 이미 running thread가 되었다는 자체가 현존하는 thread 중에서 가장 priority가 높은 thread라는 것이다.)
@/threads/synch.c
void
lock_acquire (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (!intr_context ());
ASSERT (!lock_held_by_current_thread (lock));
/*-------------------------- project.1-Priority Donation -----------------------------*/
struct thread *t = thread_current();
if (lock->holder != NULL)
{
t->wait_on_lock = lock;
list_push_back(&lock->holder->donations, &t->donation_elem);
donate_priority();
}
/*-------------------------- project.1-Priority Donation -----------------------------*/
sema_down (&lock->semaphore);
/*-------------------------- project.1-Priority Donation -----------------------------*/
// lock->holder = thread_current ();
t->wait_on_lock = NULL;
lock->holder = t;
/*-------------------------- project.1-Priority Donation -----------------------------*/
}위 코드에서 donate를 한 뒤에 sema_down()이 된 것에 주의하라. 이 thread는 기존 lock의 주인이 작업을 끝나기 전까지는 block상태로 들어가 sema_down에서 머물것이다. lock의 주인이 작업을 끝내고 lock을 반납하면 sema_down()의 while문을 벗어나 다음 단계 (t->wait_on_lock = NULL) 로 진입한다.
위의 세 개의 함수를 선언한다.
@/include/threads/thread.h
/*-------------------------- project.1-Priority Donation -----------------------------*/
void donate_priority (void);
void remove_with_lock (struct lock *);
void refresh_priority (void);
/*-------------------------- project.1-Priority Donation -----------------------------*/
donation을 실행하는 함수이다. 여기서 lock과 연결된 모든 스레드들을 순회하며 priority를 기부한다. 이는 아래 상황과 같다.
이 때, 39는 A, B, C의 주인인 31, 33, 35에게 donation을 실시한다. (36는 39가 원하는 lock의 주인이 아니기 때문에 donation을 받지 않는다.)
※ 엄밀히 말하면, 31은 33, 35, 36으로부터 donation을 받아서 priority가 (36)이 되어있을 것이고, 33는 35, 36으로부터 donation을 받아서 (36), 35는 36으로부터 donation을 받아서 (36)이 되어 있을 것이다. 이는 아래에서 상세히 기술하겠다. 일단은 무시하고 진행하길 바란다.
그렇다면 31(A)->33(B)->35(C)->39->36 순으로 실행될 것이다.
특히 C의 대기 리스트에는 39가 36보다 앞에 있는 것에 주목하라 (list에 삽입할 때, priority 순위로 정렬되어 있다.). 36는 39가 원하는 lock의 주인이 아니기 때문이다.
그러면 다음과 같은 상황은 어떨까?
39는 lock A, B, C, D가 모두 필요한데, 이미 이 lock들은 타 thread가 점유하고 있다. (ready list의 thread들) 이 때, 39는 lock A, B, C, D 를 각각 소유하고 있는 31, 32, 33, 34들이 먼저 작업을 완료하고 lock을 반납하게 해야 최우선적으로 작업을 수행할 수 있다.
하지만 여기서 유의해야할 것은 lock이 비어있는지를 확인하는 lock_acquire()는 한번에 한 lock에 대해서만 실시한다. 예를 들면, 39는 A, B, C, D가 필요한데, running thread일 때, 우선 A에 대해서 lock_acquire()를 실시한다. 그런데 A의 주인이 이미 있으므로(31) A에게 priority를 넘기고, 바로 A의 대기 리스트로 들어간다. B, C, D의 주인 thread의 priority는 바뀌지 않는다.
그래서 A가 작업이 끝나면, A의 대기 리스트에서 39를 ready list로 보낼 것이고, 그 다음 39는 A를 획득한다. 그러나 B를 획득하지 못했으므로 다시 B의 주인인 32에게 donation하고 이번에는 B의 대기 리스트에 들어갈 것이다. 그 작업을 반복하면서 A, B, C, D를 모두 획득해야 비로소 작업을 시작할 것이다.
다시 설명으로 돌아가서 코드를 구현해보자.
현재 thread가 lock과 연결된 모든 스레드들을 순회한다는 것은 그림 10의 상황이다. 39가 C를 원하는데, C의 holder는 B를 원하고, B의 holder는 A를 원한다. 이렇게 원하는 lock의 holder가 다른 lock을 원한다면 그 lock의 holder까지 donation을 하는 것을 Nested Donation이라고 한다. PintOS에는 nested depth를 8까지만 제한한다.
@threads/thread.c
void donate_priority (void)
{
int cnt = 0;
struct thread *t = thread_current();
int cur_priority = t->priority;
while ( cnt < 9 )
{
cnt++;
if (t->wait_on_lock == NULL)
{
break;
}
t = t->wait_on_lock->holder;
t->priority = cur_priority;
}
}만약 lock의 holder가 원하는 lock이 없다면 nested donation을 중지해야한다 (IF문).
원하는 lock이 있다면 lock의 holder에게도 current thread의 priority를 준다.
리스트 구조체인 donations는 이미 donate_priority()에서 사용했지만, 자세한 구조는 살펴보지 않았다.
그리고 그림 10에서 '※ 엄밀히 말하면, ~' 을 기억하는가? 전문은 아래와 같다.
※ 엄밀히 말하면, 31은 33, 35, 36으로부터 donation을 받아서 priority가 (36)이 되어있을 것이고, 33는 35, 36으로부터 donation을 받아서 (36), 35는 36으로부터 donation을 받아서 (36)이 되어 있을 것이다. 이는 아래에서 상세히 기술하겠다. 일단은 무시하고 진행하길 바란다.
이 때, 31의 donations에는 33, 35, 36이 기록되어 있다. 이 기록이 어떻게 진행되어왔는지를 재구성해보자.
31(A)가 running중인데 lock A를 요구하는 33(B)가 들어왔다고 해보자. 그러면 33은 priority가 높기 때문에 31을 밀어내고 running thread가 될 것이지만, A가 없기때문에 31에게 donation을 하고 A의 대기리스트로 갈 것이다.
이 때, 31의 Donations (list구조체인 것을 기억하자.) 에 33의 ELEM이 들어온다.
(thread의 구조체에 struct list donations와 struct list_elem donation_elem 이 추가된 것을 기억하자. 그 donation_elem이다. struct list_elem elem과는 또다른 elem이라는 것을 명심하자.)
이제 B를 요구하는 thread 35가 들어왔다. 당연하게도 lock B는 33이 들고있으므로 donation을 수행하고 lock B의 대기리스트로 들어갈 것이다.
주의할 것은 35는 nested donation으로 인해 33은 물론, 31에도 donation을 했음에도 불구하고 31의 donations에 있지 않다. 그 이유는 31이 35로부터 donation을 받은 이유가, 35는 33의 lock B를 원하고, 그 33은 31의 lock A를 원하기 때문에 donation을 받은 것이지, 35가 31한테 직접적으로 바라는 것이 없다. (33을 통해 31이 donation을 받은 것이다.)
그렇기 때문에 31의 donations에는 33만 있고, 35는 없다.
이렇게 반복하면 그림 11에서 donations는 다음과 같이 될 것이다.
이것이 donations의 메커니즘이다. 이제 새로 만들 함수를 살펴보자.
이 함수들은 다음과 같은 상황에서 일어난다.
※ thread는 priority가 낮은 순대로 삽입되었다고 가정한다.
현재 31이 lock A와 B를 들고 작업을 수행하고 있다. lock A에는 33과 35가 대기하고 있다. lock B에는 34와 36이 대기하고 있다. lock C는 39가 대기 중인데, 34가 C를 들고 있기 때문에 31과 34가 donation을 받고 있는 상태이다.
이 상황에서 donations를 보자.
이 상황에서 31이 lock B를 반환한다고 해보자. (31은 여전히 lock A를 들고있다.)
lock B가 해제되었으므로, lock B를 들고있었기 때문에 받고있던 donation이 해제된다. 이제 해제를 구현하는 함수인 remove_with_lock() 을 추가해보자.
@threads/thread.c
void remove_with_lock (struct lock *lock)
{
struct thread *t = thread_current();
struct list_elem *e = list_begin(&t->donations);
for (e ; e != list_end((&t->donations));)
{
struct thread *cur = list_entry(e, struct thread, donation_elem);
if (cur->wait_on_lock == lock)
{
e = list_remove(e);
}
else
{
e = list_next(e);
}
}
}thread *t 는 현재 running중인 thread를 말한다. (그림 20에서 thread 31)
그리고 31의 donations를 순회한다. 만약 donation_elem의 주인 thread가 이제 해제한 lock이면 그 elem을 리스트에서 제외한다.
그러면 그림 21에서 lock B에 대해 remove_with_lock()을 실행하면 어떻게 될까?
그림 22와 같이 된다. 그런데 이상한게 하나 있지 않은가?
31의 priority는 39였는데, 이는 lock B를 원하는 34로 부터 받은 priority였다. (물론 34는 39로부터 받았고)
그런데 lock B가 해제되었으니 더이상 donation을 받을 이유가 없어진다.
다음 그림이 그 상황이다.
우선, lock B가 해제되었으므로 34로부터 받은 prioirty를 버려야한다.
하지만, running_thread인 31은 여전히 A를 들고있으므로, A의 대기 리스트 중에서 가장 높은 priority인 35를 받아온다.
그래서 lock이 해제되었을 때, priority를 갱신하는 작업이 필요하다. 그것이 refresh_priority()이다. (lock_release에서 remove_with_lock()을 실행하고 바로 refresh_priority()를 실행했던 것을 기억하자.)
@threads/thread.c
void refresh_priority (void)
{
struct thread *curr = thread_current();
curr->priority = curr->init_priority;
if (list_empty(&curr->donations) == false)
{
list_sort(&curr->donations, &cmp_priority, NULL);
struct thread *high;
high = list_entry(list_front(&curr->donations), struct thread, donation_elem);
if (high->priority > curr->priority)
{
curr->priority = high->priority;
}
}
}lock이 해제되었을 때, 여전히 thread_current (=running_thread)가 다른 lock을 들고 있어서 donation을 받을 수 있다면, donations에서 priority 순으로 정렬하고, 그 중 가장 높은 prioirty를 받아온다.
※ if 문으로 donations의 가장 높은 priority가 현재 priority보다 높으면 갱신한다 라고 되어있는데, 얼핏 보면 당연히 donations에 있는 priority는 항상 running thread의 priority보다 높을 거라고 생각한다. 왜냐하면, donations에 들어가는 전제 자체가 running thread보다 높아야 들어가기 때문이다. 왜 이 if문을 넣는지는 아래에서 설명하겠다.
그것을 수행하면 그림 23처럼 된다. 그런데 여전히 그림 23에서 이상한 점이 하나 있다. 무엇일까?
31의 priority가 갱신되어서 35가 되었는데, lock B의 대기리스트의 34의 priority가 39로 더 높다. 그래서 refresh_priority()가 실행되면 thread들의 priority 상태에 따라 running thread가 교체될 수 있다. 이는 지난 시간에 구현한 test_max_priority()를 가져다쓰면 된다.
이제 마지막으로 현재 running_thread의 priority (init priority를 말한다.) 가 변경되었을 때를 생각하자.
만약 running_thread의 lock을 원하는 타 thread가 있다면, running_thread의 init_prioirty가 변경되었어도 lock의 보유는 그대로이므로 다시 donation을 받아 priority를 높일 수 있다.
이 ppt에서 이상한 점이 하나 있는데, donate_priority()는 실행할 필요가 없다. 왜냐하면 현재 running_thread()는 running하는데 필요한 lock을 모두 획득한 상태인데, donate_priority()는 필요한 lock이 없을 때 실행하는 함수이기 떄문이다. 그래서 thread_set_priority()와 test_max_prioirty()만 실행한다. 이 두 함수는 이미 구현되어있다.
@threads/thread.c
/* Sets the current thread's priority to NEW_PRIORITY. */
void thread_set_priority(int new_priority)
{
thread_current()->init_priority = new_priority;
/*-------------------------- project.1-Priority Scheduling -----------------------------*/
// test_max_priority();
/*-------------------------- project.1-Priority Scheduling -----------------------------*/
/*-------------------------- project.1-Priority Donation -----------------------------*/
refresh_priority();
test_max_priority();
/*-------------------------- project.1-Priority Donation -----------------------------*/
}현재 thread의 priority가 변경되었다면, refresh_priority()가 실행되어야한다. 그래야 priority가 내려가도 다시 donation을 받을 수 있다.
그런데 현재 thread의 priority가 donations의 모든 priority보다 높아졌다면? 그러면 donation을 받을 필요가 없어진다.
이 때문에 refresh_priority()에서 if문을 걸어준 것이다. 만약 if문이 없이 refresh()를 한다면 priority가 init_priority()보다 낮아질 가능성이 있다.
'Pintos Project > Project 1' 카테고리의 다른 글
| [PintOS, Project1] Priority_Scheduling and Synchronization (semaphore 관련) (0) | 2021.02.04 |
|---|---|
| [PintOS, Project1] Condition Variable을 이용한 Monitor System (0) | 2021.02.04 |
| [PintOS, Project1] Priority_Scheduling (1) | 2021.02.03 |
| [PintOS, Project 1] Alarm Clock 구현 (4) | 2021.02.01 |
| [PintOS, Project 1] 1/30 : 공부 노트 - 각종 관련 함수들 (0) | 2021.01.31 |
댓글