[FCDS] Mutex and Lock basics

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


  • 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.


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


  • 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


  • 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


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;
            temp = value;
            value = value + 1;
        return temp;

Crital section access Using locks

private Lock lock;
    <Non-critical section>
    <critical section>


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.

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

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

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
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++){

    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


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.


  • 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