Priority Scheduling - gon2gon2/pintos-kaist GitHub Wiki

문제

• 새로운 스레드가 추가되었을 때, 새로운 스레드가 현재 실행중이던 스레드보다 더 높은 우선순위를 갖고 있는 경우 ready_list에 있는 스레드가 우선순위가 더 높음에도 불구하고 우선순위가 낮은 스레드를 기다려야 하는 문제가 발생한다.
• 이와 유사하게, 여러 스레드가 lock, semaphore, or condition variable을 기다리는 경우, 우선순위가 가장 높은 스레드가 깨어나 이 한정된 자원을 갖게 해야한다.
• 언제든 스레드의 우선순위가 변경된다면, 체크해서 가장 우선순위가 높은 스레드가 실행되도록 해야한다.
• Priority Inversion: H,M,L을 각각 High, Medium, Low의 우선순위를 갖는 스레드라고 하자. H가 kernel data에 읽기나 쓰기를 하려는데 L이 해당 kernel data에 대한 lock을 갖고 있는 경우 H는 L의 lock_release를 기다려야 하는데, 이때 M이 CPU를 선점하게 되면 M이 H의 스케줄링을 늦추게 된다.

해결방법 - Priority Donation

• 높은 우선순위를 가진 스레드의 우선순위를 낮은 스레드에게 기부한다.

cases

1. Priority Donation: H가 원하는 lock을 가진 L이나 M에게 H의 priority를 기부한다. L은 기부받은 우선순위로 lock에 대한 작업을 마친 다음, lock을 반환하면서 CPU를 양보한다.
2. Multiple Donation: L이 lock A와 B를 갖고(hold) 있는 상황. L은 M과 H로부터 우선순위를 여러번 기부받는다.
3. Nested Donation: H는 M이 가진 lock을, M은 L이 가진 lock을 원하는 상황. H의 우선순위는 M을 거쳐 L에게 전달된다.