Priority Inversion 優(yōu)先級反轉(zhuǎn)是嵌入式實時系統(tǒng)里面的一個經(jīng)典的問題。簡單描述一下這個問題：有三個優(yōu)先級不同的task,A,B,C; A的優(yōu)先級最高，B次之，C最低。其中A和C有共享的臨界區(qū)。如果C已進(jìn)入臨界區(qū)，那么A在進(jìn)入進(jìn)入臨界區(qū)之前，就會被阻塞。task B有可能打斷C而進(jìn)入運行狀態(tài)，這樣C什么時候從臨界區(qū)退出，就是一個未知的時間。A只有C從臨界區(qū)退出后才能被調(diào)度，A被阻塞的時間也是未知的。這樣，低優(yōu)先級的B先于高優(yōu)先級的A被調(diào)度，優(yōu)先級發(fā)生了逆轉(zhuǎn)。
這個問題在一般的操作系統(tǒng)里面不是一個嚴(yán)重的問題，最多A被多阻塞了一段時間。但是，在實時系統(tǒng)里面，如果一個任務(wù)在規(guī)定的時間里面沒有被調(diào)度運行，系統(tǒng)就相當(dāng)于失敗了，可能引發(fā)系統(tǒng)崩潰。
解決這個問題有兩種手段：
1：Priority inheritance(優(yōu)先級繼承)，如果一個高優(yōu)先級的task被阻塞，與它共享臨界區(qū)的低優(yōu)先級的task在進(jìn)入臨界區(qū)后，優(yōu)先級就會繼承高優(yōu)先級task的優(yōu)先級，保證它不會被其他優(yōu)先級次高的任務(wù)打斷。從臨界區(qū)退出后，C的優(yōu)先級恢復(fù)正常。
2：A priority ceiling（最高優(yōu)先級），給臨界區(qū)分配最高優(yōu)先級，如果一個task進(jìn)入臨界區(qū)，就把臨界區(qū)的優(yōu)先級賦給它，已保證它不會被打斷。從臨界區(qū)退出后，task的優(yōu)先級恢復(fù)正常。
實時操作系統(tǒng)的一個特點就是，一個實時任務(wù)，會在規(guī)定的時間內(nèi)得到響應(yīng)，并且在規(guī)定的時間內(nèi)完成任務(wù)。所以，一切不可預(yù)知的動作都是有害的。
有興趣可以看看下面兩個鏈接：
http://en.wikipedia.org/wiki/Priority_inversion
Priority inversion
From Wikipedia, the free encyclopedia
Jump to: navigation, search
In scheduling, priority inversion is the scenario where a low priority task holds a shared resource that is required by a high priority task. This causes the execution of the high priority task to be blocked until the low priority task has released the resource, effectively "inverting" the relative priorities of the two tasks. If some other medium priority task, one that does not depend on the shared resource, attempts to run in the interim, it will take precedence over both the low priority task and the high priority task.
In some cases, priority inversion can occur without causing immediate harm—the delayed execution of the high priority task goes unnoticed, and eventually the low priority task releases the shared resource. However, there are also many situations in which priority inversion can cause serious problems. If the high priority task is left starved of the resources, it might lead to a system malfunction or the triggering of pre-defined corrective measures, such as a watch dog timer resetting the entire system. The trouble experienced by the Mars lander "Mars Pathfinder"[1][2] is a classic example of problems caused by priority inversion in realtime systems.
Priority inversion can also reduce the perceived performance of the system. Low priority tasks usually have a low priority because it is not important for them to finish promptly (for example, they might be a batch job or another non-interactive activity). Similarly, a high priority task has a high priority because it is more likely to be subject to strict time constraints—it may be providing data to an interactive user, or acting subject to realtime response guarantees. Because priority inversion results in the execution of the low priority task blocking the high priority task, it can lead to reduced system responsiveness, or even the violation of response time guarantees.
A similar problem called deadline interchange can occur within Earliest Deadline First Scheduling (EDF).
Contents
[
hide]
[edit] Solutions
The existence of this problem has been known since the 1970s, but there is no fool-proof method to predict the situation. There are however many existing solutions, of which the most common ones are:
- Disabling all interrupts to protect critical sections
- When disabled interrupts are used to prevent priority inversion, there are only two priorities: preemptible, and interrupts disabled. With no third priority, inversion is impossible. Since there's only one piece of lock data (the interrupt-enable bit), misordering locking is impossible, and so deadlocks cannot occur. Since the critical regions always run to completion, hangs do not occur. Note that this only works if all interrupts are disabled. If only a particular hardware device's interrupt is disabled, priority inversion is reintroduced by the hardware's prioritization of interrupts. A simple variation, "single shared-flag locking" is used on some systems with multiple CPUs. This scheme provides a single flag in shared memory that is used by all CPUs to lock all inter-processor critical sections with a busy-wait. Interprocessor communications are expensive and slow on most multiple CPU systems. Therefore, most such systems are designed to minimize shared resources. As a result, this scheme actually works well on many practical systems. These methods are widely used in simple embedded systems, where they are prized for their reliability, simplicity and low resource use. These schemes also require clever programming to keep the critical sections very brief, under 100 microseconds in practical systems. Many software engineers consider them impractical in general-purpose computers.
- Arguably, these methods are similar to priority ceilings.
- A priority ceiling
- With priority ceilings, the shared mutex process (that runs the operating system code) has a characteristic (high) priority of its own, which is assigned to the task locking the mutex. This works well, provided the other high priority task(s) that try to access the mutex does not have a priority higher than the ceiling priority.
- Priority inheritance
- Under the policy of priority inheritance, whenever a high priority task has to wait for some resource shared with an executing low priority task, the low priority task is assigned the priority of the highest waiting priority task for the duration of its own use of the shared resource, thus keeping medium priority tasks from pre-empting the (originally) low priority task, and thereby effectively the waiting high priority task as well.
[edit] See also
- ^ What Really Happened on Mars by Glenn Reeves of the JPL Pathfinder team
- ^ Explanation of priority inversion problem experienced by Mars Pathfinder
[edit] References
- by Butler W. Lampson and David D. Redell, CACM 23(2):105-117 (Feb 1980) - One of the first (if not the) first papers to point out the priority inversion problem. Also suggested disabling interrupts and the priority ceiling protocol as solutions, noting that the former of these two cannot not tolerate page faults while in use.
[edit] External links
Retrieved from "