17_Deadlock

1 .Lecture 17 – Deadlock and Starvation Define the terms deadlock , livelock and starvation Give an example that causes deadlock List the four conditions that are necessary for deadlock to occur Given a problem description, draw a resource allocation graph Given a resource allocation graph, determine if a system is in deadlock Describe the four methods of dealing with deadlock Describe the Banker’s Algorithm for avoiding deadlock with multiple shared resources Identify whether a given state is safe or unsafe according to the Banker’s Algorithm Learning Goals © Paul Davies, C. Antonio Sanchez. Not to be copied, used, or revised without explicit written permission from the copyright owner.

2 .Deadlock and Starvation 2

3 .Access to Multiple Resources So far, we have mainly discussed protecting access to a single critical section or resource at a time. However, in many cases we will need protected access to multiple resources simultaneously to complete an action. Deadlock and Starvation 3 Bank Account A balance: $1000 Bank Account B balance: $500 Transfer $500 Simple approach: lock account A lock account B check if sufficient funds transfer cash money unlock account B unlock account A Complete transfer such that all money is accounted for at all times, as seen by an outside process or thread.

4 .Access to Multiple Resources Deadlock and Starvation 4 When handling problem that requires access to multiple resources Need to acquire and hold multiple locks Locks are normally acquired in one order, released in the opposite (last locked – first unlocked) Problems with this approach? Bank Account A balance: $1000 Bank Account B balance: $500 Transfer $500 Transfer $200

5 .Access to Multiple Resources Deadlock and Starvation 5 Bank Account A balance: $1000 Bank Account B balance: $500 Transfer $500 Transfer $200 struct Account { double balance; std::mutex mutex; void lock() { mutex.lock(); } void unlock() { mutex.unlock(); } }; void transfer( double amount, Account& a, Account& b) { a.lock(); b.lock(); a.balance -= amount; b.balance += amount; b.unlock(); a.unlock(); } transfer( 500 , Me, You); transfer( 200 , You, Me); Me.lock(); You.lock(); You.lock(); Me.lock(); acq. acq. wait wait Both threads are stuck waiting for each other. They will wait forever. DEADLOCK!!

6 .Deadlock in Databases Deadlock and Starvation 6 Process A if (…) { … confirm bookings … } Process B if (…) { … confirm bookings … } Process A is blocked by B Process B is blocked by A Process A acquires ‘Hotel’ Process B acquires ‘Flight’ Hotel.Lock() Flight.Lock() Flight.Lock() Hotel.Lock() In databases, a process may have to lock several records to prevent them being changed by other processes while a decision on whether to update the data is performed, e.g. holding a Hotel and Flight reservations simultaneously. If process A locks record r1 and process B locks record r2 , and then each process tries to lock the record the other has locked, again we have deadlock.

7 .Deadlock Deadlock: when two or more threads/processes are stuck in a pattern of waiting for each other, with no one progressing. Deadlock and Starvation 7 Conditions for deadlock: Mutual exclusion: only one process (or set #) can access the resources No pre-emption: the resources must be released voluntarily (i.e. cannot be forcibly taken away) Hold and wait: at least one process is holding on to a resource while waiting for another resource to become available Circular wait: there exists a circular pattern of wait dependencies at the moment of deadlock. E.g. A waits for B waits for C waits for A

8 .Resource Allocation Graph We can try to detect when a deadlock is about to occur using a resource allocation graph : Deadlock and Starvation 8 R 1 R 3 R 4 R 2 P 1 P 2 P 3 Resources drawn as a box Dots indicate number available Circles represent processes Arrow from process to resource indicates request Arrow from resource dot to process indicates assignment

9 .Deadlock and Starvation 9 Resource Allocation Graph R 1 R 3 R 4 R 2 P 1 P 2 P 3 cycle If graph contains no cycles  no deadlock If graph contains a cycle if there is only one instance per resource  deadlock if one or more resources has several instances  possible deadlock P1  R1  P2  R2 DEADLOCK!!

10 .Deadlock and Starvation 10 Resource Allocation Graph R 1 R 3 R 4 R 2 P 1 P 2 P 3 cycle No Deadlock  R 1 R 3 R 4 R 2 P 1 P 2 P 3

11 .The Dining Philosophers Problem Deadlock and Starvation 11 A group of 6 philosophers are sitting around a dining table containing 6 bowls of rice and 6 chopsticks. Each philosopher alternates between eating and thinking. They have access to two chopsticks: one on their left, and one on their right. To eat, the philosopher needs to pick up two chopsticks one-at-a-time. To think, they put down the chopsticks one-at-a-time. How should they proceed?

12 .The Dining Philosophers Problem If all pick up left chopstick at the same time then wait for the right-one, they are stuck in deadlock . If all philosophers decide to put the left chopstick down if they cannot pick up the right-one, could lead to livelock . Both cases lead to starvation . Deadlock and Starvation 12 Starvation: thread is unable to acquire a resource so does not progress Deadlock: threads are stuck in a wait pattern, leads to starvation. Livelock: threads are continuously performing actions but unable to progress, leads to starvation.

13 .The Dining Philosophers Problem Possible solutions: Drop left chopstick if can’t pick up right… wait a random amount of time before trying again. could still potentially lead to livelock, or at least multiple collisions, but probability is vanishingly small (tends to 0 very quickly) Remove the circular dependency by making one philosopher start with the right chopstick. lock ordering : assign each resource a unique ID, always lock in order of increasing IDs. Deadlock and Starvation 13

14 .The Dining Philosophers Problem Deadlock and Starvation 14 1 6 5 4 3 2 Solution 2: lock ordering Number chopsticks Each philosopher starts picking up lowest numbered chopstick, then the higher one Philosophers release chopsticks in opposite order R 2 R 4 R 3 R 1 P 1 P 2 P 3 P 4 P 5 P 6 R 5 R 6 Either: P6 doesn’t have R1, P6—R6 broken P6 does have R1, P1—R2 broken

15 .The Dining Philosophers Problem Deadlock and Starvation 15 R 2 R 4 R 3 R 1 P 1 P 2 P 3 P 4 P 5 P 6 R 5 R 6 1 6 5 4 3 2 Solution 2: lock ordering Number chopsticks Each philosopher starts picking up lowest numbered chopstick, then the opposite one Philosophers release chopsticks in opposite order Either: P6 doesn’t have R1, P6—R6 broken P6 does have R1, P1—R2 broken

16 .Dealing with Deadlocks In general, there are four solutions: Ignorance: ignore the problem altogether. Avoidance: anticipate the deadlock and avoid it by carefully allocating the resources during program design. Detection and Recovery: acknowledge that deadlocks can occur outside of your control. Detect when they happen and take action to recover. Prevention: employ resource allocation algorithms at run-time to make sure that the system never gets into a situation where deadlock can arise. Deadlock and Starvation 16

17 .Dealing with Deadlocks: Ignorance Also called the ostrich algorithm “bury your head in the sand like an Ostrich and pretend it isn’t happening”. Not as crazy as it sounds. If deadlock is only expected to occur once every three months, is fixed by a reboot, and not catastrophic, maybe it’s acceptable. Fixing it may impose too many restrictions or performance penalties. E.g. Windows, Unix. Deadlock and Starvation 17 Deadlock – What Deadlock?

18 .Dealing with Deadlocks: Avoidance Deadlock and Starvation 18 Avoid by using careful design. Solution 1: voluntarily relinquishing resources when we cannot acquire all e.g. dining philosophers drop chopsticks and pause before retrying Solution 2: strict ordering of resource acquisitions e.g. one dining philosopher reverses pickup order Solution 3: treating multiple resources as one single resource e.g. each dining philosopher grabs all chopsticks at once

19 .Dealing with Deadlocks: Avoidance Deadlock and Starvation 19 Solution 1: voluntarily relinquishing resources when we cannot acquire all Try to acquire resources with a timeout. If timeout elapses, release those acquired and try again. struct Account { int account_id; double balance; std::timed_mutex mutex; void lock() { mutex.lock(); } template < typename T> bool try_lock_for(T time) { return mutex.try_lock_for<T>(time); } void unlock() { mutex.unlock(); } }; void transfer( double amount, Account& a, Account& b){ auto timeout = std::chrono::milliseconds( 1000 ); // keep trying until we succeed bool acquired = false ; while (!acquired) { a.lock(); if (b.try_lock_for(timeout)) { // timed try acquired = true ; break ; } a.unlock(); // release and try again std::this_thread::sleep_for(timeout); } a.balance -= amount; b.balance += amount; b.unlock(); a.unlock(); }

20 .Dealing with Deadlocks: Avoidance Deadlock and Starvation 20 Solution 1: voluntarily relinquishing resources when we cannot acquire all Try to acquire resources with a timeout. If timeout elapses, release those acquired and try again. Advantages: easy to implement, doesn’t require too much design or communication with team members. Disadvantages: not very efficient, possible starvation. Once the thread gives up resources, there’s no guarantee it can get any of them back. Often used in networking, where servers and webpages can become temporarily unavailable.

21 .Dealing with Deadlocks: Avoidance Deadlock and Starvation 21 Solution 2: acquire multiple resources using strict ordering. struct Account { int id; double balance; std::mutex mutex; void lock() { mutex.lock(); } void unlock() { mutex.unlock(); } }; void transfer( double amount, Account& a, Account& b) { // order resources by id Account* first = &a; Account* second = &b; if (a.id > b.id) { first = &b; second = &a; } first->lock(); second->lock(); first->balance -= amount; second->balance += amount; second->unlock(); first->unlock(); } transfer( 500 , Me, You); transfer( 200 , You, Me); Me.lock(); You.lock(); You.lock(); Me.lock(); acq. wait acq. Second thread waits until first is completed. Deadlock avoided 

22 .Dealing with Deadlocks: Avoidance Deadlock and Starvation 22 Solution 2: acquire multiple resources using strict ordering Number or sort the resource locks in a unique order, always acquire in that sorted order. This eliminates any potential cycles in the resource allocation graph. Advantages: threads hold on to resources already acquired, more efficient. Disadvantages: requires all designers of each process to agree on the order, establish a convention. Can get pretty complicated. Most real systems use avoidance by resource ordering.

23 .Dealing with Deadlocks: Avoidance Deadlock and Starvation 23 Solution 3: treat multiple resources as one Anything that may need to be acquired simultaneously must all belong to same amalgamated resource. struct Account { double balance; static std::mutex mutex; static void lock_all() { mutex.lock(); } static void unlock_all() { mutex.unlock(); } }; void transfer( double amount, Account& a, Account& b) { Account::lock_all(); a.balance -= amount; b.balance += amount; Account::unlock_all(); }

24 .Dealing with Deadlocks: Avoidance Deadlock and Starvation 24 Solution 3: treat multiple resources as one Anything that may need to be acquired simultaneously must all belong to same amalgamated resource. Advantages: easy to implement, good for relatively simple problems with few resources. Disadvantages: no process can ever be allowed to acquire a subset of resources using a separate mutex. Leads to inefficiencies, waiting for resources that may not be used at all by a thread/process.

25 .Dealing with Deadlocks: Detection and Recovery Deadlock and Starvation 25 Allow deadlock to occur, use the operating system to break it. OS maintains a directed graph such as the resource allocation graph , recording processes and allocated resources Every time a resources is requested, check the graph or circular dependency loops Recover using one of the following strategies: Pre-emption: steal a resource from another thread Roll-back: cause a thread to roll back to a previous state Kill: terminate a thread or process, potentially losing information

26 .Dealing with Deadlocks: Detection and Recovery Deadlock and Starvation 26 Pre-emption: the OS may be able to forcibly take back a resource from a process and give it to another, breaking the circular dependency list. Issues: could introduce race conditions, since resources may be in some partially modified state (which is why there were multiple locks in the first place) resource may not return in the same state as when taken away To fix these, we often need to trigger the process/thread which relinquishes the resource to roll-back to its state before the resource was acquired.

27 .Dealing with Deadlocks: Detection and Recovery Deadlock and Starvation 27 Roll-back: a program saves checkpoints or snapshots of its state before trying to acquire a resource. If deadlock occurs, the operating system triggers the process to rewind to its previous state and then try to acquire the resources again in the future. Often used in database systems and e-commerce applications. Challenge: rolling back my require undoing many transactions which were already recorded as successful. Can be quite a complex procedure to undo multiple distributed transactions.

28 .Dealing with Deadlocks: Detection and Recovery Deadlock and Starvation 28 Killing: asking the OS to forcibly terminate a thread or process. If a process/thread can’t resume from a previous state, it may be better to force it to close and restart from scratch. This will release all its current resources to break the circular dependency graph. The victim should be carefully chosen so that other processes can continue. The killed process should also not leave the system in some partially changed state, and restarting it should not cause any adverse affects.

29 .Dealing with Deadlocks: Prevention In avoidance, the onus was on the programming to design the system to avoid deadlocks altogether. Prevention relies on algorithms at run time to prevent deadlock from occurring. Dijkstra’s Banker’s Algorithm: based on how a bank manager might deal with customer credits and loans. Processes declare up-front the number and type of each resource they intend to request. The OS will deny a process access to a resource, even if the resource is available, if at some time in the future it coult lead to a circular dependency list. Deadlock and Starvation 29