우선순위 역전(Priority Inversion)

I. 실시간 운영체제에서의 스케줄링 문제점, 우선순위 역전의 개요

가. 우선순위역전(Priority Inversion)의 정의 

  - 낮은 우선순위를 가진 작업에 의해 높은 우선순위를 가진 작업이 임계영역 대기 때문에 블록 되어 수행되지 않는 현상

 

  - 선점형 스케쥴링 방식에서 우선 순위가 높은 작업이 우선 순위가 낮은 작업에 실행 순서가 역전되는 현상

나. 우선순위역전의 원인

  - 스케줄링과 동기화 사이의 상호작용 결과로 발생

  - 스케줄링 규칙에서 실행되어야 하는 쓰레드와 동기화에서 실행되어야 하는 쓰레드가 서로 다른 경우, 결과적으로 두 쓰레드의 우선 순위가 역전되어 나타남

---

II. 우선순위역전 발생 시나리오

가. 우선순위 역전 발생 시나리오

- Task 1,2,3이 각각 high, medium, low priority를 가진다고 가정 시 우선순위 역전 현상 발생 사례

 

나. 우선순위 역전 발생 시나리오 단계별 활동

순서	설명
1	- task 3이 공유자원을 액세스하기 위해 바이너리 세마포어를 가지고 수행
2	- 운영체제 스케줄러에 의해 task 1 수행
3	- task 1이 task 3이 먼저 획득한 세마포어를 얻으려 하고, task 3이 그 세마포어를 반환 할 때까지 대기 상태가 된다.
4	- 스케줄러에 의해 task3 수행
5	- 스케줄러의 의해 task2 수행, 이 때 task 3의 우선순위가 task 2보다 높음에도 불구하고 task 2가 먼저 수행되는 우선순위 역전 현상이 발생
6	- task 2의 수행이 종료되면 다시 task 3 수행
7	- task 3이 세마포어를 반환
8	- task 1 수행

- task 1 이 가장 높은 우선순위를 가졌으나 결국 가장 나중에 수행, 우선순위 올림 및 상속 프로토콜을 통해 해결

---

III. 우선순위 역전 해결방법

가. 우선순위 올림 프로토콜

- 어떤 쓰레드가 세마포어를 소유하고 있는 동안은 지정된 우선순위에서 동작 - 단, 쓰레드의 우선순위가 지정된 우선순위 올림 값보다 작은 경우에만 우선순위 변경 - 세마포어를 이미 잠근 쓰레드는 다른 쓰레드들에 의해 선점되지 않고 자신의 작업을 종료 가능

나. 우선순위 상속 프로토콜

- 특정 쓰레드가 더 낮은 우선순위의 쓰레드가 소유하고 있는 임계영역에서 대기 중인 경우, 소유자의 우선 순위를 대기자의 우선순위로 증가시켜 해결
순서	설명
1	- task 3이 공유자원을 액세스하기 위해 바이너리 세마포어를 가지고 수행
2	- 운영체제 스케줄러에 의해 task 1 이 수행
3	- task 1이 task3이 먼저 획득한 세마포어를 얻으려 하고, task 3이 그 세마포어를 반환 할 때까지 대기 상태가 된다.
4	- 스케줄러에 의해 task 3이 수행되는데, task 1이 대기 상태인 동안 task 3의 우선순위를 task1의 레벨로 높임. Task3의 우선순위가 task2보다 높기 때문에 preemption 없이 수행
5	- task 3이 세마포어를 반환
6	- task 1이 세마포어를 얻어서 수행됨과 동시에, task 3의 우선순위가 다시 예전 값으로 복귀
7	- task 1
8	- task 2

- 세마포어를 획득한 쓰레드가 절대 선점되지 않도록 한다.

- 우선순위 높은 TASK가 수행될 때 하위 우선순위의 TASK가 세마포어를 선점하고 있으면 동일한 우선순위로 상속하여 선점한 TASK를 먼저 수행한다.

---

IV. 우선순위 역전 해결방법 비교