By

Dr. M.O. Eze

Department of Computer Science,
Babcock University, Ilisan-Remo, Ogun State, Nigeria
 CONTENTS

Preliminary Reviews
Why CPU Optimization The Algorithms
- Process Concepts Scheduling? Criteria
- Interrupts
In order to gain a better understanding
of CPU Scheduling, we shall first do some
preliminary reviews in two areas of OS:

- Process Concepts
- System Interrupts
An operating system executes a variety of programs/ tasks. A

Process is defined as a program in execution. As a process

executes, it changes state. The possible states of a process are:

1. NEW: The process is being created.

2. RUNNING : Instructions are being executed.

3.WAITING: The process is waiting for some event to occur.

4. READY: The process is waiting to be assigned a processor.

5. TERMINATED: The process has finished execution.

 Source: OS Concepts by
Abraham Silberschatz et al)
The PCB is a special data structure that keeps
information about a process. Some of the
information in the PCB are:
1. Process state
2. Program counter
3. CPU registers
4. CPU scheduling information
5. Memory-management information
6. etc.
Interrupts are hardware signals sent to the CPU, so as to

interrupt its current operation, and to demand that it spends

some clock cycles servicing their own request. An interrupt of

very serious system implication is known as a trap or

exception. For instance, when a value is divided by “ZERO”, it

leads to an error. Thus, the system raises a trap/exception in

response to such an error operation/condition.

a. Keyboard  When a user presses the keyboard, the CPU stops

what it is doing, reads the keyboard, places the key value into

the buffer for later reading, then proceeds with what it was

doing.

b. System clock Sends periodic clock signals at intervals.

c. Devices  Send interrupts when through with I/O operations.

d. User Program  Also generates interrupts.

Interrupts are graded in levels, and the interrupt levels

determine the interrupt priorities. The implication is

that a high level interrupt can override a low level

interrupt. Thus the CPU must be able to recover from

several layers of interruptions, and end up doing the

request of highest priority.

QUE: Which of the following process interrupts {A,
X, R, Q} has the highest priority?

Intrerrupts A X R Q V
Level 10 7 5 18 2
QUE: Which of the following statement is true?

Interrupts W X R Q V
Level 10 7 5 18 2

a. {X} can Interrupt {W, Q},

b. {R} can interrupt {V, W}

c. {W} can interrupt {X,R}

It is possible to ignore interrupts. This is achieved
through a technique known as masking. However,
masking could lead to loss of data. The OS has some
non-maskable interrupts, for the most critical
operations.
Every single-processor system allows only one process to

run at a time while others wait until the CPU is free for their

usage. Multiprogramming ensures that many processes run

at all times. Scheduling is a fundamental function of the OS.

The aim is to determine which process should run, and

thereby maximize CPU utilization.

The success of CPU scheduling depends on the

following property of processes. Process execution

consists of a cycle of:

1. CPU execution

2. I/O wait.
Processes alternate between these two states.

Process execution begins with a CPU burst. That is

followed by an I/O burst, which is followed by

another CPU burst, then another I/O burst, …..

Eventually, the final CPU burst ends with a system

request to terminate execution (See Figure Below).

 CPU Burst

I/O Burst (Wait for I/O)

CPU Burst

I/O Burst (Wait for I/O)

CPU Burst

…
…
…
The durations of CPU bursts have been measured extensively by a number of

scientific researches. Although they vary greatly from process to process and from

computer to computer, they tend to have a similar frequency curve. The curve is

generally characterized as exponential or hyper-exponential, with:

- A large number of short CPU bursts and

- A small number of long CPU bursts.

An I/O-bound program typically has many short CPU bursts. A CPU-bound

program might have a few long CPU bursts. This distribution can be

important in the selection of an appropriate CPU-scheduling algorithm.

A Sample CPU Burst Histogram (Source: OS Concepts by Abraham Silberschatz et al)
 5.
2. 4. Response time
1. 3.
Waiting
CPU Throughp Turnarou time
(Amount of time it
takes from when a
Utilization ut nd time (Amount of request was
(Amount of time a submitted until the
(Keep the (No. of first response is
CPU as busy processes that time to process has
execute a been produced, not
as possible) complete their output (for time-
particular waiting in
execution per process) the ready sharing
time unit) queue) environment)
 MINIMIZE:
1. Waiting Time (Sum of Time Spent in Ready Queue)
2. Turnaround Time (Submission to Completion)
MAXIMIZE 3. Response time (Production of First Response)

1. CPU Utilization
2. Throughput
(Task per unit of Time) FAIRNESS
1. No Starvation (Every Task should be
handled after all)
2. Equality (Task with Similar
Characteristics should be treated Equally)

OPTIMIZATION
There are many CPU scheduling algorithms. We shall

concentrate our attention on the following:

1. First Come First Serve (FCFS) Algorithm

2. Shortest Job First (SJF) Algorithm

3. Priority Scheduling Algorithm

4. Round Robin Scheduling (RRS) Algorithm

5. Multi-Level Queue (MLQ) Scheduling

- In FCFS Algorithm, jobs are executed according to

their order of arrival.

- It is easy to implement.

- A major disadvantage is that FCFS has poor

performance due to its high average waiting time.

Sample Process Information Table
Processes Arrival Execute Time (CPU Burst)
P0 0 5
P1 1 3
P2 2 8
P3 3 6

Gantt Chart
P0 P1 P2 P3
5 3 8 6

0 5 8 16 22
CALCULATIONS:
The Waiting Time (WT) for a process is the time it waited before being

served. Based on the Gantt Chart, this is calculated as follows.

WT for P0 = 0

WT for P1 = 5

WT for P2 = 8

WT for P3 = 16

Hence Average Waiting Time (AWT) = (0+5+8+16)/4 = 29/4 = 7.25

- The SJF Algorithm is the best approach to

minimize waiting time.

- However, it is impossible to implement.

- Reason is that the execution time for each job

should be predicted in advance as accurately as

possible.
Process Information Table.
Processes Arrival Execute Time (CPU Burst)
P0 0 5
P1 1 3
P2 2 8
P3 3 6

Gantt Chart for SJF Algorithm

P1 P0 P3 P2
3 5 6 8

0 3 8 14 22
CALCULATIONS:
Based on the Gantt Chart, the waiting time for each process in the SJF

Algorithm are calculated as follows.

WT for P1 = 0

WT for P0 = 3

WT for P3 = 8

WT for P2 = 14

Hence Average Waiting Time (AWT) = (0+3+8+14)/4 = 25/4 = 6.25

- Each process is assigned a priority. The process

with highest priority is executed first.

- Processes with same priority are executed on a

FCFS bases.

- Priorities could be decided/assigned based on

memory, timing and other requirements.

Process Information Table.
Process Arrival Execute Time (CPU Burst) Priority

P0 0 5 2
P1 1 3 1
P2 2 8 1
P3 3 6 3

Gantt Chart for PBS Algorithm

P3 P0 P1 P2
6 5 3 8

0 6 11 14 22
CALCULATIONS:
Based on the Gantt Chart, the waiting time for each process in the PBS

Algorithm are calculated as follows.

WT for P3 = 0

WT for P0 = 6

WT for P1 = 11

WT for P2 = 14

Hence Average Waiting Time (AWT) = (0+6+11+14)/4 = 31/4 = 7.75

- In RRS Algorithm, each process is assigned an

equal execution time known as quantum.

- After the quantum of time, the process is pre-

empted and another one takes over.

- The initial execution takes place on a FCFS basis.

Process Information Table for RR Algorithm with
Quantum = 3.
Process Arrival Execute Time (CPU Burst)

P0 0 5
P1 1 3
P2 2 8
P3 3 6

Gantt Chart for RR Algorithm

P0 P1 P2 P3 P0 P2 P3 P2
3 3 3 3 3 3 3 3

0 3 6 9 12 15 18 21 24
CALCULATIONS:
Based on the Gantt Chart, the waiting time for each process in the RR

Algorithm are calculated as follows.

WT for P0 = 0 + (12-3) = 9

WT for P1 = 3

WT for P2 = 6+ (15-9) + (21-18) =6+6+3 = 15

WT for P3 = 9 + (18-12) = 9+6 =15

Hence Average Waiting Time (AWT) = 9+3+15+15 = 42/4 = 10.5

Based on the Gantt Chart and the calculated Average
Waiting Time, it is obvious that the estimated
Execution Time (CPU Burst) has been exceeded. The
reason is that in this version of RR Algorithm, each
quantum is spent, even when the process holding it
has completed execution. This can be optimized to
give rise to the following Gantt Chat.

P0 P1 P2 P3 P0 P2 P3 P2
3 3 3 3 2 3 3 2

0 3 6 9 12 14 17 20 22
New Calculation:
Based on the Gantt Chart for the Optimized Version of RR, the Average

Waiting Time will be as follows:

WT for P0 = 0 + (12-3) = 9

WT for P1 = 3

WT for P2 = 6+ (14-9) + (20-17) =6+5+3 = 14

WT for P3 = 9 + (17-12) = 9+5 =14

Hence Average Waiting Time (AWT) = 9+3+14+14 = 40/4 = 10

 CLASS ASSIGNMENT/
QUESTION & ANSWERS
QUE 1: The SJF algorithm is a special case of both the
PBS and the FCFS algorithms. Briefly explain.

ANSWER: The SJF algorithm is a special case of the

PBS algorithm. This is because, like the PBS, a
priority is associated with each process in the SJF.
However, the highest priority is allocated to the
process with lowest estimated execution time. Hence,
an SJF algorithm is simply a priority algorithm where
the priority (p) is the inverse of the (predicted) next
CPU burst. The larger the CPU burst, the lower the
priority, and vice versa. This is why SJF algorithm is a
special case of the PBS algorithm.
QUE 2: Both the SJF and PBS algorithms are special
cases of the FCFS algorithm. Briefly explain.

ANSWER:
Both the SJF and PBS algorithms are special cases of
the FCFS algorithms. This is because if two or more
processes have equal priority (in PBS algorithm), or
they have equal CPU burst (in case of SJF algorithm),
those processes will automatically follow the FCFS
order of execution., and the CPU is allocated to the
process with the highest priority. Equal-priority
processes are scheduled in FCFS order.
QUE 3: Given the following Process Information
Table T1 and T2. Which one is a more standard way
to represent the processes P0,P1,…P3 in a PBS
algorithm?
Process Table T1 Process Table T2
Priority P0 P1 P2 P3 Priority P0 P1 P2 P3
Priority 1 2 3 4 Priority 4 3 2 1

ANSWER:
Both tables are acceptable. This is because, priority
levels could be in terms of ascending or descending
order of numeric value. However, whichever applies
should be clearly stated to avoid confusion.
QUE 4: Priority Scheduling could be Preemptive or
non-preemptive. Explain

ANSWER:
When a process arrives at the ready queue, its
priority is compared with the priority of the currently
running process. A preemptive priority scheduling
algorithm will preempt the CPU if the priority of the
newly arrived process is higher than the priority of
the currently running process. A non preemptive
priority scheduling algorithm will simply put the
new process at the head of the ready queue.
QUE 5: One of the problems of Priority Scheduling is
Starvation (or Process Blocking). Explain

ANSWER:
A major problem with priority scheduling algorithms
is indefinite blocking, or 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. In a heavily loaded computer system, a
steady stream of higher-priority processes can
prevent a low-priority process from ever getting the
CPU.
Generally, one of two things will happen.

1. Either the process will eventually be run (at 2

A.M. Sunday, when the system is finally lightly
loaded),
2. or the computer system will eventually crash and
lose all unfinished low-priority processes.

There is a rumour that when the IBM 7094 was shut

down at MIT in 1973, they found a low-priority
process submitted since 1967 yet to be run!
QUE 6: Mention and explain the strategy used to solve
the problem of Starvation (process blocking).

ANSWER:
The solution strategy is the use of aging. This
involves the upgrade of priority of a waiting process
in such a way that it will be possible for it to execute
after a while. One way of achieving this is to increase
the process priority by 1 every interval of say, 5
minutes.
Abraham Silberschatz, Peter Galvin, and Greg Gagne,
"Operating System Concepts", 9th Ed, Published by
John Wiley & Sons, Inc., NJ USA, 2013