GATE Questions & Answers of CPU Scheduling

What is the Weightage of CPU Scheduling in GATE Exam?

Total 14 Questions have been asked from CPU Scheduling topic of Operating System subject in previous GATE papers. Average marks 1.71.

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

Process P1 P2 P3 P4
Arrival time 0 1 3 4
CPU burst time 3 1 3 Z

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________.

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

Process Arrival time Burst time
P1 0 7
P2 3 3
P3 5 5
P4 6 2

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.

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.

Process Arrival time Burst Time Priority 
P1 0 11 2
P2 5 28 0
P3 12 2 3
P4 2 10 1
P5 9 16 4

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

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.

Process Arrival Time Burst Time
$P_1$ 0 10
$P_2$ 3 6
$P_3$ 7 1
$P_4$ 8 3
The average turn around time of these processes is milliseconds ________.

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.

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

Process Arrival
A 0 3
B 1 6
C 4 4
D 6 2

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

Process Name Arrival Time Execution Time
A 0 6
B 3 2
C 5 4
D 7 6
E 10 3

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

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 ___________.

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 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?

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

Process Arrival
Time Units
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

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

Process Arrival time Burst Time
P0 0 ms 9 ms
P1 1 ms 4 ms
P2 2 ms 9 ms

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?

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

Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match entries in Group 1 to entries in Group 2.

Group 1 Group 2
P. Gang Scheduling                                1. Guaranteed Scheduling
Q. Rate Monotonic Scheduling 2. Real-time Scheduling
R. Fair Share Scheduling 3. Thread Scheduling