Race Conditions and How to Prevent Them - A Look at Dekker's Algorithm
Vložit
- čas přidán 12. 06. 2024
- When two programs both need access to some shared data, how do we ensure that they don’t try to manipulate the data at the same time? This is the mutual exclusion problem, and it’s often solved with hardware. But even without any special hardware, Dekker’s Algorithm offers a way to ensure that programs can only access the shared data one at a time. Here, we take a visual look at Dekker’s Algorithm: what’s the intuition behind it? How does it work? And why does it prevent race conditions?
0:00 Mutual Exclusion
2:24 Signaling
4:05 Dekker’s Algorithm
***
Spanning Tree is an educational video series about computer science and mathematics. See more at spanningtree.me
To be notified when a new video is released, sign up for the Spanning Tree mailing list at spanningtree.substack.com/
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at brian@spanningtree.me to suggest a future topic.
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! :)
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.
Mann....I really felt bad for those cute bots when they were stuck in a deadlock.😭😭😭
A livelock is more exhausting though.
@@ouwebrood497 what’s a livelock?
@@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.
Hello Brian, I am a Junior Student in CS major. I'm struggle a lot in university but your lectures inspire me a lot and help me keep going, especially CS50w. Hope you continue these great contents and get more success in the future.
How are you doing now, still doing CS?
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 !!!
Amazing explanation. I liked the part towards the end where you go over the subtleties of what makes the algorithm good
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:)
Love the explanations and animations! Great work on cs50 AI too
Well this is a much more coherent explanation than my old professor, thanks!
Very thanks for the great lesson, very simple and straight to the point.
the best channel on youtube
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 wish there were videos like this for finance and business
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!
The video is secretly teaching us how to count from 1 to 10.
These are very well made and easy to understand. Good stuff!
This is what efficiently conveying an idea means.!
Developer, Take a bow !
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 .....
This video deserves much more views. You got a new sub.
What a great explanation! loved it and understood 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
Literally had a program suffer from race conditions and this video really helped me fix it
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!
Excellent content, thanks for making this.
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.
i had no idea this could be resolved without atomic operations, wonderful explanation
This is Amazing...if only you could cover everything it would helps millions around the world
Absolutely brilliant explanation! 😃💯💥👍💫
Very good explanation and nice animations!
Great and simple explanation :)
Great video! It was so useful!
That's a fantastic explanation thanks for creating this.
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.
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
Very intuitive...thank you!
this video deserve more views
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.
this was greatly presented! Cheers
Excellent explanation!
how can someone come here and actually dislike this excellent content?....... amazing work bro!🔥
Amazing Explanation
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.
Brilliant explanation. One of the best explanations I have seen on CZcams. A few minutes of video saves you from reading and trying to understand something for about an hour.
it's cool how involved a solution is to a very simple issue
Great Video!!!
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".
best video on this topic
Thank you. please also explain peterson solution
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...
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"
Amazing vid!
I thank you so much, I understood you way better than my teacher and he speaks my native language!! haha Best regards :)
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.
GREAT VIDEO!
Can be scaled too.
Just add more lights and a turn indicator with more positions to accommodate more programs.
excelente muchas gracias
Thank you for the very clear explanation.
The little bots are cute and they show the operations very well 🙂
love this explanation and the cute robots:3
I just love these videos.
excellent bro
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
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.
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.
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 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.
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.
Amazing!!
You are a true Hero
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!
oh my god! this was amazing!
easy way to understand something that would have likely confused me, thanks
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!
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.
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.
What about lag in receiving information? Both could look at the light at exactly the same time, but due to network speed, see the light is off and then both switch their light on without knowing the other is on. Would we need another check of the light, shortly before we want to manipulate the data?
I think the order is reversed: first you turn your light on and then you check if the other process has their light on. If the processes are connected over a network you are right that there is a chance lag will create an issue like you describe.
One solutions I can think of is to check the other light's timestamp and ensure the information you're receiving is from after your light was turned on. If both processes do this then it is impossible for lag to be an issue. What should you do about a timeout? Well, that's another issue entirely.
Another thing you can do is centralize the process of acting on the shared resource. You do this by making a third process which accepts commands from over the network. In the example of incrementing a number, if the third process receives two increment commands it does not matter which comes first. This does not work if the order of commands is significant, in that case you can attach timestamps to the commands and replay commands on the shared resource in the proper order.
What happens if a read happens between a fast command with a late timestamp and a slow command with an early timestamp?
Well.......leave me the hell alone. :P
Without the context of this being a computer related video, "race condition" meant a whole other thing to me
I'd have gone with a slight tweak: "if both signal lights are on, if the turn indicator is ours, we have access: do the thing we want, flip the turn indicator, and turn off signal." The last two can be in either order, as the program that had priority has already left the critical area, so either indication that its the other program's turn will work.
I agree, this seems simpler to me, there’s less backtracking to “turn off my signal if it’s not my turn, then wait for my turn and switch the signal back on”.
I wonder why this isn’t the algorithm? I assume there’s a good reason.
That would imply that whenever there is only one light on, if the indicator is not pointed to the one who lit it, he would still have to wait for the other process to arrive, turn on his light, do the task and flip the turn indicator.
If the other never comes, you process would be waiting indefinitely
This doesn't work. What if program A turns on its light, enters the critical section, leaves the critical section, flips the turn indicator to B, and turns off its light, then turns it back on and enters the critical section again. Program B turns on its signal light, and sees that both lights are on and the turn indicator is on B, and your idea says it is fine to enter the critical section but A is still in there executing code.
@@OMGclueless I was also confused why this wouldn't work. Thanks for the explanation, it makes more sense to me now.
@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?
very very cute and best explanation :D
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.
Now understood what those yellow lights and Indicator were meant to be in the application code, I was doing code review recently.
This was great
What if you don't know how many concurrent programs will connect? For example editors on news websites can push the Save new article button 2 or more in parallel when they're working.
You should extrapolate the logic for N threads your server works with.
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 is the best!!
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?
Amazing
Can you make a video about semaphores?
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.
Cool. How does expand to 3+?
How do you implement that in programs
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.
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.
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?