Scheduling Policies

SCHEDULING POLICIES

PRIORITY-BASEDSCHEDULING

Now that we have a priority as context switching mechanism, we have to determine an algorithm by which to assign n priorities to processes. After assigning priorities, the OS takes care of the rest by choosing the highest-priority ready process. There are two major ways to assign priorities: static priorities that do not change during execution and dynamic priorities that do change. We will look at examples of each in this section.

1 Rate-Monotonic Scheduling

Rate-monotonic scheduling(RMS), introduced by Liu and Lay land[Liu73], was one of the first

scheduling policies developed for real-time systems and is still very widely used. RMS is a static

scheduling policy. It turns out that these fixed priorities are sufficient to efficiently schedule the processes in many situations.

The theory underlying RMS is known as rate-monotonic analysis(RMA). This theory, as summarized below, uses a relatively simple model of the system.

■All processes run periodically on a single CPU.

■Context switching time is ignored.

■There are no data dependencies between processes.

■The execution time for a process is constant.

■All deadlines are at the ends of their periods.

■The highest-priority ready process is always selected for execution.

The major result of RMAs that a relatively simple scheduling policy is optimal under certain conditions. Priorities are assigned by rank order of period, with the process with the shortest period being assigned the highest priority. This fixed-priority scheduling policy is the optimum assignment of static priorities to processes, in that it provides the highest CPU utilization while ensuring that all processes meet their deadlines. Example6.3 illustrates RMS.

If, on the other hand, we give higher priority to P2, the n critical-instant analysis tells us that we must execute all of P2 and all of P1 in one of P1’s periods in the worst case:

T1  T2    1.

There are cases where the first relationship can be satisfied and the second cannot, but there are no cases where the second relationship can be satisfied and the first cannot. We can inductively show that the process with the shorter period should always be given higher priority for process sets of arbitrary size. It is also possible to prove that RMS always provides a feasible schedule if such a schedule exists.

The bad news is that, although RMS is the optimal static-priority schedule, it does not always allow the system to use 100% of the available CPU cycles. In the RMS frame work, the total CPU utilization for a set of n tasks is the fraction Ti/ I is the fraction of time that the CPU spends executing task i.

It is possible to show that for a set of two tasks under RMS scheduling, the CPU utilization U

will be no greater than 2(21/2  1)∼ 0.83. In other words, the CPU will be idle at least 17% of

the time. This idle time is due to the fact that priorities are assigned statically; we see in the next section that more aggressive scheduling.

2 Earliest-Deadline-First Scheduling

Earliest deadline first(EDF) is another well-known scheduling policy that was also studied by Liu and Lay land[Liu73]. It is a dynamic priority scheme—it changes process priorities during execution based on initiation times. As a result, it can achieve higher CPU utilizations than RMS. The EDF policy is also very simple: It assigns priorities in order of deadline. The highest-priority process is the one whose deadline is nearest in time, and the lowest- priority process is the one whose deadline is farthest away. Clearly, priorities must be recalculated at every completion of a process. However, the final step of the OS during the scheduling procedure is the same as for

RMS— the highest-priority ready process is chosen for execution.

Example6.4 illustrates EDF scheduling in practice. In some applications, it may be acceptable for some processes to occasionally miss deadlines. For example, a set-top box for video decoding is not a safety-critical application, and the occasional display artifacts caused by missing deadlines may be acceptable in some markets. What if your set of processes is un schedulable and you need to guarantee that they complete their deadlines? There are several possible ways to solve this problem:

■Get a faster CPU. That will reduce execution times with out changing the periods, giving you lower utilization. This will require you to redesign the hardware, but this is often feasible because you are rarely using the fastest CPU available.

■  Redesign the processes to take less execution time. This requires knowledge of the code and may or may not be possible.

■  Rewrite the specification to change the deadlines. This is un likely to be feasible, but may be in a few cases where some of the deadlines were initially made tighter than necessary.