Schedulin
g
Algorithm
s
Group No. 2
Overview
Basic Concepts
Scheduling Criteria
Scheduling Algorithms
Implementation in C++
Demonstration
Involvement of Operating System
CPU Scheduling Algorithms
Basic Concepts
Main objective of multiprogramming is to
keep on running processes all the time for
maximum CPU utilization.
Scheduling is fundamental function of OS.
The task of selecting the processes in
memory that are ready to execute, and
allocating them to the CPU is performed
by the CPU Scheduler.
CPU Scheduling Algorithms
CPU Scheduler
CPU scheduling decisions may take
place when a process:
o 1. Switches from running to waiting
state
o 2. Switches from running to ready
state
o 3. Switches from waiting to ready
o 4. Terminates
Scheduling under 1 and 4 is non
preemptive.
All other scheduling is preemptive.
CPU Scheduling Algorithms
CPU Scheduler
CONT
Nonpreemptive
Once a process is allocated the CPU, it
does not leave unless:
o it has to wait, e.g., for I/O request
o it terminates
Preemptive
o OS can force (preempt) a process
from CPU at anytime
o E.g., to allocate CPU to another
higher-priority process
CPU Scheduling Algorithms
Scheduling Criteria
CPU
utilization: keep the CPU as busy
as possible
Maximize
Throughput: No of processes that
complete their execution per time unit
Maximize
Turnaround time: amount of time to
execute a particular process (time
from submission to termination)
Minimize
CPU Scheduling Algorithms
Scheduling Criteria
CONT
Waiting time: amount of time a process
has been waiting in the ready queue
(sum of time waiting in ready queue)
o Minimize
Response time amount of time it
takes from when a request was
submitted until the first response is
produced, not output (for timesharing environment)
o Minimize
CPU Scheduling Algorithms
Scheduling Algorithms
First Come, First Served
Shortest Job First
Priority
Round Robin
CPU Scheduling Algorithms
Implementation in C++
Class: cpuschedule
Attributes:
o n
number of processes
o Bu[ ] Array to store Burst
Time
o A[ ]
Array to store Arrival
Time
o Wt[ ] Array to store Waiting
Time
o Twt
Total Waiting Time
o Awt
Average Waiting Time
CPU Scheduling Algorithms
CONT
Implementation in C++
Operations
:o
Getdata() To get number of
processes and Burst Times from
the user
o Fcfs() First Come, First Served
Algorithm
o Sjf() Shortest Job First
(normal) Algorithm
o SjfP() Shortest Job First
(Preemption) Algorithm
o SjfNp() Shortest Job First (non
preemption) Algorithm
o Priority() Priority Algorithm
CPU Scheduling Algorithms
10
First Come, First
Served
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
24
P3
27
30
Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17
CPU Scheduling Algorithms
11
First Come First
Served
Suppose that the processes arrive in the
CONT
order :
P2 , P3 , P1 (P1:24,P2:3,P3:3)
The Gantt chart for the schedule is:
P2
P3
P1
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
CPU Scheduling Algorithms
12
Shortest Job First
Normal SJF
Process
P1
Burst Time
7
P2
P3
The Gantt Chart for SJF (Normal) is:
P2
0
P3
3
P1
7
14
Average waiting time = (0 + 3 + 7)/3 =
CPU Scheduling Algorithms
3.33
13
CONT
Shortest Job First
Non-Preemptive SJF
Process
P1
Arrival Time
0.0
Burst Time
7
P2
2.0
P3
4.0
P4
5.0
The Gantt Chart for SJF (non-preemptive)
is:
P1
P3
P2
P4
0
12
16
CPU Scheduling Algorithms
14
CONT
Shortest Job First
Preemptive SJF
Process Arrival Time
P1
0.0
P2
2.0
P3
4.0
P4
5.0
The
Burst Time
7
4
1
4
Gantt Chart for SJF (preemptive) is:
P1
0
P2
2
Average
P3
4
P2
5
P4
7
P1
11
16
waiting time = (9 + 1 + 0 +2)/4 = 3
CPU Scheduling Algorithms
15
Shortest Job First
CONT
Associate with each process the length of
its next CPU burst.
Use these lengths to schedule the process
with the shortest time.
Two schemes:
o Non-Preemptive: once CPU given to the
process it cannot be preempted until
completes its CPU burst.
o Preemptive: if a new process arrives with
CPU burst length less than remaining
time of current executing process,
preempt. This scheme is know as the
Shortest-Remaining-Time-First (SRTF).
SJF is optimal:
gives minimum average
waiting time for a given set of processes.
CPU Scheduling Algorithms
16
Priority
Process
P1
P2
P3
P4
P5
Priority
3
1
4
5
2
Gantt Chart
P2
0
Burst Time
10
1
2
1
5
P5
1
P1
6
P3
16
P4
18
19
Average waiting time = (6 + 0 + 16 + 18 +
1)/5 = 8.2
CPU Scheduling Algorithms
17
Priority
CONT
priority number (integer) is associated
with each process.
Lager the CPU burst lower the priority.
The CPU is allocated to the process with
the highest priority (smallest integer
highest priority)
Starvation
(Infinity
blocking):
low
priority processes may never execute.
Aging: as time progresses increase the
priority of the process.
CPU Scheduling Algorithms
18
Round Robin
Process
P1
P2
P3
Burst Time
24
3
3
Quantum
time = 4 milliseconds
The Gantt chart is:
P1
0
P2
4
P3
7
P1
10
P1
14
P1
18
P1
22
P1
26
30
Average
waiting time = {[0+(10-4)]
+4+7}/3 = 5.6
CPU Scheduling Algorithms
19
Round Robin
CONT
Typically, higher average turnaround
than SJF, but better response
Each process gets a small unit of CPU
time (time quantum), usually 10-100
milliseconds. After this time has
elapsed, the process is preempted and
added to the end of the ready queue.
Performance
o q large FCFS
o q small q must be large with
respect to context switch, otherwise
overhead is too high
CPU Scheduling Algorithms
20
Involvement of OS
Source Code
Compiler
Conversion
Executable
Microsoft
Windows
Microkernel
(.c)
(.i , .o)
(.exe)
(load executable
directly to memory)
Memory
CP
U
Execut
e
Scheduling
Algorithms
CPU Scheduling Algorithms
21
CPU
Schedulin
g
Algorithm
Group No.
s
2
Group No. 2
22
