Delay-Bounded Scheduling

Michael Emmi, Shaz Qadeer, Zvonimir Rakamaric. 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2011), Austin, TX, USA.
[pdf] [bib]

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.


  author = {Michael Emmi and Shaz Qadeer and Zvonimir Rakamari\'c},
  title = {Delay-Bounded Scheduling},
  booktitle = {Proceedings of the 38th ACM SIGPLAN-SIGACT
    Symposium on Principles of Programming Languages (POPL 2011)},
  publisher = {ACM},
  editor = {Thomas Ball and Mooly Sagiv},
  year = {2011},
  pages = {411--422},

You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

Comments are closed.