Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Implementing multiple locks using Lamport's mutual exclusion algorithm

Implementing multiple locks using Lamport's mutual exclusion algorithm Implementing Multiple Locks Using Lamport ™s Mutual Exclusion Algorithm HANS-J. BOEHM Xerox PARC and CHRIS UHLER Xsoft and ALAN J. DEMERS We describe an approach for implementing higher-level mutual-exclusion constructs using Lamport ™s algorithm. A straightforward implementation of, for example, monitor locks based on Lamport ™s algorithm requires O(n) space per monitor lock if there are n processes that may share the lock. It has occasionally been claimed that this makes the algorithm undesirable in practice. The insight presented here is that we only need a (small) constant amount of space per lock, plus O(n) space shared by all locks in the system. For some common applications, this adds no memory references to the implementation of the algorithm. Fully general spin-lock acquisition and release can usually be implemented with the addition of one memory reference to Lamport ™s algorithm. On particularly unfavorable hardware, three additional memory references may be required in the contention-free case. D.3.3 Categories and Subject Descriptors: programming structures; Constructs ”concurrent [Programming D.4.1 Languages]: Language [Operating Systems]: Process Manage- ment ”mutual General Additional exclusion Terms: Algorithms, Verification Critical section, monitor lock, multiprocessing, spin lock Key Words and Phrases: 1. LAMPORT ™S Lamport ™s ware support ALGORITHM http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Letters on Programming Languages and Systems (LOPLAS) Association for Computing Machinery

Implementing multiple locks using Lamport's mutual exclusion algorithm

Download PDF
13 pages

Loading next page...
 
/lp/association-for-computing-machinery/implementing-multiple-locks-using-lamport-s-mutual-exclusion-algorithm-PezFcOH2BH
Publisher
Association for Computing Machinery
Copyright
Copyright © 1993 by ACM Inc.
ISSN
1057-4514
DOI
10.1145/176454.176479
Publisher site
See Article on Publisher Site

Abstract

Implementing Multiple Locks Using Lamport ™s Mutual Exclusion Algorithm HANS-J. BOEHM Xerox PARC and CHRIS UHLER Xsoft and ALAN J. DEMERS We describe an approach for implementing higher-level mutual-exclusion constructs using Lamport ™s algorithm. A straightforward implementation of, for example, monitor locks based on Lamport ™s algorithm requires O(n) space per monitor lock if there are n processes that may share the lock. It has occasionally been claimed that this makes the algorithm undesirable in practice. The insight presented here is that we only need a (small) constant amount of space per lock, plus O(n) space shared by all locks in the system. For some common applications, this adds no memory references to the implementation of the algorithm. Fully general spin-lock acquisition and release can usually be implemented with the addition of one memory reference to Lamport ™s algorithm. On particularly unfavorable hardware, three additional memory references may be required in the contention-free case. D.3.3 Categories and Subject Descriptors: programming structures; Constructs ”concurrent [Programming D.4.1 Languages]: Language [Operating Systems]: Process Manage- ment ”mutual General Additional exclusion Terms: Algorithms, Verification Critical section, monitor lock, multiprocessing, spin lock Key Words and Phrases: 1. LAMPORT ™S Lamport ™s ware support ALGORITHM

Journal

ACM Letters on Programming Languages and Systems (LOPLAS) – Association for Computing Machinery

Published: Mar 1, 1993

There are no references for this article.