Mutex

Mutual Exclusion problem: How to keep two or more threads from being in their critical sections at the same time

A Mutex (Mutual Exclusion lock) cclass can be used.

Examples :

  • Mutex0.java : No synchronization. Critical sections are overlapped.
import java.util.Random;
 
// no synchronization at all
class Mutex0 extends Thread
{
    private static final Random rand = new Random();
    private int id;
 
    public Mutex0(int i)
    {
        id = i;
    }
 
    private void busy()
    {
        try
        {
            sleep(rand.nextInt(500));
        } catch (InterruptedException e)
        {
        }
    }
 
    private void non_critical()
    {
        System.out.println("Thread " + id + " is in a NON critical section");
        busy();
    }
 
    private void pre_protocol()
    {
    }
 
    private void critical()
    {
        System.out.println("Thread " +  id + " is entering the critical section");
        busy();
        System.out.println("Thread " + id + " is leaving the critical section");
    }
 
    private void post_protocol()
    {
    }
 
    public void run()
    {
        for(int i = 0; i<2; ++i)
        {
            non_critical();
            pre_protocol();
            critical();
            post_protocol();
        } 
    }
 
    public static void main(String[] args)
    {
        int N = 2; // number of processes
 
        Mutex0[] p = new Mutex0[N];
 
        // Configure and start processes p[0] ... p[N-1]
 
        for (int i = 0; i < N; i++)
        {
            p[i] = new Mutex0(i);
            p[i].start();
        }
    }
}
  • Mutex1.java
import java.util.Random;
 
/*
 * First attempt to solve the mutual exclusion problem 
 * Use of a turn variable
 */
class Mutex1 extends Thread
{
    private static final Random rand = new Random();
    static int turn = 0;
 
    private int id;
 
    static int N;
 
    public Mutex1(int i, int n)
    {
        id = i;
        N = n;
    }
 
    private void busy()
    {
        try
        {
            sleep(rand.nextInt(500));
        } catch (InterruptedException e)
        {
        }
    }
 
    private void non_critical()
    {
        System.out.println("Thread " + id + " is in a NON critical section");
        busy();
    }
 
    private void critical()
    {
 
        System.out
                .println("Thread " + id + " is entering the critical section");
        busy();
        System.out.println("Thread " + id + " is leaving the critical section");
 
    }
 
    private void pre_protocol()
    {
        do
        {
        } while (turn != id); //keep thread busy if until it gets its turn
    }
 
    private void post_protocol()
    {
        turn = random(N);
        System.out.println("turn = " + turn);
    }
 
    public void run()
    {
        for (int i = 0; i < 2; ++i)
        {
            non_critical();
            pre_protocol();
            critical();
            post_protocol();
        }
    }
 
    // Number of processes.
 
    public static void main(String[] args)
    {
        int N = 2;
        Mutex1[] p = new Mutex1[N];
 
        // Configure and start processes.
 
        for (int i = 0; i < N; i++)
        {
            p[i] = new Mutex1(i, N);
            p[i].start();
        }
    }
}
  • Mutex2.java : Adding Java's yield method
import java.util.Random;
 
/*
 * Second attempt to solve the mutual exclusion problem 
 * Use of a turn variable and add Java's yield method from class Thread for being busy
 */
class Mutex2 extends Thread
{
    private static final Random rand = new Random();
    static int turn = 0;
 
    private int id;
 
    static int N;
 
    public Mutex2(int i, int n)
    {
        id = i;
        N = n;
    }
 
    private void busy()
    {
        try
        {
            sleep(rand.nextInt(500));
        } catch (InterruptedException e)
        {
        }
    }
 
    private void non_critical()
    {
        System.out.println("Thread " + id + " is in a NON critical section");
        busy();
    }
 
    private void critical()
    {
 
        System.out
                .println("Thread " + id + " is entering the critical section");
        busy();
        System.out.println("Thread " + id + " is leaving the critical section");
 
    }
 
    private void pre_protocol()
    {
        while (turn != id) yield() ;
    }
 
    private void post_protocol()
    {
        turn = random(N);
        System.out.println("turn = " + turn);
    }
 
    public void run()
    {
        for (int i = 0; i < 2; ++i)
        {
            non_critical();
            pre_protocol();
            critical();
            post_protocol();
        }
    }
 
    // Number of processes.
 
    public static void main(String[] args)
    {
        int N = 2;
        Mutex2[] p = new Mutex2[N];
 
        // Configure and start processes.
 
        for (int i = 0; i < N; i++)
        {
            p[i] = new Mutex2(i, N);
            p[i].start();
        }
    }
}
  • Mutex3.java : Using a "flag of intention" (unsafe)
import java.util.Random;
 
/*
 * Third attempt.
 * Using a "flag of intention". 
 * Warning: This is unsafe
 */
class Mutex3 extends Thread
{
    private static final Random rand = new Random();
    static int turn = 0;
 
    private int id;
 
    static int N;
 
    static boolean[] flag;
 
    public Mutex3(int i, int n)
    {
        id = i;
        N = n;
        flag = new boolean[N];
    }
 
    private void busy()
    {
        try
        {
            sleep(rand.nextInt(500));
        } catch (InterruptedException e)
        {
        }
    }
 
    private void non_critical()
    {
        System.out.println("Thread " + id + " is in a NON critical section");
        busy();
    }
 
    private void critical()
    {
 
        System.out
                .println("Thread " + id + " is entering the critical section");
        busy();
        System.out.println("Thread " + id + " is leaving the critical section");
 
    }
 
    private boolean wait(int i)
    {
        boolean r = false;
 
        for (int j = 0; j < N; j++)
            if (j != i)
                r |= flag[j];
 
        return r;
    }
 
    private void pre_protocol()
    {
        do
        {
        } while (wait(id));
        flag[id] = true;
    }
 
    private void post_protocol()
    {
        flag[id] = false;
    }
 
    public void run()
    {
        for (int i = 0; i < 2; ++i)
        {
            non_critical();
            pre_protocol();
            critical();
            post_protocol();
        }
    }
 
    // Number of processes.
 
    public static void main(String[] args)
    {
        int N = 2;
        Mutex3[] p = new Mutex3[N];
 
        // Configure and start processes.
 
        for (int i = 0; i < N; i++)
        {
            p[i] = new Mutex3(i, N);
            p[i].start();
        }
    }
}
  • Mutex4.java : The first serious solution. Using a synchronized block.
import java.util.Random;
package concurrency;
 
//using a synchronized block
 
class Mutex4 extends Thread
{
    private static final Random rand = new Random();
 
    private int id;
 
    static final Object lock = new Object();
 
    public Mutex4(int i)
    {
        id = i;
    }
 
    private void busy()
    {
        try
        {
            sleep(rand.nextInt(500));
        } catch (InterruptedException e)
        {
        }
    }
 
    private void non_critical()
    {
        System.out.println("Thread " + id + " is in a NON critical section");
        busy();
    }
 
    private void critical()
    {
 
        System.out
                .println("Thread " + id + " is entering the critical section");
        busy();
        System.out.println("Thread " + id + " is leaving the critical section");
 
    }
 
    public void run()
    {
        for (int i = 0; i < 2; ++i)
        {
            non_critical();
            synchronized (lock)
            {
                critical();
            }
 
        } 
    }
 
    // Number of processes.
 
    public static void main(String[] args)
    {
        int N = 2;
        Mutex4[] p = new Mutex4[N];
 
        // Configure and start processes.
 
        for (int i = 0; i < N; i++)
        {
            p[i] = new Mutex4(i);
            p[i].start();
        }
    }
}
  • Mutex5.java : Final solution. Using a synchronized method.
import java.util.Random;
 
//using a synchronized method
 
class Mutex5 extends Thread
{
    private static final Random rand = new Random();
 
    private int id;
 
    static final Object lock = new Object();
 
    public Mutex5(int i)
    {
        id = i;
    }
 
    private void busy()
    {
        try
        {
            sleep(rand.nextInt(500));
        } catch (InterruptedException e)
        {
        }
    }
 
    private void non_critical()
    {
        System.out.println("Thread " + id + " is in a NON critical section");
        busy();
    }
 
    private  synchronized void critical()
    {
 
        System.out
                .println("Thread " + id + " is entering the critical section");
        busy();
        System.out.println("Thread " + id + " is leaving the critical section");
 
    }
 
    public void run()
    {
        for (int i = 0; i < 2; ++i)
        {
            critical();
        }
    }
 
    // Number of processes.
 
    public static void main(String[] args)
    {
        int N = 2;
        Mutex5[] p = new Mutex5[N];
 
        // Configure and start processes.
 
        for (int i = 0; i < N; i++)
        {
            p[i] = new Mutex5(i);
            p[i].start();
        }
    }
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.