Sequencer and Eventcount

operating-systems concurrency

Definition

Sequencer and Eventcount

Sequencer and eventcount are low-level synchronisation primitives that provide a way to order events and wait for their completion. They are often used together to implement mutual exclusion and bounded waiting without the complexity of semaphores.

The Primitives

Eventcount

An eventcount $E$ is an integer-valued variable initialised to 0 that represents the number of times a specific event has occurred. It supports three operations:

• advance(E): Increments $E$ by 1 and resumes any processes waiting for this value.
• read(E): Returns the current value of $E$.
• await(E, val): Blocks the calling process until $E\ge \text{val}$.

Sequencer

A sequencer $S$ is an integer-valued variable initialised to 0 that serves as a “ticket server.” It supports one operation:

• ticket(S): Returns the current value of $S$ and then increments $S$.

Implementation of Mutual Exclusion

Using these primitives, a critical section can be protected using a “take a number” approach:

// Global variables
var S: sequencer := 0;
var E: eventcount := 0;
 
// Process Pi:
myticket := ticket(S); // Take a ticket
await(E, myticket);    // Wait until it is my turn
    // --- Critical Section ---
advance(E);            // Signal that I am done, incrementing E

The Deli Counter Analogy

This mechanism can be understood as a service counter (the sequencer) and a “Now Serving” display (the eventcount):

1. Taking a Ticket: When a process calls ticket(S), it receives a unique, increasing number—much like taking a paper ticket at a bakery or deli.
2. Watching the Display: The await(E, myticket) operation is equivalent to the process watching the “Now Serving” display. If the display shows a number smaller than the process’s ticket, it must wait. Because await blocks until $E\ge \text{val}$, the process only proceeds when its number is called.
3. Updating the Display: Once the process finishes its task (the critical section), it calls advance(E). This is like the clerk pressing a button to increment the “Now Serving” number, allowing the person with the next ticket to proceed.

Because each ticket is unique and only one number is “served” at a time (starting from 0), this ensures that only one process enters the critical section at a time and that they do so in strict arrival order.

Benefits

• Fairness: Naturally enforces First-In-First-Out (FIFO) ordering.
• Simplicity: Does not require explicit management of a blocked queue by the programmer, as the await logic handles the blocking.