CS 350 Concurrency APIs

Spinlock

A lock that causes a thread to loop (or spin) when trying to acquire it when locked

Spinlock benefits

• Sufficient for short critical sections (ie. within other locks)

• Lightweight

Spinlock drawbacks

• Requires a lot of CPU to spin

• No FIFO (some thread may lose every time)

• No bounded-waiting

Wait channel

Manages a list of sleeping threads, abstracting the details of the thread scheduler

Semaphore

Initialized with $N$ available permits

Binary semaphore

A semaphore initialized with $N=1$ available permits, with a paired wait/post

Mutex

A blocking lock for mutual exclusion similar to a semaphore, but with no counter

Condition variables

A mutual-exclusion pattern to wait for changes in a shared state

cond_wait(c, m)

1. m is atomically unlocked

2. Wait

3. Re-acquire m and resume executing automatically

cond_signal(c)

Wait up a single thread waiting on a condition

cond_broadcast(c)

Wake up all threads waiting on a condition

Steps of cond_signal(c)

1. Call WaitChannel_Wake(c->chan)

Steps of cond_broadcast(c)

1. Call WaitChanne_WakeAll(c->chan)

Steps of cond_wait(c, m)

1. Lock the wait channel with WaitChannel_Lock(c->chan)

2. Unlock m with Mutex_Unlock(m)

3. Call WaitChannel_Wait(c->chan)

4. Re-aquire m with Mutex_Lock(m)

acquire()

Atomically check if the lock is already acquired, and acquire it if not

release()

Atomically release the lock and set it as unlocked

WaitChannel_Lock(wc)

Protect the queue registration and disallow new threads from being queued on the wait channel

WaitChannel_Sleep(wc)

• Queues the caller, releases the lock, and puts the calling thead to sleep

• Caller must hold the channel lock

• Caller does not re-acquire the lock

WaitChannel_Wake(wc)

Wake up a sleeping thread on the wait channel, and acquires the channel lock automatically

WaitChannel_WakeAll(wc)

Wakes up all threads sleeping on the wait channel, and acquires the channel lock automatically

wait(sem) (P)

Consume the available permit, and block if none are available

post(sem) (V)

Add a new available permit, allow a waiter to proceed

Steps of Semaphore_Wait(s)

1. Lock the internal spinlock Spinlock_Lock(s->lock)

2. While there are no permits available (count = 0):

   • Lock the wait channel WaitChannel_Lock(s->wc)

   • Unlock the internal spinlock Spinlock_Unlock(s->lock)

   • Sleep on the wait channel WaitChannel_Sleep(s->wc)

   • Lock the internal spinlock Spinlock_Lock(s->lock)

3. Decrement the permit count

4. Unlock the internal spinlock Spinlock_Unlock(s->lock)

Steps of Semaphore_Post(s)

1. Lock the internal spinlock Spinlock_Lock(s->lock)

2. Increment the permit count

3. Wake a sleeping thread on the wait channel WaitChannel_Wake(s->wc)

4. Unlock the internal spinlock Spinlock_Unlock(s->lock)

Steps of Mutex_Lock(m)

1. Lock the internal spinlock Spinlock_Lock(m->lock)

2. While the mutex is currently locked:

   • Lock the wait channel WaitChannel_Lock(m->wc)

   • Unlock the internal spinlock Spinlock_Unlock(m->lock)

   • Sleep on the wait channel WaitChannel_Sleep(m->wc)

   • Lock the internal spinlock Spinlock_Lock(m->lock)

3. Set the status of the mutex as locked

4. Set the owner of the mutex as the current thread

5. Unlock the internal spinlock Spinlock_Unlock(m->lock)

Steps of Mutex_TryLock(m)

1. Lock the internal spinlock Spinlock_Lock(m->lock)

2. If the mutex is currently locked:

   • Return EBUSY

3. Set the status of the mutex as locked

4. Set the owner of the mutex as the current thread

5. Unlock the internal spinlock Spinlock_Unlock(m->lock)

Steps of Mutex_Unlock(m)

1. Lock the internal spinlock Spinlock_Lock(m->lock)

2. Assert the current thread owns the mutex

3. Assert the mutex is currently locked

4. Set the owner of the mutex to NULL

5. Set the status of the mutex to unlocked

6. Wake a sleeping thread on the wait channel WaitChannel_Wake(m->wc)

7. Unlock the internal spinlock Spinlock_Unlock(m->lock)