Exercise set

Operating System CPU Scheduling, Dispatch, and Response-Time Exercises

Solved OS scheduling exercises for context switches, round-robin response, scheduler ticks, CPU affinity, preemption and release gates.

Branch: Computer Engineering
Content: Exercise set
Updated: Jul 03, 2026
Revision: v1.0.0 · reviewed

These exercises focus on operating-system CPU scheduling and dispatch behavior. They cover context-switch loss, round-robin response, scheduler ticks, affinity penalties, run-queue delay, preemption latency, priority inversion and release gates for runtime configuration.

Assume a known workload boundary. Production evidence should include scheduler policy, runtime version, CPU topology, priority map, trace method, load generator and acceptance threshold.

Release Evidence Notes

Scheduler evidence should be trace-based whenever possible. Average CPU utilization is not enough when dispatch overhead, tick frequency, non-preemptive sections, priority inversion or cache migration can dominate response time.

Engineering Boundary Notes

These calculations are screening models for operating-system scheduling. They do not replace kernel tracing, load testing, real-time certification, driver audit, multicore interference analysis or workload-specific performance qualification.

Scenario Map

Scenario	Exercises	Primary check	Engineering decision
Dispatch overhead	1, 3, 5, 13	Context switch, scheduler tick, migration and tracing overhead	Decide whether runtime overhead is acceptable.
Response time	2, 6, 7, 8, 10, 14	Round-robin waiting, run queue, preemption and blocking	Decide whether service response has enough margin.
Scheduling policy	4, 9, 11, 12, 15, 16	Affinity, priority aging, utilization and deadline policy	Decide whether scheduler configuration should change.
Release gate	17, 18	Starvation and all-of scheduling gate	Decide whether deployment can proceed.

Exercise 1: Context-Switch CPU Loss

A workload performs $4200$ context switches per second. Each switch costs $3.5\ \mu\text{s}$ . Compute CPU percentage lost.

Solution

U=4200(3.5\times10^{-6})=0.0147

U=1.47\%

Engineering Comment

This overhead is small but measurable. The release trace should use the same kernel, tracing level and workload mix as production.

Plausibility Check

Thousands of switches at a few microseconds each should consume about one percent of a CPU.

Exercise 2: Round-Robin Time-Slice Response

Five runnable tasks share one CPU with round-robin quantum $20\ \text{ms}$ . A newly ready task may wait behind four tasks. Estimate worst wait before its first run.

Solution

W=4(20)=80\ \text{ms}

Engineering Comment

This is a simple worst-position screen. Real response also includes context-switch overhead and whether tasks block before using their full quantum.

Plausibility Check

Waiting for four full quanta at twenty milliseconds each gives eighty milliseconds.

Exercise 3: Scheduler Tick Overhead

A scheduler tick runs at $1000\ \text{Hz}$ and costs $2.2\ \mu\text{s}$ per tick. Compute CPU overhead.

Solution

U=1000(2.2\times10^{-6})=0.0022=0.22\%

Engineering Comment

The tick overhead is low, but tick frequency can still affect power, latency and timer precision.

Plausibility Check

One thousand very short events per second should be well below one percent CPU.

Exercise 4: CPU Affinity Cache Penalty

A service takes $4.0\ \text{ms}$ when it stays on the same core and $4.6\ \text{ms}$ after migration. Compute migration penalty percentage.

Solution

p=\dfrac{4.6-4.0}{4.0}=0.15=15\%

Engineering Comment

CPU affinity can improve cache locality but may reduce load balancing. The decision should use tail latency, not only mean time.

Plausibility Check

An added $0.6\ \text{ms}$ on $4.0\ \text{ms}$ is a mid-teen percentage.

Exercise 5: Dispatch Overhead per Request

A request triggers $6$ context switches. Each costs $4\ \mu\text{s}$ . At $2500$ requests per second, compute CPU overhead.

Solution

Switches per second:

N=6(2500)=15000

CPU overhead:

U=15000(4\times10^{-6})=0.060=6.0\%

Engineering Comment

The overhead is no longer trivial. Batching, fewer thread handoffs or async design may be needed.

Plausibility Check

Fifteen thousand switches per second at several microseconds each reaches several CPU percent.

Exercise 6: Run-Queue Waiting Time

A CPU has average runnable queue length $6$ including the running task. Mean service time per dispatch slice is $8\ \text{ms}$ . Estimate waiting time before service for a new task.

Solution

Tasks ahead are:

N=6-1=5

Waiting time:

W=5(8)=40\ \text{ms}

Engineering Comment

Queue length should be measured under the target load. Averages can hide bursts that dominate response.

Plausibility Check

Five tasks ahead at eight milliseconds each gives forty milliseconds.

Exercise 7: Preemption-Latency Margin

A task must begin within $2.0\ \text{ms}$ . Measured worst preemption latency is $0.55\ \text{ms}$ , dispatch time is $0.12\ \text{ms}$ and interrupt masking adds $0.30\ \text{ms}$ . Compute margin.

Solution

L=0.55+0.12+0.30=0.97\ \text{ms}

M=2.0-0.97=1.03\ \text{ms}

Engineering Comment

The margin passes, but the interrupt masking term must be measured in the released driver stack.

Plausibility Check

All components are below one millisecond combined, leaving about one millisecond margin.

Exercise 8: Blocking Section Response

A service has execution time $1.6\ \text{ms}$ , queue wait $2.4\ \text{ms}$ and non-preemptive blocking $0.7\ \text{ms}$ . Requirement is $5.0\ \text{ms}$ . Compute margin.

Solution

R=1.6+2.4+0.7=4.7\ \text{ms}

M=5.0-4.7=0.3\ \text{ms}

Engineering Comment

The response passes narrowly. Reducing non-preemptive work would be a high-value improvement.

Plausibility Check

The three terms nearly sum to the requirement, so margin should be small.

Exercise 9: Priority Aging Wait Limit

A scheduler raises a waiting job one priority level every $50\ \text{ms}$ . A job needs four raises to reach service priority. Estimate maximum aging delay.

Solution

T=4(50)=200\ \text{ms}

Engineering Comment

Priority aging limits starvation, but it may still be too slow for interactive or control workloads.

Plausibility Check

Four equal aging intervals produce exactly two hundred milliseconds.

Exercise 10: Priority-Inversion Blocking

A high-priority task has base response $3.0\ \text{ms}$ . A lower-priority critical section can block it for $2.2\ \text{ms}$ . Deadline is $6.0\ \text{ms}$ . Compute margin.

Solution

R=3.0+2.2=5.2\ \text{ms}

M=6.0-5.2=0.8\ \text{ms}

Engineering Comment

The task passes but depends heavily on the blocking bound. Priority inheritance or shorter critical sections may be needed.

Plausibility Check

The blocking term is large relative to base response, leaving less than one millisecond margin.

Exercise 11: Rate-Monotonic Utilization Screen

Three periodic OS services have utilizations $0.18$ , $0.22$ and $0.16$ . Compare with the RM sufficient bound for $n=3$ .

Solution

U=0.18+0.22+0.16=0.56

U_{LL}=3(2^{1/3}-1)=0.780

Since:

0.56<0.780

the set passes the sufficient screen.

Engineering Comment

This is a sufficient test, not a full proof of every OS overhead and blocking path.

Plausibility Check

A utilization near fifty-six percent should pass the three-task RM bound.

Exercise 12: EDF Utilization Screen

Four implicit-deadline jobs have utilization $0.20$ , $0.15$ , $0.18$ and $0.12$ . Check EDF utilization.

Solution

U=0.20+0.15+0.18+0.12=0.65

For implicit-deadline EDF:

U\le1

so the set passes.

Engineering Comment

EDF can use more CPU than fixed-priority scheduling, but release still needs overhead and overload behavior checks.

Plausibility Check

Sixty-five percent is clearly below one full CPU.

Exercise 13: Trace Overhead Allowance

Scheduler tracing adds $0.4\ \mu\text{s}$ to each of $18000$ events per second. Compute tracing CPU cost.

Solution

U=18000(0.4\times10^{-6})=0.0072=0.72\%

Engineering Comment

Trace overhead is small but should be subtracted or bounded when using traces as release evidence.

Plausibility Check

Less than a microsecond per event at tens of thousands of events per second stays below one percent.

Exercise 14: Interactive Tail Response Gate

The $99$ th percentile response is $85\ \text{ms}$ . The release limit is $100\ \text{ms}$ with $10\ \text{ms}$ guard. Decide status.

Solution

Guarded limit:

L_g=100-10=90\ \text{ms}

Since:

85<90

the tail response passes.

Engineering Comment

The result should come from representative load. A single clean benchmark is weak release evidence.

Plausibility Check

The response is below both the raw and guarded limit.

Exercise 15: Quantum Selection Trade-Off

A task needs $12\ \text{ms}$ CPU. Compare number of quanta with $5\ \text{ms}$ and $20\ \text{ms}$ quantum sizes.

Solution

For $5\ \text{ms}$ :

N_5=\left\lceil\dfrac{12}{5}\right\rceil=3

For $20\ \text{ms}$ :

N_{20}=\left\lceil\dfrac{12}{20}\right\rceil=1

Engineering Comment

Shorter quanta improve responsiveness but increase context-switch overhead. Longer quanta reduce overhead but can increase waiting time.

Plausibility Check

A twelve-millisecond CPU burst cannot fit in two five-millisecond quanta, but it fits in one twenty-millisecond quantum.

Exercise 16: CPU Reservation Check

A service has reservation $25\%$ CPU. Its measured guarded demand is $18\ \text{ms}$ every $80\ \text{ms}$ . Check margin.

Solution

Demand fraction:

U=\dfrac{18}{80}=0.225=22.5\%

Margin:

M=25.0\%-22.5\%=2.5\%

Engineering Comment

The reservation passes but has little margin for instrumentation, kernel changes or workload growth.

Plausibility Check

Eighteen is slightly less than one quarter of eighty.

Exercise 17: Starvation Screen

A low-priority maintenance task must run at least once every $5\ \text{s}$ . Trace shows maximum gap $6.4\ \text{s}$ . Decide status.

Solution

Because:

6.4>5.0

the starvation screen fails by:

6.4-5.0=1.4\ \text{s}

Engineering Comment

Starvation of maintenance tasks can delay cleanup, monitoring or health reporting. Aging or reservation policy may be needed.

Plausibility Check

The observed maximum gap is clearly larger than the requirement.

Exercise 18: OS Scheduling Release Gate

A release gate requires context overhead pass, tail response pass, starvation pass, priority-inversion pass and trace-overhead pass. Results are pass, pass, fail, pass and pass. Decide status.

Solution

The all-of gate fails because starvation failed:

G=\text{blocked}

Engineering Comment

A scheduler can look efficient and still be unreleasable if a required task starves.

Plausibility Check

One failed required condition blocks the release gate.

Common Release Mistakes

Reporting CPU utilization without dispatch, tick and trace overhead.
Validating average latency while ignoring tail response.
Changing CPU affinity without measuring cache and load-balance effects.
Treating priority aging as acceptable without a maximum wait requirement.
Ignoring starvation of maintenance or health tasks.
Using traces from a different kernel, load or instrumentation mode.

Validation Package Checklist

Scheduler policy, priority map, quantum, tick and CPU affinity configuration.
Context-switch, dispatch, preemption and trace-overhead measurements.
Tail-response and starvation evidence under representative load.
Blocking and priority-inversion measurements for shared resources.
CPU reservation or utilization screen with guard margin.
Release gate tied to worst-case trace evidence, not average load only.

REF