How Does a Timing Wheel Work?

A timing wheel is a data structure for organizing tasks that should become ready at different points in time. Instead of storing every task in one continuously sorted collection, it divides future time into slots arranged in a circle. Each task is placed into the slot associated with its delay, and a moving pointer advances through those slots as time progresses.

The basic mechanism has three parts:

1. Task insertion: calculate the slot that corresponds to a task's delay and place the task there.
2. Pointer advancement: move a pointer from one slot to the next as time advances.
3. Round counting: distinguish tasks that share a slot but are due on different revolutions of the wheel.

This article uses a six-slot timing wheel as the running example. Six slots are small enough to make wraparound and long delays easy to see. The same ideas can be applied to a wheel with a different number of slots.

The central mental model is:

slot position + revolution information = scheduled time

A slot tells us where a task belongs within one revolution. A round counter tells us how many complete revolutions must pass before that task is ready.

The Circular Time Model​

Imagine a clock face with six positions instead of twelve. Each position is a bucket that can contain one or more tasks. A pointer marks the current position, and it moves around the circle as time advances.

The wheel can be drawn like this:

        [0]
    [5]     [1]
    [4]     [2]
        [3]

The visual shape is not important. What matters is the repeating sequence:

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 0 -> ...

Assume that one slot represents one unit of time. If the pointer is currently at slot 0, a task with a delay of one time unit belongs in slot 1. A task with a delay of two units belongs in slot 2, and so on.

The pointer does not move every task from bucket to bucket. Instead, tasks generally stay where they were inserted while the pointer changes which bucket represents the current time position. When the pointer reaches a bucket, the scheduler examines the tasks stored there and decides which ones are ready.

This separation is the key idea behind the data structure:

• The wheel stores tasks according to their positions in repeating time.
• The pointer represents the passage of time through those positions.
• The round counter distinguishes one visit to a slot from a later visit to the same slot.

Why Organize Tasks into Slots?​

A scheduler repeatedly needs to answer a basic question: which tasks are ready now?

One possible design is to keep tasks in a structure ordered by deadline. When a task is inserted, the scheduler places it according to its absolute deadline. When time advances, it examines the earliest task. This approach can be useful, but maintaining a global ordering requires work whenever tasks are added or changed.

A timing wheel takes a different approach. It maps a delay to a position using circular arithmetic. Rather than maintaining one globally sorted sequence, it groups tasks by their future position in a repeating time range.

For a wheel with six slots, if the current pointer is at position p and a task has a delay of d time units, its target position is conceptually:

(p + d) modulo 6

For example, if the pointer is at slot 4:

Delay 1: (4 + 1) modulo 6 = 5
Delay 2: (4 + 2) modulo 6 = 0
Delay 3: (4 + 3) modulo 6 = 1

The modulo operation causes the position to wrap back to 0 after 5. A task delayed by two units from slot 4 therefore belongs in slot 0, because the pointer will visit 5 first and then wrap to 0.

However, the slot calculation alone is not enough for long delays. Modulo arithmetic records the position within a cycle but discards the number of complete cycles. That missing information is represented by the round counter.

A Six-Slot Example​

Assume the following initial state:

Current pointer: 0
Wheel size: 6
One slot: one unit of time

Now insert three tasks:

• Task A has a delay of 1.
• Task B has a delay of 3.
• Task C has a delay of 5.

Their target positions are:

Task A: (0 + 1) modulo 6 = 1
Task B: (0 + 3) modulo 6 = 3
Task C: (0 + 5) modulo 6 = 5

The wheel now contains:

Slot 0: empty
Slot 1: Task A
Slot 2: empty
Slot 3: Task B
Slot 4: empty
Slot 5: Task C

As the pointer advances, the scheduler visits these positions:

Time 0: pointer at 0
Time 1: pointer at 1, process Task A
Time 2: pointer at 2
Time 3: pointer at 3, process Task B
Time 4: pointer at 4
Time 5: pointer at 5, process Task C

After slot 5, the next movement returns to slot 0. The wheel has completed one full revolution.

This simple example illustrates the relationship between insertion and advancement. Insertion places a task at the position reached after its delay. Advancement visits positions in time order. When the pointer reaches the task's position at the correct point in the cycle, the task becomes ready.

Inserting a Task​

Task insertion requires at least two pieces of information:

• The current pointer position.
• The task's delay, or a delay calculated from its deadline.

For a delay that fits within the next revolution, the target slot can be calculated directly. Suppose the pointer is at slot 2 and a task has a delay of 4:

(2 + 4) modulo 6 = 0

The task belongs in slot 0. Although 0 is numerically smaller than 2, it is four pointer advances away in the circular sequence:

2 -> 3 -> 4 -> 5 -> 0

This is why slot numbers should not be treated as absolute timestamps. They are positions on a repeating wheel. A task in slot 0 may be due soon or much later, depending on the pointer's current position and the task's round information.

A conceptual insertion operation looks like this:

insert(task, delay):
    target_slot = (current_slot + delay) modulo wheel_size
    rounds = delay divided by wheel_size, using whole-number division
    add task and rounds to wheel[target_slot]

The exact treatment of a zero delay and the current slot depends on the scheduler's boundary convention. For example, a design must decide whether the current slot represents the instant currently being processed or the next interval to be processed. The important requirement is consistency: insertion and advancement must interpret slot boundaries in the same way.

For short delays, the target slot may be enough to understand the placement. For longer delays, the round count is essential.

Why a Slot Number Is Not Enough​

Consider a six-slot wheel with the pointer currently at slot 0. Compare two tasks:

• Task A has a delay of 1.
• Task B has a delay of 7.

Their target positions are:

Task A: (0 + 1) modulo 6 = 1
Task B: (0 + 7) modulo 6 = 1

Both tasks belong in slot 1, but they are not due at the same time. Task A should be ready on the next visit to slot 1. Task B should wait for one complete revolution and become ready on the following visit to slot 1.

The slot index stores only the remainder of the delay after division by the wheel size. It does not store the number of complete revolutions. To represent the full delay, each task needs two values:

• A slot index, identifying its position inside a revolution.
• A round count, identifying how many complete revolutions remain.

For a wheel size of 6, any delay can be decomposed as:

delay = rounds * 6 + remainder

For a delay of 7:

7 = 1 * 6 + 1

The target slot is therefore the position associated with remainder 1, while the round information records one complete revolution.

For a delay of 13:

13 = 2 * 6 + 1

This task also belongs in slot 1, but it must wait through two complete revolutions before becoming ready.

The round-counter trick allows a small physical wheel to represent delays longer than one revolution without creating a separate slot for every possible delay.

Understanding the Round Counter​

The round counter can be viewed as a countdown attached to a task. Every time the pointer visits the task's slot, the scheduler checks that task's counter.

If complete revolutions still remain, the task is not ready. The scheduler updates the round information and leaves the task associated with the slot for a later visit. When the counter reaches the state that represents the final required visit, the task becomes ready.

There are several equivalent ways to define the stored value. An implementation might store:

• The number of complete revolutions remaining.
• The absolute revolution number at which the task should run.
• Another equivalent value that allows the scheduler to compare the current revolution with the task's due revolution.

The exact representation can differ, but the conceptual division remains the same: the slot handles the within-cycle position, and the round information handles complete cycles.

Suppose the pointer starts at slot 0, and insert these tasks:

Task A: delay 1
Task B: delay 7
Task C: delay 13

Their decompositions are:

Task A: 1  = 0 * 6 + 1
Task B: 7  = 1 * 6 + 1
Task C: 13 = 2 * 6 + 1

All three tasks go into slot 1, but their round values differ. The scheduler encounters slot 1 once per revolution:

First visit to slot 1:  Task A is ready; Task B and Task C wait
Second visit to slot 1: Task B is ready; Task C waits
Third visit to slot 1:  Task C is ready

The bucket is reused. The round information prevents the tasks from running early.

Advancing the Pointer​

Pointer advancement is what makes time move through the wheel. At each time step, the pointer moves to the next slot, wrapping around after the final slot.

For a six-slot wheel:

current_slot = (current_slot + 1) modulo 6

Starting at slot 0, repeated advancement produces:

0, 1, 2, 3, 4, 5, 0, 1, ...

When the pointer reaches a slot, the scheduler examines the tasks in that bucket. For each task, it checks the round information. A matching slot does not automatically mean that the task is ready; the task must also be at the correct revolution.

Conceptually:

advance():
    current_slot = (current_slot + 1) modulo wheel_size

    for each task in wheel[current_slot]:
        if the task is due on this revolution:
            remove the task
            make it ready
        else:
            update its round information

This pseudocode intentionally leaves the exact counter convention open. One implementation might decrement a positive counter on each visit and execute when it reaches a terminal state. Another might store a due-revolution identifier and compare it with the current revolution. Both approaches can express the same rule.

The essential behavior is that the pointer visits every slot in order, and tasks are released only when both conditions are satisfied:

1. The pointer has reached the task's target slot.
2. The required number of complete revolutions has passed.

A Complete Walkthrough with Long Delays​

Consider a six-slot wheel with the pointer initially at slot 0. Insert four tasks:

Task A: delay 2
Task B: delay 6
Task C: delay 8
Task D: delay 14

Break each delay into a quotient and remainder using the wheel size:

Task A:  2 = 0 * 6 + 2
Task B:  6 = 1 * 6 + 0
Task C:  8 = 1 * 6 + 2
Task D: 14 = 2 * 6 + 2

Their target slots are:

Task A: slot 2
Task B: slot 0
Task C: slot 2
Task D: slot 2

The wheel can be summarized as:

Slot 0: Task B, with one-revolution information
Slot 1: empty
Slot 2: Task A, Task C, Task D
Slot 3: empty
Slot 4: empty
Slot 5: empty

The tasks in slot 2 share a position but have different delays:

• Task A is due on the first relevant visit to slot 2.
• Task C is due after one complete revolution and then a visit to slot 2.
• Task D is due after two complete revolutions and then a visit to slot 2.

The pointer advances from 0 to 1, then to 2. During that first visit to slot 2, Task A becomes ready. Task C and Task D remain because their round information says that their delays have not elapsed.

The pointer continues through slots 3, 4, and 5, then wraps to slot 0. At slot 0, Task B is handled according to the chosen round-counter convention. The pointer then reaches slots 1 and 2 again. On the next relevant visit to slot 2, Task C becomes ready, while Task D continues waiting. On the later visit required by its round information, Task D becomes ready.

This example demonstrates a two-dimensional representation of time:

absolute delay = within-revolution position + complete revolutions

The slot gives the local position. The counter gives the larger-scale distance.

Multiple Tasks in One Slot​

A slot is a bucket, not necessarily a location for only one task. Many tasks can map to the same slot, especially when the wheel has few slots or when delays have the same remainder modulo the wheel size.

For example, with a pointer at 0, delays 2, 8, and 14 all map to slot 2:

2  modulo 6 = 2
8  modulo 6 = 2
14 modulo 6 = 2

Their round values are different:

2  = 0 * 6 + 2
8  = 1 * 6 + 2
14 = 2 * 6 + 2

When slot 2 is processed, the scheduler examines every task in that bucket. It may:

• Release tasks whose round information says they are due.
• Reduce or update the round information of tasks that must wait.
• Keep waiting tasks in the bucket for a later visit.

The internal structure of a bucket is an implementation choice. It might be a list or another collection that supports inspecting and removing entries. The timing-wheel idea does not require one particular container. It requires that the scheduler can inspect tasks associated with the current slot and preserve tasks that are not yet ready.

Processing a bucket must also avoid a common mistake: releasing every task merely because the pointer has reached the shared slot. Tasks with different round values are intentionally due on different visits.

Insertion from a Nonzero Current Position​

The target calculation must be relative to the current pointer. It must not assume that the pointer is always at slot 0.

Suppose the pointer is currently at slot 4, and insert tasks with delays of 1, 2, and 5:

Delay 1: (4 + 1) modulo 6 = 5
Delay 2: (4 + 2) modulo 6 = 0
Delay 5: (4 + 5) modulo 6 = 3

The positions reached in time order are:

5, 0, 1, 2, 3

Numerically, the sequence appears to move backward after 5, but circularly it is the next five positions. This is why comparing slot numbers as ordinary linear values can lead to errors.

A delay of 8 from slot 4 maps to slot 0:

(4 + 8) modulo 6 = 0

The pointer reaches that slot after eight advances. The round information preserves the fact that the task is not due during the first ordinary visit to slot 0.

The current pointer acts as the origin for every new delay. If an implementation accidentally calculates all target slots from a fixed origin, tasks inserted after the pointer has moved will be scheduled at incorrect times.

What the Pointer Does Not Do​

The pointer does not need to move every task to a new slot whenever time advances. That would require updating a large number of tasks repeatedly and would undermine the purpose of the circular organization.

Instead, the pointer changes the interpretation of the buckets. A task can stay in one bucket while the pointer travels around the wheel. When the pointer visits that bucket, the scheduler checks the task's round information.

This gives the data structure a useful separation of responsibilities:

• The wheel stores tasks spatially according to a repeating time position.
• The pointer advances globally as time moves forward.
• The round counter resolves ambiguity caused by repeated slot visits.

In other words, time is not represented by constantly subtracting one from every task's remaining delay. The global pointer moves, and task-specific work occurs when a relevant bucket is processed.

Correctness Intuition​

The representation works because every delay can be divided into complete wheel revolutions and a remainder.

Let:

• p be the current pointer position.
• d be a task's delay.
• w be the wheel size.

Write the delay as:

d = q * w + r

where q is the whole-number quotient and r is the remainder.

After d pointer advances:

• The pointer has completed q full revolutions.
• It has advanced another r positions within the next revolution.
• Its slot is (p + r) modulo w.

The target slot stores the remainder position, and the round information stores the complete-revolution component. Together they identify the position reached after the entire delay.

For a short delay, q may be zero. For a delay equal to the wheel size, q is one and r is zero. For a delay longer than one revolution, q is positive and the target slot may be the same as that of a much shorter task.

The correctness requirement is consistency. Insertion must calculate slot and round information using the same boundary interpretation that advancement uses. If one operation treats a slot as representing the current instant while the other treats it as representing the next interval, tasks can run early or late.

Important Boundary Cases​

Timing-wheel implementations should explicitly define several boundary cases.

Delay of Zero​

A delay of zero raises a policy question. Should the task run immediately? Should it run during the current processing step? Or should it run on the next pointer advancement?

There is no single answer implied by the circular structure. The implementation must choose a convention and apply it consistently. The choice affects the target slot and the order in which insertion and advancement interact.

Delay Equal to the Wheel Size​

With six slots, a delay of 6 produces:

(current + 6) modulo 6 = current

The task maps to the current numeric slot, but it is not necessarily due immediately. It represents a complete revolution. This is one of the clearest examples of why the slot index cannot stand alone.

Delay One Greater Than the Wheel Size​

A delay of 7 maps to the slot after the current one and requires one complete revolution. It must not be confused with a delay of 1, even though both share the same remainder modulo 6.

Several Tasks in One Bucket​

Tasks sharing a slot can have different round counts. Processing one task must not accidentally release the others. The scheduler must inspect each task's round information independently.

Insertion While a Slot Is Being Processed​

If a new task is inserted while the current bucket is being processed, the implementation needs a policy for whether that task can become ready in the same processing step or must wait for a later visit. This is another consequence of the chosen slot-boundary convention.

These cases are valuable because they make the abstract rules concrete. They should be included in tests and examples rather than left to accidental behavior.

Conceptual Pseudocode​

The following pseudocode presents the main operations for a six-slot wheel:

wheel_size = 6
current_slot = 0
wheel = an array containing six buckets

insert(task, delay):
    target_slot = (current_slot + delay) modulo wheel_size
    remaining_rounds = delay divided by wheel_size, using whole-number division
    add (task, remaining_rounds) to wheel[target_slot]

advance():
    current_slot = (current_slot + 1) modulo wheel_size

    for each entry in wheel[current_slot]:
        if entry's round information says it is due:
            remove entry from the bucket
            make its task ready
        else:
            update entry's round information

The phrase “round information says it is due” is intentionally abstract. A concrete implementation must decide whether the stored value is decremented before or after the check, and how it represents the final eligible state. Those choices affect details such as a delay equal to the wheel size or a delay of zero.

A production scheduler may also need behavior for cancellation, repeated scheduling, completed tasks, and the mechanism that supplies time steps. Those concerns are separate from the central timing-wheel operations discussed here: calculate a slot, advance the pointer, and use revolution information for long delays.

Complexity Perspective​

The target-slot calculation is direct. It uses arithmetic involving the current position, the delay, and the wheel size rather than walking through all slots to find a location.

Pointer advancement also moves directly to the next slot. The task-specific work performed during an advancement depends on the bucket that has been reached:

• An empty bucket requires little task-specific processing.
• A bucket containing several tasks requires inspecting those tasks.
• Waiting tasks may need their round information updated.
• Ready tasks must be removed or otherwise marked as ready.

This distinction is important. The wheel makes pointer movement and position calculation simple, but it does not eliminate work associated with tasks in the current bucket.

A small wheel can cause many tasks to share a bucket, particularly when their delays have the same remainder modulo the wheel size. The round counter preserves correctness, but each relevant task still has to be examined when the bucket is processed.

Consequently, practical behavior depends on several factors:

• The number of wheel slots.
• The time represented by each slot.
• How delays are distributed among slots.
• How many tasks occupy each bucket.
• How much work is required when a task becomes ready.

The important organizing advantage is that insertion is based on circular placement rather than maintaining one globally ordered collection for every task. The precise performance depends on the bucket contents and the surrounding scheduler design.

Choosing a Six-Slot Wheel for Learning​

Six is not special because it is universally the best wheel size. It is useful as a teaching model because the cycle is short and wraparound happens frequently.

A six-slot wheel makes it easy to observe:

• The sequence 0 through 5, followed by 0.
• Modulo-based insertion.
• Several delays mapping to the same position.
• The need for round information.
• The difference between a slot visit and a complete revolution.

For example, delays 1, 7, and 13 all have remainder 1 when divided by 6. They can therefore share a target slot while becoming ready on different revolutions.

A larger wheel follows the same rules but may make wraparound less visible in a diagram. A smaller wheel causes more tasks to share positions. In every case, the model remains the same: a circular position plus information about the number of revolutions.

A Calendar Analogy​

A repeating calendar provides a useful analogy. The word “Monday” does not identify one absolute date. It might mean this coming Monday, the Monday after that, or a Monday several weeks later. To identify the intended date, we need both:

• The weekday position.
• The number of weeks to wait.

A timing-wheel slot works like a repeating weekday. Slot 2 can be reached on every revolution, so the slot number alone cannot identify which visit is intended. The round counter supplies the missing information.

The analogy also explains why a long delay is not solved merely by adding modulo arithmetic. Modulo arithmetic tells us the repeating position, just as a weekday tells us a position in a weekly cycle. It does not preserve the number of complete cycles. That information must be stored separately.

Common Misunderstandings​

“A Slot Number Is an Absolute Deadline”​

It is not. Slot numbers repeat on every revolution. A slot is meaningful only in relation to the current pointer and the task's round information.

“A Task in the Current Slot Must Run Immediately”​

Not necessarily. A task may map to the current numeric slot because its delay is one or more complete wheel lengths. The round counter distinguishes that task from one that is ready now.

“The Wheel Moves Every Task as It Advances”​

The central mechanism is the moving pointer. Tasks can remain in their buckets while the pointer changes which bucket is current.

“Modulo Arithmetic Represents the Entire Delay”​

Modulo arithmetic represents only the remainder within a cycle. It discards complete cycles, which is why long delays require round information.

“Every Task in One Bucket Is Due Together”​

Tasks in one bucket may have different round values. They can become ready on different visits to that bucket.

“A Larger Wheel Eliminates the Need for a Counter”​

A larger wheel covers more positions in one revolution, but any delay beyond one revolution still wraps around. Long delays still need revolution information unless another structure represents them.

A Practical Debugging Strategy​

A small, visible wheel is useful when validating an implementation. Use six slots and log the state at every important operation:

current slot
current revolution, if tracked
inserted delay
target slot
stored round information
slot being processed
whether each task waits or becomes ready

Start with one task at a time. Test delays such as:

0, 1, 2, 5, 6, 7, 12, 13

These values exercise several important boundaries:

• The zero-delay policy.
• Short delays near the beginning of the cycle.
• The final slot before wraparound.
• An exact multiple of the wheel size.
• A value just beyond one complete revolution.
• Multiple complete revolutions.

Then test tasks that share a slot:

1, 7, 13

When inserted from the same current position, they should map to the same target slot but become ready on different visits to that slot.

Next, move the pointer away from slot 0 before inserting tasks. This checks that placement is relative to the current pointer rather than accidentally calculated from a fixed origin.

A useful invariant is:

number of pointer advances until readiness = requested delay

The exact interpretation of a delay of zero depends on the implementation's convention, but every other test should respect the chosen timing model. Checking this invariant can reveal incorrect modulo calculations, off-by-one errors, and round-counter mistakes.

Practical Takeaways​

A timing wheel can be understood through three operations.

1. Insert by Position​

Use the current pointer and the delay to find the target slot:

target_slot = (current_slot + delay) modulo wheel_size

The modulo operation handles wraparound around the circular array.

2. Advance by Moving the Pointer​

Time progresses as the pointer moves to the next slot:

current_slot = (current_slot + 1) modulo wheel_size

After slot 5, the pointer returns to slot 0 in the six-slot example.

3. Track Complete Revolutions​

The target slot stores the remainder after complete revolutions are removed. The round counter stores the complete-revolution component:

delay = rounds * 6 + remainder

A task becomes ready only when the pointer reaches its target slot on the correct revolution.

Final Summary​

A timing wheel organizes scheduled tasks in a circular array of time slots. In the six-slot model, the pointer moves through positions 0, 1, 2, 3, 4, 5, and then wraps back to 0.

When a task is inserted, its delay is converted into a target slot relative to the current pointer. Modulo arithmetic handles the circular layout. However, delays that differ by complete wheel revolutions can produce the same target slot. For example, delays of 1, 7, and 13 all have remainder 1 modulo 6, but they are due on different visits to that slot.

The round-counter technique resolves this ambiguity. The slot identifies the task's position within a revolution, while the round information identifies how many complete revolutions must pass. Pointer advancement then visits each bucket in order, and the scheduler releases only tasks whose slot and round information both indicate that their delays have elapsed.

The lasting mental model is:

slot position + revolution count = scheduled time

Once that relationship is clear, task insertion, pointer advancement, and long-delay handling become parts of one coherent circular representation of time.