An investigation of the dual priorityscheduling paradigm

Abstract: Real-time computing paradigm is being pervasively deployed in many critical and non-critical applicationssuch as aerospace and telecommunication systems. Most of these systems employ a preemptiveFixed Priority Scheduling (FPS) policy to schedule real-time tasks. Fixed priority scheduling is knownfor its implementation simplicity and low run-time overheads. However, FPS may not be able to use100% of the processor time, when compared to dynamic priority scheduling policies such as the EarliestDeadline First (EDF) scheduling scheme. Dynamic priority scheduling scheme, on the other hand, has tore-calculate the priorities on-line and hence may have significantly high run-time overheads. In this thesis, we investigate a novel scheduling scheme, known as the Dual Priority Scheduling scheme,that can potentially guarantee a feasible schedule. The main advantage of using a dual priority scheduleris that, it can achieve the implementation simplicity of a FPS scheme, while potentially assuring 100%processor utilization similar to EDF. Alan Burns proved the optimality of the dual priority scheme for twotasks, leaving its optimality for n tasks as an open problem. We investigate the optimality of dual priorityscheduling for three tasks, using simulations. We propose and evaluate three different approaches: lastchance method, slack method and brute force method, to calculate the dual priorities and the time intervalswhere these priorities are valid. Our evaluations showed that, of the proposed heuristics, the extended slack method which is a variationof the slack method, performed same as the brute force method. An interesting observation was that,the brute force and the extended slack methods could not schedule the same task sets, nor was the tasksets schedulable using any of the proposed methods.