Race Conditions and How to Prevent Them - A Look at Dekker's Algorithm

[@programaths]

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.

[@ytuseraccount]

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

[@aroundtheworld5344]

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.

[@PuchuKt]

How are you doing now, still doing CS?

[@williamwalcher3333]

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]

Glad you enjoyed it!

[@BritishBeachcomber]

That's the *difference between programming and coding.*

[@cezarcatalin1406]

@@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.

[@SuperDarmino]

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

[@enlgn7050]

Mann....I really felt bad for those cute bots when they were stuck in a deadlock.😭😭😭

[@ouwebrood497]

A livelock is more exhausting though.

[@ouwebrood497]

@@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.

[@_abdul]

Great Explanation I've never seen two programs that adorable.

[@rishabhrathi22]

This is no doubt the best explanation of Dekker's algorithm I have ever seen. Amazing work !!!

[@anamigator]

Amazing explanation. I liked the part towards the end where you go over the subtleties of what makes the algorithm good

[@stgram12]

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!

[@bettercalldelta]

Literally had a program suffer from race conditions and this video really helped me fix it

[@bscorvin]

Well this is a much more coherent explanation than my old professor, thanks!

[@maheswaran6628]

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:)

[@hoangphamduc3928]

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!

[@saurabhsoni5047]

This is what efficiently conveying an idea means.! Developer, Take a bow !

[@jamesdaus]

Love the explanations and animations! Great work on cs50 AI too

[@goofynigiri]

Super clear explanation, your video really helped me understand the Critical Section better, thank you!

[@ayaanahabel9238]

The best explanation ever! I swear youtube is better than these lectures

[@victoriam6569]

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!

[@ruantristancarlinsky3851]

This is Amazing...if only you could cover everything it would helps millions around the world

[@mahdi7d1rostami]

This video deserves much more views. You got a new sub.

[@miguelnischor]

Very thanks for the great lesson, very simple and straight to the point.

[@theuniverse2268]

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

[@bloodywolftr]

I just discovered this channel. Brilliant instructions with brilliant graphics. Thanks for all.

[@gagadaddy8713]

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 .....

[@Rising_Pho3nix_23]

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.

[@danielyuan9862]

The video is secretly teaching us how to count from 1 to 10.

[@nigelkay6264]

how can someone come here and actually dislike this excellent content?....... amazing work bro!🔥

[@ennergyspotato5566]

I wish there were videos like this for finance and business

[@MrPierreSab]

the best channel on youtube

[@natriac.6092]

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!

[@rubixtheslime]

i had no idea this could be resolved without atomic operations, wonderful explanation

[@AttilaAsztalos]

Mad Max's algorithm: Two bots enter, one bot leaves...

[@transientaardvark6231]

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.

[@solsystem1342]

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.

[@transientaardvark6231]

@@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.

[@p7willm]

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.

[@JoseFernandez-qt8hm]

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...

[@mkd0x]

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

[@DiThi]

If you use python you should just use a mutex, which uses exactly the same algorithm, just at a lower level.

[@ah-rdk]

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.

[@budstep7361]

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!

[@fozanshahid8687]

What a great explanation! loved it and understood it!

[@jesseanonanimous8728]

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!

[@cate01a]

it's cool how involved a solution is to a very simple issue

[@happmacdonald]

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.

[@argothiel]

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

[@krazykidmusic4954]

These are very well made and easy to understand. Good stuff!

[@posi0504]

this video deserve more views

[@gonegahgah]

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?

[@MountPanda]

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".

[@FoxDren]

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.

[@punditgi]

Absolutely brilliant explanation! 😃💯💥👍💫

[@surajregmi11]

Brilliant explanation. One of the best explanations I have seen on KZbin. A few minutes of video saves you from reading and trying to understand something for about an hour.

[@youtubeuniversity3638]

Can be scaled too. Just add more lights and a turn indicator with more positions to accommodate more programs.

[@blacklistnr1]

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.

[@friskylime]

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.

[@icedlava7063]

I don't know if that's simpler, but it's certainly another way to solve it!

[@lassipulkkinen273]

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.

[@gamecashers2472]

an amazing way to explain some ways to code

[@damienlcom]

Excellent content, thanks for making this.

[@wisteria3032]

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.

[@liushaomin7004]

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?

[@enderboy-db3sh]

Without the context of this being a computer related video, "race condition" meant a whole other thing to me

[@asdfghyter]

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

[@thomasmaughan4798]

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.

[@bluesillybeard]

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.

[@asdfghyter]

@@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"

[@gabeb4326]

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!

[@yana_k6424]

Cool video! What do you use to make the animations by the way? They remind me of three.js renders

[@PawanSingh-in4xx]

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.

[@MrJegerjeg]

Exactly my thoughts!

[@DajesOfficial]

It is already protected because it can be changed only by process that was allowed to access the critical section.

[@NeutronDev]

Very good explanation and nice animations!

[@MaadCoding]

Great and simple explanation :)

[@alikaperdue]

@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?

[@ryandaepic1838]

Very intuitive...thank you!

[@kweinhold22]

Amazing Explanation

[@R.B.]

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.

[@dennisgonzales9521]

Excellent explanation!

[@ITR]

Though for simple stuff like adding a number, using an atomic add is probably better

[@bob456fk6]

Thank you for the very clear explanation. The little bots are cute and they show the operations very well 🙂

[@Cospel]

Great video! It was so useful!

[@BradenBest]

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

[@iosifpuha6114]

this was greatly presented! Cheers

[@enclocreations4427]

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.

[@animeshkumar1201]

best video on this topic

[@thewelder3538]

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.

[@clasherofclans1482]

Now understood what those yellow lights and Indicator were meant to be in the application code, I was doing code review recently.

[@MAlanThomasII]

Hmm. But you could still deadlock if both programs are turning their light on and off at the same time (same effective start time and frequency). Rather than check the state of the turn indicator and then turn off a light, the program with the turn indicator should take their turn, turn off their light if and only if they're finished for now, and then flip the turn indicator. This avoids a light-flipping deadlock, and it alternates between the programs each time there's a conflict. It also reduces both reads and writes to both the turn indicator and the lights, reducing overhead.

[@demonslime]

I don't think there will be a light-flipping deadlock, since once you turn your light off you aren't allowed to turn it back again. We should see all the other processes turn their light off one by one until only the one with the turn indicator remains on. Also, the one with the turn indicator can't just immediately go in because it's possible someone else is in it since you wouldn't know whether the process with a light on is waiting to use it or is currently using it.

[@ayushsingh-hd5ld]

Thank you. please also explain peterson solution

[@brandonhunter3036]

That's a fantastic explanation thanks for creating this.

[@GerardWassink]

Rather have a semaphore inside the critical section itself and have it set the semaphore when it enters and reset it when it exits. That way the critical section ‘protects’ itself against double (even multiple) use.

[@lost4889]

easy way to understand something that would have likely confused me, thanks

[@gonegahgah]

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?

[@zilvarro5766]

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.

[@greciaguerrero218]

I thank you so much, I understood you way better than my teacher and he speaks my native language!! haha Best regards :)

[@luizsantana4475]

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.

[@APaleDot]

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.

[@agate_jcg]

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?

[@ACcaptive]

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.

[@p7willm]

This requires a third program. If there is a fault in the third program both of the other two would wait forever.

[@RyanLynch1]

how do you avoid the potential non-atomicity of setting your signal light and checking if the other signal light is on?

[@jeffreygordon7194]

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.

[@charetjc]

@@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.

[@CFEF44AB1399978B0011]

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?

[@runforitman]

My first thought is to have them do something like check a place in memory, if it's 0, write their ID to it (say 1 and 2), then check it again and make sure their ID is there, if it is, it writes its data then resets the point in memory to 0. This means, if they both overwrite it at the same time, only one will actually write their final data, and as soon as its free, the other will take it.

[@runforitman]

this would be basically like a token system but instead of them taking it, where two threads could take it at the same time and think they both have it, it writes, so only one will have it

[@runforitman]

but yeah it could have issues with hogging the critical zone, and one program never gets a go, I also don't think you could implement a turn system easily

[@p7willm]

1 reads a 0, 2 reads a 0, 1 writes its ID, 1 reads its ID and continues, 2 writes its id, 2 reads its id and continues. Bad. Unless you guarantee both process run at the same speed, with no interruptions, down to the instruction.

[@lolitsBilly]

Can you make a video about semaphores?

[@SirSidi]

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)

[@DigitalArchmage]

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.

[@hereigoagain5050]

Spanning Tree is way more fun than "Art of Programming," by Donald Knuth, though I think he would be an enthusiastic supporter of these video clips.

[@shalinluitel1332]

Great Video!!!

[@majorjohnson8001]

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.

[@acidrain99]

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.

[@hugopinto4269]

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.

[@hugopinto4269]

If the other never comes, you process would be waiting indefinitely

[@OMGclueless]

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.

[@kalahatze]

​@@OMGclueless I was also confused why this wouldn't work. Thanks for the explanation, it makes more sense to me now.

[@stea27]

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.

[@DajesOfficial]

You should extrapolate the logic for N threads your server works with.

[@fastrobreetus]

Great video!

[@mohammedkhalid5517]

In real-life programs, when does a thread need to access data more frequently?

[@raz0229]

lets say, a shared increment procedure for updating time, where the value behind minutes is to be incremented every 60000ms and seconds need to be incremented every 1000ms (60 times as frequent than minutes).

[@Windows__2000]

This doesn't really work when there's more than just two, wouldn't it be easier to have a single thread, that you ask and it tells u whether u can go? Kinda like it works with files? Or tell the single thread what you want to do? I'm curious if this is actually used anywhere...

[@reda29100]

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).

[@leightonshelley]

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?