article

Kill-safe synchronization abstractions

Authors:

Robert Bruce FindlerAuthors Info & Claims

ACM SIGPLAN Notices, Volume 39, Issue 6

Pages 47 - 58

https://doi.org/10.1145/996893.996849

Published: 09 June 2004 Publication History

Abstract

When an individual task can be forcefully terminated at any time, cooperating tasks must communicate carefully. For example, if two tasks share an object, and if one task is terminated while it manipulates the object, the object may remain in an inconsistent or frozen state that incapacitates the other task. To support communication among terminable tasks, language run-time systems (and operating systems) provide kill-safe abstractions for inter-task communication. No kill-safe guarantee is available, however, for abstractions that are implemented outside the run-time system.In this paper, we show how a run-time system can support new kill-safe abstractions without requiring modification to the run-time system, and without requiring the run-time system to trust any new code. Our design frees the run-time implementor to provide only a modest set of synchronization primitives in the trusted computing base, while still allowing tasks to communicate using sophisticated abstractions.

References

[1]

G. Back, W. Hsieh, and J. Lepreau. Processes in KaffeOS: Isolation, resource management, and sharing in Java. In Proc. USENIX Conference on Operating Systems Design and Im-plementation, pages 333--346, Oct. 2000.]]

Digital Library

[2]

G. Back, P. Tullmann, L. Stoller, W. C. Hsieh, and J. Lepreau. Java operating systems: Design and implementation. In Proceedings of the USENIX 2000 Technical Conference, pages 197--210, San Diego, CA, June 2000.]]

[3]

B. N. Bershad, S. Savage, P. Pardyak, E. G. Sirer, M. Fiuczynski, D. Becker, S. Eggers, and C. Chambers. Extensibility, safety and performance in the SPIN operating system. In Proc. ACM Symposium on Operating Systems Principles, pages 267--284, Dec. 1995.]]

Digital Library

[4]

D. L. Black, D. B. Golub, D. P. Julin, R. F. Rashid, R. P. Draves, R. W. Dean, A. Forin, J. Barrera, H. Tokuda, G.-R. Malan, and D. Bohman. Microkernel operating system architecture and Mach. Journal of Information Processing, 14(4):442--453, 1991.]]

[5]

M. Flatt. PLT MzScheme: Language Manual, 2004. www.mzscheme.org.]]

[6]

M. Flatt, R. B. Findler, S. Krishnamurthi, and M. Felleisen. Programming languages as operating systems (or revenge of the son of the Lisp machine). In Proc. ACM International Conference on Functional Programming, pages 138--147, Sept. 1999.]]

Digital Library

[7]

P. Graunke, S. Krishnamurthi, S. V. D. Hoeven, and M. Felleisen. Programming the Web with high-level programming languages. In Proc. European Symposium on Programming, volume 2028 of Lecture Notes in Computer Science. Springer-Verlag, 2001.]]

Digital Library

[8]

S. P. Harbison. Modula-3. Prentice Hall, 1991.]]

Digital Library

[9]

C. Hawblitzel, C.-C. Chang, G. Czajkowski, D. Hu, and T. von Eicken. Implementing multiple protection domains in Java. In Proc. of USENIX Annual Technical Conference, pages 259--270, June 1998.]]

Digital Library

[10]

C. Hawblitzel and T. von Eicken. Luna: a flexible Java protection system. In Proc. USENIX Conference on Operating Systems Design and Implementation, Oct. 2002.]]

Digital Library

[11]

C. A. R. Hoare. Communicating Sequential Processes. Prentice-Hall, Englewood Cliffs, NJ, 1985.]]

Digital Library

[12]

I. M. Leslie, D. McAuley, R. J. Black, T. Roscoe, P. R. Barham, D. M. Evers, R. Fairburns, and E. A. Hyden. The design and implementation of an operating system to support distributed multimedia applications. IEEE Journal on Selected Areas in Communications, 14(7):1280--1297, Sept. 1996.]]

Digital Library

[13]

B. Liskov and R. Scheifler. Guardians and actions: Linguistics support for robust, distributed systems. ACM Transactions on Computing Systems, 5(3):381--404, 1983.]]

Digital Library

[14]

S. Marlow, S. L. Peyton Jones, A. Moran, and J. H. Reppy. Asynchronous exceptions in Haskell. In Proc. ACM Conference on Programming Language Design and Implementation, pages 274--285, 2001.]]

Digital Library

[15]

R. Milner. Communication and Concurrency. International Series in Computer Science. Prentice Hall, 1989.]]

Digital Library

[16]

National Institute of Standards and Technology (U.S.). POSIX: portable operating system interface for computer environments, Sept. 1988.]]

[17]

P. Panangaden and J. H. Reppy. The essence of Concurrent ML. In F. Nielson, editor, ML with Concurrency: Design, Analysis, Implementation and Application, Monographs in Computer Science, pages 5--29. Springer-Verlag, 1997.]]

[18]

D. Redell, Y. Dalal, T. Horsley, H. Lauer, W. Lynch, P. McJones, H. Murray, and S. Purcell. Pilot: An operating system for a personal computer. Communications of the ACM, 23(2):81--92, Feb. 1980.]]

Digital Library

[19]

J. H. Reppy. Synchronous operations as first-class values. In Proc. ACM Conference on Programming Language Design and Implementation, pages 250--259, 1988.]]

Digital Library

[20]

J. H. Reppy. Higher-Order Concurrency. PhD thesis, Cornell University, 1992.]]

Digital Library

[21]

J. H. Reppy. Concurrent Programming in ML. Cambridge University Press, 1999.]]

Digital Library

[22]

A. Rudys, J. Clements, and D. S. Wallach. Termination in language-based systems. ACM Transactions on Information and System Security, 5(3):138--168, 2002.]]

Digital Library

[23]

A. Rudys and D. S. Wallach. Transactional rollback for language-based systems. In Proc. International Conference on Dependable Systems and Networks, June 2002.]]

Digital Library

[24]

Soper, P., specification lead. JSR 121: Application isolation API specification, 2003. http://www.jcp.org/.]]

Cited By

Chuang CIraci GZiarek L(2021)Synchronous Message-Passing with PriorityPractical Aspects of Declarative Languages10.1007/978-3-030-67438-0_3(37-53)Online publication date: 18-Jan-2021
https://dl.acm.org/doi/10.1007/978-3-030-67438-0_3
Cortinas CVassena MRusso A(2020)Securing Asynchronous Exceptions2020 IEEE 33rd Computer Security Foundations Symposium (CSF)10.1109/CSF49147.2020.00023(214-229)Online publication date: Jul-2020
https://doi.org/10.1109/CSF49147.2020.00023
CHUANG CIRACI GZIAREK L(2022)Send to me first: Priority in synchronous message-passingJournal of Functional Programming10.1017/S095679682200011932Online publication date: 22-Dec-2022
https://doi.org/10.1017/S0956796822000119
Show More Cited By

Index Terms

Kill-safe synchronization abstractions
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Concurrent programming structures
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management
        Process synchronization

Recommendations

Kill-safe synchronization abstractions
PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation

When an individual task can be forcefully terminated at any time, cooperating tasks must communicate carefully. For example, if two tasks share an object, and if one task is terminated while it manipulates the object, the object may remain in an ...
Accepting blame for safe tunneled exceptions
PLDI '16

Unhandled exceptions crash programs, so a compile-time check that exceptions are handled should in principle make software more reliable. But designers of some recent languages have argued that the benefits of statically checked exceptions are not ...
Accepting blame for safe tunneled exceptions
PLDI '16: Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation

Unhandled exceptions crash programs, so a compile-time check that exceptions are handled should in principle make software more reliable. But designers of some recent languages have argued that the benefits of statically checked exceptions are not ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 39, Issue 6

PLDI '04

May 2004

299 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/996893

Issue’s Table of Contents

PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation
June 2004
310 pages
ISBN:1581138075
DOI:10.1145/996841
General Chair:
William Pugh
University of Maryland, College Park
,
Program Chair:
Craig Chambers
University of Washington

Copyright © 2004 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: 09 June 2004

Published in SIGPLAN Volume 39, Issue 6

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
566
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chuang CIraci GZiarek L(2021)Synchronous Message-Passing with PriorityPractical Aspects of Declarative Languages10.1007/978-3-030-67438-0_3(37-53)Online publication date: 18-Jan-2021
https://dl.acm.org/doi/10.1007/978-3-030-67438-0_3
Cortinas CVassena MRusso A(2020)Securing Asynchronous Exceptions2020 IEEE 33rd Computer Security Foundations Symposium (CSF)10.1109/CSF49147.2020.00023(214-229)Online publication date: Jul-2020
https://doi.org/10.1109/CSF49147.2020.00023
CHUANG CIRACI GZIAREK L(2022)Send to me first: Priority in synchronous message-passingJournal of Functional Programming10.1017/S095679682200011932Online publication date: 22-Dec-2022
https://doi.org/10.1017/S0956796822000119
Tew KSwaine JFlatt MFindler R[email protected] P(2011)PlacesACM SIGPLAN Notices10.1145/2168696.204786047:2(85-96)Online publication date: 24-Oct-2011
https://dl.acm.org/doi/10.1145/2168696.2047860
Hoffman KMetzger HEugster P(2011)RibbonsACM SIGPLAN Notices10.1145/2076021.204809146:10(289-306)Online publication date: 22-Oct-2011
https://dl.acm.org/doi/10.1145/2076021.2048091
Hoffman KMetzger HEugster PLopes CFisher K(2011)RibbonsProceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications10.1145/2048066.2048091(289-306)Online publication date: 22-Oct-2011
https://dl.acm.org/doi/10.1145/2048066.2048091
Tew KSwaine JFlatt MFindler R[email protected] PD'Hondt T(2011)PlacesProceedings of the 7th symposium on Dynamic languages10.1145/2047849.2047860(85-96)Online publication date: 24-Oct-2011
https://dl.acm.org/doi/10.1145/2047849.2047860
Disney TFlanagan CMcCarthy JChakravarty MHu ZDanvy O(2011)Temporal higher-order contractsProceedings of the 16th ACM SIGPLAN international conference on Functional programming10.1145/2034773.2034800(176-188)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.1145/2034773.2034800
Disney TFlanagan CMcCarthy J(2011)Temporal higher-order contractsACM SIGPLAN Notices10.1145/2034574.203480046:9(176-188)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.1145/2034574.2034800
Ziarek LSivaramakrishnan KJagannathan SHall MPadua D(2011)Composable asynchronous eventsProceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/1993498.1993572(628-639)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/1993498.1993572
Show More Cited By

View Options

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents