More Web Proxy on the site http://driver.im/

article

Free access

Synchronization with eventcounts and sequencers

Authors:

Rajendra K. KanodiaAuthors Info & Claims

Communications of the ACM, Volume 22, Issue 2

Pages 115 - 123

https://doi.org/10.1145/359060.359076

Published: 01 February 1979 Publication History

Abstract

Synchronization of concurrent processes requires controlling the relative ordering of events in the processes. A new synchronization mechanism is proposed, using abstract objects called eventcounts and sequencers, that allows processes to control the ordering of events directly, rather than using mutual exclusion to protect manipulations of shared variables that control ordering of events. Direct control of ordering seems to simplify correctness arguments and also simplifies implementation in distributed systems. The mechanism is defined formally, and then several examples of its use are given. The relationship of the mechanism to protection mechanisms in the system is explained; in particular, eventcounts are shown to be applicable to situations where confinement of information matters. An implementation of eventcounts and sequencers in a system with shared memory is described.

References

[1]

Bell, D.E., and LaPadula, L.J. Secure computer systems: A mathematical model. Air Force Electr. Systs. Div. Rcp. ESD-TR-73- 278, Vol. II, Nov. 1973.

[2]

Brinch-Hansen, P. Concurrent programming concepts. Computing Surveys .5, 4 (Dec. 1973), 223-245.

Digital Library

[3]

Courtois, P. J., Heymans, F., and Parnas, D. L. Concurrent control with "readers" and "writers." Comm. A CM 14, 5 (Oct. 1971), 667-668.

Digital Library

[4]

Denning, D. A lattice model of secure information flow. Comm. ACM 19, 5 (May 1976), 236-243.

Digital Library

[5]

Dijkstra, E. W. Cooperating sequential processes. In Programming Languages, F. Genuys, Ed., Academic Press, New York, 1968.

[6]

Dijkstra, E. W. Hierarchical ordering of sequential processes. Acta Informatica 1 (1970, 115-138.

Digital Library

[7]

Easton, W. B. Process synchronization without long-term interlock. Proc. Third ACM Symp. Operating Syst. Principles, Operating Syst. Rev. (ACM) 6, I and 2 (June 1972), pp. 50-95.

Digital Library

[8]

Greff, I. Semantics of communicating parallel processes. M.I.T. Proj. MAC TR-154, Sept. 1975.

[9]

Habcrmarm, A. N. Synchronization of communicating processes. Comm. ACM 15, 3 (March 1972), 171-176.

Digital Library

[10]

Hoare, C. A. R. Monitors: An operating system structuring concept. Comm. ACM 17, 10 (Oct. 1974), 549-557.

Digital Library

[11]

Howard, J. H. Proving monitors. Comm. ACM I9, 5 (May 1976), 273-279.

Digital Library

[12]

Kanodia, R. K., and Reed, D. P. Synchronization in distributed systems. In Preparation.

[13]

Kohavi, Z. Switching and Finite Automata Theory. McGraw-Hill, New York, 1970, pp. 12-14.

Digital Library

[14]

Lamport, L. Time, clocks, and the ordering of events in a distributed system. Comm. A CM 21, 7 (July 1978), 558-565.

Digital Library

[15]

Lamport, L. Synchronization of independent processes. Acta Informatica 7, 1 (1976), 15-34.

Digital Library

[16]

Lamport, L. Concurrent reading and writing. Comm. A CM 20, 11 (Nov. 1977), 806-811.

Digital Library

[17]

Lampson, B. W. A note on the confinement problem. Comm. ACM 16, 5 (Oct. 1973), 613-615.

Digital Library

[18]

Owicki, S., and Giles, D. Verifying properties of parallel programs: An axiomatic approach. Comm. ACM 19, 5 (May 1976), 279-285.

Digital Library

[19]

Patti, S. S. Limitations and capabilities of Dijkstra's semaphore primitives for coordination among processes. M.I.T. Proj. MAC Computational Structures Group Memo 57, Feb. 1971.

[20]

Reed, D. P. Processor multiplexing in a layered operating system. S.M. and E.E. Th., M.I.T., Dept. of Electr. Eng. and Comptr. Sci., June 1976; Tech. Rep. TR-164, M.I.T., Lab. Comptr. Sci,

Digital Library

[21]

Schaefer, M. Quasi-synchronization of readers and writers in a secure multi-level environment. Syst. Develop. Corp. TM-5407/003, Sept. 1974.

Cited By

Nie SLiu YNiu JWu W(2024)CAL: Core-Aware Lock for the big.LITTLE Multicore ArchitectureApplied Sciences10.3390/app1415644914:15(6449)Online publication date: 24-Jul-2024
https://doi.org/10.3390/app14156449
Nagarajan DScheipel TBaunach MHong JPark J(2024)Fair and Starvation-Free Spinlock for Real-Time AUTOSAR systemsProceedings of the 39th ACM/SIGAPP Symposium on Applied Computing10.1145/3605098.3635922(436-445)Online publication date: 8-Apr-2024
https://dl.acm.org/doi/10.1145/3605098.3635922
Shahare VChabbi MHegde NAgrawal KShun J(2023)Protecting Locks Against Unbalanced Unlock()Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591091(199-211)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591091
Show More Cited By

Recommendations

Synchronization with eventcounts and sequencers (Extended Abstract)
SOSP '77: Proceedings of the sixth ACM symposium on Operating systems principles

The design of computer systems to be concurrently used by multiple, independent users requires a mechanism that allows programs to synchronize their use of shared resources. Many such mechanisms have been developed and used in practical applications. ...
Synchronization with eventcounts and sequencers (Extended Abstract)

The design of computer systems to be concurrently used by multiple, independent users requires a mechanism that allows programs to synchronize their use of shared resources. Many such mechanisms have been developed and used in practical applications. ...
A generic distributed monitor construct for programming process synchronization in distributed systems
ISPA'07: Proceedings of the 5th international conference on Parallel and Distributed Processing and Applications

The monitor construct has been implemented in several concurrent and/or parallel programming languages for shared-memory system environments, Extensions of the monitor to support process synchronization in distributed systems have also been proposed. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 22, Issue 2

Feb. 1979

61 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359060

Editor:
Robert L. Ashenhurst
The Univ. of Chicago, IL

Issue’s Table of Contents

Copyright © 1979 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1979

Published in CACM Volume 22, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

154
Total Citations
View Citations
2,216
Total Downloads

Downloads (Last 12 months)504
Downloads (Last 6 weeks)77

Reflects downloads up to 26 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nie SLiu YNiu JWu W(2024)CAL: Core-Aware Lock for the big.LITTLE Multicore ArchitectureApplied Sciences10.3390/app1415644914:15(6449)Online publication date: 24-Jul-2024
https://doi.org/10.3390/app14156449
Nagarajan DScheipel TBaunach MHong JPark J(2024)Fair and Starvation-Free Spinlock for Real-Time AUTOSAR systemsProceedings of the 39th ACM/SIGAPP Symposium on Applied Computing10.1145/3605098.3635922(436-445)Online publication date: 8-Apr-2024
https://dl.acm.org/doi/10.1145/3605098.3635922
Shahare VChabbi MHegde NAgrawal KShun J(2023)Protecting Locks Against Unbalanced Unlock()Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591091(199-211)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591091
Lu Z(2023)PiN: Processing in Network-on-ChipIEEE Design & Test10.1109/MDAT.2023.330794340:6(30-38)Online publication date: Dec-2023
https://doi.org/10.1109/MDAT.2023.3307943
Xing TZhou CShen XWu DLi QLiu Y(2022)A Web-Based Collaborative Method for SysML ModelingJournal of Computing and Information Science in Engineering10.1115/1.405524022:6Online publication date: 19-Sep-2022
https://doi.org/10.1115/1.4055240
Chi HFu CZeng QDu X(2022)Delay Wreaks Havoc on Your Smart Home: Delay-based Automation Interference Attacks2022 IEEE Symposium on Security and Privacy (SP)10.1109/SP46214.2022.9833620(285-302)Online publication date: May-2022
https://doi.org/10.1109/SP46214.2022.9833620
Álvarez DSala KMaroñas MRoca ABeltran VLee JPetrank E(2021)Advanced synchronization techniques for task-based runtime systemsProceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3437801.3441601(334-347)Online publication date: 17-Feb-2021
https://dl.acm.org/doi/10.1145/3437801.3441601
Giles CPeterson CHeinrich M(2020)KnightSim: A Fast Discrete Event-Driven Simulation Methodology for Computer Architectural SimulationIEEE Transactions on Computers10.1109/TC.2019.293850769:1(65-71)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1109/TC.2019.2938507
Guerraoui RGuiroux HLachaize RQuéma VTrigonakis V(2019)Lock–UnlockACM Transactions on Computer Systems10.1145/330150136:1(1-149)Online publication date: 14-Mar-2019
https://dl.acm.org/doi/10.1145/3301501
Dice DKogan A(2019)TWA – Ticket Locks Augmented with a Waiting ArrayEuro-Par 2019: Parallel Processing10.1007/978-3-030-29400-7_24(334-345)Online publication date: 26-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-29400-7_24
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents