Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Delay-bounded scheduling

Michael Emmi, Shaz Qadeer, and Zvonimir Rakamaric

Abstract

We provide a new characterization of scheduling nondeterminism by allowing deterministic schedulers to delay their next-scheduled task. In limiting the delays an otherwise-deterministic scheduler is allowed, we discover concurrency bugs efficiently---by exploring few schedules---and robustly---i.e., independent of the number of tasks, context switches, or buffered events. Our characterization elegantly applies to any systematic exploration (e.g., testing, model checking) of concurrent programs with dynamic task-creation. Additionally, we show that certain delaying schedulers admit efficient reductions from concurrent to sequential program analysis.

Details

Publication typeInproceedings
Published inProceedings of the 38th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages
PublisherAssociation for Computing Machinery, Inc.
> Publications > Delay-bounded scheduling