An Optimal Priority Inheritance Protocol for Real-Time Synchronization

IN PRIORITY-DRIVEN PREEMPTIVE SCHEDULING, RESOURCES SHOULD, IDEALLY, ALWAYS BE ALLOCATED TO THE HIGHEST PRIORITY TASK. PRIORITY INVERSION IS A SITUATION IN WHICH A HIGHER PRIORITY JOB IS FORCED TO WAIT FOR A LOWER PRIORITY JOB. PRIORITY INVERSION DEGRADES SYSTEM SCHEDULABILITY, WHICH IS THE PROCESSOR UTILIZATION BELOW WHICH ALL JOB DEADLINES ARE GUARANTEED TO BE MET. HENCE, PRIORITY INVERSION SHOULD BE MINIMIZED IN A HARD REAL-TIME ENVIRONMENT. UNFORTUNATELY, A DIRECT APPLICATION OF SYNCHRONIZATION PRIMI- TIVES SUCH AS SEMAPHORES, MONITORS AND ADA RENDEZVOUS CAN CAUSE UNCONTROLLED PRIORITY INVERSION, A SITUATION IN WHICH A LOW PRIORITY JOB BLOCKS A HIGHER PRIORITY JOB FOR AN INDEFINITE PERIOD OF TIME. IN THIS PAPER, WE INVESTIGATE PROTOCOLS BELONGING TO THE CLASS OF `PRIORITY INHERI- TANCE PROTOCOLS'' THAT MINIMIZE PRIORITY INVERSION. WE DEVELOP A PRIORITY INHERITANCE PROTOCOL CALLED THE `SEMAPHORE CONTROL PROTOCOL'' WHICH HAS TWO PROPERTIES: DEADLOCKS ARE AVOIDED AND THE WORST-CASE BLOCKING DURATION OF A JOB IS REDUCED TO THE DURATION OF EXECUTION OF A SINGLE CRITICAL SECTION. THE PROTOCOL IS OPTIMAL IN THE SENSE THAT THE PROTOCOL EMBEDS NECESSARY AND SUFFICIENT CONDITIONS TO OBTAIN THESE TWO DESIRABLE PROPERTIES. FINALLY, WE CONSIDER IMPLEMENTATION ISSUES AND PRESENT OTHER PROTOCOLS WHICH ARE COMPUTATIONALLY SIMPLER THAN THE SEMAPHORE CONTROL PROTOCOL BUT ARE SUB- OPTIMAL.