A program logic for concurrent objects under fair scheduling
Authors:
Open Access
- 11 January 2016
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 51 (1) , 385-399
Abstract
Existing work on verifying concurrent objects is mostly concerned with safety only, e.g., partial correctness or linearizability. Although there has been recent work verifying lock-freedom of non-blocking objects, much less efforts are focused on deadlock-freedom and starvation-freedom, progress properties of blocking objects. These properties are more challenging to verify than lock-freedom because they allow the progress of one thread to depend on the progress of another, assuming fair scheduling. We propose LiLi, a new rely-guarantee style program logic for verifying linearizability and progress together for concurrent objects under fair scheduling. The rely-guarantee style logic unifies thread-modular reasoning about both starvation-freedom and deadlock-freedom in one framework. It also establishes progress-aware abstraction for concurrent objects, which can be applied when verifying safety and liveness of client code. We have successfully applied the logic to verify starvation-freedom or deadlock-freedom of representative algorithms such as ticket locks, queue locks, lock-coupling lists, optimistic lists and lazy lists.Keywords
Funding Information
- National Natural Science Foundation of China (61229201, 61379039, 91318301, 61502442)
This publication has 31 references indexed in Scilit:
- Mechanically verified proof obligations for linearizabilityACM Transactions on Programming Languages and Systems, 2011
- Abstraction for concurrent objectsTheoretical Computer Science, 2010
- Local rely-guarantee reasoningACM SIGPLAN Notices, 2009
- Proving that non-blocking algorithms don't blockACM SIGPLAN Notices, 2009
- Ownership types for safe programmingACM SIGPLAN Notices, 2002
- Fair SimulationInformation and Computation, 2002
- The rely-guarantee method for verifying shared variable concurrent programsFormal Aspects of Computing, 1997
- Conjoining specificationsACM Transactions on Programming Languages and Systems, 1995
- Algorithms for scalable synchronization on shared-memory multiprocessorsACM Transactions on Computer Systems, 1991
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990