우선순위 역전

개념
우선 순위가 높은 태스크가 READY상태 (실행 가능)로 바뀌었지만 더 낮은 우선순위의 태스크가 CPU를 점유하고 있어서 실행되지 못하는 상태

I. 실시간 스케줄링의 문제점 Priority Inversion(우선순위 역전) 개요
    가.  Priority Inversion 의 개념 

  • 우선 순위가 높은 태스크가 READY상태 (실행 가능)로 바뀌었지만 더 낮은 우선순위의 태스크가 CPU를 점유하고 있어서 실행되지 못하는 상태

 

    나.  Priority Inversion의 문제점

  • RTOS 환경하에서 중요한 태스크의 수행이 요구된 시간에 끝내지 못함
  • 중요한 태스크의 무한정 대기로 인한 전체 시스템의 이상현상 발생 가능함

 

    다.  Priority Inversion 의 원인

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

        1) 비선점 스케쥴링에서 낮은 우선순위의 태스크가 자원을 점유
        2) 실시간 운영체제에서의 상호배제를 위한 세마포어를 이용
        3) 공유자원의 장기 소유
        4) 자원점유후 릴리즈시 낮은 우선순위의 태스크가 자원을 점유하는 경우

 

II. 사례 기반 Priority Inversion 설명
    가.  Priority Inversion Flow
 

  • task1,2,3이 각각 high, medium, low priority를 가진다고 가정 했을 때 Priority Inversion 발생 사례

 

    나. Priority Inversion 발생 설명

순서

우선순위역전 발생 상태

1

task3이 공유자원을 액세스 위해 binary semaphore를 가지고 수행

2

Scheduler에 의해 task1이 수행

3

task1은 task3가 먼저 획득한 Semaphore를 얻으려(take)하고, task3가 그 Semaphore를 반환할 때(give)까지 Waiting 상태로 됨

4

Scheduler에 의해 task3 수행

5

Scheduler에 의해 task2가 수행

이 시점에서 task1의 priority가 task2보다 높음에도 불구하고 task2가 먼저 수행 되는 Priority Inversion 문제가 발생

6

task2의 수행이 종료 되면, task3가 재 수행

7

task3가 Semaphore 반환

8

task1 수행

 

        - task1이 가장 높은 우선순위를 가졌으나 결국 가장 나중에 수행
III. Priority Inheritance 이용한 Priority Inversion 해결 방법
    가. 우선순위 상속(Priority Inheritance)에 처리 개념도
 

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

 

    나.  우선순위 상속(Priority Inheritance)에 의한 처리 프로세스

순서

Priority Inheritance 처리 방법

1

task3이 공유자원을 액세스 위해 binary semaphore를 가지고 수행

2

Scheduler에 의해 task1이 수행

3

task1은 task3가 먼저 획득한 Semaphore를 얻으려(take)하고, task3가 그 Semaphore를 반환할 때(give), Waiting 상태로 됨

4

Scheduler에 의해 task3 수행되는데, task3의 priority를 task1이 waiting 상태인 동안, task1의 레벨로 높임(Priority Inheritance)으로써 task3의 priority가 task2보다 높기 때문에 preemption 없이 수행 

5

Task3이 Semaphore를 반환

6

Task1이 Semaphore를 얻어서 수행됨과 동시에, task3의 priority가 다시 예전의 값으로 복귀

7

Task1 수행

8

Task2 수행

 
  • 뮤텍스를 잠근 쓰레드가 절대 선점되지 않도록 해 줌
  • 쓰레드가 뮤텍스의 잠금을 풀게 되면, 쓰레드의 우선순위는 자동으로 원래의 값으로 낮아지고, 가장 높은 우선순위를 갖는 대기자가 깨어남
  • 우선순위가 상승된 상태에서 더 높은 우선순위를 가지는 쓰레드가 뮤텍스에서 블록된다면,  다시 한 번 우선순위 상승하게 됨

 

VI. Priority Ceiling 이용한 Priority Inversion 해결 방법
    가. 우선순위 올림(Priority Ceiling)의 개념도
 

  • 어떤 쓰레드가 뮤텍스를 소유하고 있는 동안은 지정된 우선순위에서 동작

 

    나. 우선순위 올림(Priority Ceiling)의 우선순위역전 해결 원리

  • 어떤 쓰레드가 priority ceiling 속성을 가지는 뮤텍스를 Lock설정 하면, 쓰레드의 우선순위는 뮤텍스의 우선순위 올림 값으로 자동으로 상승
  • 단, 쓰레드의 우선순위가 뮤텍스의 우선순위 올림 값보다 작은 경우에만 우선순위 변경됨
  • 올림 값 보다 더 높은 우선순위 가지는 쓰레드가 잠글 경우 규칙 깨짐 
  • 따라서 뮤텍스를 이미 잠근 쓰레드는 뮤텍스를 잠그려고 시도하는 다른 쓰레드 들에 의해 선점되지 않고 자신의 작업을 종료 가능

 

V.우선 순위 역전 해결 방안 비교 및 고려 사항
    가. 우선 순위 역전 해결 방안 비교

항목

Priority Inheritance

Priority Celling

특징

낮은 우선순위를 높여줌

우선순위 한정

장점

자동으로 우선순위 동적변경

우선순위 변동에 대한 부하적음

단점

세마포어이용 자료공유로 완벽한 해결방법이 못됨

우선순위 변경에 따른 오버헤드

우선순위 한정 범위 설정 힘듬

 

    나.  Priority Inversion의 회피와 활용

  • Priority Inversion의 문제를 해결하는 것은 상속이나 한정 방법으로는 한계가 있음. 따라서 실시간 OS의 응용프로그램 개발시 태스크간 우선순위를 예상하여 Priority Inversion 이 일어나지 않토록 해야함.

댓글