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 12
LEARNING MODULE
FOR
IT 121: INTRODUCTION TO COMPUTING
 _____________________________________________________

WEEK 10

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 12
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 12
Operating System Scheduling Algorithms

Priority Based Scheduling

∙ Priority scheduling is a nonpreemptive algorithm and one of the most common sched- uling algorithms in
batch systems.
∙ Each process is assigned a priority. Process with highest priority is to be executed first and so on. ∙
Processes with same priority are executed on first come first serve basis.
∙ Priority can be decided based on memory requirements, time requirements or any other resource
requirement.
Process Arrival Time Execute Priority Service
Time Time

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

Wait time of each process is following

P2 14-2=12
Process Wait Time: Service Time – Arrival Time
P3 0-0=0
P0 9-0=9

P1 6-1=5
Step by Step Example:
Average Wait Time: (9+5+12+0)/4=6.5

∙ Consider following five processes P1 to P5. Each process has its unique priority, burst time, and
arrival time.
Process Priority Burst time Arrival time

P1 1 4 0

P2 2 3 0

P3 1 7 6

P4 3 4 11

P5 2 2 12

∙ Step0) At time=0, Process P1 and P2 arrive. P1 has higher priority than P2. The execution begins
with process P1, which has burst time 4.

∙ Step 1) At time=1, no new process arrive. Execution continues with P1.

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 4 - of 12
 ∙
∙ Step 2) At time 2, no new process arrives, so you can continue with P1. P2 is in the waiting queue.

∙
∙ Step
3) At time 3, no new process arrives so you can continue with P1. P2 process still in the waiting
queue.

∙
∙ Step 4) At time 4, P1 has finished its execution. P2 starts execution.

∙
∙ Step 5) At time= 5, no new process arrives, so we continue with P2.

∙
∙ Step6) At time=6, P3 arrives. P3 is at higher priority (1) compared to P2 having priority (2). P2 is
preempted, and P3 begins its execution.
Process Priority Burst time Arrival time

P1 1 4 0

P2 2 1 out of 3 pending 0
 P3 1 7 6

P4 3 4 11

P5 2 2 12

Step 7) At time 7, no-new process arrives, so we continue with P3. P2 is in the waiting queue.

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 5 - of 12

Step 8) At time= 8, no new process arrives, so we can continue with P3.

Step 9) At time= 9, no new process comes so we can continue with P3.

Step 10) At time interval 10, no new process comes, so we continue with P3

Step 11) At time=11, P4 arrives with priority 4. P3 has higher priority, so it continues its execution.
 Process Priority Burst time Arrival time

P1 1 4 0

P2 2 1 out of 3 pending 0

P3 1 2 out of 7 pending 6

P4 3 4 11

P5 2 2 12

Step 12) At time=12, P5 arrives. P3 has higher priority, so it continues execution.

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 6 - of 12

Step 13) At time=13, P3 completes execution. We have P2,P4,P5 in ready queue. P2 and P5 have equal
priority. Arrival time of P2 is before P5. So P2 starts execution.
Process Priority Burst time Arrival time

P1 1 4 0

P2 2 1 out of 3 pending 0

P3 1 7 6

P4 3 4 11

P5 2 2 12

Step 14) At time =14, the P2 process has finished its execution. P4 and P5 are in the waiting state. P5
has the highest priority and starts execution.
Step 15) At time =15, P5 continues execution.

Step 16) At time= 16, P5 is finished with its execution. P4 is the only process left. It starts

execution.

Step 17) At time =20, P5 has completed execution and no process is left.

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

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 7 - of 12
Waiting Time = start time - arrival time + wait time for next burst

P1 = o - o = o
P2 =4 - o + 7 =11
P3= 6-6=0
P4= 16-11=5
Average Waiting time = (0+11+0+5+2)/5 = 18/5= 3.6

Advantages of priority scheduling

Here, are benefits/pros of using priority scheduling method:

∙ Easy to use scheduling method

∙ Processes are executed on the basis of priority so high priority does not need to wait for long
which saves time
∙ This method provides a good mechanism where the relative important of each process may be
precisely defined.
∙ Suitable for applications with fluctuating time and resource requirements.

Disadvantages of priority scheduling

Here, are cons/drawbacks of priority scheduling

∙ Ifthe system eventually crashes, all low priority processes get lost.
∙ Ifhigh priority processes take lots of CPU time, then the lower priority processes may starve and
will be postponed for an indefinite time.
∙ This scheduling algorithm may leave some low priority processes waiting indefinitely. ∙ A process
will be blocked when it is ready to run but has to wait for the CPU because some other process is
 running currently.
∙ If a new higher priority process keeps on coming in the ready queue, then the process which is in
the waiting state may need to wait for a long duration of time.

IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 8 - of 12
Round Robin Scheduling
∙ Round Robin is the preemptive process scheduling algorithm.
∙ Each process is provided a fix time to execute called quantum.
∙ Once a process is executed for given time period. Process is preempted and other process executes for
given time period.
∙ Context switching is used to save states of preempted processes.

Wait time of each process is following

Here are the important characteristics of Round-Robin
Process Wait Time: Service Time – Arrival Time
Scheduling: ∙ Round robin is a pre-emptive algorithm
P0 (0-0)+(12-3)=9
Average Wait Time: (3+0+14+5)/4=5.50
P1 (3-1)=2

P2 (6-2)+(14-9)+(20-17)=12

P3 (9-3)+(17-12)=11

Characteristics of Round-Robin Scheduling

 ∙ The CPU is shifted to the next process after fixed interval time, which is called time
quantum/time slice.
∙ The process that is preempted is added to the end of the queue.
∙ Round robin is a hybrid model which is clock-driven
∙ Time slice should be minimum, which is assigned for a specific task that needs to be processed.
However, it may differ OS to OS.
∙ It is a real time algorithm which responds to the event within a specific time limit. ∙
Round robin is one of the oldest, fairest, and easiest algorithm.
∙ Widely used scheduling method in traditional OS.

Example of Round-robin Scheduling

∙ Consider this following three processes

Process Queue Burst time

P1 4

P2 3

P3 5

IT

121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 9 - of 12

∙
∙ Step
1) The execution begins with process P1, which has burst time 4. Here, every process
executes for 2 seconds. P2 and P3 are still in the waiting queue.
 ∙
∙ Step 2) At time =2, P1 is added to the end of the Queue and P2 starts executing ∙

∙ Step 3) At time=4 , P2 is preempted and add at the end of the queue. P3 starts executing.

∙
∙ Step 4) At time=6 , P3 is preempted and add at the end of the queue. P1 starts executing.

∙
∙ Step 5) At time=8 , P1 has a burst time of 4. It has completed execution. P2 starts execution ∙
IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 10 - of 12
∙ Step 6) P2 has a burst time of 3. It has already executed for 2 interval. At time=9, P2 completes
execution. Then, P3 starts execution till it completes.

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

Wait time
P1= 0+ 4= 4
P2= 2+4= 6
P3= 4+3= 7

Advantage of Round-robin Scheduling

Here, are pros/benefits of Round-robin scheduling method:

∙ It doesn't face the issues of starvation or convoy effect.

∙ All the jobs get a fair allocation of CPU.
∙ It deals with all process without any priority
∙ If you know the total number of processes on the run queue, then you can also assume the worst-case
response time for the same process.
∙ This scheduling method does not depend upon burst time. That's why it is easily implementable on the
system.
∙ Once a process is executed for a specific set of the period, the process is preempted, and another
process executes for that given time period.
∙ Allows OS to use the Context switching method to save states of preempted processes. ∙
It gives the best performance in terms of average response time.

Disadvantages of Round-robin Scheduling

Here, are drawbacks/cons of using Round-robin scheduling:

∙ If slicing time of OS is low, the processor output will be reduced.

∙ This method spends more time on context switching
∙ Its performance heavily depends on time quantum.
∙ Priorities cannot be set for the processes.
∙ Round-robin scheduling doesn't give special priority to more important tasks.
∙ Decreases comprehension
∙ Lower time quantum results in higher the context switching overhead in the system. ∙
Finding a correct time quantum is a quite difficult task in this system.
IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 11 - of 12
Lab Activity

Activity 1: Problem Solving.

Consider the following set of processes, assumed to have arrived at time 0, in the order P1, P2, P3, P4, P5,
with the length of the CPU burst given in milliseconds:
Customer Burst Time Priority

J1 10 3

J2 1 1

J3 2 4

J4 1 5

J5 5 2

Using Priority Scheduling, give the Average Waiting Time of this process.

Exercises

Research Study: Explain each question based on your research learnings.

a. What is preemptive and non-preemptive? The difference between the two.

b. Give atleast one example of Priority preemptive and Priority non-preemptive.
c. What is the major problem with priority scheduling algorithms and give the solution to the
problem.
d. What is Round Robin and how to solve the average waiting time and average Turn Around time.
e. Give atleast one example of Round Robin preemptive with explanation of your insights.
IT 121: Introduction to Computing

SOUTH EAST ASIAN INSTITUTE OF TECHNOLOGY, INC.

Page - 12 - of 12