Skip to main content

Scheduling Policy Lab

A hands-on lab for running, comparing, and computing metrics for the scheduling policies introduced in clusters 2 and 3.

Retrieval Prompts​

  1. State the scheduling rule for FCFS, SJF, SRTF, and Round-Robin in one sentence each.
  2. Define turnaround time, waiting time, response time, and throughput.
  3. State the main argument for why SJF minimizes average turnaround time.
  4. State the tradeoff a smaller time quantum in Round-Robin trades off.
  5. Give the two MLFQ rules that together define its priority adjustment.

Compare and Distinguish​

Separate these pairs clearly:

  • turnaround time versus waiting time
  • response time versus turnaround time
  • throughput versus utilization
  • SJF versus SRTF (non-preemptive versus preemptive; which assumption does each rely on?)
  • MLFQ versus CFS (discrete queues versus continuous vruntime)

Common Mistake Check​

Identify the error in each statement:

  1. "Round-Robin is always fairer than SJF because it gives everyone a turn."
  2. "SJF is the best policy for interactive systems."
  3. "Throughput and average turnaround time are the same metric in different units."
  4. "A smaller quantum always improves responsiveness."
  5. "MLFQ is just Round-Robin with multiple queues."

Mini Application -- Worked Gantt Charts​

For each workload, draw the Gantt chart on paper and compute:

  • per-job turnaround time and response time
  • average turnaround, average waiting, and average response
  • throughput (jobs per unit time)

Workload A​

Four jobs, all arrive at time 0:

Job   Length
A     8
B     4
C     2
D     6

Compute all metrics under:

  1. FCFS (arrival order A, B, C, D)
  2. SJF
  3. Round-Robin with quantum q = 2 (same arrival order as a tie-break)

Workload B​

Staggered arrivals:

Job   Arrival   Length
P1    0         7
P2    2         4
P3    4         1
P4    5         4

Compute all metrics under:

  1. FCFS
  2. Non-preemptive SJF
  3. SRTF (preemptive)

Workload C -- interactive mix​

Ten "jobs," half CPU-bound (length = 10) and half interactive (length = 1, arriving one per time unit starting at t = 1):

Compute response time for the interactive jobs under:

  1. FCFS
  2. Round-Robin with q = 2
  3. A two-queue MLFQ (higher queue q = 1, lower queue q = 8; priority boost every 50 ticks)

Describe why the MLFQ response times are better than FCFS and whether they are better or worse than pure RR.

Mini Application -- Metric Reasoning​

Explain in 2-3 sentences each:

  1. Why SJF is unfair to long jobs (use a three-job workload to illustrate).
  2. Why Round-Robin with q larger than the longest job reduces to FCFS.
  3. Why Round-Robin with q close to the context-switch cost approaches zero useful throughput.
  4. Why priority inversion can cause a high-priority job to have a huge turnaround time.

Evidence Check​

This page is complete only if:

  • You can draw a correct Gantt chart for each workload without looking at a reference.
  • You can compute per-job and average turnaround, waiting, and response time from the Gantt chart.
  • You can pick the correct policy for a given stated goal ("minimize average turnaround," "minimize worst response time") and justify it in one sentence.
  • You can state, for any policy, one realistic workload on which it performs badly.