SCHEDULING TASKS UNDER TIME AND RESOURCE CONSTRAINT FOR HARD REAL-TIME SYSTEMS

Abstract

This dissertation concentrates on a heuristic approach ;for solving the problem of ,scheduling a set of tasks in hard real time system. Each task has an arbitrary and known worst case processing time and a deadline and may request simultaneous use of number of resources. A resource- can be used either in shared mode or in exclusive mode, if the task set is schedulable then the correspond-ing schedule has also been described. In many real time application environments, tasks are sche-d--uled dynamically and hence the scheduling strategy should have low run time cost. To keep run time cost low, the suboptimal algorithms are used rather than optimal ones. The computational complexity of the used scheme for scheduling 'n; tasks in a system having 'r' resources is 0(rn2), which is much lower than that of known algo-rithms. An extensive performance analysis by simulating task .sets do not show very good results with simple heuristics. The extended technique which uses combination of such heuristics in conjuction with limited backtrack is described and it performs excelently.