Reasoning about the correctness of multithreaded programs is complicated by the potential for unexpected interference between threads. Previous work on controlling thread interference focused on verifying race freedom and/or atomicity. Unfortunately, race freedom is insufficient to prevent unintended thread interference. The notion of atomic blocks provides more semantic guarantees, but offers limited benefits for non-atomic code and it requires bimodal sequential/multithreaded reasoning (depending on whether code is inside or outside an atomic block). This paper proposes an alternative strategy that uses yield annotations to control thread interference, and we present an effect system for verifying the correctness of these yield annotations. The effect system guarantees that for any preemptively-scheduled execution of a well-formed program, there is a corresponding cooperative execution with equivalent behavior in which context switches happen only at yield annotations. This effect system enables cooperative reasoning: the programmer can adopt the simplifying assumption of cooperative scheduling, even though the program still executes with preemptive scheduling and/or true concurrency on multicore processors. Unlike bimodal sequential/multithreaded reasoning, cooperative reasoning can be applied to all program code. Keywords Effect system, yield, atomicity, race conditions Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. TLDI'10, January 23, 2010, Madrid, Spain. Copyright c 2010 ACM 978-1-60558-891-9/10/01. . . $10.00 Categories and Subject Descriptors Multiple threads of control are widely used in software development because they help reduce latency and increase throughput on multicore and multiprocessor machines. Reasoning about the behavior and correctness of multithreaded code is difficult, however, due to the need to consider all possible interleavings of the various threads. Thus, methods for specifying and controlling the interference between threads are crucial to the cost-effective development of reliable multithreaded software. Race Freedom Early attempts at controlling thread interference focused on race conditions, where two threads access a shared variable at the same time, and at least one access is a write. Race freedom ensures that thread interference occurs only at certain actions (those that manipulate volatile variables, locks, semaphores, etc). By itself, race freedom does not entirely prevent errors due to unexpected interactions between threads. We illustrate this limitation via the following code, in which the shared variable x is protected by the lock m, and t is a thread-local variable: acquire(m); t = x; release(m); t = t + 1; acquire(m); x = t; release(m); Although this code is race-free, it may not have the expected effect of incrementing m by 1, due to interference from other threads. Similar but less obvious errors arise in practice, often via multiple calls to synchronized methods [19] . Atomicity Motivated by this limitation of race-freedom, much recent work [5, 6, 18-23, 27, 40, 49-52] has used atomic blocks to specify where thread interference may occur. Programs can use traditional synchronization idioms (locks, etc.) to ensure that atomic blocks cannot be influenced by interleaved actions of concurrent threads. The atomic block annotations in a program are correct if any execution trace is serializable, that is, equivalent to a serial trace in which atomic blocks execute contiguously, without interleaved actions of other threads. Atomic blocks are amenable to sequential reasoning, which significantly simplifies subsequent correctness arguments. Despite the benefits of atomicity, it suffers from two significant limitations. First, atomicity forces a form of bimodal sequential/-multithreaded reasoning. To illustrate this point, consider the simple code fragment 1 : x++ If sequential reasoning is valid, then this code is a simple increment operation. If multithreaded reasoning is required, then this code becomes a potentially non-atomic read-modify-write sequence (with no syntactic hints to reflect this sea change from traditional, sequential semantics).
The notion of cooperability was introduced by Yi and Flanagan REF .
Effects for cooperable and serializable threads
TLDI '10
Computer Science