
🖐️Priority Scheduling ( 정리 )
PintOS에서 우선순위 스케쥴링 방식을 구현해 보자!
Alarm Clock을 구현하면서 PintOS가 어렵지 않다고 생각했는데 이번 과제를 구현하면서 생각이 많이 달라졌다. Local 환경도 아니고 Docker에서 PintOS를 구현하기 때문에 디버깅이 쉽지 않은 것은 물론이고 이슈 찾기가 무척 어렵다. 무엇보다 과제의 난이도가 올라갔다..
그래서 우선순위 스케쥴링(Priority Scheduling)은 구현 방법을 소개하기 앞서 과제에 대한 정리를 하고 들어가고자 한다.
☑️ 과제의 최종 목표
FIFO 방식의 스케쥴링을 우선순위 스케쥴링으로 변경하기!"

이번 과제는 달성하기 위해서 Alarm Clock에 비해서 복잡한 구현을 진행해야 한다. 조금 더 쉽게 해결하기 위해서 과제를 3가지 단계로 분할해서 접근해야 한다.
일단 이번 과제가 무엇인지부터 이해해 보자.
☑️ 과제 사양

- 실행할 스레드를 선택하는 방법은 ready list에서 가장 높은 우선순위를 보유하고 있어야 한다.
- 선점
- 새로운 스레드를 ready list에 삽입할 때, 실행 중인 스레드와 우선순위를 비교해라.
- 새롭게 삽입된 스레드가 현재 실행 중인 스레드보다 우선순위가 높다면 스케쥴링.
- Lock : Semaphore, condition variable
- 잠금을 기다리는 waiters 목록에서 선택할 때, 우선순위가 가장 높은 것을 선택하게 해라.
결과적으로 목표는 선점형 스케쥴링 방식을 만드는 것이다. 그리고 부가적으로 발생하는 문제들을 해결하는 것이 이번 과제의 메인 목표다.
☑️ 어떤 문제가 발생하는가? - 우선순위 역전(Priority Inversion)

이번 과제의 핵심은 우선순위 역전을 해결하는 것이다. 우선순위 역전이 무엇인지 보자.
- 스레드 H, M, L이 있다.
- 스레드 우선순위는 L < M < H 순으로 높다.
- 스레드 L이 Lock 1을 가지고 있다.
- 스레드 H이 작업을 하기 위해서 Lock 1이 필요한 상황이다.
- 하지만 스레드 L이 Lock 1을 가지고 있기 때문에 접근할 수 없다.
- 스레드 H는 스레드 L에게 CPU 사용 권한을 넘기고 BLOCK 처리된다.
- 이때, 스레드 M은 Lock 1과 무관한 작업을 실행한다.
- 스레드 L은 스레드 M 보다 우선순위가 낮으므로, 스레드 M이 우선 실행된다.
위 상황에서 문제는 우선순위 스케쥴링임에도 스레드 H가 우선실행되지 못했다. 이러한 상황을 우선순위 역전 상황이라고 한다.
☑️ 어떻게 해결하나? - 우선순위 기부(Priority Donation)

- 스레드 L이 보유한 Lock 1을 얻기 위해서 스레드 H는 자신의 우선순위를 스레드 L에게 빌려준다.
- 일시적으로 스레드 L은 스레드 H와 동일한 우선순위로 변경된다.
- 이후 작업이 종료되고 Lock 1을 반환하게 된다면, 다시 본래의 우선순위로 돌아간다.
- 스레드 M이 실행되어도 스레드 L은 일시적으로 높은 우선순위를 가지고 있기 때문에 스레드 M의 실행은 지연된다.
위와 같은 프로세스로 일시적으로 의존성이 필요한 낮은 우선순위의 스레드에게 높은 우선순위의 스레드가 우선순위를 빌려주는 것을 우선순위 기부라고 한다.
우선순위 기부는 총 3가지의 Case를 해결해야 한다.
⭐ 단일 우선순위 기부

- T1은 Lock을 보유하고 있고 T2, T3, T4는 T1이 보유한 Lock을 필요로 하는 대기 목록이다. 이때, 가장 높은 우선순위를 T1에게 기부한다.
⭐ 중첩 우선순위 기부

- T1은 Lock A를 가지고 있다.
- T2는 Lock B를 가지고 있다.
- T3는 Lock C를 가지고 있다.
- 위 상황에서는 T1의 우선순위가 가장 높고 T2의 우선순위가 다음으로 높기 때문에 우선순위 기부가 일어나지 않는다.
- T1보다 더 높은 우선순위를 가진 T4가 Lock C를 필요로 하고 있을 때, 우선순위 기부는 중첩해서 일어나야 한다.
- T4는 Lock C가 필요한데, T3는 Lock B가 필요하다.
- Lock B는 T2가 보유하고 있고 T2 역시 Lock A를 필요로 한다.
- 우선순위 스케쥴링이 정상적으로 작동하기 위해서는 T1까지 우선순위를 높이고 Lock을 순차적으로 받아야 한다.
⭐ 복수 우선순위 기부

- Lock A, B, C가 모두 T1에게 있다고 보자.
- Lock A는 T2가 필요로 하고 있다.
- Lock B는 T3가 필요로 하고 있다.
- Lock C는 T4가 필요로 하고 있다.
- 이 중에서 T4의 우선순위가 가장 높으므로, T1은 T4에게 우선순위를 기부받는다.
- T1이 Lock C를 반환하면, T1은 본래의 우선순위로 돌아가는 것이 아니라, 대기하고 있는 T2와 T3 중에서 가장 높은 우선순위를 할당받아야 한다.
- 기다리고 있는 스레드가 본인보다 우선순위가 낮다면, 본래의 우선순위를 가지게 된다.
☑️ 구현을 위한 3가지 단계
앞서 말했듯이 우선순위 스케쥴링을 간단하게 구현하기 위해서 다음과 같이 3가지의 Case로 나눌 수 있다.
- ready_list를 우선순위 기준으로 정렬
- 기본 동기화의 waiters 목록을 우선순위 기준으로 정렬
- Priority Inversion 문제 해결

이번 과제를 종료하면 최종적으로 위와 같은 TC를 통과할 수 있다.
'활동 > 크래프톤 정글' 카테고리의 다른 글
[크래프톤 정글/Week 09] 키워드 정리 (2) | 2024.11.12 |
---|---|
[크래프톤 정글/Week 08/PintOS] Priority Scheduling ( 높은 우선순위 먼저 실행하기 ) (0) | 2024.11.08 |
[크래프톤 정글/Week 08] 키워드 정리 (3) | 2024.11.05 |
[크래프톤 정글/Week 08/PintOS] Alarm Clock ( Busy-Waiting을 Sleep/Wakeup으로 바꿔보자 ) (8) | 2024.11.04 |
[크래프톤 정글/Week 07] 키워드 정리 (1) | 2024.10.29 |