2019년 3월 12일
우선순위 역전 현상
I. 실시간 스케줄링 문제, 우선순위 역전 현상의 개요
가. 우선순위 역전 현상의 정의
- 우선순위가 높은 task가 준비 상태로 바뀌었지만 더 낮은 task가 CPU를 점유하고 있어 실행되지 못하는 현상
나. 우선순위 역전의 원인
- 스케줄링과 동기화 사이 상호작용 결과로 발생
- 스케줄링 규칙에서 실행되어야 하는 스레드와 동기화에서 실행되어야 하는 스레드가 서로 다른 경우, 우선 순위 역전 발생
II. 우선순위 역전 상황 시나리오 설명
가. 우선순위 역전 발생 시나리오
 |
- task1이 가장 높은 우선순위를 가졌지만 결국 가장 나중에 완료
나. 우선순위 역전 현상 시나리오 상세내용
| 순서 | 우선순위 역전 발생 상태 |
|---|---|
| 1 | task3이 공유자원 접근 위해 바이너리 세마포어 획득 |
| 2 | 스케줄러에 의해 task1이 수행 (문맥 교환) |
| 3 | task1은 task3이 획득한 세마포어를 얻으려 하고, task3이 그 세마포어를 반환할 때까지 waiting 상태 |
| 4 | 스케줄러에 의해 task3이 수행 |
| 5 | 스케줄러에 의해 task2 수행. 이 때, task1의 우선순위가 task2보다 높음에도 task2가 먼저 수행. 우선순위 역전 |
| 6 | task2 수행 종료 시 다시 task3이 수행 |
| 7 | task3 세마포어 반납 |
| 8 | task1 세마포어 획득 후 수행 완료 |
III. 우선순위 역전 현상 해결기법I (우선순위 상속)
가. 우선순위 상속 (Priority Inheritance Protocol) 개념도
 |
- 특정 스레드가 더 낮은 우선순위의 스레드가 소유하고 있는 임계 영역에서 대기 중인 경우, 소유 우선순위를 대기자의 우선순위로 증가시켜 해결
나. 우선순위 상속 시나리오 상세 내용
| 순서 | 우선순위 역전 발생 상태 |
|---|---|
| 1 | task3이 공유자원 접근 위해 바이너리 세마포어 획득 |
| 2 | 스케줄러에 의해 task1이 수행 (문맥 교환) |
| 3 | task1은 task3이 획득한 세마포어를 얻으려 하고, task3이 그 세마포어를 반환할 때까지 waiting 상태 |
| 4 | task1이 세마포어 획득을 위한 waiting 시 task3의 우선순위를 task1의 레벨로 높임. task3의 우선순위가 task2보다 높기 때문에 preemption(선점) 없이 수행 |
| 5 | task3이 세마포어를 반납 |
| 6 | task1이 세마포어 획득 후 수행과 동시에 task3의 우선순위는 다시 예전 레벨로 복귀 |
| 7 | task1 수행 완료 |
| 8 | task2 수행 완료 |
- 세마포어를 획득한 스레드가 다른 스레드에 의해 선점되지 않도록 함
IV. 우선순위 역전 현상 해결기법II (우선순위 올림)
가. 우선순위 올림 (Priority Ceiling Protocol)의 개념도
 |
- 스레드가 세마포어(뮤텍스) 소유 동안 지정된 우선순위로 올림
나. 우선순위 올림 기법
| 올림 기법 | 세부 내용 |
|---|---|
| 우선순위 | 스레드가 세마포어(뮤텍스)를 소유하는 동안 지정된 우선순위로 올림 |
| 올림값 보다 작은 경우 | 지정된 우선순위 올림값보다 작은 경우에만 우선순위 변경 |
| 종료까지 스레드 수행 | 세마포어(뮤텍스)를 이미 잠근 스레드는 다른 스레드에 의해 선점되지 않고 자신의 작업 종료 가능 |
About The Author
도리
10 Comments
질문드립니다! 우선순위 역전 정의가 “우선순위가 높은 task가 준비 상태로 바뀌었지만 더 낮은 task가 CPU를 점유하고 있어 실행되지 못하는 현상”이면 t4시점이 역전되는 지점 아닌가요? 왜 t5부분인지 이해가 안가서 질문 남깁니다ㅠㅠ꼭 좀 답변 부탁드려요!!
우선순위 역전 발생 시나리오의 그림에서 보면, task3이 바이너리 세마포어를 획득했기 때문에 우선순위와 관계없이 task3이 바이너리 세마포어를 반납해야 task1이 바이너리 세마포어를 획득하여 실행 가능하게 됩니다. 이 상태에서 우선순위가 task3보다 높지만 task1보다 낮은 task2가 등장하여 task3의 실행을 중단시키고 task1보다 먼저 실행되는 현상이 우선순위 역전현상입니다. 따라서 우선순위역전현상 발생부분은 우선순위가 task1보다 낮은 task2가 먼저 수행되는 부분입니다.
이해하시는데 도움이 되셨으면 좋겠습니다.^^
정말 감사합니다^^*
먼저 올려주신 자료들 정말 잘 보고 있습니다.
좋은 자료 올려주신거에 먼저 고맙습니다.
질문이 있어서 이렇게 글을 남깁니다.
1. 우선순위역전의 스케줄링은 비선점형, 선점형 스케줄링 중 어떤 스케줄링인지요?
2. 선점형 스케줄링이라면 바이너리 세마포어이기 때문에
공유자원을 선점 못하는건지요?
3. 앞에 순서를 이해한 내용을 말씀 드리면
TASK3이 바이너리 세마포어를 획득 -> 이로 인해 TASK1이 WAIT상태->
TASK3이 실행중에 우선순위가 높은 TASK2가 수행을 했기 때문에
이 부분에서 우선순위 역전 현상이 일어난다라고 이해를 했습니다.
TASK2도 똑같이 바이러니 세마포어의 자원을 접근 할려면
TASK1과 똑같이 WAIT상태가 되어야 하는게 아닌가?라는 의문이 듭니다.
설명 좀 부탁 드리겠습니다.
본문의 우선순위 역전 발생 시나리오에서는 우선순위 역전 현상을 발생시키기 위해 바이너리 세마포어가 필요한 task는 task1, task3으로 임의로 정의하고, task2는 바이너리 세마포어가 불필요한 것으로 임의로 정의하였습니다.
본문의 우선순위 역전 현상 시나리오 순서 5번에서 task2는 바이너리 세마포어가 필요없으므로 세마포어 획득을 기다리는 task1보다 먼저 수행되어 종료되므로, task1 보다 낮은 우선순위의 task2가 먼저 수행되어 종료된다는 점에서 우선순위 역전이 발생되었다는 것을 의미합니다.
문의하신 부분에 대해 답변 드리자면,
1. 우선순위역전의 스케줄링은 비선점형, 선점형 스케줄링 중 어떤 스케줄링인지요?
=> 우선순위 역전 현상은 선점형 스케줄링에서 나타나는 문제입니다.
2. 선점형 스케줄링이라면 바이너리 세마포어이기 때문에 공유자원을 선점 못하는건지요?
=> 맞습니다. 바이너리 세마포어이기 때문에 우선순위가 높더라도 다른 task가 세마포어를 반환할때까지 세마포어의 공유자원을 획득하지 못합니다.
3. 앞에 순서를 이해한 내용을 말씀 드리면
TASK3이 바이너리 세마포어를 획득 -> 이로 인해 TASK1이 WAIT상태->
TASK3이 실행중에 우선순위가 높은 TASK2가 수행을 했기 때문에
이 부분에서 우선순위 역전 현상이 일어난다라고 이해를 했습니다.
=> 세마포어를 기다리는 TASK1보다 우선순위가 낮은 TASK2가 먼저 수행을 했기 때문에 우선순위 역전 현상이 일어난다라고 이해를 하시면 될 것 같습니다.
TASK2도 똑같이 바이러니 세마포어의 자원을 접근 할려면
TASK1과 똑같이 WAIT상태가 되어야 하는게 아닌가?라는 의문이 듭니다.
=> 시나리오에서 우선순위 역전 현상을 발생시키기 위해 바이너리 세마포어가 필요한 TASK는 TASK1, TASK3으로 임의로 정의하고, TASK2는 바이너리 세마포어가 불필요한 것으로 임의로 정의한 것입니다.
하나도 질문 있는데요~
어디에서는 task3,1은 공유자원 접근이고
task2는 로컬자원이기 때문에 자원측면이 아닌 우선 실행이 기준으로 봤을때
우선순위 처리 역전이라는걸로 이해를 하고 있는데
어떤 내용인지 정확히 알고 싶어서 이렇게 질문 남깁니다.
어디서 보셨는지 모르겠지만, task3,1은 공유자원 접근이므로 세마포어가 필요하고, task2는 로컬자원이기 때문에 세마포어가 불필요한 것으로 이해하시면 어떨까 합니다. 보신 내용이 정확히 어떤 내용인지 알 수가 없어서 답변이 정확하지 않을 수도 있습니다.
이해가 잘 되게 답변을 주셔서 고맙습니다.
한 가지만 더 질문 할 게 있는데요~
해결책인(상속)에서
순서 4번
task1이 세마포어 획득을 위한 waiting 시 task3의 우선순위를 task1의 레벨로 높임. task3의 우선순위가 task2보다 높기 때문에 preemption(선점) 없이 수행
=> 이말이 task3 우선순위를 task1과 같은 우선순위로 올렸기 때문에
task1이나 task3이 수행중에
이보다 낮은 우선순위의 task가 오면 선점이 안되기 때문에
“preemption(선점) 없이 수행”된다라는 뜻으로 보면 되는건지요?
네~ 맞습니다.