How to write deadlock free code?

Write an engineering article with a concrete timeline in Markdown format from the following transcript.

so Deadlocks are the worst that could happen when you're using threads but can we write a program that is deadlock free is there some kind of pattern that will ensure that a program never go into deadlock state in this video with Hands-On examples we will understand what Deadlocks are what happens when your program hits a deadlock and how to write deadlock free code so here I'm using a cloud-based IDE called replit to code this out because it is cloud-based I do not have to set up anything locally and I just need a browser to get started replit has an amazing llm assistant named Ghostwriter which is extremely powerful because it is vertically trained on programming and software development knowledge base and the best part is it spits out answers and suggestions in the context of the code that you are writing apart from this replit has something called as bounties which can help you make some money on the site as a bounty companies post paid projects on web applications AI tools Discord Bots and so much more you can pick the one that interests you complete it and get paid just sign up on replied with my link in the description down below once you sign up on the home page itself you can see a section called bounties when you click on explode you can see the projects that are listed there and the amount of money you can make out of that pick the one that interests you apply for it and just get started so the link for the sign up is in the description down below go through that sign up for my link and this to be honest is a great way to make some money on the site doing what you love so do check that out so now let's head back to the video so the most common side effect of multi-thread programs are deadlock let's understand it with a very simple example let's say we have three threads T1 T2 T3 each thread wants two resources to move forward and it wants exclusive lock on them which means that let's say T1 helps the lock on R1 but wants lock on R2 T2 helps the lockout R2 what's the lock on R3 T3 helps the lock on R3 but wants a lock on R1 now this is a classic case where you can see a very nice circular dependency being formed and none of the thread could proceed because everyone is waiting on other thread to release the lock this is where your program enters the deadlock State what happens when a program hits a Deadlock your program hangs and there is no you know elegant way or a graceful way to come out of it so which is why Deadlocks are deadly and you if you are riding a multi-thread program you have to ensure that the program never ever enters a deadlock set because if it enters a red lock State you would have to either kill the thread kill the process reboot the system and what not to get out of it so in real world two very common examples and we will look at them in depth but just to uh give you a high brief of it that databases ensures that it never enters a deadlock side now just imagine a database which obviously is multi-threaded it handles so much of traffic in parallel leverages or the course needs threads to do it and if a transaction has locked a particular row and is dependent on another row which is locked by some other transition there is a circular dependency being formed the database entering into a deadlock State there is no way for you to get out of it which means either you kill one of the existing transaction leads to povert user experience or you reboot the resource you reboot your entire database right either way it's not a good experience and it would lead to a production outage similar case would happen when you're using web servers because your web servers are multi-threaded there is a chance of Deadlock there so your web servers ensure that they never go in a deadlock state plus you're the business only that you are writing as part of your API logic that also if you are leveraging multiple threads due to any reason ensure that it never enters a deadlock state because everyone loves stable softwares although boring but yeah like no one loves thrill in production right so can we simulate deadlock locally it should not be difficult because at that it just requires threads and you can mimic a lot of stuff there so what do we do is we would try to mimic uh deadlock locally and what we will see is what happens when a program enters a deadlock and then we try to fix it we will try to write a deadlock free code so to mimic this locally what we do is we create six threads right and we would try to acquire lock on three records so imagine this is a database six threads are six transactions that are trying to acquire lock on three records which is three rows and when they try to acquire a lock on three rows let's say they are trying to Upward lock in random order depending on the SQL query that is fired it could be in some particular case but let's assume we do it in underwater because identity care of simulating the deadlock and not like actually replicating it so here what our logic would be is are threads would constantly try to acquire lock on any two of these items will sleep for a couple of seconds mimicking like some kind of processing right and then they would release the lock right now here because we have six threads which are trying to acquire lock onto records it is possible that a deadlock is formed for example if you look at this diagram here you can see how a deadlock is getting formed right and we would want to see what happens when a program hits the deadlock so let's take an example let's take a practical Hands-On example to understand how to you know solve this or how to what see to see what happens when your program enters a deadlock so here I am using replet uh as you may see because wise thing why basically set up things locally so here this is a simple C program in which what we are doing is we are spinning up threads I'll start walking through on what we are doing so that we understand what would happen when we when our program hits a Deadlock so here we are mimicking three records and six connections six connections simply six transactions there is a struct which mimics a record data having three attributes like imagine it being name L sorry it three integer so ID age and something else then let's say you have your uh struct in which you are storing record data and a log welcome to that now what what we would want to do is when we are initing or when we are starting our execution is sure our main starts over here we see the random function we initialize database add some dummy values into that but the idea is that what we want is we want to simulate 6 transactions so for I equal to 0 is less than num con I plus plus I am spinning up a transient I am just I'm just creating a string so that I can show it in a beautiful way but I am the decor ideas I am just creating a thread which would execute this function mimic load and as this particular transaction so 0 is a one is B and 2 is C something like that then what we are doing is this mimic load function will take a look at it but the idea is that when my threads are running I would wait for all the threads to complete and then I am destroying my mutexes now let me look at what mimic load does now what memory Cloud does it is imagine it's a connection or that is constantly trying to acquire lock on two random items so here I invoke random function twice record one record two and I would just if record what is same as recorded because we want two distinct records on which we can take lock so I'm just acquiring two records at random if they are same we would just continue but it's just a simulation right so here at this stage we would have two records that this transaction has picked up not yet acquired the log which are distinct and then we acquire the lock on the records Rec 1 and rec2 on this corresponding transaction so we are passing transaction name as an argument here we are passing transaction name as an argument sorry not here mimic load transaction null and here we are busier this is the argument that we are passing which is TX cell and this argument will be accepted over here which is a cad start and we are just using it to print it right so what acquire log does is what we have is for each of the record here you can see for each of the record we have a record data in which we can store the three attributes that we just described ID let's say ID age and class name or class number you could have strings and what not here but along with that for each record we have a mutex right that is this logged or not right so what our acquire log function would do is it would say that hey this transaction is acquiring a lock on this particular record so that's what you do p thread mutex lock DB of records of record ID so for that record I've been working a log function I'm locking that particular thing in this for this particular thread right and release simply just unlocks that particular stuff right that's what we are doing so here the idea is we take two distinct random records and then we acquire the lock on first record acquire the lock on second record it would move forward only when both of the acquirations are successful otherwise it would wait and then sleep for two seconds it's basically mimicking some kind of processing some kind of compute and then we are releasing the lock release lock record 2 and release lock record one and then we sleep and this is an infinite Loop that is continuously running imagine it's like continuously trying to occur the two log process on that release the lock and so on and so forth right now when we try to run this program let's see what happens when I try to run this we see some print statements happening you see transition have acquired lock on record one transaction app one stock wire lock on record two record two and so on and so forth but now if we look carefully our program is not moving forward it printed a bunch of statement but the program is not moving forward why because the program entered a Deadlock that if you plot a dependency graph of these of these logs you would see that there would be a cyclic dependency that is formed because of which your program is your program has entered a deadlock State and the program is not moving forward this is what happens if your database enters a deadlock state right so I'll stop this execution because now we have to fix it but now we understand why our program would enter a deadlock and how and what would happen if your program enters a deadlock right so now let's take a step to see how we could fix it to fix a red lock you can very clearly see there is a circular dependency which you have to break what are the possible ways to break it you kill one of the thread and break a circular dependency that's the easiest one now which one to break you can pick the oldest one you can pick the newest one you can pick the one which is least busy pick the one which is most busy depending on multiple strategies pick one that works for you or just pick one at random and kill it right and there's no one way to do it to be honest uh depending on the system that you are building or system that you are using they would pick one over other because depends on what suits them right the second thing is screw it let me restart the process if threads are causing it let me restart the process if multiple threads or multiple processes are in deadlock you restart your system the idea is you do restart so that the circular dependency now literally does not exist right two common ways of handling network but yeah you pick the one that you write in right now this is about when you entered a deadlock and then you are fixing it other ways to do it can we do better what if we prevent a deadlock from happening now most Real World Systems they cannot afford to enter a deadlock State because they cannot afford that your program suddenly stops working let's say imagine your database suddenly stopped working imagine a web server suddenly stopped working Real World Systems would want that their program no matter what no matter how extreme the situation is no matter how rare the use case is the program should never enter a deadlock state so is there a way to prevent a Deadlock so few examples this is this is where what you do is before acquiring the lock your most of your real world systems they check the resource allocation graph what we just saw that dependency thing that's a resource allocation graph that which resource is allocated to which thread so what happens is whenever any thread or any process or any Entertainer system has acquired a lock on something else it maintains a global resource allocation graph for it and before acquiration it checks that hey if I take this will there be a circular dependency that is forming so this is deadlock detection that is not really detection but rather this is deadlock avoidance that is continuously running right so here you are preventing the deadlock from happening by checking every time before you acquire the lock that hey if I acquire this lock will it form a circular dependency or not that's the core idea most real world databases do this for example in MySQL if you try to mimic exclusive if you take exclusive locks on rows and try to mimic this deadlock you would see that the second transaction when it tries to acquire the log and your database as your database it sees that if I give this transaction lock on this particular row my database will enter into a deadlock set it would stop it would kill the transaction the idea being that your debt lock is prevented it's not avoided it's prevented that your deadlock good your system could have gone into a deadlock state but you are preventing it because before acquiring the lock you are always checking that hey would it result in a deadlock or not and most level systems prefer this but there's other way what if you avoid you completely avoid a deadlock that no matter like there is no need of maintaining resource allocation graph there is no need of checking cyclic dependence every time is there a way for you to write a code that will avoid the deadlock total and which is how you write a deadlock free code I'll take I'll show you one of the examples to do it another example is really interesting thinking on the first principles the program enters into deadlock State because of a cyclic dependency that is formed right and the cyclic dependencies formed because let's say I take example of two threads and two resources threat T1 has the lock on T1 wants lock on T2 T2 has the lock on sorry T2 has the lock on R2 once the lock on R1 right now because of this out of order acquiration you see this depend you see this deadlock condition or this deadlock situation being happening why because if they would have like if there was no way for your thread T2 to have acquired block on R2 then your program would have never entered into a deadlock state so that's the idea so what if there is a total order in your system what is total ordering that if a thread wants to acquire a lock on two resources what if there is a total order in which it would need to acquire the law so for example let's say the total ordering that we do is is numerically sorted R1 R2 R3 R4 so if let's say thread T1 wants to acquire a lock on resource R1 and R2 it will have to acquire log in the same order R1 and R2 if T2 won't stop at the lock on R2 and R1 say no that's total order T2 would have to acquire log on R1 and then R2 so you are imposing a total order in your system where your threads would have to acquire the lock in a certain order and this will help you avoid the deadlock how come because for example in this case the situation where T1 and T2 acquiring the like cross acquiring the lock would never happen why because T1 will also acquire lock on First on R1 then on R2 T2 will also try to acquire log on First on R1 then on R2 so if out of T1 and T2 any one of them let's say T1 has acquired a lock on R1 T2 would not be able to move forward because it is acquiring the lock on R1 then on R2 this is the importance of total ordering that in this situation your T2 will have to wait until your T1 res like your T1 releases the log that it took on R1 why because there is a total order imposition that has just happened this is how you avoid a Deadlock right and this total order that you are of that you are imposing ensures that the acquiration is happening in order which means that there is no way it is possible for your system to go like for your T2 thread to acquire lock on R2 and then on R1 so R2 will always be free for T1 Docker because T1 has acquired lock on R1 this total order imposition is one of the ways not the only way one of the ways to avoid a Deadlock now let's see a quick demonstration of this if we take this exact same example that we did we just add one condition to it we go back to the screen now here in the transaction or in the mimic node function when we had this infinite Loop trying to acquire lock on randomly picking record 1 and record two here there is no total order now here it is possible that your record one and record two could be R2 and then R1 in some cases R1 and R2 because we are randomly picking so what if we impose total order something like this what if we say that if record one is less if record 1 is greater than record 2 we swap it and we swap it so we say that swap the records if record 1 is greater than record two this means that by any chance if it was R2 and R1 it would be swapped with R1 R2 this is imposition of total order in your system and now if we run it we would see that our program never stops or never hangs it would continuously be moving forward no matter what happens because in case there is one of the thread who has acquired a lock on summon there is in one order only the locks can be acquired on the resources right this way what would happen is that there is never going to be a case where someone else has acquired low on some other thing and then won't stop a lock on something else that's never going to happen and this is one when it's not that every system can afford to put or impose a total order in their system for example in case of database transition it is really difficult but wherever possible if you can impose a total order of acquiration that would be the best way to write deadlock free code and this is one of the ways there are many ways to do it is one of the ways to do it and this is pretty fascinating and look how easy it is to build a deeper understanding right and this is how you write a deadlock free code right one of the ways to write deadlock free code and yeah this is all what I wanted to cover in this one I hope you found it interesting and I would highly highly highly recommend you to just code it it's not difficult and by the way it's not just C specific you could pick literally any language to do it you just need mutexes to mimic this but once you get a deeper understanding on why it is working how it is doing you'll understand what database must be doing internally right and this is not what most database do but you you will start framing the ideas around it right so this is one of the ways to write deadlock free code I'll cover punch more in future videos but yeah I hope you found it interesting hope you found it amusing that's it for this one I'll see in the next one thanks [Music] [Music] thank you

Here's the video ⤵