우선순위 역전 현상

I. 실시간 스케줄링 문제, 우선순위 역전 현상의 개요

가. 우선순위 역전 현상의 정의

  • 우선순위가 높은 task가 준비 상태로 바뀌었지만 더 낮은 task가 CPU를 점유하고 있어 실행되지 못하는 현상

나. 우선순위 역전의 원인

  • 스케줄링과 동기화 사이 상호작용 결과로 발생
  • 스케줄링 규칙에서 실행되어야 하는 스레드와 동기화에서 실행되어야 하는 스레드가 서로 다른 경우, 우선 순위 역전 발생

 

II. 우선순위 역전 상황 시나리오 설명

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

  • task1이 가장 높은 우선순위를 가졌지만 결국 가장 나중에 완료

나. 우선순위 역전 현상 시나리오 상세내용

순서우선순위 역전 발생 상태
1task3이 공유자원 접근 위해 바이너리 세마포어 획득
2스케줄러에 의해 task1이 수행 (문맥 교환)
3task1은 task3이 획득한 세마포어를 얻으려 하고, task3이 그 세마포어를 반환할 때까지 waiting 상태
4스케줄러에 의해 task3이 수행
5스케줄러에 의해 task2 수행. 이 때, task1의 우선순위가 task2보다 높음에도 task2가 먼저 수행. 우선순위 역전
6task2 수행 종료 시 다시 task3이 수행
7task3 세마포어 반납
8task1 세마포어 획득 후 수행 완료

 

III. 우선순위 역전 현상 해결기법I (우선순위 상속)

가. 우선순위 상속 (Priority Inheritance Protocol) 개념도

  • 특정 스레드가 더 낮은 우선순위의 스레드가 소유하고 있는 임계 영역에서 대기 중인 경우, 소유 우선순위를 대기자의 우선순위로 증가시켜 해결

나. 우선순위 상속 시나리오 상세 내용

순서우선순위 역전 발생 상태
1task3이 공유자원 접근 위해 바이너리 세마포어 획득
2스케줄러에 의해 task1이 수행 (문맥 교환)
3task1은 task3이 획득한 세마포어를 얻으려 하고, task3이 그 세마포어를 반환할 때까지 waiting 상태
4task1이 세마포어 획득을 위한 waiting 시 task3의 우선순위를 task1의 레벨로 높임. task3의 우선순위가 task2보다 높기 때문에 preemption(선점) 없이 수행
5task3이 세마포어를 반납
6task1이 세마포어 획득 후 수행과 동시에 task3의 우선순위는 다시 예전 레벨로 복귀
7task1 수행 완료
8task2 수행 완료
  • 세마포어를 획득한 스레드가 다른 스레드에 의해 선점되지 않도록 함

 

IV. 우선순위 역전 현상 해결기법II (우선순위 올림)

가. 우선순위 올림 (Priority Ceiling Protocol)의 개념도

  • 스레드가 세마포어(뮤텍스) 소유 동안 지정된 우선순위로 올림

나. 우선순위 올림 기법

올림 기법세부 내용
우선순위스레드가 세마포어(뮤텍스)를 소유하는 동안 지정된 우선순위로 올림
올림값 보다
작은 경우
지정된 우선순위 올림값보다 작은 경우에만 우선순위 변경
종료까지
스레드 수행
세마포어(뮤텍스)를 이미 잠근 스레드는 다른 스레드에 의해 선점되지 않고 자신의 작업 종료 가능

 

10 Comments

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^