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:

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

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

1. Switching from running to ready (e.g., time slice expires)
2. 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.

Example:

Q: A non-preemptive algorithm makes a scheduling decision whenever… (True/False)

1. New process arrives in the RL

2. Process changes from blocked to ready

3. process requests an

4. New process arrives in RL

Scheduling Algorithms

Non-Preemptive: Once a CPU-burst is started, the CPU cannot be interrupted until the CPU burst has been completed.

• FCFS
• SJF
• Priority

Preemptive: TODO

• Round Robin
• SRT
• TODO

We use a Gantt chart

Dispatcher

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

• 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 CPU is kept busy.

Throughput: # of processes completing 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 = Reponse 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 1: Calculating AWT, ATT, APT

TODO Gantt Chart

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

Average Waiting Time:

Average Turnaround Time:

Average Process Time:

We can see that waiting time = response time.

Example 2: Calculating AWT, ATT, APT

Example: Convoy Effect

Suppose we get these three processes:

If we order the processes on the ready line as P_2, P_3, P_1; we get

Waiting time for P_1 = 6, $P_2 = 0, $P_3 = 3

Average Waiting Time:

Average Turnaround Time:

Average Process Time:

Convoy Effect: Short processes behind long processes.

This is the basis of SJF

Shorted Job First (SJF)

Associate each process with the lenght of its execution time.

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

Two Schemes:

1. Non-Preemptive: Once CPU starts, it cannot be stopped until it completes its quota.
2. 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 1: Non-Preemptive SJF

All processes arrive at time 0.

SJF will pick the lowest burst-time processes, scheduling: 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)

Prediction Formula

For long term scheudling, total CPU measrues betwene process creatio nand destruction

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

• We use exponential averaging to predict future CPU time

\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.

Example: Applying Prediction Formula TODO

Predict S_3 based on following TODO

Priority Scheduler

CPU allocated to process with highest priority.

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

On Aging:

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

SJF is actually an example of priority scheduling where priority is determined by predicted CPU burst time.

TODO Non-preemptive scheduler