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

[Music] let's imagine two programs that both make use of some shared resource some piece of data for example that both programs need to access if one program is trying to say increase some value by one there is no problem the program can see what the value is calculate the number one higher and then replace the existing value a challenge computers face though is how to deal with concurrency if both programs try to access the shared data at the same time what happens well now we might have a problem if we're unlucky both programs will look at the original value both will calculate the number one higher and then both will try to replace the original value we meant to increase the value twice but in effect we've only ended up with a number increased by one this is an example of a race condition and we'd like to avoid it if possible to do so we need some mechanism to ensure that only one program at a time can access some particular region of code a region commonly called the critical section one simple strategy is to force the programs to take turns we can add a value to our setup that is responsible for keeping track of whose turn it is the turn indicator starts by pointing to one program and only that program is allowed to enter the critical section when the program leaves the critical section they can flip the turn indicator the other way to let it be the other programs turn this setup does ensure that only one program is in the critical section at any given time but it's not a great solution if for example one of the programs might need to access the critical section much more often than the other if we need to access the critical section but it's the other programs turn then we're forced to wait even if the other program doesn't need the critical section until later so there must be a way to do better our original problem came about when both programs tried to access the critical section simultaneously not realizing that the other wanted access to so let's solve this problem by giving each program a way to first signal their intent to enter the critical section before they actually enter we'll give each program a signal light that can be toggled on or toggled off any time a program wants to enter the critical section they'll first turn on their signal light to indicate their intent then to be safe each program must obey this rule a program can never enter the critical section if the other programs signal light is turned on if the other program signal light is turned off then we know they don't want to enter the critical section so we're free to enter it and access the shared data regardless of which way the turn indicator is pointing after all if the other program doesn't signal intent to enter we know we can enter the critical section without conflict after we're done we can exit and turn off our signal light this approach now lets a program that needs access to the critical section more frequently do so what we need to be careful about though is what happens when both programs want to enter the critical section in that case both programs turn on their signal lights but remember no program is allowed to access the critical section if the other programs that signal light is turned on so both programs are now stuck in what's known as deadlock both programs are left waiting forever for the other programs light to turn off but neither light ever turns off we need some way then to resolve this deadlock when both signal lights are on well that's when we can now look back to the turn indicator to let it decide who gets to enter the section next if ever we want to enter the critical section but the other programs signal light is turned on we can check to see who is turn it is and if the turn indicator says that it's the other programs turn then we should turn off our own signal light then wait for it to be our turn and only afterwards that turn our own signal light back on the other program meanwhile when it sees that our signal light has been turned off can then enter the critical section work with the shared data and then exit once it exits the program should toggle the turn indicator back to us and then it can turn off its own signal light once we see the turn indicator switch will turn our own signal light back on and since the other program signal light is turned off we are now clear to enter the critical section ourselves this then is Decker's algorithm for solving the mutual exclusion problem first we turn on our signal light and while the other program signal light is turned on we can't enter the critical section so we should instead it check to see if it's the other programs turn if it is we turn off our signal light wait for it to become our turn and then turn on our signal light again once the other programs signal light turns off we can now enter the critical section do the work we need it and then switch the turn indicator to let it be the other programs turn and then turn off our own signal light it's a lot of precision for what might sound like a simple problem but we need that precision without signaling we might end up with race conditions where two programs enter the critical section at the same time without keeping track of turns we might inadvertently let one faster program have all the access to the critical section starving the other slower program of the access that it needs and without turning off our own light when it's the other programs turn then we could get stuck in a deadlock these are the kinds of challenges we need to deal with whenever thinking about concurrency Decker's algorithm isn't the only way to solve this problem but it was one of the first algorithms invented to do so and it's able to work without any special hardware just three pieces of data two signals and one turn indicator to help make sure that two programs can share access to data without conflict [Music]

Channel: Spanning Tree

Views: 12,524

Rating: 4.9805827 out of 5

Keywords: computer science, software, hardware, concurrency, algorithm, race condition, mutual exclusion, lock, mutex, busy waiting, Dijkstra, shared memory, communication, process, flag, variable, pseudocode, deadlock, starvation

Id: MqnpIwN7dz0

Length: 6min 53sec (413 seconds)

Published: Sun Jul 12 2020