CPU scheduling interview questions, with answers

The questions, with answers

1. 1.What is CPU scheduling, and which criteria are used to compare algorithms?

   In short: Choosing which ready process gets the CPU next, judged by utilisation, throughput, turnaround, waiting and response time.

   When several processes are ready, the short-term scheduler picks one and the dispatcher switches the CPU to it. Algorithms are compared on CPU utilisation (keep the CPU busy), throughput (processes completed per unit time), turnaround time (from arrival to completion), waiting time (time spent in the ready queue) and response time (from arrival to the first response). Batch systems favour throughput and turnaround, while interactive systems favour response time. No algorithm is best on every criterion, which is why real schedulers combine several ideas.

2. 2.What is the difference between preemptive and non-preemptive scheduling?

   In short: Preemptive scheduling can take the CPU from a running process; non-preemptive scheduling waits until it blocks or finishes.

   In non-preemptive scheduling, once a process gets the CPU it keeps it until it finishes or blocks for I/O; FCFS and non-preemptive SJF work this way. Preemptive scheduling lets the OS interrupt a running process, typically on a timer interrupt or when a higher-priority process arrives, and put it back in the ready queue; round robin, preemptive priority and shortest remaining time first are examples. Preemption gives better response times for interactive work but costs context switches, and it means shared data can be interrupted mid-update, which is why kernels need synchronisation.

3. 3.How do you calculate waiting time and turnaround time?

   In short: Turnaround = completion time − arrival time; waiting time = turnaround time − burst time; average each over the processes.

   Draw the Gantt chart of the schedule first, then read each process's completion time from it. Turnaround time is completion minus arrival, and waiting time is turnaround minus the CPU burst, the time the process spent ready but not running. In the FCFS example, three processes arrive at time 0 with bursts of 5, 3 and 2 ms: they wait 0, 5 and 8 ms, so the average waiting time is 13 / 3 ≈ 4.33 ms. Response time, by contrast, measures only until a process first runs, which differs from waiting time under preemptive algorithms.

   FCFS, all arrive at 0:
   | P1    | P2  | P3 |
   0       5     8    10
   waits: 0, 5, 8
   avg = 13 / 3 = 4.33 ms

4. 4.How does round robin scheduling work, and how should the time quantum be chosen?

   In short: Each ready process runs for at most one time quantum in turn; the quantum trades response time against switching overhead.

   Round robin keeps the ready processes in a circular queue and gives each one CPU time slice, the quantum, before preempting it and moving it to the back of the queue, so every process gets a fair share and interactive users see quick responses. The quantum is the key parameter. If it is very large, round robin degenerates into FCFS. If it is very small, the CPU spends a large fraction of its time on context switches rather than work. A common rule of thumb is to make it longer than most CPU bursts, so most processes finish or block within one quantum; typical values are 10 to 100 ms.

5. 5.What is the convoy effect?

   In short: Under FCFS, short processes pile up behind one long CPU-bound process, inflating average waiting time and idling I/O devices.

   With first-come, first-served scheduling, a long CPU-bound process at the head of the queue makes every process behind it wait for its whole burst, even processes that need the CPU only briefly. The short, I/O-bound processes form a convoy behind it, so average waiting time rises sharply, and the I/O devices sit idle because the processes that would use them cannot get the CPU to issue requests. Running the short jobs first removes the convoy, which is the motivation for shortest-job-first scheduling and for preemptive algorithms such as round robin.

6. 6.Why is shortest job first optimal, and why is it hard to use?

   In short: Running shorter bursts first minimises average waiting time, but the length of the next CPU burst is not known in advance.

   Shortest job first runs the ready process with the smallest next CPU burst. Moving a short job ahead of a long one reduces the short job's wait by more than it increases the long one's, so SJF gives the minimum average waiting time of any non-preemptive schedule, and its preemptive version, shortest remaining time first, does the same among preemptive ones. The catch is that the scheduler cannot know the next burst length. Systems estimate it from past bursts using exponential averaging: the prediction is α × the last burst + (1 − α) × the previous prediction.

7. 7.What is multilevel feedback queue scheduling?

   In short: Several ready queues with different priorities and quanta; processes move between them based on how they use the CPU.

   A multilevel feedback queue keeps several queues, from high priority with a short quantum to low priority with a long one or FCFS. New processes start at the top. A process that uses its whole quantum is treated as CPU-bound and moved down; one that gives up the CPU early, typically for I/O, stays high, so interactive processes get quick responses without the scheduler knowing burst lengths in advance. Processes that wait long in low queues are periodically moved back up. The design is configurable through the number of queues, their quanta and the promotion rules, and it underlies many real schedulers.

How the diagnostic asks it

One question from the Operating Systems bank, exactly as a sitting would show it. The bank has 4 on cpu scheduling and 30 across Operating Systems.

P1  10
P2  4
P3  2