What does Atomic Locks for Many Windows conclude, in numbers, about “The Race Window: Exhaustive Interleavings of Check-then-Create and Their Width on the Wall Clock”?
Answer: Program p11 counted every schedule: with two windows using check-then-create, 12 of 16 schedules give a double claim; with four windows, 74880 of 74976. Atomic exclusive creation has no bad schedule at any window count. Program p12 converted the gap to the wall clock: collisions are rare when starts are spread out, and about 0.02966 per batch when windows rush in together. Yet this chapter has only answered which primitive to use. A more fundamental question remains: if the file system offered no exclusive creation and only atomic reads and writes, could several windows still exclude each other? Dijkstra answered yes in 1965. The next chapter checks his answer with a small model checker and explains why it cannot be used for many windows.
Scope of the numbers: Marked boxes separate published evidence, runnable Python calculations (19 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 12, 16, 74880, 74976
| protocol | n | schedules | double-hold | share | P(uniform) |
|---|---|---|---|---|---|
| check-then-create 2 | 16 | 12 | 0.7500 | 0.5000 | |
| check-then-create 3 | 702 | 684 | 0.9744 | 0.6667 | |
| check-then-create 4 | 74976 | 74880 | 0.9987 | 0.7500 | |
| exclusive-create | 2 | 4 | 0 | 0.0000 | 0.0000 |
| exclusive-create | 3 | 18 | 0 | 0.0000 | 0.0000 |
| exclusive-create | 4 | 96 | 0 | 0.0000 | 0.0000 |
Show the full program
# Chapter 1. p11: every interleaving of n windows claiming one lock file,
# check-then-create against exclusive create, counted exactly.
# Model: an in-memory file system holding one name; no file is touched.
# Each window runs fixed atomic steps; the schedule picks which window
# moves next. Counts are exact (memoised over states); the probability
# column assumes a scheduler that picks a runnable window uniformly.
import math
from functools import lru_cache
# 先检查后创建:check(存在否) -> create(覆盖写) -> hold
# 独占创建:create_x(已存在即失败) -> hold
NAIVE = ("check", "create", "hold")
EXCL = ("create_x", "hold")
def run(prog, n):
@lru_cache(maxsize=None)
def walk(exists, procs):
live = [i for i, (pc, ok) in enumerate(procs)
if pc < len(prog) and ok]
if not live:
held = len([1 for pc, ok in procs if ok and pc == len(prog)])
bad = 1 if held >= 2 else 0
return 1, bad, float(bad)
tot, bad, pr = 0, 0, []
for i in live:
pc, ok = procs[i]
op = prog[pc]
ex = exists
if op == "check":
ok = not exists
elif op == "create":
ex = True
elif op == "create_x":
ok = not exists
ex = True
nxt = list(procs)
nxt[i] = (pc + 1, ok)
t, b, p = walk(ex, tuple(nxt))
tot += t
bad += b
pr.append(p)
return tot, bad, math.fsum(p / len(live) for p in pr)
return walk(False, tuple((0, True) for _ in range(n)))
print("protocol n schedules double-hold share P(uniform)")
for name, prog in (("check-then-create", NAIVE),
("exclusive-create", EXCL)):
for n in (2, 3, 4):
tot, bad, prob = run(prog, n)
print("%-17s %d %9d %11d %6.4f %6.4f"
% (name, n, tot, bad, bad / tot, prob))Single source and citation
Fan, Y. (2026). Atomic File-Lock Protocols for Multiple Windows: Self-Recovering Orphan Locks after Power Loss and Cross-Window Hand-Over State Machines (Version 1.0.0), Chapter 1: The Race Window: Exhaustive Interleavings of Check-then-Create and Their Width on the Wall Clock. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-254 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026254,
author = {Fan, Yafu},
title = {Atomic File-Lock Protocols for Multiple Windows: Self-Recovering Orphan Locks after Power Loss and Cross-Window Hand-Over State Machines},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 2 · Mutual Exclusion from Reads and Writes Alone: Model-Checking Six Entry Protocols and the Roster Bound
- Chapter 3 · After the Power Cut: Empty Locks, Missing Status and Write-Temporary-then-Link
- Chapter 4 · Leases, Clocks and Fencing Tokens
- Chapter 5 · Judging Orphan Locks: How Long a Silence Means Death
- Chapter 6 · State Machines for Hand-Over between Windows: Transfer, Tokens and a Status That Only Moves Forward
- Chapter 7 · Classical Sources East and West: the Gatekeeper Who "Keeps and Issues the Keys" and Dijkstra in 1965
- Chapter 8 · Closing the Loop: a Formal Health Check of This Series' Lock Protocol and a Pre-Registered Test