Process Synchronization – VI – Priority Inversion

In the previous post, we discussed the implementation of semaphores without busy waiting. In this post, let us cover an interesting topic of Priority inversion.

What exactly is priority inversion?

  • Priority inversion is a problem which occurs while scheduling tasks.
  • The meaning of Priority inversion can be understood from the literal meaning of words priority and inversion.
  • Inversion of priority : When a high priority task is indirectly preempted by a lower priority task → Effectively inverting the relative priorities of the two tasks.
    • This is a problem, since it violates the Priority model, which by definition has it that a high priority task should be given high priority while scheduling.
    • In some cases, priority inversion can occur without causing any immediate harm, and delayed execution of the high priority task goes unnoticed.
    • However, sometimes Priority inversion is more than just a scheduling inconvenience. Why?
      • In Real-time systems, if a process to take longer than it should to accomplish a task due to priority inversion, it can cause a failure.
      • Cascading failures can lead to system failure, which can have devastating effects.

When does Priority Inversion happen?

  • A scheduling challenge arises when a higher-priority process needs to read or modify kernel data (which is usually protected with a lock) that are currently being accessed by a lower-priority process—or a chain of lower-priority processes
  • In these situations, the higher-priority process will have to wait for a lower-priority one to finish with the resource
     

    Process Priority

    Current Status

    What happens?

    Comments

    1

    H > L

    L is running outside of Critical section using resource R. H wants to run outside of critical section using R

    Since priority of H > L, therefore H preempts L. H takes control of R and starts executing. After that, H releases R and then L resumes its execution.

    No priority inversion

    2

    H > L

    L is executing its Critical section using resource R. H wants to run outside of critical section using R

    Since priority of H > L, therefore H preempts L. H takes control of R and starts executing. After that, H releases R and then L resumes its execution.

    Why is this Preemption legal? This is because we are guaranteed that H will not modify any shared memory/resource inside Critical section. Again, no priority inversion

    3

    H>L

    L is executing its Critical section using resource R. H wants to run inside critical section using R

    Here, since both of them want to execute critical section, and since L has already started its execution inside critical section, H will block() until L comes out of the Critical section.

    No priority inversion.

    4

    H>M>L

    L is executing its Critical section using resource R. H wants to execute critical section using R. M wants to use shared resource R, but will execute outside of Critical section.

    H cannot preempt L, as we have seen in case 3. However, M can preempt L as we have seen in Case 2. Therefore, M preempts L ans starts its execution. After that, it releases R which is acquired by L. L  releases R after coming out of Critical section. After this, H enters Critical section and starts execution.

    This is the case of Priority Inversion. Here, the execution of M before H, even though priority of H > M is not according to the rules of priority scheduling.

Let us assume that there are three processes – L, M, and H.
The priorities of these processes follow the order L < M < H, i.e. H has the highest priority. (As discussed in Case 4 above)

  • 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 wants to run, 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.

 

Priority Inversion Illustration
  Priority Inversion Illustration

Solving the Priority Inversion Problem

  • From the above table, we can notice that the problem of priority inversion (PI) doesn’t occur, if the system has only two levels of priorities.
    • This can be one solution to the PI problem.
    • However, two levels of priority are generally insufficient for most general purpose OS.
  • Typical solution used is to implement Priority Inheritance 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
    • e.g. → In the example discussed above. 
      • 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.

A real life example of the Priority inversion problem can be found in the case study of Mars Pathfinder.

  • The NASA space probe – The Mars Pathfinder, landed robot – Sojourner rover on Mars in 1977.
  • Problem → Shortly after the Sojourner began operating, it started to experience frequent computer resets [causing all hardware and software re-initializations]
  • Reason?
    • One high-priority task, “bc_dist,” was taking longer than expected to complete its work [H in our example]
    • This task was being forced to wait for a shared resource that was held by the lower-priority “ASI/MET” task [L in our case]
    • L was getting preempted by multiple medium-priority tasks [M in our case]
    • The “bc_dist” task would stall waiting for the shared resource, and ultimately the “bc_sched” task would discover the problem and perform the reset.
  • Solution
    • The solution was to enable priority inheritance by setting the mutex flag for the select() calls of ASI/MET to “on”.

In the next post, we will discuss the classical problems of Synchronization, i.e. the Bounded buffer problem, dining philosophers’ problem, and the Readers-writers problem. Until then, keep reading and sharing 🙂

Sources: 1,2,3,4,5