PROFESSOR ACADEMY

NTA NET/TNSET CS-PAPER-2/DEC-23

Operating System Class2

 Context Switch
• A Context Switch is the mechanism to store
and restore the state or context of a CPU in
Process Control block so that a process
execution can be resumed from the same
point at a later time.
• This is a feature of a multitasking operating
system and allows a single CPU to be shared by
multiple processes.
 Context Switch
• In the above diagram, initially Process 1 is running.
Process 1 is switched out and Process 2 is switched in
because of an interrupt or a system call.
• Context switching involves saving the state of Process 1
into PCB1 and loading the state of process 2 from PCB2.
• After some time again a context switch occurs and
Process 2 is switched out and Process 1 is switched in
again.
• This involves saving the state of Process 2 into PCB2 and
loading the state of process 1 from PCB1.
 • In the following process state transition diagram for a uniprocessor system, assume
that there are always some processes in the ready state: Now consider the following
statements:

I. If a process makes a transition D, it would result in Another

process making transition A immediately.
II. A process P2 in blocked state can make transition E While
another process P1 is in running state. (A) I and II
III. The OS uses preemptive scheduling. (B) I and III
IV. The OS uses non-preemptive scheduling. (C) II and III
Which of the above statements are TRUE? (D) II and IV
Answer: C
 GATE-CS-2002
Which combination of the following features
will suffice to characterize an OS as a
multi-programmed OS?
(a)More than one program may be loaded into main memory at the
same time for execution.

(b) If a program waits for certain events such as I/O, another

program is immediately scheduled for execution.

(c) If the execution of program terminates, another program is

immediately scheduled for execution.
(A) a (B) a and b

(C) a and c (D) a, b and c

Answer: b
 GATE-CS-2001
Where does the swap space reside?
(A) RAM
(B) Disk
(C) ROM
(D) On-chip cache
Answer: b
TOPIC 2: CPU SCHEDULING
 What is Process Scheduling?
Process Scheduling
• Process or CPU Scheduling can be defined as a set of
policies and mechanisms which controls the order in
which the work to be done is completed.
• Whenever the CPU becomes idle, it is the job of the
CPU Scheduler to select another process from the
ready queue to run next.
• The selection process will be carried out by the CPU
scheduler.
Goal of CPU Scheduling
 CPU Scheduling-Terms and Terminology
CPU Utilization : A scheduling algorithm should be designed so that
CPU remains busy as possible. It should make efficient use of CPU
Throughput :Number of processes completed per unit time.
Arrival Time: Time at which the process arrives in the ready queue.
Completion Time: Time at which process completes its execution.
Burst Time: Time required by a process for CPU execution.
Response time: The–amount of time it takes from when a request was
submitted until the first response is produced
 CPU Scheduling-Terms and Terminology
Turn Around Time: Time Difference between completion time
and arrival time.

Turn Around Time(TAT) = Completion Time(CT) – Arrival

Time(AT)

Waiting Time(W.T): Time Difference between turn around time

and burst time.

Waiting Time(WT)= Turn Around Time(TAT) – Burst Time(BT)

 Types of CPU Scheduling
1. First Come First Serve (FCFS)
2. Shortest-Job-First (SJF) Scheduling
3. Preemptive Shortest Job First or Shortest
Remaining Time
4. Non-preemptive Priority Scheduling
5. Preemptive Priority Scheduling
6. Round Robin Scheduling
 GATE-CS-2001
Consider a set of n tasks with known runtimes
r1,r2,……..rn to be run on a uniprocessor machine.
Which of the following processor scheduling
algorithms will result in the maximum throughput ?
• (A) Round-Robin
• (B) Shortest-Job-First
• (C) Highest-Response-Ratio-Next
• (D) First-come-First-Served
Answer: B
 GATE-CS-2002
Which of the following scheduling algorithms is non-
preemptive?
1. Round Robin
2. First-In First-Out
3. Multilevel Queue Scheduling
4. Multilevel Queue Scheduling with Feedback
Answer: b
 GATE-CS-2010
Which of the following statements are true ?
I.Shortest remaining time first scheduling may
cause starvation
II. Preemptive scheduling may cause starvation
III.Round robin in better than FCFS in terms of
response time
(A) I only (B) I and III only (C) II and III only (D) I, II and III
Answer: d
 ISRO Question

Which of the following statement(s) is/are not correct in the context

of CPU scheduling?
1.Turnaround time includes waiting time
2.The goal is to only maximize CPU utilization and minimize throughput
3.Round-robin policy can be used even when the CPU time required by
each of the processes is not known apriori
4.Implementing pre-emptive scheduling needs hardware support
Answer: B
ISRO 2020

Which of the following algorithms defines time quantum?

A.shortest job scheduling algorithm
B.round robin scheduling algorithm
C.priority scheduling algorithm
D.multilevel queue scheduling algorithm
 1. First Come First Serve

• It is the simplest algorithm to implement. The

process which come first will use the CPU first.
• It is the non-preemptive type of scheduling.
 FCFS Scheduling Algorithm
Consider the following FCFS scheduling algorithm. In the
Following schedule, there are 5 processes with process ID
P0, P1, P2, P3 and P4. The processes and their respective
Arrival and Burst time are given in the following table. Find
out the average waiting time Arrival
Process Burst Time
Time
P0 0 2
P1 1 6
P2 2 4
P3 3 9
P4 4 12
Gantt chart

Burst
Arrival Completion Turn Around Waiting
Process Time
Time(AT) Time(CT) Time(TAT) Time(WT)
(BT)
P0 0 2
P1 1 6
P2 2 4
P3 3 9
P4 4 12
Consider the following CPU processes with arrival times (in milliseconds) and length of
CPU bursts (in milliseconds) as given below: Process Arrival Time Burst Time
P1 0 3
P2 1 6
P3 4 4
P4 6 2
 Shortest Job First (SJF)
• The job with the shortest burst time will get the CPU first. The
lesser the burst time, the sooner will the process get the CPU. It
is the non-preemptive type of 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 algorithm also knows as Shortest Job
Next (SJN) .
• This scheduling method can be preemptive or non-preemptive.
• To successfully implement it, the burst time/duration time of
the processes should be known to the processor in advance,
which is practically not feasible all the time
• This is the best approach to minimize waiting time.
 Example-Shortest-Job-First (SJF)
Consider the following four processes with the arrival time and length of
CPU burst given in milliseconds
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
The average waiting time for SJF scheduling algorithm is .................
(1) 6.5 ms
(2) 7.5 ms
(3) 6.75 ms
(4) 7.75 ms
Gantt chart

PROCESS ARRIVAL TIME BURST TIME COMPLETION TURNAROUND TIME WAITING

TIME TIME

P1 0 8
P2 1 4
P3 2 9
P4 3 5
TOTAL WAITING TIME
 WORK OUT FOR YOU
An operating system uses shortest Job first scheduling
algorithm of processes. Consider the following set of processes
with their arrival times and CPU burst times (in milliseconds):
Process Arrival Time Burst Time
P1 0 12
P2 2 4
P3 3 6
P4 8 5

The average waiting time (in milliseconds) of the processes is .

(A) 4.5
(B) 5.0
(C) 5.5
(D) 9.0
 P1 P2 P4 P3

0 12 16 21 27
Process Arrival Time Burst Time Completion Turnaround Waiting
Time Time Time
P1 0 12 12 12 0
P2 2 4 16 14 10
P3 3 6 27 24 18
P4 8 5 21 13 8
36

Average waiting time=36/4

=9
 Shortest Remaining Time First
It is the preemptive form of SJF. In this algorithm, the OS
schedules the Job according to the remaining time of the
execution.
Shortest Remaining Time First (SRTF), is a scheduling
method that is a preemptive version of Shortest Job First(SJF)
scheduling.
Shortest remaining time is advantageous because short
processes are handled very quickly
SRTF and Shortest Job First scheduling algorithms are
suffered by starvation problem.
 Example-SRTF (Preemptive SJF)
Consider the following four processes with the arrival time and length of CPU burst
given in milliseconds :
Process Arrival Time Burst Time
P1 0 8
P2 1 4
P3 2 9
P4 3 5
The average waiting time for preemptive SJF scheduling algorithm is .................
(1) 6.5 ms
(2) 7.5 ms
(3) 6.75 ms
(4) 9.0 ms
Gantt chart

PROCESS ARRIVAL BURST COMPLETION TURNAROUND TIME WAITING

TIME TIME TIME TIME
P1 0 8
P2 1 4
P3 2 9
P4 3 5
TOTAL WAITING TIME
 WORK OUT FOR YOU-NTA NET
Consider the set of processes with arrival time(in
milliseconds), CPU burst time (in milliseconds)
Process Arrival Time Burst Time
P1 0 12
P2 2 4
P3 3 6
P4 8 5
The average waiting time (in milliseconds) of the processes using
Shortest Remaining Time first scheduling is .
(A) 4.5
(B) 5.0
(C) 5.5
(D) 6.5
 Solutions
10
P1 P2 P3 P4 P1

0 2 6 12 17 27

Process Arrival Burst Time Completion Time Turnaround Time Waiting Time
Time
P1 0 12 27 27 15
P2 2 7 6 4 0
P3 3 6 12 9 3
P4 8 5 17 9 4
22

Average waiting time=22/4

=5.5
 ISRO 2020

Three CPU-bound tasks, with execution times of 15,12 and 5 time units
respectively arrive at times 0,t and 8, respectively. If the operating system
implements a shortest remaining time first scheduling algorithm, what should
be the value of t to have 4 context switches? Ignore the context switches at
time 0 and at the end.
A.0<t<3
B.t=0
C.t<=3
D.3<t<8
Answer: A
 GATE CS 2020
Consider the following set of processes, assumed to have arrived at
time 0. Consider the CPU scheduling algorithms Shortest Job First
(SJF) and Round Robin (RR). For RR, assume that the processes
are scheduled in the order P1, P2, P3, P4.

If the time quantum for RR is 4 ms, then the absolute value of the difference
between the average turnaround times (in ms) of SJF and RR (round off to 2
decimal places) is _________ .
Note – This question was Numerical Type.
(A) 5.0
(B) 5.25
(C) 5.50
(D) 5.75
 Gate CS 2012-Workout
Consider the 3 processes, P1, P2 and P3 shown in the table.
Process Arrival time Time Units Required
P1 0 5
P2 1 7
P3 3 4
The completion order of the 3 processes under the policies FCFS and
RR2 (round robin scheduling with CPU quantum of 2 time units) are
 (A)
FCFS: P1, P2, P3
RR2: P1, P2, P3
(B)
FCFS: P1, P3, P2
RR2: P1, P3, P2
(C)
FCFS: P1, P2, P3
RR2: P1, P3, P2
(D)
FCFS: P1, P3, P2
RR2: P1, P2, P3