Performance issues in non-blocking synchronization on shared-memory multiprocessors

Juan Alemany, Edward W. Felten

Research output: Chapter in Book/Report/Conference proceedingConference contribution

34 Scopus citations

Abstract

This paper considers the implementation of non-blocking concurrent objects on shared-memory multiprocessors. Real multiprocessors have properties not present in theoretical models; these properties can be exploited to design non-blocking protocols that are more efficient in practice than those allowed by theoretical models. These new protocols rely on the operating system to take action when a thread of control is delayed during its non-blocking update. We illustrate the effectiveness of this approach by presenting two protocols that address factors hindering the performance of Herlihy's standard non-blocking protocol [Herlihy 90, Herlihy 91a]. These factors are: resources wasted by attempted non-blocking operations that fail, and the cost of data copying. We demonstrate the importance of these factors experimentally, and show how they can be reduced using protocols that rely on operating system support. To reduce the overhead of failing non-blocking operations, our first protocol maintains information about the utilization of the shared object; experiments show that this protocol performs better than the known alternatives. To reduce the cost of data copying, we introduce a second, optimistic protocol that avoids copying, except in the case when a thread of control is delayed during its attempted update.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM Symposium on Principles of Distributed Computing
PublisherPubl by ACM
Pages125-134
Number of pages10
ISBN (Print)0897914953, 9780897914956
DOIs
StatePublished - 1992
Externally publishedYes
EventProceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing - Vancouver, BC, Can
Duration: Aug 10 1992Aug 12 1992

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

OtherProceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing
CityVancouver, BC, Can
Period8/10/928/12/92

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Performance issues in non-blocking synchronization on shared-memory multiprocessors'. Together they form a unique fingerprint.

Cite this