A.Y.

: 2023-24 Sub: System Fundamentals

Experiment 2

(CPU Scheduling –Non Preemptive algorithm)

Aim: Implement CPU Scheduling –Non Preemptive Algorithm.

Theory: CPU scheduling is the task of selecting a waiting process from the ready queue and
allocating the CPU to it. The CPU is allocated to the selected process by the dispatcher (It is the
module that gives control of the CPU to the processes by short-term scheduler). Scheduling is a
fundamental operating system function. In a single processor system, onlyone process can run at a
time; any other process must wait until the CPU is free and can be rescheduled. The objective of
multiprogramming is to have some process running at all times, to maximize CPU utilization.
CPU scheduling decisions may take place under the following four circumstances:

1. When a process switches from the running state to the waiting state
2. When a process switches from the running state to the ready state.
3. When a process switches from the waiting state to the ready state.
4. When a process terminates.
Depending on the above circumstances the two types of scheduling are:

1. Non-Preemptive
2. Preemptive
1. Non-Preemptive: Under this scheduling, once the CPU has been allocatedto a process,
the process keeps the CPU until it releases the CPU either by terminating or by
switching to the waiting state.
2. Preemptive: Under this scheduling, once the CPU has been allocated to a process,
the process does not keep the CPU but can be utilized by some other process. This
incurs a cost associated with access to shared data. It also affects the design of the
operating system kernel.

Scheduling Criteria:

1. CPU utilization: It can range from 0-100%. In a real system, it ranges shouldrange
from 40-90%.

2. Throughput: Number of processes that are completed per unit time.

3. Turnaround time: How long a process takes to execute. It is the sum of the periods
spent waiting to get into memory, waiting in the ready queue, executing on the CPU,
and doing I/O

4. Waiting time: It is the sum of the periods spent waiting in the ready queue.
5. Response time: Time from the submission of a request until the first response is
A.Y.: 2023-24 Sub: System Fundamentals
produced. It is desirable to maximize CPU utilization and Throughput and minimize
Turnaround time, waiting time and Response time.
NON-PREEMPTIVE SCHEDULING ALGORITHMS:

1. FCFS
2. SJF
3. PRIORITY
1. FCFS (First-Come, First-Served):
 It is the simplest algorithm and NON-PREEMPTIVE.
 The process that requests the CPU first is allocated to the CPU first.
 The implementation is easily managed by queue. When a process enters the ready
queue, its PCB is linked onto the tail of the queue. When the CPU is free, it is
allocated to the process at the head of the queue
 The average waiting time, however, is long. It is not minimal and may vary
substantially if the process’s CPU burst time varies greatly.
 This algorithm is particularly troublesome for time-sharing systems.
2. SJF (Shortest Job First):
 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. If the next CPU bursts of two processes are the same, FCFS is used to
break the tie.
 It is also called shortest next CPU burst algorithm or shortest remaining time first
scheduling.
 It is provably optimal; in that it gives the minimum average waiting time for a given
set of processes.
 The real difficulty with SJF knows the length of the next CPU request.
 It can be either PREEMPTIVE (SRTF- Shortest Remaining Time First) or NON-
PREEMPTIVE.
3. PRIORITY SCHEDULING:
 The SJF is a special case of priority scheduling.
 In priority scheduling algorithm, a priority is associated with each process, and the
CPU is allocated to the process with the highest priority.
 It can be either PREEMPTIVE or NON-PREEMPTIVE
 A major problem with priority scheduling algorithms is indefinite blocking, or
starvation.
 A solution to starvation is AGING. It is a technique of gradually increasing the
priority of process that wait in the system for long time.

Expected Output:
A.Y.: 2023-24 Sub: System Fundamentals
Enter the no. of process: 5
Enter the arrival time for process P1: 0
Enter the arrival time for process P2: 1
Enter the arrival time for process P3: 3
Enter the arrival time for process P4: 9
Enter the arrival time for process P5: 12
Enter the burst time for process P1: 3
Enter the burst time for process P2: 5
Enter the burst time for process P3: 2
Enter the burst time for process P4: 5
Enter the burst time for process P5: 5
Inputs given by the user are:

==============================================================

Process BT
AT
P1 0 3
P2 1 5
P3 3 2
P4 9 5
P5 12 5
============================================================

Gant Chart is as follows:

0->P1->3->P2->8->P3->10->P4->15->P5->20
A.Y.: 2023-24 Sub: System Fundamentals

TABLE
Process AT BT FT TAT WT

P1 0 3 3 3.000000 0.000000
P2 1 5 8 7.000000 2.000000
P3 3 2 10 7.000000 5.000000
P4 9 5 15 6.000000 1.000000
P5 12 5 20 8.000000 3.000000

Average Turn Around Time:

6.200000 Average Waiting Time:
2.200000

Lab Assignments to complete in this session

1.Consider the set of 6 processes arrived at zero instance and burst time are 7, 5, 3, 1, 2, 1. If the
CPU scheduling policy is First Come First Serve, calculate the average waiting time.
2.Consider the set of 3 processes arrived at zero instance and burst time are 9, 4, 9 respectively
and priority 2, 1 and 3 respectively. If the CPU scheduling policy is SJF, calculate the average
waiting time and average turnaround time.
3.Consider the set of 3 processes arrived at zero instance and burst time are 9, 4, 9 respectively
and priority 2, 1 and 3 respectively. If the CPU scheduling policy is Priority Scheduling,
calculate the average waiting time and average turnaround time.