SCHEDULING STRATEGIES FOR PERIODIC AND APERIODIC TASKS IN REAL-TIME SYSTEMS

Abstract

Task scheduling is one of the most important issues in designing a real-time system. Areal-time system typically consists of a mixture of periodic and aperiodic tasks having hard, firm or soft deadlines. The goal of any scheduling algorithm is to guarantee the hard deadlines of periodic tasks while minimizing the probability of missing deadlines of aperiodic tasks. Avery important feature of real-time scheduling is the schedulability analysis, which is used to predict the temporal behavior of areal-time system. The analysis is used to find whether afeasible schedule exists according to agiven scheduling algorithm. The scheduling algorithm uses the notion of schedulability test to ensure the predictability of meeting the deadlines of tasks. In modern real-time systems, priority based scheduling has gained widespread popularity and is being followed by the researchers of the community as one of the most preferred approaches. The fixed priority preemptive scheduling algorithms are generally used for scheduling periodic tasks while dynamic priority scheduling algorithms are preferred for aperiodic tasks. The research work reported in this thesis is concerned with the study and development of scheduling schemes for periodic and aperiodic tasks in uniprocessor and multiprocessor systems under fixed priority scheduling environment. Aschedulability analysis for periodic tasks based on the concept of processor utilization, has been proposed. The Rate Monotonic and Deadline Monotonic scheduling approaches have been considered and schedulability tests are developed. The tests determine the maximum value of the processor utilization required for the given task set by attempting to determine the exact value of the interference faced by any task due to the higher priority tasks. The performance of these tests is further improved by grouping the tasks into equivalence classes defined based on the relationship between their periods. These tests provide an improved performance when compared with other tests of their class. Another major advantage of these tests is due to their analytical approach in determining the maximum processor utilization for feasibly scheduling the given periodic task set. A scheduling scheme for simultaneous scheduling of the hard deadline periodic and aperiodic tasks is also proposed. The core of this scheme is the schedulability analysis developed for the periodic tasks, which provides more slack for the aperiodic service and hence renders better performance. The acceptance tests necessary for servicing the hard deadline aperiodic tasks in order to provide a predictable behavior have also been developed. The performance of the proposed algorithms has been evaluated through simulation. The developed scheduling approaches are then extended to the multiprocessor systems. The central problem in multiprocessor scheduling is to determine when and where a given task is to be executed. The proposed schedulability tests are used to develop new task assignment schemes for assigning periodic tasks to processors with the goal of minimizing the number of processors required. The approach developed for uniprocessor systems is extended to address the problem of simultaneously scheduling the periodic and aperiodic tasks in multiprocessor systems. In addition, simulation studies have also been carried out to study the effect of parallelization on those aperiodic tasks whose deadlines are not guaranteed if assigned to a single processor in the system.