A simple deterministic algorithm for guaranteeing the forward progress of transactions
This paper describes a remarkably simple deterministic (not probabilistic) contention-management algorithm for guaranteeing the forward progress of transactions - avoiding deadlocks, livelocks, and other anomalies. The transactions must be finite (no infinite loops), but on each restart, a transacti...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Elsevier
2018
|
| Online Access: | http://hdl.handle.net/1721.1/114871 https://orcid.org/0000-0001-6386-5552 |
| Summary: | This paper describes a remarkably simple deterministic (not probabilistic) contention-management algorithm for guaranteeing the forward progress of transactions - avoiding deadlocks, livelocks, and other anomalies. The transactions must be finite (no infinite loops), but on each restart, a transaction may access different shared-memory locations. The algorithm supports irrevocable transactions as long as the transaction satisfies a simple ordering constraint. In particular, a transaction that accesses only one shared-memory location is never aborted. The algorithm is suitable for both hardware and software transactional-memory systems. It also can be used in some contexts as a locking protocol for implementing transactions "by hand.". |
|---|