Login
 

Maze for Linux

  • Increase font size
  • Default font size
  • Decrease font size

Detecting a deadlock

This example uses a “classic” deadlock between two threads. Each thread locks and then unlocks two mutexes. The first thread acquires the mutexes in the order “mutex_1, mutex_2”, while the second thread acquires them in the order “mutex_2, mutex_1”.

#include <assert.h>
#include <pthread.h>

static void * simple_thread(void *);

pthread_mutex_t mutex_1
= PTHREAD_MUTEX_INITIALIZER;

pthread_mutex_t mutex_2= PTHREAD_MUTEX_INITIALIZER;


int main()
{
pthread_t tid = 0;

// create a thread
error = pthread_create(&tid, 0, &simple_thread, 0);
assert(error == 0);

error = pthread_mutex_lock(&mutex_1); // acquire mutex_1
assert(error == 0);

error = pthread_mutex_lock(&mutex_2); // acquire mutex_2
assert(error == 0);

error = pthread_mutex_unlock(&mutex_2); // release mutex_2
assert(error == 0);

error = pthread_mutex_unlock(&mutex_1); // release mutex_1
assert(error == 0);

error = pthread_join(tid, NULL);
assert(error == 0);

return 0;
}


static void * simple_thread(void * dummy)
{
int error = pthread_mutex_lock(&mutex_2); // acquire mutex_2
assert(error == 0);

error = pthread_mutex_lock(&mutex_1); // acquire mutex_1
assert(error == 0);

error = pthread_mutex_unlock(&mutex_1); // release mutex_1
assert(error == 0);

error = pthread_mutex_unlock(&mutex_2); // release mutex_2
assert(error == 0);

return NULL;
}

 

Below is an example of three possible sequences of the lock/unlock events in the two threads.

Two successful and one unsuccesful lock/unlock scenario

Depending on timing the threads may run into a deadlock: the first thread has acquired mutex_1 and is waiting for the mutex_2, while the second thread has acquired mutex_2 and is waiting for the mutex_1.

Compile the code and run it several times:

$ gcc -g deadlock.c -o deadlock -lpthread

$ ./deadlock

If the deadlock occurs, the process blocks. Otherwise it runs to completion.

Now test deadlock with maze, running it 100 timesTip:

$ maze -r 100 ./deadlock > my_logTip

Most of the runs complete successfully, yet some of them reveal the deadlock:

maze: ERROR: A deadlock was detected in the run # 59.
maze: ERROR: A deadlock was detected in the run # 88.
maze: ERROR: A deadlock was detected in the run # 100.

The stacksTip of the threads in a deadlock can be found under run # 59, 88 or 100 in my_log:

maze: Run # 59
.........................
maze:
maze: The following processes are blocking:
maze:
maze: Main thread (tgid = 16029, pid = 16029) is waiting for a mutex.
maze:
maze: #0 0x55555425 in __kernel_vsyscall ()
maze: #1 0x55578839 in __lll_lock_wait () from /lib/libpthread-2.8.so
maze: #2 0x8048653 in main () at deadlock.c:30
maze:
maze: Thread (tgid = 16029, pid = 16030) is waiting for a mutex.
maze:
maze: #0 0x55555425 in __kernel_vsyscall ()
maze: #1 0x55578839 in __lll_lock_wait () from /lib/libpthread-2.8.so
maze: #2 0x804874b in simple_thread (dummy = 0) at deadlock.c:48
maze: #3 0x5557232f in start_thread () from /lib/libpthread-2.8.so
maze: #4 0x40820e in __clone () from /lib/libc-2.8.so
maze:
maze: Run # 59 completed with 1 error.


The deadlock can be reproduced by maze in the RECONSTRUCTION mode:

$ maze -R 59