"CPU & I/O Scheduling" — Practice

Question 1

Define turnaround, waiting and response time in terms of arrival, completion, burst and first-dispatch times.

Accepted Answer

Turnaround equals completion minus arrival. Waiting equals turnaround minus total CPU burst. Response equals first dispatch minus arrival.

Question 2

Three processes arrive at time 0 with bursts 6, 2, 8. Give the average waiting time under FCFS in that order and under SJF.

Accepted Answer

FCFS: waits are 0, 6, 8, average 14 over 3, about 4.67. SJF orders 2, 6, 8 with waits 0, 2, 8, average 10 over 3, about 3.33.

Question 3

A disk head at cylinder 50 must serve 20, 60, 80. Compute total movement under FCFS and under SSTF.

Accepted Answer

FCFS moves 30 then 40 then 20, a total of 90. SSTF serves 60, then 80, then 20, moving 10 plus 20 plus 60, a total of 90 as well in this case.

Question 4

Processes P1 at 0 with burst 5, P2 at 1 with burst 3, P3 at 2 with burst 1. Compute average waiting time under SRTF.

Accepted Answer

P1 runs at 0. At time 1 P2 arrives with 3 against P1's remaining 4, so P2 preempts. At time 2 P3 arrives with 1 against P2's remaining 2, so P3 preempts and finishes at 3. P2 resumes to 5, then P1 runs to 9. Waits are 4, 1, 0, average 5 over 3, about 1.67.

Question 5

Under round robin with quantum 2 and a context switch cost of 0.2, three processes with bursts 4, 4, 4 run to completion. What fraction of total elapsed time is overhead?

Accepted Answer

Each process needs 2 quanta, giving 6 quanta and therefore 6 switches counting the one after the last quantum, or 5 between them. Taking 5 switches, overhead is 1.0 against 12 units of work, so overhead is 1 in 13, about 7.7 percent of elapsed time.

Question 6

Explain why a multilevel feedback queue approximates shortest job first without measuring burst lengths.

Accepted Answer

A process that blocks before exhausting its quantum is behaving like a short interactive job and keeps its high priority, while one that consumes a full quantum is behaving like a long batch job and is demoted to a lower queue with a larger quantum. Observed behaviour substitutes for the unknown burst length.

Question 7

A head at cylinder 100 on a 0 to 199 disk has requests 30, 70, 140, 190. Compute movement under SCAN toward higher cylinders and under C-LOOK.

Accepted Answer

SCAN serves 140, 190, travels to 199, reverses and serves 70 then 30, moving 99 plus 169, which is 268. C-LOOK serves 140, 190, jumps to 30, then serves 70, moving 90 plus 160 plus 40, which is 290.

Question 8

Prove that shortest job first minimises average waiting time when all processes arrive at time 0.

Accepted Answer

Take any schedule with an adjacent pair long then short, bursts a then b with a greater than b, starting at time t. Their combined waiting is 2t plus a. Swapping gives 2t plus b, which is smaller, and no other process is affected because the pair occupies the same interval. So an optimal schedule has no out-of-order adjacent pair, meaning it is sorted by increasing burst.

Question 9

A priority scheduler ages waiting processes by one level per 8 time units. A process enters at priority 24, where 0 is highest. Bound its waiting time and state the cost of the scheme.

Accepted Answer

It reaches priority 0 after 24 times 8, which is 192 time units of waiting, after which no arrival can outrank it, so its wait is bounded. The cost is that a sufficiently patient low-priority job eventually preempts genuinely urgent work, which is why real-time systems do not age their top band.

Question 10

Under what workload does round robin with a large quantum become indistinguishable from FCFS, and why?

Accepted Answer

When every CPU burst is shorter than the quantum, no process is ever preempted, so each runs to completion in arrival order, which is exactly FCFS. The quantum then only sets an upper bound that is never reached.

Practice — "CPU & I/O Scheduling"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities