Peterson’s Algorithm

Two‐thread mutual exclusion using two flags and a “turn”:

// Shared globals
int flag[2] = {0, 0};
int turn;

// Thread i = 0 or 1; j = 1 - i
void* thread_function(void* arg) {
    int i = *(int*)arg;
    int j = 1 - i;

    while (1) {
        // Entry section
        flag[i] = 1;
        turn = j;
        while (flag[j] && turn == j) {
            // busy-wait
        }

        // Critical section
        printf("Thread %d is in the critical section.\\n", i);
        // ... perform operations that require mutual exclusion ...

        // Exit section
        flag[i] = 0;

        // Remainder section
        printf("Thread %d is in the remainder section.\\n", i);
        // ... perform non-critical operations ...
    }

    return NULL;
}

• Mutual exclusion: only one thread can enter CS at a time.
• Progress & bounded waiting: each thread enters CS after at most one turn by the other.

Test-and-Set

Atomic primitive; builds simple spinlocks:

// atomic test-and-set with acquire semantics
bool test_and_set(bool *lock) {
  bool old = *lock;
  *lock = true;
  return old;
}

void spin_lock(bool *lock) {
  while (test_and_set(lock)) /* busy‐wait */;
}
// atomic clear with release semantics
void spin_unlock(bool *lock) {
  *lock = false;
}

// Assuming `lock` is declared and initialized to false
do {
    // Acquire the spinlock
    spin_lock(&lock);

    /* ===== CRITICAL SECTION START ===== */
    // Place your critical operations here
    // e.g., counter++; printf("In CS: %d\\n", counter);
    /* ===== CRITICAL SECTION END ===== */

    // Release the spinlock
    spin_unlock(&lock);

    /* ===== REMAINDER SECTION ===== */
    // Perform non-critical work or sleep here
    // e.g., usleep(100000);
} while (1);

• Pros: easy to implement in hardware.
• Cons: unfair, high bus traffic under contention.

Test-and-Test-and-Set (TTAS)

do {
    // Phase 1: plain‐read spin until the lock looks free
    while (lock) {
        /* spin on the cached value, no atomic ops */
    }
    // Phase 2: once it seems free, invoke your existing spin_lock()
    spin_lock(&lock);

    /* ===== CRITICAL SECTION START ===== */
    // Place your critical operations here
    // e.g., counter++; printf("In CS: %d\\n", counter);
    /* ===== CRITICAL SECTION END ===== */

    // Release with your existing spin_unlock()
    spin_unlock(&lock);

    /* ===== REMAINDER SECTION ===== */
    // Perform non-critical work or sleep here
    // e.g., usleep(100000);
} while (1);

Bounded‐waiting with test_and_set

do {
    waiting[i] = true;
    key = true;
    while (waiting[i] && key)
        key = test_and_set(&lock);    // solution using spinlock
    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;
    /* remainder section */
} while (true);

Extended Peterson’s with Bounded Waiting

Generalizes to N threads with levels 1…N–1 and victim array:

// Shared: level[N], victim[N];
void lock(int i) {
  for (int k = 1; k < N; k++) {
    level[i] = k;
    victim[k] = i;
    // wait until no threads at >= level k or it's our turn
    while (exists j != i with level[j] >= k && victim[k] == i)
      /* busy‐wait */;
  }
}
void unlock(int i) {
  level[i] = 0;
}

• Guarantees mutual exclusion, progress, and bounded waiting.

Pthreads mutexes