우선 순위 반전이란 무엇입니까?

우선 순위 반전이란 무엇입니까?

---

운영체제 개발과 관련하여 '우선 순위 반전'이라는 말을 들었습니다.

우선 순위 반전이란 정확히 무엇입니까?

해결하려는 문제는 무엇이며 어떻게 해결합니까?

---

우선 순위 반전은 해결책이 아니라 문제입니다. 일반적인 예는 우선 순위가 높은 프로세스가 필요로하는 자원을 획득 한 다음 중간 우선 순위 프로세스에 의해 선점되는 낮은 우선 순위 프로세스로, 중간 우선 순위 프로세스가 완료되는 동안 자원에서 높은 우선 순위 프로세스가 차단됩니다 (효과적으로 낮은 우선 순위).

다소 유명한 예는 Mars Pathfinder 로버가 경험 한 문제입니다. http://www.cs.duke.edu/~carla/mars.html , 꽤 흥미로운 읽기입니다.

---

우선 순위가 서로 다른 세 가지 작업 (tLow, tMed 및 tHigh)을 상상해보십시오. tLow 및 tHigh는 서로 다른 시간에 동일한 중요 리소스에 액세스합니다. tMed는 자체 작업을 수행합니다.

1. tLow가 실행 중이고 tMed 및 tHigh가 현재 차단됩니다 (중요 섹션에는 없음).
2. tLow가 나타나서 중요한 섹션으로 들어갑니다.
3. tHigh는 차단을 해제하고 시스템에서 우선 순위가 가장 높은 작업이므로 실행됩니다.
4. tHigh는 중요한 리소스에 들어 가려고 시도하지만 tLow가 있으면 차단합니다.
5. tMed는 차단을 해제하고 이제 시스템에서 우선 순위가 가장 높은 작업이므로 실행됩니다.

tLow는 자원을 포기할 때까지 실행할 수 없습니다. tLow는 tMed가 차단되거나 종료 될 때까지 실행할 수 없습니다. 작업의 우선 순위가 반전되었습니다. tHigh는 우선 순위가 가장 높지만 실행 체인의 맨 아래에 있습니다.

우선 순위 반전을 "해결"하려면 tLow의 우선 순위가 최소한 tHigh만큼 높아야합니다. 일부는 우선 순위를 가능한 가장 높은 우선 순위 수준으로 올릴 수 있습니다. tLow의 우선 순위 레벨을 높이는 것만 큼 중요한 것은 적절한 시간에 tLow의 우선 순위 레벨을 낮추는 것입니다. 시스템마다 접근 방식이 다릅니다.

tLow의 우선 순위를 떨어 뜨리는시기 ...

1. tLow가 가지고있는 자원에서 다른 작업은 차단되지 않습니다. 시간 초과 또는 리소스 해제 때문일 수 있습니다.
2. tLow의 우선 순위를 높이는 데 기여하는 다른 작업은 tLow가 가진 리소스에서 차단되지 않습니다. 시간 초과 또는 리소스 해제 때문일 수 있습니다.
3. 작업이 리소스를 기다리는 변경이있는 경우 해당 리소스에서 차단 된 가장 높은 우선 순위 수준 작업의 우선 순위와 일치하도록 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 is executing a critical section. While entering the critical section, LP must have acquired a lock on some object, say OBJ. LP is now inside the critical section.

Meanwhile, HP is created. Because of higher priority, CPU does a context switch, and HP is now executing (not the same critical section, but some other code). At some point during HP's execution, it needs a lock on the same OBJ (may or may not be on the same critical section), but the lock on OBJ is still held by LP, since it was pre-empted while executing the critical section. LP cannot relinquish now because the process is in READY state, not RUNNING. Now HP is moved to BLOCKED / WAITING state.

Now, MP comes in, and executes its own code. MP does not need a lock on OBJ, so it keeps executing normally. HP waits for LP to release lock, and LP waits for MP to finish executing so that LP can come back to RUNNING state (.. and execute and release lock). Only after LP has released lock can HP come back to READY (and then go to RUNNING by pre-empting the low priority tasks.)

So, effectively it means that until MP finishes, LP cannot execute and hence HP cannot execute. So, it seems like HP is waiting for MP, even though they are not directly related through any OBJ locks. -> Priority Inversion.

A solution to Priority Inversion is Priority Inheritance -

increase the priority of a process (A) to the maximum priority of any other process waiting for any resource on which A has a resource lock.

---

Let me make it very simple and clear. (This answer is based on the answers above but presented in crisp way).

Say there is a resource R and 3 processes. L, M, H. where p(L) < p(M) < p(H) (where p(X) is priority of X).

Say

• L starts executing first and catch holds on R. (exclusive access to R)
• H comes later and also want exclusive access to R and since L is holding it, H has to wait.
• M comes after H and it doesn't need R. And since M has got everything it wants to execute it forces L to leave as it has high priority compared to L. But H cannot do this as it has a resource locked by L which it needs for execution.

Now making the problem more clear, actually the M should wait for H to complete as p(H) > p(M) which didn't happen and this itself is the problem. If many processes such as M come along and don't allow the L to execute and release the lock H will never execute. Which can be hazardous in time critical applications

And for solutions refer the above answers :)

---

Priority inversion is where a lower priority process gets ahold of a resource that a higher priority process needs, preventing the higher priority process from proceeding till the resource is freed.

eg: FileA needs to be accessed by Proc1 and Proc2. Proc 1 has a higher priority than Proc2, but Proc2 manages to open FileA first.

Normally Proc1 would run maybe 10 times as often as Proc2, but won't be able to do anything because Proc2 is holding the file.

So what ends up happening is that Proc1 blocks until Proc2 finishes with FileA, essentially their priorities are 'inverted' while Proc2 holds FileA's handle.

As far as 'Solving a problem' goes, priority inversion is a problem in itself if it keeps happening. The worst case (most operating systems won't let this happen though) is if Proc2 wasn't allowed to run until Proc1 had. This would cause the system to lock as Proc1 would keep getting assigned CPU time, and Proc2 will never get CPU time, so the file will never be released.

---

Priority inversion occurs as such: Given processes H, M and L where the names stand for high, medium and low priorities, only H and L share a common resource.

Say, L acquires the resource first and starts running. Since H also needs that resource, it enters the waiting queue. M doesn't share the resource and can start to run, hence it does. When L is interrupted by any means, M takes the running state since it has higher priority and it is running on the instant that interrupt happens. Although H has higher priority than M, since it is on the waiting queue, it cannot acquire the resource, implying a lower priority than even M. After M finishes, L will again take over CPU causing H to wait the whole time.

---

Priority Inversion can be avoided if the blocked high priority thread transfers its high priority to the low priority thread that is holding onto the resource.

---

A scheduling challenge arises when a higher-priority process needs to read or modify kernel data that are currently being accessed by a lower-priority process—or a chain of lower-priority processes. Since kernel data are typically protected with a lock, the higher-priority process will have to wait for a lower-priority one to finish with the resource. The situation becomes more complicated if the lower-priority process is preempted in favor of another process with a higher priority. As an example, assume we have three processes—L, M, and H—whose priorities follow the order L < M < H. Assume that process H requires resource R,which is currently being accessed by process L.Ordinarily,process H would wait for L to finish using resource R. However, now suppose that process M becomes runnable, thereby preempting process L. Indirectly, a process with a lower priority—process M—has affected how long process H must wait for L to relinquish resource R. This problem is known as priority inversion.It occurs only in systems with more than two priorities,so one solution is to have only two priorities.That is insufficient for most general-purpose operating systems, however. Typically these systems solve the problem by implementing a priority-inheritance protocol. According to this protocol, all processes that are accessing resources needed by a higher-priority process inherit the higher priority until they are finished with the resources in question.When they are finished,their priorities revert to their original values. In the example above, a priority-inheritance protocol would allow process L to temporarily inherit the priority of process H,thereby preventing process M from preempting its execution. When process L had finished using resource R,it would relinquish its inherited priority from H and assume its original priority.Because resource R would now be available, process H—not M—would run next. Reference :ABRAHAM SILBERSCHATZ

---

Consider a system with two processes,H with high priority and L with low priority. The scheduling rules are such that H is run whenever it is in ready state because of its high priority. At a certain moment, with L in its critical region, H becomes ready to run (e.g., an I/O operation completes). H now begins busy waiting, but since L is never scheduled while H is running, L never gets the chance to leave the critical section. So H loops forever.

This situation is called Priority Inversion. Because higher priority process is waiting on lower priority process.

참고URL : https://stackoverflow.com/questions/4252158/what-is-priority-inversion