Prev Next

Synchronization Primitives and Problems

Locks

Locks are a synchronization primitive used to implement critical sections.

Threads acquire a lock when entering a critical section.
Threads release a lock when leaving a critical section.

Spinlocks

What we discussed Friday is known as a spinlock:

lock for the fact that it guards a critical section (we will have more to say about locks next time), and
spin describing the process of acquiring it.

Spinlocks are rarely used on their own to solve synchronization problems.

Spinlocks are commonly used to build more useful synchronization primitives.

More Bank Example

void giveGWATheMoolah(account_t account, int largeAmount) {
  int gwaHas = get_balance(account);
  gwaHas = gwaHas + largeAmount;
  put_balance(account, gwaHas);
  notifyGWAThatHeIsRich(gwaHas);
  return;
}

lock gwaWalletLock; // Need to initialize somewhere

void giveGWATheMoolah(account_t account, int largeAmount) {
+ lock_acquire(&gwaWalletLock);
  int gwaHas = get_balance(account);
  gwaHas = gwaHas + largeAmount;
  put_balance(account, gwaHas);
+ lock_release(&gwaWalletLock);
  notifyGWAThatHeIsRich(gwaHas);
  return;
}

What happens if we call lock_acquire() while another thread is in the critical section?

The thread acquiring the lock must wait until the thread holding the lock calls lock_release().

How To Wait

How do we wait?

Active (or busy) waiting: repeat some action until the lock is released.
Passive waiting: tell the kernel what we are waiting for, go to sleep, and rely on lock_release to awaken us.

Spinning v. Sleeping

There are cases where spinning is the right thing to do. When?

Only on multicore systems. Why?
- On single core systems nothing can change unless we allow another thread to run!
If the critical section is short.
- Balance the length of the critical section against the overhead of a context switch.

When to Spin

If the critical section is short:

When to Sleep

If the critical section is long:

How to Sleep

The kernel provides functionality allowing kernel threads to sleep and wake on a key:

thread_sleep(key): "Hey kernel, I’m going to sleep, but please wake me up when key happens."
thread_wake(key): "Hey kernel, please wake up all (or one of) the threads who were waiting for key."
Similar functionality can be implemented in user space.

Thread Communication

Locks are designed to protect critical sections.
lock_release() can be considered a signal from the thread inside the critical section to other threads indicating that they can proceed.
- In order to receive this signal a thread must be sleeping.
What about other kinds of signals that I might want to deliver?
- The buffer has data in it.
- Your child has exited.

Condition Variables

A condition variable is a signaling mechanism allowing threads to:
- cv_wait until a condition is true, and
- cv_notify other threads when the condition becomes true.
The condition is usually represented as some change to shared state.
- The buffer has data in it: bufsize > 0.
- cv_wait: notify me when the buffer has data in it.
- cv_signal: I just put data in the buffer, so notify the threads that are waiting for the buffer to have data.

Condition variable can convey more information than locks about some change to the state of the world.
As an example, a buffer can be full, empty, or neither.
- If the buffer is full, we can let threads withdraw but not add items.
- If the buffer is empty, we can let threads add but not withdraw items.
- If the buffer is neither full nor empty, we can let threads add and withdraw items.
We have three different buffer states (full, empty, or neither) and two different threads (producer, consumer).

Why are condition variables a synchronization mechanism?

Want to ensure that the condition does not change between checking it and deciding to wait!

Thread A Thread B

Thread A	Thread B
`if (buffer_is_empty):`
	`put(buffer) notify(buffer)`
`sleep...`
`...forever`

if (buffer_is_empty):

put(buffer)
notify(buffer)

sleep...

...forever

Locking Multiple Resources

Locks protect access to shared resources.
Threads may need multiple shared resources to perform some operation.

Consider two threads A and B that both need simultaneous access to resources 1 and 2:

Thread A runs, grabs the lock for Resource 1.
→ CONTEXT SWITCH ←
Thread B runs, grabs the lock for Resource 2.
→ CONTEXT SWITCH ←
Thread A runs, tries to acquire the lock for Resource 2.
→ THREAD A SLEEPS ←
Thread B runs, tries to acquire the lock for Resource 1.
→ THREAD B SLEEPS ←

Now what?

Deadlock

Deadlock occurs when a thread or set of threads are waiting for each other to finish and thus nobody ever does.

Self Deadlock

A single thread can deadlock. How?

Thread A acquires Resource 1. Thread A tries to reacquire Resource 1.

This seems inane. Why would this happen?

foo() needs Resource 1. bar() needs Resource 1. While locking Resource 1 foo() calls bar().

Can we solve this problem?

Yes! Recursive locks. Allow a thread to reacquire a lock that it already holds, as long as calls to acquire are matched by calls to release.
This kind of problem is not uncommon. You may want to implement recursive locks for OS/161.
(But don’t make the locks we gave you suddenly recursive…)

Conditions for Deadlock

A deadlock cannot occur unless all of the following conditions are met:

Protected access to shared resources, which implies waiting.
No resource preemption, meaning that the system cannot forcibly take a resource from a thread holding it.
Multiple independent requests, meaning a thread can hold some resources while requesting others.
Circular dependency graph, meaning that Thread A is waiting for Thread B which is waiting for Thread C which is waiting for Thread D which is waiting for Thread A.

Dining Philosophers

"Classic" synchronization problem which I feel obligated to discuss.
Illustrated below.

Feeding Philosophers

Breaking deadlock conditions usually requires eliminating one of the requirements for deadlock.

Don’t wait: don’t sleep if you can’t grab the second chopstick and put down the first.
Break cycles: usually by acquiring resources in a well-defined order. Number chopsticks 0–4, always grab the higher-numbered chopstick first.
Break out: detect the deadlock cycle and forcibly take away a resource from a thread to break it. (Requires a new mechanism.)
Don’t make multiple independent requests: grab both chopsticks at once. (Requires a new mechanism.)

Deadlock v. Starvation

Starvation is an equally-problematic condition in which one or more threads do not make progress.

Starvation differs from deadlock in that some threads make progress and it is, in fact, those threads that are preventing the "starving" threads from proceeding.

Deadlock v. Race Conditions

What is better: a deadlock (perhaps from overly careful synchronization) or a race condition (perhaps from a lack of correct synchronization)?

I’ll take the deadlock. It’s much easier to detect!