HN Theater @HNTheaterMonth

The best talks and videos of Hacker News.

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
HN Theater has aggregated all Hacker News stories and comments that mention Spanning Tree's video "Race Conditions and How to Prevent Them - A Look at Dekker's Algorithm".
Youtube Summary
When two programs both need access to some shared data, how do we ensure that they don’t try to manipulate the data at the same time? This is the mutual exclusion problem, and it’s often solved with hardware. But even without any special hardware, Dekker’s Algorithm offers a way to ensure that programs can only access the shared data one at a time. Here, we take a visual look at Dekker’s Algorithm: what’s the intuition behind it? How does it work? And why does it prevent race conditions?

0:00 Mutual Exclusion
2:24 Signaling
4:05 Dekker’s Algorithm

***

Spanning Tree is a collection of educational videos covering topics related to computer science and mathematics.

Brian Yu
https://brianyu.me/
https://spanningtree.me/
HN Theater Rankings

Hacker News Stories and Comments

All the comments and stories posted to Hacker News that reference this video.
Jan 07, 2022 · 32 points, 10 comments · submitted by optimalsolver
ncmncm
I 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
Rather 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).
skyde
Transaction
bob1029
The 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.

gpderetta
race conditions still exist on shared nothing concurrent systems.
felixgallo
by definition, they don't.
formerly_proven
Not all race conditions are data races.
felixgallo
'shared nothing' has meaning.
None
None
gpderetta
Yes, 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.
optimalsolver
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.

HN Theater is an independent project and is not operated by Y Combinator or any of the video hosting platforms linked to on this site.
~ yaj@
;laksdfhjdhksalkfj more things
yahnd.com ~ Privacy Policy ~
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.