Lecture 4

Scheduling
Algorithms
 Context switching

• A context switch is the computing process of storing and restoring

the state (context) of a CPU so that execution can be resumed from
the same point later.

• This enables multiple processes to share a single CPU.

• The context switch is an essential feature of a multitasking operating

system.

• Operating systems designer try to optimize the use of context

switches.
 Context switching
• The following steps are needed for a context switch to occur:
• Save the values of the program counter, registers, stack pointer.
• Change the state of the process in the PCB from running state to blocked
state.
• Update the various times for process accounting information.
• Select a new process for execution.
• Update the state field in its PCB to running.
• Update memory management related information.
• Change the context of the CPU to the new process by loading the values of
program counter and registers that were saved earlier.

• Context switching is a costly operation.

• Choose the time slice wisely.
• context switch time = T – (SUM for all processes (waiting time +
execution time))
CPU Switch From Process to Process
 Process Scheduling

• Maximize CPU use, quickly switch processes onto CPU for

time sharing.

• Process scheduler selects among available processes for

next execution on CPU.

• Maintains scheduling queues of processes

• Job queue – set of all processes in the system
• Ready queue – set of all processes residing in main memory, ready
and waiting to execute
• Device queues – set of processes waiting for an I/O device

Processes migrate among the various queues

Representation of Process Scheduling

Queueing diagram represents queues, resources, flows

 Schedulers
• Long-term scheduler (or job scheduler) – selects which
processes should be brought into the ready queue.
• Short-term scheduler (or CPU scheduler) – selects which
process should be executed next and allocates CPU.
• Sometimes the only scheduler in a system
• Short-term scheduler is invoked very frequently (milliseconds)
 (must be fast)

• Long-term scheduler is invoked very infrequently (seconds,

minutes)  (may be slow)

• The long-term scheduler controls the degree of

multiprogramming
 Schedulers
• Types of process scheduling:

• Preemptive
• Can be taken out from the processor after the time slice gets
expire.

• Non-preemptive
• Can’t be taken out unless it completes its execution
 Scheduling Algorism Criteria (5)
• CPU utilization – keep the CPU as busy as possible.
(Optimization Max)
• Throughput – # of processes that complete their execution per
time unit.
Optimization Max
• Turnaround time – amount of time to execute a particular process
Optimization Min
• Waiting time – amount of time a process has been waiting in the
ready queue
Optimization Min
• Response time – amount of time it takes from when a request was
submitted until the first response is produced, not output (for
time-sharing environment).
Optimization Min
First-Come First-Served (FCFS) Scheduling Alg. Or (FIFO)

Process Burst Time

P1 24
P2 3
P3 3
• Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:

P1 P2 P3

0 24 27 30

• Waiting time for P1 = 0; P2 = 24; P3 = 27

• Average waiting time: (0 + 24 + 27)/3 = 17
 FCFS Scheduling (Cont.)

Suppose that the processes arrive in the order:

P2 , P3 , P1
• The Gantt chart for the schedule is:
P2 P3 P1

0 3 6 30

• Waiting time for P1 = 6; P2 = 0; P3 = 3

• Average waiting time: (6 + 0 + 3)/3 = 3
• Much better than previous case
• Convoy effect - short process behind long process.
Shortest-Job-First (SJF) Scheduling
• Associate with each process the length of its next CPU burst
• Use these lengths to schedule the process with the shortest time

• SJF is optimal – gives minimum average waiting time for a given

set of processes.

• The longer processes may starve if there is a steady supply of

shorter processes.
Example of SJF

ProcessTime Burst Time

P1 0.0 6
P2 2.0 8
P3 4.0 7
P4 5.0 3
• SJF scheduling chart

P4 P1 P3 P2

0 3 9 16 24

• Average waiting time = (0+3 + 9 + 16) / 4 = 7

 Exercise (SJF)
Process Execution Time

P1 7

P2 8

P3 4

P4 3

P4 P3 P1 P2

0 7 14 22
3

Average waiting time = (0+ 3 +7 + 14 ) / 4 = 6

 Shortest Remaining Time First (SRF)

• The preemptive version of SJF.

• Calculate the remaining execution time for each process

• Schedule the process with the minimum remaining time

• Like SJF, longer processes can starve in SRT algorithm

 Example of Shortest-remaining-time-first

• Now we add the concepts of varying arrival times and preemption to the
analysis

ProcessA arri Arrival TimeT Burst Time

P1 0 8
P2 1 4
P3 2 9
P4 3 5
• Preemptive SJF Gantt Chart

P1 P2 P4 P1 P3

0 1 5 10 17 26

• Average waiting time = [(10-1)+(1-1)+(17-2)+(5-3)]/4 = 26/4 = 6.5 msec

Exercise (SRF)
Process Arrival Time Execution Time

P1 0 7

P2 1 3

P3 2 8

P4 3 4

P1 P2 P4 P1 P3

8 14 22
0 1 4

P1 = 8 – 1 = 7
P2 = 1 – 1 = 0
P3 = 14 – 2 = 12
P4 = 4 – 3 = 1
Average waiting time = (7 + 0 + 12 + 1) / 4 = 5
 Priority Scheduling
• A priority number (integer) is associated with each process.

• The CPU is allocated to the process with the highest priority

(smallest integer  highest priority)
• Non-preemptive Alg.

• SJF is priority scheduling where priority is the inverse of predicted next

CPU burst time

• Problem  Starvation ; low priority processes may never execute

• Solution  Aging ; as time progresses increase the priority of the process

 Example of Priority Scheduling

ProcessA arri Burst TimeT Priority

P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
• Priority scheduling Gantt Chart

P2 P5 P1 P3 P4

0 1 6 16 18 19

• Average waiting time = (6 + 0 + 16 + 18 + 1) / 5 = 41 / 5 = 8.2

Round Robin (RR)
• Each process gets a small unit of CPU time (time quantum q),
usually 10-100 milliseconds. After this time has elapsed, the
process is preempted and added to the end of the ready queue.
• If there are n processes in the ready queue and the time quantum is
q, then each process gets 1/n of the CPU time in chunks of at most
q time units at once. No process waits more than (n-1)q time units.
• Timer interrupts every quantum to schedule next process.
• Performance
• q large  FIFO
• q small  q must be large with respect to context switch, otherwise
overhead is too high
 Example of RR

Process Burst Time

P1 24
P2 3
P3 3
Time slice = 4
• The Gantt chart is:

P1 P2 P3 P1 P1 P1 P1 P1

0 4 7 10 14 18 22 26 30

• Typically, higher average turnaround than SJF, but better response

• q should be large compared to context switch time
• q usually 10ms to 100ms, context switch < 10 msec
 Algorithm Evaluation

• How to select CPU-scheduling algorithm for an OS?

• Determine criteria, then evaluate algorithms
• Deterministic modeling
• Type of analytic evaluation
• Takes a particular predetermined workload and defines the performance
of each algorithm for that workload
• Consider 5 processes arriving at time 0:
 Deterministic Evaluation

➢For each algorithm, calculate minimum average waiting time

Simple and fast, but requires exact numbers for input, applies only
to those inputs
▪ FCFS is 28ms:

▪ Non-preemptive SJF is 13ms:

▪ RR is 23ms: wt= Σ(completion time – burst time)/#P

Which is the best scheduling algorithm?

• Sometimes FCFS algorithm is better than the other in

short burst time while Round Robin is better for
multiple processes in every single time.

However, it cannot be predicted what process will come

after.

Average Waiting Time is a standard measure for giving

credit to the scheduling algorithm.
The End