[FCDS] Mutex and Lock basics

NOTES ON [FCDS] : mutex.
Keywords: Mutual Exclusion, Locks, Peterson’s Algo. Filter Algo. Bakery Algo.

takeaways:

• Concepts & Terminology
• Mutual Exclusion
• Atomic
• Time, Event, Intervals and threads(considered as events)
• Partial and total ordering
• Lock basics
• Interface and basic usage.
• Properties: Mutual Exclusion, Deadlock-free, Lockout Free , fairness(FIFO)
• Doorway and waiting sections
• Lock Implementations for 2 thread
• Peterson’s Algorithm
• Filter Algo.
• Bakery Algo. (cool but not practical)

Theorem: at least n MRSW registers are needed to solve deadlock-free mutual exclusion. today we solve FIFO n thread mutual exclusion using 2n RW-registers.

CONCEPTS & TERMINOLOGY

Mutual Exclusion ensures security(correctness) but not good for speedup. (it goes Sequential).

Atomic operations e.g. implementing a shared counter

long getAndIncrement(){
long temp = value;
value = temp + 1;
return temp;
}

solutions to Make it atomic:

• Use “increment” functionality provided by cpu (Atomic Integer). Nice speedup.
• Use a lock(synchronized): is usually slower but sometimes we have no choice.

An event a0 of thread A is

• Instantaneous: not a interval but a time point.
• No simultaneous events (events wont happen at exactly the same time point)
• Assign to shared/local variable
• Invoke method
• return from method

• A sequence of events.
• “Trace” model
• Notation: a0->a1 indicates order

States

• Thread state: Program Counter; Local Variables
• System State: Object fields (shared variables); Union of thread states

Events of two or more threads - Interleaved - Not necessarily independent

Intervals:

• time between 2 events
• Intervals may overlap

Intervals may be disjoint:

• Precedence: Interval A0 precedes interval B0;
• (end event of A0 precedes starting event of B0)
• (Intervals don’t overlap)
• Notation: happen before/precedes A0->B0

Partial Ordering (For Intervals):

• Irreflexive A->A is never true
• Antisymmetric if A->B then B->A is not true
• Transitive A->B And B->C then A->C;
• A->B and B->A can both be false(e.g. overlap)

Total Ordering (For Events):

• Irreflexive
• Antisymmetric
• Transitive
• for every distinct A,B , Either A->B or B->A

Lock

e.g. to Implement a counter (atomic read & increment), we build a lock mechanism.

long temp = value;
value = temp +1;

For a lock, the interface is like:

public interface Lock{
public void lock();  // Acquire lock
public void unlock();// release lock
}

counter with lock:

public class Counter {
private long value;
private Lock lock;
public long getAndIncrement(){
int temp;
lock.lock();
try{
temp = value;
value = value + 1;
}finally{
lock.unlock();
}
return temp;
}
}

Crital section access Using locks

private Lock lock;
...
while(true){
<Non-critical section>
lock.lock();
<critical section>
lock.unlock();

}

Good practice to put critical section in a try-block. (lock always gets released).

Properties of Lock:

• Mutual Exclusion: two threads won’t be in CS at the same time.
• If some thread calls lock() and never returns, then (it means) other threads must complete lock() and unlock() calls infinitely often.
• System as a whole makes progress,even if individuals starve.
• Lockout Free (Starvation-Free)
• If some thread calls lock(), it will eventually return.

• Deadlock-free: if you are blocked and can’t acquire the lock,it means at least someone else is making progress.
• Lockout free : if you want a lock, you will eventually get it.

Doorway and Waiting Sections:
In the case of filter algo. the doorway section is setting the level[A] and victim[j]. And the waiting section is the loop.

“Fairness”:
A lock is first-come-fist-served if, whenever, thread A finishes its doorway before thread B starts its doorway, then A cannot be overtaken by B

class ... implements Lock{
...
public void lock(){
// Thread ID is 1 or 0.
int j = 1-i;            // The other thread

}
}

Implementation #1

class LockOne implements Lock{
private volatile boolean[] flag = new boolean;
// volatile means shared by threads

public void lock(){
flag[i] = true;
while (flag[j]){}
}
public void unlock(){
flag[i] = false;
}
}
• This is a wrong Implementation (deadlock)
• LockOne satisfies Mutual Exclusion.

Show that mutual exclusion is satisfied:
Assume CSA overlaps CSB (Critical Section access from thread A and B)..

From the Assumption: for thread A, to enter CS, A must read flag[B] false before B write to it.

• readA(flag[B]==false) -> writeB(flag[B] = true)
• readB(flag[B]==false) -> writeA(flag[A] = true)

From the code :

• writeA(flag[A]=true) -> readA(flag[B]==false) -> CSA
• writeB(flag[B]=true) -> readB(flag[A]==false) -> CSB

Combine the relations (transitive), there is a loop. Contradiction! A event precedes itself, violates total orders!

Implementation #2

public class LockTwo implements Lock{
private volatile int victim;
public void lock(){
victim = i;
while (victim == i){

}
}

public void unlock(){}
}
• Satisfies mutual exclusion

Implementation #3:
Combine the two: Peterson’s Algorithm

public void lock(){
flag[i] = true
victim  = i;
while (flag[j] && victim == i){}
// i will wait if the other is interested and I'm the victim
}

public void unlock(){
flag[i] = false;
}

Mutual Exclusion? yes.

If thread 0 in critical section: flag == true; Not(flag and victim == 0)
If thread 1 in critical section: flag == true; Not(flag and victim == 1)

If thread 0/1 both in critical section: flag == true and flag == true;
victim == 0/1 cannot both be true!

If I have to wait (in the while loop), it means the other is interested and I am the victim. Then the other thread must succeed eventually. If the other is not interested then I will succeed anyways.

Thread i blocked only if j repeatly re-enters with flag[j] == true and victim == i; while j re-enters, it sets victim to j so i can enter.

The filter Algorithm for n threads**

• There are n-1 “waiting rooms” called levels
• At each level (we hold back one thread)
• At least one enters level l
• At least one blocked if many try to enter level l
• Only one thread makes it through
------------------------------
L=0     n              NON CS
L=1     n-1
...     ...
L=n-2   2
L=n-1   1              CS
class Filter implements Lock{
volatile int[] level;    // level[i] is the level of thread i
volatile int[] victim;   // victim[L] is the victim thread for level L

public Filter(int n){
// n is the number of threads that may use the lock
// Level 0: not interested && Out of CS
level = new int [n];
victim = new int [n];
for (int i=0;i<n;i++){
level[i]=0;
}
}

public void lock(){
for (int L = 1; L<n;L++){
level[me] = L;
victim[L] = me;

for (int k=0;k<n;k++){
while(  (k!=i) && (level[k] >=i && victim[L] == i) ){}
}
}
}
public void unlock(){
level[i] = 0;
}
}

Clarify: setting level[me] = L doesn’t mean the thread is already in level L;

we say thread A is at level L for L>0, when it last completes the waiting while loop with level[A]>=L threads at level L is also at level L-1

I will wait when: someone else is at the same or higher level and I’m the victim(on this level). victims won’t proceed to next level (unless it’s the only one on top).

I will proceed to next level if : I’m the only one on the highest level. or I’m not victim.

• Mutual exclusion at CS is satisfied : (Lemma) at most 1 thread enter n-1 level (CS), Entering the CS is equivalent to entering level n-1,thus at most 1 threads enters CS.
• Filter Algorithm is Starvation-free : prove by reverse induction.
• First-come-first-served(Fair)

Lamport’s Bakery Algorithm

each thread takes a number in the doorway, and then wait until no thread with an earlier number is trying to enter it.

The bakery alg. (see P.33)

• First come first serve
• satisfies mutual exclusion
class Bakery implements Lock{
boolean[] flag;   // whether it is interested
Label[]   label;  // Label is basically a integer
public Bakery(int n){
flag = new boolean[n];
label = new Label[n];
for(int i=0;i<n;i++){
flag[i] = false; label[i] = 0;
}
}

public void lock(){
flag[i] = true;
label[i] = max(label,....,label[n-1]) +1;

while( (exists k!=i)  (k!=i) && flag[k] && (label[k],k) << (label[i],i)  ){}
// see notes

}

public void unlock(){
}
}

Note1: if two threads A and B enters the doorway concurrently, they may read the same maximal label number and set their label to the same. To compare threads with same label: use the threadID as a secondary compare.

(label[k],k) « (label[i],i) if and only if: label[k] < (label[i]) or label[k] = label[j] and k<j

Note2:

Since releasing a lock does not reset the label[], it is easy to see that each thread’s labels are strictly increasing. Interestingly, in both the doorway and wait- ing sections, threads read the labels asynchronously and in an arbitrary order, so that the set of labels seen prior to picking a new one may have never existed in memory at the same time. Nevertheless, the algorithm works.

Does it work?

Bakery alg. is cool but not practical: have to read n distinct values

shared read/write memory location called registers (not the registers in CPU hw).

• Multi-Reader-Single-Writer (flag[]), Only I can write to my own flag and all others can read
• Not so interesting: SRMW and SRSW

Theorem at least n MRSW registers are needed to solve deadlock-free mutual exclusion.

• today we solve FIFO n thread mutual exclusion using 2n RW-registers.

Questions:

• What if events happen at exactly same CPU circle? are they simultaneous?
• in Bakery Algo. A and B reads the same maximal label. A has lower priority because it has smaller thread ID, how is this fair? (it is fair per defination)
• There is no mechanism to reset the label numbering? (bounded timestamps)

Post Notes:

Proving Filter Algorithm is correct(Mutex)

• Start at level L=0
• Lemma: At most n-L threads enter level L

Now prove the Lemma: At most n-L threads enter level L with induction

• Induction Hypothesis: at most n-j threads at level j.
• Induction Start: for j=0, is trivial
• Induction Step: the induction hypothesis implies at most n-j+1 threads at level j-1. Zu zeigen: at least one thread cannot progress to level j

let A be the LAST thread at level j to write to victim[j]. For any other thread B at level j:

writeB(victim[j]) -> writeA(victim[j])

Inspecting the code: B writes to level[B] before it writes to victim[j] ; A reads level[B] after it writes to victim[j];

writeB(level[B]=j) -> writeB(victim[j]) -> writeA(victim[j])

B is at level j, every time A reads level[B], it reads a value >= j, A can’t have completed the waiting loop. A contradiction

Proving Filter Algorithm is deadlock free see book P51

Parallel Primality Testing

Challenge: Print primes from 1 to 10^10