Priority Inversion

Intro

• All synchronization mechanisms that are based on mutual exclusion suffer from priority inversion.
• This is where a low-priority SO enters into a mutual-exclusion zone which it shares with a high-priority SO.
• Now the low priority SO is in a mutex zone. Now, consider a medium priority thread which doesnt use the mutex zone, it preempts the low priority thread and starts performing a computationally intensive task.
• So the low priority SO cant run and get out of the mutex zone. Which means, the high priority thread is blocked.
• The medium-priority thread thereby indirectly blocks the progression of the high-priority thread for a potentially unbounded period of time.

• Solutions ?
  • Priority Inheritance
  • Non Blocking Communication

Priority Inheritance

• If thread p is blocking thread q, then p runs with q's priority.

RTSJ Model

• RTSJ requires all system Q's to be priority ordered.
  • Q's of SO's waiting for an object lock.
  • SO's blocked on wait().
• If more than one SO in the Q has same priority, then FIFO is followed.
• Has facilities to specify priority inversion control algorithms.
  • By default, RTSJ requires simple priority inheritance to occur whenever a SO is blocked waiting for a resource.

• There is a class called javax.realtime.MonitorControl which specifies the monitor priority control Policy.
• The PriorityInheritance class extends the MonitorControl class.

Blocking

• If a SO has m critical sections, the max no of times it can be blocked is m, ( with Priority Inheritance.)

Deadlock

• Deadlock can still occur with priority inheritance.

• LP Thread-A wants to use CS's x and y. HP Thread-B wants to use the same CS' x and y.
• LP locks x, HP prempts LP and locks y.
• Now with priority inheritance LP should get HP's priority, but doesnt solve any problems- because LP cant enter y which is held by HP.
• Deadlock !