Scheduling Algorithms For Multiprocessor Hard Real-Time Systems

In hard real-time systems, every task should complete execution no later than its deadline, otherwise severe consequences would occur. The hard real-time scheduling algorithm sets up a deterministic execution order and proves the correctness by systematic approach so that it plays a very important role in hard real-time systems. Since the demand of computing capability grows, multiprocessor is widely adopted in hard real-time systems. Comparing with the counterpart in single processor systems, it is of much more difficulties in analysis and designing of scheduling behavior due to parallelism. Then efficient and effective multiprocessor hard-real time scheduling algorithms are important for hard real-time systems.The preemption, which increases the schedulability and flexibility while cost additional resources at the same time, is a critical attribute of hard real-time systems. Particularly in multiprocessor platforms the task migration induced by the preemption would cause non-neglectable performance drop. Reducing unnecessary preemptions is an important aspect in scheduling algorithm research. For this purpose we propose the global preemption threshold scheduling (GPTS) algorithm for multiprocessor hard real-time systems. GPTS is a hybrid approach between preemptive scheduling and non-preemptive scheduling. GPTS promotes the priority of a job when it first time get execution, by which the probability of being preempted is decreased. This approach can reduce the number of preemptions significantly while maintaining the schedulability.Limiting preemptions not only reduce unnecessary resource cost but also improve schedulability. Increasing the priority of an entire job would add too much interference on high priority tasks so that high priority tasks may become unschedulable. For improving the schedulability of the whole system, we propose the fixed priority limited preemption scheduling (FPLPS) algorithm for multiprocessor hard real-time systems. FPLPS sets up a region with higher priority at the end of a task. This approach can reduce the number of being preempted of the task in that region and add less additional interference on high priority tasks, which lead to the improvement of the schedulability of the entire system.During the execution period, fault happens occasionally. So the fault-tolerant capability is of great importance in hard real-time systems. The primary-backup approach is widely adopted in hard real-time scheduling. In primary-backup approach a backup starts execution only after the corresponding primary encounters a fault. This leads to a short execution time window for backups which make backups likely miss their deadlines. For solving the problem of bad real-time property of backups, we propose fault-tolerant global scheduling with non-preemptive backups (FTGS-NPB). This algorithm gives backups the highest priority to eliminate the interference on them. By this approach the response time of backups is shortened. The additional resource for fault-tolerance is also reduced.The backups can be split into active and passive backups. Active backups cost resources even no fault happens but have better real-time property. Passive backups don’t cost resources when no fault happens but have worse real-time property. Additionally passive backups can’t be implemented for high utilization tasks (total utilization higher than 1). For utilizing the advantages of both approaches, we propose the fault-tolerant global scheduling with backup delay (FTGS-BD). In FTGS-BD backups are configured as active or passive by resource utilization. The activation time of a primary is also pushed as late as possible. If no fault happens to the primary until response, the backup is cancelled immediately for saving resources. FTGS-BD can also be adopted when there are high utilization tasks.