Access Restriction

Author Liu, Yujie ♦ Dice, Dave ♦ Lev, Yossi ♦ Moir, Mark ♦ Luchangco, Victor
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 Hardware transactional memory ♦ Readers-writer lock
Abstract Designing correct synchronization algorithms is notoriously difficult, as evidenced by a bug we have identified that has apparently gone unnoticed in a well-known synchronization algorithm for nearly two decades. We use hardware transactional memory (HTM) to construct a corrected version of the algorithm. This version is significantly simpler than the original and furthermore improves on it by eliminating usage constraints and reducing space requirements. Performance of the HTM-based algorithm is competitive with the original in "normal" conditions, but it does suffer somewhat under heavy contention. We successfully apply some optimizations to help close this gap, but we also find that they are incompatible with known techniques for improving progress properties. We discuss ways in which future HTM implementations may address these issues. Finally, although our focus is on how effectively HTM can correct and simplify the algorithm, we also suggest bug fixes and workarounds that do not depend on HTM.
Description Affiliation: Oracle Labs, Burlington, MA, USA (Dice, Dave; Lev, Yossi; Luchangco, Victor; Moir, Mark) || Lehigh University, Bethlehem, PA, USA (Liu, Yujie)
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 48
Issue Number 8
Page Count 10
Starting Page 261
Ending Page 270

Open content in new tab

   Open content in new tab
Source: ACM Digital Library