Article

Free access

Using continuations to implement thread management and communication in operating systems

Authors:

Richard P. Draves,

Brian N. Bershad,

Richard F. Rashid,

Randall W. DeanAuthors Info & Claims

SOSP '91: Proceedings of the thirteenth ACM symposium on Operating systems principles

Pages 122 - 136

https://doi.org/10.1145/121132.121155

Published: 01 September 1991 Publication History

Abstract

We have improved the performance of the Mach 3.0 operating system by redesigning its internal thread and interprocess communication facilities to use continuations as the basis for control transfer. Compared to previous versions of Mach 3.0, our new system consumes 85% less space per thread. Cross-address space remote procedure calls execute 14% faster. Exception handling runs over 60% faster.In addition to improving system performance, we have used continuations to generalize many control transfer optimizations that are common to operating systems, and have recast those optimizations in terms of a single implementation methodology. This paper describes our experiences with using continuations in the Mach operating system.

References

[1]

Accetta, M. J., Baron, R. V., Bolosky, W., Golub, D. B., Rashid, R. F., Tevanian, Jr., A., and Young, M. W. Mach: A New Kernel Foundation for UNIX Development. In Proceedings of the Summer 1986 USENIX Conference, pages 93-113, July 1986.]]

[2]

Anderson, T. E., Lazowska, E. D., and Levy, H. M. The Performance Implications of Thread Management Alternatives for Shared Memory Multiprocessors. IEEE Transactions on Computers, 38(12):1631-1644, December 1989.]]

Digital Library

[3]

Anderson, T. E., Bershad, B. N., Lazowska, E. D., and Levy., H. M. Scheduler Activations: Effective Kernel Support for the Uaer-Level Management of Parallelism. In Proceedings of the 13th A CM Symposium on Operating Systems Principles, October 1991. This issue.]]

Digital Library

[4]

Appel, W. and Li, K. Virtual Memory Primitives for User Programs. In Proceedings of the Fourth Symposium on Architectural Support for Programming Languages and Operating Systems, pages 96-107, April 1991.]]

Digital Library

[5]

Ball, J. E., Feldman, J. A., Low, J. R., Rashid, R. F., and Rovner, P. D. RiG, Rochester's Intelligent Gateway: System Overview. IEEE Transaction on Software Engineering, 2(4):321-328, December 1976.]]

Digital Library

[6]

Bershad, B. N. High Performance Cross- Address Space Communication. PhD dissertation, University of Washington, Department of Computer Science and Engineering, Seattle, WA 98195, June 1990.]]

Digital Library

[7]

Bershad, B. N., Anderson, T. E., Lazowska, E. D., and Levy, H. M. Lightweight Remote Procedure Call. A CM Transactions on Computer Systems, 8(1):37-55, February 1990. Also appeared in Proceedings of the i~th A CM Symposium on Operating Systems Principles, December 1989.]]

Digital Library

[8]

Black, D. L. Scheduling and Resource Management Techniques .for Multiprocessors. PhD dissertation, School of Computer Science, Carnegie Mellon University, July 1990.]]

Digital Library

[9]

Black, D. L. Scheduling Support for Concurrency and Parallelism in the Mach Operating System. IEEE Computer Magazine, 23(5):35-43, May 1990.]]

Digital Library

[10]

Black, D., Golub, D., Hauth, K., Tevanian, Jr., A., and Sanzi, R. The Mach Exception Handling Facility. In Proceedings of the A CM SIGPLAN/SIGOPS Workshop on Parallel and Distributed Debugging, pages 45-56, May 1988.]]

Digital Library

[11]

Black, D. L., Golub, D. B., Julin, D. P., Rashid, R. F., Draves, R. P., Dean, R. W., Forin, A., Barrera, J., Tokuda, H., MMan, G., and Bohman, D. Microkernel Operating System Architectures and Mach. Journal of Information Processing, December 1991. To appear.]]

[12]

Cheriton, D. R. The V Distributed System. Communications of the ACM, 31(3):314-333, March 1988.]]

Digital Library

[13]

Cheriton, D. R. PersonM Communication, May 1991.]]

[14]

Cooper, E. C. and Draves, R. P. C- Threads. Technical Report CMU-CS-88-154, School of Computer Science, Carnegie Mellon University, February 1988.]]

[15]

Cooper, E. C. and Morrisett, J.G. Adding Threads to Standard ML. Technical Report 186, School of Computer Science, Carnegie Mellon University, December 1990.]]

[16]

Draves, R. P. A Revised IPC Interface. In Proceedings of the First Mach USENIX Workshop, pages 101-121, October 1990.]]

[17]

Duncan, R. Advanced MS-DOS: the Microsoft guide for assembly language and C programmers. Redmond, Washington, 1986.]]

Digital Library

[18]

Geschke, C., Morris, J., and Satterthwaite, E. Early Experiences with Mesa. Communications of the ACM, 20(8):540-553, August 1977.]]

Digital Library

[19]

Golub, D., Dean, R., Forin, A., and Rashid, R. Unix as an Application Program. In Proceedings of the Summer 1990 USENIX Conference, pages 87-95, June 1990.]]

[20]

Haskin, R., Malachi, Y., Sawdon, W., and Chan, G. Recovery Management in QuickSilver. ACM Transactions on Computer Systems, 6(1):82- 108, February 1988.]]

Digital Library

[21]

Haynes, C. T. and Friedman, D. P. Engines Build Process Abstractions. In Conference Record of the 198~1 A CM Symposium on LISP and Functional Programming, pages 18-23, August 1984.]]

Digital Library

[22]

Hutchinson, N. C., Peterson, L. L., Abbott, M. B., and O'Malley, S. RPC in the x-Kernel: Evaluating New Design Techniques. In Proceedings of the 12th ACM Symposium on Operating Systems Principles, pages 91-101, December 1989.]]

Digital Library

[23]

Lampson, B. W., Mitchell, J. G., and Satterthwaite, E. H. On the Transfer of Control Between Contexts. In Lecture Notes On Computer Science: Proceedings of the Programming Symposium, pages 181-203. Springer-Verlag, 1974.]]

Digital Library

[24]

Leffier, S., McKusick, M., Karels, M., and Quarterman, J. The Design and Implementation of the ~4.3BSD UNIX Operating System. Addison- Wesley, Reading, MA, 1989.]]

Digital Library

[25]

Levy, H. M. and Eckhouse, R. H. Computer Programming and Architecture: The VAX- 11 (2nd Edition). Digital Press, Bedford, MA, 1989.]]

Digital Library

[26]

Marsh, B., Scott, M., LeBlanc, T., and Markatos, E. First-Class User-Level Threads. In Proceed,ngs of the 13th ACM Symposium on Operating Systems Principles, October 1991. This issue.]]

Digital Library

[27]

Milne, R. and Strachey, C. A Theory of Programming Language Semantics. H alsted Press, New York, 1976.]]

Digital Library

[28]

Mullender, S. j., van Rossum, G., Tanenbaum, A. S., van Renesse, R., and van Staveren, H. Amoeba: A Distributed Operating System for the 1990s. IEEE Computer Magazine, 23(5):44-54, May 1990.]]

Digital Library

[29]

Rashid, R. F. and Robertson, G. G. Accent: A Communication Oriented Network Operating System Kernel. In Proceedings of the 8th A CM Symposium on Operating Systems Principles, pages 64-75, December 1981.]]

Digital Library

[30]

Rashid, R. From RIG to Accent to Mach: The Evolution of a Network Operating System. In Proceedings of the ACM/IEEE Computer Society 1986 Fall Joint Computer Conference. ACM, November 1986.]]

Digital Library

[31]

Rashid, R., Tevanian, Jr., A., Young, M., Golub, D., Baron, R., Black, D., Bolosky, W., and Chew, J. Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures. In Proceedings of the ~nd Symposium on Architectural Support for Programming Languages and Operating Systems, April 1987.]]

[32]

Ritchie, D. and Thompson, K. The UNIX Time-Sharing System. Bell System Technical Journal, July 1978.]]

[33]

Rose, K. and Hacker, B. Inside Macintosh. Addison-Wesley, Reading, MA, 1985.]]

Digital Library

[34]

Rozier, M., Abrossimov, V., Armand, F., Boule, I., Giend, M., Guillemont, M., Herrmann, F., Leonard, P., Langlois, S., and Neuhauser, W. The Chorus Distributed Operating System. Computing Systems, 1(4), 1988.]]

[35]

Satyanarayanan, M., Howard, J., Nichols, D., Sidebotham, R., and Spector, A. The ITC Distributed File System: Principles and Design. In Proceedings o} the l Oth A CM Symposium on Operating Systems Principles, pages 35-50, December 1985.]]

Digital Library

[36]

Schroeder, M. D. and Burrows, M. Performance of Firefly RPC. ACM Transactions on Computer Systems, 8(1):1-17, February 1990.]]

Digital Library

[37]

Scott, M. L., LeBlanc, T. J., and Marsh, B. D. Evolution of an Operating System for Large- Scale Shared Memory Multiprocessors. Technical Report 309, University of Rochester, School of Computer Science, March 1989.]]

Digital Library

[38]

Thacker, C. P., Stewart, L. C., and Satterthwaite, Jr., E. H. Firefly: A Multiprocessor Workstation. IEEE Transactions on Computers, 37(8):909-920, August 1988.]]

Digital Library

[39]

Wand, M. Continuation-Based Multiprocessing. In Conference Record of the 1980 LISP Conference, pages 19-28, August 1980.]]

Digital Library

[40]

Ward, S. A. and Halstead, Jr., R. H. A Syntactic Theory of Message Passing. Journal of the A CM, 27(2):a65-asa, April 1980.]]

Digital Library

[41]

Young, M., Tevanian, Jr., A., Rashid, R., Golub, D., Eppinger, J., Chew, J., Bolosky, W., Black, D., and Baron, R. The Duality of Memory and Communication in the implementation of a Multiprocessor Operating System. In Proceedings of the 11th A CM Symposium on Operating Systems Principles, pages 63-76, November 1987.]]

Digital Library

Cited By

Zhang WFang VPanda AShenker SFonseca RDelimitrou COoi B(2020)KappaProceedings of the 11th ACM Symposium on Cloud Computing10.1145/3419111.3421277(328-343)Online publication date: 12-Oct-2020
https://dl.acm.org/doi/10.1145/3419111.3421277
Marty Mde Kruijf MAdriaens JAlfeld CBauer SContavalli CDalton MDukkipati NEvans WGribble SKidd NKononov RKumar GMauer CMusick EOlson LRubow ERyan MSpringborn KTurner PValancius VWang XVahdat ABrecht TWilliamson C(2019)SnapProceedings of the 27th ACM Symposium on Operating Systems Principles10.1145/3341301.3359657(399-413)Online publication date: 27-Oct-2019
https://dl.acm.org/doi/10.1145/3341301.3359657
Dietrich CLohmann D(2018)Semi-Extended Tasks: Efficient Stack Sharing Among Blocking Threads2018 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS.2018.00049(338-349)Online publication date: Dec-2018
https://doi.org/10.1109/RTSS.2018.00049
Show More Cited By

Index Terms

Using continuations to implement thread management and communication in operating systems
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Process management

Recommendations

Using continuations to implement thread management and communication in operating systems

We have improved the performance of the Mach 3.0 operating system by redesigning its internal thread and interprocess communication facilities to use continuations as the basis for control transfer. Compared to previous versions of Mach 3.0, our new ...
Traveling forward in time to newer operating systems using ShadowReboot
VEE '13: Proceedings of the 9th ACM SIGPLAN/SIGOPS international conference on Virtual execution environments

Operating system (OS) reboots are an essential part of updating kernels and applications on laptops and desktop PCs. Long downtime during OS reboots severely disrupts users' computational activities. This long disruption discourages the users from ...
Traveling forward in time to newer operating systems using ShadowReboot
VEE '13

Operating system (OS) reboots are an essential part of updating kernels and applications on laptops and desktop PCs. Long downtime during OS reboots severely disrupts users' computational activities. This long disruption discourages the users from ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SOSP '91: Proceedings of the thirteenth ACM symposium on Operating systems principles

September 1991

253 pages

ISBN:0897914473

DOI:10.1145/121132

Chairman:
Henry M. Levy
Univ. of Washington, Seattle

ACM SIGOPS Operating Systems Review Volume 25, Issue 5
Oct. 1991
253 pages
ISSN:0163-5980
DOI:10.1145/121133
Editor:
Henry M. Levy
Univ. of Washington, Seattle
Issue’s Table of Contents

Copyright © 1991 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]

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1991

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SOSP91

Sponsor:

SIGOPS

SOSP91: 13th ACM Symposium on Operating Systems Principles

October 13 - 16, 1991

California, Pacific Grove, USA

Acceptance Rates

Overall Acceptance Rate 131 of 716 submissions, 18%

Upcoming Conference

SOSP '24

Sponsor:
sigops

ACM SIGOPS 30th Symposium on Operating Systems Principles

November 4 - 6, 2024

Austin , TX , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

104
Total Citations
View Citations
2,316
Total Downloads

Downloads (Last 12 months)217
Downloads (Last 6 weeks)28

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang WFang VPanda AShenker SFonseca RDelimitrou COoi B(2020)KappaProceedings of the 11th ACM Symposium on Cloud Computing10.1145/3419111.3421277(328-343)Online publication date: 12-Oct-2020
https://dl.acm.org/doi/10.1145/3419111.3421277
Marty Mde Kruijf MAdriaens JAlfeld CBauer SContavalli CDalton MDukkipati NEvans WGribble SKidd NKononov RKumar GMauer CMusick EOlson LRubow ERyan MSpringborn KTurner PValancius VWang XVahdat ABrecht TWilliamson C(2019)SnapProceedings of the 27th ACM Symposium on Operating Systems Principles10.1145/3341301.3359657(399-413)Online publication date: 27-Oct-2019
https://dl.acm.org/doi/10.1145/3341301.3359657
Dietrich CLohmann D(2018)Semi-Extended Tasks: Efficient Stack Sharing Among Blocking Threads2018 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS.2018.00049(338-349)Online publication date: Dec-2018
https://doi.org/10.1109/RTSS.2018.00049
Veselý JBasu ABhattacharjee ALoh GOskin MReinhardt S(2018)Generic system calls for GPUsProceedings of the 45th Annual International Symposium on Computer Architecture10.1109/ISCA.2018.00075(843-856)Online publication date: 2-Jun-2018
https://dl.acm.org/doi/10.1109/ISCA.2018.00075
Nuratch S(2016)Firmware design and development of MCU and Matlab-Simulink interfacing for real-time measurement, analysis and control applications2016 13th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON)10.1109/ECTICon.2016.7561476(1-6)Online publication date: Jun-2016
https://doi.org/10.1109/ECTICon.2016.7561476
Katz DBarbalace AAnsary SRavichandran ARavindran B(2015)Thread Migration in a Replicated-Kernel OS2015 IEEE 35th International Conference on Distributed Computing Systems10.1109/ICDCS.2015.36(278-287)Online publication date: Jun-2015
https://doi.org/10.1109/ICDCS.2015.36
Nakajima MOikawa S(2014)Analyzing Behavior of Less Interrupt Overhead Architecture for Effective Cache UtilizationProceedings of the 2014 Second International Symposium on Computing and Networking10.1109/CANDAR.2014.112(611-613)Online publication date: 10-Dec-2014
https://dl.acm.org/doi/10.1109/CANDAR.2014.112
Bruns FKuschnerus DBilgic AShin SMaldonado J(2013)Virtualization for safety-critical, deeply-embedded devicesProceedings of the 28th Annual ACM Symposium on Applied Computing10.1145/2480362.2480640(1485-1492)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2480362.2480640
Blackham BShi YHeiser GFelber PBellosa FBos H(2012)Improving interrupt response time in a verifiable protected microkernelProceedings of the 7th ACM european conference on Computer Systems10.1145/2168836.2168869(323-336)Online publication date: 10-Apr-2012
https://dl.acm.org/doi/10.1145/2168836.2168869
Bergel AHarrison WCahill VClarke S(2011)FlowTalkIEEE Transactions on Software Engineering10.1109/TSE.2010.6637:4(526-543)Online publication date: 1-Jul-2011
https://dl.acm.org/doi/10.1109/TSE.2010.66
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Table of Contents