CPU Scheduling Algorithms Questions and Answers

Q: The processes A, B and C are started at times 0, 5 and 10 miliseconds respectively, in a pure time thrashing system (round robin scheduling) that uses a time slice of 50 miliseconds. The time in miliseconds at which process C would complete its first I/O operation is :

Process C completes its first I/O at 1000 ms.Each process first needs its CPU burst (A 100 ms, B 350 ms, C 200 ms) and then 500 ms of I/O on its own device. With a 50 ms slice and arrivals at 0, 5 and 10 ms, the CPU runs in turn:0-50 A50-100 B100-150 C150-200 A (done)200-250 B250-300 C300-350 B350-400 C400-450 B450-500 C (done)A finishes its 100 ms at 200 ms and starts I/O, leaving B and C to alternate. C receives its fourth slice from 450 to 500 ms, completing 200 ms of CPU, and begins its I/O at 500 ms. The I/O takes 500 ms, so it ends at 500 + 500 = 1000 ms. A's first I/O ends at 700 ms, which is the trap in option A.

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

The algorithm is Shortest remaining time first.Shortest-job-first is provably optimal for minimizing average waiting time: running shorter jobs first means fewer processes wait behind each long one. All processes here arrive together, so shortest remaining time first behaves exactly like SJF and achieves that optimum.Round-robin with a small quantum interleaves everything, so every process waits through slices of all the others. A uniform random order is optimal only by chance. Priority proportional to burst length runs the longest jobs first, the worst possible order for average waiting time.

Q: A computer has two processors, M1 and M2. Four processes P1, P2, P3, P4 with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows:• M1 uses priority of execution for the processes as, \(P1 \gt P3 \gt P2 \gt P4\), i.e., P1 and P4 have highest and lowest priorities, respectively.• M2 uses priority of execution for the processes as, \(P2 \gt P3 \gt P4 \gt P1\), i.e., P2 and P1 have highest and lowest priorities, respectively.A process Pi is scheduled to a processor Mk, if the processor is free and no other process Pj is waiting with higher priority. At any given point of time, a process can be allocated to any one of the free processors without violating the execution priority rules. Ignore the context switch time. What will be the average waiting time of the processes in milliseconds?

The average waiting time is 9.00 ms.All four processes arrive at time 0 and both processors are free.t = 0: M1 picks its highest-priority process, P1 (runs 0 to 20). M2 picks its highest-priority process, P2 (runs 0 to 16).t = 16: M2 is free. P3 and P4 are waiting, and M2 ranks P3 above P4, so P3 runs 16 to 41.t = 20: M1 is free and only P4 is waiting, so P4 runs 20 to 30.Waiting times are P1 = 0, P2 = 0, P3 = 16 and P4 = 20, so\[ \text{average} = \frac{0 + 0 + 16 + 20}{4} = 9.00\ \text{ms} \]The other averages do not come from a schedule that obeys both processors' priority rules; for instance, starting P3 at time 0 on either processor breaks the rule, since each processor has a higher-priority process waiting then.

Q: 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.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?

The average waiting times are SRTF = 6, NP-SJF = 7.5.SRTF. A runs 0-2. B arrives with 6 against A's remaining 8 and runs 2-4. C arrives with 3 against B's remaining 4 and runs 4-7 (D, arriving at 6 with 7, does not preempt C's remaining 1). Then B runs 7-11, D 11-18 and A 18-26. Waiting time is finish minus arrival minus burst: A 16, B 3, C 0, D 5, total 24, average 6.NP-SJF. A runs 0-10 without interruption. At 10, C (3) is shortest and runs 10-13, then B (6) 13-19, then D (7) 19-26. Waiting times: A 0, C 6, B 11, D 13, total 30, average 7.5.The other options get one of the two schedules wrong: 7 for SRTF, or 7 and 8.5 for NP-SJF, do not match these timelines.

Q: Processes \(P_{1}\), \(P_{2}\), \(P_{3}\), \(P_{4}\) arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times.Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds?

The average turnaround time is 19 ms.Under SRTF the process with the least remaining time runs, and an arrival can preempt it:0-2: P1 runs (P2 arrives at 1 with 13, more than P1's 9 left). At 2, P3 arrives with 6, less than P1's 8 left, and preempts.2-8: P3 runs to completion at 8. P4 arrives at 8 with 9.8-16: P1 (8 left) runs to completion at 16.16-25: P4 (9) runs; 25-38: P2 (13) runs.\[ \begin{aligned} \text{TAT} &= (16-0) + (38-1) + (8-2) + (25-8) \\ &= 16 + 37 + 6 + 17 = 76 \\ \text{average} &= 76/4 = 19\ \text{ms} \end{aligned} \]37 is P2's turnaround alone. 22 is close to the first-come first-served average, (10 + 22 + 27 + 30)/4 = 22.25, which ignores the shortest-remaining-time rule, and 15 matches no schedule of these processes.

Q: Which one of the following CPU scheduling algorithms cannot be preemptive?

The algorithm that cannot be preemptive is First Come First Serve (FCFS).FCFS runs processes in arrival order, and each process keeps the CPU until it finishes or blocks. Taking the CPU away from a running process would break the first-come order, so FCFS is non-preemptive by definition.SRTF is the preemptive version of shortest job first: a newly arrived process with a shorter remaining time takes over the CPU. Round robin preempts each process when its time quantum expires. Priority scheduling can be implemented either way; in its preemptive form a higher-priority arrival takes over the CPU.

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

The burst times that are NOT possible are P = 3, Q = 7, R = 7, S = 3.With a quantum of 4 and the order P, Q, R, S, these bursts run as P (3, done), Q (4, 3 left), R (4, 3 left), S (3, done), Q (3, done), R (3, done). The switches are P to Q, Q to R, R to S, S to Q and Q to R, so there is no switch from R to Q at all, against the 'exactly one' required.Each of the other sets meets every condition. For P = 4, Q = 10, R = 6, S = 2 the run is P, Q, R, S, Q, R, Q, giving one S to Q, one R to Q, two Q to R and no S to P. P = 2, Q = 9, R = 5, S = 1 runs in the same order (P, Q, R, S, Q, R, Q), and so does P = 4, Q = 12, R = 5, S = 4, where R finishes its last unit before Q's final quantum. In each, Q still needs CPU time after R's second turn, which is what produces the single R to Q switch.

Q: Three processes P, Q and R enter the ready queue simultaneously with the length of the cpu burst given in milliseconds as 20, 10 and 15 respectively. The wailing time for process R in case of shortest job first scheduling is :

The waiting time of R is 10 milliseconds.Shortest job first runs the process with the shortest burst first. All three arrive together, so the order is Q (10), then R (15), then P (20):\[ \begin{aligned} Q &: 0 \text{ to } 10 \\ R &: 10 \text{ to } 25 \\ P &: 25 \text{ to } 45 \end{aligned} \]R waits while Q runs, so its waiting time (printed 'wailing time') is 10 ms. 25 is R's completion time, 15 its own burst, and 20 the burst of P.

Q: Which of the following algorithms may cause starvation ?(i) First-come-first-serve(ii) Round Robin(iii) Priority(iv) Shortest process next(v) Shortest remaining time first

Starvation can occur with (iii), (iv) and (v).Under priority scheduling, a low-priority process can wait indefinitely if higher-priority processes keep arriving. Shortest process next and shortest remaining time first always favour short jobs, so a long process can be postponed forever if short jobs keep coming.First-come-first-served and round robin cannot starve a process. FCFS serves every process in arrival order, and round robin gives each ready process a time slice in turn, so every process eventually runs. Options including (i) or (ii) are therefore wrong.

Q: What is the most appropriate purpose of 'nice' command in Linux ?

The nice command is used to set execution priority level for a process.nice starts a program with a modified scheduling priority (its niceness, from -20, the highest priority, to 19, the lowest); a higher niceness makes the process 'nicer' to others by taking less CPU time. renice changes the value for a running process.Real-time messages between users are sent with commands such as write and wall, and memory status is checked with free or vmstat. No command called nice checks whether there is enough memory for a process.

Direction for [ Question No: 1 To 1 ] :

Three processes A, B and C each executes a loop of 100 iterations. In each iteration of the loop, a process performs a single computation that requires \(t_{c}\) CPU miliseconds and the initiates single I/O operation that requires \(t_{io}\) miliseconds. 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	\(t_{c}\)	\(t_{io}\)
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 miliseconds respectively, in a pure time thrashing system (round robin scheduling) that uses a time slice of 50 miliseconds. The time in miliseconds at which process C would complete its first I/O operation is :

A.700 ms
B.900 ms
C.800 ms
D.1000 ms

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: D

Process C completes its first I/O at 1000 ms.

Each process first needs its CPU burst (A 100 ms, B 350 ms, C 200 ms) and then 500 ms of I/O on its own device. With a 50 ms slice and arrivals at 0, 5 and 10 ms, the CPU runs in turn:

0-50 A	50-100 B	100-150 C
150-200 A (done)	200-250 B	250-300 C
300-350 B	350-400 C	400-450 B
450-500 C (done)

A finishes its 100 ms at 200 ms and starts I/O, leaving B and C to alternate. C receives its fourth slice from 450 to 500 ms, completing 200 ms of CPU, and begins its I/O at 500 ms. The I/O takes 500 ms, so it ends at 500 + 500 = 1000 ms. A's first I/O ends at 700 ms, which is the trap in option A.

Discuss in Forum

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

Exam Year(s)

GATE CS - 2016,

Answer: A

The algorithm is Shortest remaining time first.

Shortest-job-first is provably optimal for minimizing average waiting time: running shorter jobs first means fewer processes wait behind each long one. All processes here arrive together, so shortest remaining time first behaves exactly like SJF and achieves that optimum.

Round-robin with a small quantum interleaves everything, so every process waits through slices of all the others. A uniform random order is optimal only by chance. Priority proportional to burst length runs the longest jobs first, the worst possible order for average waiting time.

Discuss in Forum

A computer has two processors, M1 and M2. Four processes P1, P2, P3, P4 with CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, arrive at the same time and these are the only processes in the system. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows:
• M1 uses priority of execution for the processes as, \(P1 \gt P3 \gt P2 \gt P4\), i.e., P1 and P4 have highest and lowest priorities, respectively.
• M2 uses priority of execution for the processes as, \(P2 \gt P3 \gt P4 \gt P1\), i.e., P2 and P1 have highest and lowest priorities, respectively.

A process Pi is scheduled to a processor Mk, if the processor is free and no other process Pj is waiting with higher priority. At any given point of time, a process can be allocated to any one of the free processors without violating the execution priority rules. Ignore the context switch time. What will be the average waiting time of the processes in milliseconds?

A.9.00
B.8.75
C.6.50
D.7.50

Exam Year(s)

GATE CS - 2025,

Answer: A

The average waiting time is 9.00 ms.

All four processes arrive at time 0 and both processors are free.

t = 0: M1 picks its highest-priority process, P1 (runs 0 to 20). M2 picks its highest-priority process, P2 (runs 0 to 16).
t = 16: M2 is free. P3 and P4 are waiting, and M2 ranks P3 above P4, so P3 runs 16 to 41.
t = 20: M1 is free and only P4 is waiting, so P4 runs 20 to 30.

Waiting times are P1 = 0, P2 = 0, P3 = 16 and P4 = 20, so

\[ \text{average} = \frac{0 + 0 + 16 + 20}{4} = 9.00\ \text{ms} \]

The other averages do not come from a schedule that obeys both processors' priority rules; for instance, starting P3 at time 0 on either processor breaks the rule, since each processor has a higher-priority process waiting then.

Discuss in Forum

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.

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

Exam Year(s)

GATE CS - 2024,

Answer: B

The average waiting times are SRTF = 6, NP-SJF = 7.5.

SRTF. A runs 0-2. B arrives with 6 against A's remaining 8 and runs 2-4. C arrives with 3 against B's remaining 4 and runs 4-7 (D, arriving at 6 with 7, does not preempt C's remaining 1). Then B runs 7-11, D 11-18 and A 18-26. Waiting time is finish minus arrival minus burst: A 16, B 3, C 0, D 5, total 24, average 6.

NP-SJF. A runs 0-10 without interruption. At 10, C (3) is shortest and runs 10-13, then B (6) 13-19, then D (7) 19-26. Waiting times: A 0, C 6, B 11, D 13, total 30, average 7.5.

The other options get one of the two schedules wrong: 7 for SRTF, or 7 and 8.5 for NP-SJF, do not match these timelines.

Discuss in Forum

Processes \(P_{1}\), \(P_{2}\), \(P_{3}\), \(P_{4}\) arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times.

Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds?

A.22
B.15
C.37
D.19

Exam Year(s)

GATE CS - 2025,

Answer: D

The average turnaround time is 19 ms.

Under SRTF the process with the least remaining time runs, and an arrival can preempt it:

0-2: P1 runs (P2 arrives at 1 with 13, more than P1's 9 left). At 2, P3 arrives with 6, less than P1's 8 left, and preempts.
2-8: P3 runs to completion at 8. P4 arrives at 8 with 9.
8-16: P1 (8 left) runs to completion at 16.
16-25: P4 (9) runs; 25-38: P2 (13) runs.

\[ \begin{aligned} \text{TAT} &= (16-0) + (38-1) + (8-2) + (25-8) \\ &= 16 + 37 + 6 + 17 = 76 \\ \text{average} &= 76/4 = 19\ \text{ms} \end{aligned} \]

37 is P2's turnaround alone. 22 is close to the first-come first-served average, (10 + 22 + 27 + 30)/4 = 22.25, which ignores the shortest-remaining-time rule, and 15 matches no schedule of these processes.

Discuss in Forum

Which one of the following CPU scheduling algorithms cannot be preemptive?

A.Shortest Remaining Time First (SRTF) Scheduling
B.First Come First Serve (FCFS) Scheduling
C.Round Robin Scheduling
D.Priority Scheduling

Exam Year(s)

GATE CS - 2026,

Answer: B

The algorithm that cannot be preemptive is First Come First Serve (FCFS).

FCFS runs processes in arrival order, and each process keeps the CPU until it finishes or blocks. Taking the CPU away from a running process would break the first-come order, so FCFS is non-preemptive by definition.

SRTF is the preemptive version of shortest job first: a newly arrived process with a shorter remaining time takes over the CPU. Round robin preempts each process when its time quantum expires. Priority scheduling can be implemented either way; in its preemptive form a higher-priority arrival takes over the CPU.

Discuss in Forum

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?

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

Exam Year(s)

GATE CS - 2022,

Answer: D

The burst times that are NOT possible are P = 3, Q = 7, R = 7, S = 3.

With a quantum of 4 and the order P, Q, R, S, these bursts run as P (3, done), Q (4, 3 left), R (4, 3 left), S (3, done), Q (3, done), R (3, done). The switches are P to Q, Q to R, R to S, S to Q and Q to R, so there is no switch from R to Q at all, against the 'exactly one' required.

Each of the other sets meets every condition. For P = 4, Q = 10, R = 6, S = 2 the run is P, Q, R, S, Q, R, Q, giving one S to Q, one R to Q, two Q to R and no S to P. P = 2, Q = 9, R = 5, S = 1 runs in the same order (P, Q, R, S, Q, R, Q), and so does P = 4, Q = 12, R = 5, S = 4, where R finishes its last unit before Q's final quantum. In each, Q still needs CPU time after R's second turn, which is what produces the single R to Q switch.

Discuss in Forum

Three processes P, Q and R enter the ready queue simultaneously with the length of the cpu burst given in milliseconds as 20, 10 and 15 respectively. The wailing time for process R in case of shortest job first scheduling is :

A.20
B.25
C.10
D.15

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

Answer: C

The waiting time of R is 10 milliseconds.

Shortest job first runs the process with the shortest burst first. All three arrive together, so the order is Q (10), then R (15), then P (20):

\[ \begin{aligned} Q &: 0 \text{ to } 10 \\ R &: 10 \text{ to } 25 \\ P &: 25 \text{ to } 45 \end{aligned} \]

R waits while Q runs, so its waiting time (printed 'wailing time') is 10 ms. 25 is R's completion time, 15 its own burst, and 20 the burst of P.

Discuss in Forum

Which of the following algorithms may cause starvation ?

(i) First-come-first-serve
(ii) Round Robin
(iii) Priority
(iv) Shortest process next
(v) Shortest remaining time first

A.(i), (iii) and (v)
B.(iii), (iv) and (v)
C.(ii), (iv) and (v)
D.(ii), (iii) and (iv)

Exam Year(s)

MH SET - 2019, SET Exam - 2019,

Answer: B

Starvation can occur with (iii), (iv) and (v).

Under priority scheduling, a low-priority process can wait indefinitely if higher-priority processes keep arriving. Shortest process next and shortest remaining time first always favour short jobs, so a long process can be postponed forever if short jobs keep coming.

First-come-first-served and round robin cannot starve a process. FCFS serves every process in arrival order, and round robin gives each ready process a time slice in turn, so every process eventually runs. Options including (i) or (ii) are therefore wrong.

Discuss in Forum

10.

What is the most appropriate purpose of 'nice' command in Linux ?

A.Send real-time messages among the users
B.Check the status of memory
C.Set execution priority level for a process
D.Verify the availability of enough memory space for a process

Exam Year(s)

MH SET - 2021, SET Exam - 2021,

Answer: C

The nice command is used to set execution priority level for a process.

nice starts a program with a modified scheduling priority (its niceness, from -20, the highest priority, to 19, the lowest); a higher niceness makes the process 'nicer' to others by taking less CPU time. renice changes the value for a running process.

Real-time messages between users are sent with commands such as write and wall, and memory status is checked with free or vmstat. No command called nice checks whether there is enough memory for a process.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: CPU Scheduling Algorithms Questions and Answers || CPU Scheduling Algorithms MCQ Questions and Answers || CPU Scheduling Algorithms GK Questions and Answers || CPU Scheduling Algorithms GK MCQ Questions || CPU Scheduling Algorithms Multiple Choice Questions and Answers || CPU Scheduling Algorithms GK || GK on CPU Scheduling Algorithms || Operating Systems Questions and Answers || Operating Systems MCQ Questions and Answers || Operating Systems GK Questions and Answers || GK on Operating Systems

CPU Scheduling Algorithms Questions and Answers

Direction for [ Question No: 1 To 1 ] :

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications