CPU Scheduling

What is Scheduling?

• determining when each process/thread gets to to execute
• includes allocation of CPU (dispatching)
• may also include allocation of other resources needed for execution:
  • memory (see Load Control in Chapter 8)
  • mutexes, other resource locks

Typical Goals of Good Scheduling

• Response time
• Throughput
• Processor efficiency

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

Types of Scheduling

Scheduling and Process State Transition

Levels of Scheduling

Long-Term Scheduling

• Determines which programs are admitted to the system for processing
• Controls the degree of multiprogramming
• More processes => smaller percentage of time each process is executed

Medium-Term Scheduling

• Part of the swapping function
• Based on the need to manage the degree of multiprogramming
• More processes => more chance of thrashing
• Fewer processes => more chance of idle CPU

Short-Term Scheduling

• Done by module called the dispatcher
• Executes most frequently
• Invoked when an event occurs that may required a different process to execute:
• Clock interrupts (maybe wake up sleeping process, or end time slice)
• I/O interrupts (maybe wake up process waiting for I/O to complete)
• Operating system calls (maybe block process, unblock another process)
• Signals (maybe kill, suspend, wake up processes)

Two Dimensions of Short-Term Scheduling Criteria

User vs. System Orientation

• User: response time (elapsed time between the submission of a request until there is output)
• System: effective and efficient utilization of the processor

Performance vs. Non-performance Orientation

• Performance: quantitative, measurable (e.g., response time and throughput)
• Non-performance: qualitative (e.g., predictability, determinism)

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

• Turnaround time - submission to completion
• Response time - submission until start of response
• Deadlines
• Predictability
• Throughput - processes completed per unit time (*)
• Processor utilization - % of time CPU is working
• Fairness
• Enforcing priorities
• Balancing utilization of all resources

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

Priorities

• Scheduler will always choose a process of higher priority over one of lower priority
• Have multiple ready queues to represent each level of priority
• Lower-priority may suffer starvation
• this is OK in a real-time system
• for others, we can dynamically adjust priorities based on age or execution history

Priority Queuing

Decision Mode: When does the dispatcher execute?

• Nonpreemptive: running process continues until it terminates or blocks itself, e.g. for I/O
• Preemptive: running process may be interrupted and execution switched to a different process, by the operating system

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

First-Come-First-Served

• Each process joins the Ready queue (at the tail) when it arrives or wakes up
• When the current process ceases to execute, the oldest process in the Ready queue is selected
• A short process may have to wait a very long time before it can execute
• Favors CPU-bound processes
• I/O-bound processes have to wait until CPU-bound process completes

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

Round-Robin Time Slicing

• Uses preemption based on a clock
• An amount of time (quantum) is determined that allows each process to use the processor for that length of time
• Clock interrupt is generated at periodic intervals
• When an interrupt occurs, the currently running process is placed at the tail of the ready queue, and the next ready job is selected

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

• Nonpreemptive policy
• Process with shortest expected processing time is selected next
• Short process jumps ahead of longer processes
• Predictability of longer processes is reduced
• If estimated time for process not correct, the operating system may abort it
• Possibility of starvation for longer processes

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?

• Execution times are not known in advance
• Most processes do not execute from beginning to end, without stopping
• They alternate between bursts of execution and periods of blocking, e.g., for I/O
• Lengths of bursts of execution are not known in advance
• Try using history to predict the future

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

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

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

• Preemptive version of shortest process next policy
• Must estimate processing time

Highest Response Ratio Next (HRRN)

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

• Choose next process with the lowest ratio
• (time spent waiting + expected service time) / 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

• Penalize jobs that have been running longer
• Don't know remaining time process needs to execute

Feedback Example

Feedback with Aging

• Allow processes that feedback scheme has kicked down in priority to move back up over time
• Recognizes that processes can go through different phases that are compute or I/O bound
• Helps prevent complete starvation of longer processes.

Fair-Share Scheduling

• User's application runs as a collection of processes (or threads)
• User is concerned about the performance of the group, as a whole
• Need to make scheduling decisions based on process sets

Traditional UNIX Scheduling

• Multilevel feedback using round robin within each of the priority queues
• Priorities are recomputed once per second
• Base priority divides all processes into fixed bands of priority levels
• Adjustment factor used to keep process in its assigned band

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

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

Base_j = base priority of process j

nice_j = user-controllable adjustment factor

Bands

• Decreasing order of priority
• Swapper
• Block I/O device control
• File manipulation
• Character I/O device control
• User processes

The Linux Kernel Scheduler

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