Difference between revisions of "Priority Inversion"

From Suhrid.net Wiki
Jump to navigationJump to search
Line 42: Line 42:
 
= Priority Ceiling Emulation =
 
= Priority Ceiling Emulation =
  
*  
+
* Each thread has a static (base) default priority assigned to it.
 +
* Each resource has a static ceiling value defined - this is the maximum priority of the threads that use it. For e.g if a resource is being used by thread with priority 10,2,1. It's ceiling is 10.
 +
* A thread has a dynamic (active) priority which is max(its own static priority, ceiling value of any resource it has locked).
 +
* As a consequence, the thread will only suffer a block at the beginning of its execution. How ? For e.g. if a LP thread starts first and locks a resource, then LP thread gets ceiling value priority of resource and runs to completion, so HP thread waits until then. Once HP thread starts running, then it wont block, because whenever it locks any resource - it runs with max priority possible.
 +
* Once the thread starts actually executing,
 +
** all the resources it needs must be free;
 +
** if they were not, it means that some equal or higher priority thread would be using the resource and the thread’s execution would be postponed.
  
 
[[Category:RealtimeJava]]
 
[[Category:RealtimeJava]]

Revision as of 17:40, 6 January 2012

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 !

Priority Ceiling Emulation

  • Each thread has a static (base) default priority assigned to it.
  • Each resource has a static ceiling value defined - this is the maximum priority of the threads that use it. For e.g if a resource is being used by thread with priority 10,2,1. It's ceiling is 10.
  • A thread has a dynamic (active) priority which is max(its own static priority, ceiling value of any resource it has locked).
  • As a consequence, the thread will only suffer a block at the beginning of its execution. How ? For e.g. if a LP thread starts first and locks a resource, then LP thread gets ceiling value priority of resource and runs to completion, so HP thread waits until then. Once HP thread starts running, then it wont block, because whenever it locks any resource - it runs with max priority possible.
  • Once the thread starts actually executing,
    • all the resources it needs must be free;
    • if they were not, it means that some equal or higher priority thread would be using the resource and the thread’s execution would be postponed.