WIL(weekly I learned)
1) 과제개요 : Priority Inversion Problem 해결
이번 과제에서는 Priority inversion Problem 해결하는 것이 목표이며, 이를 위해서 3가지 도네이션 기능을 구현해야 한다.
Priority Inversion이란?
- 우선순위가 높은 thread가 우선순위가 낮은 스레드를 기다리는 현상이다. 아래의 그림을 보자.
priority 는 값이 클수록 우선순위가 높은 것을 의미하며 위의 이미지를 보면, 우선순위가 낮은 연두색 L이 실행되는데 우선순위가 높은 H가 Lock을 요청하고 기다리는 상태인데 H보다 낮은 M이 먼저 실행되는 문제가 발생하는데 이를 Inversion이 발생했다고 한다.
L이 CPU에 올라가서 공유 데이터 A를 사용하고 있을때 우선순위가 높은 H가 들어오면 아래와 같이 된다.
H가 CPU를 선점했고, L은 Ready_list로 돌아간다. 하지만, H는 공유 데이터 A를 쓰고 싶은데(Lock을 acquire하고 싶은데), 이미 데이터 A에 대한 Lock을 L이 쥐고 있기 때문에, H는 해당 Lock A 을 얻기 위해서 대기자 Waiters list로 들어가게 된다.
그러고 Ready_list에 있던 L이 CPU에 다시 올라가고, M이 새롭게 들어온다. 근데 M이 원하는 공유 데이터가 다른 경우에 문제가 발생한다.
H는 M이 본인의 뒤로 오는걸 기대 했지만,
M은 L의 공유 데이터 A가 아니라 공유 데이터 B만 쓰면 되기 때문에, L을 미뤄내고도 계속 그 자리를 차지하고 있는다. 근데 이제 더 큰 문제는 아래의 경우다.
L이 Ready list에 있다가 lock이 realease 되어서 H 가 실행되어야 하는데, L보다 높은 우선순위를 가지고 있는 Thread 들이 ready_list에 들어오는 경우이다.
게다가 L보다 높은 우선순위의 M1, M2, M3 들은 공유데이터 B만 필요로 하기 때문에 이 Thread들이 전부 처리될 때까지 H는 그대로 굶어 죽는 Starvation이 발생한다.
2) 해결방법 : Priority Donation
위의 그림과 같은 문제 를 해결하기 위해서는, Lock은 L이 작업을 다 끝내고 나면 놓을 수 있기 때문에, H 가 최대한 빨리 다시 실행할 수 있도록 앞의 L이 작업을 우선해서 끝낼 수 있도록 우선순위를 donate 해서 높여주면 된다.
위의 그림이 위의 문제상황을 inversion으로 해결하는 것을 보여준다.
핀토스 document 에서는 priority donation이 일어날 수 있는 모든 상황을 고려해야 한다고 말하며, 두 가지를 말한다.
Multiple donation
표현 그대로 여러번 Donation이 발생하는 상황을 뜻한다. 하나의 Thread 가 여러개의 공유 데이터를 동시에 사용해서 여러개의 Lock을 쥐고 있는 상황이다.
아래의 그림에서 보면 처음에 31의 Priority 값을 가지고 있는 L이 동시에 공유 데이터 A, B를 쓰고 있기에 Lock을 쥐고 있다.
이때, 더높은 우선순위를 가지고 있는(32) M이 와서 Lock A 를 요청한다. starvation은 방지하기 위해서 자신의 Priority를 donation 하고 리스트에 들어간다.
이후에 다시 더 더 높은 우선순위를 가지고 있는 H가 도착해 Lock B를 요청한다. 이러면, 다시 새롭게 우선순위를 donation 해준다. 이 과정은 의 sinlge Lock 경우와 마찬가지로, L보다 높은 우선순위가 왔을 때, CPU가 선점되어서 waiters list에 기다리고 있는 H와 M이 starvation이 일어나지 않도록 donation을 하고 있다.
아래의 그림이 이 과정을 한 장으로 요약한 사진이다.
아래의 그림은 세개의 Lock을 가지고 있는 새로운 경우를 보여주고 있다. 이 상태에서 만일 하나의 Lock을 release 하면 어떻게 일어나는지 다음의 그림부터 보도록 하자.
아래의 그림은 Thread T1이 세 개의 Lock을 쥐고 있다가(세 개의 자원을 동시에 쓰고 있다가) Lock C를 다 써서 다른 Lock보다 먼저 놔준 상황에 waiters list를 검은색 박스로 그려놓은 것이다.
각각의 A/B/C Lock은 각자 Lock의 정보에 다음에 쓰고 싶어하는 Thread list인 waiters 리스트를 가지고 있고. C가 방금 release 되어서 Lock C의 waiters list에 있는 녀석들 중에서 가장 앞에 있는 녀석이 쓸 수 있는 상태가 되었다.
Lock C의 waiters 의 제일 앞에 있는 녀석은 원래 가장 높은 우선순위를 가지고 있고, Release 를 했을때 다시 T1의 우선순위를 최신화해주지 않으면, T4는 C를 쓸 수 있는 상태이고 가장 처음의 T1의 우선순위, T2, T3의 우선순위보다 높은 우선순위를 가지고 있는데도 T1이 모든 작업을 다 끝내고 난 뒤에야 실행될 수 있다. 만일 T1 이 끝나기를 기다리고 있는데 또 새로운 Ready_list에 높은 우선순위를 가지고 있는 Thread 들이 들어오면 이 역시도 starvation이 발생할 수 있다.
그렇기 때문에, Multiple Donation 상황을 고려하기 위해서 각 Thread 마다 나에게 donation을 줄 수 있는 모든 waiter thread 들을 기록해둘 수 있는 list가 필요하고 이것이 donation list이다.
Nested Donation
이 경우는 multiple과 헷갈릴 수 있지만, 조금 다른 개념이다. 아래의 그림을 보자.
왼쪽부터 L/M/H Thread는 순서대로 우선순위를 가지고 있다. 이를 풀어서 쓰면, H는 Lock B 를 써야 하는데, Lock B를 현재 M이 쥐고 있으며, M은 동시에 Lock A를 같이 쓰고 싶은데, L이 Lock A를 쥐고 있는 경우이다.
즉, H가 실행되기 위해서는 Lock B를 받아야 하고, Lock B 를 위해서 M이 Lock A를 얻은 뒤에 쓸만큼 쓰고, Lock을 release 해야 한다.
하지만 Priority 순서대로 한다면 H만 계속 실행이 되고, L은 실행이 되지 않아서 모두가 ready_list를 순회하는 Loop에 빠질 수 있기 때문에, priority donation을 통해서 이런 문제를 해결할 수 있다. 아래의 그림에 해결 과정이 잘 정리되어 있다.
Multiple & Nested Donation 총 정리
그림을 통해서 Multiple Donation이 일어나는 경우와 Nested Donation이 일어나는 경우를 한번에 정리하였다. 10번 Thread를 기준으로 왼쪽은 nested Donation이 일어나는 경우를, 오른쪽은 Multiple Donation이 일어나는 경우이다.
3) 과제 구현
과제 구현전에 어떻게 과제를 진행해 갔는지 작성했다.
PintOS 과정은 굉장히 복잡하기 때문에 함수들을 기준으로 모듈화를 통해서 순서대로 따라가보는 것에서 해결 방법의 실마리를 찾았다. 앞으로의 PintOS 과제에서도 동일한 방법으로 하는 것이 가장 효과적이었다.
4) 코드리뷰
전체코드는 구글에 검색하면 많은 사람들이 과제를 통해 올린 잘 정리된 코드를 읽어보는 걸 추천하고 우리가 실제로 과제를 진행하며 디버깅했던 부분을 정리할 것이다.
(void) remove_with_lock()
void remove_with_lock(struct lock *lock) {
struct list_elem *e;
struct thread *cur = thread_current ();
for (e = list_begin (&cur->donation_list); e != list_end (&cur->donation_list); e = list_next (e)){
struct thread *t = list_entry (e, struct thread, d_elem);
if (t->wait_on_lock == lock)
list_remove (&t->d_elem);
}
}위의 경우 실행시 문제가 발생하는 부분이었는데, 이는 처음에 donation_list에서 list_pop_front() 함수를 사용해서 list에서 priority를 가진 d_elem을 제거했었는데(donation_list에 순서를 priority를 기준으로 정렬하여 넣었기 때문에.), 문제가 발생했다.
왜냐하면 Lock을 Release를 하는 경우는 우선순위가 낮은 lock이 먼저 release 될 수도 있고, lock 한 개에 여러개의 lock_acquire 요청이 들어오면 donation_list에 여러 d_elem이 동시에 한개의 lock에 대해서 존재할 수 있기 때문이다.
그래서 우리는 직접 인자로 받은 lock을 이용해 list를 순회하며 해당하는 d_elem을 전부 제거하였다.
(void) thread_set_priority(int new_priority)
void thread_set_priority (int new_priority) {
thread_current ()->origin_priority = new_priority;
refresh_priority();
test_max_priority();
}해당 함수에서는 origin priority를 갱신해야 했는데, 기존의 코드는 Priority 를 바로 갱신했다.
refresh_priority()를 했을때, 새로 설정한 값으로 되어야 하는지, 혹은 donation_list에서 최대값이 설정되어야 하는지 결정할 수 있기 때문에 origin_priority를 갱신해야 한다.
(void) lock_acquire(struct lock *lock)
void lock_acquire (struct lock *lock) {
ASSERT (lock != NULL);
ASSERT (!intr_context ());
ASSERT (!lock_held_by_current_thread (lock));
struct thread *curr = thread_current();
if (lock->holder)
{
list_insert_ordered(&(lock->holder->donation_list), &(curr->d_elem), cmp_sem_priority, NULL);
curr->wait_on_lock = lock;
donate_priority();
}
// sema down 해서 ready에서 cpu에 새로 넣음
sema_down (&lock->semaphore);
lock->holder = thread_current ();
curr->wait_on_lock = NULL;
}lock acquire()함수는 sema_down()을 이용해서 수행하는데, sema_down 함수를 뜯어보면, 내부에서 while 문을 통해 자동적으로 현재 해당 lock을 얻을 수 있는지 확인한다. 만일 획득 할 수 없다면, 자동으로 Thread 를 대기시키고 lock 획득할 수 있으면, sema-- 를 해준다.
sema_down() 함수의 기능을 정확히 파악하지 못해서 lock_acquire() 함수에서 sema_down()이 하는 역할을 이중으로 수행하여 버그가 발생함.
그리고 lock획득하면, Thread의 wait_on_lock 필드를 Null로 업데이트 해주어야 한다. 이 부부분을 놓치면, 이 Thread는 lock을 가지고도, lock 요청을 계속하는 것과 같기 때문에 오류가 발생한다.
이외에도 세세한 문법 실수가 존재하나, 과제를 수행하면서 발생한 문제점을 몇가지 정리했다. 이후 Project를 진행하면서도 동일하게 남길 예정이다.
아래는 작성하는데 참고한 그림의 출처이다. 함수별로 상세히 설명이 되어있으니 궁금하다면 방문을 추천한다.
(출처:https://woonys.tistory.com/entry/PintOS-Project-123-Priority-Inversion-59%EC%9D%BC%EC%B0%A8)
