핀토스 1주차 - Priority_Scheduling Donation
Priority Scheduling
Part 1 : Threads
1주차의 과제는 총 3개인데
- Alarm Clock
- Priority Scheduling
- Advanced Scheduler
이며,
현재 진행하는 과제는 Priority Scheduling이다
그 중 Donation에 관련된 문제를 해결하는 방식이다
Donation에 대한 구현 내용은
- priority donation
- nested donation
- multiple donation
이며, 이들은 ‘priority inversion’ 상태를 해결하기 위하여 고안된 개념이다
(요약하자면, lock의 요청으로 인하여 ‘우선순위’가 높은 스레드가
오히려 늦게 실행되거나, 기아상태가 되는 상태이다)
그렇기에, priority donation 개념이 등장하는데
이는, 현재 스레드(A)가 특정한 ‘lock’을 원하는 상황인데,
해당하는 lock을 가진 스레드(B)의 우선순위가 A보다 낮다면,
B의 우선순위를 일시적으로 A까지 올려주도록 한다
(이후, lock_release 등이 호출되면 B는 원래의 우선순위대로 돌아가고,
A가 필요한 락을 가지고 먼저 수행된다)
nested는 ‘lock A’가 필요한 쓰레드(t1)가
해당 락을 가진 쓰레드(t2)의 우선순위를 올려주려 갔는데
t2는 ‘lock B’를 필요로 하며, 그 락은 t3가 가지고 있는 상황이다
이 경우, t1의 우선순위가 높은 경우,
t1의 우선순위를 t2와 t3에도 부여한다
(t3가 락 B를 해제하고, t2가 락 A를 해제하고
이후 t1이 먼저 쓰레드를 종료하게 된다)
multiple도 상황은 비슷하다
다만 이 경우는
t1이 lock A, lock B를 모두 가지고 있는 경우
lock A를 t2가, lock B를 t3가 원하는 경우
t1은 둘 중 높은 priority를 donation 받는다
구현시 깜빡한 점
- 별도의 listelem을 사용하는 경우, list_entry() 의 3번째 인자는 해당 변수의 이름으로 해야한다
- lock을 해제할 때, 먼저 ‘대기리스트’에서 ‘해당 락’을 요구하는
요소들을 제거한다 - set_priority로 ‘초기화할 priority’를 수정해야 한다
- NULL 체크는 좋으나, break를 할 위치를 잘 못 잡으면 들어오는것 조차 못한다
- lock이 필요한 경우는 결국 해당 lock 구조체의 wait 에서 기다리게 된다
- cond 에 집어넣는 세마포어는 사실상 mutex에 가깝다
(1개 요소의 삽입 후,추가적인 요소를 집어넣지 않으며, signal을 기다림)
다음 구현할 요소는 MLFQS 일 것 같다
댓글남기기