A Verified Parallel Scheduler for OCaml 5
Open Access
- 8 June 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (PLDI) , 2253-2276
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.Keywords
This publication has 40 references indexed in Scilit:
- Scheduling computations with provably low synchronization overheadsJournal of Scheduling, 2021
- Nowa: A Wait-Free Continuation-Stealing Concurrency Platform2021
- Iris from the ground up: A modular foundation for higher-order concurrent separation logicJournal of Functional Programming, 2018
- A mechanized refinement proof of the Chase–Lev deque using a proof systemComputing, 2018
- Lace: Non-blocking Split Deque for Work-Stealing2014
- TaDA: A Logic for Time and Data Abstraction2014
- Resources, concurrency, and local reasoningTheoretical Computer Science, 2007
- Separation logic: a logic for shared mutable data structures2003
- Local Reasoning about Programs that Alter Data Structures2001
- Cilk: An Efficient Multithreaded Runtime SystemJournal of Parallel and Distributed Computing, 1996