paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Frightening Small Children and Disconcerting Grown-ups

吓坏小孩,让大人不安
ASPLOS Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems2018匹配度 2/10 · 该论文聚焦 Linux 内核内存一致性的 cat 形式模型与 RCU 定律证明,属于并发内存模型和形式语义方向;虽兼具形式化与工业落地价值,但与用户核心关注的 LLM/Agent 与静态分析、浮点程序分析或贝叶斯程序分析的交叉方向没有直接关联。引用 37 inbox
Jade Alglave, Luc Maranget, Paul E. McKenney, Andrea Parri, Alan Stern
crossref: 2026-09-12

AI 速览

一句话:为 Linux 内核内存一致性提供可执行的 cat 形式模型,并用 herd 验证,形式化并证明 RCU 定律。

Linux 内核中的并发行为及其一致性模型长期存在争议:内核支持 30 多种 CPU 架构,程序应如何表现、在外来硬件上是否正确,需要精确规范。本文提出一个用 cat 语言编写的 Linux 内核内存一致性形式模型,该模型不仅形式化,还可由 herd 模拟器执行,便于程序员实验和建立直觉。作者将模型与真实硬件行为对照测试,并与内核维护者协商精化模型。最后,他们形式化了 Read-Copy-Update(RCU)同步机制的基本定律,并证明其中一种实现满足该定律。

问题
Linux 内核并发代码在多种 CPU 架构上的内存一致性行为缺乏统一、可执行的形式规范,导致正确性判断困难。
方法
用 cat 语言给出可执行的形式模型,由 herd 模拟器执行;将模型与真实硬件行为对照测试,并结合维护者意见精化;同时形式化 RCU 基本定律。
评估
通过对照真实硬件行为测试模型,并依据内核维护者反馈迭代精化;最后形式化并证明 RCU 基本定律及某个实现满足该定律。
原文摘要(Abstract)

Concurrency in the Linux kernel can be a contentious topic. The Linux kernel mailing list features numerous discussions related to consistency models, including those of the more than 30 CPU architectures supported by the kernel and that of the kernel itself. How are Linux programs supposed to behave? Do they behave correctly on exotic hardware? A formal model can help address such questions. Better yet, an executable model allows programmers to experiment with the model to develop their intuition. Thus we offer a model written in the cat language, making it not only formal, but also executable by the herd simulator. We tested our model against hardware and refined it in consultation with maintainers. Finally, we formalised the fundamental law of the Read-Copy-Update synchronisation mechanism, and proved that one of its implementations satisfies this law.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot4289,
  title = {Frightening Small Children and Disconcerting Grown-ups},
  author = {Jade Alglave and Luc Maranget and Paul E. McKenney and Andrea Parri and Alan Stern},
  booktitle = {ASPLOS},
  year = {2018},
  doi = {10.1145/3173162.3177156}
}