Priority Inversion

From Suhrid.net Wiki
Jump to: navigation, search

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.
  • Priority inheritance is where a low priority real-time thread is holding a lock that is needed by a higher priority thread. The low priority threads runs at the priority of the

high priority thread when accessing the lock. The inheritance doesn’t occur until the high priority thread requests the lock.


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. This can be system wide or per shared object.
  • 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

  • Priority ceiling emulation is a form of priority inheritance. However, in this case the low priority thread runs at the highest priority of any thread that might request the lock.
  • It acquires this priority IMMEDIATE it locks the lock irrespective of whether anyone is being blocked.
  • 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. (As opposed to m blocks in Priority Inheritance)
  • 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.
  • In RTSJ PriorityCeilingEmulation is a subclass of MonitorControl.

Deadlocks

  • Can deadlocks occur while using PCE ?
  • No. When a SO, A, wants to run all its locks must be free. If they were not the SO B holding a lock must be executing at a priority equal of greater

to A. Therefore, A will not be executed until B has finished with the lock.

  • So if thread wants to access two critical resources - it will access both without pre-emption from any other thread.

Ceiling Violation

  • Whenever a SO calls a method for an object which has PCE in force the RTJVM will check the priority of the caller.
  • If the priority > ceiling priority for the object, CeilingViolation will be thrown.

Communication between heap and no heap SOs

  • SO's that should be completely predictable can be defined not to reference the heap.
  • This means they can preempt any GC.
  • However there is a need to share info between Heap using and Non Heap using SO's.
  • To ensure NoHeap SO's are not indirectly delayed by GC.
    • All no heap SO's have great priority than heap SO's.
    • PCE should be used for all shared synchronized objects.
    • All shared synchronized objects must have their memory preallocated.
    • Objects passed while communicating should be primitives or be from scope or immortal.