Goals

• Mutual exclusion (e.g., A and B don’t run at the same time) — process mutual exclusion
  • solved with locks
• Ordering (e.g., B runs after A does something) — process synchronization
  • solved with condition variables OR semaphores

CS 537 Videos 小林coding

Locks

You can think of a lock as a mutex. It’s just a variable with two states: available/acquired. Each thread can acquire and release it. Reference: OSTEP-Locks

Principles for lock design

1. Mutual exclusion: Only one thread (at most) in the critical section at a time
2. Progress (deadlock-free): If several simultaneous requests, must allow one to proceed
3. Bounded (starvation-free): Must eventually allow each waiting thread to enter
4. Fairness: Each thread waits for (roughly) the same amount of time
5. Performance: CPU is not used unnecessarily (e.g., spinning)

Failed Attempt 1: Turn off interrupts

This is a hardware approach. In the critical section, disable interrupts to prevent the dispatcher from context switching. Drawbacks: Not suitable for multiprocessors; not applicable to user processes — only kernel mode, because user space cannot directly disable/enable interrupts.

Failed Attempt 2: Test And Set

Use a flag as the lock. The root cause of the problem: the test and set are separate, non-atomic operations.

Feasible but outdated: Peterson’s Algorithm

Before entering the critical section, both parties indicate intent and can show courtesy by setting turn to the other’s id. The last thread to express courtesy succeeds in yielding. Compared to this software-only approach, there are better hardware-supported ways to implement locks, so it’s considered outdated.

Hardware approach: test-and-set

1
2
3

void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1) ; // spin-wait (do nothing)
}

TestAndSet atomically does two things: returns the old value 0 of lock->flag (test discovers the lock is available) and sets its new value to 1 to indicate the lock is acquired.

Hardware approach: Compare-And-Swap

1
2
3
4

void acquire(lock_t *lock) { 
	while(CompareAndSwap(&lock->flag, 0, 1) == 1) ; 
	// spin-wait (do nothing) 
} 

If the old lock-flag value equals the expected 0, set it to 1; in all cases, return the old value.

Spinning burns CPU? Use yield()

1
2
3
4
5

void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1){
        yield();
    }
}

If lock acquisition fails, don’t keep spinning; call the OS system call yield() to relinquish the CPU and let the OS context switch to another runnable thread. But you must weigh the cost of spinning vs. context switching. Also, with many contending threads, a thread may repeatedly fail to acquire the lock and keep yielding, leading to starvation (similarly for pure spinning).

from spin to sleep

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void lock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ; // acquire guard lock by spinning
    if (m->flag == 0) {
        m->flag = 1; // lock is acquired
        m->guard = 0;
    } else {
        queue_add(m->q, gettid());
        m->guard = 0;
        park();
    }
}

void unlock(lock_t *m) { 
    while (TestAndSet(&m->guard, 1) == 1)
        ; // acquire guard lock by spinning
    if (queue_empty(m->q))
        m->flag = 0; // let go of lock; no one wants it
    else
        unpark(queue_remove(m->q)); // hold lock (for next thread!)
        // m->flag = 0; WE CAN'T DO THIS!!!
    m->guard = 0;
}

There are two locks: guard and flag. The guard protects flag operations via a short spin, ensuring mutual exclusion over flag updates. The guard won’t spin long because as soon as the flag operation finishes, guard is reset to 0.

Solaris provides two atomic functions: park() and unpark(threadId). If a thread fails to acquire the flag, it enqueues itself and blocks. When another thread finishes the critical section and unlocks, it wakes one waiting thread directly; the flag remains 1 to indicate the newly awakened thread is holding/continuing with the lock.

Why not set flag to 0 when A wakes B? If set to 0, the lock would appear free, but B doesn’t hold guard (A still does), so B can’t safely set flag back to 1 to acquire it.

Pitfall: A fails to get the lock; right after releasing guard but before calling park(), the OS context switches to B which calls unlock(). B tries to unpark A, but since A hasn’t parked yet, unpark has no effect. A later calls park() and will sleep forever.

Fix: setpark()

1
2
3
4

queue_add(m->q, gettid());
setpark();
m->guard = 0;
park();

setpark() ensures that if a context switch happens before park(), then the subsequent call to park() will immediately return instead of blocking.

Condition Variables

Basic

Condition variables solve ordering problems, i.e., process/thread synchronization. A condition variable is a queue of waiting threads.

pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);

1. Atomically block the thread and release the lock
2. The thread must hold the lock before calling wait()
3. When returning from wait(), the thread re-acquires the lock before proceeding

pthread_cond_signal(pthread_cond_t *c);

1. Wake one thread from the queue
2. If no threads are waiting, return immediately

Condition variables are used with a state variable to encode program state.

1
2
3
4
5
6
7

// parent code
void thread_join() {
    Mutex_lock(&m);       // w
    if (done == 0)        // x
        Cond_wait(&c, &m);// y
    Mutex_unlock(&m);     // z
}

1
2
3
4
5
6
7

// child code
void thread_exit() {
    Mutex_lock(&m);   // a
    done = 1;         // b
    Cond_signal(&c);  // c
    Mutex_unlock(&m); // d
}

The lock protects the state variable.

The Producer/Consumer (Bounded Buffer) Problem

There is a shared buffer; producers put data in, consumers take data out.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void *producer(void *arg) { 
    for (int i = 0; i < loops; i++) { 
        Mutex_lock(&m); // p1 
        while (numfull == max) // p2 
            Cond_wait(&empty, &m); // p3 
        do_fill(i);  // p4
        Cond_signal(&fill); // wake one consumer, not sure which
        Mutex_unlock(&m); // p6
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void *consumer(void *arg) { 
    while (1) { 
        Mutex_lock(&m); 
        while (numfull == 0)
            Cond_wait(&fill, &m); // may not immediately reacquire the lock on wakeup
        int tmp = do_get();
        Cond_signal(&empty);
        Mutex_unlock(&m); 
    }
} 

Two CVs are used: fill and empty, plus while-loops for rechecking state.

Why while? On wakeup from wait(), the state variable must be rechecked. If we used if instead, consider: a producer signals a consumer A, but A can’t acquire the lock immediately; another consumer B acquires it first and sets numfull to 0. When A later acquires the lock and proceeds without rechecking, it reads invalid state and calls do_get() erroneously.

Rules of thumb for CVs

1. Keep state variables in addition to CVs
2. Always call wait/signal with the lock held
3. Whenever a thread wakes from waiting, recheck the state

Semaphores

Semaphores can serve as Lock + CV. The core operations are P() and V(), i.e., decrement and increment.

Sem_wait(): Wait until value > 0, then decrement Sem_post(): Increment value, then wake a single waiter

Binary Semaphores (Locks)

We can use a semaphore to implement mutual exclusion.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

typedef struct __lock_t { 
    sem_t sem; // binary semaphore
} lock_t;

void init(lock_t *lock) {
    sem_init(&lock->sem, 1);
}
void acquire(lock_t *lock) {
    sem_wait(&lock->sem); // P: on success sets semaphore from 1 to 0
} 
void release(lock_t *lock) {
    sem_post(&lock->sem); 
}

Initialize the semaphore to 1 to allow one thread to hold the lock. Thread A calls wait(), semaphore becomes 0 and A enters the critical section; if thread B calls wait(), it decrements to -1 and sleeps. When A finishes and posts, the semaphore goes to 0 and wakes B; after B finishes and posts, the semaphore returns to 1.

Mutual exclusion pattern: P — critical section — V

Process synchronization with semaphore

Initialize semaphore to 0. Desired order: Code A — V — P — Code B. The semaphore’s value represents resource count. Initially 0, Code A must “produce” the resource (V makes it 1) to allow P and thus Code B to proceed. If P runs first, it decrements to -1 and sleeps.

Producer/Consumer

This problem involves both mutual exclusion and synchronization.

Notes

Difference vs. ordinary locks: semaphores bundle hardware support and queues, making wait/post atomic so we don’t worry about their safety. Difference vs. CVs: semaphores keep state; with CVs you must recheck state after wakeup.