Academic Commons

Articles

Scheduling-Independent Threads and Exceptions in SHIM

Tardieu, Olivier; Edwards, Stephen A.

Concurrent programming languages should be a good fit for embedded systems because they match the intrinsic parallelism of their architectures and environments. Unfortunately, typical concurrent programming formalisms are prone to races and nondeterminism, despite the presence of mechanisms such as monitors. In this paper, we propose SHIM, the core of a deterministic concurrent language, meaning the behavior of a program is independent of the scheduling of concurrent operations. SHIM does not sacrifice power or flexibility to achieve this determinism. It supports both synchronous and asynchronous paradigms-loosely and tightly synchronized threads-the dynamic creation of threads and shared variables, recursive procedures, and exceptions. We illustrate our programming model with examples including breadth-first-search algorithms and pipelines. By construction, they are race-free. We provide the formal semantics of SHIM and a preliminary implementation.

Subjects

Files

  • thumnail for tardieu2006scheduling-independent.pdf tardieu2006scheduling-independent.pdf application/pdf 126 KB Download File

Also Published In

Title
EMSOFT 2006: proceedings of the Sixth ACM & IEEE International Conference on Embedded Software: October 22-25, 2006, Seoul, Korea, Embedded Systems Week 2006
DOI
https://doi.org/10.1145/1176887.1176908

More About This Work

Academic Units
Computer Science
Publisher
ACM Press
Published Here
September 22, 2011
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.