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

How do you implement that in programs

this is cool, but how would this work with an infinite amount of threads, lets say I want 5 threads instead of 2, how would the light issue and turn indicator work?

this video deserve more views

Theres 2 disadvantages with the algoritm:
1: It can only suffice for 2 processes, due to the "turn indicator".
2: It cannot be used for unknown amount of processes, or anonymous processes. Everything needs to be planned before the shared resource is created.

This effectively means, that you actually can drop the shared resource alltogether. Just tell the other process what you want to do, and then you both keep tally. It MIGHT desync, but provided theres reliable communication between the processes, which it must exist if you use a "signal light", it will work out fine without a shared resource.

For a good mutual exclusion to exist, you need to be able to use it with a unknown amount of processes (imagine visitors to a website, then you can't know which visitors are going to manipulate the shared data, and there can be any amount of visitors to a website), and these processes need to be able to be anonymous, meaning each process cannot uniquely identify each other process, because the process are forked from a main process.

This is where MySQL (or other database languages) comes in. Which could be described as a "manager", like a resturant waiter. You order a change of the shared data (like a customer ordering food). Manager will execute order in a first-serve first-come basis, so there will never be starvation, never any deadlocking, and never any concurrent access to the data, as the manager will only execute one process's request for change at a time.

Wouldn't the turn indicator be another shared piece of data? Why does race conditions do not occur over it?

Can be scaled too.

Just add more lights and a turn indicator with more positions to accommodate more programs.

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

This is the example of opening application

Brian, your name should be Brilliant!

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.

wow

oh my god! this was amazing!

Where was this when I was in Op Systems last semester ughh 😭

As far as I remember there is a superior algorithm, that also works without extra hardware and even avoids the active waiting. It's called X's algorithm where X is another famous guy.

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 wonder how it would work with 3 programs, and 2 of them with indicators on, while the turn is on the third...

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!

Now consider how to bypass caches.

This was great

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?

ah, so the solution to the "race" problem is segregation.







wait a minute..

this is so cool. must be a blast to do this for a living
sometimes programs have used swords or guns to access resources and starve others without regard for turns tho 😅

I wish they showed us this stuff when we were in college.
The teachers would blabber on for hours without really explaining. It was such a learning-boner-killer and a waste of time.

If this doesn't make sense, remember that computers can only write to memory in a destructive manner, by replacing what was there and has no recollection of the prior value

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

In the real world, there is one more bot called "kernel". Its job is to decide who enters the critical section

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 had no idea this could be resolved without atomic operations, wonderful explanation

Race condition: When you're black, and losing an argument on twitter.

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!

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?

If more than 2, so the pointer becomes a binary code, +1 after every usage?

I need this for sharing the bathroom with my roommates

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!

couldnt you also make each program have their own data, then when you want to read the actual data, you sum each one’s data up (only works with operations that are unordered)

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

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

smol heha

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

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

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

Absolutely brilliant explanation! 😃💯💥👍💫

Lock out tag out

In the 60's IBM had a hardware instruction, compare and swap CS, that ran as a single CPU instruction. It took 3 inputs, a, b, and c. It would compare b to a and if they were equal it replaced A with C. The condition code was the result of the compare. In your program you read A into B and C, added 1 to C, did the CAS, if condition code was equal continue on, If it was not loop back to the start.

Easy on a single CPU system. I looked at the Z POPs and by magic it works in a multiprocessor environment.

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

Wouldn't allowing the database handle this a better solution? Each dataset has a flag "isRequested". Whenever a program wants access, the database sets the variable to true. If some other program wants access, the database won't allow it, until "isRequested" is set back to false.

Allowing a single program to handle this, will make it physically impossible for 2 programs to set the variable to true, since no operation happens at once on a program. If we allowed the individual programs to handle the setting of this variable, then it could technically happen at once, and we would need a Dekker algorithm.
Now, i know this would cause a slow down of the general system, since only a single program is handling the switching, but the major question is: is this trade of performance for reliability worth it?

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!

I feel like the double light deadlock is nearly the same problem we started with, just with a different skin.
I don't know if this would be the right way to do this, but my intuition says just don't share the memory (critical area).
So each program would have it's own copy that it modifies and the "shared memory" from before could just be a total of the two.
This allows both programs to run at their own rates without waiting or even needing to know the other exists at all.
I don't really know if this sort of solution is feasible or scalable at all, but it sounds better to just have each program keep up with the changes it "would" make.
Then you could just have the main "shared data" be managed by a singular program that applies those changes as necessary.
example:

program 1:
var s = 0
func foo()
s+=1
end

program 2:
var s = 0
func foo()
s-=1
end

main program
var s = 4

while(1)
s = s+program1.s+program2.s
end