우선 순위 뒤집기
Priority inversion | 이 기사는 대체로 또는 전적으로 단일 출처에 의존한다.– · ·· · (2010년 9월) |
컴퓨터 과학에서 우선순위 역전은 높은 우선순위 작업이 간접적으로 낮은 우선순위 작업으로 대체되어 할당된 우선순위를 효과적으로 뒤집는 스케줄링의 시나리오다.이는 높은 우선순위 태스크가 높은 우선순위 태스크에 의해서만 실행되지 못하도록 할 수 있는 우선순위 모델을 위반하는 것이다.우선 순위가 낮은 태스크로 리소스 경합이 발생하여 중간 우선 순위 태스크가 선점할 때 역전이 발생한다.
예
공유 리소스 을(를) 독점적으로 사용할 수 있는 높은 우선 와 낮은 우선 순위의 가지 H {\ L을를) 고려하십시오 이(가 획득한 후 을(를) 획득하려고 하면, 이(가) 리소스를 포기할 때까지 H 이(가) 차단됨잘 설계된 시스템에서 전용 리소스( 경우 R R를 공유하면 일반적으로 이(가) 한 시간 동안 차단되지 않도록 R 을(를) 즉시 포기해야 한다.좋은 디자인에도 불구하고 그러나, 중간 정도의 3분의 1과제 M{M\displaystyle}우선 순위(나는 p()<>안(M)<>, p()){\displaystyle p())}과제()){\displaystyle())}을 위한 우선 순위를 나타내는 안(H){\displaystyle p(L)<, p(M)<, p(H)},)나는 동안{\displaystyle 사냥하기 적합한이 가능하다 L.}의 사용 제일의 것이다f . At this point, being higher in priority than , preempts (since does not depend on ), causing to not be able to relinquish promptly, 따라서 최고 우선순위 프로세스인 을(를) 실행할 수 없게 된다(, H 은(는 M {\과 같은 낮은 우선순위 작업에 의해 간접적으로 예기치 않은 차단을 겪는다).
결과들
어떤 경우에는 우선순위 역전이 즉각적인 위해를 초래하지 않고 발생할 수 있다. 즉 높은 우선순위 작업의 지연된 실행이 눈에 띄지 않게 되고 결국 낮은 우선순위 태스크가 공유 리소스를 해제한다.그러나 우선순위 역전이 심각한 문제를 일으킬 수 있는 상황도 많다.우선 순위가 높은 작업이 자원에 의존하지 않고 방치되면 시스템 오작동이나 감시 타이머가 전체 시스템을 재설정하는 등 사전 정의된 시정 조치의 트리거로 이어질 수 있다.1997년[1][2] 화성 패스파인더 착륙선이 겪은 문제는 실시간 시스템의 우선순위 역전에 의해 야기된 문제의 전형적인 예다.
우선순위 역전은 또한 시스템의 인식된 성능을 감소시킬 수 있다.우선순위가 낮은 태스크는 일반적으로 우선순위가 낮은데, 그 이유는 태스크가 신속하게 완료되는 것이 중요하지 않기 때문이다(예를 들어, 일괄 작업이나 다른 비 상호 작용 활동일 수 있음).마찬가지로 우선순위가 높은 과제는 엄격한 시간 제약에 노출될 가능성이 높기 때문에 우선순위가 높다. 즉, 대화형 사용자에게 데이터를 제공하거나 실시간 응답 보증의 적용을 받을 수 있다.우선순위 역전이 높은 우선순위 과제를 차단하는 낮은 우선순위 작업의 실행으로 이어지기 때문에 시스템 응답성이 저하되거나 응답시간 보증을 위반하는 결과를 초래할 수 있다.
마감 교환이라고 불리는 유사한 문제는 가장 빠른 마감일 내에 첫 번째 스케줄링(EDF)에서 발생할 수 있다.
해결 방법
이 문제의 존재는 1970년대부터 알려져 왔다.램프슨과 레델은 우선 순위 뒤집기 문제를 지적하는 첫 번째 논문 중 하나를 발표했다.UNIX 커널과 같은 시스템은 이미 splx() 원시적인 문제를 해결하고 있었다.상황을 예측할 수 있는 바보 같은 방법은 없다.그러나 기존 솔루션에는 여러 가지가 있으며, 그 중 가장 일반적인 솔루션은 다음과 같다.
- 중요한 섹션을 보호하기 위해 모든 인터럽트 사용 안 함
- 우선 순위 역전을 방지하기 위해 인터럽트를 비활성화할 경우 사전 예방 가능과 인터럽트 비활성화라는 두 가지 우선순위만 있다.세 번째 우선순위가 없으면 뒤집기는 불가능하다.잠금 데이터(인터럽트 활성화 비트)가 하나만 있기 때문에 순서를 잘못 매기는 잠금이 불가능해 교착 상태가 발생할 수 없다.임계 영역은 항상 완료되기 때문에 중단은 발생하지 않는다.이는 모든 인터럽트가 비활성화된 경우에만 작동한다는 점에 유의하십시오.특정 하드웨어 장치의 인터럽트만 비활성화된 경우, 우선 순위 역전은 하드웨어의 인터럽트 우선 순위에 의해 다시 도입된다.UNIX의 초기 버전에서는 splx(0) ... splx(7)라는 이름의 일련의 원시 요소들이 주어진 우선순위를 통해 모든 인터럽트를 비활성화했다.중요 섹션에 진입한 모든 인터럽트의 최고 우선순위를 적절하게 선택함으로써, 우선 순위 역전 문제를 모든 인터럽트를 차단하지 않고 해결할 수 있었다.천장은 요율-단조적 순서로 배정되었다. 즉, 느린 장치의 우선 순위는 더 낮았다.
- 여러 CPU 시스템에서는 간단한 변화인 "단일 공유 플래그 잠금"이 사용된다.이 체계는 모든 CPU가 프로세서 간 중요 섹션을 모두 사용 중 대기 상태로 잠그는 데 사용하는 단일 플래그를 공유 메모리에 제공한다.프로세서 간 통신은 대부분의 다중 CPU 시스템에서 비용이 많이 들고 속도가 느리다.따라서 그러한 시스템은 대부분 공유자원을 최소화하도록 설계되어 있다.결과적으로, 이 계획은 실제로 많은 실제 시스템에서 잘 작동한다.이러한 방법은 단순한 임베디드 시스템에서 널리 사용되며, 신뢰성, 단순성 및 낮은 자원 사용으로 높이 평가된다.또한 이러한 계획은 중요한 부분을 매우 간략하게 유지하기 위해 영리한 프로그래밍을 필요로 한다.많은 소프트웨어 엔지니어들은 이 컴퓨터들이 범용 컴퓨터에서는 비현실적이라고 생각한다.[citation needed]
- 우선 순위 상한 프로토콜
- 우선 순위 상한 프로토콜의 경우, (운영 체제 코드를 실행하는) 공유 뮤텍스 프로세스 자체의 특성(높은) 우선 순위를 가지며, 뮤텍스를 잠그는 작업에 할당된다.뮤텍스에 액세스하려는 다른 높은 우선순위 작업이 최대 우선순위보다 높은 우선순위를 가지지 않는 한, 이 작업은 잘 작동한다.
- 우선상속
- 우선 순위 상속 정책에서는 우선 순위가 높은 태스크가 낮은 태스크로 공유되는 일부 리소스를 대기해야 할 때마다 우선 순위가 낮은 태스크는 공유 리소스를 직접 사용하는 기간 동안 일시적으로 가장 높은 대기 우선 순위 태스크의 우선 순위를 할당하므로 중간 우선 순위 태스크가 미리 비워지는 것을 방지한다.우선순위가 낮은 과제, 즉 대기 우선순위가 높은 과제에도 영향을 미친다.일단 리소스가 해제되면 우선 순위가 낮은 태스크는 원래 우선 순위 수준에서 계속된다.
- 무작위 부스팅
- 잠금 장치를 고정하는 준비 작업은 중요 섹션을 종료할 때까지 우선순위가 무작위로 증가된다.이 솔루션은 마이크로소프트 윈도우즈에서 사용된다.[4]
- 차단을 피하십시오.
- 우선순위 역전은 우선순위가 낮은 태스크가 높은 태스크를 차단하는 것을 수반하기 때문에 우선순위 역전을 피하는 한 가지 방법은 예를 들어 읽기-복사-업데이트와 같은 비차단 알고리즘을 사용하여 차단을 피하는 것이다.
참고 항목
참조
- ^ Glenn Reeves, What Really Happened on Mars, JPL Pathfinder team, retrieved 2019-01-04
- ^ Explanation of priority inversion problem experienced by Mars Pathfinder (PDF), retrieved 2019-01-04
- ^ Lampson, B; Redell, D. (June 1980). "Experience with processes and monitors in MESA". Communications of the ACM. 23 (2): 105–117. CiteSeerX 10.1.1.46.7240. doi:10.1145/358818.358824. S2CID 1594544.
- ^ MSDN의 우선 순위 반전
