Scheduling Algorithms

In this section, we take a look at various scheduling algorithms, and show whether or not each task meets its deadline.

Assume the following two tasks, P1 and P2; how do we schedule them?

• T1 = 50 msec, C1 = 25 msec, U1 = 50%
• T2 = 100 msec, C2 = 40 msec, U2 = 40%
• U = U1 + U2 = 90%

The deadline for each task is assumed to be the start of next period. If we use a highest-priority-first algorithm, there are two possibilities

• Case 1: Priority P1 > Priority P2
• Case 2: Priority P1 < Priority P2

Let us consider each case separately. Case 1 is shown in See Fixed-Priority, P1 > P2. All tasks meet their respective deadlines, while Case 2 is shown in See Fixed-Priority, P1 < P2. -- P2 misses half of its deadlines. In the second case, the task set is not schedulable, even though total utilization is less than 100%.

Fixed Priority Scheduling: Rate Monotonic Algorithm

The Rate-Monotonic Algorithm (RMA) is a procedure for assigning fixed priorities to tasks to maximize the possibility that the task set is schedulable. The basic algorithm is to do the following:

• Assigned fixed priorities proportionally to the tasks frequency
• Highest frequency task gets highest priority
• Lowest frequency task gets lowest priority

RMA is an optimal fixed priority algorithm. This means that if a task set cannot be scheduled using the rate monotonic algorithm, then it cannot be scheduled using any fixed priority algorithm.

Problems with Rate Monotonic Algorithm

One major problem for the RMA is that the schedulable bound is less than 100%. Specifically, it has been proven that the worst case schedulable bound is as low as 69%, while the average schedulable bound is 88%. This means that even though the total processor utilization is less than 100%, if that utilization is higher than the schedulable bound, then there is no guarantee that the task set will meet all deadlines.

Example, Case 3 in See Fixed-Priority, P1 > P2. P2 misses some deadlines is a modification of Case 1

• T1 = 50 msec, C1 = 25 msec, U1 = 50%
• T2 = 75 msec, C2 = 30 msec, U1 = 40%
• U = U1 + U2 = 90% (same as Case 1)

Using rate monotonic algorithm, assign Priority P1 > Priority P2

Even though utilization = 90% is the same as Case 1, this task set cannot be scheduled using any FIXED priority assignment.

Dynamic Scheduling

An alternative to fixed priority scheduling is dynamic priority scheduling, where priority is a function of time. There exist the following optimal dynamic priority algorithms:

• Earliest Deadline First (EDF)
• earliest deadline gets highest priority
• Minimum Laxity First (MLF)
• laxity = deadline - present - cpu_still_needed; smallest laxity gets highest priority.

If a task set cannot be scheduled with one of these algorithms, then it cannot be scheduled with any algorithm. The schedulable bound in each of these cases is 100%. Thus, as long as total utilization is less than 100%, then task set is schedulable. As an example, consider the task set in Case 3, that was not schedulable using a fixed-priority scheduling algorithm. In Case 4, we see that the task set is indeed schedulable when using EDF.

Advantages/Disadvantages of Fixed and Dynamic Scheduling

Rate Monotonic Algorithm

Advantage: A critical set can be specified, thus tasks can be selectively chosen during a transient overload

Disadvantage: Worst case schedulable bound is 69% (average case 88%)

Disadvantage: Deadline Failures are difficult to detect

Earliest Deadline First and Minimum-Laxity First:

Advantage: Schedulable bound is 100%

Advantage: Deadline Failures can be detected

Disadvantage: Cannot specify a critical task set, thus no control of which tasks fail during a transient overload

Disadvantage: Require more overhead during a reschedule

There also exist mixed-priority scheduling algorithms, that combine some of the advantages of the fixed and mixed priority algorithms.

Communication and Synchronization

As with processes in non-real-time systems, real-time tasks must often share resources, using the same mechanisms, such as shared memory, semaphores, messages, and locks. Sometimes, a real-time task must block until the shared resource is available. What happens if a high-priority process needs the resource immediately in order to not miss a deadline, but a lower-priority process is holding the resource?

We define Priority Inversion as the blocking of a high priority task due to a lower priority task locking a shared resource. For example, See Example of Priority Inversion illustrates the priority version problem. The task set consists of 3 tasks:

• PH: A high priority task
• PM: A medium priority task
• PL: A low priority task

For this example, we are not concerned with their period or execution time.

Assume a resource R1 shared between PH and PL, and PL acquires the resource first.

There have been many solutions proposed for addressing problems such as priority inversion. For example:

• Priority Inheritance Protocol
• Lower priority tasks inherit higher priority when holding a shared resource
• Priority Ceiling Protocol
• Maximum blocking time can be predetermined
• Used mostly with fixed priority scheduling
• Deadlock free
• Resource scheduling
• Schedule resources as well as tasks
• Various algorithms proposed
• Often used in client/server environments.
• Prioritized Message Passing
• Higher priority messages are treated first
• Messages can specify maximum response time

See Priority inheritance protocol for solving priority inversion problem illustrates the priority inheritance solution to the priority inversion problem. Although this solution has some merits, it is usually used because the method is deadlock-prone, and it is difficult to analyze since the number of times a task can be preempted due to resource usage is not bounded.

A better solution is the priority ceiling protocol. Theoretically it provides the desired result. In practice, however, it is expensive to implement, as significant setup time and overhead is required.