<?xml version="1.0" encoding="UTF-8"?>
<rss version="2.0" xmlns:atom="http://www.w3.org/2005/Atom" xmlns:dc="http://purl.org/dc/elements/1.1/">
  <channel>
    <title>DEV Community: Binary Dose</title>
    <description>The latest articles on DEV Community by Binary Dose (@binarydose).</description>
    <link>https://dev.to/binarydose</link>
    <image>
      <url>https://media2.dev.to/dynamic/image/width=90,height=90,fit=cover,gravity=auto,format=auto/https:%2F%2Fdev-to-uploads.s3.us-east-2.amazonaws.com%2Fuploads%2Fuser%2Fprofile_image%2F4204496%2F51ff9ee5-7dac-46e9-95ec-c9eff53d3ed4.png</url>
      <title>DEV Community: Binary Dose</title>
      <link>https://dev.to/binarydose</link>
    </image>
    <atom:link rel="self" type="application/rss+xml" href="https://dev.to/feed/binarydose"/>
    <language>en</language>
    <item>
      <title>Solving the Readers-Writers Problem: Fair Synchronization with Turnstiles</title>
      <dc:creator>Binary Dose</dc:creator>
      <pubDate>Sun, 15 Nov 2026 19:28:54 +0000</pubDate>
      <link>https://dev.to/binarydose/solving-the-readers-writers-problem-fair-synchronization-with-turnstiles-24c3</link>
      <guid>https://dev.to/binarydose/solving-the-readers-writers-problem-fair-synchronization-with-turnstiles-24c3</guid>
      <description>&lt;h1&gt;
  
  
  Solving the Readers-Writers Problem: Fair Synchronization with Turnstiles
&lt;/h1&gt;

&lt;p&gt;In multi-threaded architecture, reading shared data is intrinsically safe: multiple threads can read memory concurrently without data corruption.&lt;/p&gt;

&lt;p&gt;However, writing requires &lt;strong&gt;exclusive access&lt;/strong&gt;: no reader and no other writer may access the resource simultaneously.&lt;/p&gt;

&lt;p&gt;This asymmetry introduces one of the most famous classical problems in operating systems: &lt;strong&gt;The Readers-Writers Problem&lt;/strong&gt;.&lt;/p&gt;




&lt;h2&gt;
  
  
  1. The First Variation: Reader Preference (Writer Starvation)
&lt;/h2&gt;

&lt;p&gt;The naive implementation prioritizes read throughput:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight c"&gt;&lt;code&gt;&lt;span class="c1"&gt;// Reader logic:&lt;/span&gt;
&lt;span class="nf"&gt;wait&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;mutex&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="n"&gt;read_count&lt;/span&gt;&lt;span class="o"&gt;++&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="k"&gt;if&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;read_count&lt;/span&gt; &lt;span class="o"&gt;==&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt;
    &lt;span class="nf"&gt;wait&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;rw_mutex&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="c1"&gt;// First reader locks out writers&lt;/span&gt;
&lt;span class="p"&gt;}&lt;/span&gt;
&lt;span class="nf"&gt;signal&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;mutex&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="c1"&gt;// Read data...&lt;/span&gt;

&lt;span class="nf"&gt;wait&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;mutex&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="n"&gt;read_count&lt;/span&gt;&lt;span class="o"&gt;--&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="k"&gt;if&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;read_count&lt;/span&gt; &lt;span class="o"&gt;==&lt;/span&gt; &lt;span class="mi"&gt;0&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt;
    &lt;span class="nf"&gt;signal&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;rw_mutex&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="c1"&gt;// Last reader releases writers&lt;/span&gt;
&lt;span class="p"&gt;}&lt;/span&gt;
&lt;span class="nf"&gt;signal&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;mutex&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;h3&gt;
  
  
  The Starvation Flaw:
&lt;/h3&gt;

&lt;p&gt;If reader &lt;code&gt;R₁&lt;/code&gt; is active, a writer &lt;code&gt;W₁&lt;/code&gt; arrives and blocks on &lt;code&gt;rw_mutex&lt;/code&gt;. &lt;/p&gt;

&lt;p&gt;Before &lt;code&gt;R₁&lt;/code&gt; finishes, reader &lt;code&gt;R₂&lt;/code&gt; arrives. Since &lt;code&gt;read_count &amp;gt; 0&lt;/code&gt;, &lt;code&gt;R₂&lt;/code&gt; enters immediately. Before &lt;code&gt;R₂&lt;/code&gt; finishes, &lt;code&gt;R₃&lt;/code&gt; arrives. In a read-heavy system, &lt;code&gt;read_count&lt;/code&gt; never drops to zero. &lt;strong&gt;The writer starves indefinitely.&lt;/strong&gt;&lt;/p&gt;




&lt;h2&gt;
  
  
  2. The Fair Solution: The Turnstile Pattern
&lt;/h2&gt;

&lt;p&gt;To guarantee that both readers and writers experience bounded waiting, modern kernels implement a &lt;strong&gt;FIFO Turnstile&lt;/strong&gt;:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight c"&gt;&lt;code&gt;&lt;span class="n"&gt;semaphore&lt;/span&gt; &lt;span class="n"&gt;turnstile&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="n"&gt;semaphore&lt;/span&gt; &lt;span class="n"&gt;rw_mutex&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="n"&gt;semaphore&lt;/span&gt; &lt;span class="n"&gt;mutex&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;read_count&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="mi"&gt;0&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="c1"&gt;// Reader:&lt;/span&gt;
&lt;span class="nf"&gt;wait&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;turnstile&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="nf"&gt;signal&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;turnstile&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="c1"&gt;// Pass through turnstile&lt;/span&gt;

&lt;span class="nf"&gt;wait&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;mutex&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="n"&gt;read_count&lt;/span&gt;&lt;span class="o"&gt;++&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="k"&gt;if&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;read_count&lt;/span&gt; &lt;span class="o"&gt;==&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="nf"&gt;wait&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;rw_mutex&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="nf"&gt;signal&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;mutex&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="c1"&gt;// Read data...&lt;/span&gt;

&lt;span class="nf"&gt;wait&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;mutex&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="n"&gt;read_count&lt;/span&gt;&lt;span class="o"&gt;--&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="k"&gt;if&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;read_count&lt;/span&gt; &lt;span class="o"&gt;==&lt;/span&gt; &lt;span class="mi"&gt;0&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="nf"&gt;signal&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;rw_mutex&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="nf"&gt;signal&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;mutex&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="c1"&gt;// Writer:&lt;/span&gt;
&lt;span class="nf"&gt;wait&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;turnstile&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="c1"&gt;// Lock turnstile; blocks subsequent readers!&lt;/span&gt;
&lt;span class="nf"&gt;wait&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;rw_mutex&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="c1"&gt;// Write data...&lt;/span&gt;

&lt;span class="nf"&gt;signal&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;rw_mutex&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="nf"&gt;signal&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;turnstile&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;h3&gt;
  
  
  How the Turnstile Enforces Fairness:
&lt;/h3&gt;

&lt;p&gt;When a writer arrives, it holds &lt;code&gt;turnstile&lt;/code&gt;. Any subsequent reader attempting &lt;code&gt;wait(turnstile)&lt;/code&gt; is queued behind the writer in the semaphore queue. &lt;/p&gt;

&lt;p&gt;Once the currently reading threads exit, the writer executes immediately. Starvation is mathematically eliminated.&lt;/p&gt;

&lt;p&gt;Explore full classical synchronization blueprints at &lt;a href="https://binarydose.in/coredose/os/chapter-04/classical-synchronization-problems-readers-writers-and-dining-philosophers" rel="noopener noreferrer"&gt;Binary Dose&lt;/a&gt;.&lt;/p&gt;

</description>
      <category>operatingsystems</category>
      <category>concurrency</category>
      <category>linux</category>
      <category>systemsengineering</category>
    </item>
    <item>
      <title>The Most Dangerous Keyword in C/C++: Why volatile Is Not Atomic</title>
      <dc:creator>Binary Dose</dc:creator>
      <pubDate>Sun, 15 Nov 2026 11:57:51 +0000</pubDate>
      <link>https://dev.to/binarydose/the-most-dangerous-keyword-in-cc-why-volatile-is-not-atomic-4d4d</link>
      <guid>https://dev.to/binarydose/the-most-dangerous-keyword-in-cc-why-volatile-is-not-atomic-4d4d</guid>
      <description>&lt;h1&gt;
  
  
  The Most Dangerous Keyword in C/C++: Why volatile Is Not Atomic
&lt;/h1&gt;

&lt;p&gt;One of the most persistent myths in systems programming is the belief that declaring a shared variable as &lt;code&gt;volatile&lt;/code&gt; makes it safe for concurrent multi-threaded access.&lt;/p&gt;

&lt;p&gt;Consider the following multi-threaded counter:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight c"&gt;&lt;code&gt;&lt;span class="kd"&gt;volatile&lt;/span&gt; &lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;counter&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="mi"&gt;0&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="kt"&gt;void&lt;/span&gt; &lt;span class="nf"&gt;worker&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt;
    &lt;span class="k"&gt;for&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="mi"&gt;0&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="o"&gt;&amp;lt;&lt;/span&gt; &lt;span class="mi"&gt;100000&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt;&lt;span class="o"&gt;++&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt;
        &lt;span class="n"&gt;counter&lt;/span&gt;&lt;span class="o"&gt;++&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="c1"&gt;// DATA RACE &amp;amp; LOST UPDATES!&lt;/span&gt;
    &lt;span class="p"&gt;}&lt;/span&gt;
&lt;span class="p"&gt;}&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Running two threads executing &lt;code&gt;worker()&lt;/code&gt; concurrently will almost never result in &lt;code&gt;200,000&lt;/code&gt;. Increments will be silently lost.&lt;/p&gt;

&lt;p&gt;To understand why, we must examine the difference between &lt;strong&gt;Compiler Optimizations&lt;/strong&gt; and &lt;strong&gt;CPU Hardware Coherence&lt;/strong&gt;.&lt;/p&gt;




&lt;h2&gt;
  
  
  1. What volatile Actually Does
&lt;/h2&gt;

&lt;p&gt;The &lt;code&gt;volatile&lt;/code&gt; keyword was introduced into the C standard in 1989 for a single specific purpose: &lt;strong&gt;interacting with Memory-Mapped I/O (MMIO) hardware registers and asynchronous signal handlers&lt;/strong&gt;.&lt;/p&gt;

&lt;p&gt;It communicates one instruction to the compiler:&lt;/p&gt;

&lt;blockquote&gt;
&lt;p&gt;&lt;em&gt;"Do not cache this variable inside a CPU register. Do not optimize away repeated reads or writes. Every read must emit a fresh load from memory."&lt;/em&gt;&lt;br&gt;
&lt;/p&gt;
&lt;/blockquote&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight c"&gt;&lt;code&gt;&lt;span class="c1"&gt;// Without volatile:&lt;/span&gt;
&lt;span class="k"&gt;while&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="o"&gt;!&lt;/span&gt;&lt;span class="n"&gt;flag&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt;&lt;span class="p"&gt;}&lt;/span&gt; &lt;span class="c1"&gt;// Compiler may optimize to: if (!flag) while(1){}&lt;/span&gt;

&lt;span class="c1"&gt;// With volatile:&lt;/span&gt;
&lt;span class="k"&gt;while&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="o"&gt;!&lt;/span&gt;&lt;span class="n"&gt;flag&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt;&lt;span class="p"&gt;}&lt;/span&gt; &lt;span class="c1"&gt;// Compiler emits a CMP instruction reading RAM every loop iteration&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;






&lt;h2&gt;
  
  
  2. What volatile Fails to Provide
&lt;/h2&gt;

&lt;h3&gt;
  
  
  Failure 1: Zero Atomicity
&lt;/h3&gt;

&lt;p&gt;The operation &lt;code&gt;counter++&lt;/code&gt; is not a single atomic hardware instruction. It decomposes into a 3-step sequence in assembly:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight nasm"&gt;&lt;code&gt;&lt;span class="k"&gt;mov&lt;/span&gt; &lt;span class="nb"&gt;eax&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="kt"&gt;dword&lt;/span&gt; &lt;span class="kt"&gt;ptr&lt;/span&gt; &lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="n"&gt;counter&lt;/span&gt;&lt;span class="p"&gt;]&lt;/span&gt; &lt;span class="c1"&gt;; 1. Read from memory into register&lt;/span&gt;
&lt;span class="k"&gt;add&lt;/span&gt; &lt;span class="nb"&gt;eax&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;                   &lt;span class="c1"&gt;; 2. Increment register value&lt;/span&gt;
&lt;span class="k"&gt;mov&lt;/span&gt; &lt;span class="kt"&gt;dword&lt;/span&gt; &lt;span class="kt"&gt;ptr&lt;/span&gt; &lt;span class="p"&gt;[&lt;/span&gt;&lt;span class="n"&gt;counter&lt;/span&gt;&lt;span class="p"&gt;]&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="nb"&gt;eax&lt;/span&gt; &lt;span class="c1"&gt;; 3. Write back to memory&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;If Thread 1 reads &lt;code&gt;counter = 5&lt;/code&gt;, and is preempted before Step 3, Thread 2 can read &lt;code&gt;5&lt;/code&gt;, increment to &lt;code&gt;6&lt;/code&gt;, and write back. When Thread 1 resumes, it writes &lt;code&gt;6&lt;/code&gt;, completely obliterating Thread 2's increment.&lt;/p&gt;

&lt;h3&gt;
  
  
  Failure 2: Zero Memory Barriers
&lt;/h3&gt;

&lt;p&gt;Modern superscalar CPUs (x86, ARM64) execute instructions &lt;strong&gt;out of order&lt;/strong&gt; to maximize execution pipeline throughput.&lt;/p&gt;

&lt;p&gt;&lt;code&gt;volatile&lt;/code&gt; imposes constraints on the &lt;strong&gt;compiler&lt;/strong&gt;, but it emits &lt;strong&gt;zero hardware memory barrier instructions&lt;/strong&gt; (like &lt;code&gt;MFENCE&lt;/code&gt; or &lt;code&gt;DMB&lt;/code&gt;). The CPU is free to reorder reads and writes around volatile variables across cache lines.&lt;/p&gt;




&lt;h2&gt;
  
  
  3. The Modern Solution: &lt;code&gt;std::atomic&amp;lt;T&amp;gt;&lt;/code&gt;
&lt;/h2&gt;

&lt;p&gt;For thread-safe operations in C and C++, never use &lt;code&gt;volatile&lt;/code&gt;. Use the standard atomic types:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight cpp"&gt;&lt;code&gt;&lt;span class="cp"&gt;#include &amp;lt;atomic&amp;gt;&lt;/span&gt;

&lt;span class="n"&gt;std&lt;/span&gt;&lt;span class="o"&gt;::&lt;/span&gt;&lt;span class="n"&gt;atomic&lt;/span&gt;&lt;span class="o"&gt;&amp;lt;&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt;&lt;span class="o"&gt;&amp;gt;&lt;/span&gt; &lt;span class="n"&gt;counter&lt;/span&gt;&lt;span class="p"&gt;{&lt;/span&gt;&lt;span class="mi"&gt;0&lt;/span&gt;&lt;span class="p"&gt;}&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;

&lt;span class="kt"&gt;void&lt;/span&gt; &lt;span class="nf"&gt;worker&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt;
    &lt;span class="k"&gt;for&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="mi"&gt;0&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt; &lt;span class="o"&gt;&amp;lt;&lt;/span&gt; &lt;span class="mi"&gt;100000&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="n"&gt;i&lt;/span&gt;&lt;span class="o"&gt;++&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt;
        &lt;span class="n"&gt;counter&lt;/span&gt;&lt;span class="p"&gt;.&lt;/span&gt;&lt;span class="nf"&gt;fetch_add&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;std&lt;/span&gt;&lt;span class="o"&gt;::&lt;/span&gt;&lt;span class="n"&gt;memory_order_relaxed&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt; &lt;span class="c1"&gt;// Hardware Atomic!&lt;/span&gt;
    &lt;span class="p"&gt;}&lt;/span&gt;
&lt;span class="p"&gt;}&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;On x86, this compiles to the hardware instruction &lt;code&gt;lock inc [counter]&lt;/code&gt;, asserting the CPU bus lock and guaranteeing atomic execution.&lt;/p&gt;

&lt;p&gt;Read the full systems engineering breakdown at &lt;a href="https://binarydose.in/blog/2-volatile-is-not-thread-safe" rel="noopener noreferrer"&gt;Binary Dose&lt;/a&gt;.&lt;/p&gt;

</description>
      <category>cprogramming</category>
      <category>cpp</category>
      <category>concurrency</category>
      <category>systemsengineering</category>
    </item>
    <item>
      <title>When Normalization Hurts: The 3NF vs BCNF Trade-off</title>
      <dc:creator>Binary Dose</dc:creator>
      <pubDate>Sat, 14 Nov 2026 18:53:01 +0000</pubDate>
      <link>https://dev.to/binarydose/when-normalization-hurts-the-3nf-vs-bcnf-trade-off-332m</link>
      <guid>https://dev.to/binarydose/when-normalization-hurts-the-3nf-vs-bcnf-trade-off-332m</guid>
      <description>&lt;h1&gt;
  
  
  When Normalization Hurts: The 3NF vs BCNF Trade-off
&lt;/h1&gt;

&lt;p&gt;Database normalization is the systematic process of decomposing relational tables to eliminate redundancy and insertion, update, and deletion anomalies.&lt;/p&gt;

&lt;p&gt;By the time developers reach &lt;strong&gt;Third Normal Form (3NF)&lt;/strong&gt; and &lt;strong&gt;Boyce-Codd Normal Form (BCNF)&lt;/strong&gt;, a natural assumption arises: higher normal forms are always superior.&lt;/p&gt;

&lt;p&gt;Yet in database administration and distributed system architecture, schemas are routinely left in 3NF rather than decomposed into BCNF.&lt;/p&gt;

&lt;p&gt;Here is the mathematical dilemma.&lt;/p&gt;




&lt;h2&gt;
  
  
  1. The Core Definitions
&lt;/h2&gt;

&lt;p&gt;For every non-trivial Functional Dependency (FD) &lt;code&gt;X → Y&lt;/code&gt;:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;BCNF&lt;/strong&gt;: &lt;code&gt;X&lt;/code&gt; &lt;strong&gt;must be a Superkey&lt;/strong&gt;.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;3NF&lt;/strong&gt;: &lt;code&gt;X&lt;/code&gt; must be a Superkey &lt;strong&gt;OR&lt;/strong&gt; &lt;code&gt;Y&lt;/code&gt; must be a &lt;strong&gt;Prime Attribute&lt;/strong&gt; (an attribute participating in at least one candidate key).&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;3NF is an intentional compromise: it permits dependencies where the determinant &lt;code&gt;X&lt;/code&gt; is not a superkey, provided the dependent attribute &lt;code&gt;Y&lt;/code&gt; is prime.&lt;/p&gt;




&lt;h2&gt;
  
  
  2. The Classic Failure Case of BCNF
&lt;/h2&gt;

&lt;p&gt;Consider a student advising database:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;Advisor(Student, Advisor, Department)
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;With constraints:&lt;/p&gt;

&lt;ol&gt;
&lt;li&gt;Each student has one advisor per department: &lt;code&gt;(Student, Department) → Advisor&lt;/code&gt;
&lt;/li&gt;
&lt;li&gt;Each advisor belongs to exactly one department: &lt;code&gt;Advisor → Department&lt;/code&gt;
&lt;/li&gt;
&lt;/ol&gt;

&lt;h3&gt;
  
  
  Candidate Keys:
&lt;/h3&gt;

&lt;ul&gt;
&lt;li&gt;&lt;code&gt;(Student, Department)&lt;/code&gt;&lt;/li&gt;
&lt;li&gt;&lt;code&gt;(Student, Advisor)&lt;/code&gt;&lt;/li&gt;
&lt;/ul&gt;

&lt;h3&gt;
  
  
  Normal Form Analysis:
&lt;/h3&gt;

&lt;ul&gt;
&lt;li&gt;In &lt;code&gt;Advisor → Department&lt;/code&gt;, the determinant &lt;code&gt;Advisor&lt;/code&gt; is &lt;strong&gt;not a superkey&lt;/strong&gt;.&lt;/li&gt;
&lt;li&gt;However, &lt;code&gt;Department&lt;/code&gt; is part of the candidate key &lt;code&gt;(Student, Department)&lt;/code&gt;, making it a &lt;strong&gt;Prime Attribute&lt;/strong&gt;.&lt;/li&gt;
&lt;li&gt;Therefore, the relation is in &lt;strong&gt;3NF&lt;/strong&gt;, but &lt;strong&gt;NOT in BCNF&lt;/strong&gt;!&lt;/li&gt;
&lt;/ul&gt;

&lt;h3&gt;
  
  
  The BCNF Decomposition:
&lt;/h3&gt;

&lt;p&gt;To achieve BCNF, we must split the table:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;&lt;code&gt;R₁(Advisor, Department)&lt;/code&gt;&lt;/li&gt;
&lt;li&gt;&lt;code&gt;R₂(Student, Advisor)&lt;/code&gt;&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;Both tables are now in BCNF. But look at what was lost:&lt;br&gt;
The original dependency &lt;strong&gt;&lt;code&gt;(Student, Department) → Advisor&lt;/code&gt;&lt;/strong&gt; spans attributes from both tables!&lt;/p&gt;

&lt;p&gt;To enforce this constraint upon every &lt;code&gt;INSERT&lt;/code&gt;, the database engine must execute an expensive &lt;strong&gt;cross-table JOIN&lt;/strong&gt;.&lt;/p&gt;




&lt;h2&gt;
  
  
  3. The Normalization Hierarchy Theorem
&lt;/h2&gt;

&lt;ol&gt;
&lt;li&gt;A &lt;strong&gt;Lossless-Join Decomposition&lt;/strong&gt; is always achievable in both 3NF and BCNF.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Dependency Preservation&lt;/strong&gt; is &lt;strong&gt;always achievable in 3NF&lt;/strong&gt;.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Dependency Preservation is NOT always achievable in BCNF&lt;/strong&gt;.&lt;/li&gt;
&lt;/ol&gt;

&lt;p&gt;Because verifying functional dependencies across tables degrades write throughput, production database systems overwhelmingly choose 3NF.&lt;/p&gt;

&lt;p&gt;Explore functional dependency solvers and minimal covers at &lt;a href="https://binarydose.in/coredose/dbms/chapter-06/third-normal-form-3nf-vs-bcnf" rel="noopener noreferrer"&gt;Binary Dose&lt;/a&gt;.&lt;/p&gt;

</description>
      <category>dbms</category>
      <category>sql</category>
      <category>database</category>
      <category>systemdesign</category>
    </item>
    <item>
      <title>Stopping Tinygrams: Silly Window Syndrome and Nagle's Algorithm</title>
      <dc:creator>Binary Dose</dc:creator>
      <pubDate>Sat, 14 Nov 2026 11:29:40 +0000</pubDate>
      <link>https://dev.to/binarydose/stopping-tinygrams-silly-window-syndrome-and-nagles-algorithm-3e6a</link>
      <guid>https://dev.to/binarydose/stopping-tinygrams-silly-window-syndrome-and-nagles-algorithm-3e6a</guid>
      <description>&lt;h1&gt;
  
  
  Stopping Tinygrams: Silly Window Syndrome and Nagle's Algorithm
&lt;/h1&gt;

&lt;p&gt;Every TCP/IP packet incurs a mandatory protocol header overhead:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;IPv4 Header&lt;/strong&gt;: 20 bytes (minimum)&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;TCP Header&lt;/strong&gt;: 20 bytes (minimum)&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Total Overhead&lt;/strong&gt;: 40 bytes&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;When an interactive application transmits small data chunks (such as single keystrokes over Telnet or SSH), transmitting 1 byte of user data inside a 41-byte datagram results in an appalling &lt;strong&gt;4,000% header overhead&lt;/strong&gt;.&lt;/p&gt;

&lt;p&gt;Left unchecked, this dynamic triggers &lt;strong&gt;Silly Window Syndrome (SWS)&lt;/strong&gt;, choking high-speed networks under waves of &lt;em&gt;tinygrams&lt;/em&gt;.&lt;/p&gt;




&lt;h2&gt;
  
  
  1. Silly Window Syndrome: The Receiver's Role
&lt;/h2&gt;

&lt;p&gt;Silly Window Syndrome occurs when:&lt;/p&gt;

&lt;ol&gt;
&lt;li&gt;The receiving application consumes data slowly (e.g., calling &lt;code&gt;read()&lt;/code&gt; for 1 byte at a time).&lt;/li&gt;
&lt;li&gt;The receiver advertises an updated Receive Window (&lt;code&gt;rwnd&lt;/code&gt;) of 1 byte.&lt;/li&gt;
&lt;li&gt;The sender immediately transmits a 1-byte segment.&lt;/li&gt;
&lt;li&gt;The cycle repeats continuously, locking the connection into 1-byte transmissions.&lt;/li&gt;
&lt;/ol&gt;

&lt;h3&gt;
  
  
  Clark's Receiver Solution:
&lt;/h3&gt;

&lt;p&gt;To prevent receiver-driven SWS, &lt;strong&gt;Clark's Algorithm&lt;/strong&gt; instructs the receiver to refuse advertising tiny windows:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;The receiver advertises &lt;code&gt;rwnd = 0&lt;/code&gt; until it can accommodate:
&lt;/li&gt;
&lt;/ul&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;Free Space ≥ min(MSS, (Buffer Size / 2))
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Once this threshold is reached, the receiver opens the window with a large update.&lt;/p&gt;




&lt;h2&gt;
  
  
  2. Nagle's Algorithm: The Sender's Role
&lt;/h2&gt;

&lt;p&gt;Published in RFC 896 by John Nagle, &lt;strong&gt;Nagle's Algorithm&lt;/strong&gt; prevents the sender from emitting tinygrams:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;if there is new data to send:
    if the window size &amp;gt;= MSS and available data &amp;gt;= MSS:
        send complete MSS segment immediately
    else:
        if there is unconfirmed data in flight (waiting for ACK):
            buffer data in memory until previous ACK arrives
        else:
            send the data immediately
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;h3&gt;
  
  
  Key Intuition:
&lt;/h3&gt;

&lt;ul&gt;
&lt;li&gt;The sender sends the first packet immediately (ensuring zero latency for initial writes).&lt;/li&gt;
&lt;li&gt;While waiting for the roundtrip ACK, subsequent small writes are automatically coalesced into a single larger buffer.&lt;/li&gt;
&lt;/ul&gt;




&lt;h2&gt;
  
  
  3. The Modern Gotcha: Nagle vs Delayed ACK
&lt;/h2&gt;

&lt;p&gt;Modern operating systems enable &lt;strong&gt;Delayed ACKs&lt;/strong&gt; (waiting 40ms–200ms before sending an ACK to piggyback on return data).&lt;/p&gt;

&lt;p&gt;When Nagle's Algorithm (waiting for an ACK) meets Delayed ACKs (waiting for data to send an ACK), the connection deadlocks in a &lt;strong&gt;200ms latency pause&lt;/strong&gt;!&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Fix&lt;/strong&gt;: For interactive applications, real-time gaming, and microservices (gRPC), disable Nagle's algorithm by setting the socket option:
&lt;/li&gt;
&lt;/ul&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight c"&gt;&lt;code&gt;&lt;span class="kt"&gt;int&lt;/span&gt; &lt;span class="n"&gt;flag&lt;/span&gt; &lt;span class="o"&gt;=&lt;/span&gt; &lt;span class="mi"&gt;1&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;span class="nf"&gt;setsockopt&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;sock&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="no"&gt;IPPROTO_TCP&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="no"&gt;TCP_NODELAY&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;char&lt;/span&gt; &lt;span class="o"&gt;*&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="o"&gt;&amp;amp;&lt;/span&gt;&lt;span class="n"&gt;flag&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="k"&gt;sizeof&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="kt"&gt;int&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;)&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Explore full TCP transport architectures at &lt;a href="https://binarydose.in/coredose/cn/module-07/tcp-sliding-window-flow-control-and-silly-window-syndrome" rel="noopener noreferrer"&gt;Binary Dose&lt;/a&gt;.&lt;/p&gt;

</description>
      <category>computernetworks</category>
      <category>protocols</category>
      <category>systemdesign</category>
      <category>linux</category>
    </item>
    <item>
      <title>More RAM, More Faults: Belady's Anomaly in FIFO Page Replacement</title>
      <dc:creator>Binary Dose</dc:creator>
      <pubDate>Fri, 13 Nov 2026 20:40:36 +0000</pubDate>
      <link>https://dev.to/binarydose/more-ram-more-faults-beladys-anomaly-in-fifo-page-replacement-4d5n</link>
      <guid>https://dev.to/binarydose/more-ram-more-faults-beladys-anomaly-in-fifo-page-replacement-4d5n</guid>
      <description>&lt;h1&gt;
  
  
  More RAM, More Faults: Belady's Anomaly in FIFO Page Replacement
&lt;/h1&gt;

&lt;p&gt;Intuition suggests that allocating more physical memory (RAM frames) to a process must either decrease the number of page faults or, in the worst case, keep them unchanged.&lt;/p&gt;

&lt;p&gt;Yet in 1969, computer scientist László Bélády proved a startling paradox: under &lt;strong&gt;First-In, First-Out (FIFO)&lt;/strong&gt; page replacement, &lt;strong&gt;increasing the number of page frames can actually increase the total page faults&lt;/strong&gt;.&lt;/p&gt;

&lt;p&gt;This phenomenon is known as &lt;strong&gt;Bélády's Anomaly&lt;/strong&gt;.&lt;/p&gt;




&lt;h2&gt;
  
  
  1. The Mathematical Counterexample
&lt;/h2&gt;

&lt;p&gt;Consider the following reference string of page requests:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;σ = 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;h3&gt;
  
  
  Trace A: 3 Page Frames
&lt;/h3&gt;

&lt;ul&gt;
&lt;li&gt;Tracing FIFO replacement through the 12 memory accesses results in &lt;strong&gt;9 Page Faults&lt;/strong&gt;.&lt;/li&gt;
&lt;/ul&gt;

&lt;h3&gt;
  
  
  Trace B: 4 Page Frames
&lt;/h3&gt;

&lt;ul&gt;
&lt;li&gt;Expanding physical allocation to 4 frames results in &lt;strong&gt;10 Page Faults&lt;/strong&gt;!&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;Adding a 4th physical frame increases total page faults by 11%.&lt;/p&gt;




&lt;h2&gt;
  
  
  2. Why FIFO Suffers: The Lack of Locality
&lt;/h2&gt;

&lt;p&gt;FIFO replacement selects the page that has been in memory the longest time. &lt;/p&gt;

&lt;p&gt;Crucially, &lt;strong&gt;the age of a page has no correlation with its future utility&lt;/strong&gt;. When a 4th frame is added, the timing of page evictions shifts. A frequently accessed page that happened to survive under 3 frames is prematurely evicted under 4 frames, triggering an avalanche of subsequent faults.&lt;/p&gt;




&lt;h2&gt;
  
  
  3. Why LRU Is Immune: The Stack Inclusion Property
&lt;/h2&gt;

&lt;p&gt;Why does &lt;strong&gt;Least Recently Used (LRU)&lt;/strong&gt; never exhibit Bélády's Anomaly?&lt;/p&gt;

&lt;p&gt;LRU belongs to a mathematical class known as &lt;strong&gt;Stack Algorithms&lt;/strong&gt;.&lt;br&gt;
A page replacement algorithm is a stack algorithm if it satisfies the &lt;strong&gt;Inclusion Property&lt;/strong&gt;:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;B(M, t) ⊆ B(M+1, t)
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;&lt;em&gt;Where &lt;code&gt;B(M, t)&lt;/code&gt; represents the set of pages present in memory of size &lt;code&gt;M&lt;/code&gt; at time &lt;code&gt;t&lt;/code&gt;.&lt;/em&gt;&lt;/p&gt;

&lt;p&gt;In LRU, the top &lt;code&gt;M&lt;/code&gt; most recently used pages are &lt;em&gt;always&lt;/em&gt; a strict subset of the top &lt;code&gt;M+1&lt;/code&gt; most recently used pages. Therefore:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;Any memory hit under &lt;code&gt;M&lt;/code&gt; frames is &lt;strong&gt;guaranteed&lt;/strong&gt; to be a hit under &lt;code&gt;M+1&lt;/code&gt; frames.&lt;/li&gt;
&lt;li&gt;Adding RAM can &lt;strong&gt;never&lt;/strong&gt; increase page faults under LRU or Optimal replacement!&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;Explore interactive page replacement simulations at &lt;a href="https://binarydose.in/coredose/os/chapter-08/page-replacement-algorithms-fifo-and-beladys-anomaly" rel="noopener noreferrer"&gt;Binary Dose&lt;/a&gt;.&lt;/p&gt;

</description>
      <category>operatingsystems</category>
      <category>computermemory</category>
      <category>algorithms</category>
      <category>computerscience</category>
    </item>
    <item>
      <title>Killing Deadlocks Before They Form: Wait-Die vs Wound-Wait Schemes</title>
      <dc:creator>Binary Dose</dc:creator>
      <pubDate>Thu, 12 Nov 2026 21:10:29 +0000</pubDate>
      <link>https://dev.to/binarydose/killing-deadlocks-before-they-form-wait-die-vs-wound-wait-schemes-283e</link>
      <guid>https://dev.to/binarydose/killing-deadlocks-before-they-form-wait-die-vs-wound-wait-schemes-283e</guid>
      <description>&lt;h1&gt;
  
  
  Killing Deadlocks Before They Form: Wait-Die vs Wound-Wait Schemes
&lt;/h1&gt;

&lt;p&gt;In relational database systems running under Two-Phase Locking (2PL), deadlock is an inevitable side effect of concurrent lock acquisition.&lt;/p&gt;

&lt;p&gt;Traditionally, databases employ &lt;strong&gt;Deadlock Detection&lt;/strong&gt;: the engine builds a &lt;em&gt;Wait-For Graph&lt;/em&gt; in memory, runs cycle-detection algorithms (e.g., Tarjan's or DFS), and selects a victim to abort when a cycle forms.&lt;/p&gt;

&lt;p&gt;However, in ultra-high-throughput systems, constantly searching for cycles introduces significant locking overhead.&lt;/p&gt;

&lt;p&gt;Instead, database engines can employ &lt;strong&gt;Timestamp-Based Deadlock Prevention&lt;/strong&gt;: &lt;strong&gt;Wait-Die&lt;/strong&gt; and &lt;strong&gt;Wound-Wait&lt;/strong&gt;.&lt;/p&gt;




&lt;h2&gt;
  
  
  1. The Timestamp Precedence Rule
&lt;/h2&gt;

&lt;p&gt;Every transaction &lt;code&gt;T_i&lt;/code&gt; is assigned a monotonically increasing timestamp &lt;code&gt;TS(T_i)&lt;/code&gt; when it begins.&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;If &lt;code&gt;TS(T_i) &amp;lt; TS(T_j)&lt;/code&gt;, &lt;code&gt;T_i&lt;/code&gt; is &lt;strong&gt;older&lt;/strong&gt; (senior).&lt;/li&gt;
&lt;li&gt;If &lt;code&gt;TS(T_i) &amp;gt; TS(T_j)&lt;/code&gt;, &lt;code&gt;T_i&lt;/code&gt; is &lt;strong&gt;younger&lt;/strong&gt; (junior).&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;A deadlock requires a cyclic dependency chain:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;T₁ → T₂ → ... → T_n → T₁
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;By enforcing strict directional rules based on age, cyclic dependencies become mathematically impossible.&lt;/p&gt;




&lt;h2&gt;
  
  
  2. The Wait-Die Scheme (Non-Preemptive)
&lt;/h2&gt;

&lt;p&gt;Suppose transaction &lt;code&gt;T_i&lt;/code&gt; requests a lock currently held by &lt;code&gt;T_j&lt;/code&gt;:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;If &lt;code&gt;T_i&lt;/code&gt; is older than &lt;code&gt;T_j&lt;/code&gt; (&lt;code&gt;extTS(T_i) &amp;lt; extTS(T_j)&lt;/code&gt;)&lt;/strong&gt;:

&lt;ul&gt;
&lt;li&gt;
&lt;code&gt;T_i&lt;/code&gt; is allowed to &lt;strong&gt;WAIT&lt;/strong&gt; until &lt;code&gt;T_j&lt;/code&gt; releases the lock.&lt;/li&gt;
&lt;/ul&gt;
&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;If &lt;code&gt;T_i&lt;/code&gt; is younger than &lt;code&gt;T_j&lt;/code&gt; (&lt;code&gt;extTS(T_i) &amp;gt; extTS(T_j)&lt;/code&gt;)&lt;/strong&gt;:

&lt;ul&gt;
&lt;li&gt;
&lt;code&gt;T_i&lt;/code&gt; &lt;strong&gt;DIES&lt;/strong&gt; (aborts, rolls back its mutations, and restarts).&lt;/li&gt;
&lt;/ul&gt;
&lt;/li&gt;
&lt;/ul&gt;

&lt;h3&gt;
  
  
  Intuition:
&lt;/h3&gt;

&lt;p&gt;Only older transactions may wait for younger transactions. A younger transaction can never wait for an older one, making cycles impossible.&lt;/p&gt;




&lt;h2&gt;
  
  
  3. The Wound-Wait Scheme (Preemptive)
&lt;/h2&gt;

&lt;p&gt;Suppose transaction &lt;code&gt;T_i&lt;/code&gt; requests a lock currently held by &lt;code&gt;T_j&lt;/code&gt;:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;If &lt;code&gt;T_i&lt;/code&gt; is older than &lt;code&gt;T_j&lt;/code&gt; (&lt;code&gt;extTS(T_i) &amp;lt; extTS(T_j)&lt;/code&gt;)&lt;/strong&gt;:

&lt;ul&gt;
&lt;li&gt;
&lt;code&gt;T_i&lt;/code&gt; &lt;strong&gt;WOUNDS&lt;/strong&gt; &lt;code&gt;T_j&lt;/code&gt;. The engine immediately preempts and aborts &lt;code&gt;T_j&lt;/code&gt;, granting the lock to &lt;code&gt;T_i&lt;/code&gt;.&lt;/li&gt;
&lt;/ul&gt;
&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;If &lt;code&gt;T_i&lt;/code&gt; is younger than &lt;code&gt;T_j&lt;/code&gt; (&lt;code&gt;extTS(T_i) &amp;gt; extTS(T_j)&lt;/code&gt;)&lt;/strong&gt;:

&lt;ul&gt;
&lt;li&gt;
&lt;code&gt;T_i&lt;/code&gt; is allowed to &lt;strong&gt;WAIT&lt;/strong&gt; for &lt;code&gt;T_j&lt;/code&gt;.&lt;/li&gt;
&lt;/ul&gt;
&lt;/li&gt;
&lt;/ul&gt;




&lt;h2&gt;
  
  
  4. Preventing Starvation
&lt;/h2&gt;

&lt;p&gt;In both schemes, when an aborted transaction restarts, it &lt;strong&gt;retains its original timestamp&lt;/strong&gt;.&lt;/p&gt;

&lt;p&gt;As time progresses, an aborted transaction becomes progressively older relative to newly arriving transactions. Eventually, it becomes the oldest transaction in the system, guaranteeing it will never be aborted again.&lt;/p&gt;

&lt;p&gt;Explore full database concurrency control architectures at &lt;a href="https://binarydose.in/coredose/dbms/chapter-08/deadlock-handling-wait-die-vs-wound-wait" rel="noopener noreferrer"&gt;Binary Dose&lt;/a&gt;.&lt;/p&gt;

</description>
      <category>dbms</category>
      <category>database</category>
      <category>systemdesign</category>
      <category>sql</category>
    </item>
    <item>
      <title>Behind Routing Tables: CIDR and the Longest Prefix Match Rule</title>
      <dc:creator>Binary Dose</dc:creator>
      <pubDate>Thu, 12 Nov 2026 12:45:00 +0000</pubDate>
      <link>https://dev.to/binarydose/behind-routing-tables-cidr-and-the-longest-prefix-match-rule-4bfl</link>
      <guid>https://dev.to/binarydose/behind-routing-tables-cidr-and-the-longest-prefix-match-rule-4bfl</guid>
      <description>&lt;h1&gt;
  
  
  Behind Routing Tables: CIDR and the Longest Prefix Match Rule
&lt;/h1&gt;

&lt;p&gt;The global Internet routing table currently exceeds &lt;strong&gt;1,000,000 routes&lt;/strong&gt;.&lt;/p&gt;

&lt;p&gt;Yet a backbone router must inspect the destination IP address of an incoming packet, find the correct outgoing interface, and forward the packet in under &lt;strong&gt;10 nanoseconds&lt;/strong&gt; to sustain 100 Gbps line-rate throughput.&lt;/p&gt;

&lt;p&gt;The scalability of the entire Internet rests on &lt;strong&gt;Classless Inter-Domain Routing (CIDR)&lt;/strong&gt; and the &lt;strong&gt;Longest Prefix Match (LPM)&lt;/strong&gt; algorithm.&lt;/p&gt;




&lt;h2&gt;
  
  
  1. CIDR and Route Aggregation (Supernetting)
&lt;/h2&gt;

&lt;p&gt;Before 1993, IP addresses were bound to rigid classes:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Class A&lt;/strong&gt;: &lt;code&gt;/8&lt;/code&gt; (16 million hosts)&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Class B&lt;/strong&gt;: &lt;code&gt;/16&lt;/code&gt; (65,536 hosts)&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Class C&lt;/strong&gt;: &lt;code&gt;/24&lt;/code&gt; (256 hosts)&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;Organizations needing 2,000 IPs were forced to request an entire Class B block, wasting 63,000 addresses. Furthermore, every network required its own routing table entry.&lt;/p&gt;

&lt;p&gt;&lt;strong&gt;CIDR&lt;/strong&gt; introduced variable-length subnet masks (&lt;code&gt;/n&lt;/code&gt;). Upstream Internet Service Providers (ISPs) aggregate contiguous subnets into a single supernet route:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;Instead of advertising sixteen separate &lt;code&gt;/24&lt;/code&gt; subnets, an ISP announces a single &lt;code&gt;/20&lt;/code&gt; prefix to the global BGP routing table.&lt;/li&gt;
&lt;/ul&gt;




&lt;h2&gt;
  
  
  2. The Overlapping Route Dilemma
&lt;/h2&gt;

&lt;p&gt;Route aggregation inevitably creates overlapping routing entries:&lt;/p&gt;

&lt;div class="table-wrapper-paragraph"&gt;&lt;table&gt;
&lt;thead&gt;
&lt;tr&gt;
&lt;th&gt;Network Destination&lt;/th&gt;
&lt;th&gt;Subnet Mask&lt;/th&gt;
&lt;th&gt;Next Hop Interface&lt;/th&gt;
&lt;/tr&gt;
&lt;/thead&gt;
&lt;tbody&gt;
&lt;tr&gt;
&lt;td&gt;&lt;code&gt;192.168.0.0&lt;/code&gt;&lt;/td&gt;
&lt;td&gt;&lt;code&gt;/16&lt;/code&gt;&lt;/td&gt;
&lt;td&gt;&lt;code&gt;eth0&lt;/code&gt;&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;&lt;code&gt;192.168.1.0&lt;/code&gt;&lt;/td&gt;
&lt;td&gt;&lt;code&gt;/24&lt;/code&gt;&lt;/td&gt;
&lt;td&gt;&lt;code&gt;eth1&lt;/code&gt;&lt;/td&gt;
&lt;/tr&gt;
&lt;tr&gt;
&lt;td&gt;&lt;code&gt;0.0.0.0&lt;/code&gt;&lt;/td&gt;
&lt;td&gt;
&lt;code&gt;/0&lt;/code&gt; (Default)&lt;/td&gt;
&lt;td&gt;&lt;code&gt;eth2&lt;/code&gt;&lt;/td&gt;
&lt;/tr&gt;
&lt;/tbody&gt;
&lt;/table&gt;&lt;/div&gt;

&lt;p&gt;Suppose a packet arrives with destination IP &lt;code&gt;192.168.1.55&lt;/code&gt;:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;Bitwise AND with &lt;code&gt;/16&lt;/code&gt; yields &lt;code&gt;192.168.0.0&lt;/code&gt; &lt;code&gt;implies&lt;/code&gt; &lt;strong&gt;Matches &lt;code&gt;eth0&lt;/code&gt;&lt;/strong&gt;.&lt;/li&gt;
&lt;li&gt;Bitwise AND with &lt;code&gt;/24&lt;/code&gt; yields &lt;code&gt;192.168.1.0&lt;/code&gt; &lt;code&gt;implies&lt;/code&gt; &lt;strong&gt;Matches &lt;code&gt;eth1&lt;/code&gt;&lt;/strong&gt;.&lt;/li&gt;
&lt;li&gt;Bitwise AND with &lt;code&gt;/0&lt;/code&gt; yields &lt;code&gt;0.0.0.0&lt;/code&gt; &lt;code&gt;implies&lt;/code&gt; &lt;strong&gt;Matches &lt;code&gt;eth2&lt;/code&gt;&lt;/strong&gt;.&lt;/li&gt;
&lt;/ul&gt;




&lt;h2&gt;
  
  
  3. The Longest Prefix Match Rule
&lt;/h2&gt;

&lt;blockquote&gt;
&lt;p&gt;&lt;strong&gt;When a packet destination matches multiple routes, the router forwards the packet out the interface associated with the longest prefix length (the most specific route).&lt;/strong&gt;&lt;/p&gt;
&lt;/blockquote&gt;

&lt;p&gt;In our example, &lt;code&gt;/24&lt;/code&gt; has 24 matching network bits, compared to 16 bits for &lt;code&gt;/16&lt;/code&gt;. The router selects &lt;strong&gt;&lt;code&gt;eth1&lt;/code&gt;&lt;/strong&gt;.&lt;/p&gt;

&lt;h3&gt;
  
  
  Hardware Implementation:
&lt;/h3&gt;

&lt;p&gt;Software linear search across 1,000,000 routes is too slow. Modern core routers use:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Patricia Tries / Radix Trees&lt;/strong&gt;: Hierarchical prefix trees traversed bit by bit.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Ternary Content Addressable Memory (TCAM)&lt;/strong&gt;: Specialized associative hardware that searches all 1,000,000 prefixes in parallel in a single clock cycle (&lt;code&gt;&amp;lt;5ns&lt;/code&gt;).&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;Explore full IP networking architectures and subnetting calculators at &lt;a href="https://binarydose.in/coredose/cn/module-04/classless-inter-domain-routing-cidr-and-subnetting" rel="noopener noreferrer"&gt;Binary Dose&lt;/a&gt;.&lt;/p&gt;

</description>
      <category>computernetworks</category>
      <category>networking</category>
      <category>systemdesign</category>
      <category>softwareengineering</category>
    </item>
    <item>
      <title>The Cost of Virtual Memory: TLBs and Effective Memory Access Time</title>
      <dc:creator>Binary Dose</dc:creator>
      <pubDate>Wed, 11 Nov 2026 11:53:53 +0000</pubDate>
      <link>https://dev.to/binarydose/the-cost-of-virtual-memory-tlbs-and-effective-memory-access-time-1hbf</link>
      <guid>https://dev.to/binarydose/the-cost-of-virtual-memory-tlbs-and-effective-memory-access-time-1hbf</guid>
      <description>&lt;h1&gt;
  
  
  The Cost of Virtual Memory: TLBs and Effective Memory Access Time
&lt;/h1&gt;

&lt;p&gt;Virtual memory provides every user process with a private, uniform address space protected from neighboring applications.&lt;/p&gt;

&lt;p&gt;However, address translation incurs an inherent architectural penalty: &lt;strong&gt;every memory reference requires translating a virtual address into a physical address&lt;/strong&gt;.&lt;/p&gt;




&lt;h2&gt;
  
  
  1. The Two-Access Penalty
&lt;/h2&gt;

&lt;p&gt;Because the Page Table is itself a data structure stored in main memory (RAM):&lt;/p&gt;

&lt;ol&gt;
&lt;li&gt;
&lt;strong&gt;Access 1&lt;/strong&gt;: The MMU reads the Page Table entry in RAM to translate the Virtual Page Number (VPN) into a Physical Frame Number (PFN).&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Access 2&lt;/strong&gt;: The CPU accesses the actual data byte at the physical address.&lt;/li&gt;
&lt;/ol&gt;

&lt;p&gt;Without hardware acceleration, virtual memory doubles the latency of every instruction! In 64-bit systems with 4-level paging, a naive lookup requires &lt;strong&gt;5 sequential memory accesses&lt;/strong&gt; per operation.&lt;/p&gt;




&lt;h2&gt;
  
  
  2. The Translation Lookaside Buffer (TLB)
&lt;/h2&gt;

&lt;p&gt;To eliminate this bottleneck, the Memory Management Unit (MMU) incorporates a small, high-speed associative hardware cache: the &lt;strong&gt;Translation Lookaside Buffer (TLB)&lt;/strong&gt;.&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Associative Search&lt;/strong&gt;: All TLB entries are compared simultaneously in parallel, resolving in sub-nanosecond time (&lt;code&gt;c&lt;/code&gt;).&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;TLB Hit&lt;/strong&gt;: The VPN is cached in the TLB. The physical frame number is returned immediately, requiring only &lt;strong&gt;1 main memory access&lt;/strong&gt;.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;TLB Miss&lt;/strong&gt;: The translation is absent. The MMU must walk the Page Table in RAM, requiring &lt;strong&gt;2 main memory accesses&lt;/strong&gt; (or &lt;code&gt;k+1&lt;/code&gt; for &lt;code&gt;k&lt;/code&gt;-level paging).&lt;/li&gt;
&lt;/ul&gt;




&lt;h2&gt;
  
  
  3. Effective Memory Access Time (EMAT) Formula
&lt;/h2&gt;

&lt;p&gt;Let:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;code&gt;h&lt;/code&gt; = TLB Hit Ratio&lt;/li&gt;
&lt;li&gt;
&lt;code&gt;c&lt;/code&gt; = TLB Lookup Time&lt;/li&gt;
&lt;li&gt;
&lt;code&gt;m&lt;/code&gt; = Main Memory Access Time
&lt;/li&gt;
&lt;/ul&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;EMAT = h · (c + m) + (1 - h) · (c + 2m)
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;h3&gt;
  
  
  Worked Example:
&lt;/h3&gt;

&lt;p&gt;Assume main memory access time &lt;code&gt;m = 100ns&lt;/code&gt;, TLB lookup time &lt;code&gt;c = 10ns&lt;/code&gt;, and hit ratio &lt;code&gt;h = 98\%&lt;/code&gt;:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;EMAT = 0.98 · (10 + 100) + 0.02 · (10 + 200)
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;





&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;EMAT = 0.98 · 110 + 0.02 · 210 = 107.8 + 4.2 = 112ns
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Despite paging overhead, the Effective Memory Access Time is only &lt;code&gt;12ns&lt;/code&gt; higher than raw physical RAM!&lt;/p&gt;

&lt;p&gt;Explore interactive virtual address translation rails at &lt;a href="https://binarydose.in/coredose/os/chapter-07/translation-lookaside-buffer-tlb-and-emat" rel="noopener noreferrer"&gt;Binary Dose&lt;/a&gt;.&lt;/p&gt;

</description>
      <category>operatingsystems</category>
      <category>computermemory</category>
      <category>hardware</category>
      <category>computerscience</category>
    </item>
    <item>
      <title>Why OS Virtual Memory Paging Saved LLM Inference: The vLLM Breakthrough</title>
      <dc:creator>Binary Dose</dc:creator>
      <pubDate>Tue, 10 Nov 2026 20:38:13 +0000</pubDate>
      <link>https://dev.to/binarydose/why-os-virtual-memory-paging-saved-llm-inference-the-vllm-breakthrough-19ha</link>
      <guid>https://dev.to/binarydose/why-os-virtual-memory-paging-saved-llm-inference-the-vllm-breakthrough-19ha</guid>
      <description>&lt;h1&gt;
  
  
  Why OS Virtual Memory Paging Saved LLM Inference: The vLLM Breakthrough
&lt;/h1&gt;

&lt;p&gt;In high-throughput Large Language Model (LLM) serving, the primary hardware bottleneck is rarely raw compute (FLOPs)—it is &lt;strong&gt;GPU High-Bandwidth Memory (VRAM)&lt;/strong&gt;.&lt;/p&gt;

&lt;p&gt;Specifically, the auto-regressive generation of tokens requires saving the Key and Value attention matrices for every preceding token: the &lt;strong&gt;KV Cache&lt;/strong&gt;.&lt;/p&gt;

&lt;p&gt;Until the introduction of &lt;strong&gt;PagedAttention (vLLM)&lt;/strong&gt; in 2023, standard serving systems (like HuggingFace and v1 inference engines) wasted between &lt;strong&gt;60% and 80% of all GPU memory&lt;/strong&gt;.&lt;/p&gt;

&lt;p&gt;The solution didn't come from new AI algorithms; it came from a 50-year-old operating systems concept: &lt;strong&gt;Virtual Memory Paging&lt;/strong&gt;.&lt;/p&gt;




&lt;h2&gt;
  
  
  1. The Contiguous Allocation Problem
&lt;/h2&gt;

&lt;p&gt;In standard self-attention, the key and value vectors of a sequence must be stored in contiguous physical memory so that CUDA matrix kernels can execute efficiently.&lt;/p&gt;

&lt;p&gt;Because the system cannot predict how many tokens an LLM will generate before emitting the &lt;code&gt;&amp;lt;EOS&amp;gt;&lt;/code&gt; stop token, traditional engines pre-allocated contiguous memory slots for the &lt;strong&gt;maximum request length&lt;/strong&gt; (e.g., 2,048 or 4,096 tokens).&lt;/p&gt;

&lt;h3&gt;
  
  
  Two Forms of Memory Waste:
&lt;/h3&gt;

&lt;ol&gt;
&lt;li&gt;
&lt;strong&gt;Internal Fragmentation&lt;/strong&gt;: If a request pre-allocates 2,048 tokens but stops after 150 tokens, the remaining 1,898 slots sit reserved and completely idle.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;External Fragmentation&lt;/strong&gt;: Because requests start and finish dynamically, allocating contiguous variable-sized memory blocks creates fragmented holes in GPU VRAM, preventing new batches from scheduling.&lt;/li&gt;
&lt;/ol&gt;




&lt;h2&gt;
  
  
  2. The PagedAttention Architecture
&lt;/h2&gt;

&lt;p&gt;PagedAttention resolves this by relaxing the requirement that KV vectors be stored in contiguous physical memory.&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;KV Blocks&lt;/strong&gt;: The KV cache is divided into fixed-size physical blocks (e.g., 16 tokens per block).&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Block Table&lt;/strong&gt;: Identical to an Operating System's &lt;strong&gt;Page Table&lt;/strong&gt;, the engine maintains a mapping between logical token positions and physical GPU memory blocks.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;On-Demand Allocation&lt;/strong&gt;: Physical blocks are allocated one by one only as new tokens are generated.&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;When computing attention for a newly generated token, the custom CUDA kernel looks up the physical block addresses in the block table, fetching key-value vectors on the fly from non-contiguous memory locations.&lt;/p&gt;




&lt;h2&gt;
  
  
  3. Copy-on-Write for Prompt Sharing
&lt;/h2&gt;

&lt;p&gt;PagedAttention also implements &lt;strong&gt;Copy-on-Write (COW)&lt;/strong&gt;:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;In parallel sampling (generating multiple answers for the same prompt) or beam search, all branches share the exact same physical prompt KV blocks.&lt;/li&gt;
&lt;li&gt;Only when a specific branch generates a new token does it allocate its own private block.&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;Memory waste plummets from &lt;strong&gt;80% to under 4%&lt;/strong&gt;, enabling servers to double or quadruple active batch sizes.&lt;/p&gt;

&lt;p&gt;Read the full deep-dive with interactive architectural schematics at &lt;a href="https://binarydose.in/blog/2026/09/23/how-vllm-paged-attention-works" rel="noopener noreferrer"&gt;Binary Dose&lt;/a&gt;.&lt;/p&gt;

</description>
      <category>ai</category>
      <category>machinelearning</category>
      <category>operatingsystems</category>
      <category>systemdesign</category>
    </item>
    <item>
      <title>Why MySQL and Postgres Use B+ Trees Instead of B-Trees for Indexing</title>
      <dc:creator>Binary Dose</dc:creator>
      <pubDate>Tue, 10 Nov 2026 12:40:42 +0000</pubDate>
      <link>https://dev.to/binarydose/why-mysql-and-postgres-use-b-trees-instead-of-b-trees-for-indexing-4cp7</link>
      <guid>https://dev.to/binarydose/why-mysql-and-postgres-use-b-trees-instead-of-b-trees-for-indexing-4cp7</guid>
      <description>&lt;h1&gt;
  
  
  Why MySQL and Postgres Use B+ Trees Instead of B-Trees for Indexing
&lt;/h1&gt;

&lt;p&gt;When indexing relational databases (such as MySQL's InnoDB or PostgreSQL's standard btree index), the underlying data structure is almost universally a &lt;strong&gt;B+ Tree&lt;/strong&gt;, rather than a standard B-Tree.&lt;/p&gt;

&lt;p&gt;To understand why, we must analyze how physical storage hardware and operating system page caches interact with tree fan-out.&lt;/p&gt;




&lt;h2&gt;
  
  
  1. The Fan-Out Problem in Standard B-Trees
&lt;/h2&gt;

&lt;p&gt;In a standard B-Tree, every node (both internal and leaf) stores:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;Search Keys&lt;/li&gt;
&lt;li&gt;Child Pointers&lt;/li&gt;
&lt;li&gt;&lt;strong&gt;Record / Tuple Pointers (Data Pointers)&lt;/strong&gt;&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;Because physical storage is organized into fixed-size blocks (typically &lt;strong&gt;16 KB&lt;/strong&gt; in InnoDB), the inclusion of bulky data pointers significantly reduces the number of keys that can fit into a single page.&lt;/p&gt;

&lt;h3&gt;
  
  
  The Math:
&lt;/h3&gt;

&lt;ul&gt;
&lt;li&gt;If each entry is 128 bytes (key + data pointer), a 16 KB page holds &lt;code&gt;≈ 125&lt;/code&gt; keys.&lt;/li&gt;
&lt;li&gt;If internal nodes store only 16-byte routing entries (8-byte key + 8-byte child pointer), a 16 KB page holds &lt;strong&gt;1,000 keys&lt;/strong&gt;!&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;Higher fan-out directly reduces tree height &lt;code&gt;h&lt;/code&gt;. In a database indexing 1 billion rows:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;Lower fan-out B-Tree: Height = 5–6 (5–6 disk seeks).&lt;/li&gt;
&lt;li&gt;Higher fan-out B+ Tree: Height = &lt;strong&gt;3&lt;/strong&gt; (3 disk seeks).&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;Because the root and level-1 nodes reside permanently in the database RAM buffer pool, nearly all point lookups execute in just &lt;strong&gt;1 physical disk seek&lt;/strong&gt;!&lt;/p&gt;




&lt;h2&gt;
  
  
  2. Linked Leaf Nodes for Sequential Range Queries
&lt;/h2&gt;

&lt;p&gt;Relational database queries frequently retrieve ranges of records:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight sql"&gt;&lt;code&gt;&lt;span class="k"&gt;SELECT&lt;/span&gt; &lt;span class="o"&gt;*&lt;/span&gt; &lt;span class="k"&gt;FROM&lt;/span&gt; &lt;span class="n"&gt;orders&lt;/span&gt; &lt;span class="k"&gt;WHERE&lt;/span&gt; &lt;span class="n"&gt;order_date&lt;/span&gt; &lt;span class="k"&gt;BETWEEN&lt;/span&gt; &lt;span class="s1"&gt;'2026-01-01'&lt;/span&gt; &lt;span class="k"&gt;AND&lt;/span&gt; &lt;span class="s1"&gt;'2026-01-31'&lt;/span&gt;&lt;span class="p"&gt;;&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;h3&gt;
  
  
  In a B-Tree:
&lt;/h3&gt;

&lt;p&gt;Records matching the range are scattered across internal nodes and leaf nodes. The engine must perform an expensive, recursive &lt;strong&gt;in-order tree traversal&lt;/strong&gt;, repeatedly navigating up and down parent pointers.&lt;/p&gt;

&lt;h3&gt;
  
  
  In a B+ Tree:
&lt;/h3&gt;

&lt;ul&gt;
&lt;li&gt;&lt;strong&gt;All data records reside exclusively in leaf pages.&lt;/strong&gt;&lt;/li&gt;
&lt;li&gt;Every leaf page contains a pointer to the &lt;strong&gt;next&lt;/strong&gt; and &lt;strong&gt;previous&lt;/strong&gt; leaf page (forming a doubly-linked list).&lt;/li&gt;
&lt;li&gt;The engine performs a single point lookup to find the start key (&lt;code&gt;2026-01-01&lt;/code&gt;), and then simply scans horizontally across the leaf linked list in &lt;code&gt;O(K)&lt;/code&gt; time!&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;Explore full database storage engine architectures at &lt;a href="https://binarydose.in/coredose/dbms/chapter-09/b-trees-structure-and-node-capacity" rel="noopener noreferrer"&gt;Binary Dose&lt;/a&gt;.&lt;/p&gt;

</description>
      <category>dbms</category>
      <category>database</category>
      <category>systemdesign</category>
      <category>sql</category>
    </item>
    <item>
      <title>The Math of Collisions: Pure ALOHA vs Slotted ALOHA Efficiency</title>
      <dc:creator>Binary Dose</dc:creator>
      <pubDate>Mon, 09 Nov 2026 23:11:49 +0000</pubDate>
      <link>https://dev.to/binarydose/the-math-of-collisions-pure-aloha-vs-slotted-aloha-efficiency-4dkc</link>
      <guid>https://dev.to/binarydose/the-math-of-collisions-pure-aloha-vs-slotted-aloha-efficiency-4dkc</guid>
      <description>&lt;h1&gt;
  
  
  The Math of Collisions: Pure ALOHA vs Slotted ALOHA Efficiency
&lt;/h1&gt;

&lt;p&gt;In shared medium networks, multiple autonomous stations compete for access to a single communication channel without a central scheduler.&lt;/p&gt;

&lt;p&gt;Developed at the University of Hawaii in 1970, &lt;strong&gt;Pure ALOHA&lt;/strong&gt; and &lt;strong&gt;Slotted ALOHA&lt;/strong&gt; are the foundational random access protocols that established the mathematical framework for modern Ethernet and Wi-Fi.&lt;/p&gt;




&lt;h2&gt;
  
  
  1. Pure ALOHA: &lt;code&gt;S = G · e^-2G&lt;/code&gt;
&lt;/h2&gt;

&lt;p&gt;In Pure ALOHA, stations transmit frames whenever data is generated. If a frame collides with another transmission—even by a single bit—the entire frame is destroyed.&lt;/p&gt;

&lt;h3&gt;
  
  
  The Vulnerability Period (&lt;code&gt;2 · T_f&lt;/code&gt;):
&lt;/h3&gt;

&lt;p&gt;Let &lt;code&gt;T_f&lt;/code&gt; be the frame transmission time. Suppose station &lt;code&gt;A&lt;/code&gt; starts transmitting at time &lt;code&gt;t₀&lt;/code&gt;:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;If station &lt;code&gt;B&lt;/code&gt; began transmitting between &lt;code&gt;t₀ - T_f&lt;/code&gt; and &lt;code&gt;t₀&lt;/code&gt;, its end overlaps with &lt;code&gt;A&lt;/code&gt;'s start.&lt;/li&gt;
&lt;li&gt;If station &lt;code&gt;C&lt;/code&gt; begins transmitting between &lt;code&gt;t₀&lt;/code&gt; and &lt;code&gt;t₀ + T_f&lt;/code&gt;, its start overlaps with &lt;code&gt;A&lt;/code&gt;'s end.&lt;/li&gt;
&lt;/ul&gt;

&lt;p&gt;The &lt;strong&gt;Vulnerability Window&lt;/strong&gt; is &lt;code&gt;2 · T_f&lt;/code&gt;.&lt;/p&gt;

&lt;p&gt;Assuming frame generation follows a Poisson distribution with attempt rate &lt;code&gt;G&lt;/code&gt; frames per slot time:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;P(k frames in 2T_f) = frac(2G)^k · e^-2Gk!
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;The probability of a successful transmission (&lt;code&gt;k = 0&lt;/code&gt; collisions) is &lt;code&gt;e^-2G&lt;/code&gt;.&lt;br&gt;
Throughput &lt;code&gt;S&lt;/code&gt; is:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;S = G · e^-2G
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Differentiating &lt;code&gt;(dS / dG) = e^-2G(1 - 2G) = 0 implies G = 0.5&lt;/code&gt;.&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;S_max = (1 / 2e) ≈ 18.4\%
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;






&lt;h2&gt;
  
  
  2. Slotted ALOHA: &lt;code&gt;S = G · e^-G&lt;/code&gt;
&lt;/h2&gt;

&lt;p&gt;Slotted ALOHA introduces a centralized clock dividing time into discrete slots of length &lt;code&gt;T_f&lt;/code&gt;. Stations can only begin transmission at the beginning of a slot boundary.&lt;/p&gt;

&lt;h3&gt;
  
  
  Halving the Vulnerability Window:
&lt;/h3&gt;

&lt;p&gt;Because all transmissions start simultaneously:&lt;/p&gt;

&lt;ul&gt;
&lt;li&gt;A frame either collides completely or passes completely.&lt;/li&gt;
&lt;li&gt;The vulnerability period shrinks from &lt;code&gt;2 · T_f&lt;/code&gt; down to &lt;strong&gt;&lt;code&gt;T_f&lt;/code&gt;&lt;/strong&gt;.
&lt;/li&gt;
&lt;/ul&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;P(0 frames in T_f) = e^-G
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;





&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;S = G · e^-G
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Differentiating &lt;code&gt;(dS / dG) = 0 implies G = 1.0&lt;/code&gt;.&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;S_max = (1 / e) ≈ 36.8\%
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Synchronizing transmissions doubles the channel capacity from &lt;code&gt;18.4\%&lt;/code&gt; to &lt;code&gt;36.8\%&lt;/code&gt;.&lt;/p&gt;

&lt;p&gt;Explore complete protocol derivations and framing simulations at &lt;a href="https://binarydose.in/coredose/cn/module-03/random-access-protocols-pure-and-slotted-aloha" rel="noopener noreferrer"&gt;Binary Dose&lt;/a&gt;.&lt;/p&gt;

</description>
      <category>computernetworks</category>
      <category>protocols</category>
      <category>algorithms</category>
      <category>softwareengineering</category>
    </item>
    <item>
      <title>Mutex vs Spinlock: When Should a Thread Sleep or Spin?</title>
      <dc:creator>Binary Dose</dc:creator>
      <pubDate>Mon, 09 Nov 2026 12:54:30 +0000</pubDate>
      <link>https://dev.to/binarydose/mutex-vs-spinlock-when-should-a-thread-sleep-or-spin-1cce</link>
      <guid>https://dev.to/binarydose/mutex-vs-spinlock-when-should-a-thread-sleep-or-spin-1cce</guid>
      <description>&lt;h1&gt;
  
  
  Mutex vs Spinlock: When Should a Thread Sleep or Spin?
&lt;/h1&gt;

&lt;p&gt;In multi-threaded software engineering, managing shared mutable state requires synchronization primitives to enforce Mutual Exclusion.&lt;/p&gt;

&lt;p&gt;Yet choosing between a &lt;strong&gt;Mutex&lt;/strong&gt;, a &lt;strong&gt;Spinlock&lt;/strong&gt;, and a &lt;strong&gt;Semaphore&lt;/strong&gt; is not a matter of syntax—it is a hardware-level trade-off between &lt;strong&gt;CPU Context Switching Latency&lt;/strong&gt; and &lt;strong&gt;CPU Cycle Waste&lt;/strong&gt;.&lt;/p&gt;




&lt;h2&gt;
  
  
  1. Mutex: Sleep-Waiting with Strict Ownership
&lt;/h2&gt;

&lt;p&gt;A Mutex is a binary synchronization primitive with &lt;strong&gt;ownership semantics&lt;/strong&gt;: only the thread that locks a mutex is legally permitted to unlock it.&lt;/p&gt;

&lt;h3&gt;
  
  
  Mechanics:
&lt;/h3&gt;

&lt;p&gt;When thread &lt;code&gt;T₁&lt;/code&gt; attempts to acquire a contested mutex:&lt;/p&gt;

&lt;ol&gt;
&lt;li&gt;The kernel transitions &lt;code&gt;T₁&lt;/code&gt; from &lt;code&gt;RUNNING&lt;/code&gt; to &lt;code&gt;BLOCKED&lt;/code&gt;.&lt;/li&gt;
&lt;li&gt;
&lt;code&gt;T₁&lt;/code&gt;'s register state is saved, and the CPU schedules another thread.&lt;/li&gt;
&lt;li&gt;When the lock is released, the kernel moves &lt;code&gt;T₁&lt;/code&gt; back to the &lt;code&gt;READY&lt;/code&gt; queue.&lt;/li&gt;
&lt;/ol&gt;

&lt;h3&gt;
  
  
  The Overhead Cost:
&lt;/h3&gt;

&lt;p&gt;A mutex operation incurs &lt;strong&gt;two full context switches&lt;/strong&gt; (descheduling + rescheduling). On modern x86/ARM hardware, this represents roughly &lt;code&gt;1µs - 5µs&lt;/code&gt; of latency, accompanied by L1/L2 cache pollution.&lt;/p&gt;




&lt;h2&gt;
  
  
  2. Spinlock: Busy-Waiting with Atomic Hardware
&lt;/h2&gt;

&lt;p&gt;A Spinlock does not surrender the CPU core. Instead, it loops in place executing atomic instructions (such as &lt;code&gt;lock cmpxchg&lt;/code&gt; or &lt;code&gt;test_and_set&lt;/code&gt;).&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight c"&gt;&lt;code&gt;&lt;span class="c1"&gt;// Conceptually:&lt;/span&gt;
&lt;span class="k"&gt;while&lt;/span&gt; &lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="n"&gt;__atomic_test_and_set&lt;/span&gt;&lt;span class="p"&gt;(&lt;/span&gt;&lt;span class="o"&gt;&amp;amp;&lt;/span&gt;&lt;span class="n"&gt;lock&lt;/span&gt;&lt;span class="p"&gt;,&lt;/span&gt; &lt;span class="n"&gt;__ATOMIC_ACQUIRE&lt;/span&gt;&lt;span class="p"&gt;))&lt;/span&gt; &lt;span class="p"&gt;{&lt;/span&gt;
    &lt;span class="cp"&gt;#if defined(__x86_64__)
&lt;/span&gt;    &lt;span class="n"&gt;__builtin_ia32_pause&lt;/span&gt;&lt;span class="p"&gt;();&lt;/span&gt; &lt;span class="c1"&gt;// Emits PAUSE instruction to prevent pipeline stalls&lt;/span&gt;
    &lt;span class="cp"&gt;#endif
&lt;/span&gt;&lt;span class="p"&gt;}&lt;/span&gt;
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;h3&gt;
  
  
  Advantages &amp;amp; Disadvantages:
&lt;/h3&gt;

&lt;ul&gt;
&lt;li&gt;
&lt;strong&gt;Advantage&lt;/strong&gt;: Zero context-switch cost. Acquisition latency is measured in nanoseconds.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Disadvantage&lt;/strong&gt;: Burns 100% of an entire CPU core while spinning. If the thread holding the lock is preempted, the spinning thread starves the system.&lt;/li&gt;
&lt;li&gt;
&lt;strong&gt;Rule&lt;/strong&gt;: Mandatory in &lt;strong&gt;Interrupt Service Routines (ISRs)&lt;/strong&gt; because hardware interrupt handlers cannot sleep.&lt;/li&gt;
&lt;/ul&gt;




&lt;h2&gt;
  
  
  3. The Mathematical Rule of Thumb
&lt;/h2&gt;

&lt;p&gt;Let &lt;code&gt;T_ctx&lt;/code&gt; be the time required for a context switch, and &lt;code&gt;T_hold&lt;/code&gt; be the average time a thread holds the critical section:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;If T_hold &amp;lt; 2 · T_ctx implies Use a Spinlock
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;





&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;If T_hold &amp;gt; 2 · T_ctx implies Use a Mutex
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;Explore interactive concurrency state machines at &lt;a href="https://binarydose.in/coredose/os/chapter-04/semaphores-counting-semaphores-binary-semaphores-and-mutexes" rel="noopener noreferrer"&gt;Binary Dose&lt;/a&gt;.&lt;/p&gt;

</description>
      <category>operatingsystems</category>
      <category>concurrency</category>
      <category>linux</category>
      <category>systemsengineering</category>
    </item>
  </channel>
</rss>
