Hacker News Comments on
Race Conditions and How to Prevent Them - A Look at Dekker's Algorithm
Spanning Tree
·
Youtube
·
32
HN points
·
0
HN comments
- This course is unranked · view top recommended courses
Hacker News Stories and Comments
All the comments and stories posted to Hacker News that reference this video.⬐ ncmncmI found this video wholly unenlightening. And, it took a long time to be unenlightened.There must be a better way.
The fact most usually omitted from presentations is that, to get reasonable performance, a system needs to be designed so that the sort of interaction described practically never happens. This omission is sort of understandable, in that a carefully resolved conflict is interesting and tricky. But the most characteristic feature of any such interaction is that it is very, very slow. So, the goal is to make the uncontended case fast, and the contended case anyway correct, but most importantly rare enough that it doesn't matter that it is so very slow.
Thus, the best protocols are designed so that you assume everything went fine, do a quick check, and skip on your way. If the check fails, you then have to do a complex dance. As the user of the mechanism, it is your responsibility to arrange not to trigger it.
⬐ Jtsummers⬐ skydeRather than "unenlightening", I'd say that this video was too narrowly scoped for its title here, the actual video has a subtitle: A Look at Dekker's Algorithm. With the subtitle, it's a reasonable presentation of its topic (though I found it excruciatingly slow, I generally skip video submissions).Transaction⬐ bob1029The best way to eliminate these conditions is to stop trying to share resources between threads in the first place.There is a fundamental theoretical limit to how quickly multiple things separated by some distance can reliably communicate about a shared thing. No amount of trickery will get you out of this mess.
The most powerful hack available if you absolutely must share resources between threads is the compare and swap (CAS) operation. This will get you pretty close to the performance limit in these scenarios.
Now to really help put things in perspective - A single thread looping over a resource uncontended will be approximately 2 orders of magnitude faster than two or more threads hotly contending over the same resource via CAS mechanism.
Paying close attention to this stuff can make the difference between neatly fitting the entire business in 1 computer system and having to build some netflix-scale monstrosity.
⬐ gpderettarace conditions still exist on shared nothing concurrent systems.⬐ felixgallo⬐ optimalsolverby definition, they don't.⬐ formerly_provenNot all race conditions are data races.⬐ felixgallo'shared nothing' has meaning.⬐ NoneNone⬐ gpderettaYes, it means that nodes do not share physical memory (whether volatile or persistent). It is the opposite of shared memory. They can still exchange messages and that can easily lead to races.Take the case of parallel, derivative-free optimization.A set of agents independently traversing a solution space need some kind of shared information to base their decisions on, eg. the current best solution found by all agents, together with its score and location, and what areas of the search space have low values (or high ones).
I'm sure there's a way to do this without shared data, but I doubt it beats the ease of slapping a "#pragma omp parallel" on a code block and adding a critical section for resource access.