SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY,

INC. National Highway, Crossing Rubber, Tupi, South

Cotabato

COLLEGE OF INFORMATION AND COMMUNICATION

TECHNOLOGY ___________________________________________________

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 1 - of 13
LEARNING MODULE
FOR
IT 121: INTRODUCTION TO COMPUTING
 _____________________________________________________

WEEK 9

COURSE OUTLINE

COURSE CODE : IT 121

TITLE : Introduction to Computing

TARGET POPULATION : All BS Information Technology Students

INSTRUCTOR : Ms. Juliet Lugan

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 2 - of 13
Overview:

Computers are everywhere: at work, at school, and at home. Computers are a primary means of local and
global communications for billions of people. Through computers, society has instant access to information from
around the globe. This module presents the knowledge you need to be computer literate. The course acquaints
students to discover different and innovative ways of using various technology and learn how computing is
applied creatively to solve problems. Students will finish this course with a solid understanding of computers,
how to use computers, and how to access information on the Web.

Objectives:
 General Objective
Understand the significance of different process to be assigned to the CPU.
Discuss the different processes of scheduling algorithms.
To learn how to calculate average waiting time of different process.
Understand the process of operating system scheduling algorithms.
Familiarize themselves with the use of scheduling algorithms to the computer world.

Instruction to the Learner

Each chapter in this module contains a major lesson involving the introduction to computers and learn
how computing is applied creatively to solve problems. The units are characterized by continuity, and are
arranged in such a manner that the present unit is related to the next unit. For this reason, you are advised to
read this module. After each unit, there are exercises to be given. Submission of task given will be submitted by
the agreed deadline.

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 3 - of 13
Operating System Scheduling Algorithms

The Process Scheduler schedule different processes to be assigned to the CPU based on particular scheduling
algorithm. There are six popular process scheduling algorithms which we are going to discuss in the following
section:
∙ First-Come, First-Served (FCFS) Scheduling
∙ Shortest-Job-Next (SJN) Scheduling
∙ Priority Scheduling
∙ Round Robin(RR) Scheduling
These algorithms are either nonpreemptive or preemptive. Non-preemptive algorithms are designed so that
once a process enters the running state, it cannot be preempted until it completes its allotted time where as the
preemptive scheduling is based on priority where a scheduler may preempt a low priority running process
anytime when a high priority process enters into a ready state.
First Come First Serve (FCFS)
∙ Jobs are executed on first come, first serve basis.
∙ It is a nonpreemptive scheduling algorithm.
∙ Easy to understand and implement.
∙ Its implementation is based on FIFO
queue.
Process Arrival Execute
Time Time

P0 0
P1 1
P2 2
P3 3
 ∙ Poor in performance as average wait time is high.

Wait time of each process is following

P3 16-3=13
Process Wait Time: Service Time – Arrival Time

P0 0-0=0
Step by Step Example:
P1 5-1=4
How FCFS Works? Calculating Average Waiting Time
P2 8-2=6
Average Wait Time: (0+4+6+13)/4=5.75

Here is an example of five processes arriving at different times. Each process has a different burst time.

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY,

INC.

Page - 4 - of 13

Using the FCFS scheduling algorithm, these processes

are handled as follows.

(Step 0) The process begins with P4 which has arrival time 0 Process

Burst time Arrival time

P1 6 2
 P2 3 5

P3 8 1

P4 3 0

P5 4 4

Step 1) At time=1, P3 arrives. P4 is still executing.

Hence, P3 is kept in a queue.

Process Burst time Arrival time

P1 6 2

P2 3 5

P3 8 1

P4 3 0

P5 4 4

Step 2) At time= 2, P1 arrives which is kept in the queue.

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 5 - of 13
Process Burst time Arrival time

P1 6 2

P2 3 5

P3 8 1
 P4 3 0

P5 4 4

Step 3) At time=3, P4 process completes its execution.

Step 4) At time=4, P3, which is first in the queue, starts execution.

Process Burst time Arrival time

P1 6 2

P2 3 5

P3 8 1

P4 3 0

P5 4 4

Step 5) At time =5, P2 arrives, and it is kept in a

queue.

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 6 - of 13
Process Burst time Arrival time

P1 6 2

P2 3 5
 P3 8 1

P4 3 0

P5 4 4

Step 6) At time 11, P3 completes its execution.

Step 7) At time=11, P1 starts execution. It has a burst time of 6. It completes execution at time interval

17

Step 8) At time=17, P5 starts execution. It has a burst time of 4. It completes execution at

time=21

Step 9) At time=21, P2 starts execution. It has a burst time of 2. It completes execution at time interval

23

Step 10) Let's calculate the average waiting time for above example.

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 7 - of 13
Waiting time = Start time - Arrival time P4 = 0-0 = 0 P5= 17-4 = 13
P2= 21-5= 16
P3 = 3-1 = 2

PI = 11-2 = 9
Average Waiting Time = 40/5= 8

In the following example, we have 4 processes with process ID P0, P1, P2, and P3. The arrival time of P0 is 0, P1
is 1, P2 is 2, and P3 is 3. The arrival time and burst time of the processes are given in the following table.

The waiting time and Turnaround time are calculated with the help of the following

formula. Waiting Time = Turnaround time – Burst Time

Turnaround Time = Completion time – Arrival time

Process Arrival Burst Completion Time Turnarou Waiting
ID Time Time nd Time Time

P0 0 6 6 6 0

P1 1 8 14 13 5

P2 2 10 24 22 12

P3 3 12 36 33 21

Average Waiting Time = 0+5+12+21/4

= 38/4
= 9.5 ms
Average Turnaround Time = 6+13+22+33/4
=74/4
= 18.5 ms

Shortest Job Next (SJN)

∙ This is also known as shortest job first, or SJF
∙ This is a nonpreemptive scheduling algorithm.
∙ Best approach to minimize waiting time.
∙ Easy to implement in Batch systems where required CPU time is known in advance. ∙
Impossible to implement in interactive systems where required CPU time is not known. ∙
Processer should know in advance how much time process will take.

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

 Page - 1 - of 13

Process Arrival Execute Service

Time Time Time

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

Wait time of each process is following

Process Wait Time: Service Time – Arrival Time

P0 3-0=3

P1 0-0=0

P2 16-2=14

P3 8-3=5

Step by Step Example:

How to compute below times in SJF using a program?

Average Wait Time: (3+0+14+5)/4=5.50
 1. Completion Time: Time at which process completes its execution.
2. Turn Around Time: Time Difference between completion time and arrival time. Turn Around Time =
Completion Time – Arrival Time
3. Waiting Time(W.T): Time Difference between turn around time and burst time.
Waiting Time = Turn Around Time – Burst Time

Consider the below processes available in the ready queue for execution, with arrival time as 0 for all and

given burst times.

As you can see in the GANTT chart above, the process P4 will be picked up first as it has the shortest burst time,
then P2, followed by P3 and at last P1.
We scheduled the same set of processes using the First come first serve algorithm in the previous tutorial, and
got average waiting time to be 18.75 ms, whereas with SJF, the average waiting time comes out 4.5 ms.What
is Shortest Job First Scheduling?

Shortest Job First (SJF) is an algorithm in which the process having the smallest execution time is chosen for the
next execution. This scheduling method can be preemptive or non-preemptive. It significantly reduces the
average waiting time for other processes awaiting execution. The full form of SJF is Shortest Job First.

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 2 - of 13
Characteristics of SJF Scheduling

∙ It is associated with each job as a unit of time to complete.

∙ This algorithm method is helpful for batch-type processing, where waiting for jobs to complete is not
critical.
∙ It can improve process throughput by making sure that shorter jobs are executed first, hence possibly
have a short turnaround time.
∙ It improves job output by offering shorter jobs, which should be executed first, which mostly have a
shorter turnaround time.

Non-Preemptive SJF

In non-preemptive scheduling, once the CPU cycle is allocated to process, the process holds it till it reaches a
waiting state or terminated.

Consider the following five processes each having its own unique burst time and arrival time.

Process Queue Burst time Arrival time P1 6 2 P2 Step 0) At time=0, P4 arrives and starts execution.

2 5 P3 8 1 P4 3 0 P5 4 4
 execution.

Step 1) At time= 1, Process P3 arrives. But, P4 still needs

2 execution units to complete. It will continue

Step 2) At time =2, process P1 arrives and is added to the

waiting queue. P4 will continue execution.

Step 3) At time = 3, process P4 will finish its execution. The burst

executed because its burst time is less compared to P3.

Step 4) At time = 4, process P5 arrives and is added to the waiting

queue. P1 will continue execution.

Step 5) At time = 5, process P2 arrives and is added to the waiting

queue. P1 will continue execution.

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 3 - of 13

Step 6) At time = 9, process P1 will finish its execution. The burst time of P3, P5, and P2 is compared. Process P2
is executed because its burst time is the lowest.

Step 7) At time=10, P2 is executing and P3 and P5 are in the waiting queue.

Step 8) At time = 11, process P2 will finish its execution. The burst time of P3 and P5 is compared. Process P5 is

executed because its burst time is lower. Step 9) At

time = 15, process P5 will finish its execution.

Step 10) At time = 23, process P3 will finish its execution.

Step 11) Let's calculate the average waiting time for above example.

Wait time
P4= 0-0=0
P1= 3-2=1
P2= 9-5=4
P5= 11-4=7
P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 4 - of 13
Lab Activity

Research Activity: The input and output process of Shortest Job First (SJF) Scheduling Algorithm is given

below. Explain how the FCFS scheduling algorithm solved the problem. Is the solution correct? *Consider the

following set of processes, with the length of the CPU burst given in milliseconds:

0 3 9 16 24
Process ID Burst Time P4 P1 P3 P2

P1 6

P2 8 Waiting Time for P1 = 3 ms Waiting Time for P2 = 16 ms

P3 7 Waiting Time for P3 = 9 ms Waiting Time for P4 = 0 ms

P4 3

Average Waiting Time

Gantt Chart:
= (3 + 16 + 9 + 0) /4 = 7 ms

By comparison, if we were using the FCFS scheduling scheme, the average waiting time would be
10.25 millisecond.

Problem Solving:
Use the First Come First Served Scheduling Algorithm to solve the average waiting time below.
Customer Arrival Time Burst Time

J1 0 2

J2 2 5

J3 5 2

J4 6 1

J5 8 5

J6 12 2

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 5 - of 13
Exercises

Test I: The input and output process of First Come First Serve Scheduling Algorithm is given below.

a.) Explain how the FCFS scheduling algorithm solved the problem. Is the solution correct? And what is your
insight about the topic?

*Consider the set of 5 processes whose arrival time and burst time are given below:
Process ID Arrival Time Burst Time

P1 4 5

P2 6 4

P3 0 3

P4 6 2

P5 5 4

Calculate the average waiting time and average turnaround time, if FCFS scheduling algorithm is
followed.

Solution: Gantt Chart 0

P3 P1 P
0 3 49 13 17 19

Process ID Completion Time Turnaround Time Waiting Time

P1 9 9-4=5 5-5=0

P2 17 17-6=11 11-4=7

P3 3 3-0=3 3-3=0

P4 19 19-6=13 13-2=11

P5 13 13-5=8 8-4=4

Now,
 Average Turn Around Time = (5 + 11 + 3 + 13 + 8) / 5

= 40/5

= 8 units

b.) what is preemptive and non-preemptive and their difference. c.) Give

atleast one example of preemptive and non-preemptive process.

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 6 - of 13