A dynamic online non preemptive soft real time scheduling algorithm – high deadline meeting rate

Abstract

The evergreen Earliest Deadline First algorithm is an excellent dynamic real time job scheduler under normal System Load. However, its’ performance in terms of deadline meeting rate is simply undeterministic under overload condition. This thesis presents a new algorithm in scheduling Soft Real Time Jobs by means of Dynamic Non Preemptive scheme, which is capable of maintaining excellent deadline meeting rate during normal System Load, while producing much better deadline meeting rate during overload. In a soft real time system it is critical that an algorithm is capable of maintaining acceptable performance during overload, because soft real time tolerates some level of missing deadline at the benefit of efficiency in its own parameter of interest. Many other works has been done to cater the issue of undeterministic behavior of Earliest Deadline First during overload. However, most of them uses preemptive scheme, requires overload detection and tailored to specific application. The proposed algorithm, which group jobs using purely dynamic parameters in its grouping formula is by itself novel. Next, the jobs in the group are schedule by another novel approach which is identical to shortest job first, but comes with a minimum of two extra benefits. To analyze the performance of the developed algorithm and compares it to other algorithms, a non preemptive, non resource constraint soft real time simulation model is developed on the OMNeT++ discrete event simulator. The Real Time Scheduling Simulator is rather moderate in size but is serve the simulation purpose. The Real Time Scheduling simulation model is then validated based on its specification. As for verification, the simulation model is tested against known cases to ensure correctness of operation and results achieved is found to be identical to theory. The analysis of the algorithm has been conducted by means of excessive simulation approach, where each simulation runs has been repeated with different seeds. The performance of the algorithms has been experimented with combinations of parameters which compose of Relative Deadline Size, Deadline Tolerance and Execution Time. Simulations results shows that, the developed algorithm, named gutEDF always achieved much better performance in terms deadline meeting rate compared to Earliest Deadline First and its immediate predecessor known as Group Earliest Deadline First, under different combinations of input parameters. Not only that, the algorithm is also evaluated in terms of Average Response Time, which is a Soft Real Time performance parameter for some application and results collected shows that gutEDF always achieved much better Average Response Time.