Unix Prog: Deadlock Avoidance(1)

1. Deadlock Occur
1) One thread try to lock same mutex twice
2) One thread locks mutex a while waiting for unlocking of mutex b.
Another thread locks mutex b while waiting for unlocking of mutex a.

Solution:
1) Don't try to lock same mutex more than one time.
2) Always lock mutex with same order at all threads!
always lock mutex a then mutex b in above example

2. Example avoiding the deadlock:
deadlock.c:

 #include<stdio.h>  
 #include<stdlib.h>  
 #include<unistd.h>  
 #include<pthread.h>  
   
 #define NHASH 29  
 #define HASH(fp) (((unsigned long)fp) % NHASH)  
 struct foo *fh[NHASH];  
   
 pthread_mutex_t hashlock = PTHREAD_MUTEX_INITIALIZER;  
   
 struct foo {  
  int f_count;  
  pthread_mutex_t f_lock;  
  struct foo *f_next;  
  int f_id;  
 };  
   
 struct foo *foo_alloc(int id)  
 {  
  struct foo *fp;  
  int idx;  
   
  // Create the struct foo and insert into hash table  
  if ((fp = malloc(sizeof(struct foo))) != NULL) {  
   fp->f_count = 1;  
   fp->f_id = id;  
   if(pthread_mutex_init(&fp->f_lock, NULL) != 0) {  
    free(fp);  
    return NULL;  
   }  
   
   // Call hash function to get the hash index  
   // Insert the struct into hash table  
   // Insert the struct into the front of list  
   idx = HASH(fp);  
   pthread_mutex_lock(&hashlock);  
   fp->f_next = fh[idx];  
   fh[idx] = fp;  
   
   // After inserting into the hash table, struct foo is inside  
   // global data structure. It is possible that other threads may  
   // access it. At this time, we need lock the mutex. Also, we honor  
   // the order of locking hashlcok firstly then f_lock in struct foo  
   pthread_mutex_lock(&fp->f_lock);  
   pthread_mutex_unlock(&hashlock);  
   /* ... cotinue initialization ... */  
   pthread_mutex_unlock(&fp->f_lock);  
  }  
   
  return (fp);  
 }  
   
 void foo_hold(struct foo *fp)  
 {  
  pthread_mutex_lock(&fp->f_lock);  
  fp->f_count++;  
  pthread_mutex_unlock(&fp->f_lock);  
 }  
   
 struct foo * foo_find(int id)  
 {  
  struct foo *fp;  
  int idx;  
   
  pthread_mutex_lock(&hashlock);  
   
  // Find the struct with specified id  
  for(idx = 0; idx < NHASH; idx++) {  
   for(fp = fh[idx]; fp != NULL; fp = fp->f_next) {  
    if(fp->f_id == id) {  
     // if found the struct, call foo_hold, note that we are still  
     // honoring the order of locking hashlock firstly then f_lock  
     // to avoid deadlock  
     foo_hold(fp);  
     pthread_mutex_unlock(&hashlock);  
     return fp;  
    }  
   }  
  }  
   
  // If not found the struct, return NULL  
  pthread_mutex_unlock(&hashlock);  
  return NULL;  
 }  
   
 void foo_rele(struct foo*fp)  
 {  
  struct foo *tfp;  
  int idx;  
   
  // Before accessing the struct in global data structure, we need  
  // to acquire the lock firstly  
  pthread_mutex_lock(&fp->f_lock);  
  if(fp->f_count == 1) {  
   // After confirming that f_count = 1, we plan to remove it from  
   // the hash table. Then we need to lock hashlock mutex to modify  
   // the hash table. But the problem here is: we need to unlock  
   // f_lock firstly, then lock hashlock, to honor the order that  
   // we should always lock hashlock firstly then lock f_lock to avoid  
   // dead lock.  
   
   // After we unlock f_lock, and then lock the hashlock, and then  
   // lock f_lock, during this minor time period, other threads are  
   // possible to modify the struct. so we need to re-confirm whether  
   // f_count is still 1, if not, reduce the reference count and return  
   pthread_mutex_unlock(&fp->f_lock);  
   pthread_mutex_lock(&hashlock);  
   pthread_mutex_lock(&fp->f_lock);  
   if(fp->f_count != 1) {  
    fp->f_count--;  
    pthread_mutex_unlock(&fp->f_lock);  
    pthread_mutex_unlock(&hashlock);  
    return;  
   }  
   
   //If reference count is still 1, then we proceed to remove it from list  
   idx = HASH(fp);  
   tfp = fh[idx];  
   if(tfp == fp) {  
    fh[idx] = fp->f_next;  
   } else {  
    while(tfp->f_next != fp)  
     tfp = tfp->f_next;  
    tfp->f_next = fp->f_next;  
   }  
   
   //Release lock the struct foo  
   pthread_mutex_unlock(&hashlock);  
   pthread_mutex_unlock(&fp->f_lock);  
   pthread_mutex_destroy(&fp->f_lock);  
   free(fp);  
  }  
  else {  
   fp->f_count--;  
   pthread_mutex_unlock(&fp->f_lock);  
  }  
 }  
   
 int main(int argc, char* argv[])  
 {  
  struct foo *fp1;  
  struct foo *fp2;  
  fp1 = foo_alloc(1);  
  fp2 = foo_alloc(2);  
  fp1 = foo_find(1);  
   
  foo_rele(fp1);  
  foo_rele(fp1);  
  foo_rele(fp2);  
  exit(0);  
 }  

With all methods used in above example, we made struct foo in hash table to be thread safety. It won't be deadlocked in any situation.