Priority Inversion
   HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, priority inversion is a scenario in
scheduling A schedule or a timetable, as a basic time-management tool, consists of a list of times at which possible task (project management), tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order ...
in which a high priority task is indirectly superseded by a lower priority task effectively inverting the assigned priorities of the tasks. This violates the priority model that high-priority tasks can only be prevented from running by higher-priority tasks. Inversion occurs when there is a
resource contention In computer science, resource contention is a conflict over access to a shared resource such as random access memory, disk storage, cache memory, internal buses or external network devices. A resource experiencing ongoing contention can be des ...
with a low-priority task that is then preempted by a medium-priority task.


Formulation

Consider two tasks H and L, of high and low priority respectively, either of which can acquire exclusive use of a shared resource R. If H attempts to acquire R after L has acquired it, then H becomes blocked until L relinquishes the resource. Sharing an exclusive-use resource (R in this case) in a well-designed system typically involves L relinquishing R promptly so that H (a higher priority task) does not stay blocked for excessive periods of time. Despite good design, however, it is possible that a third task M of medium priority becomes runnable during L's use of R. At this point, M being higher in priority than L, preempts L (since M does not depend on R), causing L to not be able to relinquish R promptly, in turn causing H—the highest priority process—to be unable to run (that is, H suffers unexpected blockage indirectly caused by lower priority tasks like M).


Consequences

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 ''Starved'' is an American television sitcom that aired for one season on FX for seven episodes in 2005. The series was about four friends who each suffer from eating disorders, who met at a "shame-based" support group called Belt Tighteners. I ...
of the resources, it might lead to a system malfunction or the triggering of pre-defined corrective measures, such as a
watchdog timer A watchdog timer (sometimes called a ''computer operating properly'' or ''COP'' timer, or simply a ''watchdog'') is an electronic or software timer that is used to detect and recover from computer malfunctions. Watchdog timers are widely used in ...
resetting the entire system. The trouble experienced by the
Mars Pathfinder ''Mars Pathfinder'' (''MESUR Pathfinder'') is an American robotic spacecraft that landed a base station with a roving probe on Mars in 1997. It consisted of a lander, renamed the Carl Sagan Memorial Station, and a lightweight, wheeled robot ...
lander in 1997 is a classic example of problems caused by priority inversion in
realtime ''RealTime'', also known as ''RealTime Arts'', was a free Australian arts magazine, published by Open City in print from 1994 until 2015 and online from 1996 to December 2017. History The free national arts magazine ''RealTime'', also known as ...
systems. Priority inversion can also reduce the
perceived performance Perceived performance, in computer engineering, refers to how quickly a software feature appears to perform its task. The concept applies mainly to user acceptance aspects. The amount of time an application takes to start up, or a file to downlo ...
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 Computerized batch processing is a method of running software programs called jobs in batches automatically. While users are required to submit the jobs, no other interaction by the user is required to process the batch. Batches may automatically ...
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 real-time response guarantees. Because priority inversion results in the execution of a lower-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 Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occurs (task finishes, new task released, etc.) ...
(EDF).


Solutions

The existence of this problem has been known since the 1970s. Lampson and Redell published one of the first papers to point out the priority inversion problem. Systems such as the UNIX kernel were already addressing the problem with the splx() primitive. There is no foolproof 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 disabling interrupts is 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. In early versions of UNIX, a series of primitives named splx(0) ... splx(7) disabled all interrupts up through the given priority. By properly choosing the highest priority of any interrupt that ever entered the critical section, the priority inversion problem could be solved without locking out all of the interrupts. Ceilings were assigned in rate-monotonic order, i.e. the slower devices had lower priorities. :In multiple CPU systems, a simple variation, "single shared-flag locking" is used. 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 In computer science and software engineering, busy-waiting, busy-looping or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input or a lock is available. Spinning can also be used ...
. 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 system An embedded system is a computer system—a combination of a computer processor, computer memory, and input/output peripheral devices—that has a dedicated function within a larger mechanical or electronic system. It is ''embedded'' as ...
s, 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. Many software engineers consider them impractical in general-purpose computers. ;Priority ceiling protocol :With
priority ceiling protocol In real-time computing, the priority ceiling protocol is a synchronization protocol for shared resources to avoid unbounded priority inversion and mutual deadlock due to wrong nesting of critical sections. In this protocol each resource is assign ...
, the shared
mutex In computer science, a lock or mutex (from mutual exclusion) is a synchronization primitive: a mechanism that enforces limits on access to a resource when there are many threads of execution. A lock is designed to enforce a mutual exclusion concur ...
process (that runs the operating system code) has a characteristic (high) priority of its own, which is assigned to the task of locking the mutex. This works well, provided the other high-priority task(s) that tries to access the mutex does not have a priority higher than the ceiling priority. ;Priority inheritance :Under the policy of
priority inheritance In real-time computing, priority inheritance is a method for eliminating unbounded priority inversion. Using this programming method, a process scheduling algorithm increases the priority of a process (A) to the maximum priority of any other proce ...
, whenever a high-priority task has to wait for some resource shared with an executing low-priority task, the low-priority task is temporarily 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 affecting the waiting high priority task as well. Once the resource is released, the low-priority task continues at its original priority level. ;Random boosting :Ready tasks holding locks are randomly boosted in priority until they exit the critical section. This solution is used in
Microsoft Windows Windows is a group of several proprietary graphical operating system families developed and marketed by Microsoft. Each family caters to a certain sector of the computing industry. For example, Windows NT for consumers, Windows Server for serv ...
.Priority Inversion
on
MSDN Microsoft Developer Network (MSDN) was the division of Microsoft responsible for managing the firm's relationship with developers and testers, such as hardware developers interested in the operating system (OS), and software developers developing ...
;Avoid blocking :Because priority inversion involves a low-priority task blocking a high-priority task, one way to avoid priority inversion is to avoid blocking, for example by using
non-blocking algorithm In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking im ...
s such as
read-copy-update In computer science, read-copy-update (RCU) is a synchronization mechanism that avoids the use of lock primitives while multiple threads concurrently read and update elements that are linked through pointers and that belong to shared data structure ...
.


See also

*
Nice (Unix) nice is a program found on Unix and Unix-like operating systems such as Linux. It directly maps to a kernel call of the same name. nice is used to invoke a utility or shell script with a particular CPU priority, thus giving the process more or ...
*
Non-blocking synchronization In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking im ...
*
Pre-emptive multitasking In computing, preemption is the act of temporarily interrupting an executing task, with the intention of resuming it at a later time. This interrupt is done by an external scheduler with no assistance or cooperation from the task. This preempt ...
*
Read-copy-update In computer science, read-copy-update (RCU) is a synchronization mechanism that avoids the use of lock primitives while multiple threads concurrently read and update elements that are linked through pointers and that belong to shared data structure ...
(RCU) *
Resource starvation In computer science, resource starvation is a problem encountered in concurrent computing where a process is perpetually denied necessary resources to process its work. Starvation may be caused by errors in a scheduling or mutual exclusion algori ...


References

{{reflist


External links


Description from FOLDOCCitations from CiteSeerIEEE Priority Inheritance Paper by Sha, Rajkumar, LehoczkyIntroduction to Priority Inversion by Michael Barr
Concurrency control Software bugs Embedded systems