Deadlock 1: Conditions For Deadlock

deadlock is a problematic situation in computer science in which multiple processes are unable to get any work done because each one is trying to gain control of a resource that another process is holding when this happens none of the processes are able to do anything they simply block and your program typically freezes so a typical example of this is the following here we have two separate processes a and B and each of them need to lock a mutex m and another mutex in before they can perform their critical section now this example uses mutexes but in general we could be claiming any resource it could be file it could be memory resources it could be semaphores in general it could be anything so we're claiming resources with the lock commands and then releasing them with the unlock commands now both processes have to have both resources before they can do their critical section unfortunately they gain their resources in different orders process a locks M and then n whereas process B locks N and then M this opens up the possibility of deadlock what can happen is that this process progresses through this line of code meaning that mutex M has been locked then process B goes through this line of code meaning that mutex n has been locked at this point we have deadlock because an attempt by either of these processes to continue forward will cause them to block if process a tries to lock mutex n then this process will block because N has already been locked by process be similarly if process be tries to lock mutex em well that's also already been claimed so it will block and now both of these processes are blocked each of them is holding on to a mutex lock and nothing will ever change execution will not continue a helpful visual aid for understanding this kind of problem is a resource allocation graph in a resource allocation graph we represent processes using circles so we have process a in a circle and process B in a circle and we represent resources with squares so M and n are resources so we'll have resource m and resource n now in general some resources can have multiple units available in our particular problem there's simply one mutex m and one mutex n but if we're talking about memory or other types of resources there could be multiple instances of a resource available each individual instance of a resource is depicted with a dot inside of the resource square now given these four points we can show the situation that's occurring here that has led to deadlock we will draw arrows between these circles and squares to create a graph so the circles and squares are actually vertices in a graph and we'll be drawing directed edges so at the point when process a locks m we say that a has successfully claimed the resource M and therefore we draw an arrow from this dot to the process and so when we have an arrow from a dot within a resource to a process it represents that this process is holding this resource then process B claims resource n so we draw an arrow from n to P B and we can also draw arrows to represent resource requests so if an arrow goes from a process to a resource it means that the process has requested that resource but it can't claim it yet so here process a requests resource n meaning it we draw an arrow from the circle the process to the box the resource now we can't claim it because there's no available dots to claim similarly process B requests resource M so we draw this and the result is a cycle in this graph so a cycle in a directed graph is when if you follow the arrows you end up getting back to where you started so this is known as a circular weight and this shows that we have deadlock now in general there are three conditions that create the possibility of deadlock and then a fourth condition that means you have experienced deadlock so the three conditions that make deadlock possible in a given system are the following first is mutual exclusion meaning that we have some aspect of the code that can only be executed by one process at a time so these locks provide mutual exclusion because once process B has locked n no other process that needs to lock in can continue until process B unlocks that mutex so we need mutual exclusion another condition that is required is a lack of preemption now preemption is when a resource is taken away from a process even though it's not finished using it so we don't allow that in this system once you lock a mutex you get to hold it until you unlock it so this process is responsible for unlocking the mutex when it is finished with it preemption would be if process a came along and said hey I'm taking it away from you you don't get to have it anymore in general we don't allow preemption because allowing it in a way that doesn't break programs is complicated and difficult and so it is common to not allow it but it is one step in the sequence that makes deadlock possible the other condition that creates the possibility of deadlock is known as hold and wait and in these processes once you lock a mutex you hold it until you are done with it and it doesn't matter whether you are actively executing code or not so process a will lock mutex m and hold on to it until it gets through all of this code and unlocks it this is true even if the process blocks forever because it cannot get resource in so it's holding onto this resource it's going to wait until it has all the resources it needs to execute this code and so it's waiting while holding on to that resource so if you have these three aspects in your system or in your code it's possible that deadlock can arise now it could be that you execute this code and it runs fine just by coincidence in the example I showed we executed up to this point in process a and then pause and then went up to this point and process B and that's why deadlock occurred it could be that that never happens it could be that process a locks m and then n so quickly that it's able to get through its critical section and move on and that never coincides with process be locking N and M however that's a pretty bad argument because in a live system you don't want sudden unexpected deadlock to occur out of nowhere and these bugs can be particularly hard to catch if you're not using good programming principles now you know that deadlock has actually occurred when this fourth special condition comes along and this is circular wait so this is the scenario depicted in this resource allocation graph where not only is it possible for deadlock to occur but the worst sequence of lock requests has occurred such that we get this circular white scenario and your programs are now deadlock so we'll be discussing ways of combating this in future videos

Channel: Jacob Schrum

Views: 10,634

Rating: 5 out of 5

Keywords: deadlock, resource allocation graph, mutex, concurrency, mutual exclusion, preemption, hold and wait, circular wait, graph, directed graph, cycle, process, thread

Id: vmSKp0PExRY

Length: 10min 49sec (649 seconds)

Published: Thu Aug 04 2016