우선순위 역전 Priority Inversion
- 간단히 말하면, 어쩌다 보니 우선순위 가장 높은 프로세스가 가장 늦게 완료되는 상황을 말한다.
- 임계구역 / 공유자원에 대한 접근을 제어하다가 이러한 문제가 발생할 수 있다.
예시) 우선순위 역전이 일어나는 상황
- task3이 공유 자원 접근 위해 바이너리 세마포어 (binary semaphore) 획득
- 스케줄러에 의해 task1이 수행됨
- task1은 task3이 갖고 있는 세마포어를 획득하기 위해 기다림 (waiting)
- 스케줄러에 의해 task3이 다시 실행됨
- 이 때 세마포어와 관련 없는 task2가 task3보다 우선순위가 높아 스케줄러에 의해 실행됨.
- 그러면서 task3의 완료가 뒤로 밀리며, 우선순위가 가장 높은 task1이 결국 가장 늦게 수행됨 (우선순위 역전)
해결책
우선순위 상속 기법 Priority Inheritance Protocol
방법
task1이 task3이 갖고 있는 세마포어를 획득하기 위해 waiting한다면, task3의 우선순위를 task1만큼으로 임시적으로 높여주면 된다.
이렇게 하면, task2에 의해 선점되지 않고 우선순위 역전 없이 각 작업이 완료된다.
장점
- 구현이 간단하다 → 많이 사용 된다.
단점
- 공유 자원이 여러 개 있는 상황에서 순환 대기가 일어난다면 데드락이 발생할 수 있다.
- 예시 상황)
- task2이 S1 (세마포어1) 을 획득한 후 임계 영역을 실행하던 중 task1이 실행되고, task1이 실행 중에 S2 (세마포어2) 를 요청하고 획득한 후, S1을 요청하게 되면 task2를 기다리게 됨.
- 그래서 다시 task2가 실행되는데, task2도 S2를 요청하게 되면 순환 대기가 발생.
- 상호 배제, 점유 및 대기, 순환 대기, 비선점이 모두 일어나므로 자연스레 데드락(deadlock)!
- 예시 상황)
우선순위 상한 기법 Priority Ceiling Protocol
스레드가 세마포어(뮤텍스) 소유하는 동안 지정된 우선순위로 올림
방법
- 지정된 우선순위로 변경
(단, 당연히 지정된 우선순위보다 작은 경우에만 더해주면 된다) - 스레드가 세마포어/뮤텍스를 소유하는 동안 지정된 우선순위로 변경한다.
- 세마포어/뮤텍스를 잠근 스레드는 다른 스레드에 의해 선점되지 않고 종료까지 수행된다.
특징
- 모든 프로세스의 우선순위와 각 프로세스가 요구하는 공유자원을 미리 알고 있다는 가정 하에 가능하다
- 즉, 구현이 복잡하므로 결국 잘 안 쓰이고, 기존 버전인 계승 프로토콜이 주로 쓰인다.