Pintos Project 1-3. Priority Scheduling w/ Priority Donation

군대는 거꾸로 돌아가지 않지만 OS 스케줄링은 잘못 짜면 거꾸로 돌아갑니다. Credit: https://www.hankyung.com/article/2022021177567

인트로

우선순위 스케줄링에서 중요한 또 다른 개념은 우선순위 역전(inversion)/기부(donation)입니다. 낮은 우선순위 스레드가 높은 우선순위 스레드가 필요로 하는 뮤텍스를 획득하고 오랫동안 놓지 않으면, 높은 우선순위 스레드는 계속 기다려야 하는 우선순위 역전 문제가 발생합니다.

이를 해결하기 위해 우선순위 상속 메커니즘이 사용될 수 있습니다. 뮤텍스를 획득한 낮은 우선순위 스레드는 그 뮤텍스를 기다리는 가장 높은 우선순위 스레드의 우선순위를 일시적으로 상속받아 실행됩니다. 뮤텍스를 해제하면 원래의 우선순위로 돌아갑니다.

들어가기에 앞서 mutex와 semaphore, condition variable에 대한 포스트를 읽고 와주시기를 권해 드립니다.

---

우선순위 역전

아래와 같은 상황을 가정합시다.

Credit: https://oslab.kaist.ac.kr/pintosslides/

싱글코어 환경의 기본적인 우선순위 스케줄링 정책을 적용하는 OS에서 스레드 H, M, L이라는 3개의 스레드가 있다고 가정합니다. 각각 높은, 중간, 낮은 우선순위를 가지고 있습니다. 스레드 H와 L은 둘 다 A라는 공유 자원을 써야 합니다 (M은 해당 자원과는 무관).

1. 먼저 L이 ready list에 들어왔습니다. 공유 자원 A를 잠그고 실행됩니다.
2. 이후 H가 ready list에 들어왔습니다. 안타깝게도 공유 자원 A는 이미 잠겨 있으므로, H는 block된 상태가 됩니다.
3. 그 다음 M이 ready list에 들어왔습니다. OS 스케줄러는 그 즉시 우선순위에 따라 CPU 제어권을 M에게 넘깁니다.
4. L은 미처 작업을 완료하지 못한 채 공유 자원 A를 잠가놓은 상태가 됩니다.
5. H는 필요한 공유 자원을 계속 얻지 못하므로 실행될 수 없습니다.
6. 이윽고 M의 작업이 완료됩니다. OS 스케줄러는 CPU 제어권을 공유 자원 A를 원래 점유하던 L에게 넘깁니다.
7. 이윽고 L의 작업이 완료됩니다. 
8. M과 L이 완료된 다음에서야 비로소 H의 작업이 실행됩니다.

결과적으로 우선순위가 거꾸로 돌아가버리는 모양새가 된 것입니다. 이러한 현상을 바로 우선순위 역전이라고 합니다.

---

우선순위 기부

위와 같은 상황은 어떻게 해결할 수 있을까요? 바로 스레드 H의 우선순위를 스레드 L에게 헌납하는, 말 그대로 '우선순위 기부'를 통해 해결 가능합니다. 우선순위 기부란, 뮤텍스를 획득한 낮은 우선순위 스레드는, 그 뮤텍스를 기다리는 가장 높은 우선순위 스레드의 우선순위를 임시로 상속받아 실행됩니다. 뮤텍스를 해제하면 원래의 우선순위로 돌아갑니다.

위 시나리오로 다시 설명 드리겠습니다.

1. 먼저 L이 ready list에 들어왔습니다. 공유 자원 A를 잠그고 실행됩니다.
2. 이후 H가 ready list에 들어왔습니다. 안타깝게도 공유 자원 A는 이미 잠겨 있으므로, H는 block된 상태가 됩니다.
3. 그 다음 M이 ready list에 들어왔습니다. OS 스케줄러는 그 즉시 스레드 H의 우선순위를 스레드 L에 적용시킵니다.
4. L은 공유 자원 A를 필요로 하는 스레드들 중 최우선으로 실행되어, 이윽고 완료됩니다.
5. H는 필요한 공유 자원을 획득한 뒤 실행되어, 이윽고 완료됩니다.
6. 이윽고 M의 작업이 완료됩니다.

---

다중 기부 / 중첩 기부

위 예시는 공유 자원 A 하나만 놓고 보기에 비교적 단순하지만 실제로는 여러 공유 자원이 얽히고 상속이 다단계로 이루어집니다. 이를 각각 다중 기부 (multiple donation) 및 중첩 기부 (nested donation)이라고 합니다.

아래와 같은 시나리오를 가정합니다.

스레드	우선순위	대기 자원
H	3 (높음)	lock A
M	2 (중간)	lock B
L	1 (낮음)	없음 (A와 B 모두 보유 중)

1. 스레드 L이 실행되어 먼저 lock A와 lock B를 모두 획득하고, 작업 중입니다.
2. 이때 스레드 M이 등장합니다. M은 작업을 위해 lock B가 필요합니다. 하지만 lock B는 이미 L이 보유하고 있으므로, M은 block 상태가 됩니다.
3. 이어서 스레드 H가 ready list에 들어옵니다. H는 lock A가 필요하지만, 이 또한 현재 L이 보유하고 있습니다. 그래서 H도 block 상태가 됩니다.

이제 스케줄러는 ready 상태인 스레드가 없으므로, block 상태인 스레드들이 기다리는 자원 보유자(L)에게 우선순위를 기부하게 됩니다.

• H가 L에게 우선순위 3을 기부하고 싶지만, 그 전에 L이 H에게 자원을 바로 넘겨줄 수 있는 상태가 아닙니다. 왜냐하면 L은 먼저 lock B로 인해 M에게도 대기를 발생시키고 있으므로, L이 진행되기 위해선 먼저 M이 진행되어야 합니다.
• 그런데 M 역시 block 상태이므로, 결국 H → M → L로 이어지는 기부의 연쇄가 발생합니다.

결과적으로:

• H가 M에 우선순위 3을 기부하고,
• M가 L에 우선순위 3을 기부합니다.
• 따라서 L은 임시로 우선순위 3을 부여받고, lock A와 B 모두를 빠르게 해제할 수 있게 됩니다.

---

Pintos 코드 수정 및 구현 포인트

이제 우선순위 스케줄링을 위해 Pintos의 스레드(threads/thread.c 및 thread.h) 및 동기화 (threads/synch.c 및 synch.h) 부분을 수정해야 합니다.

(작성 중)

 

 

---

테스트 결과

여기까지 구현한 뒤 테스트 결과는 아래와 같습니다. Priority scheduling의 모든 파트가 통과될 줄 알았건만... priority-condvar는 뭘까요? 왜 실패인가요? 테스트는 하나지만 다루어야 할 개념이 좀 있는 부분입니다. 이는 다음 포스트에서 다루어 보겠습니다.