Zum Inhalt springen
L

Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

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

Spanning Tree6:54 247.760 Aufrufe veröffentlicht Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 40 Zeilen
Herunterladen
  1. [Music] let's imagine two programs that both make use of some shared resource some piece of data for example that both
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. that only one program at a time can access some particular region of code a region commonly called the critical section
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. 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
  25. 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
  26. 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
  27. 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
  28. 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
  29. 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
  30. the critical section ourselves this then is Decker's algorithm for solving the mutual exclusion problem first we turn on our signal light and
  31. 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
  32. 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
  33. 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
  34. 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
  35. up with race conditions where two programs enter the critical section at the same time without keeping track of turns
  36. 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
  37. 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
  38. 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
  39. 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
  40. programs can share access to data without conflict [Music]

Zum Nachlesen

WettlaufsituationEine Wettlaufsituation, aus dem Englischen auch Race Condition (deutsch Wettlauf-Bedingung) oder Race Hazard (deutsch Wettlauf-Risiko), mitunter auch … Kritischer AbschnittKritische Abschnitte bestehen aus mehreren Einzelanweisungen, deren Zwischenergebnisse inkonsistente Zustände darstellen, auf die die anderen Threads keinen … InterprozesskommunikationDeadlocks. Bearbeiten. → Hauptartikel: Deadlock (Informatik). Eine Menge von Prozessen befindet sich in einem Deadlock-Zustand, wenn jeder Prozess aus der … Nicht-blockierende SynchronisationNicht-blockierende Synchronisation (englisch non-blocking oder auch lock-free synchronization) ist eine Technik in der Informatik, um parallele Prozesse zu …