## CPU-Scheduling

 Question 1

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): The average waiting time (in milliseconds) of the processes is

 A 5.5 B 5.6 C 5.7 D 5.8
Operating-Systems       CPU-Scheduling       GATE 2014 [Set-3]
Question 1 Explanation: WT - Waiting Time
CT - Completion Time
TAT - Turn Around Time
TAT = CT - AT < br> WT = TAT - BT
Gantt chart using Shortest remaining time first, Avg. WT = 15+0+3+4/4 = 22/4 = 5.5
 Question 2

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?

 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.
Operating-Systems       CPU-Scheduling       GATE 2013
Question 2 Explanation:
The given algorithm is equivalent to the round robin algorithm with time quantum T units.
 Question 3

Consider a disk system with 100 cylinders. The requests to access the cylinders occur in following sequence:

`    4, 34, 10, 7, 19, 73, 2, 15, 6, 20 `

Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 1ms to move from one cylinder to adjacent one and shortest seek time first policy is used?

 A 95 ms B 119 ms C 233 ms D 276 ms
Operating-Systems       CPU-Scheduling       GATE 2009
Question 3 Explanation:
The given sequence is
4, 34, 10,7, 19, 73, 2, 15, 6, 20
Arrange the sequence in order
2, 4, 6, 10, 15, 19, 20, 34, 73 ⇒ 1 ms to move from one cylinder to adjacent one
⇒ (16*1)+(14*1)+(1*1)+(4*1)+(5*1)+(3*1)+(1*1)+(2*1)+(2*1)+(71*1)
⇒ 16+14+1+4+5+3+1+2+2+71
⇒ 119 ms
 Question 4

Which scheduling policy is most suitable for a time shared operating system?

 A Shortest Job First B Round Robin C First Come First Serve D Elevator
Operating-Systems       CPU-Scheduling       GATE 1995
Question 4 Explanation:
In Round robin, we use the time quantum based on this execution can be done. Then it is said to be time shared operating system.
 Question 5

The sequence …………… is an optimal non-preemptive scheduling sequence for the following jobs which leaves the CPU idle for …………… unit(s) of time. A {3,2,1),1 B (2,1,3},0 C {3,2,1),0 D {1,2,3},5
Operating-Systems       CPU-Scheduling       GATE 1995
Question 5 Explanation:
Here, in option (B) and (C) they have given CPU idle time is 0 which is not possible as per schedule (B) and (C).
So, (B) and (C) will be eliminated.
Now in (A) and (D):
For r(A), So, idle time is between 0 to 1 which in case of option (A).
For option(D), We can see there is no idle time at all, but in option given idle time is 5, which is not matching with our chart. So option (D) is eliminated.
Therefore, the correct sequence is option (A).
 Question 6
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.
 A 12
Operating-Systems       CPU-Scheduling       GATE 2021 CS-Set-1       Video-Explanation
Question 6 Explanation:
Minimum average waiting time amongst non-preemptive scheduling is given by SJF. So, avg waiting time = (0+10+26)/3 = 12 ms.
 Question 7
There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned to a computer such that:
• The fastest computer gets the toughest job and the slowest computer gets the easiest job.
• Every computer gets at least one job.
The number of ways in which this can be done is ______
 A 65
Operating-Systems       CPU-Scheduling       GATE 2021 CS-Set-1       Video-Explanation
Question 7 Explanation:

Let the levels be  1,2,3,4,5,6. (1 is the least difficult, 6 is the most difficult level)
Let the computers be F,M,S( fast, medium, slow).

As per the given constraint,  1 must be given to F and 6 must be given to S.
Now we are left with 2,3,4,5 and  F being assigned 1, S being assigned 6 and M being assigned none.
Another constraint is that, every computer must be assigned atleast one.
So compute with assigning one job to M, two jobs to M, three jobs to M and four jobs to M.
Assigning one job to M: we can assign 1 out of 4 jobs in (4C1 ways) and remaining 3 jobs to F,S in  2*2*2 = 8  ways. (each job has two options, either F or S),

Assigning two jobs to M: we can select two jobs from 4 in 4C2 ways and remaining 2 can be distributed to  F and S in  2*2 ways ( each job has two options either F or S)

Assigning three jobs to M: we can select 3 out of 4 in 4C3 ways remaining can be distributed to F,M in 2 ways.

Assigning 4 jobs to M: it can be done in only one way.

Total : 4c1*8  +  4C2* 4  + 4C3*2 + 1

= 32+24+8+1

=65

 Question 8
Which of the following statement(s) is/are correct in the context of CPU scheduling?
 A Implementing preemptive scheduling needed hardware support. B Turnaround time includes waiting time C Round-robin policy can be used even when the CPU time required by each of the processes is not known apriori. D The goal is to only maximize CPU utilization and minimize throughput.
Operating-Systems       CPU-Scheduling       GATE 2021 CS-Set-2       Video-Explanation
Question 8 Explanation:
1. True. Preemptive scheduling needs hardware support such as a timer
2. True. Turnaround time = Burst time + Waiting time
3. True, RR assigns qunatume to each process equally. Hence, it is not required to know burst size apriori
4. False. Maximize CPU utilization and throughput, and minimize waiting time etc.
 Question 9
Which one or more of the following CPU scheduling algorithms can potentially cause starvation?
 A First-in First-Out B Round Robin C Priority Scheduling D Shortest Job First
Operating-Systems       CPU-Scheduling       GATE 2023       Video-Explanation
 Question 10
Round Robin schedule is essentially the preemptive version of
 A FIFO B Shortest job first C Shortest remaining time D Longest remaining time
Operating-Systems       CPU-Scheduling       ISRO-2007
Question 10 Explanation:
FIFO is when implemented in preemptive version, it acts like round-robin algorithm.
 Question 11
On a system using non-preemptive scheduling, processes with expected run times of 5, 18, 9 and 12 are in the ready queue. In what order should they be run to minimize wait time?
 A 5, 12, 9, 18 B 5, 9, 12, 18 C 12, 18, 9, 5 D 9, 12, 18, 5
Operating-Systems       CPU-Scheduling       ISRO-2007
Question 11 Explanation:
The processes should execute in SJF manner to get the lowest waiting time. So, the order should be 5, 9, 12, 18.
 Question 12
Feedback queues
 A are very simple to implement B dispatch tasks according to execution characteristics C are used to favour real time tasks D require manual intervention to implement properly
Operating-Systems       CPU-Scheduling       ISRO-2007
Question 12 Explanation:
n a multilevel queue-scheduling algorithm, processes are permanently assigned to a queue on entry to the system. Processes do not move between queues. This setup has the advantage of low scheduling overhead, but the disadvantage of being inflexible.

Multilevel feedback queue scheduling, however, allows a process to move between queues. The idea is to separate processes with different CPU-burst characteristics. If a process uses too much CPU time, it will be moved to a lower-priority queue. Similarly, a process that waits too long in a lower-priority queue may be moved to a higher-priority queue. This form of aging prevents starvation.
 Question 13
Four jobs to be executed on a single processor system arrive at time 0 in the order A, B, C, D . Their burst CPU time requirements are 4, 1, 8, 1 time units respectively. The completion time of A under round robin scheduling with time slice of one time unit is
 A 10 B 4 C 8 D 9
Operating-Systems       CPU-scheduling       ISRO CS 2008
Question 13 Explanation:
1. All processes are arrived at time 0.
2. Algorithm used for scheduling is round robin with time quantum of one unit time.
3. The order of execution of the processes A B C D A C A C A,C,C,C,C,C
4. After 8 context switches, process A completes it execution So the completion time is 9
There are 13 questions to complete.

Register Now