Understanding Deadlock and Starvation in Systems Programming

CS252: Systems Programming Ninghui Li Based on Slides by Prof. Gustavo Rodriguez-Rivera Topic 14: Deadlock & Dinning Philosophers

Deadlock and Starvation Deadlock It happens when one or more threads will have to block forever ( or until process is terminated) because they have to wait for a resource that will never be available. Once a deadlock happens, the process has to be killed. Therefore we have to prevent deadlocks in the first place. Starvation This condition is not as serious as a deadlock. Starvation happens when a thread may need to wait for a long time before a resource becomes available. Example: Read/Write Locks

Example of a Deadlock Assume two bank accounts protected with two mutexes int balance1 = 100; int balance2 = 20; mutex_t m1, m2; Transfer2_to_1(int amount) { mutex_lock(&m2); mutex_lock(&m1); balance2 - = amount; balance1 += amount; mutex_unlock(&m2); mutex_unlock(&m1); } Transfer1_to_2(int amount) { mutex_lock(&m1); mutex_lock(&m2); balance1 - = amount; balance2 += amount; mutex_unlock(&m1); mutex_unlock(&m2); }

Example of a Deadlock Thread 1 Thread 2 ---------------------------------------- ------------------------------------- Transfer1_to_2(int amount) { mutex_lock(&m1); context switch Transfer2_to_1(int amount) { mutex_lock(&m2); mutex_lock(&m1); block waiting for m1 mutex_lock(&m2); block waiting for m2

Example of a Deadlock Once a deadlock happens, the process becomes unresponsive. You have to kill it. Before killing get as much info as possible since this event usually is difficult to reproduce. Use gdb to attach the debugger to the processes to see where the deadlock happens. gdb progname <pid> gdb> threads //Lists all threads gdb> thread <thread number> //Switch to a thread gdb >where // Prints stack trace Do this for every thread. Then you can kill the process.

Deadlock A deadlock happens when there is a combination of instructions in time that causes resources and threads to wait for each other. You may need to run your program for a long time and stress-test them in order to find possible deadlocks Also you can increase the probability of a deadlock by running your program in a multi-processor (multi- core) machine. We need to prevent deadlocks to happen in the first place.

Graph Representation of Deadlocks Thread T1 is waiting for mutex M1 T1 M1 Thread T1 is holding mutex M1 T1 M1

Deadlock Representation T1 M2 T2 M1 Deadlock = Cycle in the graph.

Larger Deadlock T1 M2 T2 M3 M1 T3 T4 M4

Deadlock Prevention A deadlock is represented as a cycle in the graph. To prevent deadlocks we need to assign an order to the locks: m1, m2, m3 Notice in the previous graph that a cycle follows the ordering of the mutexes except at one point.

Deadlock Prevention Deadlock Prevention: When calling mutex_lock mi, lock the mutexes with lower order of I before the ones with higher order. If m1 and m3 have to be locked, lock m1 before locking m3. This will prevent deadlocks because this will force not to lock a higher mutex before a lower mutex breaking the cycle.

Lock Ordering => Deadlock Prevention Claim: By following the lock ordering deadlocks are prevented. Proof by contradiction Assume that the ordering was followed but we have a cycle. By following the cycle in the directed graph we will find mi before mj. Most of the time i< j but due to the nature of the cycle, at some point we will find i > j . This means that a tread locked mi before mj where i>j so it did not follow the ordering. This is a contradiction to our assumptions. Therefore, lock ordering prevents deadlock.

Preventing a Deadlock Rearranging the Bank code to prevent the deadlock, we make sure that the mutex_locks are locked in order. int balance1 = 100; int balance2 = 20; mutex_t m1, m2; Transfer2_to_1(int amount) { mutex_lock(&m1); mutex_lock(&m2); balance2 -= amount; balance1 += amount; mutex_unlock(&m2); mutex_unlock(&m1); } Transfer1_to_2(int amount) { mutex_lock(&m1); mutex_lock(&m2); balance1 -= amount; balance2 += amount; mutex_unlock(&m1); mutex_unlock(&m2); }

Preventing a Deadlock We can rewrite the Transfer function s more generically as: balance1 -= amount; balance2 += amount; mutex_unlock(&mutex[i] ); mutex_unlock(&mutex[j] ); } int balance[MAXACOUNTS]; mutex_t mutex[MAXACOUNTS]; Transfer_i_to_j(int i, int j, int amount) { if ( i< j) { mutex_lock(&mutex[i]); mutex_lock(&mutex[j]); } else { mutex_lock(&mutex[j]); mutex_lock(&mutex[i]); }

Ordering of Unlocking Since mutex_unlock does not force threads to wait, then the ordering of unlocking does not matter.

Clicker Question 1 (Read/Write Lock) Five threads are using one read/write lock to coordinate. Consider the following sequence of events: T1 tries to obtain read lock, T2 tries to obtain read lock, T3 tries to obtain write lock, T4 tries to obtain read lock, T5 tries to obtain write lock. Which threads are blocked at the end of the sequence? A. T2, T3, T4, T5 B. T3, T4, T5 C. T3, T5 D. T4, T5 E. T5

Clicker Question 2 (Read/Write Lock Implementation) We have T1 calls writeLock() T2 calls readLock() T3 calls readLock() What happens to T2 and T3 A. T2 blocked at 5; T3 at 5 B. T2 blocked at 5; T3 at 9 C. T2 blocked at 9; T3 at 5 D. T2 blocked at 9; T3 at 9 E. None of the above 1 void RWLock::writeLock() { 2 sem_wait( &_semAccess ); 3 } 4 void RWLock::readLock() { 5 mutex_Lock(&_mutex ); 6 _nreaders++; 7 if( _nreaders == 1 ) { 8 //First reader, get sem 9 sem_wait(&_semAccess); 10 } 11 mutex_unlock(&_mutex ); 12 }

Clicker Question 3 (Dead Lock) Which of the following combinations DO NOT lead to possible deadlocks? T1: 1 mutex_lock(&m1) 2 mutex_lock(&m2) 3 mutex_lock(&m3) T2: 4 mutex lock(&m3) 5 mutex lock(&m1) 6 mutex lock(&m4) T3 7 mutex lock(&m4) 8 mutex lock(&m1) 9 mutex lock(&m2) A. T1 and T2 B. T2 and T3 C. T1 and T3 D. T1 and T2 and T3 E. None of the above

Clicker Question 4 (Read/Write Lock Implementation) void RWLock::writeLock() { sem_wait( &_semAccess ); } void RWLock::writeUnlock() { sem_post( &_semAccess ); } void RWLock::readLock() { mutex_Lock(&_mutex ); _nreaders++; if( _nreaders == 1 ) sem_wait(&_semAccess); mutex_unlock(&_mutex ); } void RWLock::readUnlock() { mutex_lock(&_mutex ); _nreaders--; if( _nreaders == 0 ) sem_post(&_semAccess); mutex_unlock( &_mutex ); } Note that a call to readLock() may be blocked at sem_wait, while holding the mutex. A. This results in a dead lock with 1 active readers and 2 active writers at a time. B. This results in a dead lock with 2 readers. C. No dead lock, as writeLock does not need mutex. D. No dead lock, as writeUnlock does not need mutex. E. None of the above

Dining Philosophers Problem N Philosophers are in a round table. There is a fork in each side of a plate that they will use to it spaghetti. They need two forks to eat the spaghetti. Chopsticks may be a better example They will have to share the forks with their neighbors.

Dining Philosophers Problem Philosopher Spaghetti Fork

Dining Philosophers Problem Problem: They may all decide to grab the fork in their right at the same time and they will not be able to proceed. This is a deadlock

Dining Philosophers Problem Philosopher holds fork Philosopher waits for fork

Dining Philosophers Problem (Unfixed Version) const int NPHILOSOPHERS=10; mutex_t fork_mutex[NPHILOSOPHERS]; pthread_t threadid[NPHILOSOPHERS]; void eat_spaghetti_thread(int i) { while (i_am_hungry[i]) { mutex_lock(&fork_mutex[i]); mutex_lock(&fork_mutex[(i+1)%NPHILOSOPHERS); // Eat spaghetti chomp_chomp(i); mutex_unlock(&fork_mutex[i]); mutex_unlock(&fork_mutex[(i+1)%NPHILOSOPHERS); } }

Dining Philosophers Problem (Unfixed Version) main() { for (int i = 0; i < NPHILOSOPHERS; i++) { mutex_init(&_fork_mutex[i]); } for (int i = 0; i < NPHILOSOPHERS; i++) { pthread_create(&threadid[i],eat_spaghetti_thread, i, NULL); } // Wait until they are done eating for (int i = 0; i < NPHILOSOPHERS; i++) { pthread_join(&threadid[i]); } }

Dining Philosophers Problem (Fixed Version) Acquire the fork mutex in a particular order to prevent any deadlock.

Dining Philosophers Problem (Fixed Version) void eat_spaghetti_thread(int philosopherNum) { while (i_am_hungry[philosopherNum]) { int i = philosopherNum; int j = (philosopherNum+1)% NPHILOSOPHERS; if (i > j) { /*Swap i and j */ int tmp=i; i=j; j=tmp; } // Lock lower order mutex first mutex_lock(&fork_mutex[i]); mutex_lock(&fork_mutex[j]); // Eat spaghetti chomp_chomp(philosopherNum); mutex_unlock(&fork_mutex[i]); mutex_unlock(&fork_mutex[j]); } }

Other Solutions to Dinning Philosophers The global lock ordering solution avoids deadlock Requires a global ordering of philosophers/locks Limits parallelism. It is possible that only one philosopher is eating at any time. How? Ensures that at most N-1 philosophers can try to pick up forks E.g., using a semaphore with initial count N-1. Another way to avoid cycles. Requires a central semaphore. Same limitation of parallelism as the above. In worst case, only one is eating. Use a waiter: each philosopher needs to ask a waiter before picking up the forks (central coordination) The waiter can decide who should wait and who should eat Can achieve the best parallelism. When everyone wants to eat, how many philosophers can eat at the same time in the worst case?

Other Solutions to Dinning Philosophers Local ordering: an odd-numbered philosopher picks up left fork first; an even-numbered picks up right fork first Requires a global ordering of philosophers/locks. Better parallelism. When everyone wants to eat, how many philosophers can eat at the same time in the worst case? Random waiting: picks up left fork, and if right fork unavailable, put left fork down, wait a random time, try again Purely local solution, requires no global ordering of philosophers. Possible starvation. Unlucky philosopher may starve for a long time.

Review Questions What is a deadlock? How to prevent deadlocks by enforcing a global ordering of locks? Why this prevents deadlocks? Dinning Philosophers is not required for exams.