Expressive modular fine-grained concurrency specification
Authors:
Open Access
- 26 January 2011
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 46 (1) , 271-282
Abstract
Compared to coarse-grained external synchronization of operations on data structures shared between concurrent threads, fine-grained, internal synchronization can offer stronger progress guarantees and better performance. However, fully specifying operations that perform internal synchronization modularly is a hard, open problem. The state of the art approaches, based on linearizability or on concurrent abstract predicates, have important limitations on the expressiveness of specifications. Linearizability does not support ownership transfer, and the concurrent abstract predicates-based specification approach requires hardcoding a particular usage protocol. In this paper, we propose a novel approach that lifts these limitations and enables fully general specification of fine-grained concurrent data structures. The basic idea is that clients pass the ghost code required to instantiate an operation's specification for a specific client scenario into the operation in a simple form of higher-order programming. We machine-checked the theory of the paper using the Coq proof assistant. Furthermore, we implemented the approach in our program verifier VeriFast and used it to verify two challenging fine-grained concurrent data structures from the literature: a multiple-compare-and-swap algorithm and a lock-coupling list.Keywords
This publication has 7 references indexed in Scilit:
- Automatically Proving Linearizability2010
- Verification of Concurrent Programs with Chalice2009
- VCC: Contract-based modular verification of concurrent C2009
- Permission accounting in separation logic2005
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990
- Verifying properties of parallel programsCommunications of the ACM, 1976
- An axiomatic proof technique for parallel programs IActa Informatica, 1976