Transcript lecture notes

Rensselaer Polytechnic Institute
CSCI-4210 – Operating Systems
David Goldschmidt, Ph.D.

The short-term scheduler decides which
process the CPU executes next

The dispatcher gives control of the CPU to
the process selected by the CPU scheduler:
 Performs context switch
 Switches to user mode
 Jumps to the proper location in the user
program to resume program execution
the dispatcher operates here

CPU scheduling requires an algorithm to
determine which process to dispatch next

Scheduling algorithms include:
 First-Come, First-Served (FCFS)
 Shortest-Job-First (SJF)
 Round-Robin (RR)
 Priority
 Multilevel Queue (MQ)

Preemptive scheduling preempts a running
process before its
time slice expires
process
process
process
process
 Or it preempts a process
because its time slice has expired

Non-preemptive scheduling gives a process
exclusive uninterrupted access to the CPU
for the entirety of its execution

Compare scheduling algorithms by measuring
 CPU utilization – keep CPU as busy as possible
 Throughput – maximize the number of processes
that complete their execution per unit time
 Turnaround time – minimize the elapsed time to
fully execute a particular process
 Waiting time – minimize the elapsed time a
process waits in the ready queue

FCFS dispatches processes
in the order they enter
the ready queue
Process
CPU Burst Time
P1
24 ms
P2
3 ms
P3
3 ms
 FCFS is non-preemptive
P1
P2
0
24
time
P3
27
30

SJF dispatches processes by
selecting the process with
the lowest CPU burst time
Process
CPU Burst Time
P1
24 ms
P2
3 ms
P3
3 ms
 SJF is non-preemptive (and predictive)
P2
0
P3
3
P1
6
30
time

Same as SJF, but a
new process may
preempt the
running process
P1
0
P2
2
P3
4
Process
Arrival Time
CPU Burst Time
P1
0
7 ms
P2
2 ms
4 ms
P3
4 ms
1 ms
P4
5 ms
4 ms
P2
5
P4
7
time
P1
11
16

SJF is the optimal solution
 The problem with SJF is the inability to
predict required CPU burst times
 Apply a prediction algorithm that uses
previous CPU burst times
 Algorithm uses exponential averaging:
▪ tn = actual length of the nth CPU burst
▪ τn+1 = predicted value for the next CPU burst
▪ τn+1 = α tn + (1 – α) τn , where 0 < α < 1

RR is a preemptive algorithm
that gives all ready processes
a fair time slice of CPU time
Process
CPU Burst Time
P1
6 ms
P2
2 ms
P3
5 ms
 Using a time slice of 2 ms....
P1
0
P2
2
P3
4
P1
6
time
P3
8
P1
10
P3
12 13

Associate a priority number with each process
 The dispatcher selects the process
with the highest priority
 For multiple ready processes with
identical priority numbers, use FCFS
 Key problem is starvation
▪ Overcome starvation by aging, increasing
the priority of a process as it ages

Is priority scheduling preemptive
or non-preemptive?
process
 Non-preemptive priority scheduling places
higher-priority processes at the head of the
queue
 Preemptive priority scheduling requires a
running process to be interrupted and
preempted upon the arrival of a higher-priority
process
(use this one for Project #1)

Operating systems that support priority
schemes are often called multiclass systems
use a separate scheduling
algorithm for each queue

Assign processes to multiple queues,
each with its own scheduling algorithm

Dynamically assign processes to multiple
queues based on actual CPU burst times
 i.e. feedback
quantum is synonymous
with time slice

Apply the FCFS, SJF, RR, and Preemptive
Priority scheduling algorithms to this table:
Process
Arrival Time
CPU Burst Time
Priority
P1
0
45 ms
5
P2
0
5 ms
3
P3
20 ms
15 ms
1
P4
60 ms
25 ms
2
 For RR, use a time slice of 10 ms
lower number indicates
a higher priority
recalculate using
context switch
time tcs = 20 μs
 Calculate the wait and turnaround times of
each process, as well as overall averages