CPU Scheduling

Basic Concept

Maximum CPU utilization is obtained with multiprogramming

CPU-I/O Burst Cycle: Process execution consists of a cycle of CPU execution and I/O wait.

CPU burst followed by I/O burst.
CPU burst distribution is of main concern.

Scheduling

Two Levels:

Long Term: Decides when process should enter reader state and start competing for CPU
Short Term: Decides which of the ready processes should run next.

Non-Preemptive / Cooperative: CPU scheduling decisions that take place when a process:

Switches from running to waiting (e.g., hits I/O)
Terminates

Preemptive: CPU scheduling decisions that take place when a process:

Switching from running to ready (e.g., time slice expires)
Switched from waiting to ready

(All other scheduling.)

Issues with Preemption:

Access to shared data
Preemption while in kernel mode
Interrupts occurring during crucial OS activities.

Example: Data Racing

Suppose two processes, p2 and p1, which are a producer and consumer.

What if p2 is mid-generation of data when execution switches to p1?

Operating systems must be able to handle preemption to have processes with higher priority and prevent data racing.

Scheduling Algorithms

Non-Preemptive: Once a CPU-burst starts it must run to completion and cannot be interrupted.

First Come First Serve (FCFS)
Shortest Job First (SJF)
Priority

Preemptive: A running process can be interrupted when (1) a higher-priority process arrives, or (2) its time slice expires.

Round Robin (RR)
Shortest Remaining Time First (SRT / Preemptive SJF)
Preemptive Priority

Dispatcher

Dispatcher: Gives control of CPU to the process selected by the short-term scheduler. This involves:

Switching context
Switching to user mode
Jumping to proper location in user program to restore it.

Dispatch latency: Time it takes for dispatcher to stop one process and start another.

Scheduling Criteria

CPU Utilization: How much the CPU is kept busy.

Throughput: # of processes that complete their execution per time unit

Turnaround Time: Amount of time to execute a particular process.

Burst + Wait

Waiting Time: Amount of time a process has been waiting in the ready queue.

Response Time: Amount of time it takes from when a request was submitted until the first response is produced, not output.

Wait = Response when non-preemptive.

Scheduling Algorithm Optimization Criteria

Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time
- We usually optimize the average mean.

FCFS

Example: Non-Preemptive FCFS

Process	Arrive Time	Burst Time
P_1	0	24
P_2	0	3
P_3	0	3

TODO Draw Gantt chart

Waiting time for P_1 = 0, P_2 = 24, P_3 = 27

Average Waiting Time: (0+24+27)/3 = 17
Average Response Time: (Same as waiting time, because preemptive)
Average Turnaround Time: (24+27+30)/3 = 27
Average Process Time: (24+3+3)/3 = 10

We can see that waiting time = response time.

Example: Non-Preemptive FCFS

Process	Arrive Time	Burst Time
P_1	0	8
P_2	0.4	4
P_3	1	1

TODO Draw Gantt chart

Average Waiting Time: TODO
Average Response Time: TODO
Average Turnaround Time: TODO
Average Process Time: TODO

Shorted Job First (SJF)

Associate each process with the length of its execution time.

This yields the minimum average response time, but can starve long-running jobs.

Two Schemes:

Non-Preemptive: Once CPU starts, it cannot be stopped until it completes its quota.
Preemptive: If a new process arrives with less work than the remaining time of the currently executing process, preempt.

Difficulty: It’s hard to get next process length
Can predict with exponential averaging, or ask user to provide length.

Example: Non-Preemptive SJF

Suppose all these processes arrive at time 0.

Process Time	Burst Time
P_1	6
P_2	8
P_3	7
P_4	3

SJF will schedule the shortest burst-time processes first: P_4, P_1, P_3, P_2

TODO Gantt Chart

Note: ART = AWT IIF non-preemptive (we do every process in single blocks, no interruptions) TODO ^ Stop repeating myself and just say ART = AWT with reasoning in a single good location, rather than lightly rehashing in random places like this.

Average Waiting Time: TODO
Average Turnaround Time: TODO
Average Process Time: TODO

Example: Non-Preemptive SJF

Process Time	Arrive Time	Burst Time
P_1	0	8
P_2	0.4	4
P_3	1	1

TODO Gantt Chart

Average Waiting Time: (0+7+8.6)/3 = 5.2
Average Turnaround Time: (8+8+12.6)/3 = 9.53
Average Process Time: (8+4+1)/3 = 4.33

Example: Preemptive SJF (SRT)

Preemptive SJF is called shortest-remaining-time-first.

Process	Arrival Time	Burst Time
P_1	0	8
P_2	1	4
P_3	2	9
P_4	3	5

TODO Gantt Chart

Average Waiting Time: (9+0+15+2)/4 = 6.5
Average Response Time: (0+0+15+2)/4 = 4.25
Average Turnaround Time: (17+4+24+7)/4 = 13
Average Process Time: (8+4+9+5)/4 = 6.5

SJF Prediction Formula

For long term scheduling, total CPU time is measured between process creation and destruction

For short term, CPU burst changes for each arrival / departure period.

We use exponential averaging to predict future CPU bursts

\boxed{ S_{n+1} + \alpha T_n + ( 1 - \alpha ) S_n } \\~\\ \small \textit{where $S_n$ is last estimate of CPU time,} \\ \textit{$T_n$ is last observed CPU time, and} \\ \textit{$\alpha$: controls relative weight of $T_n$ v.s. $S_n$}

Note — \alpha is commonly 0.5

More on \alpha:
Big alpha makes predictions adapt quickly, but follow outliers.
Small alpha makes predictions adapt slowly, but ignore outliers.

Priority Scheduler

CPU allocated to process with highest priority.

A priority number is associated with each process (smaller number = higher priority)
Can be preemptive or non-preemptive.
Processes undergo aging.

On Aging:
Aging: To prevent starvation of low priority processes, where processes gain priority over time.

Note — SJF is actually an example of priority scheduling where priority is determined by predicted CPU burst time!

Example: Non-Preemptive Priority

Assume all arrived at time 0.

Process	Priority	Burst Time
P_1	3	8
P_2	1	4
P_3	4	9
P_4	2	5

TODO Gantt chart

Average Waiting Time: (9+0+17+4)/4 = 7.5
Average Turnaround Time: (17+4+26+9)/4 = 14
Average Process Time: (8+4+9+5)/4 = 6.5

Example: Non-Preemptive Priority

Assume all arrived at time 0.

Process	Priority	Burst Time
P_1	3	10
P_2	1	2
P_3	4	1
P_4	5	5
P_5	2	3

TODO Gantt chart

Average Waiting Time: (5+0+15+16+2)/5 = 7.6
Average Turnaround Time: (15+2+16+21+5)/5 = 11.8
Average Process Time: (10+2+1+5+2)/5 = 4.2

Example: Preemptive Priority

Process	Arrival Time	Priority	Burst Time
P_1	0	3	10
P_2	4	1	2
P_3	2	4	1
P_4	6	5	5
P_5	3	2	3

TODO Gantt chart

Average Waiting Time: (5+0+13+10+2)/5 = 6
Average Response Time: (0+0+13+10+0)/5 = 4.6
Average Turnaround Time: (15+2+14+15+5)/5 = 10.2
Average Process Time: (10+2+1+5+3)/5 = 4.2

Round Robin

Each process gets a small unit of CPU time (time quantum q). After the quantum elapses, the process as preempted and added to the end of the ready queue.

If there are n processes in the ready queue, each process gets 1/n of the CPU time in chunks of at most q time units at once, and no process waits more than (n-1)q time units.

More on Quantum — q is typically 10—100 ms.
q must be large with respect to context switch, otherwise overhead is too high.
But, a q that is too big will just result in FIFO behavior.

Note — Typically yields higher average turnaround than SJF, but better response time.
The turnaround time varies with the time quantum. (The best turnaround times occur when 80% of CPU bursts are shorter than q)

Example: Round Robin

Let q = 4

Process	Burst Time
P_1	24
P_2	3
P_3	3

TODO Gantt Chart

Average Waiting Time: (6+4+7)/3 = 5.67
Average Response Time: (0+4+7)/3 = 3.67
Average Turnaround Time: (30+7+10)/3 = 15.67
Average Process Time: (24+3+3)/3 = 10

Example: Round Robin

Let q = 6

Process	Burst Time
p_1	24
p_2	3
p_3	3

TODO Gantt Chart

Average Waiting Time: (6+6+9)/3 = 7
Average Response Time: (0+6+9)/3 = 5
Average Turnaround Time: (30+9+12)/3 = 17
Average Process Time: (24+3+3)/3 = 10

Multilevel Scheduling

Multilevel scheduling maintains a separate queue of process at each priority level, and within each level, processes are scheduled using round-robin.

We could use aging to prevent starvation.

Multilevel Feedback

Similar to multilevel scheduling, but addresses starvation and fairness by:

Using a different time quantum at each priority level
TODO

If a process takes too long, we lower the priority, which increases the quantum.