A potential pitfall of using priority scheduling to schedule the processes or threads of a computer operating system. In a simple priority scheduling system, the ready thread or process with the highest priority is given the CPU anytime there is an opportunity for a context switch (such as the current thread yielding, completing, or blocking for I/O).

Priority inversion occurs in the simplest case when there are three threads, labeled A, B, and C, with A having the highest priority and C the lowest. Suppose A performs an I/O operation, requesting data that is held by C. A then blocks for I/O, and the processor becomes available. The scheduler examines the queue of threads that are waiting to run, and selects B, since its priority is greater than C's. At this point, a priority inversion has occured. Thread A, with high priority, must wait for thread B to yield, despite the fact that thread B has lower priority.

It is possible to write code that will detect priority inversion and attempt to remedy the situation. Another approach is through careful configuration of the threads- ensuring that any thread that will act as a server thread (C, in the case above) has priority greater than any thread that will request a service from it. This is only possible if the thread acting as a server will be I/O blocked most of the time, allowing the other threads to execute normally. Otherwise, the server thread will preempt the execution of the other threads on the ready queue.

Of course, a more general solution is not to implement a system with priority-only scheduling, as such a system can be prone to accidental deadlock, and is succeptible to intentional deadlocks caused by malicious programs. The addition of some non-determinism, in the form of a limited round robin or lottery scheduling system can reduce the vulnerability to deadlock, and relieve some priority inversions, though it may not eliminate them completely.

Log in or register to write something here or to contact authors.