miku · January 11, 2026 16:12
diff --git a/945526.945527.pdf b/945526.945527.pdf
diff --git a/README.md b/README.md
diff --git a/dijkstra65.go b/dijkstra65.go
 // Solution of a Problem in Concurrent Program Control
 //
 // Dijkstra, 1965: http://rust-class.org/static/classes/class19/dijkstra.pdf
 // https://i.imgur.com/weHFuip.png
 //
 // Notes:
 //
 // * if b[i] is true, then the program is not "looping", e.g. not waiting to enter a critical section
 // * if b[i] is false (Li0), the program entered "looping" stage, before the critical section
 //
 // k looks like a "selector", the "if" statement in Li1 like a two-stage "check"
 //
 //     First we want k and i be the same; which only happens, if current
 //     program k is not waiting (i.e. b[k] is true).
 //
 //     If the program at k is not waiting, we can jump to the next branch (Li4).
 //
 //     Here, we want all other programs not in the critical section; also
 //     setting c[i] to false to indicate, that we want to run.
 //
 package main

 import (
 	"bytes"
 	"flag"
 	"fmt"
 	"io"
 	"math/rand"
 	"time"
 )

 const (
 	Enter = "\u001b[32mE\u001b[0m"
 	Exit  = "\u001b[31mX\u001b[0m"
 	False = "\u001b[34mF\u001b[0m"
 	True  = "\u001b[37mT\u001b[0m"
 )

 var (
 	N    = flag.Int("n", 3, "number of processes")
 	T    = flag.Duration("t", 1000*time.Millisecond, "exit simulation after t (e.g. 1s, 100ms, ...)")
 	Cdur = flag.Duration("C", 10*time.Millisecond, "critical section duration")
 	Rdur = flag.Duration("R", 100*time.Millisecond, "remainder duration")
 )

 func main() {
 	flag.Parse()
 	// The integer k will satisfy 1 <= k <= N, b[i] and c[i] will only be set
 	// by the ith computer; they will be inspected by others. [...] all
 	// boolean arrays mentioned set to true. The starting value of k is
 	// immaterial.
 	var (
 		k int = 0
 		b     = make([]bool, *N)
 		c     = make([]bool, *N)
 	)
 	setTrue(b)
 	setTrue(c)

 	// The program for the ith computer [...]
 	computer := func(i int) {
 		fmt.Printf("[%d] R .. k=%v, b=%v, c=%v\n", i, k, Btoa(b), Btoa(c))
 	Li0:
 		fmt.Printf("[%d] Li0  k=%v, b=%v, c=%v\n", i, k, Btoa(b), Btoa(c))
 		b[i] = false
 	Li1:
 		if k != i {
 			c[i] = true
 			// Li3
 			if b[k] {
 				k = i
 			}
 			goto Li1
 		} else {
 			// Li4
 			c[i] = false
 			for j := 0; j < *N; j++ {
 				if j != i && !c[j] {
 					goto Li1
 				}
 			}
 		}
 		// Critical section, only at most one "computer" will be in this section at any time.
 		fmt.Printf("[%d] %s >> k=%v, b=%v, c=%v\n", i, Enter, k, Btoa(b), Btoa(c))
 		time.Sleep(*Cdur)
 		fmt.Printf("[%d] %s << k=%v, b=%v, c=%v\n", i, Exit, k, Btoa(b), Btoa(c))
 		// Critical section ends.

 		c[i] = true
 		b[i] = true

 		fmt.Printf("[%d] Rem  k=%v, b=%v, c=%v\n", i, k, Btoa(b), Btoa(c))
 		time.Sleep(time.Duration(rand.Int63n(Rdur.Milliseconds())) * time.Millisecond)
 		goto Li0
 	}
 	for i := 0; i < *N; i++ {
 		go computer(i)
 	}
 	time.Sleep(*T)
 	fmt.Println("[X] timeout")
 }

 func setTrue(b []bool) {
 	for i := 0; i < len(b); i++ {
 		b[i] = true
 	}
 }

 func Btoa(b []bool) string {
 	var buf bytes.Buffer
 	for _, v := range b {
 		if v {
 			io.WriteString(&buf, True)
 		} else {
 			io.WriteString(&buf, False)
 		}
 	}
 	return buf.String()
 }

 // Appendix A: The Proof
 //
 // We start b y observing that the solution is safe in the
 // sense that no two computers can be in their critical section
 // simultaneously. For the only way to enter its critical
 // section is the performance of the compound statement
 // Li4 without jmnping back to Lil, i.e., finding all other
 // c's t r u e after having set its own e to false.
 // The second part of the proof must show that no infinite
 // "After you"-"After you"-blocking can occur; i.e., when
 // none of the computers is in its critical section, of the
 // computers looping (i.e., jumping back to Lil) at least
 // one--and therefore exactly one--will be allowed to enter
 // its critical section in due time.
 // If the kth computer is not among the looping ones,
 // bik] will be t r u e and the looping ones will all find k # i.
 // As a result one or mnore of them will find in Li3 the Boolean
 // b[k] t r u e and therefore one or more will decide to assign
 // "k : = i". After the first assignment "k : = i", b[k] becomes false and no new computers can decide again to
 // assign a new value to k. When all decided assignments to
 // k have been performed,/c will point to one of the looping
 // computers and will not change its value for the time being,
 // i.e., until b[k] becomes t r u e , viz., until the kth computer
 // has completed its critical section. As soon as the value of
 // ]c does not change any more, the kth computer will wait
 // (via the compound statement Li4) until all other c's are
 // t r u e , but this situation will certainly arise, if not already
 // present, because all other looping ones are forced to set
 // their e t r u e , as they will find k # i. And this, the author
 // believes, completes the proof.
 //
 // Appendix B: Race
 // ==================
 // WARNING: DATA RACE
 // Write at 0x00c0000bc051 by goroutine 8:
 //   main.main.func1()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:65 +0xf8e
 //
 // Previous read at 0x00c0000bc051 by goroutine 7:
 //   main.Btoa()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:111 +0xb5
 //   main.main.func1()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:84 +0x536
 //
 // Goroutine 8 (running) created at:
 //   main.main()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
 //
 // Goroutine 7 (running) created at:
 //   main.main()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
 // ==================
 // ==================
 // WARNING: DATA RACE
 // Write at 0x00c0000bc054 by goroutine 8:
 //   main.main.func1()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:68 +0x364
 //
 // Previous read at 0x00c0000bc054 by goroutine 9:
 //   main.Btoa()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:111 +0xb5
 //   main.main.func1()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:64 +0xdb3
 //
 // Goroutine 8 (running) created at:
 //   main.main()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
 //
 // Goroutine 9 (running) created at:
 //   main.main()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
 // ==================
 // ==================
 // WARNING: DATA RACE
 // Read at 0x00c0000bc055 by goroutine 7:
 //   main.Btoa()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:111 +0xb5
 //   main.main.func1()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:86 +0x7fc
 //
 // Previous write at 0x00c0000bc055 by goroutine 9:
 //   main.main.func1()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:68 +0x364
 //
 // Goroutine 7 (running) created at:
 //   main.main()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
 //
 // Goroutine 9 (running) created at:
 //   main.main()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
 // ==================
 // ==================
 // WARNING: DATA RACE
 // Write at 0x00c0000bc050 by goroutine 7:
 //   main.main.func1()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:90 +0xa5d
 //
 // Previous read at 0x00c0000bc050 by goroutine 9:
 //   main.main.func1()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:70 +0x3ea
 //
 // Goroutine 7 (running) created at:
 //   main.main()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
 //
 // Goroutine 9 (running) created at:
 //   main.main()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
 // ==================
 // ==================
 // WARNING: DATA RACE
 // Write at 0x00c0000bc048 by goroutine 8:
 //   main.main.func1()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:71 +0x418
 //
 // Previous read at 0x00c0000bc048 by goroutine 7:
 //   main.main.func1()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:86 +0x844
 //
 // Goroutine 8 (running) created at:
 //   main.main()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
 //
 // Goroutine 7 (running) created at:
 //   main.main()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
 // ==================
 // ==================
 // WARNING: DATA RACE
 // Write at 0x00c0000bc053 by goroutine 7:
 //   main.main.func1()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:68 +0x364
 //
 // Previous read at 0x00c0000bc053 by goroutine 8:
 //   main.main.func1()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:78 +0x4dd
 //
 // Goroutine 7 (running) created at:
 //   main.main()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
 //
 // Goroutine 8 (running) created at:
 //   main.main()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
 // ==================
 // ==================
 // WARNING: DATA RACE
 // Read at 0x00c0000bc052 by goroutine 7:
 //   main.Btoa()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:111 +0xb5
 //   main.main.func1()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:64 +0xd64
 //
 // Previous write at 0x00c0000bc052 by goroutine 9:
 //   main.main.func1()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:90 +0xa5d
 //
 // Goroutine 7 (running) created at:
 //   main.main()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
 //
 // Goroutine 9 (running) created at:
 //   main.main()
 //       /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
 // ==================
 // Found 7 data race(s)
 // exit status 66
diff --git a/dijkstra65.pdf b/dijkstra65.pdf
diff --git a/dijkstra65.txt b/dijkstra65.txt
 Solution of a Problem in
 Concurrent Programming Control

 computer can only request one one-way message at a time.
 And only this will make the reader realize to what extent
 this problem is far from trivial.

 E. W. DIJXSTRA

 The Solution

 Technological University, Eindhoven, The Netherlands

 The common store consists of:
 " B o o l e a n array b, c[l:N];

 A number of mainly independent sequential-cyclic processes
 with restricted means of communication with each other can
 be made in such a way that at any moment one and only one
 of them is e n g a g e d in the "critical section" of its cycle.

 Introduction

 Given in this paper is a solution to a problem for which,
 to the knowledge of the author, has been an open question
 since at least 1962, irrespective of the solvability. The
 paper consists of three parts: the problem, the solution,
 and the proof. Although the setting of the problem might
 seem somewhat academic at first, the author trusts that
 anyone familiar with the logical problems that arise in
 computer coupling will appreciate the significance of the
 fact that this problem indeed can be solved.
 The Problem

 To begin, consider N computers, each engaged in a
 process which, for our aims, can be regarded as cyclic. In
 each of the cycles a so-cMled "critical section" occurs and
 the computers have to be programmed in such a way that
 at any moment only one of these N cyclic processes is in
 its critical section. In order to effectuate this mutual
 exclusion of critical-section execution the computers can
 communicate with each other via a common store. Writing
 a word into or nondestructively reading a word from this
 store are undividable operations; i.e., when two or more
 computers try to communicate (either for reading or for
 writing) simultaneously with the same common location,
 these communications will take place one after the other,
 but in an unknown order.
 The solution must satisfy the following requirements.
 (a) The solution must be symmetrical between the N
 computers; as a result we are not allowed to introduce a
 static priority.
 (b) Nothing m a y be assumed about the relative speeds
 of the N computers; we may not even assume their speeds
 to be constant in time.
 (c) If any of the computers is stopped well outside its
 critical section, this is not allowed to lead to potential
 blocking of the others.
 (d) If more than one computer is about to enter its
 critical section, it must be impossible to devise for them
 such finite speeds, that the decision to determine which
 one of them will enter its critical section first is postponed
 until eternity. In other words, constructions in which
 "After you"-"After you"-blocking is still possible, although
 improbable, are not to be regarded as valid solutions.
 We beg the challenged reader to stop here for a while
 and have a try himself, for this seems the only way to get
 a feeling for the tricky consequences of the fact that each
 Vohm, e 8 / Number

 9 / September,

 1965

 integer k"

 The integer k will satisfy 1 < k < N, bill and c[i]
 will only be set by the ith computer; they will be inspected
 by the others. I t is assumed that all computers are started
 well outside their critical sections with all Boolean arrays
 mentioned set to t r u e ; the starting value of k is immaterial.
 The program for the ith computer (1 < i < N) is:
 "integer j;

 LiO: b[i] : = f a l s e ;
 Lil: i f k # i t h e n
 Li2: b e g i n c[i] : = true;
 Li3: i f b [ k ] t h e n k
 :=i;
 g o t o Lil

 Li4:

 end
 else
 b e g i n c[i] : = f a l s e ;
 for j : = 1 s t e p 1 u n t i l N do
 i f j # i a n d n o t c[j] t h e n go to Lil
 end ;
 critical s e c t i o n ;
 c[i] : = t r u e ; bill : = t r u e ;
 r e m a i n d e r of t h e cycle in w h i c h s t o p p i n g is a l l o w e d ;
 g o t o LiO"

 The Proof

 We start b y observing that the solution is safe in the
 sense that no two computers can be in their critical section
 simultaneously. For the only way to enter its critical
 section is the performance of the compound statement
 Li4 without jmnping back to Lil, i.e., finding all other
 c's t r u e after having set its own e to false.
 The second part of the proof must show that no infinite
 "After you"-"After you"-blocking can occur; i.e., when
 none of the computers is in its critical section, of the
 computers looping (i.e., jumping back to Lil) at least
 one--and therefore exactly one--will be allowed to enter
 its critical section in due time.
 If the kth computer is not among the looping ones,
 bik] will be t r u e and the looping ones will all find k # i.
 As a result one or mnore of them will find in Li3 the Boolean
 b[k] t r u e and therefore one or more will decide to assign
 "k : = i". After the first assignment "k : = i", b[k] becomes false and no new computers can decide again to
 assign a new value to k. When all decided assignments to
 k have been performed,/c will point to one of the looping
 computers and will not change its value for the time being,
 i.e., until b[k] becomes t r u e , viz., until the kth computer
 has completed its critical section. As soon as the value of
 ]c does not change any more, the kth computer will wait
 (via the compound statement Li4) until all other c's are
 t r u e , but this situation will certainly arise, if not already
 present, because all other looping ones are forced to set
 their e t r u e , as they will find k # i. And this, the author
 believes, completes the proof.
 Communications

 of the ACM

 569


diff --git a/dijkstra65_fixed.go b/dijkstra65_fixed.go
 // Solution of a Problem in Concurrent Program Control
 //
 // Dijkstra, 1965: http://rust-class.org/static/classes/class19/dijkstra.pdf
 // https://i.imgur.com/weHFuip.png
 //
 // This is a corrected Go implementation that uses atomic operations to ensure
 // the sequential consistency that Dijkstra's algorithm requires.
 //
 // EDUCATIONAL OVERVIEW:
 // ====================
 // This algorithm solves the mutual exclusion problem - ensuring that only one
 // process can be in its "critical section" at a time, without using any
 // built-in synchronization primitives like mutexes.
 //
 // KEY CONCEPTS:
 //
 //  1. CRITICAL SECTION: A piece of code that must not be executed by multiple
 //     processes simultaneously (e.g., updating shared data, accessing hardware).
 //
 //  2. MUTUAL EXCLUSION: The guarantee that at most one process is in its
 //     critical section at any given time.
 //
 // 3. THE CHALLENGE: How do we achieve mutual exclusion using only:
 //   - Shared memory (boolean arrays b[] and c[], integer k)
 //   - Atomic read/write operations
 //   - NO locks, semaphores, or other high-level primitives
 //
 // THE ALGORITHM'S SHARED VARIABLES:
 // =================================
 //
 // b[i] (boolean): Process i's "not trying" flag
 //   - true  = process i is NOT trying to enter critical section (in "remainder")
 //   - false = process i IS trying to enter critical section (in "looping")
 //
 // c[i] (boolean): Process i's "willing to yield" flag
 //   - true  = process i is willing to yield to others
 //   - false = process i wants to enter critical section
 //
 // k (integer): The "privileged process" selector (0 to N-1)
 //   - Points to the process that has priority to enter critical section
 //   - Only changes when b[k] is true (k is not trying)
 //
 // THE ALGORITHM'S STAGES (for process i):
 // ========================================
 //
 // REMAINDER (R):
 //   - Process is doing non-critical work
 //   - b[i] = true, c[i] = true
 //
 // Li0: ANNOUNCE INTENT
 //   - Set b[i] = false: "I want to enter critical section"
 //   - Enter the "looping" stage
 //
 // Li1-Li3: TWO-STAGE CHECK (the heart of the algorithm)
 //
 //	FIRST STAGE (Li1 check: k != i):
 //	  Ask: "Am I the privileged process?"
 //	  - If k == i: I have priority, skip to SECOND STAGE (Li4)
 //	  - If k != i: Someone else has priority, proceed to Li3
 //
 //	Li3: YIELD AND TRY TO BECOME PRIVILEGED
 //	  - Set c[i] = true: "I'm willing to yield"
 //	  - Check if b[k] is true (privileged process not trying)
 //	    * If yes: Set k = i (make myself privileged)
 //	  - Loop back to Li1 to recheck
 //
 //	SECOND STAGE (Li4 check: all other c[j] are true):
 //	  Ask: "Are all other processes willing to yield to me?"
 //	  - Set c[i] = false: "I'm not yielding anymore"
 //	  - Check all other processes: if any c[j] is false, loop back to Li1
 //	  - If all other c[j] are true: proceed to critical section
 //
 // CRITICAL SECTION:
 //   - Only one process can be here at a time (mutual exclusion)
 //   - Do the critical work
 //
 // EXIT:
 //   - Set c[i] = true, b[i] = true: "I'm done, back to remainder"
 //
 // WHY THIS WORKS (Informal):
 // ==========================
 //
 //  1. SAFETY (mutual exclusion):
 //     A process enters critical section only after finding all other c[j] true
 //     while its own c[i] is false. Two processes cannot both see this condition
 //     simultaneously.
 //
 //  2. LIVENESS (progress):
 //     If multiple processes are looping and no one is in critical section:
 //     - Eventually k stabilizes to point to one of the looping processes
 //     - That process (k) will find k == i and proceed to Li4
 //     - All other looping processes will set their c[j] = true (yielding)
 //     - Process k will enter critical section
 //
 //  3. THE ROLE OF k:
 //     k acts as a "tie-breaker" to prevent deadlock. When multiple processes
 //     compete, k determines who gets priority. The protocol ensures k eventually
 //     stabilizes, allowing progress.
 //
 // WHY ATOMIC OPERATIONS ARE NEEDED:
 // ==================================
 //
 // Dijkstra's algorithm assumes SEQUENTIAL CONSISTENCY:
 // - All reads and writes to shared variables are atomic
 // - All processes see operations in the same total order
 //
 // Modern languages like Go do NOT provide sequential consistency for plain
 // variables. Without atomic operations:
 // - Writes may not be visible to other goroutines
 // - Reads may see stale values
 // - Operations can be reordered by compiler/CPU
 // - The algorithm's invariants break down
 //
 // Solution: Use sync/atomic operations to ensure:
 // - Atomic reads and writes (no torn reads/writes)
 // - Proper memory ordering (acquire/release semantics)
 // - Visibility of changes across goroutines
 package main

 import (
 	"bytes"
 	"flag"
 	"fmt"
 	"io"
 	"math/rand"
 	"sync/atomic"
 	"time"
 )

 const (
 	Enter = "\u001b[32mE\u001b[0m"
 	Exit  = "\u001b[31mX\u001b[0m"
 	False = "\u001b[34mF\u001b[0m"
 	True  = "\u001b[37mT\u001b[0m"
 )

 var (
 	N    = flag.Int("n", 3, "number of processes")
 	T    = flag.Duration("t", 1000*time.Millisecond, "exit simulation after t (e.g. 1s, 100ms, ...)")
 	Cdur = flag.Duration("C", 10*time.Millisecond, "critical section duration")
 	Rdur = flag.Duration("R", 100*time.Millisecond, "remainder duration")
 )

 func main() {
 	flag.Parse()

 	// SHARED VARIABLES (all accessed atomically)
 	// k: the privileged process index (starts at 0)
 	var k atomic.Int32

 	// b[i]: true = process i is not trying to enter critical section
 	// Initially all true (all processes start in remainder section)
 	b := make([]atomic.Bool, *N)
 	for i := 0; i < *N; i++ {
 		b[i].Store(true)
 	}

 	// c[i]: true = process i is willing to yield
 	// Initially all true (no one is competing yet)
 	c := make([]atomic.Bool, *N)
 	for i := 0; i < *N; i++ {
 		c[i].Store(true)
 	}

 	// The program for the ith computer (process)
 	computer := func(i int) {
 		fmt.Printf("[%d] R .. k=%v, b=%v, c=%v\n", i, k.Load(), BtoaAtomic(b), BtoaAtomic(c))

 	Li0: // ANNOUNCE INTENT TO ENTER CRITICAL SECTION
 		fmt.Printf("[%d] Li0  k=%v, b=%v, c=%v\n", i, k.Load(), BtoaAtomic(b), BtoaAtomic(c))
 		// Set b[i] = false: "I am now looping (trying to enter critical section)"
 		b[i].Store(false)

 	Li1: // FIRST STAGE: CHECK IF I AM THE PRIVILEGED PROCESS
 		// Read current privileged process index
 		currentK := int(k.Load())

 		if currentK != i {
 			// I am NOT the privileged process
 			// Set c[i] = true: "I am willing to yield to others"
 			c[i].Store(true)

 			// TRY TO BECOME THE PRIVILEGED PROCESS (Li3)
 			// Check if the current privileged process is not trying to enter
 			if b[currentK].Load() {
 				// b[k] is true, meaning process k is not trying
 				// Make myself the privileged process
 				k.Store(int32(i))
 			}
 			// Loop back to Li1 to recheck (maybe I'm privileged now, or k changed)
 			goto Li1

 		} else {
 			// I AM the privileged process (k == i)

 			// SECOND STAGE: CHECK IF ALL OTHERS ARE WILLING TO YIELD (Li4)
 			// Set c[i] = false: "I am NOT yielding, I want to enter"
 			c[i].Store(false)

 			// Check if all other processes have c[j] = true (willing to yield)
 			for j := 0; j < *N; j++ {
 				if j != i && !c[j].Load() {
 					// Process j is not willing to yield (c[j] = false)
 					// We cannot enter yet, go back to Li1
 					goto Li1
 				}
 			}
 			// All other c[j] are true, we can enter critical section!
 		}

 		// ========================================================================
 		// CRITICAL SECTION START
 		// ========================================================================
 		// At this point, we have guaranteed that:
 		// - We are the privileged process (k == i)
 		// - Our c[i] = false
 		// - All other c[j] = true
 		// This ensures mutual exclusion: no other process can enter
 		fmt.Printf("[%d] %s >> k=%v, b=%v, c=%v\n", i, Enter, k.Load(), BtoaAtomic(b), BtoaAtomic(c))
 		time.Sleep(*Cdur)
 		fmt.Printf("[%d] %s << k=%v, b=%v, c=%v\n", i, Exit, k.Load(), BtoaAtomic(b), BtoaAtomic(c))
 		// ========================================================================
 		// CRITICAL SECTION END
 		// ========================================================================

 		// EXIT PROTOCOL: Release our claim
 		c[i].Store(true) // "I am willing to yield again"
 		b[i].Store(true) // "I am not trying to enter anymore"

 		// REMAINDER SECTION: Do non-critical work
 		fmt.Printf("[%d] Rem  k=%v, b=%v, c=%v\n", i, k.Load(), BtoaAtomic(b), BtoaAtomic(c))
 		time.Sleep(time.Duration(rand.Int63n(Rdur.Milliseconds())) * time.Millisecond)

 		// Loop back to try entering critical section again
 		goto Li0
 	}

 	// Launch N concurrent processes
 	for i := 0; i < *N; i++ {
 		go computer(i)
 	}

 	// Run simulation for duration T
 	time.Sleep(*T)
 	fmt.Println("[X] timeout")
 }

 // BtoaAtomic converts an array of atomic bools to a colored string representation
 func BtoaAtomic(b []atomic.Bool) string {
 	var buf bytes.Buffer
 	for i := range b {
 		if b[i].Load() {
 			io.WriteString(&buf, True)
 		} else {
 			io.WriteString(&buf, False)
 		}
 	}
 	return buf.String()
 }

 // PROOF OF CORRECTNESS (from Dijkstra's paper):
 // ==============================================
 //
 // PART 1: SAFETY (Mutual Exclusion)
 // ----------------------------------
 // We must prove that no two computers can be in their critical section
 // simultaneously.
 //
 // To enter critical section, a process must:
 // 1. Be the privileged process (k == i)
 // 2. Set its c[i] = false
 // 3. Find all other c[j] = true (Li4 check)
 //
 // Suppose two processes P and Q both enter critical section:
 // - Both must have found all other c[] = true while their own c[] = false
 // - But if P has c[P] = false, Q cannot find all c[] = true
 // - Contradiction! Therefore, mutual exclusion holds.
 //
 // PART 2: LIVENESS (Progress)
 // ----------------------------
 // We must prove that if no process is in critical section and some processes
 // are looping, at least one will eventually enter.
 //
 // Case 1: Process k is not looping
 //   - Then b[k] = true
 //   - All looping processes will find k != i (in Li1)
 //   - One or more will find b[k] = true (in Li3)
 //   - They will assign k := i
 //   - Eventually k stabilizes to one of the looping processes
 //   - Fall through to Case 2
 //
 // Case 2: Process k IS looping
 //   - Process k will find k == i (in Li1) and proceed to Li4
 //   - All other looping processes have k != i, so they set c[] = true (in Li1)
 //   - Process k will find all other c[] = true
 //   - Process k enters critical section
 //   - Progress!
 //
 // COMPARISON WITH MODERN SYNCHRONIZATION:
 // ========================================
 //
 // This algorithm is HISTORIC and EDUCATIONAL. In practice, use:
 // - sync.Mutex for mutual exclusion
 // - sync.RWMutex for reader-writer locks
 // - Channels for communication and synchronization
 //
 // Why? Modern primitives are:
 // - Simpler to use correctly
 // - Better optimized by the runtime
 // - More composable
 // - Less error-prone
 //
 // But understanding Dijkstra's algorithm teaches:
 // - The fundamentals of concurrent programming
 // - Why atomicity and memory ordering matter
 // - The complexity of building synchronization from scratch
 // - Appreciation for higher-level abstractions
 //
 // EXERCISES FOR THE READER:
 // =========================
 //
 // 1. Run with -race flag: Notice no data races!
 //    go run -race dijkstra65_fixed.go -n 3 -t 1s
 //
 // 2. Try different parameters:
 //    go run dijkstra65_fixed.go -n 5 -t 2s -C 50ms -R 200ms
 //
 // 3. Verify mutual exclusion: Check output, only one process should show
 //    "E >>" at a time (green E for enter)
 //
 // 4. Compare with original: Run dijkstra65.go with -race and see the races
 //
 // 5. Modify to add counters: Track how many times each process enters critical
 //    section. Are some processes starved? (Hint: Dijkstra's algorithm is NOT
 //    starvation-free in the strict sense, though in practice it works well)
 //
 // 6. Replace atomic operations with plain variables: See the algorithm break!
 //
diff --git a/minimal.go b/minimal.go
 // Solution of a Problem in Concurrent Program Control, http://rust-class.org/static/classes/class19/dijkstra.pdf
 package main

 import (
 	"flag"
 	"time"
 )

 var (
 	N    = flag.Int("n", 3, "number of processes")
 	T    = flag.Duration("t", 1000*time.Millisecond, "exit simulation after t (e.g. 1s, 100ms, ...)")
 	Cdur = flag.Duration("C", 10*time.Millisecond, "critical section duration")
 )

 func main() {
 	flag.Parse()
 	var (
 		k        int = 0
 		b            = boolSlice(*N, true)
 		c            = boolSlice(*N, true)
 		computer     = func(i int) {
 		Li0:
 			b[i] = false
 		Li1:
 			if k != i {
 				c[i] = true
 				if b[k] {
 					k = i
 				}
 				goto Li1
 			} else {
 				c[i] = false
 				for j := 0; j < *N; j++ {
 					if j != i && !c[j] {
 						goto Li1
 					}
 				}
 			}
 			time.Sleep(*Cdur) // simulate critical section
 			c[i] = true
 			b[i] = true
 			goto Li0
 		}
 	)
 	for i := 0; i < *N; i++ {
 		go computer(i)
 	}
 	time.Sleep(*T)
 }

 func boolSlice(n int, iv bool) []bool {
 	b := make([]bool, n)
 	for i := 0; i < len(b); i++ {
 		b[i] = iv
 	}
 	return b
 }
diff --git a/sketch.go b/sketch.go
 // Attempts at a solution to Dijkstra's 1965 concurrency puzzle.
 //
 // * N computers, cyclic program
 // * each program has one critical section
 // * only one critical section is allowed to run
 // * computer may communicate by reading and writing to memory (one read and one write is atomic)
 //
 // Idea
 //
 // If we have N processes (P1, P2, ..., PN), we require N+1 memory cells.
 // P1 wants to enter critical section. It sets M1. P1 checks whether any other
 // process cell is set. If so, then it unset M1, sleeps a bit a will reattempt
 // then.
 //
 // If after setting M1, all other cells remain zero, P1 sets M0 and enter
 // critical section. Upon leaving, if clears M0 and M1.
 package main

 import (
 	"flag"
 	"log"
 	"math/rand"
 	"time"
 )

 type Memory struct {
 	words []int
 }

 func New(size int) *Memory {
 	return &Memory{words: make([]int, size)}
 }

 // Set a flag at a position.
 func (m *Memory) Set(i int) {
 	m.words[i] = 1
 }

 // Unset clear memory at position.
 func (m *Memory) Unset(i int) {
 	m.words[i] = 0
 }

 // IsSet returns true, if memory cell is set.
 func (m *Memory) IsSet(i int) bool {
 	return m.words[i] == 1
 }

 // IsZero returns true, if all cells are zero.
 func (m *Memory) IsZero() bool {
 	for _, b := range m.words {
 		if b != 0 {
 			return false
 		}
 	}
 	return true
 }

 // IsZeroExcept returns true, if all positions of memory except position x are zero.
 func (m *Memory) IsZeroExcept(x int) bool {
 	for i, w := range m.words {
 		if i == x {
 			continue
 		}
 		if w != 0 {
 			return false
 		}
 	}
 	return true
 }

 // Lock attempts signal that a process `i` wants to enter its critical section.
 // Returns true, if it succeeded.
 func (m *Memory) Lock(i int) {
 	var attempts = 1
 	for {
 		if m.IsSet(0) {
 			time.Sleep(time.Duration(attempts) * time.Millisecond)
 			attempts++
 			continue
 		}
 		m.Set(i)
 		if m.IsZeroExcept(i) {
 			m.Set(0) // lock acquired
 			break
 		}
 		m.Unset(i)
 	}
 }

 func (m *Memory) Unlock(i int) {
 	m.Unset(0)
 	m.Unset(i)
 }

 type Process struct {
 	PID     int
 	M       *Memory
 	counter map[int]int
 }

 func (p *Process) Run() {
 	log.Printf("[%d] started", p.PID)
 	var (
 		started time.Time
 		elapsed time.Duration
 	)
 	for {
 		time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond)
 		started = time.Now()
 		p.M.Lock(p.PID)
 		elapsed = time.Since(started)
 		log.Printf("[%d] entered [%v]", p.PID, elapsed)
 		p.counter[p.PID]++
 		time.Sleep(time.Duration(rand.Intn(20)) * time.Millisecond)
 		p.M.Unlock(p.PID)
 		log.Printf("[%d] exit", p.PID)
 	}
 }

 var (
 	N    = flag.Int("n", 2, "number of processes")
 	T    = flag.Duration("t", 500*time.Millisecond, "exit simulation after t seconds")
 	seed = flag.Int64("S", time.Now().UTC().UnixNano(), "seed")
 )

 func main() {
 	flag.Parse()
 	rand.Seed(*seed)
 	var (
 		m       = New(*N + 1)
 		counter = make(map[int]int)
 	)
 	log.Printf("initialized memory: %v", m)
 	for i := 1; i <= *N; i++ {
 		counter[i] = 0
 		process := &Process{
 			PID:     i,
 			M:       m,
 			counter: counter,
 		}
 		go process.Run()
 	}
 	time.Sleep(*T)
 	log.Println("[X] timeout")
 	for k, v := range counter {
 		log.Printf("%d => %d", k, v)
 	}
 }

 // 2021/06/05 01:56:18 initialized memory: &{[0 0 0 0 0 0 0 0 0 0]}
 // 2021/06/05 01:56:18 [9] started
 // 2021/06/05 01:56:18 [9] entered [374ns]
 // 2021/06/05 01:56:18 [1] started
 // 2021/06/05 01:56:18 [6] started
 // 2021/06/05 01:56:18 [7] started
 // 2021/06/05 01:56:18 [8] started
 // 2021/06/05 01:56:18 [3] started
 // 2021/06/05 01:56:18 [2] started
 // 2021/06/05 01:56:18 [4] started
 // 2021/06/05 01:56:18 [5] started
 // 2021/06/05 01:56:18 [9] exit
 // 2021/06/05 01:56:18 [3] entered [16.820926ms]
 // 2021/06/05 01:56:18 [3] exit
 // 2021/06/05 01:56:18 [5] entered [24.362396ms]
 // 2021/06/05 01:56:18 [5] exit
 // 2021/06/05 01:56:18 [9] entered [2.15594ms]
 // 2021/06/05 01:56:18 [9] exit
 // 2021/06/05 01:56:18 [8] entered [10.776265ms]
 // 2021/06/05 01:56:18 [8] exit
 // 2021/06/05 01:56:18 [3] entered [631ns]
 // 2021/06/05 01:56:18 [3] exit
 // 2021/06/05 01:56:18 [2] entered [69.099468ms]
 // 2021/06/05 01:56:18 [2] exit
 // 2021/06/05 01:56:18 [6] entered [15.465933ms]
 // 2021/06/05 01:56:18 [6] exit
 // 2021/06/05 01:56:18 [4] entered [18.820081ms]
 // 2021/06/05 01:56:18 [4] exit
 // 2021/06/05 01:56:18 [1] entered [40.404119ms]
 // 2021/06/05 01:56:18 [1] exit
 // 2021/06/05 01:56:18 [8] entered [498ns]
 // 2021/06/05 01:56:18 [8] exit
 // 2021/06/05 01:56:18 [4] entered [19.501583ms]
 // 2021/06/05 01:56:18 [4] exit
 // 2021/06/05 01:56:18 [5] entered [62.11501ms]
 // 2021/06/05 01:56:18 [5] exit
 // 2021/06/05 01:56:18 [9] entered [13.888874ms]
 // 2021/06/05 01:56:18 [9] exit
 // 2021/06/05 01:56:18 [2] entered [62.859946ms]
 // 2021/06/05 01:56:18 [2] exit
 // 2021/06/05 01:56:18 [6] entered [79.3289ms]
 // 2021/06/05 01:56:18 [X] timeout
	// Solution of a Problem in Concurrent Program Control
	//
	// Dijkstra, 1965: http://rust-class.org/static/classes/class19/dijkstra.pdf
	// https://i.imgur.com/weHFuip.png
	//
	// Notes:
	//
	// * if b[i] is true, then the program is not "looping", e.g. not waiting to enter a critical section
	// * if b[i] is false (Li0), the program entered "looping" stage, before the critical section
	//
	// k looks like a "selector", the "if" statement in Li1 like a two-stage "check"
	//
	// First we want k and i be the same; which only happens, if current
	// program k is not waiting (i.e. b[k] is true).
	//
	// If the program at k is not waiting, we can jump to the next branch (Li4).
	//
	// Here, we want all other programs not in the critical section; also
	// setting c[i] to false to indicate, that we want to run.
	//
	package main

	import (
	"bytes"
	"flag"
	"fmt"
	"io"
	"math/rand"
	"time"
	)

	const (
	Enter = "\u001b[32mE\u001b[0m"
	Exit = "\u001b[31mX\u001b[0m"
	False = "\u001b[34mF\u001b[0m"
	True = "\u001b[37mT\u001b[0m"
	)

	var (
	N = flag.Int("n", 3, "number of processes")
	T = flag.Duration("t", 1000*time.Millisecond, "exit simulation after t (e.g. 1s, 100ms, ...)")
	Cdur = flag.Duration("C", 10*time.Millisecond, "critical section duration")
	Rdur = flag.Duration("R", 100*time.Millisecond, "remainder duration")
	)

	func main() {
	flag.Parse()
	// The integer k will satisfy 1 <= k <= N, b[i] and c[i] will only be set
	// by the ith computer; they will be inspected by others. [...] all
	// boolean arrays mentioned set to true. The starting value of k is
	// immaterial.
	var (
	k int = 0
	b = make([]bool, *N)
	c = make([]bool, *N)
	)
	setTrue(b)
	setTrue(c)

	// The program for the ith computer [...]
	computer := func(i int) {
	fmt.Printf("[%d] R .. k=%v, b=%v, c=%v\n", i, k, Btoa(b), Btoa(c))
	Li0:
	fmt.Printf("[%d] Li0 k=%v, b=%v, c=%v\n", i, k, Btoa(b), Btoa(c))
	b[i] = false
	Li1:
	if k != i {
	c[i] = true
	// Li3
	if b[k] {
	k = i
	}
	goto Li1
	} else {
	// Li4
	c[i] = false
	for j := 0; j < *N; j++ {
	if j != i && !c[j] {
	goto Li1
	}
	}
	}
	// Critical section, only at most one "computer" will be in this section at any time.
	fmt.Printf("[%d] %s >> k=%v, b=%v, c=%v\n", i, Enter, k, Btoa(b), Btoa(c))
	time.Sleep(*Cdur)
	fmt.Printf("[%d] %s << k=%v, b=%v, c=%v\n", i, Exit, k, Btoa(b), Btoa(c))
	// Critical section ends.

	c[i] = true
	b[i] = true

	fmt.Printf("[%d] Rem k=%v, b=%v, c=%v\n", i, k, Btoa(b), Btoa(c))
	time.Sleep(time.Duration(rand.Int63n(Rdur.Milliseconds())) * time.Millisecond)
	goto Li0
	}
	for i := 0; i < *N; i++ {
	go computer(i)
	}
	time.Sleep(*T)
	fmt.Println("[X] timeout")
	}

	func setTrue(b []bool) {
	for i := 0; i < len(b); i++ {
	b[i] = true
	}
	}

	func Btoa(b []bool) string {
	var buf bytes.Buffer
	for _, v := range b {
	if v {
	io.WriteString(&buf, True)
	} else {
	io.WriteString(&buf, False)
	}
	}
	return buf.String()
	}

	// Appendix A: The Proof
	//
	// We start b y observing that the solution is safe in the
	// sense that no two computers can be in their critical section
	// simultaneously. For the only way to enter its critical
	// section is the performance of the compound statement
	// Li4 without jmnping back to Lil, i.e., finding all other
	// c's t r u e after having set its own e to false.
	// The second part of the proof must show that no infinite
	// "After you"-"After you"-blocking can occur; i.e., when
	// none of the computers is in its critical section, of the
	// computers looping (i.e., jumping back to Lil) at least
	// one--and therefore exactly one--will be allowed to enter
	// its critical section in due time.
	// If the kth computer is not among the looping ones,
	// bik] will be t r u e and the looping ones will all find k # i.
	// As a result one or mnore of them will find in Li3 the Boolean
	// b[k] t r u e and therefore one or more will decide to assign
	// "k : = i". After the first assignment "k : = i", b[k] becomes false and no new computers can decide again to
	// assign a new value to k. When all decided assignments to
	// k have been performed,/c will point to one of the looping
	// computers and will not change its value for the time being,
	// i.e., until b[k] becomes t r u e , viz., until the kth computer
	// has completed its critical section. As soon as the value of
	// ]c does not change any more, the kth computer will wait
	// (via the compound statement Li4) until all other c's are
	// t r u e , but this situation will certainly arise, if not already
	// present, because all other looping ones are forced to set
	// their e t r u e , as they will find k # i. And this, the author
	// believes, completes the proof.
	//
	// Appendix B: Race
	// ==================
	// WARNING: DATA RACE
	// Write at 0x00c0000bc051 by goroutine 8:
	// main.main.func1()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:65 +0xf8e
	//
	// Previous read at 0x00c0000bc051 by goroutine 7:
	// main.Btoa()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:111 +0xb5
	// main.main.func1()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:84 +0x536
	//
	// Goroutine 8 (running) created at:
	// main.main()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
	//
	// Goroutine 7 (running) created at:
	// main.main()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
	// ==================
	// ==================
	// WARNING: DATA RACE
	// Write at 0x00c0000bc054 by goroutine 8:
	// main.main.func1()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:68 +0x364
	//
	// Previous read at 0x00c0000bc054 by goroutine 9:
	// main.Btoa()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:111 +0xb5
	// main.main.func1()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:64 +0xdb3
	//
	// Goroutine 8 (running) created at:
	// main.main()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
	//
	// Goroutine 9 (running) created at:
	// main.main()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
	// ==================
	// ==================
	// WARNING: DATA RACE
	// Read at 0x00c0000bc055 by goroutine 7:
	// main.Btoa()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:111 +0xb5
	// main.main.func1()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:86 +0x7fc
	//
	// Previous write at 0x00c0000bc055 by goroutine 9:
	// main.main.func1()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:68 +0x364
	//
	// Goroutine 7 (running) created at:
	// main.main()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
	//
	// Goroutine 9 (running) created at:
	// main.main()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
	// ==================
	// ==================
	// WARNING: DATA RACE
	// Write at 0x00c0000bc050 by goroutine 7:
	// main.main.func1()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:90 +0xa5d
	//
	// Previous read at 0x00c0000bc050 by goroutine 9:
	// main.main.func1()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:70 +0x3ea
	//
	// Goroutine 7 (running) created at:
	// main.main()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
	//
	// Goroutine 9 (running) created at:
	// main.main()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
	// ==================
	// ==================
	// WARNING: DATA RACE
	// Write at 0x00c0000bc048 by goroutine 8:
	// main.main.func1()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:71 +0x418
	//
	// Previous read at 0x00c0000bc048 by goroutine 7:
	// main.main.func1()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:86 +0x844
	//
	// Goroutine 8 (running) created at:
	// main.main()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
	//
	// Goroutine 7 (running) created at:
	// main.main()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
	// ==================
	// ==================
	// WARNING: DATA RACE
	// Write at 0x00c0000bc053 by goroutine 7:
	// main.main.func1()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:68 +0x364
	//
	// Previous read at 0x00c0000bc053 by goroutine 8:
	// main.main.func1()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:78 +0x4dd
	//
	// Goroutine 7 (running) created at:
	// main.main()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
	//
	// Goroutine 8 (running) created at:
	// main.main()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
	// ==================
	// ==================
	// WARNING: DATA RACE
	// Read at 0x00c0000bc052 by goroutine 7:
	// main.Btoa()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:111 +0xb5
	// main.main.func1()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:64 +0xd64
	//
	// Previous write at 0x00c0000bc052 by goroutine 9:
	// main.main.func1()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:90 +0xa5d
	//
	// Goroutine 7 (running) created at:
	// main.main()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
	//
	// Goroutine 9 (running) created at:
	// main.main()
	// /home/tir/code/miku/18d13ab0c7de09120a26f8ebe153ad27/dijkstra65.go:97 +0x504
	// ==================
	// Found 7 data race(s)
	// exit status 66
	Solution of a Problem in
	Concurrent Programming Control

	computer can only request one one-way message at a time.
	And only this will make the reader realize to what extent
	this problem is far from trivial.

	E. W. DIJXSTRA

	The Solution

	Technological University, Eindhoven, The Netherlands

	The common store consists of:
	" B o o l e a n array b, c[l:N];

	A number of mainly independent sequential-cyclic processes
	with restricted means of communication with each other can
	be made in such a way that at any moment one and only one
	of them is e n g a g e d in the "critical section" of its cycle.

	Introduction

	Given in this paper is a solution to a problem for which,
	to the knowledge of the author, has been an open question
	since at least 1962, irrespective of the solvability. The
	paper consists of three parts: the problem, the solution,
	and the proof. Although the setting of the problem might
	seem somewhat academic at first, the author trusts that
	anyone familiar with the logical problems that arise in
	computer coupling will appreciate the significance of the
	fact that this problem indeed can be solved.
	The Problem

	To begin, consider N computers, each engaged in a
	process which, for our aims, can be regarded as cyclic. In
	each of the cycles a so-cMled "critical section" occurs and
	the computers have to be programmed in such a way that
	at any moment only one of these N cyclic processes is in
	its critical section. In order to effectuate this mutual
	exclusion of critical-section execution the computers can
	communicate with each other via a common store. Writing
	a word into or nondestructively reading a word from this
	store are undividable operations; i.e., when two or more
	computers try to communicate (either for reading or for
	writing) simultaneously with the same common location,
	these communications will take place one after the other,
	but in an unknown order.
	The solution must satisfy the following requirements.
	(a) The solution must be symmetrical between the N
	computers; as a result we are not allowed to introduce a
	static priority.
	(b) Nothing m a y be assumed about the relative speeds
	of the N computers; we may not even assume their speeds
	to be constant in time.
	(c) If any of the computers is stopped well outside its
	critical section, this is not allowed to lead to potential
	blocking of the others.
	(d) If more than one computer is about to enter its
	critical section, it must be impossible to devise for them
	such finite speeds, that the decision to determine which
	one of them will enter its critical section first is postponed
	until eternity. In other words, constructions in which
	"After you"-"After you"-blocking is still possible, although
	improbable, are not to be regarded as valid solutions.
	We beg the challenged reader to stop here for a while
	and have a try himself, for this seems the only way to get
	a feeling for the tricky consequences of the fact that each
	Vohm, e 8 / Number

	9 / September,

	1965

	integer k"

	The integer k will satisfy 1 < k < N, bill and c[i]
	will only be set by the ith computer; they will be inspected
	by the others. I t is assumed that all computers are started
	well outside their critical sections with all Boolean arrays
	mentioned set to t r u e ; the starting value of k is immaterial.
	The program for the ith computer (1 < i < N) is:
	"integer j;

	LiO: b[i] : = f a l s e ;
	Lil: i f k # i t h e n
	Li2: b e g i n c[i] : = true;
	Li3: i f b [ k ] t h e n k
	:=i;
	g o t o Lil

	Li4:

	end
	else
	b e g i n c[i] : = f a l s e ;
	for j : = 1 s t e p 1 u n t i l N do
	i f j # i a n d n o t c[j] t h e n go to Lil
	end ;
	critical s e c t i o n ;
	c[i] : = t r u e ; bill : = t r u e ;
	r e m a i n d e r of t h e cycle in w h i c h s t o p p i n g is a l l o w e d ;
	g o t o LiO"

	The Proof

	We start b y observing that the solution is safe in the
	sense that no two computers can be in their critical section
	simultaneously. For the only way to enter its critical
	section is the performance of the compound statement
	Li4 without jmnping back to Lil, i.e., finding all other
	c's t r u e after having set its own e to false.
	The second part of the proof must show that no infinite
	"After you"-"After you"-blocking can occur; i.e., when
	none of the computers is in its critical section, of the
	computers looping (i.e., jumping back to Lil) at least
	one--and therefore exactly one--will be allowed to enter
	its critical section in due time.
	If the kth computer is not among the looping ones,
	bik] will be t r u e and the looping ones will all find k # i.
	As a result one or mnore of them will find in Li3 the Boolean
	b[k] t r u e and therefore one or more will decide to assign
	"k : = i". After the first assignment "k : = i", b[k] becomes false and no new computers can decide again to
	assign a new value to k. When all decided assignments to
	k have been performed,/c will point to one of the looping
	computers and will not change its value for the time being,
	i.e., until b[k] becomes t r u e , viz., until the kth computer
	has completed its critical section. As soon as the value of
	]c does not change any more, the kth computer will wait
	(via the compound statement Li4) until all other c's are
	t r u e , but this situation will certainly arise, if not already
	present, because all other looping ones are forced to set
	their e t r u e , as they will find k # i. And this, the author
	believes, completes the proof.
	Communications

	of the ACM

	569
	// Attempts at a solution to Dijkstra's 1965 concurrency puzzle.
	//
	// * N computers, cyclic program
	// * each program has one critical section
	// * only one critical section is allowed to run
	// * computer may communicate by reading and writing to memory (one read and one write is atomic)
	//
	// Idea
	//
	// If we have N processes (P1, P2, ..., PN), we require N+1 memory cells.
	// P1 wants to enter critical section. It sets M1. P1 checks whether any other
	// process cell is set. If so, then it unset M1, sleeps a bit a will reattempt
	// then.
	//
	// If after setting M1, all other cells remain zero, P1 sets M0 and enter
	// critical section. Upon leaving, if clears M0 and M1.
	package main

	import (
	"flag"
	"log"
	"math/rand"
	"time"
	)

	type Memory struct {
	words []int
	}

	func New(size int) *Memory {
	return &Memory{words: make([]int, size)}
	}

	// Set a flag at a position.
	func (m *Memory) Set(i int) {
	m.words[i] = 1
	}

	// Unset clear memory at position.
	func (m *Memory) Unset(i int) {
	m.words[i] = 0
	}

	// IsSet returns true, if memory cell is set.
	func (m *Memory) IsSet(i int) bool {
	return m.words[i] == 1
	}

	// IsZero returns true, if all cells are zero.
	func (m *Memory) IsZero() bool {
	for _, b := range m.words {
	if b != 0 {
	return false
	}
	}
	return true
	}

	// IsZeroExcept returns true, if all positions of memory except position x are zero.
	func (m *Memory) IsZeroExcept(x int) bool {
	for i, w := range m.words {
	if i == x {
	continue
	}
	if w != 0 {
	return false
	}
	}
	return true
	}

	// Lock attempts signal that a process `i` wants to enter its critical section.
	// Returns true, if it succeeded.
	func (m *Memory) Lock(i int) {
	var attempts = 1
	for {
	if m.IsSet(0) {
	time.Sleep(time.Duration(attempts) * time.Millisecond)
	attempts++
	continue
	}
	m.Set(i)
	if m.IsZeroExcept(i) {
	m.Set(0) // lock acquired
	break
	}
	m.Unset(i)
	}
	}

	func (m *Memory) Unlock(i int) {
	m.Unset(0)
	m.Unset(i)
	}

	type Process struct {
	PID int
	M *Memory
	counter map[int]int
	}

	func (p *Process) Run() {
	log.Printf("[%d] started", p.PID)
	var (
	started time.Time
	elapsed time.Duration
	)
	for {
	time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond)
	started = time.Now()
	p.M.Lock(p.PID)
	elapsed = time.Since(started)
	log.Printf("[%d] entered [%v]", p.PID, elapsed)
	p.counter[p.PID]++
	time.Sleep(time.Duration(rand.Intn(20)) * time.Millisecond)
	p.M.Unlock(p.PID)
	log.Printf("[%d] exit", p.PID)
	}
	}

	var (
	N = flag.Int("n", 2, "number of processes")
	T = flag.Duration("t", 500*time.Millisecond, "exit simulation after t seconds")
	seed = flag.Int64("S", time.Now().UTC().UnixNano(), "seed")
	)

	func main() {
	flag.Parse()
	rand.Seed(*seed)
	var (
	m = New(*N + 1)
	counter = make(map[int]int)
	)
	log.Printf("initialized memory: %v", m)
	for i := 1; i <= *N; i++ {
	counter[i] = 0
	process := &Process{
	PID: i,
	M: m,
	counter: counter,
	}
	go process.Run()
	}
	time.Sleep(*T)
	log.Println("[X] timeout")
	for k, v := range counter {
	log.Printf("%d => %d", k, v)
	}
	}

	// 2021/06/05 01:56:18 initialized memory: &{[0 0 0 0 0 0 0 0 0 0]}
	// 2021/06/05 01:56:18 [9] started
	// 2021/06/05 01:56:18 [9] entered [374ns]
	// 2021/06/05 01:56:18 [1] started
	// 2021/06/05 01:56:18 [6] started
	// 2021/06/05 01:56:18 [7] started
	// 2021/06/05 01:56:18 [8] started
	// 2021/06/05 01:56:18 [3] started
	// 2021/06/05 01:56:18 [2] started
	// 2021/06/05 01:56:18 [4] started
	// 2021/06/05 01:56:18 [5] started
	// 2021/06/05 01:56:18 [9] exit
	// 2021/06/05 01:56:18 [3] entered [16.820926ms]
	// 2021/06/05 01:56:18 [3] exit
	// 2021/06/05 01:56:18 [5] entered [24.362396ms]
	// 2021/06/05 01:56:18 [5] exit
	// 2021/06/05 01:56:18 [9] entered [2.15594ms]
	// 2021/06/05 01:56:18 [9] exit
	// 2021/06/05 01:56:18 [8] entered [10.776265ms]
	// 2021/06/05 01:56:18 [8] exit
	// 2021/06/05 01:56:18 [3] entered [631ns]
	// 2021/06/05 01:56:18 [3] exit
	// 2021/06/05 01:56:18 [2] entered [69.099468ms]
	// 2021/06/05 01:56:18 [2] exit
	// 2021/06/05 01:56:18 [6] entered [15.465933ms]
	// 2021/06/05 01:56:18 [6] exit
	// 2021/06/05 01:56:18 [4] entered [18.820081ms]
	// 2021/06/05 01:56:18 [4] exit
	// 2021/06/05 01:56:18 [1] entered [40.404119ms]
	// 2021/06/05 01:56:18 [1] exit
	// 2021/06/05 01:56:18 [8] entered [498ns]
	// 2021/06/05 01:56:18 [8] exit
	// 2021/06/05 01:56:18 [4] entered [19.501583ms]
	// 2021/06/05 01:56:18 [4] exit
	// 2021/06/05 01:56:18 [5] entered [62.11501ms]
	// 2021/06/05 01:56:18 [5] exit
	// 2021/06/05 01:56:18 [9] entered [13.888874ms]
	// 2021/06/05 01:56:18 [9] exit
	// 2021/06/05 01:56:18 [2] entered [62.859946ms]
	// 2021/06/05 01:56:18 [2] exit
	// 2021/06/05 01:56:18 [6] entered [79.3289ms]
	// 2021/06/05 01:56:18 [X] timeout