Operating System
Scheduling Algorithms
First-Come, First-Served Scheduling
Shortest-Job-First Scheduling
Priority Scheduling
Round-Robin Scheduling
Scheduling Algorithms
CPU Scheduling deals with the problem of deciding which of
the processes in the ready queue is to be allocated the CPU.
1. First-Come, First-Served Scheduling (FCFS)
2. Shortest-Job-First (SJF) Scheduling
3. Priority Scheduling
4. Round Robin (RR)
First-Come, First-Served Scheduling (FCFS)
Consider the following set of processes that arrive at time 0, with the
length of the CPU burst given in milliseconds.
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3 :
The FCFS Gantt Chart:
P1 P2 P3
0 24 27 30
Waiting time for each process: P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17
FCFS Scheduling (Cont.)
Suppose that the processes arrive in this order:
P 2 , P3 , P 1
The FCFS Gantt Chart:
P2 P3 P1
0 3 6 30
Waiting time for each process: P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)/3 = 3
Shortest-Job-First (SJF) Scheduling
This algorithm associates with each process the length of the
process’s next CPU burst. When the CPU is available, it is
assigned to the process that has the smallest next CPU burst.
Example of SJF
Process Burst Time
P1 7
P2 4
P3 1
P4 4
The SJF Gantt Chart:
P3 P2 P4 P1
0 1 5 9 16
Waiting time for each process: P1 = 9; P2 = 1; P3 = 0; P4 = 5
Average waiting time = (9+1+0+5)/4 = 3.75
Shortest-Job-First (SJF) Scheduling (Cont.)
Two schemes:
nonpreemptive – once CPU given to the process it cannot
be preempted until completes its CPU burst.
preemptive – if a new process arrives with CPU burst
length less than remaining time of current executing
process, preempt. This scheme is known as the
Shortest-Remaining-Time-First (SRTF).
SJF is optimal – gives minimum average waiting time for a
given set of processes.
Example of Non-Preemptive SJF
Once CPU given to the process it cannot be preempted until
completes its CPU burst
Process Arrival Time Burst Time
P1 0 7
P2 2 4
P3 4 1
P4 5 4
SJF (non-preemptive) Gantt Chart
P1 P3 P2 P4
0 7 8 12 16
Waiting time for each process: P1 = 0; P2 = 6; P3 = 3; P4 = 7
Average waiting time = (0 + 6 + 3 + 7)/4 = 4
Example of Preemptive SJF
If a new process arrives with CPU burst length less than remaining
time of current executing process, preempt.
This scheme is known as the Shortest-Remaining-Time-First (SRTF)
Process Arrival Time Burst Time
P1 0 7
P2 2 4
P3 4 1
P4 5 4
SJF (preemptive) Gantt Chart
P1 P2 P3 P2 P4 P1
0 2 4 5 7 11 16
Waiting time for each process: P1 = 9; P2 = 1; P3 = 0; P4 = 2
Average waiting time = (9 + 1 + 0 +2)/4 = 3
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).
A major problem with priority scheduling algorithm is:
Starvation: A process that is ready to run but waiting for the
CPU can be considered blocked. A priority scheduling
algorithm can leave some low priority processes waiting
indefinitely.
The Solution is: Aging; Aging involves gradually increasing
the priority of processes that wait in the system for a long
time.
Priority Scheduling
Process Burst Time 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
Waiting time for each process: P1 = 6; P2 = 0; P3 = 16; P4 = 18; P5 =1
Average waiting time = 8.2 msec
Priority Scheduling
Two schemes:
Nonpreemptive
Preemptive.
Round Robin (RR)
The round-robin (RR) scheduling algorithm is designed especially
for time-sharing system.
Each process gets a small unit of CPU time (time quantum q),
usually 10-100 milliseconds in length. 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:
If the time quantum is extremely large, the RR policy is the same
as the FCFS policy.
If the time quantum is extremely small (say, 1 millisecond), the
RR approach can result in a large number of context switches.
Round Robin (RR)
Process Burst Time
P1 24
P2 3
P3 3
Round Robin Scheduling Gantt Chart (Time Quantum = 4)
P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30
Waiting time for each process: P1 = 6; P2 = 4; P3 = 7
Average waiting time = 5.67 msec
Exercise (1)
Consider the following set of processes, with the length of the CPU-burst time given in
milliseconds:
Process Burst Time Priority
P1 10 2
P2 1 0
P3 2 2
P4 1 3
P5 5 1
The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.
a. Draw FIVE (5) Gantt charts that illustrate the execution of these processes using
the following scheduling algorithms: FCFS, SJF, non-preemptive priority (a
smaller number implies a higher priority) and RR (for quantum = 1 and =2).
b. What is the waiting time for each process for each of these scheduling algorithms?
c. Which of the algorithms results in the minimum average waiting time (over all
processes)?
Exercise (2)
Consider the following set of processes, with the length of the CPU-burst time given in
milliseconds:
Process Burst Time Priority
P1 9 2
P2 2 0
P3 3 2
P4 3 3
P5 7 1
The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.
a. Draw four Gantt charts that illustrate the execution of these processes using the
following scheduling algorithms: FCFS, SJF, non-preemptive priority (a smaller number
implies a higher priority) and RR (quantum = 2).
b. What is the waiting time for each process for each of these scheduling algorithms?
c. Which of the algorithms results in the minimum average waiting time (over all
processes)?
Exercise (3)
Consider the following set of processes, with the length of the CPU-burst time given in
milliseconds:
Process Burst Time Arrival Time
P1 2 1
P2 4 2
P3 2 0
P4 5 4
P5 3 3
a. Draw THREE (3) Gantt charts that illustrate the execution of these processes using
the following scheduling algorithms: FCFS, and RR (for quantum = 1 and =2).
b. What is the waiting time for each process for each of these scheduling algorithms?
c. Which of the algorithms results in the minimum average waiting time (over all
processes)?
