Scheduling is an objective with a queue

Prerequisites: Processes, threads, and CPU execution.

Learning objectives

• Compute waiting, response, and turnaround times for a trace.
• Explain the tradeoff between short-job scheduling and time slicing.
• Distinguish runnable work from blocked work.

A scheduler chooses among runnable work

A process provides a resource and protection context. Threads are execution contexts that can share that process’s address space. A scheduler chooses a runnable thread for a processor. A blocked thread is waiting for an event and is not merely losing a scheduling contest. When the event occurs, it may become runnable again.

For a job arriving at time a, first running at time s, and completing at time c, response time is s−a and turnaround time is c−a. Waiting time counts time spent ready but not running. These measures differ, especially when a job alternates CPU work and I/O.

Work a complete queue

Assume one CPU, zero switching cost, no I/O, and three jobs arriving together at time zero. Their CPU demands are A=8, B=2, and C=1 time units. First-come first-served in A,B,C order completes them at times 8, 10, and 11. Mean turnaround is 29/3, about 9.67. Response times are 0, 8, and 10.

Shortest-job-first runs C,B,A, completing at 1, 3, and 11. Mean turnaround becomes five. The improvement follows from letting short jobs avoid waiting behind long work. However, a real scheduler may not know future CPU demand, and a stream of short arrivals can delay long jobs unless fairness is addressed.

Round robin with a one-unit quantum and initial order A,B,C runs A, B, C, A, B, then A until completion. C completes at three, B at five, and A at eleven. Initial responses are zero, one, and two. Interactive responsiveness improves compared with the first queue, even though completion-time objectives differ.

Include the costs the model omitted

A context switch saves and restores execution state. Its effect can also include cache and translation disruption. A very short quantum provides frequent opportunities to run but can spend excessive time switching. A very long quantum approaches first-come behavior for CPU-bound jobs.

Priority scheduling raises questions about starvation and priority inversion. A low-priority thread holding a lock can delay a high-priority thread while medium-priority work runs. Mechanisms such as priority inheritance address a particular dependency, not every fairness problem.

When evaluating a scheduler, name the workload and objective: interactive response, total completion time, deadlines, fairness, or throughput. Draw arrivals, blocking events, and execution intervals before calculating averages. A scheduling policy cannot be judged solely by a short queue where its assumptions happen to hold.

Primary reading

• Scheduling: Introduction (Arpaci-Dusseau and Arpaci-Dusseau, OSTEP).

Practice problem

Jobs A and B arrive at time zero and require six and two CPU units. Assume no I/O or switch cost. Compare first-come scheduling in A,B order with round robin using a two-unit quantum. Compute response and completion times, and identify which job benefits in responsiveness.

Worked solution

First-come scheduling runs A from zero through six and B from six through eight. A responds immediately and completes at six; B responds at six and completes at eight. Round robin runs A from zero to two, B from two to four, and A from four to eight. A still responds at zero but now completes at eight. B responds at two and completes at four. B therefore receives both an earlier first response and earlier completion, while A finishes later. Both schedules perform the same eight CPU units under the zero-overhead assumption. If context switching had a cost, the more frequently switching schedule would also consume additional elapsed time, which must be included before making a throughput claim.

Check your understanding

A thread waiting for a disk completion is in which relevant state?

• Runnable but always highest priority.
• Blocked until an event makes it eligible again.
• Necessarily terminated.
• Executing continuously on every CPU.

Explanation

Blocked work is waiting for an event, distinct from ready work awaiting CPU service.

Which policy assumption makes shortest-job-first difficult to implement perfectly?

• The scheduler knows exact future CPU demand.
• The machine has registers.
• Jobs have names.
• Time has units.

Explanation

Exact future burst length is usually unavailable, so practical policies estimate or approximate it.

Primary reading

• Scheduling: Introduction: Arpaci-Dusseau and Arpaci-Dusseau, OSTEP

Open the study and save your work →