Scheduling Policies

Terminology

Long term scheduling -- decides which jobs to start next. Most relevant in context of batch systems with spooling.

Medium-term scheduling -- decides which processes to block temporarily when resources are overcommitted or unavailable.

Short-term scheduling -- decides how to share the computer among the processes that are ready to run. Refer back to picture of processes.

Tanenbaum talks about two-level scheduling where the lowest level are for jobs in memory and upper level are for jobs not in memory. Not the same as the three-level scheme above.

The importance of each type of scheduler depends on the type of jobs being serviced.

We will concentrate on short-term scheduling. How to select among a set of ready processes.

Distinguish between a short and long process. Based on the time a process runs when it gets the CPU. An I/O bound process is short and a CPU bound process is long.

Note; The idea of short vs. long is determined by how much of its time slice that a process uses, not the total amount of time it executes.

Criteria

Criteria for a good scheduling algorithm:

They are competing. Fairness/efficiency, interactive/batch

Measurements

In order to compare different short-term policies, we need a measure of performance. Assume that a process needs t time in execution before it leaves the ready list:

execution time (t)
-- execution time
response time (T)
-- finish time - arrival time. (wall clock time)
missed time (M)
-- T - t; time spend on the ready list or in blocked state.
penalty ratio (P)
-- T/t; penalty of 1 ideal (lower penalty is good)
response ratio (R)
-- t/T; response of 1 ideal (higher response is good)

Other useful measures:

First Come, First served (FCFS)

Also called FIFO. CPU services processes in the order they arrive. Processes run until they give up the CPU. If the policy is non-preemptive, a process is never blocked until it voluntarily gives up the CPU.

Non-preemptive policies resist change.

Advantages:

Disadvantages:

Round Robin (RR)

CPU services a process for only a single quantum of time, q, before moving on to the next process. A quantum is usually 1/60 to 1 second.

The quantum q acts as a parameter that can be tuned. Long quantums result in FCFS. Short quantums result in an approximation of processor sharing, in which every process thinks it is getting constant service from a processor that is slower proportionally to the number of processes.

RR achieves a good penalty ratio by preempting processes that are monopolizing the CPU.

Is there a limit as to how small can we make the quantum value?

Note: we always start the job with a full time quantum, regardless of how long it took of the last quantum.

Shortest Process Next (SPN)

Preemption is relatively expensive. SPN attempts to avoid that cost.

The SPN policy always selects the shortest job for servicing.

Of course, we can't know absolutely how long a job will take! However, its recent behavior is likely to be a good approximation. For instance, one might compute an exponential average:

$E_{smooth} = \alpha E_{smooth} + (1 - \alpha) E_{measured}$

$E_{measured}$ is how long a process runs when it gets a chance.

$\alpha$ is called the smoothing (aging) factor and may be set higher or lower to make the estimate less or more responsive to change.

Unfortunately, SPN may lead to starvation, a condition where some processes are never serviced.

In Unix, the command uptime uses an exponential decay to compute the average number of jobs in the run queue over the last 1, 5, and 15 minutes. For example: 

% uptime
  1:02pm  up 18 days,  2:02,  4 users,
      load average: 0.48, 0.26, 0.03
%

Preemptive Shortest Process Next (PSPN)

Combine preemption of round robin (RR) with shortest process next (SPN).

PSPN preempts the current process when another process is available with a total service requirement less than the remaining service time required by the current process.

Multiple-level Feedback (FB)

Maintain multiple queues, with lower numbered queues having highest priority. When a process has used a certain quanta in its queue, the scheduler moves it to another queue.

Use Round Robin policy within each queue to select a process of the highest priority.

Interactive processes have priority over longer ones, because long process migrate to lower priority queues. Give larger quanta to lower-priority.

Side note: CTSS system 1962, Policy that switched from CPU to interactive bound. Users found that it helped priority for long jobs to give keystrokes! Primitive way to detect I/O bound jobs.

Many additional policies exist.

Evaluating Policies

Mathematical Analysis involves a mathematical formulation of the policy and a derivation of its behavior.

Queueing networks model the system as a set of queues to servers (e.g. CPU, I/O devices, etc.).

  1. each server has an average service time

  2. processes move from one queue to another according to probabilities that describe the breakdown of time spent at each server

The primary drawback of mathematical analysis is that the model is only an approximation to the actual system, and complex systems are often impossible to solve.

Simulation involves tracking a large number of processes through a model and collecting statistics.

Process execution can be driven by probabilities (as in mathematical analysis) or by actual trace data.

Experimentation is the ``best'' method, because it measures the real system. Unfortunately, because the system tested must be built, experimentation is usually expensive.

Linux Process Scheduling

Two classes of processes:

Always run real-time processes above normal. It uses priorities with either a FIFO or round-robin policy.

Normal process scheduling uses a prioritized, preemptive, credit-based policy:

Windows NT Scheduling

Windows NT uses threads as the basic scheduling unit. Windows NT threads have priorities and can be preempted (not always true for threads). Will look more at threads later.

Guidelines