Module 2 · Unit 5 · Discussion 5
Scheduling a Mixed Workload
Every general-purpose operating system runs a mixed workload: interactive processes that need a fast response, batch processes that need high throughput, and background processes that can wait. No single scheduling algorithm is best for all three. This discussion asks you to choose a scheduling policy for a specific mixed workload, justify the choice in terms of the metrics that matter, and analyse the trade-offs you are accepting in return.
01 Overview
| Course | COMP 3150 / CMIS 3150 — Operating Systems |
|---|---|
| Unit | Unit 5 — CPU Scheduling |
| Weight | Part of the 5% participation grade (each discussion is worth approximately 0.4% of the final grade) |
| Opens | Monday of Week 5 |
| Initial post due | Thursday of Week 5, 23:59 |
| Peer replies due | Sunday of Week 5, 23:59 |
| Format | One initial post (450–600 words, including a small numerical analysis) and at least two substantive peer replies (150–250 words each) |
| CLOs assessed | CLO3, CLO6, CLO8 |
02 Learning outcomes addressed
By participating in this discussion you will
- Explain the scheduling objectives — CPU utilisation, throughput, turnaround time, waiting time, response time — and their trade-offs (U5.1).
- Analyse the classical scheduling algorithms — FCFS, SJF, SRTF, priority, round robin, and multilevel feedback queue (U5.2).
- Calculate scheduling metrics for a given workload and algorithm (U5.3).
- Compare scheduler designs and recommend one for a specific workload (U5.4).
- Evaluate the trade-offs between responsiveness, throughput, fairness, and simplicity (U5.5).
This discussion assesses CLO3 (analyse scheduling, synchronization, and deadlock solutions), CLO6 (apply Linux systems programming and tools), and CLO8 (design and implement OS-related components).
03 Discussion prompt
The scenario
You are the systems administrator of a small compute cluster that runs two classes of workloads:
- Interactive services. A web API and an SSH gateway. The API serves requests with a 99th-percentile latency target of 100 ms. Each request involves a short CPU burst (a few hundred microseconds) followed by a short I/O wait (a database query, a file read). These processes block frequently.
- Batch jobs. Simulation and data-processing jobs submitted by researchers. Each job runs for minutes to hours, is CPU-bound, and does almost no I/O. The researchers care about total throughput, not about the latency of any individual job.
The cluster has 16 cores. Both classes run on the same nodes, in the same kernel, with the default Linux scheduler.
Your task
-
Choose one of the following
policies for the cluster:
- Policy A — FCFS (first-come, first-served, non-preemptive).
- Policy B — Round Robin with a quantum of 10 ms.
- Policy C — Multilevel Feedback Queue with three levels (quanta 8 ms, 16 ms, and FCFS with aging). New processes enter level 0; a process that exhausts its quantum is demoted; a process that blocks before exhausting its quantum stays; level-2 processes are promoted after waiting longer than a threshold.
- Policy D — Linux CFS (the default: each task accumulates virtual runtime, and the scheduler always runs the task with the smallest virtual runtime; priorities are adjusted by the
nicevalue).
- Justify your choice with reference to the metrics that matter for each class of workload. For the interactive services, the relevant metric is response time (specifically the tail latency). For the batch jobs, the relevant metric is throughput (jobs completed per hour). State explicitly which metric each policy favours.
-
Analyse the trade-offs. Address:
- What does your policy do well, and what does it do poorly?
- What does your policy do about starvation? If it can starve a process, how is that bounded?
- What is the effect of the policy on the context-switch rate? Is the added overhead justified by the benefit?
- Would you change the policy in a mixed deployment where the interactive and batch workloads run on the same nodes? Or would you separate the workloads onto different nodes and use a different policy on each?
- Optional but encouraged: support your argument with a small numerical example. For example, take three interactive processes with burst times 1, 1, and 1 ms and two batch processes with burst times 20 and 30 ms, and compute the average waiting time and the maximum wait under two of the policies. The numbers need not be large; the point is to show that your reasoning is quantitative.
Your post should be 450–600 words, with the numerical analysis included as a small table or a short calculation. Cite at least one source (a textbook section, a paper, or the Linux kernel documentation on the scheduler).
04 Notes on the policies
The following notes may help you frame your argument. They are not exhaustive; you are expected to bring your own analysis.
4.1 FCFS
FCFS is simple and has no preemption overhead. Its problem is the convoy effect: a long batch job at the head of the queue delays every short interactive process behind it. For a workload with a mix of long and short jobs, the average response time of the interactive processes is poor. FCFS is not a realistic choice for the cluster, but it is the baseline against which the others are compared.
4.2 Round Robin
Round Robin gives every process a fair turn within one quantum of arriving at the head of the queue. With a 10 ms quantum, the response time of an interactive process is bounded by n × 10 ms, where n is the number of runnable processes. Round Robin is good for the interactive services but penalises the batch jobs because the frequent switches add overhead (roughly switch_cost / (quantum + switch_cost) ≈ 1% for 10 ms and 0.1 ms of switch cost). It also does not distinguish between interactive and batch processes.
4.3 Multilevel Feedback Queue
MLFQ approximates the best of both: short interactive processes stay in the high-priority levels, and long batch processes are demoted to the low-priority levels. Aging prevents starvation of the batch jobs. The cost is complexity and a set of tuning parameters (the number of levels, the quanta, the aging threshold) that are difficult to get right for every workload. MLFQ is the conceptual ancestor of the modern Linux scheduler.
4.4 Linux CFS
CFS is a proportional-share scheduler: each task
accumulates virtual runtime proportional to its
actual CPU time divided by its weight (derived
from its nice value), and the
scheduler always runs the task with the smallest
virtual runtime. This gives every task a fair share
of the CPU, weighted by priority. CFS has no fixed
quantum: the time slice is computed from the number
of runnable tasks and a target latency. It handles
the mixed workload well by default, but it does not
distinguish interactive from batch processes except
through the nice value, and its
fairness means that a batch job competes on equal
terms with an interactive service unless the
administrator intervenes.
05 Grading rubric
The discussion is marked out of 100 points. The criteria and their weights are given below.
| Criterion | Weight |
|---|---|
| Post quality (argument, metrics, numerical analysis) | 40% |
| Peer response quality | 30% |
| Engagement and timeliness | 20% |
| Netiquette and clarity | 10% |
5.1 Post quality (40 points)
| Level | Descriptor |
|---|---|
| Exemplary (90–100%) | A clear policy choice with a well-argued justification. The metrics that matter for each workload class are identified and used correctly. The trade-offs are analysed in detail, including the starvation behaviour and the context-switch overhead. The numerical analysis (if included) is correct and supports the argument. A source is cited. |
| Proficient (80–89%) | A clear policy choice with a sound justification. The metrics are identified. The trade-offs are mentioned but not fully analysed. The numerical analysis is present but minimal. A source is cited. |
| Developing (70–79%) | A policy is chosen but the justification is largely descriptive. The metrics are not clearly connected to the policy. The trade-offs and starvation behaviour are not addressed. The numerical analysis is missing or incorrect. |
| Beginning (60–69%) | No clear policy choice, or the choice is not justified. The post summarises the algorithms without evaluating them. |
| Not demonstrated (<60%) | The post is missing, off-topic, or a restatement of the prompt. |
5.2 Peer response quality (30 points)
The descriptors are the same as for Discussion 1. An exemplary reply might:
- Challenge the classmate's policy choice with a concrete counter-example (for example, a workload under which the chosen policy would fail).
- Point out a metric or a trade-off the classmate did not consider.
- Compare the classmate's reasoning with the reasoning in their own post, and explain the disagreement.
5.3 Engagement and timeliness (20 points)
The descriptors are the same as for Discussion 1.
5.4 Netiquette and clarity (10 points)
The descriptors are the same as for Discussion 1.
06 Resources
- Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 5 (CPU Scheduling).
- Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 7–10 (Scheduling).
- Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 2 (Processes and Threads, Section on Scheduling).
- Love, R. Linux Kernel Development, 3rd ed., Chapter 4 (Process Scheduling).
- Linux kernel documentation:
Documentation/scheduler/sched-design-CFS.rst(the design of the CFS scheduler). - Linux man-pages:
man 7 sched,man 2 sched_setscheduler,man 1 nice,man 1 chrt,man 1 taskset. - Bouron, S., Chelius, G., & Fleury, E. Better Understanding of the Linux CFS Scheduler. (Multiple technical reports are available.)