Improving dual priority scheduling

Abstract

A real-time system is a highly time constrained system and computes within restricted time intervals. These systems tend to have multiple time-critical tasks that must be carefully scheduled. Real-time systems can be used in many industries including healthcare, aircraft control, etc., where a single time derailment could create life threatening consequences.

Real-time systems commonly need to execute the same jobs repeatedly. We call these repeated jobs periodic tasks. A common scheduling paradigm, called fixed priority, assigns priorities to each task and executes all jobs generated by a task at its assigned priority. A simple variation of fixed priority is dual priority scheduling. In dual priority scheduling, tasks have a low priority, a high priority, and a promotion time. Each task executes in lower priority level untill it reaches its promotion time. Once it reaches the promotion time it starts executing at its higher priority level. This thesis focuses on improving the dual priority multiprocessor scheduling algorithm to make more task sets meet their deadlines. Our approach to increase feasibility is by increasing the priority promotion times. The increase in priority promotion time reduces the interference of the tasks that miss their deadlines in Fixed Priority schedules or Standard Dual Priority schedules. Resulting comparisons and evaluations derived from the experiments demonstrates that this approach can make many, but not all, of the task sets meet their deadlines. In fact for some scenarios 100 percent of the Fixed Priority unschedulable task sets we tested are schedulable using our Modified Dual Priority algorithm.