Previous Year Questions: CPU Scheduling | Operating System - Computer Science Engineering (CSE) PDF Download

Q1: Consider a single processor system with four processes A, B, C, and D, represented as given below, where for each process the first value is its arrival time, and the second value is its CPU burst time.  (2024 SET 2)
A (0, 10), B (2, 6), C (4, 3), and D (6, 7).
Which one of the following options gives the average waiting times when preemptive Shortest Remaining Time First (SRTF) and Non-Preemptive Shortest Job First (NP-SJF) CPU scheduling algorithms are applied to the processes?
(a) SRTF = 6, NP - SJF = 7
(b) SRTF = 6, NP- SJF = 7.5
(c) SRTF = 7, NP- SJF = 7.5
(d) SRTF = 7, NP- SJF = 8.5
Ans: (b)
Sol: SJF CPU scheduling:
 

SRTF CPU scheduling: 

Note:

• Turnaround time is calculated as (Burst time -arrival time)
• Waiting time is calculated as (Turnaround time-Burst time )

Option (B) is correct

Q2: Which one or more of the following CPU scheduling algorithms can potentially cause starvation?  (2023)
(a) First-in First-Out
(b) Round Robin
(c) Priority Scheduling
(d)Shortest Job First
Ans: (c, d)
Sol: The possible responses are (C,D), both of which are supported by standard resources.
Shortest Job First and Priority Scheduling are vulnerable to starvation.
Shortest Job First (SJF): New shorter jobs may continue to emerge.
Priority: High-level positions may continue to emerge.
Round Robin will never result in starvation because each job will be assigned a time slot after a FIXED time quantum.
Because the time quantum is finite, every job will eventually get a chance to run after a finite amount of time. It should be noted that the time quantum can be set to a large value, such as 10 minutes, 10 years, or even 100 years, but as long as it is finite, every job will get a chance to execute.

Q3: Consider four processes P, Q, R, and S scheduled on a CPU as per round robin algorithm with a time quantum of 4 units. The processes arrive in the order P, Q, R, S, all at time t = 0. There is exactly one context switch from S to Q, exactly one context switch from R to Q, and exactly two context switches from Q to R. There is no context switch from S to P. Switching to a ready process after the termination of another process is also considered a context switch. Which one of the following is NOT possible as CPU burst time (in time units) of these processes?  (2022)
(a) P = 4, Q = 10, R = 6, S = 2
(b) P = 2, Q = 9, R = 5, S = 1
(c) P = 4, Q = 12, R = 5, S = 4
(d) P = 3, Q = 7, R = 7, S = 3
Ans: (d)
Sol: Round Robin QUEUE :--  P, Q, R, S, P, Q, R, S, P, Q, R, S…..
Given that processes arrived in the order P,Q,R and S.

1. Switching to ready processes after termination of currently executing process also a context switch.
2. There is no context switch from S to P. ( Therefore P should be complete with in 1 TQ )
3. There are exactly two context switches from Q to R ( Therefore Q and R both should requires more than 1 TQ )
4. There is exactly one context switch from R to Q ( Therefore Q require more time than R )
5. Exactly one context switch  from R to S. ( Therefore S should be complete with in 1 TQ otherwise another CS from R to S required.)
6. Exactly one context switch from S to Q

Accumulating all the above points
QUEUE :---  P,Q,R,S,Q,R,Q
Given that time quantum = 4.
0 < P_BT ≤ 4
0 <S_BT ≤ 4
8 < Q_BT
4 < R_BT ≤ 8
 option D

Q4: Which of the following statement(s) is/are correct in the context of CPU scheduling? (2021 SET 2)
 [MSQ] 
(a) Turnaround time includes waiting time
(b) The goal is to only maximize CPU utilization and minimize throughput
(c) Round-robin policy can be used even when the CPU time required by each of the processes is not known apriori
(d) Implementing preemptive scheduling needs hardware support
Ans: (a, c, d)
Sol:
A. Turnaround time includes waiting time
 TRUE.  Turnaround = Waiting  Time + Burst Time
B. The goal is to only maximize CPU utilization and minimize throughput
FALSE. CPU scheduling must aim to maximize CPU utilization as well as throughput. Throughput of CPU scheduling is defined as the number of processes completed in unit time. SJF scheduling gives the highest throughput.
C. Round-robin policy can be used even when the CPU time required by each of the processes is not known apriori
TRUE. Round-robin scheduling gives a fixed time quantum to each process and for this there is no requirement to know the CPU time of the process apriori (which is not the case say for shortest remaining time first).
D. Implementing preemptive scheduling needs hardware support
TRUE. Preemptive scheduling needs hardware support to manage context switch which includes saving the execution state of the current process and then loading the next process.
Correct Answer: A;C;D

Q5: Three processes arrive at time zero with CPU bursts of 16, 20 and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is _____________ milliseconds.  (2021 SET 1)
(a) 18.66
(b) 12
(c) 15
(d) 9
Ans: (b)
Sol: We get minimum achievable average waiting time using SJF scheduling.
Lets just name these processes for explanation purpose only as A = 16, B = 20 and C = 10.
Order them according to burst time as  C < A < B
C will not wait for anyone,  schedule first ( wait time = 0)
A will wait for only C (wait time = 10)
B will wait for both C and A (wait time = 10 + 16)
Average wait time
No need to make any table or chart.
This is all for explaining purpose, you can actually ans this within 10-15 sec after reading the complete question.

Q6: 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 P₁, P₂, P₃, P_{4  (2020) 
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_______}
(a) 10.5
(b) 15.75
(c) 5.25
(d) 4.25
Ans: (c)
Sol: 
SJF:

Average Turn-Around Time :
RR:

Average Turn-Around Time :
Absolute Difference =|10.5 - 15.75 | =5.25.

Q7:Consider the following four processes with arrival times (in milliseconds) and their length of CPU burst (in milliseconds) as shown below:  (2019)

These processes are run on a single processor using preemptive Shortest Remaining Time First scheduling algorithm. If the average waiting time of the processes is 1 millisecond, then the value of Z is __________.
(a) 1
(b) 2
(c) 3
(d) 4
Ans: (b)
Sol: 

Till t = 4 , the waiting time of P1 = 1 and P2 = 0 and P3 = 1 but P 3 has not started yet.
Case  1:
Note that if P4 burst time is less than P3 then P4 will complete and after that P3 will complete. Therefore Waiting time of P4 should be 0 . And total waiting time of P3 = 1 + ( Burst time of P4 ) because until P4 completes P3 does not get a chance.
Then average waiting time

2+x / 4 = 1 ⇒ x = 2.
Case 2:
Note that if P4 burst time is greater than P3 then P4 will complete after P3 will complete.
Therefore, Waiting time of P3 remains the same. And total waiting time of P4 = ( Burst time of P3 ) because until P3 completes P4 does not get a chance.
Then average waiting time =
5 / 4 ≠ 1  ⇒ This case is invalid.
Correct Answer: 2

Q8: Consider the set of processes with arrival time (in milliseconds). CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes have I/O burst time.  (2017 SET 2) 

The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling algorithm is __________
(a) 25
(b) 29
(c) 31
(d) 34
Ans: (b)
Sol: Gantt Chart for above problem looks like :

Waiting Time =  Completion time − Arrival time  − Burst Time
∑ AT = 0 + 5 +12 + 2 + 9 = 28
∑ BT = 11 + 28 + 2 + 10 + 16 =67
∑ CT= 67 + 51 + 49 + 40 + 33 = 240
Waiting time = 240  - 28 - 67 = 145
Average Waiting Time = 145 / 5 = 29 msec.

Q9: Consider the following CPU processes with arrival times (in milliseconds) and length of CPU burst (in milliseconds) as given below:  (2017 SET 1)

If the pre-emptive shortest remaining time first scheduling algorithm is used to schedule the processes., then the average waiting time across all processes is ________ milliseconds.
(a) 1
(b) 2
(c) 3
(d) 4
Ans: (c)
Sol: 

Gantt Chart

Average Waiting Time = = 3 milliseconds

Q10: Consider the following processes, with the arrival time and the length of the CPU burst given in milli seconds. The scheduling algorithm used is preemptive shortest remaining-time first.  (2016 SET 2) 

The average turn around time of these processes is milliseconds.
(a) 6.2
(b) 7.2
(c) 8.2
(d) 6.9
Ans: (c)
Sol: SRTF Preemptive hence,

Average TAT =

Q11: Consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system. Which one of the following process scheduling algorithms would minimize the average waiting time in the ready queue?  (2016 set 1) 
(a) Shortest remaining time first
(b) Round-robin with time quantum less than the shortest CPU burst
(c) Uniform random
(d) Highest priority first with priority proportional to CPU burst length
Ans: (a)
Sol:  Answer should be (A) SRTF
SJF minimizes average waiting time. Probably optimal.
Now, here as all processes arrive at the same time, SRTF would be same as SJF. and hence, the answer.

Q12:For the processes listed in the following table, which of the following scheduling schemes will give the lowest average turnaround time?  (2015 SET 3) 

(a) First Come First Serve
(b) Non-preemptive Shortest Job First
(c) Shortest Remaining Time
(d) Round Robin with Quantum value two
Ans: (c)
Sol: Turn Around Time  = Completion Time  − Arrival Time
FCFS
Average turn around time
= [3 for A+ (2 + 6) for B + (5+ 4) for C+ (7 + 2) for D] / 4 = 7.25
Non-preemptive Shortest Job First
Average turn around time
= [3 for A+ (2 + 6) for B + (3+ 2) for D+ (7 + 4) for D] / 4 = 6.75
Shortest Remaining Time
Average turn around time
= [3 for A + (2 + 1) for B + (0+ 4) for C + (2+ 2) for D +(6 + 5) for  remaining  B
Round Robin
Average turn around time =
[2 for A (B comes after 1)
+(1+2) for B {C comes}
+(2+1) for A (A finishes after 3 cycles with turnaround time of 2 + 3 = 5)
+(1+2) for C {D comes}
+(3+2) for B
+(3+2) for D (D finishes with turnaround time of 3 + 2 = 5)
+(4+2) for C (C finishes with turnaround time of 3 + 6 = 9)
+(4+2) for B (B finishes after turnaround time of 3 + 5 + 6= 14]
/4
= 8.25

Q13: Consider a uniprocessor system executing three tasks T1, T2 and T3, each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 milliseconds, respectively. The priority of each task is the inverse of its period, and the available tasks are scheduled in order of priority, with the highest priority task scheduled first. Each instance of T1, T2 and T3 requires an execution time of 1, 2 and 4 milliseconds, respectively. Given that all tasks initially arrive at the beginning of the 1st millisecond and task preemptions are allowed, the first instance of T3 completes its execution at the end of _____________ milliseconds.  (2015 SET 1)
(a) 10
(b) 12
(c) 13
(d) 15
Ans: (b)
Sol: Answer is 12
T₁ , T₂ and T₃ have infinite instances, meaning infinite burst times. Here, problem say Run " T₁ for 1 ms", " T₂ for 2 ms", and " T₃ for 4 ms". i.e., every task is run in parts. Now for timing purpose we consider t for the end of cycle number t

•  T₁: 0, 3, 6, 9, 12,... ∞  (T₁ repeats every 3 ms)
• T₂: 0, 7, 14, 21,... ∞  (T₂ repeats every 7 ms)
• T₃: 0, 20, 40, 60,... ∞  (T3 repeats every 20 ms)

1. Priority of T₁ = 1 / 3
2. Priority of T₂ =1/ 7
3. Priority of T₃ = 1 / 20

At t = 0, No process is available
At t =  2, T2 runs because it has higher priority than T₃ and no instance of T₁ present
At t = 4,  We have T₁ arrive again and T₃ waiting but T₁ runs because it has higher pri
At t = 5, T₃ runs because no instance of T₁ or T₂ is present
At t = 11, T₃ runs because no instance of T₁ or T₂ is present
At t = 12, T₃ continue run because no instance of T₁ or T2 is present and first instance

Q14: An operating system uses shortest remaining time first scheduling algorithm for pre-emptive scheduling of processes. Consider the following set of processes with their arrival times and CPU burst times (in milliseconds):  (2014 SET 3) 

The average waiting time (in milliseconds) of the processes is _________.
(a) 6
(b) 4
(c) 5.5
(d) 5
Ans: (c)
Sol:
Gantt Chart

Average Waiting Time  = ( 15 + 0 + 3 + 4 )/ 4 = 5.5 msec.

Q15: Calculations Three processes A, B and C each execute a loop of 100 iterations. In each iteration of the loop, a process performs a single computation that requires  t_c CPU milliseconds and then initiates a single I/O operation that lasts for  t _io  milliseconds. It is assumed that the computer where the processes execute has sufficient number of I/O devices and the OS of the computer assigns different I/O devices to each process. Also, the scheduling overhead of the OS is negligible. The processes have the following characteristics:  (2014 SET 2)

The processes A, B, and C are started at times 0, 5 and 10 milliseconds respectively, in a pure time sharing system (round robin scheduling) that uses a time slice of 50 milliseconds. The time in milliseconds at which process C would complete its first I/O operation is ___________.
(a) 500
(b) 1000
(c) 650
(d) 1150
Ans: (b)
Sol: Gantt chart : ABCABCBCBC
C completes it CPU burst at=500 mili second.
IO time =500 mili second
C completes 1st IO burst at t= 500 + 500 = 1000 ms

Q16: Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds (2014 SET 1)

Using the shortest remaining time first scheduling algorithm, the average process turnaround time (in msec) is ________.
(a) 6.5
(b) 7.2
(c) 8.6
(d) 5.6
Ans: (b)
Sol:

Average  Turnaround Time =
= 36 / 5 = 7.2
So, answer is 7.2 ms

Q17: A scheduling algorithm assigns priority proportional to the waiting time of a process. Every process starts with priority zero (the lowest priority). The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule. Which one of the following is TRUE if the processes have no I/O operations and all arrive at time zero?  (2013)
(a) This algorithm is equivalent to the first-come-first-serve algorithm.
(b) This algorithm is equivalent to the round-robin algorithm.
(c) This algorithm is equivalent to the shortest-job-first algorithm.
(d) This algorithm is equivalent to the shortest-remaining-time-first algorithm.
Ans: (b)
Sol:  (B) Because here the quanta for round robin is T units, after a process is scheduled it gets executed for T time units and waiting time becomes least and it again gets chance when every other process has completed T time units.

Q18: Consider the 3 processes, P1, P2 and P3 shown in the table.

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
Ans: (c)
Sol: FCFS First Come First Server

RR2
In Round Robin We are using the concept called Ready Queue.
Note at t = 2,

• P1 finishes and sent to Ready Queue
• P2 arrives and schedules P2

This is the Ready Queue

At t=3

• P3 arrives at ready queue

At  t = 4

• P1  is scheduled as it is the first process to arrive at Ready Queue

Option (C) is correct

Q19: Consider the following table of arrival time and burst time for three processes P0, P1 and P2.  (2011)

The pre-emptive shortest job first scheduling algorithm is used. Scheduling is carried out only at arrival or completion of processes. What is the average waiting time for the three processes?
(a) 5ms
(b) 4.33ms
(c) 6.33ms
(d) 7.33ms
Ans: (a)
Sol: Answer is (A). 5ms
Gantt Chart

Average Waiting Time=

Q20: Which of the following statements are true?  (2010) 
I. Shortest remaining time first scheduling may cause starvation
II. Preemptive scheduling may cause starvation
III. Round robin is 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
Ans: (d)
Sol:  Answer is (D).
I. In SRTF ,job with the shortest CPU burst will be scheduled first bcz of this process with large CPU burst may suffer from starvation
II. In preemptive scheduling , suppose process P1 is executing in CPU and  after some time process P2 with high priority then P1 will arrive in ready queue then P1 is preemptive  and P2 will brought into CPU for execution. In this way if process which is arriving in ready queue is of higher priority then P1, then  P1 is always preempted and it may possible that it suffer from starvation.
III. Round robin will give better response time then FCFS ,in FCFS when process is executing ,it executed upto its complete burst time, but in round robin it will execute upto time quantum.