Unit 5 Self-Check Quiz

Question

Question 1

Which of the following is not a scheduling objective?

Maximising CPU utilisation.
Maximising throughput.
Minimising turnaround time.
Maximising waiting time.

Answer 1

Maximising waiting time. Waiting time — the total time a process spends in the ready queue — is a metric to be minimised, not maximised. Along with it, the standard objectives are to minimise turnaround time (submission to completion) and response time (submission to first output), and to maximise CPU utilisation and throughput. A scheduler must trade these objectives off: a quantum that is small enough to give every process a fast response also spends a larger fraction of CPU time on context switches.

Answer 2

A process alternates between bursts of CPU activity (computing) and bursts of I/O activity (waiting for a device). CPU-bound processes have long CPU bursts and few I/O bursts; I/O-bound processes have short CPU bursts and many I/O bursts. If a single process held the CPU until completion, the CPU would idle whenever the process blocked on I/O. Scheduling — switching to another ready process when one blocks — keeps the CPU busy and the I/O devices busy simultaneously. The cycle also explains why I/O-bound processes are favoured by the scheduler: they give up the CPU quickly and often, so favouring them costs little and improves device utilisation.

Answer 3

The second choice. Turnaround time = completion time − arrival time. It includes waiting in the ready queue, running on the CPU, and blocking on I/O. Response time (the first choice) is the time to first output; waiting time (the third choice) is only the time in the ready queue; throughput (the fourth choice) is a system-level rate. Turnaround is the primary metric for batch systems; response time is the primary metric for interactive systems.

Answer 4

FCFS runs them in arrival order: P1 (4), P2 (7), P3 (2), P4 (5). Wait times: P1 = 0, P2 = 4, P3 = 4 + 7 = 11, P4 = 4 + 7 + 2 = 13. Average waiting time = (0 + 4 + 11 + 13) / 4 = 28 / 4 = 7.0. Turnaround times = wait + burst: P1 = 4, P2 = 11, P3 = 13, P4 = 18. Average turnaround time = (4 + 11 + 13 + 18) / 4 = 46 / 4 = 11.5.

Answer 5

The convoy effect is the phenomenon in which one long-running CPU-bound process at the head of the queue delays many short I/O-bound processes behind it. The short processes finish their tiny CPU bursts quickly once they run, but they wait a long time for the long process to complete, so their response time and waiting time are both poor, and the I/O devices sit idle because no process has reached its I/O phase. The effect is characteristic of FCFS, which is non-preemptive and gives the CPU to whichever process arrives first, regardless of burst length. It is the main motivation for SJF and for preemptive algorithms.

Answer 6

SJF (non-preemptive). It can be proved by an exchange argument: if two adjacent processes in the schedule have burst times a > b, swapping them reduces the waiting time of the shorter process by a and increases that of the longer by b, for a net reduction of a − b > 0. Repeating this exchange yields a schedule sorted by burst length, which is exactly SJF. The catch is that the true burst length of a process is not known in advance — it must be estimated, typically with an exponential average of past bursts. SRTF (preemptive SJF) is optimal for average turnaround time under the same idealised assumption.

Answer 7

Timeline under SRTF: P1 runs from 0 to 1 (remaining 7). P2 arrives at 1 with burst 4; it is shorter than P1's remaining 7, so P2 preempts P1. P2 runs from 1 to 2 (remaining 3). P3 arrives at 2 with burst 9; P2's remaining 3 is shorter, so P2 continues. P2 runs from 2 to 5 (completes). P1's remaining 7 is shorter than P3's 9, so P1 resumes from 5 to 12. P3 runs from 12 to 21. Completion times: P1 = 12, P2 = 5, P3 = 21. Wait times = completion − arrival − burst: P1 = 12 − 0 − 8 = 4; P2 = 5 − 1 − 4 = 0; P3 = 21 − 2 − 9 = 10. Average waiting time = (4 + 0 + 10) / 3 = 14 / 3 ≈ 4.67.

Answer 8

SJF is non-preemptive: once a process starts, it runs to completion (or until it blocks). SRTF is preemptive: when a new process arrives with a burst shorter than the remaining time of the running process, the running process is preempted. SRTF has lower average waiting time than SJF, but it incurs more context switches (each preemption is a switch) and it is more complex to implement, since the scheduler must track remaining times. Both rely on knowing or estimating burst times in advance, which is impossible in general — the estimates are made with an exponential average of the process's previous bursts.

Answer 9

Starvation (also called indefinite blocking) occurs when a low-priority process never runs because higher-priority processes continually arrive and are always selected first. In the worst case, a low-priority process waits forever. The standard solution is aging: gradually increase the priority of a process the longer it waits in the ready queue. For example, increase priority by one level every few minutes. Eventually even the lowest-priority process acquires a high enough priority to be scheduled. Aging bounds the waiting time and makes the scheduler starvation-free, at the cost of a small amount of bookkeeping and a slight loss of the strict priority ordering.

Answer 10

Order: P1 (0–4), P2 (4–8), P3 (8–12), P1 (12–16), P2 (16–20), P3 (20–24). Completion: P1 at 16, P2 at 20, P3 at 24. Wait times = completion − 8: P1 = 8, P2 = 12, P3 = 16. Average waiting time = (8 + 12 + 16) / 3 = 12.0. For comparison, SJF would have run them back-to-back (all have the same burst time, so any order) with wait times 0, 8, 16 → average 8.0. Round robin is worse on average waiting time but far better on response time: P1's first response is immediate, P2's is at 4 ms, P3's at 8 ms, whereas under SJF P3 would not respond until 16 ms.

Answer 11

As the quantum → ∞, round robin degenerates into FCFS: each process runs to completion before the next is dispatched. Average waiting time improves (FCFS is often better than RR on that metric), but response time becomes very poor for processes at the back of the queue. As the quantum → 0, the scheduler switches so often that most CPU time is spent on context switches and little on useful work. The overhead fraction is approximately switch_time / (quantum + switch_time). Practical quanta are typically 10–100 ms — long enough that switching overhead is a few percent, short enough that a process reaches the CPU within a perceptible delay.

Answer 12

The second choice. If the quantum is longer than most bursts, most processes finish within one quantum and round robin degenerates toward FCFS, gaining FCFS's low average waiting time but losing its response advantage. If the quantum is shorter than most bursts, every process is preempted repeatedly, and the context-switch overhead dominates. The rule of thumb is to make the quantum slightly longer than the majority of CPU bursts — long enough that most processes finish in one quantum, short enough that no process waits too long. Typical values: 10–100 ms.

Answer 13

A multilevel queue scheduler partitions the ready queue into several separate queues — for example, one for system processes, one for interactive processes, one for batch jobs — each with its own scheduling algorithm and priority. Processes are assigned permanently to a queue at creation. The scheduler chooses among queues according to a fixed priority or a weighted share of CPU time. A multilevel feedback queue (MLFQ) allows processes to move between queues: a process that uses too much CPU is demoted to a lower-priority queue with a longer quantum, and a process that has waited too long is promoted (aging). MLFQ is the basis of many real schedulers because it approximates SJF without needing to know burst times: short jobs stay in the high-priority queues; long jobs migrate to the lower ones.

Answer 14

The scheduler uses observed behaviour: the amount of CPU time a process has recently consumed, and the length of time it has been waiting. A process that exhausts its quantum in the high-priority queue is assumed to be CPU-bound and is demoted; a process that blocks before exhausting its quantum is assumed to be I/O-bound and stays high. To prevent starvation, the scheduler periodically promotes all processes to the top queue (aging). The parameters are the number of queues, the quantum of each queue, the promotion policy, and the demotion policy — tuning them changes the character of the scheduler considerably.

Answer 15

FCFS. Once a process is dispatched, it runs until it blocks or terminates; the scheduler does not preempt it. SRTF, round robin, and preemptive priority all preempt a running process — SRTF when a shorter job arrives, round robin on every quantum expiry, and preemptive priority when a higher-priority process becomes ready. Non-preemptive priority scheduling exists but the option specifies the preemptive variant. Non-preemptive algorithms are simpler but vulnerable to a long-running process blocking the system.

Answer 16

The metrics conflict. Minimising average waiting time suggests giving the CPU to short jobs first (SJF), but that penalises long jobs and can starve them. Minimising response time suggests a small quantum (round robin), but a small quantum increases context-switch overhead and reduces throughput. Maximising throughput suggests large quanta and few switches, but that harms response time. Maximising CPU utilisation suggests keeping the CPU busy with whatever is ready, but that may mean running low-priority background work instead of high-priority interactive work. Every scheduler is therefore a compromise tuned to the expected workload — batch, interactive, real-time, or mixed.

Answer 17

The mechanism is the machinery: how the kernel saves and restores context, how it maintains the ready queue, how it delivers timer interrupts, how it selects the next process. The policy is the rule that decides which process to select next. Separating them allows the policy to be changed without rewriting the mechanism — a general-purpose kernel can support multiple policies (real-time, fair-share, batch) and select among them at run time. The classic example is Solaris, which uses the same dispatcher and thread structures for its several scheduling classes. Separation is the standard operating-systems design principle of separating policy from mechanism.

Answer 18

The second choice. The primary reason is to guarantee fairness and responsiveness: without preemption, a CPU-bound process that never blocks would hold the CPU indefinitely, and no other process — including the interactive one the user is waiting on — would run. Throughput is not necessarily improved (preemption adds switching overhead), context-switch cost is not reduced, and the implementation is more complex than non-preemptive. Preemption is a fairness and responsiveness guarantee, not an efficiency improvement.

Answer 19

CFS tries to equalise virtual runtime — a per-task counter that advances in proportion to the task's actual running time, weighted by the task's priority (niceness). When a task runs for Δt, its virtual runtime increases by Δt × (weight of a nice-0 task) / (weight of this task). The scheduler always picks the task with the smallest virtual runtime. A high-priority (low-nice) task's virtual runtime grows more slowly, so it runs more often; a low-priority task's virtual runtime grows faster, so it runs less. The effect is proportional-share scheduling: each task receives a share of the CPU proportional to its weight. CFS uses a red-black tree ordered by virtual runtime to make the selection O(log n).

Answer 20

With a 100 ms quantum: 1 ms overhead per 101 ms of wall time = about 0.99%. With a 10 ms quantum: 1 ms per 11 ms = about 9.1%. Reducing the quantum to 1 ms would give 1 ms per 2 ms = 50%, at which point half the CPU's time is spent on switching. This is the quantitative reason for choosing quanta in the tens of milliseconds: switching cost is amortised enough to be negligible, while response time remains adequate for interactive use.

Answer 21

It can starve long processes. SJF consistently favours short bursts, and if short processes keep arriving, a long process may wait indefinitely. SJF is optimal for average waiting time, not response time; it does not require the exact burst time (estimates via exponential averaging suffice, though accuracy affects optimality); and the non-preemptive version (SJF proper) is not preemptive — SRTF is its preemptive variant. The correct statement is the starvation risk.

Answer 22

The scheduler records the actual length of each burst t_n and maintains an estimate τ_n. On each new burst:

τ_n+1 = α · t_n + (1 − α) · τ_n

with 0 ≤ α ≤ 1. The choice of α controls how much weight recent history carries: α near 1 makes the estimate track the last burst, α near 0 makes it a long-running average. Typical α = 0.5. This is an exponentially weighted moving average: older bursts have exponentially decaying influence. It adapts to a process whose behaviour changes while smoothing out one-off bursts. SRTF uses these estimates to compare against remaining burst times.

Answer 23

A load-balanced system distributes runnable tasks evenly across the available cores, so that no core is idle while another has a queue of waiting tasks. On multicore systems, the kernel maintains a per-core run queue and periodically rebalances. Two mechanisms are typical. Work stealing: an idle core takes a task from the queue of the busiest core, using a per-queue lock that keeps contention low. Periodic rebalancing: the scheduler moves tasks between queues at intervals (for example, at each tick or when a core goes idle). The goal is to keep every core busy when there is work, and to avoid moving tasks so often that the migration cost (cache and TLB invalidation) outweighs the benefit.

Answer 24

The second choice. A real-time scheduler's job is to meet deadlines. If a process's deadline is imminent, the scheduler must give it the CPU immediately, preempting whatever is running. Hard real-time systems use algorithms such as Earliest Deadline First (EDF) or Rate Monotonic Scheduling (RMS) to make this decision systematically; EDF is optimal for preemptive uniprocessor scheduling of periodic tasks with deadlines equal to periods. Lowering priority, demoting to a lower queue, or ignoring deadlines would be exactly the opposite of what a deadline-driven scheduler must do.

Answer 25

When a CPU-bound process at the head of the FCFS queue holds the CPU for a long burst, the I/O-bound processes behind it cannot run, so they cannot issue their next I/O requests. The I/O devices sit idle while the CPU-bound process computes. Once the CPU-bound process finishes and the I/O-bound processes run, they issue requests in a burst, keeping the devices busy briefly and then idling again. The result is that neither the CPU nor the I/O devices are well utilised: the CPU is busy with one long task, and the devices are starved by the queue discipline. FCFS's ordering is the cause; the fix is to let short I/O-bound jobs run first (SJF, or a priority scheme that favours them).

Answer 26

The scheduler must balance responsiveness for interactive processes, which requires short quanta and frequent preemption, against throughput and low overhead, which require long quanta and few context switches. It must also balance fairness, so no process starves, against priority, so important work runs first. Every practical scheduler — CFS, MLFQ, priority with aging — is a different point on this multi-dimensional trade-off curve.

Unit 5 Self-Check Quiz

Multiple choice and short answer

Ready for the graded quiz?

Process	Arrival	Burst
P1	0	8
P2	1	4
P3	2	9