Art of MP Ch 2 - Mutual Exclusion

Some meanings

• A thread is attempting to acquire or release the lock: It invoked lock() or unlock() and has not returned
• Events happen instantaneously in time, $a_0\to a_1$ means that $a_0$ happens before $a_1$
  • This relation on events is a total order
• An interval $(a_0,a_1)$ is the duration between $a_0$ and $a_1$
  • Intervals can also precede each other. That relation is a partial order.

Properties of a good Lock algorithm

This assumes that every thread that acquires the lock eventually releases it.

• Mutual Exclusion: At most one thread holds the lock at a time
• Freedom from deadlock: If a thread is attempting to acquire or release the lock, then eventually some thread acquires or releases the lock.
  • If a thread calls lock() and never returns, then other threads must complete an infinite number of critical sections
  • Note this doesn’t say that the thread will get the lock, it just says that some thread gets the lock (might be our original thread or some other thread)
  • Deadlock happens when all threads are trying to acquire locks but are not able to proceed. This property says that some thread will actually acquire the lock
• Freedom from starvation: Every thread that attempts to acquire or release the lock eventually succeeds

Some properties

• Freedom from starvation ⇒ Freedom from deadlock: Deadlock freedom requires some thread eventually acquire/release the lock, starvation freedom says the original thread will eventually acquire/release the lock
• Mutual exclusion is a safety property, while the other two are liveness properties.

Mutual Exclusion a bit formally

Let $C{S}_A^j$ be the interval during which thread A executes the critical section for the jth time. So, $C{S}_A^j=(a_0,a_1)$ where $a_0$ is the response event for A’s $j$th call to lock() and $a_1$ is the response for A’s $j$th call to unlock(). Then mutual exclusion implies that for two distinct threads A and B: $\forall j,k\in \mathbb{Z},C{S}_A^j\to C{S}_B^k\text{ or }C{S}_B^k\to C{S}_A^j$

Livelock

Some definitions of deadlock are narrower — they say that the system doesn’t deadlock if there is some way for the threads to be scheduled so that the system makes progress. In that narrower definition’s world, livelock is a phenomena where in some scheduling of the threads, the system makes no progress

In the definition of deadlock we have used here, it includes livelock. When we say that “some thread eventually acquires or releases the lock”, it is meant that it happens in all thread schedulings.

Fairness

Fairness means (informally) that a thread which tried to acquire the lock before another thread gets the lock first. To define fairness, we split the lock() method into 2 parts:

• doorway section: Completes in a bounded number of steps
• waiting section

Bounded wait-free: A section of code that is guaranteed to complete in a bounded number of steps. E.g. code with no loops

First Come First Served Lock

A lock is FCFS if it can be split into a bounded wait-free doorway section followed by a waiting section s.t. if a thread A completes its doorway before thread B begins its doorway, then A will acquire the lock first. $D_A^i\to D_B^j⟹C{S}_A^i\to C{S}_B^j$ Here $D_A$ is the interval in which thread A executes its doorway section for the $i$th time

NOTE

Deadlock-free & FCFS algorithm implies starvation-freedom

Lamport’s Bakery Algorithm

Two arrays are stored here:

1. label[numThreads] : Each thread stores a number in its own slot
2. flag[numThreads]: Each thread sets flag[threadIdx] = true when it wants to acquire the lock

The main idea here is that each thread gets a label assigned to it during the doorway section and then the threads proceed to the critical section in order of their labels

Whenever a thread enters the lock() method:

• Sets label[threadIdx] = max(label) + 1
  • Multiple threads executing this concurrently may get the same label, so we order the labels by doing lexicographic ordering on (threadIdx, label[threadIdx])
• Waits for label[threadIdx] to become the smallest label amongst the threads that have set their flags

In the unlock() method, the flag is set to false. This allows threads with larger labels to proceed to the critical section.

This lock is deadlock-free and FCFS. By virtue of these, it is also starvation-free.

Bounded timestamps

The labels in the above algorithm can be thought of as timestamps. These timestamps grow unboundedly, and eventually will roll over to zero. This is not a problem for most programs and it’s also basically impossible for a 64-bit counter to overflow.

Sequential bounded timestamping system