Access Restriction

Author Spear, Michael F. ♦ Dalessandro, Luke ♦ Marathe, Virendra J. ♦ Scott, Michael L.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Software transactional memory ♦ Priority ♦ Contention management ♦ Inevitability ♦ Condition synchronization
Abstract In Software Transactional Memory (STM), contention management refers to the mechanisms used to ensure forward progress--to avoid livelock and starvation, and to promote throughput and fairness. Unfortunately, most past approaches to contention management were designed for obstruction-free STM frameworks, and impose significant constant-time overheads. Priority-based approaches in particular typically require that reads be visible to all transactions, an expensive property that is not easy to support in most STM systems. In this paper we present a comprehensive strategy for contention management via fair resolution of conflicts in an STM with invisible reads. Our strategy depends on (1) lazy acquisition of ownership, (2) extendable timestamps, and (3) an efficient way to capture both priority and conflicts. We introduce two mechanisms--one using Bloom filters, the other using visible read bits--that implement point (3). These mechanisms unify the notions of conflict resolution, inevitability, and transaction retry. They are orthogonal to the rest of the contention management strategy, and could be used in a wide variety of hardware and software TM systems. Experimental evaluation demonstrates that the overhead of the mechanisms is low, particularly when conflicts are rare, and that our strategy as a whole provides good throughput and fairness, including livelock and starvation freedom, even for challenging workloads.
Description Affiliation: Sun Microsystems Labs, Burlington, MA, USA (Marathe, Virendra J.) || University of Rochester, Rochester, NY, USA (Spear, Michael F.; Dalessandro, Luke; Scott, Michael L.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1983-05-01
Publisher Place New York
Journal ACM SIGPLAN Notices (SIGP)
Volume Number 44
Issue Number 4
Page Count 10
Starting Page 141
Ending Page 150

Open content in new tab

   Open content in new tab
Source: ACM Digital Library