[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
• Lock Implementations: n-threads
  • 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)
• Example Thread events:
  • Assign to shared/local variable
  • Invoke method
  • return from method
  • …

Thread can be defined as:

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

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:

1
2
3
4

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

counter with lock:

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

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.
• Deadlock-Free
  • 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.
  • Individual threads make progress.

Deadlock-free IS NOT Lockout Free.

• 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

Lock Implementations - 2 Threads

Assumption of Thread id

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

    }
}

Implementation #1

class LockOne implements Lock{
    private volatile boolean[] flag = new boolean[2];
    // 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

        }
    }

    public void unlock(){}
}

• Satisfies mutual exclusion
• Not deadlock free (wait until the other thread calls lock)

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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[0] == true; Not(flag[1] and victim == 0)
If thread 1 in critical section: flag[1] == true; Not(flag[0] and victim == 1)

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

Deadlock Free? yes.

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.

Lock Implementation: n-threads

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

    LEVEL   |threads at most|
    ------------------------------
    L=0     n              NON CS
    L=1     n-1 
    ...     ... 
    L=n-2   2  
    L=n-1   1              CS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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(){
        int me = ThreadID.get();
        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(){
        int me = ThreadID.get();
        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)

• is deadlock free
• 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(){
        int i = ThreadID.get();
        flag[i] = true;
        label[i] = max(label[0],....,label[n-1]) +1;

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

    }

    public void unlock(){
        flag[ThreadID.get()] = false;
    }
}

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
• Multi-Reader-Multi-Writer (victim)
• 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

proof of IS by contradiction:
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
10-processor, one thread per processor

REFS;

• https://eli.thegreenplace.net/2018/partial-and-total-orders/
• the art of multiprocessor programming