Showing a simple example of deadlock with semaphores

Question

I'm currently taking Operating Systems and our teacher assigned this problem for our lab but he's not very helpful. So I need to show a basic example of deadlock with semaphores and my output needs to demonstrate the occurence of the deadlock. I'm assuming he means if my exception is caught. This is as close as I've gotten.

import java.util.concurrent.Semaphore;
public class deadlockTest2
{
    private Semaphore sem1=new Semaphore(1);
    private Semaphore sem2=new Semaphore(1);
    private int num;

    public deadlockTest2(int random)
    {
            num=random;
    }
    public void run()
    {
        try 
        {
            sem1.acquire();
        }
         catch (InterruptedException e)
        {
            System.out.println("I am deadlocked");}
        }

    public static void main(String[] args)
    {
        deadlockTest2 tester=new deadlockTest2(5);
        deadlockTest2 tester2=new deadlockTest2(20);
        tester.run();
        tester2.run();
    }   
}

~
~
Am I even close? I keep reading material but not fully grasping it. I think I don't understand what a process is. Someone please help.

Answer 1

A deadlock occurs when two or more processes all block one another from completing execution. You can think of a process as just a separate program; they run concurrently with your other processes.

A basic example of a deadlock is a program with two processes and two mutexes, where each process needs access to both mutexes but does not release it's own mutex until it acquires the other mutex. An example:

1. Process A locks Mutex A
2. Process B locks Mutex B
3. Process A wants to lock Mutex B but has already been locked by Process B!
4. Process B wants to lock Mutex A but has already been locked by Process A!

Note: A mutex is simply a semaphore with a value of 1.

It's easy to see this will continue forever, since neither process will release their own resource before locking the other resource. These two processes are in deadlock.

The first problem I see with your implementation is that you're giving each process a set of their OWN semaphores, this won't work because you need these semaphores to be shared between the processes. It's as if you did this:

1. Process A locks Mutex A_A (exists in Process A)
2. Process B locks Mutex B_B (exists in Process B)
3. Process A locks Mutex B_A (exists in Process A)
4. Process B locks Mutex A_B (exists in Process B)

So it's as if you had FOUR seperate semaphores (each process has one Mutex A and one Mutex B) instead of the intended TWO.

What you want should be more along the lines of:

Semaphore sem1 = new Semaphore(1);
Semaphore sem2 = new Semaphore(1);

public class deadlockTest1 implements Runnable
{
    public void run()
    {
        sem1.acquire();
        Thread.sleep(1000);
        sem2.acquire();
    }
}

public class deadlockTest2 implements Runnable
{
    public void run()
    {
        sem2.acquire();
        Thread.sleep(1000);
        sem1.acquire();
    }
}

Then in your main function:

public static void main(String[] args)
{
    deadlockTest1 tester1 = new deadlockTest1();
    deadlockTest2 tester2 = new deadlockTest2();
    tester1.run();
    tester2.run();
}

This should do exactly what I described in my first example. When each process is first run, they will each successfully acquire their own mutexes (A lock sem1, B lock sem2) then they will sleep for 1 second. On wake up they will each try to lock the other mutex (A try lock sem2, B try lock sem1), but since those resources were never released by their respective processes, they cannot be acquired and so these two processes will block indefinitely.