Deadlock Problem:
Scenario 1: Self deadlock - "re-acquire lock"
Say there's a thread A, it acquires lock X1 and then before relenquishing the lock, it re-acquires it. This will lead to a deadlock.
thread_A()
{
. . .
spinlock_lock(&X1)
do_some_stuff()
spinlock_lock(&X1) //deadlock!!
. . .
spinlock_unlock(&X1)
}
Scenario 2: ABBA deadlock
Say there're two threads thread A and thread B executing simultaneously and two locks X1 and X2 (protecting some critical region). A acquires X1 and B acquires X2 and then A tries to acquire X2 and B tries to acquire X1. This will deadlock the both the threads.
thread_A()
{
. . .
spinlock_lock(&X1)
do_some_stuff()
spinlock_lock(&X2) //deadlock if thread_B has already acquired X2 as well as X1
. . .
}
thread_B()
{
. . .
spinlock_lock(&X2)
do_some_stuff()
spinlock_lock(&X1) //deadlock if thread_A has already acquired X1 as well as X2
. . .
}
How to avoid deadlocks (Coding Guidelines):
These guidelines are basically spawned from the kind of deadlocks that exist:
1. Maintain lock order ie where ever multiple locks are being acquired, make sure they are all acquired in the same order otherwise it would lead to a ABBA deadlock situation above.
2. Never re-acquire the same lock that you are holding, be aware the code that will be executed in the current thread, the functions that will be called, so if a lock has been acquired in some upstream function, don't reacquire it!
How to detect / solve deadlocks:
1. Manually inspect the code to check against the coding guidelines above.
2. Run strace -p <pid> and check if the process is stuck in wait.
3. If you suspect your application is *stuck*, do a ps aux|grep <application name>. If the output is "D" (uninterruptible sleep), it *could* mean there's a deadlock in your code.
4. Linux kernel has an inbuilt feature called lockdep. It can help in pin-pointing the line in code causing the deadlock. See this post (post incomplete, check my answer on stackoverflow instead) on how to detect deadlocks using lockdep.
5. Helgrind
Deadlocks (if very few), don't always need taking care of since it'll require too much effort and won't affect the system performance much, one can just reboot and get going, as Tom West said, "Not everything worth doing is worth doing well"
A deadlock is a scenario when one thread is waiting for a resource which is held by the second thread, while the second thread is waiting for a resource held by the first thread. Thus causing both the threads to wait for each other infinitely.
To show how this situation might occur, in the following example we have used two mutexes,read_mutex and write_mutex. To gain access to the file both these mutexes have to be locked. In the code, the write thread locks write_mutex and then after a little delay tries to locks read_mutex. The read thread on the other hand locks read_mutex first and then tries to lock write_mutex.
Thus by the time the write tries to access read_mutex, it has already been locked by read thread and by the time read thread tries to lock write_mutex, it has already been locked by the write thread. Thus both the threads end up waiting infinitely for each other to unlock the mutexes and process ends up in a deadlock.
examples:
#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
pthread_mutex_t read_mutex;
pthread_mutex_t write_mutex;
void * write(void *temp) {
char *ret;
FILE *file1;
char *str;
pthread_mutex_lock(&write_mutex);
sleep(5);
pthread_mutex_lock(&read_mutex);
printf("\nFile locked, please enter the message \n");
str=(char *)malloc(10*sizeof(char));
file1=fopen("temp","w");
scanf("%s",str);
fprintf(file1,"%s",str);
fclose(file1);
pthread_mutex_unlock(&read_mutex);
pthread_mutex_unlock(&write_mutex);
printf("\nUnlocked the file you can read it now \n");
return ret;
}
void * read(void *temp) {
char *ret;
FILE *file1;
char *str;
pthread_mutex_lock(&read_mutex);
sleep(5);
pthread_mutex_lock(&write_mutex);
printf("\n Opening file \n");
file1=fopen("temp","r");
str=(char *)malloc(10*sizeof(char));
fscanf(file1,"%s",str);
printf("\n Message from file is %s \n",str);
fclose(file1);
pthread_mutex_unlock(&write_mutex);
pthread_mutex_unlock(&read_mutex);
return ret;
}
main() {
pthread_t thread_id,thread_id1;
pthread_attr_t attr;
int ret;
void *res;
ret=pthread_create(&thread_id,NULL,&write,NULL);
ret=pthread_create(&thread_id1,NULL,&read,NULL);
printf("\n Created thread");
pthread_join(thread_id,&res);
pthread_join(thread_id1,&res);
}
compilation:
Save the file as mutex_deadlock.c, and compile it by passing "-lpthread" flag.
$ cc -lpthread mutex_deadlock.c -o mutex_deadlock
$ ./mutex_deadlock
There will be no output as both the threads endup in a deadlock state, to get out of the execution use "cntrl + c".
To avoid such simple deadlocks the easiest method is to make sure that all the threads access the locks in a specific order. In the above example if it is made compulsory that every thread should lock write_mutex first and then try to lock read_mutex, then the deadlock situation will not occur as only one thread will get access to write_mutex first and the same thread will be able to access read_mutex too.
The above code modified to avoid deadlock is shown below. Note that the order of acquiring lock by both the threads is the same, thus able to prevent deadlock.
#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
pthread_mutex_t read_mutex;
pthread_mutex_t write_mutex;
void * write(void *temp) {
char *ret;
FILE *file1;
char *str;
pthread_mutex_lock(&write_mutex);
sleep(5);
pthread_mutex_lock(&read_mutex);
printf("\nFile locked, please enter the message \n");
str=(char *)malloc(10*sizeof(char));
file1=fopen("temp","w");
scanf("%s",str);
fprintf(file1,"%s",str);
fclose(file1);
pthread_mutex_unlock(&read_mutex);
pthread_mutex_unlock(&write_mutex);
printf("\nUnlocked the file you can read it now \n");
return ret;
}
void * read(void *temp) {
char *ret;
FILE *file1;
char *str;
pthread_mutex_lock(&write_mutex);
sleep(5);
pthread_mutex_lock(&read_mutex);
printf("\n Opening file \n");
file1=fopen("temp","r");
str=(char *)malloc(10*sizeof(char));
fscanf(file1,"%s",str);
printf("\n Message from file is %s \n",str);
fclose(file1);
pthread_mutex_unlock(&read_mutex);
pthread_mutex_unlock(&write_mutex);
return ret;
}
main() {
pthread_t thread_id,thread_id1;
pthread_attr_t attr;
int ret;
void *res;
ret=pthread_create(&thread_id,NULL,&write,NULL);
ret=pthread_create(&thread_id1,NULL,&read,NULL);
printf("\n Created thread");
pthread_join(thread_id,&res);
pthread_join(thread_id1,&res);
}
$ cc -lpthread mutex_nodeadlok.c -o create_nodeadlock
$ ./create_nodeadlock
Created thread
File locked, please enter the message
Hello
Unlocked the file you can read it now
Opening file
Message from file is Hello
Scenario 1: Self deadlock - "re-acquire lock"
Say there's a thread A, it acquires lock X1 and then before relenquishing the lock, it re-acquires it. This will lead to a deadlock.
thread_A()
{
. . .
spinlock_lock(&X1)
do_some_stuff()
spinlock_lock(&X1) //deadlock!!
. . .
spinlock_unlock(&X1)
}
Scenario 2: ABBA deadlock
Say there're two threads thread A and thread B executing simultaneously and two locks X1 and X2 (protecting some critical region). A acquires X1 and B acquires X2 and then A tries to acquire X2 and B tries to acquire X1. This will deadlock the both the threads.
thread_A()
{
. . .
spinlock_lock(&X1)
do_some_stuff()
spinlock_lock(&X2) //deadlock if thread_B has already acquired X2 as well as X1
. . .
}
thread_B()
{
. . .
spinlock_lock(&X2)
do_some_stuff()
spinlock_lock(&X1) //deadlock if thread_A has already acquired X1 as well as X2
. . .
}
How to avoid deadlocks (Coding Guidelines):
These guidelines are basically spawned from the kind of deadlocks that exist:
1. Maintain lock order ie where ever multiple locks are being acquired, make sure they are all acquired in the same order otherwise it would lead to a ABBA deadlock situation above.
2. Never re-acquire the same lock that you are holding, be aware the code that will be executed in the current thread, the functions that will be called, so if a lock has been acquired in some upstream function, don't reacquire it!
How to detect / solve deadlocks:
1. Manually inspect the code to check against the coding guidelines above.
2. Run strace -p <pid> and check if the process is stuck in wait.
3. If you suspect your application is *stuck*, do a ps aux|grep <application name>. If the output is "D" (uninterruptible sleep), it *could* mean there's a deadlock in your code.
4. Linux kernel has an inbuilt feature called lockdep. It can help in pin-pointing the line in code causing the deadlock. See this post (post incomplete, check my answer on stackoverflow instead) on how to detect deadlocks using lockdep.
5. Helgrind
Deadlocks (if very few), don't always need taking care of since it'll require too much effort and won't affect the system performance much, one can just reboot and get going, as Tom West said, "Not everything worth doing is worth doing well"
A deadlock is a scenario when one thread is waiting for a resource which is held by the second thread, while the second thread is waiting for a resource held by the first thread. Thus causing both the threads to wait for each other infinitely.
To show how this situation might occur, in the following example we have used two mutexes,read_mutex and write_mutex. To gain access to the file both these mutexes have to be locked. In the code, the write thread locks write_mutex and then after a little delay tries to locks read_mutex. The read thread on the other hand locks read_mutex first and then tries to lock write_mutex.
Thus by the time the write tries to access read_mutex, it has already been locked by read thread and by the time read thread tries to lock write_mutex, it has already been locked by the write thread. Thus both the threads end up waiting infinitely for each other to unlock the mutexes and process ends up in a deadlock.
examples:
#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
pthread_mutex_t read_mutex;
pthread_mutex_t write_mutex;
void * write(void *temp) {
char *ret;
FILE *file1;
char *str;
pthread_mutex_lock(&write_mutex);
sleep(5);
pthread_mutex_lock(&read_mutex);
printf("\nFile locked, please enter the message \n");
str=(char *)malloc(10*sizeof(char));
file1=fopen("temp","w");
scanf("%s",str);
fprintf(file1,"%s",str);
fclose(file1);
pthread_mutex_unlock(&read_mutex);
pthread_mutex_unlock(&write_mutex);
printf("\nUnlocked the file you can read it now \n");
return ret;
}
void * read(void *temp) {
char *ret;
FILE *file1;
char *str;
pthread_mutex_lock(&read_mutex);
sleep(5);
pthread_mutex_lock(&write_mutex);
printf("\n Opening file \n");
file1=fopen("temp","r");
str=(char *)malloc(10*sizeof(char));
fscanf(file1,"%s",str);
printf("\n Message from file is %s \n",str);
fclose(file1);
pthread_mutex_unlock(&write_mutex);
pthread_mutex_unlock(&read_mutex);
return ret;
}
main() {
pthread_t thread_id,thread_id1;
pthread_attr_t attr;
int ret;
void *res;
ret=pthread_create(&thread_id,NULL,&write,NULL);
ret=pthread_create(&thread_id1,NULL,&read,NULL);
printf("\n Created thread");
pthread_join(thread_id,&res);
pthread_join(thread_id1,&res);
}
compilation:
Save the file as mutex_deadlock.c, and compile it by passing "-lpthread" flag.
$ cc -lpthread mutex_deadlock.c -o mutex_deadlock
$ ./mutex_deadlock
There will be no output as both the threads endup in a deadlock state, to get out of the execution use "cntrl + c".
To avoid such simple deadlocks the easiest method is to make sure that all the threads access the locks in a specific order. In the above example if it is made compulsory that every thread should lock write_mutex first and then try to lock read_mutex, then the deadlock situation will not occur as only one thread will get access to write_mutex first and the same thread will be able to access read_mutex too.
The above code modified to avoid deadlock is shown below. Note that the order of acquiring lock by both the threads is the same, thus able to prevent deadlock.
#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
pthread_mutex_t read_mutex;
pthread_mutex_t write_mutex;
void * write(void *temp) {
char *ret;
FILE *file1;
char *str;
pthread_mutex_lock(&write_mutex);
sleep(5);
pthread_mutex_lock(&read_mutex);
printf("\nFile locked, please enter the message \n");
str=(char *)malloc(10*sizeof(char));
file1=fopen("temp","w");
scanf("%s",str);
fprintf(file1,"%s",str);
fclose(file1);
pthread_mutex_unlock(&read_mutex);
pthread_mutex_unlock(&write_mutex);
printf("\nUnlocked the file you can read it now \n");
return ret;
}
void * read(void *temp) {
char *ret;
FILE *file1;
char *str;
pthread_mutex_lock(&write_mutex);
sleep(5);
pthread_mutex_lock(&read_mutex);
printf("\n Opening file \n");
file1=fopen("temp","r");
str=(char *)malloc(10*sizeof(char));
fscanf(file1,"%s",str);
printf("\n Message from file is %s \n",str);
fclose(file1);
pthread_mutex_unlock(&read_mutex);
pthread_mutex_unlock(&write_mutex);
return ret;
}
main() {
pthread_t thread_id,thread_id1;
pthread_attr_t attr;
int ret;
void *res;
ret=pthread_create(&thread_id,NULL,&write,NULL);
ret=pthread_create(&thread_id1,NULL,&read,NULL);
printf("\n Created thread");
pthread_join(thread_id,&res);
pthread_join(thread_id1,&res);
}
$ cc -lpthread mutex_nodeadlok.c -o create_nodeadlock
$ ./create_nodeadlock
Created thread
File locked, please enter the message
Hello
Unlocked the file you can read it now
Opening file
Message from file is Hello
No comments:
Post a Comment