Kill-safe synchronization abstractions

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.
• 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. E. Fiuczynski , D. Becker , C. Chambers , S. Eggers, Extensibility safety and performance in the SPIN operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.267-283, December 03-06, 1995, Copper Mountain, Colorado, United States
• 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: Matthew Flatt , Robert Bruce Findler , Shriram Krishnamurthi , Matthias Felleisen, Programming languages as operating systems (or revenge of the son of the lisp machine), Proceedings of the fourth ACM SIGPLAN international conference on Functional programming, p.138-147, September 27-29, 1999, Paris, France
• 7: Paul T. Graunke , Shriram Krishnamurthi , Steve Van Der Hoeven , Matthias Felleisen, Programming the Web with High-Level Programming Languages, Proceedings of the 10th European Symposium on Programming Languages and Systems, p.122-136, April 02-06, 2001
• 8: Samuel P. Harbison, Modula-3, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 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.
• 10: Chris Hawblitzel , Thorsten von Eicken, Luna: a flexible Java protection system, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060325]
• 11: C. A. R. Hoare, Communicating sequential processes, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 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.
• 13: Barbara Liskov , Robert Scheifler, Guardians and Actions: Linguistic Support for Robust, Distributed Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.381-404, July 1983 [doi>10.1145/2166.357215]
• 14: Simon Marlow , Simon Peyton Jones , Andrew Moran , John Reppy, Asynchronous exceptions in Haskell, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.274-285, June 2001, Snowbird, Utah, United States
• 15: R. Milner, Communication and concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 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: David D. Redell , Yogen K. Dalal , Thomas R. Horsley , Hugh C. Lauer , William C. Lynch , Paul R. McJones , Hal G. Murray , Stephen C. Purcell, Pilot: an operating system for a personal computer, Communications of the ACM, v.23 n.2, p.81-92, Feb. 1980 [doi>10.1145/358818.358822]
• 19: J. H. Reppy, Synchronous operations as first-class values, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.250-259, June 20-24, 1988, Atlanta, Georgia, United States
• 20: John Hamilton Reppy, Higher-order concurrency, Cornell University, Ithaca, NY, 1992
• 21: John H. Reppy, Concurrent programming in ML, Cambridge University Press, New York, NY, 1999
• 22: Algis Rudys , Dan S. Wallach, Termination in language-based systems, ACM Transactions on Information and System Security (TISSEC), v.5 n.2, p.138-168, May 2002 [doi>10.1145/505586.505589]
• 23: Algis Rudys , Dan S. Wallach, Transactional Rollback for Language-Based Systems, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.439-448, June 23-26, 2002
• 24: Soper, P., specification lead. JSR 121: Application isolation API specification, 2003. http://www.jcp.org/.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

General Terms:
Design, Languages