Pintos Project #3 : Thread scheduling

1.     프로젝트 개요

• pintos에 priority scheduler를 구현한다. 
• 추가적으로, priority inversion을 해결하기 위해 priority inheritance 기능을 구현한다. 

---

2.    문제 분석

• 현재 pintos는 RR방식의 scheduler가 구현되어 있다. 이를 수정하여 preemptive dynamic priority scheduling을 구현한다. 
• 여기서 말하는 “preemptive하다, dynamic하다”는 의미는 thread가 run이던 도중에 자신의 priority보다 높은 priority를 가진 thread가 있다면 cpu를 반납한다는 의미이다. 
• priority scheduling의 단점은 priority inversion이 생길 수 있다는 것이다. 이를 해결하기 위해서 수업시간에 배운 priority inheritance방식을 사용한다.
• priority가 낮은 thread가 semaphore, lock을 소유하고 있는데 priority가 높은 thread가 run하던 도중 semaphore, lock의 소유를 희망할 때, priority가 낮은 thread의 priority를 priority가 높은 thread의 priority만큼 임시로 올려주는 방식이다. 이로 인해 임시로 priority가 높아진 thread는 c.s에서의 작업을 빨리 마무리하고 원래의 priority로 돌아간다. priority가 높은 thread는 보다 빨리 c.s에 진입할 수 있다.
• priority inheritance를 구현하기 위해, thread.c의 thread_set_priority()와 thread_get_priority()함수를 수정하고, 다른 함수를 추가한다. 특히 thread_tick()함수의 “time slice에 의한 cpu의 반납” 부분의 code를 수정(삭제)한다. 공유 변수에 대한 동기화 문제를 해결하기 위해 synch.c의 함수도 수정한다.
• priority scheduling의 수정이 완벽한지를 테스트 하기 위해, [ priority-change, priority-preempt, priority-fifo, priority-sema, priority-donate-one, priority-donate-multiple, priority-donate-multiple2, priority-donate-nest, priority-donate-chain, priority- donate-sema, priority-donate-lower ] 테스트를 수행하여 결과를 따져본다.

---

3.    문제 해결 과정

• 다음은 수정한 주요 함수 또는 추가한 주요 함수에 대해 정리한 표이다. 
• 해당 함수가 소속된 c파일 명과 해당 함수의 code, 그리고 그 code에 대한 설명 순으로 작성했다. 

---

1  ) thread_set_priority

경로 및 함수 명	threads/thread.c/thread_set_priority()
설 명	run이던 thread의 priority의 변경을 위해 실행되는 함수이다. 기존에 있던 함수로써 약간의 변형을 하였다.  현재 thread의 priority를 이후의 비교 과정에서 사용하기 위해 old_priority로 한다. 현재 thread의 priority를 함수 선언시 변수로 받은 new_priority로 변경한다.  첫 번째의 if문을 보면, priority inversion이 발생할 수 있는 조건이라면, priority_donate()함수를 호출하여 해결한다. 두 번째의 if문을 보면, 과거의 priority가 더 큰 경우에 priority_max()함수를 호출하여 현재 thread의 상태를 결정한다. (아래의 표 참고)

---

2  ) thread_get_priority

경로 및 함수 명	threads/thread.c/thread_get_priority()
설 명	thread의 priority 값을 return하는 함수이다. 기존에 있던 함수로써 약간의 변형을 하였다.  thread의 priority 값이 담겨진 tmp를 return한다.

---

3  ) priority_donate

경로 및 함수 명

threads/thread.c/priority_donate()

설 명

lock을 소유하고 있는 현재의 thread보다 priority가 높은 thread가 lock의 소유를 희망할 때 실행되는 함수이다. priority inversion의 발생 시 이 함수를 통해 해결한다.  priority inheritance 구현 시 deadlock 상태로 빠질 위험이 있기 때문에 이를 제한하기 위해 DEPTH_LIMIT이라는 제한선을 두고 depth와 비교한다.  만약 제한선보다 큰 값을 가진다면 이 함수는 정상작동되지 않는다.  두 가지의 if문을 이용하여 현재 thread의 inversion 여부를 결정한다.  두 번째 if문은 lock을 소유하고 있는 thread의 priority와 현재 thread의 priority를 비교하는 구문이다.  마지막 부분이 함수의 실질적인 과정을 수행한다. lock을 소유한 thread의 priority를 현재 thread의 priority로 대체한다.  현재 thread가 lock의 소유를 기다리고 있다면, wait_on_lock을 할당한다.

---

4  ) priorty_max

경로 및 함수 명	threads/thread.c/priority_max()
설 명	thread를 ready list에 추가하기 전에, 현재 run하는 thread의 priority와 비교하여 thread의 상태를 조정하는 함수이다. if문을 보면, 현재 thread보다 더 큰 priority를 가지고 있을 경우 run인 thread로부터 cpu를 빼앗는다. intr_yield_on_return()의 호출이 바로 이 이유이다.

---

5  ) priority_compare

경로 및 함수 명	threads/thread.c/priority_compare()
설 명	두 개의 thread의 priority를 비교하는 함수이다. priority가 높다면 true를 return한다. list_insert_ordered()함수에서 호출되는 함수이고, 이를 통해 priority 순서대로 list내에 정렬하게 된다.  이 함수는 list의 정렬이 필요하다면 꼭 호출되는 함수이다.  이 함수를 호출하므로써, list의 맨 앞 요소만 비교하면 되므로 효율성이 올라간다.

---

6  ) priority_remove

경로 및 함수 명	threads/thread.c/priority_remove()
설 명	lock의 release를 위해 donation_list에서 thread를 제거하는 함수이다. donation_list는 lock의 소유를 기다리고 있는 thread들이 대기하는 list이다.  반복문을 통해 lock을 기다리고 있는 thread가 lock을 소유했다면 list에서 제외시킨다.

---

7  ) priority_change

경로 및 함수 명	threads/thread.c/priority_change()
설 명	lock의 소유를 대기하고 있는 list인 donation_list에서 priority가 가장 높은 thread를 가져오는 함수이다. donation_list도 이미 priority에 대해 정렬이 되어있으므로, 맨 앞 요소를 가져온다. priority_init보다 더 큰 값이라면 해당 priority를 priority_init으로 한다.

---

8  ) sema_down

경로 및 함수 명	threads/synch.c/sema_down()
설 명	semaphore를 낮추어 다른 thread의 수행을 막는 함수이다.  기존의 sema_down()함수를 일부 수정하였다. while문은 semaphore에 대한 critical section의 접근을 제어하기 위한 반복문이다.   semaphore에 대한 동기화 문제를 해결하기 위해 priority_donate()함수를 호출한다. list내의 thread의 priority순으로 정렬한다. 완료 후 sema의 value를 낮춰준다.

---

9  ) lock_acquire

경로 및 함수 명	threads/synch.c/lock_acquire()
설 명	기존의 lock_acquire()함수를 일부 수정하였다.  if문을 보면, lock의 holder가 존재한다면 현재 thread의 wait_on_lock을 lock으로 설정한다.  이후 list 정렬 함수를 통해 thread를 donation_list에 추가한다.  최종적으로 sema_down()함수를 호출한 후 현재 thread의 wait_on_lock을 NULL로 한다.  변경 전과 비교했을 때 결과적으로  lock을 소유할 때 donation이 수행되도록 변경된다.

---

10  ) lock_release

경로 및 함수 명	threads/synch.c/lock_release()
설 명	lock_release()함수를 호출하면서 받은 lock을 priority_remove()함수를 통해 thread로부터 lock을 relaeas(해제)한다.  해당 lock의 holder가 없어졌으므로, sema_up()함수를 통해 semaphore를 up해준다.

---

11  ) cond_wait

경로 및 함수 명	threads/synch.c/cond_wait()
설 명	기존의 cond_wait()함수를 일부 수정하였다. lock의 기능을 위한 함수이다. sema_init()을 통해, semaphore를 초기화하고 0을 대입한다. priority에 따라서 list에 thread를 연결한다.

---

4.   테스트

• priority scheduling과 관련된 다양한 테스트를 수행함으로써, 수정이 잘 되었는지를 따져본다. 
• 다음은 수행한 테스트 이름, 테스트의 목적, 테스트 결과에 대한 캡쳐화면을 표로 나타낸 것이다. 
• 수행한 테스트에 대한 결과가 모두 pass임을 통해 priority scheduling이 완료됨을 알 수 있다. 

---

테스트 명	priority-change
목적	thread_set_priority()의 기능이 잘 되는지 테스트

---

테스트 명	priority-preempt
목적	priority 값에 따른 preempt가 제대로 이루어지는지 테스트

---

테스트 명	priority-fifo
목적	priority가 동일한 thread간의 scheduling이 잘 되는지 테스트

---

테스트 명	priority-sema
목적	waiting queue에서도 priority가 적용되는지 테스트

---

테스트 명	priority-donate-one
목적	기본적인 priority inheritance 테스트

---

테스트 명	priority-donate-multiple
목적	복수 개의 lock에 대한 priority inheritance 테스트

---

테스트 명	priority-donate-multiple2
목적	복수 개의 lock에 대한 priority inheritance 또 다른 테스트

---

테스트 명	priority-donate-nest
목적	priority inheritance이 중첩되어 있는 경우의 테스트

---

테스트 명	priority-donate-chain
목적	여러 thread간의 priority inheritance이 연결되어 발생하는 경우의 테스트

---

테스트 명	priority-donate-sema
목적	priority inheritance이 semaphore와도 동작하는지 테스트 (lock의 경우 포함)

---

테스트 명	priority-donate-lower
목적	priority inheritance의 도중에 priority의 낮춤을 할 수 없는지 테스트