I have 20 years of development and still watching that kind of videos from time to time. Mostly to see how things are explained. Yet, I realized that one of my software is not accounting for starvation of the slowest processes! And the even funnier thing is that I did implement process priority...So, one process can flag itself as being high priority to be guaranteed the next slot. And now that I think about it...I in fact inadvertently did indeed allow slower process to not be starved as they can enter in the queue while the fast process is executing. And this is why watching entry level CS video IS still a good thing even for seniors ^^ Not only learning how to explain things, but also small reminder to think about some cases that can be overlooked.
Just wanted to drop a comment to say that this was such an elegant and well thought out explanation. I really liked how you started from first principles and built your way to the solution. Cheers! :)
@@SpanningTree Hey, what if one program sees that the signal from the other is off so it turns on its signal and enters but at the same time the other program sees that the first signal was off as well so it turns on its signal and enters too? You need to check twice. First before you decide to turn on your signal and then after you turned on your signal.
This is exactly how you explain a concept. Not only do you show very beautifully designed visuals, but you actually start from scratch. Like you pretend you also dont know the concept and we are almost ‘learning’ together in a way. Anyway, just came across your channel very recently and just kept watching one video after another. Hope to see you back soon
@@geekzombie8795 When one thread does a certain thing and that triggers the other thread to do the opposite thing and that turns the first thread to correct that by doing that first thing again and so on.
Wow... This channel seems to do a great job at explaining computer science concepts, the animations are great and really helpful 🫡. Thank you for the great job ✌️.
You are doing amazing job here......try to explain more algorithms in this same way I am sure your work will be recognized by everyone soon....Good luck:)
I am programming two robots that need to enter a shared space but only one at a time and ended up implementing something like that but with a hard priority where the first indicator forbids the second. Very nice presentation!
Yes, me too. The illustration by Spanning Tree is marvelous. Great job! But the concept of Dekker's Algorithm's solution is way too simple as we experienced on the road, day in day out. I guess it should contains some other situation in more complex competition way. Otherwise, I wonder how this simple idea can serve as an important algorithm. Most of the programmers, from junior to expert, can "derive" out a similar algorithm when they face such situation. 😅 Anyway, just raise my naïve question, I am not a hater at all .....
I dunno where your videos were all this time but I'm glad I found your channel. Very nice eli5 examples on algorithms and computer science problems. Love it
I thought the solution would be using locks. But I can see now that it may prevent slow process to use it as much as needed, thanks to your explanation. Great videos!
Great video. Thank you very much sir. I remember having trouble understanding these concepts when I was learning Operating Systems course during my Bachelor’s.
Test and Set instruction.... it works.... the big problem is when programmers or groups of programmers don't program said accessing test of the critical section and then at a customer site they bring up a second cpu and..... well use Dijkstra's P and V semaphore.... time??? Quantum clock... make sure the "critical section" is short and sweat...
Brilliant explanation. One of the best explanations I have seen on RUclips. A few minutes of video saves you from reading and trying to understand something for about an hour.
In the 60's IBM had a hardware instruction, compare and swap CS, that ran as a single CPU instruction. It took 3 inputs, a, b, and c. It would compare b to a and if they were equal it replaced A with C. The condition code was the result of the compare. In your program you read A into B and C, added 1 to C, did the CAS, if condition code was equal continue on, If it was not loop back to the start. Easy on a single CPU system. I looked at the Z POPs and by magic it works in a multiprocessor environment.
THANK YOU ! I UNDERSTOOD THIS MORE THAN THE SCRIPT! Just joking! I read something about mutual exclusion and then watched your video. It really helped me more!! THANK YOU!
Awesome videos! I'm sad to see you stopped producing them, but I have a feeling that you got hired for a good paying job! Congratulations and thank you for sharing this knowledge freely on the internet with great illustrations!
The most familiar example of race conditions would be online shopping. If you have 3 units of a certain thing, but thousands of people around the country adding 1 to their cart, there is a problem with people getting an error at checkout, or even with order fulfillment.
All well and good if you only have 2 programs accessing the data. Doesn't work if extrapolated to 3 or more though as could still deadlock if multiple programs wanted to access the data simultaneously but the turn indicator was set to a different program. Of course if we simply swap the turn indicator for a priority queue system having the program go to the back of the queue after accessing the data and have programs turn off their indicator when a program higher in the priority queue has its indicator set we have a more scalable model that acts in an equivalent manner for 2 programs.
Suppose the event is as of the following sequence: time=0 : A sees that B’s signal is off time=1 : A turns on his signal and proceed with critical section time=0.5 : B checks for A’s signal(signal is off) and turns on his signal Conflict! In such manner, both A & B are following the algorithm to signal before approaching the critical section, but they are both unaware of each other's signal due to the time difference. How do we resolve this?
I think a nice extra touch could be actually turning off the lights and letting the sings glow for a cycle. It would visually show the limited view a robot has compared to the full view we humans are used to. Obviously this is a great explanation already, no need to change it, I thought it might be a useful idea for future videos.
Hmmm, this might be a nice visual narration of an algorithm, but it glosses over the fact that the turn indicator and lights are themselves shared resources that can give rise to race conditions (eg between check the other light is off and entering the light goes on). They all need their own protections. I guess the thing at the bottom of this is that the lowest level thing has to be atomic and therefore impossible to pre-empt. That bit didn't get mentioned.
You missed something though, *before* we check for the other program's light we turn on our own. So, in the condition you stated our program enters the critical zone and does its thing. The other program having seen that our signal light is on will never enter the critical zone until we are finished and flip our own light off. This is the exception as to why we signal first and then check the other program's signal. If we did it the other way this could break the program.
@@solsystem1342 thanks for that focus on that detail. I've just watched the video again ... and I'm almost convinced. I don't have the headspace at the moment to think fully about it but I have to concede that I'm no longer as sure about my original statement.
Nice animation for this! My only puzzle is that the an important aspect, the waiting process, is thrown in with no explanation. How would the waiting be done?
Depends on the use case - if your shared resource is a bit of shared memory, then it probably makes sense to simply check the signal light every X ticks (in assembly you could add NOP commands here: en.wikipedia.org/wiki/NOP_(code) ). If your resource is something like a USB controller or an internet port, then you should probably instead check every X seconds. In which case you'll want to do a sleep system call en.wikipedia.org/wiki/Sleep_(system_call) so you don't hog the CPU. This tells your OS to basically "start another thread, and then start me up again in about X seconds".
@3:33 - Maybe a problem with Dekker's algorithm? If right bot is already in the critical zone, because no one else had an indicator on, but the turn arrow was set to left bot... the right bot would already be in the zone when the left bot turns on his indicator. The left bot sees that right indicator is on, so it consults the turn arrow. The turn arrow is already pointing to left bot. Now left bot thinks it is clear to enter critical zone. But right bot is already inside. This happened because the left bot came late. Your visual example assumed they push indicators at the same time. What happens when order is different? Is this why planes crash?
In LIFE, Dekker's Algorithm is analogous to fundamental principles of COOPERATION. The two signal light buttons are each person's WILL (intent to do something) and the turn indicator toggle switch is that person's RIGHT (of way) to do what they WILL to do. Therefore, if we live by these rules of cooperation, then we will ONLY DO something if we have the WILL to do it AND the RIGHT to do it. This ensures EFFICIENT SHARING OF RESOURCES!
Why can't the second program to access the shared value take advantage of the fact that the first program has already loaded it into a register? If it knows that the value it needs is in a register and will be written back to memory soon, then why does it wait for the write and then read it to a register all over again? Great explanation, thanks for the video!
Better solution sounds like: If turn indicator indicates your turn, turn on your wait indicator but ignore all other signal lights. Go do shared write. Now move the turn indicator away from you (to a random process that has a light if any, or any random process otherwise). Turn off your waiting light if it is on (just to be thorough) and finish. If turn indicator is not toward you, then turn on your "waiting" indicator light. If turn is pointed to someone with waiting indicator light on, block until it's your turn. If it's turned toward any off-light, forcibly take the turn indicator then proceed as above. Fewer steps, faster convergence, less redundancy. Both deadlock and dual-write should still be impossible, and slow process starving should never happen.
I don't think that works. Concurrency is tricky. For example: Turn indicator: process A Both waiting lights: off Process B checks the turn indicator Process B turns on their waiting light Process B checks the A's waiting light Process A checks the turn indicator Process B takes the turn indicator Process A turns on their waiting light Process A does the shared write / Process B does the shared write
couldn’t there still be a race condition if there is latency between turning on the signal and the effect being visible for the other program? i believe there are several ways that could happen on modern hardware, for example if it initially only writes to the core local cache and has a delay before syncing with the main memory or similarly reading from local cache even worse if your cpu has out of order execution so i guess what i’m thinking is that maybe you don’t need special hardware, but you do need your hardware to not be too special or at least a way to temporarily disable those optimizations
A single threaded application is unlikely to deadlock since whatever process is setting the flags or locks is the only thing running (in that context). But multiprocessing with multiple CPU's could still deadlock. What you need (IMO) is a variable holdoff and try again; the same algorithm is used in CSMACD, ethernet in other words. Sensing a collision because of timing characteristics, all interfaces hold off but with a randomized holdoff period. Which interface is lucky with the shorter holdoff will start transmitting and the other interfaces on the bus will see the transmission and be inhibited. An implementation is to check for lock; seeing none, set the lock to myself. But it is possible that the other process running exactly concurrently also sets a lock; the very thing that concurrency control is supposed to eliminate. But it isn't the SAME lock; it is the "lights" in this example. So you come back for a second look to see if you have *exclusive* access to the lock. If not, wait a random milliseconds, check again. It is possible for the pseudorandom generator for the holdoff to be in sync; both processes end up holding off exactly the same time. So you have a counter and after ten or so failures to get lock, exit the process with a deadlock error. Now it creates opportunity for human intervention "try again" which most assurely won't be identical for both processes since you are interacting with only one of them at a time anyway.
Usually such hardware has dedicated instructions to make sure all other cores/threads/programs see the same thing at the same time. In fact, a lot of the time that hardware has dedicated instructions that do this entire algorithm behind the scenes.
@@bluesillybeard oh, so this algorithm is still used internally? that's interesting! but yeah, those dedicated instructions is exactly what i was thinking of regarding "needing a way to compensate for your hardware being too special"
What about the turn indicator? It is being modified by both? If there are more than 2 writers, turn indicator will need to be protected just like the critical section.
Let's say I have a function whom create a file 'results' and then save some data in it. If I'm using multithreading, there is a risk that both thread will stop at the same time and then try to create the same file at the same time, and my program will crash => Racing condition So I need to implement some sort of control method to avoid two or more thread to try to save data and create said file 'result' at the same time. import os, threading def create_interruptors(index): #This function purpose is to initialize my signals (The light signal that turns yellow in the video, by default they're "OFF" => False) interruptors = {} for i in range(index): # by default they're "OFF" => False interruptors['thread '+str(i)] = False return interruptors def do_some_task(thread_index,turn): #For example create a file if a given condition is fulfilled boolean1 = True if boolean1: #If condition is satisfied, then the algorithm will try to do some task. So first off, turn your signal "ON" interruptors['thread '+str(thread_index)] = True #Get all the interruptors that are "ON" on_interruptors = len([v for k,v in interruptors.items() if v==True]) #If multiple interruptors are on at the same time, check who's turn is it if on_interruptors >1: #Is is my turn ? If yes, then do task if turn==thread_index: os.mkdir('Results') #If I did the action then it's no longer my turn, so pass your turn now. turn +=1 print('thread '+str(thread_index)) #If that's the last thread's turn, then go back to the first thread if turn > len(interruptors): turn = 0 #Once task is done, don't forget to turn "OFF" your signal interruptors['thread '+str(thread_index)] = False def multithreading(): nb_threads = 15 interruptors = create_interruptors threads = [] turn = 0 signaling = {} for thread_index in range(nb_threads): thread = threading.Thread(target=do_some_task,args=(thread_index,turn)) thread.start() threads.append(thread) for thread in threads: thread.join() Try to run this program, Normally it should crash because 15 threads are trying to create the file 'Result' at the same time, but because we used Dekker's algorithm to control threads and prevent race condition we get to run this program bug free. You can apply this concept to any task really
I assume that if there are more than two processes then a ring system of turn taking would need to be implemented? Or otherwise what cases would this solution be used for?
I guess you could turn the turn indicator into a ranking. Whenever more than one light is on, all but the highest ranked process turn their lights off. And after leaving the critical section you move yourself to the very bottom of the ranking.
Ok, I have a thought. In the way that you described the process, (or maybe I misunderstood), all this logic is kind of redundant and has the same effect of simple letting one access then and only then the other so on and so forth in times of mutual access requests. The additional conditional logic does nothing except grant one program the ability to access the critical area repeatedly until the other want's it concurrently, and, if they both want it, fall back to givin access to one then the other and repeat. Wouldn't it be much simpler to simply assign an priority pointer? If program A is granted access, the pointer points to program B. if B is granted access, the pointer points to program A. The priority is just a priority, not a queue. It means that A can still get access even if the priority pointer is pointing to B, as long as B is not requesting access, in which case the access is given to B and the priority pointer now points to A. This have the same affect, but much simpler.
You still need some way for the programs to signal to each other that they are accessing the data. For instance if A has priority and so is granted access, what's stopping B from going into the critical section at the same time? If the pointer is just for priority and so doesn't actually stop any program from entering the critical section, then there's nothing actually stopping B from entering when A is already there. So, you have to set up some booleans to indicate when A or B is in the critical section, and a program cannot enter while another program has their boolean set to 'true'. These are the lights in the animation.
in the final solution, do you need to turn off your own light if they're both on, or couldn't you leave your light on, and simply revert back to only obying the 'turn indicator'? Presumably the one who finishes would flip the turn indicator and turn his light off. The other program doesn't have to waste time turning its light back on, in can just go when it sees the other light off.
Why not just have a 3rd program, that receives intents from both other programs and add them to a queue, and 3rd program executes intents on the queue 1 by 1 until the queue is empty and waits for a new intent to come in to execute. Only 3rd program is allowed to edit resource.
Why does the bot need to turn of their signal light when we already have a switch to display who's turn it is? Is it because, when both signal lights are on, the bot wouldn’t be able to flip the switch for some reason?
@@jeffreygordon7194 What scenario do you see that creates a race condition. The closest I see are these two, but they are solved by Dekker's algorithm. You have two robots, A and B. Each robot will turn on their signal light first, and check the other signal light second, always in that order. Case 1: Both robots act at the same time. A and B turn on signals. A and B see other signal on, and check turn, etc. No deadlock. Case 2: A turns on signal. A sees B signal is off. B turns on signal. B sees A signal is on, waits. A already saw B signal off and enters critical section. No race occurred. A will turn off signal after critical section, then B can enter.
Or perhaps have code constantly checking each program one side at a time. If one program needs access, let the program do it’s actions then have the program tell when it’s done with the actions before letting the code check the other program. If the code does not see the program needing to do an action, it goes an checks the other program and repeats the process.
I generally described concurrency control in computer programs with stoplight analogies or stop sign or yield signs or other forms of traffic primitives. Curious if anyone has any issues with these types of ideas for if I might be misleading people?
Interesting! I have several questions related to "what if there's more than 2 programs"? How does this algorithm change? I assume each program gets its own light, has to check *all* lights before continuing, and the turn indicator should cycle through each program. But what happens if A and B want to use the resource, but it's C's turn? Is each program obligated to check in every now and then to advance the turn indicator to resolve any deadlocks among the other players even if it doesn't want to access the resource, or is there a more clever solution? Also, are there practical situations where the number of participants might not be known? Must there always be someone (the operating system I guess) keeping track of a master roster of participants, or can this system work with no guest list, and just a bunch of polite gatecrashers?
I'm not a programmer still a suggestion...instead of having that leaver only 2 positions it should have a third neutral position in the middle. Whoever wants to access the critical data will pull that leaver to his side and after access keep it to neutral. Will it work?
Pointer is to program B. program A needs to write to the data, but is waiting for program B's light to turn off and for the pointer to move to A. After B's light turns of, the pointer switches to A. But as A is going to turn its own light on, B turn its light on again right before. B sees that A's light isn't on yet and then goes to access the data. A then turn its light on, sees that B's light is on, but since the pointer is on A, it goes to access the data while B is still there. Is that a thing that could happen with Dekker's or am I missing something?
this wouldn't really work with 3 programs though right? because of the turn indicator? what if it's neither program's turn? a thought i had was to attach a time stamp to the intent to enter, and say the can't enter unless there are no other intents to enter *with an earlier time* on.
why can't there be a 3rd program that listens for signals? It would place the signals in a list and then respond first to whoever has priority if simultaneity occurred. Priority could be random or set to a side or even an arrow like in the video
Wouldn't a simpler solution just be a queue line? If both or more programs arrived at the queue line at the same time, you could just choose the order at random, then have them all alternate turns from then on by moving a program back to the start of the queue line if it still needs more access, and only letting another program in as one leaves the access zone, until they don't need access anymore, then the one could just keep going through the queue line over and over by itself without having to wait.
You're kinda making up new rules here. How do you maintain the queue if you can't increment an integer atomically? How do you negotiate a random choice between two parallel programs? I'd say the video is somewhat at fault for not properly explaining the constraints of the problem. Based on the integer example at the beginning I'm assuming that atomic loads and stores are possible, but not other operations like increment or swap, and that the atomic operations have a globally well-defined order of execution. None of this is a given.
I think you could replace the turn indicator with a ranking for the processes. It is then "your turn" when noone above you in the ranking has their light on. And after leaving the critical area you put yourself at the very bottom of the ranking.
Why does the program with the arrow pointing away from it has to turn off its light? Couldn't the program with the arrow pointing toward just ignore the states of the lights?
I have 20 years of development and still watching that kind of videos from time to time. Mostly to see how things are explained.
Yet, I realized that one of my software is not accounting for starvation of the slowest processes! And the even funnier thing is that I did implement process priority...So, one process can flag itself as being high priority to be guaranteed the next slot. And now that I think about it...I in fact inadvertently did indeed allow slower process to not be starved as they can enter in the queue while the fast process is executing.
And this is why watching entry level CS video IS still a good thing even for seniors ^^ Not only learning how to explain things, but also small reminder to think about some cases that can be overlooked.
well also the majority of developers even experienced ones are terrible when it comes to security even when it comes to issues within a thread
Just wanted to drop a comment to say that this was such an elegant and well thought out explanation. I really liked how you started from first principles and built your way to the solution. Cheers! :)
Glad you enjoyed it!
That's the *difference between programming and coding.*
@@SpanningTree
Hey, what if one program sees that the signal from the other is off so it turns on its signal and enters but at the same time the other program sees that the first signal was off as well so it turns on its signal and enters too?
You need to check twice. First before you decide to turn on your signal and then after you turned on your signal.
This is exactly how you explain a concept. Not only do you show very beautifully designed visuals, but you actually start from scratch. Like you pretend you also dont know the concept and we are almost ‘learning’ together in a way.
Anyway, just came across your channel very recently and just kept watching one video after another. Hope to see you back soon
Great Explanation
I've never seen two programs that adorable.
This is no doubt the best explanation of Dekker's algorithm I have ever seen. Amazing work !!!
Mann....I really felt bad for those cute bots when they were stuck in a deadlock.😭😭😭
A livelock is more exhausting though.
@@geekzombie8795 When one thread does a certain thing and that triggers the other thread to do the opposite thing and that turns the first thread to correct that by doing that first thing again and so on.
We learned 2 concepts in this video. Thank you so much.
I am a software engineer who did not graduated from CS. Your videos are great!
Amazing explanation. I liked the part towards the end where you go over the subtleties of what makes the algorithm good
Wow... This channel seems to do a great job at explaining computer science concepts, the animations are great and really helpful 🫡. Thank you for the great job ✌️.
Love the explanations and animations! Great work on cs50 AI too
Super clear explanation, your video really helped me understand the Critical Section better, thank you!
You are doing amazing job here......try to explain more algorithms in this same way I am sure your work will be recognized by everyone soon....Good luck:)
I am programming two robots that need to enter a shared space but only one at a time and ended up implementing something like that but with a hard priority where the first indicator forbids the second. Very nice presentation!
Well this is a much more coherent explanation than my old professor, thanks!
I just discovered this channel. Brilliant instructions with brilliant graphics. Thanks for all.
Yes, me too. The illustration by Spanning Tree is marvelous. Great job! But the concept of Dekker's Algorithm's solution is way too simple as we experienced on the road, day in day out. I guess it should contains some other situation in more complex competition way. Otherwise, I wonder how this simple idea can serve as an important algorithm. Most of the programmers, from junior to expert, can "derive" out a similar algorithm when they face such situation. 😅 Anyway, just raise my naïve question, I am not a hater at all .....
I dunno where your videos were all this time but I'm glad I found your channel. Very nice eli5 examples on algorithms and computer science problems. Love it
I thought the solution would be using locks.
But I can see now that it may prevent slow process to use it as much as needed, thanks to your explanation.
Great videos!
The best explanation ever! I swear youtube is better than these lectures
This video deserves much more views. You got a new sub.
Literally had a program suffer from race conditions and this video really helped me fix it
Great video. Thank you very much sir.
I remember having trouble understanding these concepts when I was learning Operating Systems course during my Bachelor’s.
the best channel on youtube
Very thanks for the great lesson, very simple and straight to the point.
how can someone come here and actually dislike this excellent content?....... amazing work bro!🔥
Mad Max's algorithm: Two bots enter, one bot leaves...
This is what efficiently conveying an idea means.!
Developer, Take a bow !
i had no idea this could be resolved without atomic operations, wonderful explanation
I wish there were videos like this for finance and business
Absolutely brilliant explanation! 😃💯💥👍💫
Test and Set instruction.... it works.... the big problem is when programmers or groups of programmers don't program said accessing test of the critical section and then at a customer site they bring up a second cpu and..... well use Dijkstra's P and V semaphore.... time??? Quantum clock... make sure the "critical section" is short and sweat...
Thanks, this was very explanatory, I will be back from time to time.
Brilliant explanation. One of the best explanations I have seen on RUclips. A few minutes of video saves you from reading and trying to understand something for about an hour.
These are very well made and easy to understand. Good stuff!
This is Amazing...if only you could cover everything it would helps millions around the world
In the 60's IBM had a hardware instruction, compare and swap CS, that ran as a single CPU instruction. It took 3 inputs, a, b, and c. It would compare b to a and if they were equal it replaced A with C. The condition code was the result of the compare. In your program you read A into B and C, added 1 to C, did the CAS, if condition code was equal continue on, If it was not loop back to the start.
Easy on a single CPU system. I looked at the Z POPs and by magic it works in a multiprocessor environment.
What a great explanation! loved it and understood it!
THANK YOU ! I UNDERSTOOD THIS MORE THAN THE SCRIPT!
Just joking!
I read something about mutual exclusion and then watched your video.
It really helped me more!!
THANK YOU!
an amazing way to explain some ways to code
this video deserve more views
Awesome videos! I'm sad to see you stopped producing them, but I have a feeling that you got hired for a good paying job! Congratulations and thank you for sharing this knowledge freely on the internet with great illustrations!
Can be scaled too.
Just add more lights and a turn indicator with more positions to accommodate more programs.
The video is secretly teaching us how to count from 1 to 10.
The most familiar example of race conditions would be online shopping. If you have 3 units of a certain thing, but thousands of people around the country adding 1 to their cart, there is a problem with people getting an error at checkout, or even with order fulfillment.
All well and good if you only have 2 programs accessing the data. Doesn't work if extrapolated to 3 or more though as could still deadlock if multiple programs wanted to access the data simultaneously but the turn indicator was set to a different program.
Of course if we simply swap the turn indicator for a priority queue system having the program go to the back of the queue after accessing the data and have programs turn off their indicator when a program higher in the priority queue has its indicator set we have a more scalable model that acts in an equivalent manner for 2 programs.
Excellent explanation!
Excellent content, thanks for making this.
it's cool how involved a solution is to a very simple issue
Suppose the event is as of the following sequence:
time=0 : A sees that B’s signal is off
time=1 : A turns on his signal and proceed with critical section
time=0.5 : B checks for A’s signal(signal is off) and turns on his signal
Conflict!
In such manner, both A & B are following the algorithm to signal before approaching the critical section, but they are both unaware of each other's signal due to the time difference. How do we resolve this?
this was greatly presented! Cheers
I think a nice extra touch could be actually turning off the lights and letting the sings glow for a cycle.
It would visually show the limited view a robot has compared to the full view we humans are used to.
Obviously this is a great explanation already, no need to change it, I thought it might be a useful idea for future videos.
Very good explanation and nice animations!
Very intuitive...thank you!
Great video! It was so useful!
Hmmm, this might be a nice visual narration of an algorithm, but it glosses over the fact that the turn indicator and lights are themselves shared resources that can give rise to race conditions (eg between check the other light is off and entering the light goes on). They all need their own protections. I guess the thing at the bottom of this is that the lowest level thing has to be atomic and therefore impossible to pre-empt. That bit didn't get mentioned.
You missed something though, *before* we check for the other program's light we turn on our own. So, in the condition you stated our program enters the critical zone and does its thing. The other program having seen that our signal light is on will never enter the critical zone until we are finished and flip our own light off.
This is the exception as to why we signal first and then check the other program's signal. If we did it the other way this could break the program.
@@solsystem1342 thanks for that focus on that detail. I've just watched the video again ... and I'm almost convinced. I don't have the headspace at the moment to think fully about it but I have to concede that I'm no longer as sure about my original statement.
Nice animation for this! My only puzzle is that the an important aspect, the waiting process, is thrown in with no explanation. How would the waiting be done?
Depends on the use case - if your shared resource is a bit of shared memory, then it probably makes sense to simply check the signal light every X ticks (in assembly you could add NOP commands here: en.wikipedia.org/wiki/NOP_(code) ). If your resource is something like a USB controller or an internet port, then you should probably instead check every X seconds. In which case you'll want to do a sleep system call en.wikipedia.org/wiki/Sleep_(system_call) so you don't hog the CPU. This tells your OS to basically "start another thread, and then start me up again in about X seconds".
Amazing Explanation
Thank you. please also explain peterson solution
@3:33 - Maybe a problem with Dekker's algorithm?
If right bot is already in the critical zone, because no one else had an indicator on, but the turn arrow was set to left bot... the right bot would already be in the zone when the left bot turns on his indicator. The left bot sees that right indicator is on, so it consults the turn arrow. The turn arrow is already pointing to left bot. Now left bot thinks it is clear to enter critical zone. But right bot is already inside. This happened because the left bot came late. Your visual example assumed they push indicators at the same time. What happens when order is different? Is this why planes crash?
Great and simple explanation :)
Thank you for the very clear explanation.
The little bots are cute and they show the operations very well 🙂
In LIFE, Dekker's Algorithm is analogous to fundamental principles of COOPERATION. The two signal light buttons are each person's WILL (intent to do something) and the turn indicator toggle switch is that person's RIGHT (of way) to do what they WILL to do. Therefore, if we live by these rules of cooperation, then we will ONLY DO something if we have the WILL to do it AND the RIGHT to do it. This ensures EFFICIENT SHARING OF RESOURCES!
Why can't the second program to access the shared value take advantage of the fact that the first program has already loaded it into a register? If it knows that the value it needs is in a register and will be written back to memory soon, then why does it wait for the write and then read it to a register all over again?
Great explanation, thanks for the video!
Cool video! What do you use to make the animations by the way? They remind me of three.js renders
Better solution sounds like:
If turn indicator indicates your turn, turn on your wait indicator but ignore all other signal lights. Go do shared write. Now move the turn indicator away from you (to a random process that has a light if any, or any random process otherwise). Turn off your waiting light if it is on (just to be thorough) and finish.
If turn indicator is not toward you, then turn on your "waiting" indicator light. If turn is pointed to someone with waiting indicator light on, block until it's your turn. If it's turned toward any off-light, forcibly take the turn indicator then proceed as above.
Fewer steps, faster convergence, less redundancy. Both deadlock and dual-write should still be impossible, and slow process starving should never happen.
I don't think that works. Concurrency is tricky. For example:
Turn indicator: process A
Both waiting lights: off
Process B checks the turn indicator
Process B turns on their waiting light
Process B checks the A's waiting light
Process A checks the turn indicator
Process B takes the turn indicator
Process A turns on their waiting light
Process A does the shared write / Process B does the shared write
That's a fantastic explanation thanks for creating this.
couldn’t there still be a race condition if there is latency between turning on the signal and the effect being visible for the other program? i believe there are several ways that could happen on modern hardware, for example if it initially only writes to the core local cache and has a delay before syncing with the main memory or similarly reading from local cache
even worse if your cpu has out of order execution
so i guess what i’m thinking is that maybe you don’t need special hardware, but you do need your hardware to not be too special or at least a way to temporarily disable those optimizations
A single threaded application is unlikely to deadlock since whatever process is setting the flags or locks is the only thing running (in that context). But multiprocessing with multiple CPU's could still deadlock. What you need (IMO) is a variable holdoff and try again; the same algorithm is used in CSMACD, ethernet in other words. Sensing a collision because of timing characteristics, all interfaces hold off but with a randomized holdoff period. Which interface is lucky with the shorter holdoff will start transmitting and the other interfaces on the bus will see the transmission and be inhibited.
An implementation is to check for lock; seeing none, set the lock to myself. But it is possible that the other process running exactly concurrently also sets a lock; the very thing that concurrency control is supposed to eliminate. But it isn't the SAME lock; it is the "lights" in this example. So you come back for a second look to see if you have *exclusive* access to the lock. If not, wait a random milliseconds, check again.
It is possible for the pseudorandom generator for the holdoff to be in sync; both processes end up holding off exactly the same time. So you have a counter and after ten or so failures to get lock, exit the process with a deadlock error. Now it creates opportunity for human intervention "try again" which most assurely won't be identical for both processes since you are interacting with only one of them at a time anyway.
Usually such hardware has dedicated instructions to make sure all other cores/threads/programs see the same thing at the same time.
In fact, a lot of the time that hardware has dedicated instructions that do this entire algorithm behind the scenes.
@@bluesillybeard oh, so this algorithm is still used internally? that's interesting! but yeah, those dedicated instructions is exactly what i was thinking of regarding "needing a way to compensate for your hardware being too special"
Great video!
Great Video!!!
What about the turn indicator? It is being modified by both? If there are more than 2 writers, turn indicator will need to be protected just like the critical section.
Exactly my thoughts!
It is already protected because it can be changed only by process that was allowed to access the critical section.
Let's say I have a function whom create a file 'results' and then save some data in it.
If I'm using multithreading, there is a risk that both thread will stop at the same time and then try to create the same file at the same time, and my program will crash => Racing condition
So I need to implement some sort of control method to avoid two or more thread to try to save data and create said file 'result' at the same time.
import os, threading
def create_interruptors(index):
#This function purpose is to initialize my signals (The light signal that turns yellow in the video, by default they're "OFF" => False)
interruptors = {}
for i in range(index):
# by default they're "OFF" => False
interruptors['thread '+str(i)] = False
return interruptors
def do_some_task(thread_index,turn):
#For example create a file if a given condition is fulfilled
boolean1 = True
if boolean1:
#If condition is satisfied, then the algorithm will try to do some task. So first off, turn your signal "ON"
interruptors['thread '+str(thread_index)] = True
#Get all the interruptors that are "ON"
on_interruptors = len([v for k,v in interruptors.items() if v==True])
#If multiple interruptors are on at the same time, check who's turn is it
if on_interruptors >1:
#Is is my turn ? If yes, then do task
if turn==thread_index:
os.mkdir('Results')
#If I did the action then it's no longer my turn, so pass your turn now.
turn +=1
print('thread '+str(thread_index))
#If that's the last thread's turn, then go back to the first thread
if turn > len(interruptors):
turn = 0
#Once task is done, don't forget to turn "OFF" your signal
interruptors['thread '+str(thread_index)] = False
def multithreading():
nb_threads = 15
interruptors = create_interruptors
threads = []
turn = 0
signaling = {}
for thread_index in range(nb_threads):
thread = threading.Thread(target=do_some_task,args=(thread_index,turn))
thread.start()
threads.append(thread)
for thread in threads:
thread.join()
Try to run this program,
Normally it should crash because 15 threads are trying to create the file 'Result' at the same time, but because we used Dekker's algorithm to control threads and prevent race condition we get to run this program bug free. You can apply this concept to any task really
If you use python you should just use a mutex, which uses exactly the same algorithm, just at a lower level.
best video on this topic
I assume that if there are more than two processes then a ring system of turn taking would need to be implemented? Or otherwise what cases would this solution be used for?
I guess you could turn the turn indicator into a ranking. Whenever more than one light is on, all but the highest ranked process turn their lights off. And after leaving the critical section you move yourself to the very bottom of the ranking.
Ok, I have a thought. In the way that you described the process, (or maybe I misunderstood), all this logic is kind of redundant and has the same effect of simple letting one access then and only then the other so on and so forth in times of mutual access requests. The additional conditional logic does nothing except grant one program the ability to access the critical area repeatedly until the other want's it concurrently, and, if they both want it, fall back to givin access to one then the other and repeat.
Wouldn't it be much simpler to simply assign an priority pointer? If program A is granted access, the pointer points to program B. if B is granted access, the pointer points to program A. The priority is just a priority, not a queue. It means that A can still get access even if the priority pointer is pointing to B, as long as B is not requesting access, in which case the access is given to B and the priority pointer now points to A. This have the same affect, but much simpler.
You still need some way for the programs to signal to each other that they are accessing the data. For instance if A has priority and so is granted access, what's stopping B from going into the critical section at the same time? If the pointer is just for priority and so doesn't actually stop any program from entering the critical section, then there's nothing actually stopping B from entering when A is already there.
So, you have to set up some booleans to indicate when A or B is in the critical section, and a program cannot enter while another program has their boolean set to 'true'. These are the lights in the animation.
in the final solution, do you need to turn off your own light if they're both on, or couldn't you leave your light on, and simply revert back to only obying the 'turn indicator'? Presumably the one who finishes would flip the turn indicator and turn his light off. The other program doesn't have to waste time turning its light back on, in can just go when it sees the other light off.
Amazing vid!
Why not just have a 3rd program, that receives intents from both other programs and add them to a queue, and 3rd program executes intents on the queue 1 by 1 until the queue is empty and waits for a new intent to come in to execute. Only 3rd program is allowed to edit resource.
Why does the bot need to turn of their signal light when we already have a switch to display who's turn it is? Is it because, when both signal lights are on, the bot wouldn’t be able to flip the switch for some reason?
how do you avoid the potential non-atomicity of setting your signal light and checking if the other signal light is on?
Yes. It seems like you've just moved your race condition from an integer to a boolean. I fail to see how this solves the issue.
@@jeffreygordon7194 What scenario do you see that creates a race condition. The closest I see are these two, but they are solved by Dekker's algorithm.
You have two robots, A and B. Each robot will turn on their signal light first, and check the other signal light second, always in that order.
Case 1: Both robots act at the same time. A and B turn on signals. A and B see other signal on, and check turn, etc. No deadlock.
Case 2: A turns on signal. A sees B signal is off. B turns on signal. B sees A signal is on, waits. A already saw B signal off and enters critical section. No race occurred. A will turn off signal after critical section, then B can enter.
Or perhaps have code constantly checking each program one side at a time. If one program needs access, let the program do it’s actions then have the program tell when it’s done with the actions before letting the code check the other program. If the code does not see the program needing to do an action, it goes an checks the other program and repeats the process.
This requires a third program. If there is a fault in the third program both of the other two would wait forever.
I generally described concurrency control in computer programs with stoplight analogies or stop sign or yield signs or other forms of traffic primitives. Curious if anyone has any issues with these types of ideas for if I might be misleading people?
excellent bro
Now understood what those yellow lights and Indicator were meant to be in the application code, I was doing code review recently.
GREAT VIDEO!
Interesting! I have several questions related to "what if there's more than 2 programs"? How does this algorithm change? I assume each program gets its own light, has to check *all* lights before continuing, and the turn indicator should cycle through each program. But what happens if A and B want to use the resource, but it's C's turn? Is each program obligated to check in every now and then to advance the turn indicator to resolve any deadlocks among the other players even if it doesn't want to access the resource, or is there a more clever solution?
Also, are there practical situations where the number of participants might not be known? Must there always be someone (the operating system I guess) keeping track of a master roster of participants, or can this system work with no guest list, and just a bunch of polite gatecrashers?
I'm not a programmer still a suggestion...instead of having that leaver only 2 positions it should have a third neutral position in the middle. Whoever wants to access the critical data will pull that leaver to his side and after access keep it to neutral.
Will it work?
Pointer is to program B. program A needs to write to the data, but is waiting for program B's light to turn off and for the pointer to move to A. After B's light turns of, the pointer switches to A. But as A is going to turn its own light on, B turn its light on again right before. B sees that A's light isn't on yet and then goes to access the data. A then turn its light on, sees that B's light is on, but since the pointer is on A, it goes to access the data while B is still there.
Is that a thing that could happen with Dekker's or am I missing something?
this wouldn't really work with 3 programs though right? because of the turn indicator? what if it's neither program's turn? a thought i had was to attach a time stamp to the intent to enter, and say the can't enter unless there are no other intents to enter *with an earlier time* on.
easy way to understand something that would have likely confused me, thanks
why can't there be a 3rd program that listens for signals? It would place the signals in a list and then respond first to whoever has priority if simultaneity occurred. Priority could be random or set to a side or even an arrow like in the video
I thank you so much, I understood you way better than my teacher and he speaks my native language!! haha Best regards :)
Wouldn't a simpler solution just be a queue line? If both or more programs arrived at the queue line at the same time, you could just choose the order at random, then have them all alternate turns from then on by moving a program back to the start of the queue line if it still needs more access, and only letting another program in as one leaves the access zone, until they don't need access anymore, then the one could just keep going through the queue line over and over by itself without having to wait.
I don't know if that's simpler, but it's certainly another way to solve it!
You're kinda making up new rules here. How do you maintain the queue if you can't increment an integer atomically? How do you negotiate a random choice between two parallel programs?
I'd say the video is somewhat at fault for not properly explaining the constraints of the problem. Based on the integer example at the beginning I'm assuming that atomic loads and stores are possible, but not other operations like increment or swap, and that the atomic operations have a globally well-defined order of execution. None of this is a given.
Wouldn't the turn indicator be another shared piece of data? Why does race conditions do not occur over it?
what would happen if the turn indicator was on a third program, and both programs 1 and 2 turned their light on?
I think you could replace the turn indicator with a ranking for the processes. It is then "your turn" when noone above you in the ranking has their light on. And after leaving the critical area you put yourself at the very bottom of the ranking.
Cool. How does expand to 3+?
Can you make a video about semaphores?
love this explanation and the cute robots:3
Why does the program with the arrow pointing away from it has to turn off its light?
Couldn't the program with the arrow pointing toward just ignore the states of the lights?
Why make the conditions for entering the critical section more complicated than "is the other signal light on"?
No, because if the light is on it can mean that the other program is already inside.
@@DajesOfficial You're right, thanks !
I really clicked on this to find out if it was a video about breeding or about running but I am happy I did it because it was really interesting.
I just love these videos.
How do you implement that in programs