Performance Experiments and Queueing
Prerequisites: S1 probability and statistics; S5 scheduling and networking. Budget: 30-45 hours. Outcome: measure equal work, explain saturation, and separate a model's predictions from empirical results.
Diagnostic
Compute a weighted average for two request classes. Explain why thousands of requests in a single run are not necessarily thousands of independent experimental replications. Repair those gaps in the probability worked examples before proceeding.
Queueing makes overload nonlinear
Little's law relates average in-system work L, throughput lambda, and average time W by L=lambda*W, under a stable system and compatible measurement boundaries. If 200 requests per second spend 0.05 seconds in a service boundary, average in-flight work is 10. This is not automatically the number of workers to provision: workers may block, and requests may queue outside the measured boundary.
For an ideal M/M/1 queue, arrivals are Poisson, service times exponential, there is one server and an unbounded queue, and arrival rate is below service rate. Mean time in the system is 1/(mu-lambda). With capacity mu=100/s, lambda=50/s gives 20 ms; lambda=90/s gives 100 ms. Utilization increases from 50% to 90%, while modeled mean response grows fivefold.
Real workloads often violate these assumptions. The lesson is to inspect queues and saturation, not to fit every production system to this formula.
Worked experiment design
A cache version appears faster because its benchmark repeatedly requests one key. Production has many keys and writes. The experiment measured a favorable workload, not general superiority.
Declare dataset size, key distribution, read/write ratio, concurrency or arrival schedule, warmup, timeout policy, duration, and correctness checks. Compare the same logical work. A closed-loop client that waits for each response lowers offered load during a stall; that can hide the experience of arrivals that would have continued during the stall. Report whether load is open-loop or closed-loop and account for timed-out work.
Alternate baseline and candidate order across repeated runs. Keep raw run-level results; report median and spread, plus request-latency percentiles with sample counts. Do not average p99 values from unequal populations and call the result a global p99. Failed or timed-out requests must not disappear from the report.
Guided assignment
Build a local service or simulator with a bounded worker count and an explicit queue. Use a deterministic service-time mode first, then a seeded variable-time distribution. Drive several offered loads below and above capacity. Compare unbounded acceptance against bounded queueing with rejection.
Record offered, accepted, completed, rejected, and timed-out work; queue depth over time; elapsed duration; response distribution; and completed-work correctness. Add one proposed optimization, such as caching or batching, and compare at least a favorable and unfavorable workload.
Acceptance: account for all offered requests, reproduce the baseline, demonstrate a saturation point, and show the optimization's tradeoff. Re-run independently at least five times as a starting protocol; justify more runs if variation prevents a decision. This minimum is not a statistical guarantee. State what uncertainty your measurements leave unresolved.
Independent transfer
Double arrival rate without changing service capacity. Why might throughput remain almost constant while latency or rejection rises? Check: completed work is capacity-limited; excess demand accumulates or is rejected. A throughput-only dashboard hides that failure.
If results depend on test order, isolate warm caches, compilation, background work, or resource throttling before attributing the difference to code. Retain contradictory measurements and explain the revised hypothesis.
Use the methodology and benchmarking material in Systems Performance. It adds experimental discipline to the existing CSAPP and OS foundations. Defend the workload and inference limits under the rubric.