2012 | OriginalPaper | Chapter
Isolating Determinism in Multi-threaded Programs
Authors : Lukasz Ziarek, Siddharth Tiwary, Suresh Jagannathan
Published in: Runtime Verification
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Futures are a program abstraction that express a simple form of fork-join parallelism. The expression
future (e)
declares that
e
can be evaluated concurrently with the
future
’s continuation.
Safe
-futures provide additional deterministic guarantees, ensuring that all data dependencies found in the original (non-future annotated) version are respected. In this paper, we present a dynamic analysis for enforcing determinism of safe-futures in an ML-like language with dynamic thread creation and first-class references. Our analysis tracks the interaction between futures (and their continuations) with other explicitly defined threads of control, and enforces an
isolation
property that prevents the effects of a continuation from being witnessed by its future, indirectly through their interactions with other threads. Our analysis is defined via a lightweight capability-based dependence tracking mechanism that serves as a compact representation of an effect history. Implementation results support our premise that futures and threads can extract additional parallelism compared to traditional approaches for safe-futures.