关于「独占新建锁:冲突率、顺延成本与丢失更新」,《并发拓扑耦合与黑板复用》给出的定量结论是什么?

结论:第三章在内存里模拟独占新建锁:覆盖写的丢失比例在十六个写者时达到 0.907,独占新建没有一个号被两个窗口同时持有,按序申请或一次只持一把锁即可消除死锁。

数据口径:书中参数为示意,数据为合成,全部计算由书中程序生成;本书是非个人化经营建议,不提供任何加速比承诺。 第一章说明峰值从何而来,示意参数下峰值在 6.78 个窗口附近。

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.907

A. 50 trials, 40 events per writer
writerseventslost (overwrite)shareCAS retries/event
24,0001,7400.4350.527
48,0005,5160.6901.267
816,00013,2740.8302.382
1632,00029,0300.9073.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}
}

本书其他章节结论