Skip to content

Latest commit

 

History

History
383 lines (307 loc) · 11.8 KB

05.md

File metadata and controls

383 lines (307 loc) · 11.8 KB
title
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:

  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.

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:

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