paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A Verified Parallel Scheduler for OCaml 5

经过验证的 OCaml 5 并行调度器
PLDI 10(PLDI)2026匹配度 2/10 · 该论文属于并发程序形式化验证(Iris/Zoo 验证 OCaml 5 并行调度器与 Chase-Lev 工作窃取队列),与用户的“形式化验证”方向有较弱交集,但未涉及 LLM/Agent 改进验证、静态分析、浮点程序分析或贝叶斯程序分析,因此匹配度低。引用 0 inbox
Clément Allain, Gabriel Scherer
crossref: 2026-09-10

AI 速览

一句话:在 Iris/Zoo 中实现并验证 OCaml 5 并行调度器,验证 Chase-Lev 工作窃取队列,提出 Iris 预言变量新抽象。

OCaml 5 引入并行域,其并行调度器(如 Domainslib)依赖工作窃取进行负载均衡,但其并发正确性缺乏机器验证。本文在基于 Iris 的 Zoo 框架中实现并机器验证了一个实际的 OCaml 5 并行调度器;该调度器具有灵活接口,既支持工作窃取,也支持其他调度策略。作为验证的一部分,作者验证了 Saturn 库中的 Chase-Lev 工作窃取双端队列,发现其具有微妙的、依赖外部与未来的线性化点,并为此在 Iris 中引入用于推理预言变量的新抽象。基准测试表明,该调度器性能与 OCaml 生态中其他调度器相当。

问题
OCaml 5 的并行调度器依赖工作窃取等并发算法,但其正确性(尤其是线性化点与内存安全)缺乏机器验证。
方法
在基于 Iris 的 Zoo 框架中实现并机器验证一个灵活的并行调度器,并验证 Saturn 中的 Chase-Lev 工作窃取双端队列;为处理其外部且依赖未来的线性化点,引入 Iris 中预言变量推理的新抽象。
评估
提供基础基准测试,表明该调度器性能与 OCaml 生态中的其他调度器相当。
原文摘要(Abstract)

We present the implementation and mechanized verification of a realistic parallel scheduler for OCaml 5 using the Iris-based Zoo framework. Similarly to Domainslib, it relies on a work-stealing strategy to perform load balancing but also supports other scheduling strategies thanks to its flexible interface. e provide basic benchmarks demonstrating that its performance is on par with other schedulers from the OCaml ecosystem. As part of this effort, we verify the Chase-Lev work-stealing deque, as implemented in the Saturn library. We show that it features a subtle external and future-dependent linearization point. To deal with it, we introduce new abstractions for reasoning about prophecy variables in Iris.

链接与引用

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

BibTeX
@article{AllainS26a,
  title = {A Verified Parallel Scheduler for OCaml 5},
  author = {Clément Allain and Gabriel Scherer},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {10},
  number = {PLDI},
  year = {2026},
  doi = {10.1145/3808337}
}