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.
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.
@@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.
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
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!
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.
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 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!
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
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!
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.
Brilliant explanation. One of the best explanations I have seen on RU-vid. A few minutes of video saves you from reading and trying to understand something for about an hour.
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...
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".
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.
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!
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.
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.
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?
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"
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.
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!
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
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
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.
@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?
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.
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.
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!
@@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.
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.
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?
But what is there are three robots? It isn't enough to have a toggle which points to the other, as that robot might not be the one that is also waiting. The change that I seem to remember is that if two robots see that their lights are on, they should turn them off for a random amount of time before they try again... It wouldn't be quite as efficient because now the critical section might not be updated as frequently as it could be, but it would break the deadlock state.
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.
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?
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.
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?
I've spent years writing multithreaded code and I really do appreciate you trying to explain quite a complex subject, but this is NOT how mutual exclusion works in practice. In the programming world, access to a shared resource is done through a mutex or semaphore. There is NO turn indicator. Anything wanting access to a resource obtains a lock upon that resource thus preventing anything else from modifying it until the lock is released. Obviously there are more complex examples where there's both a reader and writer lock to ensure that reading can always take place etc, but threads don't have to wait their turn for access. If the thread can obtain a lock, it can work with the resource. Also, using the term critical section could be an issue because a Critical Section is something very specific in Windows and is different from a mutex and semaphore.
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?
The process at 5 minutes in seems overcomplicated. If the signal light is meant to signify a mutex lock, then shouldn't the process be: * check if there is a mutex lock (check if other program's light is on) * if so, check if supervisor says it's our turn (check if turn indicator points to us) * if so, ignore the mutex lock, make the change, and then clear the mutex lock. (ignore the light, make the change, move the turn indicator and turn our light off) * otherwise, wait for either the mutex lock to go away or for the supervisor to grant access. In terms of your pseudocode: our light = on while other light = on: if turn = ours: enter critical section turn = other our light = off break Ignoring the other program's signal is a lot simpler than turning your own signal off and waiting for them to finish
Why not use a stack (first in, first served) type? More explicitly, room has exclusive occupant. When in, register name. If not none, wait, otherwise, enter and fill name. When out, erase name. Is there something I'm missing? Some probably better approach is, parallelize processes, but if we're not accessing values (only mutating), then keep a process list like above, but skip it in the process. This way, you don't need to keep process suspended when all you need is to (leave a note for the secretary that I arrived).
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
why have two signals? and what if there are more than two programs? there should be just one signal and all programs can change it (only if it is off initially), once they are done, they turn if off again and allow other programs to use it ( a locking mechanism)
