[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;

Apr 29, 2021


[+] click to leave a comment [+]
the comment system on this blog works via email. The button
below will generate a mailto: link based on this page's url 
and invoke your email client - please edit the comment there!

[optional] even better, encrypt the email with my public key

- don't modify the subject field
- specify a nickname, otherwise your comment will be shown as   
  anonymous
- your email address will not be disclosed
- you agree that the comment is to be made public.
- to take down a comment, send the request via email.

>> SEND COMMENT <<




Fun with Image Maps and SVGs via benji February 20, 2024

Over the past few weeks I've been playing around with making some images on my website interactive. My "informatics" class in high school taught us some basic HTML. By basic I mean in notepad and writing everything by hand, saving to a...

Goblin Week 2024 via Helvetica Blanc January 26, 2024

It snuck up on me, but I managed to draw my little goblins to celebrate the week! I love my children - they're like awful Pikmin. I've uploaded the whole parade as a print, as well as individual prints for each goblin. There's something very fu…

How to trust gpg keys via Travis Shears Personal Site October 27, 2023

After moving some GPG keys to a new computer I kept getting these trust warnings. It is NOT certain that the key belongs to the person named in the user ID.If you * really * know what you are doing, you may answer the next question with yes. Use this key a…

Generated by openring from webring