Mutual Exclusion

Fetch-and-Increment

Fetch-and-increment is a hardware instruction that atomically reads a value and increments it (or adds a signed value — generalized fetch-and-add). It’s what lets you build a ticket lock efficiently.

Why is this more useful than test-and-set for fairness?

Because the atomic increment hands out a sequence number. That’s FCFS by construction — no starvation. Test-and-set gives you “someone wins, others retry” with no ordering; fetch-and-increment gives you a queue line. See Bakery for the software-only version of the same idea.

Atomic pseudocode

int FetchInc( int & val ) {
    // begin atomic
    int temp = val;
    val += 1;
    // end atomic
    return temp;
}

Naive spinlock (broken)

int Lock = 0;  // shared
void Task::main() {
    while ( FetchInc( Lock ) != 0 );   // only one can get 0
    CriticalSection();
    Lock = 0;
}

Lock counter can overflow during busy waiting and starvation (rule 5) — broken.

Ticket lock (proper use)

class ticketLock {
    unsigned int tickets, serving;
public:
    ticketLock() : tickets( 0 ), serving( 0 ) {}
    void acquire() {                              // entry protocol
        int ticket = FetchInc( tickets );         // take a number
        while ( ticket != serving ) {}            // wait until I'm called
    }
    void release() { serving += 1; }              // exit protocol
};

Why overflow is fine here

• Equality test ticket != serving works under overflow (both counters wrap consistently).
• Ticket overflow is a problem only if 2^N + 1 tasks hold tickets simultaneously — practically impossible.
• FIFO service ⇒ no starvation.

Related

• Bakery Algorithm
• Set Instruction
• Swap Instruction
• Spinlock