Measure Scheduling Latency Using Clock Functions

Topic Overview

Latency Is What Users Feel

Throughput averages hide scheduling latency: the time from a thread becoming runnable to actually receiving CPU. A web server can post high requests-per-second while still stuttering if wakeups wait milliseconds behind a long-running batch job.

Measuring Wake-to-Run

Use monotonic clocks around scheduler events:

• Record CLOCK_MONOTONIC when marking a task RUNNABLE
• Record again on first dispatch after wakeup
• Latency = dispatch_time - wakeup_time

For example, if a thread becomes ready at t=1000 us and runs at t=1450 us, scheduling latency is 450 us for that event.

Why This Matters in Production

Scheduling latency is precisely what tools like cyclictest measure to certify Linux's PREEMPT_RT patches for real-time use in robotics and audio production, where a single 50-microsecond spike can cause an audible glitch or a missed control loop deadline. Using CLOCK_MONOTONIC instead of CLOCK_REALTIME here matters in practice too: NTP adjustments to wall-clock time have caused real latency-measurement bugs in production monitoring code.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will instrument your simulator or harness with timestamp hooks and print percentile summaries (p50/p95). This task asks you to compare RR quantum sizes and show how smaller slices cut latency at the cost of more context switches.

Your Task

Scheduling latency is the time between a task becoming runnable (a wakeup) and the moment it actually gets the CPU. Tools like runqlat and cyclictest measure it by timestamping both events. Wall-clock timings would differ on every run, so this task works from an event trace instead. Pair each wakeup with the run that follows it, then report per-task and overall statistics, percentiles, and a log2 histogram.

Input

One event per line: TIME_NS TASK wakeup or TIME_NS TASK run.

Rules

• Times must never decrease. A line earlier than the previous accepted line prints line N: time went backwards, ignored, and an event other than wakeup/run prints line N: unknown event E, ignored. N counts every input line.
• A wakeup makes the task pending. A second wakeup while it is already pending is counted as repeated and changes nothing, because latency is measured from the first one.
• A run while the task is pending gives one sample, run - wakeup, and clears the pending state. A run with nothing pending is counted as without wakeup.
• Per-task lines list tasks in order of first appearance: count, minimum, average (rounded half up to whole ns) and maximum. A task with no samples prints NAME: no samples.
• Percentiles use the nearest-rank method: the value at 1-based rank ceil(P * n / 100) in the sorted samples.
• Histogram buckets are in whole microseconds (ns / 1000, rounded down): 0 -> 1, 2 -> 3, 4 -> 7, 8 -> 15, and so on. Print every bucket from the lowest non-empty one to the highest, empty ones included. Each bucket gets one * per sample; if the largest bucket holds more than 40, scale every bucket to count * 40 / max, rounded down.

Output

cCopy
Loading…

events counts the accepted lines. With no samples at all, print no latency samples after the first line and stop.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Store every sample so the percentiles are exact. Sort a copy once, and index it with integer arithmetic.
2. Use 64-bit integers throughout, because nanosecond timestamps overflow 32 bits after about 4 seconds.

Hidden tests cover repeated wakeups, runs without a wakeup, out-of-order timestamps, unknown event names, a task that never gets a sample, timestamps beyond 32 bits, and a histogram with more than 40 samples in one bucket.