Process-Scheduling

Question 1

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

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
2
B
7
C
1
D
4
       Operating-Systems       Process-Scheduling       GATE 2019       Video-Explanation
Question 1 Explanation: 
This is the Gantt chart till time = 4 units

At this point P4 arrives with burst 'Z' & P3 is in queue with burst 3.
P1 & P2 have executed with P1 incurred delay 1unit & P2 0units.
Hence, Avg = 0+1+x/4 =1
⇒ x=3, the next delay should be 3. It would happen if assume Z=2.
It executes and completes at 6.
P3 will wait totally for 3units.
Hence, Avg=1.

Z=2
Question 2

Consider the following CPU processes with arrival times (in milliseconds) and length of CPU bursts (in milliseconds) as given below:

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
3
B
4
C
5
D
6
       Operating-Systems       Process-Scheduling       GATE 2017 [Set-1]       Video-Explanation
Question 2 Explanation: 
Question 3

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.

The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling algorithm is __________.

A
29
B
30
C
31
D
32
       Operating-Systems       Process-Scheduling       GATE 2017 [Set-2]       Video-Explanation
Question 3 Explanation: 

Waiting Time = 0 + (33 - 5) + (40 - 2) + (49 - 12) + (51 - 9) = 145
Average waiting time: 145/5 = 29
Question 4

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?

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
       Operating-Systems       Process-Scheduling       GATE 2016 [Set-1]       Video-Explanation
Question 4 Explanation: 
From the above question, we can get the following information.
We can consider an arbitrary set of CPU-bound processes with unequal CPU burst lengths submitted at the same time to a computer system.
We have to choose the appropriate process scheduling algorithms, which would minimize the average waiting time in the ready queue.
Waiting time is the time for which process is ready to run but not executed by CPU scheduler.
In all CPU Scheduling algorithms, shortest job first is optimal.
It gives minimum turnaround time, minimum average waiting time and high throughput and the most important thing is that shortest remaining time first is the preemptive version of shortest job first.
This scheduling algorithm may lead to starvation because if the short processes are added to the CPU scheduler continuously then the currently running process will never be able to execute as they will get pre-empted but here all the processes are arrived at same time so there will be no issue such as starvation.
SRTF would be same as SJF.
So, A is the answer. Shortest remaining time first.
Question 5

Consider the following processes, with the arrival time and the length of the CPU burst given in milliseconds. The scheduling algorithm used is preemptive shortest remaining-time first.

The average turn around time of these processes is _________ milliseconds.

A
8.25
B
8.26
C
8.27
D
8.28
       Operating-Systems       Process-Scheduling       GATE 2016 [Set-2]       Video-Explanation
Question 5 Explanation: 
Here the scheduling algorithm used is preemptive shortest remaining-time first.
To answer the question we need to design the gantt chart:

In this algorithm, the processes will be scheduled on the CPU which will be having least remaining burst time.
Turnaround Time (TAT) = Completion Time (CT) - Arrival Time (AT)
TAT for P1 = 20 - 0 = 20,
TAT for P2 = 10 - 3 = 7,
TAT for P3 = 8 - 7 = 1,
TAT for P4 = 13 - 8 = 5.
Total TAT = 20 + 7 + 1 + 5 = 33 / 4 = 8.25 (Avg. TAT)
Question 6

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.

A
13
B
12
C
15
D
16
       Operating-Systems       Process-Scheduling       GATE 2015 [Set-1]
Question 6 Explanation: 
All the processes or tasks are available at the begining of 1st millisecond, means at t=0. So, Gantt chart will be as follows:

∴ At the end of 12 milliseconds, 1st instance of T3 will complete its execution.
Question 7

The maximum number of processes that can be in Ready state for a computer system with n CPUs is

A
n
B
n2
C
2n
D
Independent of n
       Operating-Systems       Process-Scheduling       GATE 2015 [Set-3]
Question 7 Explanation: 
Number of processes which are in running processes will be atmost n as there are n processors.
Maximum number of processes that will be in ready state is independent of number of processors.
Question 8

For the processes listed in the following table, which of the following scheduling schemes will give the lowest average turnaround time?

A
First Come First Serve
B
Non-preemptive Shortest Job First
C
Shortest Remaining Time
D
Round Robin with Quantum value two
       Operating-Systems       Process-Scheduling       GATE 2015 [Set-3]
Question 8 Explanation: 

FCFS:

TAT for A = completion time(A) - AT(A) = 3 - 0 = 3
TAT of B = 9 - 1 = 8
TAT of C = 13 - 4 = 9
TAT of D = 15 - 6 = 9
∴ Avg. TAT = 29/4
SJF:

TAT of A = 3 - 0 = 3
TAT of B = 9 - 1 = 8
TAT of C = 15 - 4 = 11
TAT of D = 11 - 6 = 5
∴ Avg. TAT = 27/4
SRTF:

TAT of A = 3 - 0 = 3
TAT of B = 15 - 1 = 14
TAT of C = 8 - 4 = 4
TAT of D = 10 - 6 = 4
∴ Avg. TAT = 25/4
RR:

TAT of A = 5 - 0 = 5
TAT of B = 15 - 1 = 14
TAT of C = 13 - 4 = 9
TAT of D = 11 - 6 = 5
∴ Avg. TAT = 33/4
∴ SRTF has lowest Avg. TAT.
Question 9

Consider the following set of processes that need to be scheduled on a single CPU. All the times are given in milliseconds.

Using the shortest remaining time first scheduling algorithm, the average process turnaround time (in msec) is ________.

A
7.2
B
7.3
C
7.4
D
7.5
       Operating-Systems       Process-Scheduling       GATE 2014 [Set-1]
Question 9 Explanation: 
Using SRTF:

TAT(A) = 8-0 = 8, TAT(B)= 5-3=2, TAT(C)= 12-5=7, TAT(D)= 21-7= 14, TAT(E)=15-10=5
Average turnaround time = 8+2+7+14+5/ 5 = 7.2ms
Question 10

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 tc CPU milliseconds and then initiates a single I/O operation that lasts for tio 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:

 Process id      tc      tio
     A        100 ms    500 ms
     B        350 ms    500 ms
     C        200 ms    500 ms

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
1000
B
1001
C
1002
D
1003
       Operating-Systems       Process-Scheduling       GATE 2014 [Set-2]
Question 10 Explanation: 
Gantt chart is shown below:

So 'C' completes its I/O at 1000 time units.
Question 11

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
       Operating-Systems       Process-Scheduling       GATE 2012
Question 11 Explanation: 
FCFS is - P1, P2, P3
FCFS is clear.
RR Queue: In RR queue time slot is of 2 units.
Processes are assigned in following order
P1, P2, P1, P3, P2, P1, P3, P2, P2
This question used the ready queue concept. At t=2, P2 starts and P1 is sent to the ready queue and at t=3 P3 arrives so then the job P3 is queued in the ready queue after P1. So at t=4, again P1 is executed then P3 is executed for the first time at t=6.
RR2: P1, P3, P2
So option C.
Question 12

Consider the following table of arrival time and burst time for three processes P0, P1 and P2.

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
5.0 ms
B
4.33 ms
C
6.33 ms
D
7.33 ms
       Operating-Systems       Process-Scheduling       GATE 2011
Question 12 Explanation: 

CT = Completion time
TAT = Turn Around Time
WT = Waiting Time
TAT = CT - AT
WT = TAT - BT
Gantt Chart using pre-emptive shortest job first scheduling algorithm,

Avg. WT = 4+0+11/3 = 5ns
Question 13

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 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
       Operating-Systems       Process-Scheduling       GATE 2010
Question 13 Explanation: 
- In SRTF longer bursts will suffer from starvation.
- Pre-emptive scheduling causes starvation (for example lower priority jobs are waiting).
- Best Response time is given by RR.
Question 14

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.
    III. The OS uses preemptive scheduling.
    IV. The OS uses non-preemptive scheduling.

Which of the above statements are TRUE?

A
I and II
B
I and III
C
II and III
D
II and IV
       Operating-Systems       Process-Scheduling       GATE 2009
Question 14 Explanation: 
Statement I is false, if a process makes a transition D, then it result to perform a transition B immediately not A.
Statement II is true, a process can move to ready state when I/O completes irrespective of other process being in running state or not.
Statement III is true, the transition C, represents preemptive scheduling.
Statement IV is false, because it is preemptive scheduling.
Correct Answer is Option-C (II & III are true).
Question 15

An operating system uses Shortest Remaining Time first (SRT) process scheduling algorithm. Consider the arrival times and execution times for the following processes:

 
        Process     Execution time     Arrival time
          P1             20                0
          P2             25                15
          P3             10                30
          P4             15                45

What is the total waiting time for process P2?

A
5
B
15
C
40
D
55
       Operating-Systems       Process-Scheduling       GATE 2007
Question 15 Explanation: 

Waiting time for process P2 = TAT - Execution time
= Completion time - AT - ET
= 55 - 15 - 25
= 15
Question 16

Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end.

A
1
B
2
C
3
D
4
       Operating-Systems       Process-Scheduling       GATE 2006
Question 16 Explanation: 

Total no.of context switches is 2.
Question 17

Consider three processes (process id 0, 1, 2 respectively) with compute time bursts 2, 4 and 8 time units. All processes arrive at time zero. Consider the longest remaining time first (LRTF) scheduling algorithm. In LRTF ties are broken by giving priority to the process with the lowest process id. The average turnaround time is:

A
13 units
B
14 units
C
15 units
D
16 units
       Operating-Systems       Process-Scheduling       GATE 2006
Question 17 Explanation: 
Algorithm: LRTF (Longest Remaining Time First)

Avg TAT = 12+13+14/3 = 39/3 = 13 units
Question 18

Consider three processes, all arriving at time zero, with total execution time of 10, 20 and 30 units, respectively. Each process spends the first 20% of execution time doing I/O, the next 70% of time doing computation, and the last 10% of time doing I/O again. The operating system uses a shortest remaining compute time first scheduling algorithm and schedules a new process either when the running process gets blocked on I/O or when the running process finishes its compute burst. Assume that all I/O operations can be overlapped as much as possible. For what percentage of time does the CPU remain idle?

A
0%
B
10.6%
C
30.0%
D
89.4%
       Operating-Systems       Process-Scheduling       GATE 2006
Question 18 Explanation: 

Total time needed to complete the execution = 47
Idle time = 2+3 = 5
Percentage of Idle time = 5/47 × 100 =10.6%
Question 19

Consider the following set of processes, with the arrival times and the CPU-burst times given in milliseconds.

  Process   Arrival Time    Burst Time
     P1          0              5
     P2          1              3
     P3          2              3
     P4          4              1 

What is the average turnaround time for these processes with the preemptive shortest remaining processing time first (SRPT) algorithm?

A
5.50
B
5.75
C
6.00
D
6.25
       Operating-Systems       Process-Scheduling       GATE 2004
Question 19 Explanation: 
Uses SRPT Algorithm:

Avg. TAT = 12+3+6+1/4 = 22/4 = 5.50
Question 20

A uni-processor computer system only has two processes, both of which alternate 10ms CPU bursts with 90ms I/O bursts. Both the processes were created at nearly the same time. The I/O of both processes can proceed in parallel. Which of the following scheduling strategies will result in the least CPU utilization (over a long period of time) for this system?

A
First come first served scheduling
B
Shortest remaining time first scheduling
C
Static priority scheduling with different priorities for the two processes
D
Round robin scheduling with a time quantum of 5 ms
       Operating-Systems       Process-Scheduling       GATE 2003
Question 20 Explanation: 
We have two processes P and Q. These process have 10ms CPU burst time and 90ms I/O bursts.
(i) FCFS:
0-10: Process 1 can execute
10-20: Process 2 can execute
100-110: Process 1 Terminate
110-120: Process 2 Terminate
CPU utilization = 20/100 [In every 100ms it utilizes]
=20%
(ii) SRTF: can process P and Q same as FCFS
then CPU utilization = 20%
(iii) Round robin: with TQ-5
0-5: Process P1
5-10: Process P2
10-15: Process P1
15-20: Process P2
105-110: Process P1
110-115: Process P2
CPU utilization = 20/105 = 19.5
Question 21

Which of the following scheduling algorithms is non-preemptive?

A
Round Robin
B
First-In First-Out
C
Multilevel Queue Scheduling
D
Multilevel Queue Scheduling with Feedback
       Operating-Systems       Process-Scheduling       GATE 2002
Question 21 Explanation: 
First-in first-out scheduling algorithm is non-preemptive. In this whichever the process enter into ready queue first that will be served first.
There are 21 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access