Schedulability analysis of resource access control protocols in real-time systems
Min-Ih Chen · 1992
To guarantee the timing requirements of real-time systems are satisfied, the timing behavior of the systems must be predictable. Priority driven scheduling algorithms, such as the earliest deadline first algorithm, are known to be effective and predictable in scheduling independent tasks. However, when concurrent tasks share resources in a mutually exclusive manner, the timing behavior of the system becomes less predictable. Due to the conflict in accessing shared resources, a high priority task may have to wait for the execution of a low priority task, a phenomenon called priority inversion, causing it to miss its deadline requirement. To minimize the occurrences of priority inversion in using the earliest deadline first algorithm, we proposed two resource access control protocols to coordinate the accesses to shared resources. The dynamic priority ceiling is used when every shared resource is unique and can be identified by the tasks using it. When two or more shared resources provide the same service and can be used interchangeably, the generalized priority ceiling protocol is used. We analyzed the properties of these two protocols, and showed that they are effective in making the timing behavior of tasks more predictable. Schedulability conditions are conditions under which all tasks in a system are guaranteed to be schedulable. The availability of schedulability conditions allows system designers to verify if a given system can meet its timing requirement in a simple and straightforward way, without going through more expensive and time-consuming testing or simulation. We derived several schedulability conditions for a class of resource access control protocols based on the earliest deadline first algorithm, and showed that they are more general and more exact than the schedulability conditions currently reported in the literature. We also investigated the schedulability conditions of a particular real-time reader and writer problem and suggested two operation coalescence schemes to improve its performance.