Lec 26: Deadlock Avoidance
Table of Contents
1 Deadlocks Review
Recall from the previous lecture that when we use fine grain locking, there is a potential for deadlock. Where two threads hold the resource the other needs. An example of this is in the following code:
#include <stdio.h> #include <stdlib.h> #include <pthread.h> pthread_mutex_t lock_a, lock_b; void * fun_1(void * arg){ int i; for (i = 0 ; i< 10000 ; i++){ pthread_mutex_lock(&lock_a); //lock a then b pthread_mutex_lock(&lock_b); //CRITICAL SECTION pthread_mutex_unlock(&lock_a); pthread_mutex_unlock(&lock_b); } return NULL; } void * fun_2(void * arg){ int i; for (i = 0 ; i< 10000 ; i++){ pthread_mutex_lock(&lock_b); //lock b then a pthread_mutex_lock(&lock_a); //CRITICAL SECTION pthread_mutex_unlock(&lock_b); pthread_mutex_unlock(&lock_a); } return NULL; } int main(){ pthread_t thread_1,thread_2; pthread_mutex_init(&lock_a, NULL); pthread_mutex_init(&lock_b, NULL); pthread_create(&thread_1, NULL, fun_1, NULL); pthread_create(&thread_2, NULL, fun_2, NULL); pthread_join(thread_1, NULL); pthread_join(thread_2, NULL); return 0; }
In this code we have two threads and two locks. One thread acquires
lock_a and then lock_b while the other thread acquires lock_b
and then lock_a. If we run this program we find that nothing
happens; the program hangs. This is because of a deadlock.
Consider what happens when one each thread run such that one holds
lock_a and the other holds lock_b, then one thread is waiting
on the lock the other thread holds. Both threads are now blocking
on acquiring the resources, and the main thread is blocking trying
to join the worker threads. Nothing is running: deadlock.
2 Avoiding Deadlocks
Deadlocks are very hard to debug and are a big part of concurrent programming. The best way to avoid deadlocks is to ensure that all locking for all threads occur in the same order. That may seam like a simple task, but it is not because the notion of ordering is not always clear. Let's look at a slightly more complicated example of the bank where instead of a single account, we have multiple accounts. A thread randonly chooses two accounts and transfer money between them.
#define INIT_BALANCE 1000 #define NUM_TRANS 100 #define MAX_TRANS 10 #define NUM_ACCOUNTS 10 //create an account struct account{ int balance; int credits; int debits; }; //array of accounts struct account accounts[NUM_ACCOUNTS]; void * transactions(void * args){ int i,v; int a1,a2; for(i=0;i<NUM_TRANS;i++){ //choose a random value v = (int) random() % NUM_TRANS; //choose two random accounts a1 = (int) random() % NUM_ACCOUNTS; while((a2 = (int) random() % NUM_ACCOUNTS) == a1); //transfer from a1 to a2 accounts[a1].balance += v; accounts[a1].credits += v; accounts[a2].balance -= v; accounts[a2].debits += v; } return 0; }
If we run this program, since we have no locking, we run into the same situation as before, inconsistent output. Let's look at how we might want to add locks to the program. The simplest means to do this is to use fine locking at the level accounts.
2.1 Lock Acquisition Issues
By adding a lock to each account, we now require a worker thread to acquire the account lock on both accounts before executing a transfer:
//create an account struct account{ int balance; int credits; int debits; pthread_mutex_t lock; //lock for the account }; //array of accounts struct account accounts[NUM_ACCOUNTS]; void * transactions(void * args){ int i,v; int a1,a2; for(i=0;i<NUM_TRANS;i++){ //choose a random value v = (int) random() % NUM_TRANS; //choose two random accounts a1 = (int) random() % NUM_ACCOUNTS; while((a2 = (int) random() % NUM_ACCOUNTS) == a1); //transfer from a1 to a2 // printf("Transfer %d->%d : %d \n", a1,a2,v); //acquire lock for a1 then a2 pthread_mutex_lock(&accounts[a1].lock); pthread_mutex_lock(&accounts[a2].lock); accounts[a1].balance += v; accounts[a1].credits += v; accounts[a2].balance -= v; accounts[a2].debits += v; pthread_mutex_unlock(&accounts[a1].lock); pthread_mutex_unlock(&accounts[a2].lock); } return 0; }
This might seem to work, but this locking strategy actually will
form a deadlock. Why? The locking strategy is to lock a1 then a2
always in that order, how could a deadlock occur?
Consider that the accounts are chosen randomly from all accounts and
that there are multiple threads running. The variables a1 and a2
are standin's for account numbers or indexes into the array of
accounts. What if in two threads the following happens?
Thread 1 Thread 2 --------- ---------- a1 = 5; a1 = 3; a2 = 3; a2 = 5;
Then when we look at lock ordering, we find the following situation and deadlock might occur:
Thread 1 Thread 2
--------- ----------
lock( 5 )
lock( 3 )
lock( 3 )
lock( 5 )
DEADLOCK
We find ourselves back where we started, each thread is now waiting on a lock held by another thread. Progress cannot be made and a deadlock occurs. This happens because we did not apply a proper order to locking: How do we apply a proper ordering?
2.2 Ordering Resources to Avoid Deadlock
One way to apply a proper ordering is to leverage the fact that the
account indexes are already ordered. What if we always lock accounts
in account order? Then in above example, both threads would do
lock(3) then lock(5). In code, this would look like this:
void * transactions(void * args){ int i,v; int a1,a2; for(i=0;i<NUM_TRANS;i++){ //choose a random value v = (int) random() % NUM_TRANS; //choose two random accounts a1 = (int) random() % NUM_ACCOUNTS; while((a2 = (int) random() % NUM_ACCOUNTS) == a1); //transfer from a1 to a2 if(a1 < a2){ pthread_mutex_lock(&accounts[a1].lock); pthread_mutex_lock(&accounts[a2].lock); }else{ pthread_mutex_lock(&accounts[a2].lock); pthread_mutex_lock(&accounts[a1].lock); } accounts[a1].balance += v; accounts[a1].credits += v; accounts[a2].balance -= v; accounts[a2].debits += v; if(a1 < a2){ pthread_mutex_unlock(&accounts[a2].lock); pthread_mutex_unlock(&accounts[a1].lock); }else{ pthread_mutex_unlock(&accounts[a1].lock); pthread_mutex_unlock(&accounts[a2].lock); } } return 0; }
Now, everything is consistent and deadlock is avoided.
3 EXERCISE: The Dining Philosophers
The Dining philosophers is a classic problem of deadlock avoidance. The story goes that a philosopher does only two things in life, eat or philosophize. This particular group of philosophers sits at a large round table with food in front of each of them, and between each philosopher is a single fork. When a philosopher wishes to eat, they must acquire the fork to their right and their left, but those forks are also shared with the adjacent philosopher. If an adjacent philosopher is currently eating, then the hungry philosopher must wait for the other to finish before acquiring the fork. Once a fork is acquired, a philosopher must hold on to it until they are finished eating.
Let's look at a code example of how this might be implemented using threading:
#include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <sys/types.h> #include <pthread.h> #define NUM_PHIL 10 #define ROUNDS 1000 struct fork{ int id; pthread_mutex_t * lock; //the lock on the fork }; struct philosopher{ int id; //id of this philosopher struct fork * left; //the left fork struct fork * right; //the right fork pthread_t thread_id; //POSIX thread id }; struct fork forks[NUM_PHIL]; struct philosopher philosophers[NUM_PHIL]; void * eat(void * args){ struct philosopher * phil = (struct philosopher *) args; int i; for (i = 0;i<ROUNDS;i++){ //TODO: fix locking to avoid deadlock printf("Philosopher %d ACQUIRING left fork %d\n", phil->id, phil->left->id); pthread_mutex_lock(phil->left->lock); printf("Philosopher %d ACQUIRING right fork %d\n", phil->id, phil->right->id); pthread_mutex_lock(phil->right->lock); printf("Philosopher %d EATING with fork %d and %d\n", phil->id, phil->left->id, phil->right->id); usleep(250); //sleep for a quarter second printf("Philosopher %d RELEASING fork %d\n", phil->id, phil->left->id); pthread_mutex_unlock(phil->left->lock); printf("Philosopher %d RELEASING fork %d\n", phil->id, phil->right->id); pthread_mutex_unlock(phil->right->lock); } return NULL; } int main(){ int i; printf("Initializing forks: %d\n", NUM_PHIL-1); //initialize the forks for(i=0;i<NUM_PHIL;i++){ forks[i].id = i; forks[i].lock = malloc(sizeof(pthread_mutex_t)); pthread_mutex_init(forks[i].lock, NULL); } printf("Initializing philosophers: %d\n", NUM_PHIL); //initialize the philosophers for(i=0;i<NUM_PHIL;i++){ philosophers[i].id = i; if( i == 0){ philosophers[i].left = &forks[(NUM_PHIL-1)]; }else{ philosophers[i].left = &forks[i-1]; } philosophers[i].right = &forks[(i) % NUM_PHIL]; } printf("Starting Threads\n"); //start the threads for(i=0;i<NUM_PHIL;i++){ pthread_create(&(philosophers[i].thread_id), NULL, eat, (void *) &(philosophers[i])); } //join the threads for(i=0;i<NUM_PHIL;i++){ pthread_join(philosophers[i].thread_id, NULL); } printf("All threads joined\n"); //clean memory for(i=0;i<NUM_PHIL-1;i++){ pthread_mutex_destroy(forks[i].lock); free(forks[i].lock); } return 0; }
You'll see we have a structure for philosophers and forks, and that
each philosopher has a fork to the right and left. The philosopher
with id 0 shares a fork with the philosopher with id NUM_PHIL-1
because they are sitting at a round table.
If we look at the locking procedure more closely, we see that there appears to be reasonable ordering:
printf("Philosopher %d ACQUIRING left fork %d\n", phil->id, phil->left->id); pthread_mutex_lock(phil->left->lock); printf("Philosopher %d ACQUIRING right fork %d\n", phil->id, phil->right->id); pthread_mutex_lock(phil->right->lock);
Every philosopher first reaches left to pick up a fork and then reaches right to pick up a fork. But, it doesn't avoid deadlock.
Your task, working with a partner, is to:
- Analyze the program to determine why a deadlock occurs by providing a scenario that causes deadlock.
- Provide a solution that avoids deadlock.
DO NOT GOOGLE THE ANSWERS
You must fill in your solution on the lab sheet provided.