Consider a hypothetical example. Suppose you are taking a computer science course and have to do a project on "Chess Programming using SDL". The project is simple and may take one or two days to finish. However, to do the project you must study two books, one on "Chess Programming" and one on "SDL", and your college's library has one copy of each of them. You first check out the "Chess Programming" book and study it. Later, you try to check out the "SDL" book but it turns out that the book has been checked out by another student, say, Arnold who is doing the same project. You are waiting for Arnold to return "SDL" so that you can check it out to finish the project and return both books to the library ( you will not return any book until you have finished your project ). However, Arnold is also waiting for you to return "Chess Programming". The problem is that none of you can have both books and none of you can finish the project. So both of you are waiting indefinitely for the other person to return the book. You and Arnold are in a deadlock state.
In reality, deadlocks can occur in many ways. The following figure shows a deadlock that could develop in cities. A number of of automobiles are trying to drive through a busy cross street, and the traffic is completely snarled. The patrol has to unwind the jam by carefully and slowly backing the cars out of the congested section.
In a multi-threaded program, deadlocks develop because of the normal contention among threads for dedicated resources ( i.e. resources that may be used over time by many threads but only one thread at a time, sometimes referred to as serially reusable resources ). For deadlock to occur, four conditions must be met:
- Mutual exclusion: At least one resource must be held in a nonsharable way. That is, only one thread at a time can use the resource.
- Hold and wait: A thread must be holding at least one resource and waiting to acquire additional resources that are currently being held by other threads.
- Circular wait: The threads are hold-and-wait in a circular manner.
- No preemption: The resources cannot be preempted. That is, a resource can be released only voluntarily by the thread holding it, after the that thread has completed her task.
The following program deadlock.cpp shows the occurence of deadlock. Thread Arnold has acquired variable a and requests to access variable b while Groper has acquired b and requests access to a. So they are in a deadlock state. When you execute the program, it will be hung after each thread has printed a message as the two threads are deadlocked and could not proceed further.
/*
deadlock.cpp
A simple example demonstrating the occurrence of deadlock.
Compile: g++ -o deadlock deadlock.cpp -lSDL -lpthread
Execute: ./deadlock
*/
#include <SDL/SDL.h>
#include <SDL/SDL_thread.h>
#include <stdlib.h>
using namespace std;
bool value_consumed = true;
SDL_mutex *mutexa, *mutexb; //mutexes for accessing a, b
bool quit = false;
int a = 0, b = 0;
int thread1 ( void *data )
{
char *tname = ( char * )data;
while ( !quit ) {
printf("I am %s. ", tname );
SDL_mutexP ( mutexa ); //lock before processing a
printf("%s has locked a\n", tname);
++a; //dummy instruction
//do somehting
SDL_Delay( 10 );
//also need b value
SDL_mutexP ( mutexb ); //lock before accessing b
printf("%s has locked b\n", tname);
a += b++; //dummy instruction
//release lock b
SDL_mutexV ( mutexb );
//release lock a
SDL_mutexV ( mutexa );
//delay for a random amount of time
SDL_Delay ( rand() % 3000 );
}
printf("%s quits\n"), tname;
return 0;
}
int thread2 ( void *data )
{
char *tname = ( char * )data;
while ( !quit ) {
printf("I am %s. ", tname );
SDL_mutexP ( mutexb ); //lock before processing b
printf("%s has locked b\n", tname);
++b; //dummy instruction
//do somehting
SDL_Delay( 10 );
//also need a value
SDL_mutexP ( mutexa ); //lock before accessing a
printf("%s has locked b\n", tname);
a += b++; //dummy instruction
//release the lock a
SDL_mutexV ( mutexa );
//release the lock b
SDL_mutexV ( mutexb );
//delay for a random amount of time
SDL_Delay ( rand() % 3000 );
}
printf("%s quits\n"), tname;
return 0;
}
int main ()
{
SDL_Thread *id1, *id2; //thread identifiers
char *tnames[2] = { "Arnold", "Groper" }; //names of threads
mutexa = SDL_CreateMutex();
mutexb = SDL_CreateMutex();
//create the threads
id1 = SDL_CreateThread ( thread1, tnames[0] );
id2 = SDL_CreateThread ( thread2, tnames[1] );
//experiment with 20 seconds
for ( int i = 0; i < 10; ++i )
SDL_Delay ( 2000 );
quit = true; //signal the threads to return
//wait for the threads to exit
SDL_WaitThread ( id1, NULL );
SDL_WaitThread ( id2, NULL );
return 0;
}
|
The above example shows how easy deadlock could occur in a multi-threaded program. You must be careful when using semaphores; one subtle error would make everything come to a grinding halt. Errors could originate from race conditions, deadlocks, and other forms of unpredictable and ireproducible behavior.
To make it easier to write programs, other higher level synchronization methods have been proposed. A more well-known synchronization primitive called monitor is quite commonly used in concurrent programming. A monitor is a collection of functions, variables, and data structures that are all grouped together in a special kind of module package. A thread may call the functions in a monitor whenever she wants to, but she cannot directly access the monitor's internal data structures from functions declared outside the monitor. This is also the main method used in the Java language to synchronize threads. Java uses the key word synchronized to declare a monitor.