Combined scheduling of hard and soft real-time tasks in multiprocessor systems

Many complex real-time systems are composed of both hard and soft real-time tasks. Combined scheduling of hard and soft tasks in such systems should satisfy two important goals: (1) maximize the schedulability of soft real-time tasks with no or little impact on the schedulability of hard real-time tasks; (2) minimize the scheduling overhead. In this thesis, we develop two sets of algorithms for the problem, of which the first set allows sacrificing the schedulability of hard tasks and the second set does not. The first set of algorithms is based on a new concept, called task association , by which each soft task is associated with a hard task, whenever possible, in order to minimize the scheduling overhead. The second set has two algorithms, namely, background scheduling and emergency based scheduling. The background scheduling schedules soft tasks in the holes that are present in the schedule considering only the hard tasks. The emergency based scheduling always maintains two schedules (primary schedule and emergency schedule) and switches back and forth between them during the schedule construction process depending on the schedulability of a given hard task. To evaluate the schedulability of the proposed algorithms, extensive simulation studies were conducted and the results show that the proposed algorithms are superior to existing algorithms, in addition to some of them incurring lesser scheduling overhead