[운영 체제] 우선 순위 반전이란 무엇입니까?
우선 순위 반전은 해결책이 아니라 문제입니다. 일반적인 예는 우선 순위가 높은 프로세스가 필요로하는 자원을 획득 한 다음 중간 우선 순위 프로세스에 의해 선점되는 낮은 우선 순위 프로세스로, 중간 우선 순위 프로세스가 완료되는 동안 자원에서 높은 우선 순위 프로세스가 차단됩니다 (효과적으로 낮은 우선 순위).
다소 유명한 예는 Mars Pathfinder 로버가 경험 한 문제입니다. http://www.cs.duke.edu/~carla/mars.html , 꽤 흥미로운 읽기입니다.
-------------------우선 순위가 서로 다른 세 가지 작업 (tLow, tMed 및 tHigh)을 상상해보십시오. tLow 및 tHigh는 서로 다른 시간에 동일한 중요 리소스에 액세스합니다. tMed는 자체 작업을 수행합니다.
- tLow가 실행 중이고 tMed 및 tHigh가 현재 차단됩니다 (중요 섹션에는 없음).
- tLow가 나타나서 중요 섹션으로 들어갑니다.
- tHigh는 차단을 해제하고 시스템에서 우선 순위가 가장 높은 작업이므로 실행됩니다.
- tHigh는 중요한 리소스에 들어 가려고 시도하지만 tLow가 있으면 차단합니다.
- tMed는 차단을 해제하고 이제 시스템에서 우선 순위가 가장 높은 작업이므로 실행됩니다.
tLow는 자원을 포기할 때까지 실행할 수 없습니다. tLow는 tMed가 차단되거나 종료 될 때까지 실행할 수 없습니다. 작업의 우선 순위가 반전되었습니다. tHigh는 우선 순위가 가장 높지만 실행 체인의 맨 아래에 있습니다.
우선 순위 반전을 "해결"하려면 tLow의 우선 순위가 최소한 tHigh만큼 높아야합니다. 일부는 우선 순위를 가능한 가장 높은 우선 순위 수준으로 높일 수 있습니다. tLow의 우선 순위 레벨을 높이는 것만 큼 중요한 것은 적절한 시간에 tLow의 우선 순위 레벨을 낮추는 것입니다. 시스템마다 접근 방식이 다릅니다.
tLow의 우선 순위를 떨어 뜨리는시기
- tLow가 가지고있는 자원에서 다른 작업은 차단되지 않습니다. 시간 초과 또는 리소스 해제 때문일 수 있습니다.
- tLow의 우선 순위를 높이는 데 기여하는 다른 작업은 tLow가 가진 리소스에서 차단되지 않습니다. 시간 초과 또는 리소스 해제 때문일 수 있습니다.
- 작업이 리소스를 기다리는 변경이있는 경우 해당 리소스에서 차단 된 가장 높은 우선 순위 수준 작업의 우선 순위와 일치하도록 tLow의 우선 순위를 낮 춥니 다.
방법 # 2는 tLow가 우선 순위 수준에 도달 한 시간을 단축한다는 점에서 방법 # 1보다 개선 된 것입니다. 우선 순위 레벨은이 기간 동안 tHigh의 우선 순위 레벨로 유지됩니다.
방법 # 3을 사용하면 tLow의 우선 순위 수준이 필요한 경우 한 단계 또는 전혀 단계가 아니라 단계적으로 감소 할 수 있습니다.
다른 시스템은 중요하다고 생각하는 요소에 따라 다른 방법을 구현합니다.
- 메모리 공간
- 복잡성
- 실시간 응답 성
- 개발자 지식
도움이 되었기를 바랍니다.
-------------------그것은이다 문제 보다는 솔루션입니다.
우선 순위가 낮은 스레드가 작업 중에 잠금을 획득하면 우선 순위가 높은 스레드가 완료 될 때까지 기다려야하는 상황을 설명합니다 (우선 순위가 낮기 때문에 특히 오래 걸릴 수 있음). 여기서 반전은 우선 순위가 높은 스레드가 우선 순위가 낮은 스레드가 수행 할 때까지 계속 될 수 없기 때문에 실제로는 우선 순위가 낮습니다.
일반적인 해결책은 우선 순위가 낮은 스레드가 잠금을 대기중인 모든 사람의 높은 우선 순위를 일시적으로 상속하도록하는 것입니다.
-------------------애플리케이션에 세 개의 스레드가 있다고 가정합니다.
Thread 1 has high priority.
Thread 2 has medium priority.
Thread 3 has low priority.
Thread 1과 Thread 3이 동일한 중요 섹션 코드를 공유한다고 가정 해 보겠습니다.
스레드 1과 스레드 2는 예제 시작 부분에서 휴면 중이거나 차단되었습니다. 스레드 3이 실행되고 중요 섹션에 들어갑니다.
이때 스레드 2가 우선 순위가 더 높기 때문에 스레드 2가 실행되기 시작하고 스레드 3을 선점합니다. 따라서 스레드 3은 계속해서 중요한 섹션을 소유합니다.
나중에 스레드 1이 실행되기 시작하여 스레드 2를 선점합니다. 스레드 1은 스레드 3이 소유 한 중요 섹션에 들어 가려고하지만 다른 스레드가 소유하고 있기 때문에 스레드 1이 차단하여 중요 섹션을 기다립니다.
이 시점에서 스레드 2는 스레드 3보다 우선 순위가 높고 스레드 1이 실행되고 있지 않기 때문에 실행을 시작합니다. 스레드 3은 스레드 2가 계속 실행되기 때문에 스레드 1이 대기중인 중요 섹션을 해제하지 않습니다.
따라서 시스템에서 우선 순위가 가장 높은 스레드 인 스레드 1이 우선 순위가 낮은 스레드가 실행되기를 기다리면서 차단됩니다.
-------------------[가정, 낮은 프로세스 = LP, 중간 프로세스 = MP, 높은 프로세스 = HP]
LP가 중요한 섹션을 실행 중입니다. 중요 섹션에 들어가는 동안 LP는 OBJ와 같은 일부 개체에 대한 잠금을 획득 했어야합니다. LP는 이제 임계 섹션 안에 있습니다.
한편 HP가 만들어집니다. 우선 순위가 높기 때문에 CPU는 컨텍스트 전환을 수행하고 HP는 이제 실행 중입니다 (동일한 중요 섹션이 아니라 다른 코드). HP 실행 중 어느 시점에서 동일한 OBJ에 대한 잠금이 필요하지만 (동일한 중요 섹션에있을 수도 있고 아닐 수도 있음) OBJ에 대한 잠금은 중요 섹션을 실행하는 동안 선점되었으므로 여전히 LP에 의해 유지됩니다. . 프로세스가 RUNNING이 아닌 READY 상태이기 때문에 LP는 지금 포기할 수 없습니다. 이제 HP는 BLOCKED / WAITING 상태로 이동합니다.
이제 MP가 들어 와서 자체 코드를 실행합니다. MP는 OBJ에 대한 잠금이 필요하지 않으므로 정상적으로 계속 실행됩니다. HP는 LP가 잠금을 해제 할 때까지 대기하고 LP는 MP가 실행을 완료 할 때까지 대기하여 LP가 RUNNING 상태 (.. 및 실행 및 잠금 해제)로 돌아올 수 있도록합니다. LP가 잠금을 해제 한 후에 만 HP가 준비 상태로 돌아올 수 있습니다 (그런 다음 우선 순위가 낮은 작업을 선점하여 RUNNING으로 이동할 수 있습니다).
따라서 이는 MP가 완료 될 때까지 LP를 실행할 수 없으므로 HP가 실행할 수 없음을 의미합니다. 따라서 OBJ 잠금을 통해 직접 관련되지는 않지만 HP가 MP를 기다리는 것처럼 보입니다. -> 우선 순위 반전 .
Priority Inversion에 대한 해결책은 Priority Inheritance입니다 .
-------------------프로세스 (A)의 우선 순위를 A가 리소스 잠금을 가진 리소스를 기다리는 다른 프로세스의 최대 우선 순위로 높입니다.
우선 순위 반전은 더 낮은 우선 순위 프로세스가 더 높은 우선 순위 프로세스에 필요한 자원을 확보하여 자원이 해제 될 때까지 더 높은 우선 순위 프로세스가 진행되는 것을 방지하는 것입니다.
예 : FileA는 Proc1 및 Proc2에 의해 액세스되어야합니다. Proc 1은 Proc2보다 우선 순위가 높지만 Proc2는 먼저 FileA를 엽니 다.
일반적으로 Proc1은 Proc2보다 10 배 더 자주 실행되지만 Proc2가 파일을 보유하고 있기 때문에 아무것도 할 수 없습니다.
따라서 결국 Proc1은 Proc2가 FileA로 끝날 때까지 차단되며 기본적으로 Proc2는 FileA의 핸들을 보유하는 동안 우선 순위가 '반전'됩니다.
'문제 해결'에 관한 한 우선 순위 반전은 계속 발생하면 그 자체로 문제입니다. 최악의 경우 (대부분의 운영 체제에서는 이런 일이 발생하지 않음)는 Proc1이 실행될 때까지 Proc2를 실행할 수없는 경우입니다. 이로 인해 Proc1이 CPU 시간 할당을 계속 받고 Proc2는 CPU 시간을 얻지 못하므로 시스템이 잠기 게되므로 파일이 해제되지 않습니다.
-------------------아주 간단하고 명확하게하겠습니다. (이 답변은 위의 답변을 기반으로하지만 명확하게 제시되었습니다).
자원 R과 3 개의 프로세스 가 있다고 가정 합니다. L, M, H. 여기서 p(L) < p(M) < p(H)(여기서 p(X)우선 순위는 X).
말하다
L먼저 실행을 시작하고R. (에 대한 독점 액세스R)H나중에도이에 단독으로 액세스 할 제공R하고 있기 때문에L그것을 들고,H기다려야한다.M다음에 오는H하고 그것을 필요로하지 않는다R. 그리고 이후M모든 것을 가지고 그것이 강제로 실행하고자하는L가에 비해 높은 우선 순위를 가지고로 떠나L. 그러나 실행에 필요한H리소스가 잠겨 있으므로이를 수행 할 수 없습니다L.
이제 문제를 더 명확하게 만들면 실제로는 발생하지 않은 작업이 완료 될 M때까지 기다려야 하며 이것이 문제입니다. 과 같은 많은 프로세스 가 나타나고 실행 및 해제를 허용하지 않으면 잠금 이 실행되지 않습니다. 시간이 중요한 애플리케이션에서 위험 할 수 있음Hp(H) > p(M)MLH
그리고 솔루션은 위의 답변을 참조하십시오 :)
-------------------우선 순위 반전은 다음과 같이 발생합니다. 이름이 높은 우선 순위, 중간 및 낮은 우선 순위를 나타내는 프로세스 H, M 및 L이 주어지면 H와 L만이 공통 자원을 공유합니다.
L은 먼저 리소스를 획득하고 실행을 시작합니다. H도 해당 리소스가 필요하기 때문에 대기 대기열에 들어갑니다. M은 리소스를 공유하지 않고 실행을 시작할 수 있으므로 공유합니다. L이 어떤 방법 으로든 인터럽트되면 M은 우선 순위가 더 높고 인터럽트가 발생하는 순간에 실행 중이므로 실행 상태를 취합니다. H는 M보다 우선 순위가 높지만 대기 대기열에 있기 때문에 리소스를 얻을 수 없으므로 M보다 우선 순위가 낮습니다. M이 끝나면 L이 다시 CPU를 인수하여 H가 전체 시간을 대기하게합니다.
-------------------차단 된 높은 우선 순위 스레드가 자원을 보유하고있는 낮은 우선 순위 스레드로 높은 우선 순위를 전송하면 우선 순위 반전을 피할 수 있습니다.
-------------------스케줄링 문제는 우선 순위가 높은 프로세스가 현재 우선 순위가 낮은 프로세스 또는 낮은 우선 순위 프로세스 체인에서 액세스하고있는 커널 데이터를 읽거나 수정해야 할 때 발생합니다. 커널 데이터는 일반적으로 잠금으로 보호되기 때문에 우선 순위가 높은 프로세스는 우선 순위가 낮은 프로세스가 리소스로 완료 될 때까지 기다려야합니다. 우선 순위가 낮은 프로세스가 우선 순위가 더 높은 다른 프로세스를 선호하는 경우 상황은 더욱 복잡해집니다. 예를 들어, 우선 순위가 L <M <H 인 순서를 따르는 L, M 및 H의 세 가지 프로세스가 있다고 가정합니다. 프로세스 H에는 현재 프로세스 L에서 액세스중인 리소스 R이 필요하다고 가정합니다. 일반적으로 프로세스 H는 자원 R을 사용하여 L이 완료 될 때까지 기다립니다. 그러나 이제 프로세스 M이 실행 가능하게되어 프로세스 L을 선점한다고 가정합니다. 간접적으로, 우선 순위가 낮은 프로세스 (프로세스 M)는 프로세스 H가 L이 리소스 R을 포기할 때까지 기다려야하는 시간에 영향을 미쳤습니다.이 문제를 우선 순위 반전이라고합니다. 우선 순위가 두 개 이상인 시스템에서만 발생하므로 한 가지 해결책은 다음과 같습니다. 그러나 대부분의 범용 운영 체제에는 충분하지 않습니다. 일반적으로 이러한 시스템은 우선 순위 상속 프로토콜을 구현하여 문제를 해결합니다. 이 프로토콜에 따르면 우선 순위가 높은 프로세스에 필요한 리소스에 액세스하는 모든 프로세스는 해당 리소스가 완료 될 때까지 더 높은 우선 순위를 상속받으며, 완료되면 우선 순위가 원래 값으로 돌아갑니다. 위의 예에서 우선 순위 상속 프로토콜은 프로세스 L이 프로세스 H의 우선 순위를 일시적으로 상속하도록 허용합니다. 따라서 프로세스 M이 실행을 선점하는 것을 방지합니다. 프로세스 L이 리소스 R을 사용하여 완료되면 H에서 상속 된 우선 순위를 포기하고 원래 우선 순위를 가정합니다. 이제 리소스 R을 사용할 수 있으므로 M이 아닌 프로세스 H가 다음에 실행됩니다. 참고 : ABRAHAM SILBERSCHATZ
-------------------H우선 순위가 높고 우선 순위 L가 낮은 두 개의 프로세스가있는 시스템을 고려하십시오 . 스케줄링 규칙은 H우선 순위가 높기 때문에 준비 상태가 될 때마다 실행됩니다. L임계 영역에서 특정 순간 H에 실행할 준비가됩니다 (예 : I / O 작업 완료). H이제는 대기로 바쁘게 시작되지만 실행 L중에는 예약 되지 않으므로 중요 섹션을 떠날 기회가 없습니다. 그래서 영원히 반복됩니다. HLH
이 상황을라고 Priority Inversion합니다. 우선 순위가 높은 프로세스가 낮은 우선 순위 프로세스를 기다리고 있기 때문입니다.
출처
https://stackoverflow.com/questions/22079911