Pintos Project 1 Threads. Priority Donation

우선순위를 스케쥴링을 할 때, 현재 실행중인 얻고자 하는 lock을 소유하고 있는 스레드가 나보다 우선순위가 낮다면 lock을 절대 얻지 못하는 문제가 발생한다.

이를 해결하기 위한 방법으로 제시하는 것이 priority donation이다. lock을 소유하고자 하는 스레드에서 lock을 소유하고 있는 스레드의 우선순위를 자신만큼 올려주는 것이다. 이를 priority donation이라고 부른다.

다행히도 테스트에서 요구하는 것은 lock에 대해서만 이를 구현해주는 것이다.

이제 donation은 lock에 대해서만 일어난다고 가정하고 진행하자.

일단, donation이 일어날 조건은 현재 실행중인 스레드가 소유하고자 하는 lock이 다른 스레드에 의해서 점유되어 있고 그 스레드는 실행되고 있지 않은 BLOCKED 혹은 READY 상태이다. 그리고 lock을 점유하고 있는 스레드의 우선순위는 현재 실행중인 스레드의 우선순위보다 낮다.

이 경우에 한해서 실행중인 스레드가 lock을 소유하고 있는 스레드에 대하여 기부를 하게 된다. 그리고 실행중인 스레드는 기부를 끝냈으니 lock을 소유중인 스레드가 lock을 놓아주길 기다리며 잠에 든다.

이 과정은 lock을 얻고자 하는 상황에서만 발생하기 때문에 synch.c:lock_acquire 함수에서 처리해주면 된다.

그럼 기부를 받은 입장에서 lock을 다 사용하고 반납할 때 어떤 식으로 행동해야 할까? 난 기부를 받았기 때문에 현재 가지고 있는 우선순위는 내가 원래 갖고 있던 우선순위가 아니다.

따라서, lock을 반납하면서 내 원래 우선순위로 돌아가야 한다. 그리고 내 우선순위가 변경되었으니 다른 스레드에 의해서 선점될 수 있다. 특히, 나에게 기부를 했던 스레드는 나보다 우선순위가 높았을 것이기 때문에 바로 CPU를 양보해줄 필요가 있을 것이다.

여기까지가 기본적인 donation 과정이 되겠다. 이제 조금은 tricky한 경우들을 생각해보자.

donation이 발생할 때, 기부를 받은 스레드 또한 다른 lock을 기다리는 중이었다면? 제일 처음에 lock을 소유하고 있던 스레드를 A, A에게 기부를 한 스레드를 B, B에게 기부를 한 스레드를 C라고 하자.

기본적으로 기부가 발생하려면 lock의 소유 스레드가 실행중인 스레드보다 우선순위가 높아야 했다.

따라서, 원래 우선순위는 A<B<C 였을 것이다. B가 A에게 기부를 했으므로 A=B<C인 상황이 되었다.

이 상황에서 A<B=C가 되면 A는 다시 실행될 수 없어진다. 따라서, C가 B에게 기부를 할 때 A=B=C로 만들도록 해야 한다.

모든 스레드는 하나의 스레드에만 직접적으로 기부를 한다. 위 상황에서는 B->A, C->B가 될 것이다.

그러면 어떤 스레드가 기부를 한 상태라면 내가 기부한 lock을 저장해두면 나보다 큰 우선순위를 가진 스레드가 나한테 기부했을 때, 이 저장해둔 lock을 전부 타고 넘어가면서 기부를 전파할 수 있다.

이러한 경우를 nested donation 이라고 부른다.

기부를 받은 스레드가 lock을 반납하려 할 때, 자신의 원래 우선순위로 변경해야 하는데 만약 lock을 여러개 들고 있어서 다른 스레드에게도 기부를 받았다면 어떻게 될까?

다시 또 lock을 들고 있는 스레드가 실행되지 않는 상황이 발생한다. 이를 해결하기 위해서 lock을 반납할 때, 다른 lock을 들고 있다면 원래 우선순위가 아닌 해당 lock에 기부를 한 스레드들 중에서 가장 높은 우선순위로 변경되어야 한다.

이런 경우를 multiple donation이라고 부른다.

priority donation에서 처리해야하는 경우는 제일 기본적인 경우와 위에서 말한 nested donation, multiple donation이 있다.

그리고 이를 위해서는 추가적인 정보를 스레드별로 저장해야 하는데, 첫째는 본인의 원래 우선순위, 둘째는 본인이 기부를 한 lock, 셋째는 본인이 들고 있는 lock들의 정보이다.

이것들을 thread의 구조체에 추가적으로 선언해주자. 그리고 lock도 list에 들어가야 되니 lock의 구조체에도 이를 위한 list_elem을 넣어줘야 한다.

이제 lock을 소유하고자 할 때 쓰는 lock_acquire, lock을 반납할 때 쓰는 lock_release에서 위에서 설명한 과정들을 구현해주자.

donate_priority를 살펴보면 ready_flag가 있는데 기부를 받을 스레드가 ready_list안에 존재할 수도 있다. 그래서 이런 스레드가 기부를 받았을 때는 ready_list를 다시 정렬하도록 했다. 그런데 이 코드가 없어도 테스트는 전부 통과하더라...

여기서 눈치챌 수도 있지만 semaphore의 waiters에서 기다리고 있는 스레드들의 우선순위 또한 변화될 수 있다. 따라서, sema_up 함수 내에서 우선순위가 높은 스레드를 뽑아올 때 뽑기 전에 정렬을 해줘야 한다.

다음은 lock_release다.

update_priority에서는 cur이 갖고 있는 lock들의 waiters를 살펴보면서 그 중에서 가장 높은 우선순위가 본인의 원래 우선순위보다 높다면 여전히 그 우선순위로 변경을 해줍니다. 만약 그런 경우가 아니라면 본인의 원래 우선순위로 변경합니다.

여기기까지가 priority donation과 관련해서 synch.c를 수정해줘야할 부분이고, thread의 구조체에 추가 변수를 넣었으니 스레드 초기화 함수랑 우선순위 관련해서 추가 변수를 넣었으니까 thread_set_priority도 적절하게 수정해야 합니다.

이와 관련된 구현 코드는 여기에서 확인하실 수 있습니다. 

이것까지 구현을 한다면 mlfqs 관련 테스트를 제외하고는 전부 통과하게 됩니다. 다음 글에서는 mlfqs 관련 테스트도 통과시켜봅시다.