The 80’s Algorithm to Avoid Race Conditions (and Why It Failed)

Comments · 635

• DA

  @DavidRomigJr · 1 year ago · pinned

  For fun, I implemented the code in the video on my mid-2012 Mac PowerBook. Using volatiles, I got the assembly to emit in the correct order for this algorithm with -O3 optimizations on insuring no compiler-caused race conditions. Of course, some runs worked, but most were slightly short, indicating hardware optimization on my machine was definitely causing race conditions. So, I put 32 nops between each statement, making sure the compiler left them in as well just to see how much of an affect that had. Most runs worked, but every now and again, a run would be short by 1 or 2. So, yeah, there's no reliable way around race conditions without mutex or atomic operations. It's just interesting to see it happen on my local machine. BTW, subscribed!

  473

• IN

  @InterDylan · 1 year ago

  This video&apos;s title is a perfect example for why i hate YouTube&apos;s automatic title translation.<br>They absolutely butchered the meaning of the title in Dutch by translating it to: &quot;The algorithm from the 80s to avoid race hatred (and why it failed)&quot;

  1K

• MA

  @maxcai3795 · 1 year ago

  I think it&apos;s important to note that this isn&apos;t inherently a problem with Peterson&apos;s algorithm itself, but rather how this specific implementation makes assumptions on the platform&apos;s memory model which aren&apos;t necessarily guaranteed by the C specification! This same idea, but with more careful use of atomic memory orders on the loads and stores, could be thread-safe.

  174

• TI

  @tiranito3715 · 1 year ago (edited)

  For anyone wondering if marking the variables as volatile to prevent compiler optimizations would fix the issue... yes, in an older CPU, that would work. But the moment the CPU has instruction pipelining, the instructions executed by the hardware are changed not just by the compiler, but also by the CPU, so volatile does not fix the issue. Software only solutions would work if it weren&apos;t for CPU instruction pipelining and optimizations applied to microcode, so the solution, as the video states, is to use hardware atomics, which is what mutex implementations use under the hood on modern platforms.<br><br>EDIT : I&apos;m tired of explaining this to people and having my replies be deleted by YT over and over again, so I&apos;ll write it once and hope people with a minimum of intelligence can understand this: I&apos;m talking about out of order execution and instruction reordering. Just because you didn&apos;t know that CPUs can reorder instructions, it doesn&apos;t mean that they can&apos;t. Look it up. The video literally talks about microcode, one would expect that people would watch the whole thing BEFORE going to the comments, but it seems not to be the case.

  531

• 葛帝

  @葛帝恩 · 1 year ago

  <a href="https://www.youtube.com/watch?v=QAzuAn3nFGo&amp;t=124">2:04</a> Even worse, single line assembly statements can be non-atomic, like in this case inc dword [rbp-8] in i386 assembly. Still suffers from this race condition.

  69

• CA

  @canaDavid1 · 1 year ago

  All of this breaks down when you consider memory consistency models. All of this assumes sequential consistency (there is a total order on all memory operations), but that is not the case for any current cpu. Specifically, x86 uses TSO, total store order, where stores are ordered with each other but are allowed to appear after later loads. This is very useful so that an instruction does not need to wait for a preceding store to go all the way through memory before continuing.

  49

• ZU

  @Zuckerbuck · 1 year ago

  COREDUMPED IS HEREEEEEE

  148

• JO

  @josephoyinkan5480 · 1 year ago

  YAY coredumped, keep up with the videos on the OS. It&apos;s has been really helpful

  35

• FA

  @famrofexl · 7 months ago

  Apart from using atomic instructions, peterson&apos;s algorithm can also be implemented using the x86 &quot;mfence&quot; instruction, which guarantees memory load and store operations won&apos;t be reordered with memory load and store instructions after it.

  4

• BL

  @Blezerker · 1 year ago (edited)

  coredumped is literally the only content vreator ill listen to with a TTS voice in this day and age. any other video that even remotely sounds robotic or AI generated immediately gets the “do not recommend this channel to me again” treatment

  128

• TI

  @Tigrou7777 · 7 months ago

  <a href="https://www.youtube.com/watch?v=QAzuAn3nFGo&amp;t=942">15:42</a> modern CPUs have buffer called &quot;reorder buffer&quot; (up to 128 entries). Inside, you have all instructions that are already fetched and decoded. CPU will inspect that buffer and will pick up any instruction that is ready to be executed (eg: the operands are ready), &nbsp;and it will dispatch it to execution units. As soon as result is computed, it will update available operands and will check who is next in the &quot;reorder buffer&quot;. In modern CPUs it&apos;s common to execute up to 4 instructions at the same time that way. Additionally, register renaming allows to use create even more dependency (and thus increase parallelism) between instructions that use same registers but are independant.

  1

• NO

  @no-one6790 · 1 year ago (edited)

  Your channel is literally the best one among all the CS-focused channels. I am currenly studying computer science and your channel is one of the reasons I got into low-level C programming.<br>Your explanations are just so clear and unlike CS textbooks, you don&apos;t omit &quot;obvious&quot; information. Cheers 🎉<br>EDIT: Just to be clear, I know mostly everything that is talked about in these videos but they are just so well made and help me rearrange the knowledge in my head.

  4