In scheduling, priority inversion is the "inverting" the relative priorities of the two tasks. If some other medium priority task, 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. Scheduling is a key concept in computer multitasking and multiprocessing operating system design, and in real-time operating system design. ...

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. In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. ... A watchdog timer is a computer hardware timing device that triggers a system reset if the main program, due to some fault condition, such as a hang, neglects to regularly service the watchdog (writing a “service pulse” to it, also referred to as “petting the dog”). The intention is to... The Mars Pathfinder was launched on December 4, 1996 by NASA aboard a Delta II just a month after the Mars Global Surveyor was launched. ... In computer science, real-time computing (RTC) is the study of hardware and software systems which are subject to a real-time constraint—i. ...

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. Perceived performance, in computer engineering, refers to how quickly a software feature appears to perform its task. ... Batch processing is the sequential execution of a series of programs (jobs) on a computer. ...

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: The 1970s decade refers to the years from 1970 to 1979. ...

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

When priority is inherited, the low priority task inherits the priority of the high priority task, thus stopping the medium priority task from pre-empting the low priority task.

To wait for an event by iterating through a tight loop or time-delayed loop that polls for the occurrence of the event on each pass rather than calling an interrupt and continuing execution on another part of the process. ... It has been suggested that Embedded System Design in an FPGA be merged into this article or section. ... In computer science, priority ceiling protocol is used in scheduling to avoid deadlock due to priority inversion. ... Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of un-shareable resources by pieces of computer code called critical sections. ... Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of un-shareable resources by pieces of computer code called critical sections. ... In computer science, priority inheritance is a method for eliminating priority inversion problems. ...

See also

• Starvation
• Pre-emptive multitasking
• Lock-free and wait-free algorithms
• Non-blocking synchronization
• Read-copy-update
• Priority inheritance
• Priority ceiling
• Nice (Unix)

In computer science, starvation is a multitasking-related problem, where a process is perpetually denied necessary resources. ... Pre-emptive multitasking is a form of multitasking. ... In contrast to algorithms that protect access to shared data with locks, lock-free and wait-free algorithms are specially designed to allow multiple threads to read and write shared data concurrently without corrupting it. ... In computer science, non-blocking synchronization ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. ... Read-copy-update is an operating system kernel technology for improving performance on computers with more than one CPU. The basic idea is as follows. ... In computer science, priority inheritance is a method for eliminating priority inversion problems. ... In computer science, priority ceiling protocol is used in scheduling to avoid deadlock due to priority inversion. ... nice (IPA pronunciation: ) is a command found on UNIX and other POSIX-like operating systems such as Linux. ...

References

1. ^ What Really Happened on Mars by Glenn Reeves of the JPL Pathfinder team
2. ^ Explanation of priority inversion problem experienced by Mars Pathfinder

External links

• Introduction to Priority Inversion
• Description from FOLDOC
• Citations from CiteSeer
• IEEE Priority Inheritance Paper by Sha, Rajkumar, Lehoczky
• Priority Inversion and other Perils of Preemption