Test-and-set, swap and atomic instructions

Why it exists

The software solutions of the previous page work only for two processes (Peterson) or are slow (the bakery), and they assume that memory behaves in a simple order that real processors do not promise. The cure is a single machine instruction that reads a memory location and writes it again with nothing able to come in between: an atomic read-modify-write. With it, mutual exclusion for any number of threads needs only a few lines. GATE asks what these instructions do, which properties of the locks built on them hold (mutual exclusion, progress, bounded waiting, first-come first-served), and whether a given lock is correct.

Prerequisites

You need the three requirements of a solution to the critical-section problem: mutual exclusion, progress and bounded waiting.

Precise definitions

Disabling interrupts. On one processor a thread can be switched out only when an interrupt (the timer) arrives. If the thread disables interrupts on entry and enables them on exit, nobody else runs in between. It works only in the kernel (a user program must not be able to do it), only on a uniprocessor (another processor keeps running), and it delays the handling of real events if the section is long.

Atomic instruction. An instruction whose read and write of one memory location happen as a single step: no other access to that location, by any processor, is interleaved. The four classic ones, in C-like notation (each function body is ONE hardware step):

boolean test_and_set(boolean *target)           { boolean old = *target; *target = true;    return old; }
void    swap(boolean *a, boolean *b)            { boolean t = *a; *a = *b; *b = t; }
int     compare_and_swap(int *v, int expected, int new)
                                                { int old = *v; if (old == expected) *v = new;   return old; }
int     fetch_and_add(int *v, int i)            { int old = *v; *v = old + i;               return old; }

Spinlock with test-and-set. lock is a shared variable, false (0) when free.

entry:  while (test_and_set(&lock)) ;       /* spin until it returns false */
        critical section
exit:   lock = false;

The first thread to execute test_and_set gets false back and has set the lock; everyone after it gets true and spins. The same lock can be written with swap (key = true; while (key) swap(&lock, &key);) or with compare_and_swap(&lock, 0, 1) != 0 as the spin condition.

What it guarantees.

• Mutual exclusion: yes. Only one test_and_set can ever return false between two releases.
• Progress: yes. If the lock is free, some spinner gets it; a thread outside the competition holds nothing. The system cannot get stuck.
• Bounded waiting: no. A waiting thread can be overtaken as often as the scheduler likes, because the winner of each race is arbitrary. Waiting is not first-come first-served.
• Two threads in the critical section: impossible.

Bounded waiting with test-and-set. Shared lock and waiting[0..n-1], private key:

waiting[i] = true;  key = true;
while (waiting[i] && key)  key = test_and_set(&lock);
waiting[i] = false;
        critical section
j = (i + 1) % n;
while (j != i && !waiting[j])  j = (j + 1) % n;
if (j == i)  lock = false;  else  waiting[j] = false;

A leaving thread does not just free the lock: it looks for the next waiting thread in the order $i + 1, i + 2, \ldots$ and hands the critical section to it by clearing its waiting flag (the lock stays true). So a waiting thread is overtaken at most $n - 1$ times.

Ticket lock with fetch-and-add. Two shared counters, next (the next ticket to give) and now (the ticket being served):

entry:  my = fetch_and_add(&next, 1);  while (now != my) ;
exit:   now = now + 1;

Threads enter in the order of their tickets: first come, first served, and a thread is overtaken only by those that took a ticket before it.

A lock that looks right and is wrong. Consider

acquire:  while (fetch_and_add(&L, 1)) L = 1;          release:  L = 0;

with $L = 0$ meaning free. A thread that finds $L$ non-zero adds 1 to it and then writes $L = 1$. If the holder writes $L = 0$ between the spinner's add and the spinner's write, the spinner puts $L = 1$ back: the lock is free but looks taken, and since nobody holds it nobody will ever write 0. Mutual exclusion still holds; the lock is simply lost. The same happens to any lock whose waiter writes the lock variable without an atomic test.

Atomic instructions and semaphores. A binary semaphore's P can be written as a spin on fetch-and-set (do fetch_and_set(x, y) while (y)) and V as x = 0: this implements mutual exclusion. Replacing the atomic instruction by an ordinary load and store (while (x) ; x = 1) is wrong, for the same reason that test-then-set fails in the earlier page. On a uniprocessor a busy-waiting P can also be useless: if context switching is disabled while it spins, the thread that would run V is never scheduled.

Busy waiting and blocking. A spinning thread burns CPU. Spinlocks pay off when the critical section is shorter than a context switch and each thread has its own processor; otherwise the thread should block (a semaphore queue), as the kernel does. Real hardware: a spinner that repeats the atomic instruction floods the memory bus with writes; implementations first spin on an ordinary read of the lock and execute the atomic instruction only when it looks free ("test and test-and-set").

How it works

The animations are real schedules found by exploring every interleaving of three looping threads. Test-and-set first: T3 is ready to try, but the shortest schedule that overtakes it three times lets T1 and T2 win the race over and over. The search shows this can go on for ever.

▶remainder section
while (test_and_set(&lock)) ;
critical section
lock = 0

▶remainder section
while (test_and_set(&lock)) ;
critical section
lock = 0

▶remainder section
while (test_and_set(&lock)) ;
critical section
lock = 0

The bounded-waiting version: this is the shortest schedule in which a thread enters through the hand-over (its key is still true when it enters, it did not win a test_and_set).

▶remainder section
waiting[0] = true; key = true
while (waiting[0] && key)
    key = test_and_set(&lock);
waiting[0] = false
critical section
j = (0 + 1) % 3
while (j != 0 && !waiting[j])
    j = (j + 1) % 3;
if (j == 0) lock = 0; else waiting[j] = false;

▶remainder section
waiting[1] = true; key = true
while (waiting[1] && key)
    key = test_and_set(&lock);
waiting[1] = false
critical section
j = (1 + 1) % 3
while (j != 1 && !waiting[j])
    j = (j + 1) % 3;
if (j == 1) lock = 0; else waiting[j] = false;

▶remainder section
waiting[2] = true; key = true
while (waiting[2] && key)
    key = test_and_set(&lock);
waiting[2] = false
critical section
j = (2 + 1) % 3
while (j != 2 && !waiting[j])
    j = (j + 1) % 3;
if (j == 2) lock = 0; else waiting[j] = false;

The ticket lock: whatever the scheduler does between the steps, the threads enter in the order of their tickets.

▶remainder section
my = Fetch_And_Add(&next, 1)
while (now != my) ;
critical section
now = now + 1

▶remainder section
my = Fetch_And_Add(&next, 1)
while (now != my) ;
critical section
now = now + 1

▶remainder section
my = Fetch_And_Add(&next, 1)
while (now != my) ;
critical section
now = now + 1

The tempting fetch-and-add lock: the shortest schedule that ends with nobody inside and $L = 1$. From here no schedule at all ever lets a thread enter.

▶remainder section
while (Fetch_And_Add(L, 1))
    L = 1;
critical section
L = 0

▶remainder section
while (Fetch_And_Add(L, 1))
    L = 1;
critical section
L = 0

▶remainder section
while (Fetch_And_Add(L, 1))
    L = 1;
critical section
L = 0

A semaphore written with an ordinary load and store instead of fetch_and_set: the shortest schedule with two threads inside.

▶remainder section
while (x) ;
x = 1
critical section
x = 0

▶remainder section
while (x) ;
x = 1
critical section
x = 0

▶remainder section
while (x) ;
x = 1
critical section
x = 0

And the properties of six locks, found by the search (not argued):

Worked examples

#include <stdatomic.h>
#include <stdio.h>
 
int main(void) {
    atomic_flag f = ATOMIC_FLAG_INIT;
    int a = atomic_flag_test_and_set(&f);
    int b = atomic_flag_test_and_set(&f);
    atomic_flag_clear(&f);
    int c = atomic_flag_test_and_set(&f);
    printf("test_and_set: returns %d, then %d, after clear %d\n", a, b, c);
 
    atomic_int x = 5;
    int old = atomic_exchange(&x, 9);
    printf("swap: returns the old value %d, x is now %d\n", old, atomic_load(&x));
 
    int expected = 9;
    int ok1 = atomic_compare_exchange_strong(&x, &expected, 12);
    printf("compare_and_swap(x, 9, 12): success %d, x is now %d\n", ok1, atomic_load(&x));
    expected = 9;
    int ok2 = atomic_compare_exchange_strong(&x, &expected, 20);
    printf("compare_and_swap(x, 9, 20): success %d, x stays %d (it found %d)\n", ok2, atomic_load(&x), expected);
 
    int before = atomic_fetch_add(&x, 3);
    printf("fetch_and_add(x, 3): returns %d, x is now %d\n", before, atomic_load(&x));
    return 0;
}

test_and_set: returns 0, then 1, after clear 0
swap: returns the old value 5, x is now 9
compare_and_swap(x, 9, 12): success 1, x is now 12
compare_and_swap(x, 9, 20): success 0, x stays 12 (it found 12)
fetch_and_add(x, 3): returns 12, x is now 15

#include <pthread.h>
#include <sched.h>
#include <stdatomic.h>
#include <stdio.h>
 
#define THREADS 3
#define ROUNDS 20000
 
static atomic_flag spin = ATOMIC_FLAG_INIT;
static atomic_int next_ticket, now_serving;
static atomic_int atomic_counter;
static int plain_a, plain_b;
 
static void *with_spinlock(void *arg) {
    (void)arg;
    for (int i = 0; i < ROUNDS; i++) {
        while (atomic_flag_test_and_set(&spin)) sched_yield();   /* sched_yield only keeps a busy machine responsive */
        plain_a++;                                                /* critical section on a PLAIN variable */
        atomic_flag_clear(&spin);
    }
    return NULL;
}
 
static void *with_ticket(void *arg) {
    (void)arg;
    for (int i = 0; i < ROUNDS; i++) {
        int my = atomic_fetch_add(&next_ticket, 1);
        while (atomic_load(&now_serving) != my) sched_yield();
        plain_b++;
        atomic_fetch_add(&now_serving, 1);
    }
    return NULL;
}
 
static void *with_fetch_add(void *arg) {
    (void)arg;
    for (int i = 0; i < ROUNDS; i++) atomic_fetch_add(&atomic_counter, 1);
    return NULL;
}
 
static void run(void *(*fn)(void *)) {
    pthread_t t[THREADS];
    for (int i = 0; i < THREADS; i++) pthread_create(&t[i], NULL, fn, NULL);
    for (int i = 0; i < THREADS; i++) pthread_join(t[i], NULL);
}
 
int main(void) {
    run(with_spinlock);
    run(with_ticket);
    run(with_fetch_add);
    printf("expected %d\n", THREADS * ROUNDS);
    printf("test-and-set spinlock around a plain counter: %d\n", plain_a);
    printf("ticket lock around a plain counter: %d\n", plain_b);
    printf("atomic fetch-and-add on its own: %d\n", atomic_load(&atomic_counter));
    return 0;
}

expected 60000
test-and-set spinlock around a plain counter: 60000
ticket lock around a plain counter: 60000
atomic fetch-and-add on its own: 60000

Cheat box

Traps and GATE patterns

Connections

These instructions are what the semaphore implementation uses inside the kernel to protect its own queue; the software solutions show what can be done with plain reads and writes, and why it is not enough. The classic problems are solved with semaphores built on these locks. Interrupt disabling, the other tool of the kernel, is the subject of interrupts.

PYQs

Fetch_And_Add (X, i) is an atomic Read-Modify-
Write instruction that reads the value of memory
location X, increments it by the value i, and returns
the old value of X. It is used in the pseudocode
shown below to implement a busy-wait lock. L is
an unsigned integer shared variable initialized to 0.
The value of 0 corresponds to lock being available,
while any non-zero value corresponds to the lock
being not available.

AcquireLock(L) {

while (Fetch_And_Add(L,1))

  L = 1;

}

ReleaseLock(L) {

L = 0;

}

This implementation........

The enter_CS() and leave_CS() functions to
implement critical section of a process are realized
using test-and-set instruction as follows:

void enter_CS(X)
{
    while test-and-set(X) ;
}

void leave_CS(X)
{

OPERATING SYSTEMS
    X = 0;
}

In the above solution, X is a memory location
associated with the CS and is initialized to 0. Now
consider the following statements:

I. The above solution to the CS problem is
deadlock-free.
II.
The
solution
is
starvation
free.
III. The processes enter CS in FIFO order.
IV. More than one process can enter CS at the same
time.

Which of the above statements is TRUE?

The
atomic
fetch-and-set
x,
y
instruction
unconditionally sets the memory location x to 1 and
fetches the old value of x in y without allowing any
intervening access to the memory location x.
Consider the following implementation of P and V
functions on a binary semaphore S.

void P (binary_semaphore *s) {

unsigned y;

OPERATING SYSTEMS

unsigned *x = &(s->value);

do {

fetch-and-set x, y;

}  while (y);

}

void V (binary_semaphore *s) {

S->value = 0;

}

Which one of the following is true?

Self-check

Revision card

References