Characterization of scheduling algorithms in real-time computing systems

Most task scheduling algorithms in real-time applications are either preemptive or non-preemptive. We analyze two important characteristics, the schedulability and scheduling overhead, for these two types of algorithms. Simulation results are provided based on two well-known scheduling algorithms, the rate-monotonic (RM) and the earliest-deadline-first (EDF) algorithms. We also study the task blocking problem in preemptive scheduling algorithms caused by the need of sharing resources. Although the priority-inheritance (PI) and priority-ceiling (PC) protocols developed in [1] can be used to protect real-time tasks from missing their deadlines, changing priorities all the time will result in more overhead. We thus propose the locking protocol, a task becomes non-preemptive when it is using a shared resource, which is easier to implement and its overhead is also lower