关于「独占新建锁:冲突率、顺延成本与丢失更新」,《并发拓扑耦合与黑板复用》给出的定量结论是什么?
结论:第三章在内存里模拟独占新建锁:覆盖写的丢失比例在十六个写者时达到 0.907,独占新建没有一个号被两个窗口同时持有,按序申请或一次只持一把锁即可消除死锁。
数据口径:书中参数为示意,数据为合成,全部计算由书中程序生成;本书是非个人化经营建议,不提供任何加速比承诺。 第一章说明峰值从何而来,示意参数下峰值在 6.78 个窗口附近。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.907
| A. 50 trials, 40 events per writer | ||||
| writers | events | lost (overwrite) | share | CAS retries/event |
| 2 | 4,000 | 1,740 | 0.435 | 0.527 |
| 4 | 8,000 | 5,516 | 0.690 | 1.267 |
| 8 | 16,000 | 13,274 | 0.830 | 2.382 |
| 16 | 32,000 | 29,030 | 0.907 | 3.924 |
| B. events lost under CAS and under append, all runs: 0 |
查看完整验算程序
# Chapter 3. p32: lost updates under overwrite vs compare-and-swap vs append.
# N writers each record M = 40 progress events in one shared status.
# Overwrite: read the value, think for a while, write value + 1; any
# write in between is silently lost. CAS: write only if the value is
# unchanged since the read, else re-read and retry. Append: each event
# is its own entry at the end of a log, the count is the log length.
# Random interleaving in memory; the think time is 0 to 3 steps.
import random
M = 40
TRIALS = 50
def overwrite(n, rng):
val = 0
plan = {w: M for w in range(n)}
read = {w: None for w in range(n)}
wait = {w: 0 for w in range(n)}
act = list(range(n))
while act:
w = act[rng.randrange(len(act))]
if read[w] is None:
read[w] = val
wait[w] = rng.randrange(4)
elif wait[w] > 0:
wait[w] -= 1
else:
val = read[w] + 1
read[w] = None
plan[w] -= 1
if plan[w] == 0:
act.remove(w)
return val
def cas(n, rng):
val = retries = 0
plan = {w: M for w in range(n)}
read = {w: None for w in range(n)}
wait = {w: 0 for w in range(n)}
act = list(range(n))
while act:
w = act[rng.randrange(len(act))]
if read[w] is None:
read[w] = val
wait[w] = rng.randrange(4)
elif wait[w] > 0:
wait[w] -= 1
elif val != read[w]:
retries += 1
read[w] = None
else:
val += 1
read[w] = None
plan[w] -= 1
if plan[w] == 0:
act.remove(w)
return val, retries
def append(n, rng):
log = []
plan = {w: M for w in range(n)}
act = list(range(n))
while act:
w = act[rng.randrange(len(act))]
log.append((w, M - plan[w]))
plan[w] -= 1
if plan[w] == 0:
act.remove(w)
return len(log)
if __name__ == "__main__":
rng = random.Random(41132)
print("A. {} trials, {} events per writer".format(TRIALS, M))
print(" writers events lost (overwrite) share "
"CAS retries/event")
alost = 0
for n in (2, 4, 8, 16):
lost = rtot = 0
for _ in range(TRIALS):
lost += n * M - overwrite(n, rng)
v, r = cas(n, rng)
rtot += r
alost += n * M - v
alost += n * M - append(n, rng)
ev = n * M * TRIALS
print(" {:>7} {:>6,} {:>16,} {:>5.3f} {:>17.3f}"
.format(n, ev, lost, lost / ev, rtot / ev))
print("B. events lost under CAS and under append, all runs: {}"
.format(alost))唯一数据源与引用
范雅福(Fan, Y.). (2026). 《多核并发操作拓扑耦合、共享黑板无锁通信与跨节点涌现增益母典》第 3 章「独占新建锁:冲突率、顺延成本与丢失更新」(版本 1.0.0). 5D Library. DOI 待发布
DOI 待发布 · 专著页正式发布后上线(本站暂无专著页) · 5DL-B-411 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026411,
author = {Fan, Yafu},
title = {Topological Coupling of Concurrent Multi-Core Operations: Lock-Free Blackboard Signalling and Cross-Node Emergent Gains},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}