CPU Scheduling


What is Scheduling?

Typical Goals of Good Scheduling

Can you define one or more precise measures for each of these qualities?

Types of Scheduling

Time FrameDetermines
Long-term (system) which processes are admitted to the system
(process creation)
Medium-term (memory) which processes are in real memory (fully or partially)
(swapping, suspension, load control)
Short-term (cpu) which process is currently executed by the processor(s)
I/O which process's request is handled by each available I/O device

Scheduling and Process State Transition

Levels of Scheduling

Long-Term Scheduling

Medium-Term Scheduling

Short-Term Scheduling

Two Dimensions of Short-Term Scheduling Criteria

User vs. System Orientation

Performance vs. Non-performance Orientation

For each of the two pairs of criteria, improvement in one generally comes at the cost of degradation of the other. Can you argue why this is so, in each case?

Scheduling Criteria

Can you define each of these?

Can you argue the importance of each, identifing circumstances under which it is important?

Can you explain how some are in conflict with one another?

Long, Medium and Short-Term Queue Structures


Priority Queuing

Decision Mode: When does the dispatcher execute?

Most scheduling algorithms can be applied in both preemptive and nonpreemptive modes.

Preemptive scheduling allows for fairer service (if that is desired) since any one process cannot monopolize the processor for very long.

It is also critical for real-time systems, since response to an external event may require a different process to run immediately.

Process Scheduling Example


Review: What is the difference between and IO-bound process and a CPU-bound process?

Round-Robin Time Slicing

The term round-robin applies to the way processes are moved around to the tail of the ready queue. The term time slicing refers to the way each process is limited to executing one quantum of CPU time before it is preempted.

Shortest Process Next

When we apply the shortes process next in a preemptive scheduling environment, it becomes the shortest remaining processing time next algorithm.

SPTF Minimizes Average Response Time

There is a very simple "picture proof" that shortest-processing-time-first (SPTF) minimizes average response time. This is not a serious proof, but it captures the core idea that can be used to construct a more formal proof.

Suppose two schedules differ only in the order in which two jobs are executed. In the first schedule, the longer job is executed first. In the second, the order of the two jobs is swapped, so the shorter job executes first. Look at the figures. The average response time is equal to the area beneath the step-shaped curve, divided by the number of jobs. It is clear that in the second figure (the one with the shorter job first) the area beneath the curve is smaller, so the average response time must be smaller.

By induction on the number of pairs of jobs that are out of order, we can show that the schedule with the shortest average response time is the one in which the jobs are executed in increasing order of execution time.

This proof considers only the simple case where all the jobs are initially ready to run at the same time. The same argument can be generalized for systems with asychronous job arrivals and preemptive scheduling, to show that shortest-remaining-processing-time-first minimizes average response time.

How to Tell which Process is Shortest?

With CPU scheduling as with the page replacement, if we cannot predict the future with certainty we are forced to do the best we can by extrapolating from the past. (Again, as with page references, there are some specialized systems where the length of execution time bursts may predicable, but for general-purpose operating systems, we must do without that information.)

By the way, it is important to notice that the page replacement strategy affects CPU scheduling. For example, giving a process high priority in CPU scheduling may not help it much if the process does not get some preference for having its pages stay in main memory. This principle -- of consistency in policies for allocating different resources -- is very important in real-time systems.

Averaging Process Execution "Burst" Times

Sn+1 = 1/n Tn + (1 - 1/n)Sn

We can try approximating the future behavior using the average execution burst time for each process, but this tends to not give enough weight to recent behavior.

Can you see why this is true?

Exponential Averaging

Sn+1 = aTn + (1 - a)Sn

The exponential averaging technique gives more weight to the more recent execution burst times. The parameter a controls how much weight is given to the past. The smaller it is the faster the exponential average responds to changes in the process behavior. The value of a must be tuned.

Shortest Remaining Time

Highest Response Ratio Next (HRRN)

R = response ratio = (w + s) / s
w = time spent waiting for the processor
s = expected service time

Another way of looking at R is as the normalized response time.

R can be no lower than 1, which occurs when the process does not need to wait at all.

Highest Response Ratio Next (HRRN) Example


Feedback Example

Feedback with Aging

Fair-Share Scheduling

Traditional UNIX Scheduling

CPUj(i) = CPUj(i-1) /2
Pj(i) = Basej + CPUj(i-1) /2 + nicej

CPUj(i) = processor utilization by process j through interval i

Pj(i) = priority of process j at beginning of interval i (lower value means higher priority)

Basej = base priority of process j

nicej = user-controllable adjustment factor


The Linux Kernel Scheduler

You should look at the code of the Linux kernel scheduler to see what a real dispatcher looks like.

© 2002 T. P. Baker & Florida State University. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means without written permission. (Last updated by $Author: cop4610 $ on $Date: 2002/09/26 20:06:06 $.)