Process coordination with fetch-and-increment

Eric Freudenthal, Allan Gottlieb

Research output: Contribution to conferencePaper

Abstract

The fetch-and-add (F&A) operation has been used effectively in a number of process coordination algorithms. In this paper we assess the power of fetch-and-increment (F&I) and fetch-and-decrement (F&D), which we view as restricted forms of F&A in which the only addends permitted are ±1. F&A-based algorithms that use only unit addends are thus trivially expressed with just F&I and F&D. Our primary contributions are new F&I/F&D algorithms for readers/writers coordination and barrier synchronization for dynamically-sized groups. We also restructure an existing F&A-based algorithm for queues-with-multiplicity to obtain an algorithm using just F&I and F&D. When executed on certain hardware architectures, most of these algorithms are free of serial bottlenecks. We also discuss a general technique for implementing F&A using F&I/F&D at a cost logarithmic in the number of processors.

Original languageEnglish (US)
Pages260-268
Number of pages9
DOIs
StatePublished - 1991
Event4th International Conference on Architectural Support for Programming Languages and Operating Systems - Santa Clara, CA, USA
Duration: Apr 8 1991Apr 11 1991

Other

Other4th International Conference on Architectural Support for Programming Languages and Operating Systems
CitySanta Clara, CA, USA
Period4/8/914/11/91

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Process coordination with fetch-and-increment'. Together they form a unique fingerprint.

  • Cite this

    Freudenthal, E., & Gottlieb, A. (1991). Process coordination with fetch-and-increment. 260-268. Paper presented at 4th International Conference on Architectural Support for Programming Languages and Operating Systems, Santa Clara, CA, USA, . https://doi.org/10.1145/106973.106998