Quantitative Reasoning for Proving Lock-Freedom
Authors:
- Jan HoffmannJHJan Hoffmann
- Michael MarmarMMMichael Marmar
- Zhong ShaoZSZhong Shao
- 1 June 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10436871,p. 124-133
Abstract
This article describes a novel quantitative proof technique for the modular and local verification of lock-freedom. In contrast to proofs based on temporal rely-guarantee requirements, this new quantitative reasoning method can be directly integrated in modern program logics that are designed for the verification of safety properties. Using a single formalism for verifying memory safety and lock-freedom allows a combined correctness proof that verifies both properties simultaneously. This article presents one possible formalization of this quantitative proof technique by developing a variant of concurrent separation logic (CSL) for total correctness. To enable quantitative reasoning, CSL is extended with a predicate for affine tokens to account for, and provide an upper bound on the number of loop iterations in a program. Lock-freedom is then reduced to total-correctness proofs. Quantitative reasoning is demonstrated in detail, both informally and formally, by verifying the lock-freedom of Treiber's non-blocking stack. Furthermore, it is shown how the technique is used to verify the lock-freedom of more advanced shared-memory data structures that use elimination-backoff schemes and hazard-pointers.Keywords
This publication has 28 references indexed in Scilit:
- Data structures in the multicore ageCommunications of the ACM, 2011
- Scalable synchronous queuesCommunications of the ACM, 2009
- Local rely-guarantee reasoningACM SIGPLAN Notices, 2009
- A general technique for proving lock-freedomScience of Computer Programming, 2009
- A hybrid type system for lock-freedom of mobile processesACM Transactions on Programming Languages and Systems, 2008
- Hazard pointers: safe memory reclamation for lock-free objectsIEEE Transactions on Parallel and Distributed Systems, 2004
- Wait-free synchronizationACM Transactions on Programming Languages and Systems, 1991
- 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 basis for computer programmingCommunications of the ACM, 1969