Brian N. Bershad
ABSTRACT
In this paper we describe restartable atomic sequences, an optimistic mechanism for implementing simple atomic operations (such as Test-And-Set) on a uniprocessor. A thread that is suspended within a restartable atomic sequence is resumed by the operating system at the beginning of the sequence, rather than at the point of suspension. This guarantees that the thread eventually executes the sequence atomically. A restartable atomic sequence has significantly less overhead than other software-based synchronization mechanisms, such as kernel emulation or software reservation. Consequently, it is an attractive alternative for use on uniprocessors that do no support atomic operations. Even on processors that do support atomic operations in hardware, restartable atomic sequences can have lower overhead.
We describe different implementations of restartable atomic sequences for the Mach 3.0 and Taos operating systems. These systems' thread management packages rely on atomic operations to implement higher-level mutual exclusion facilities. We show that improving the performance of low-level atomic operations, and therefore mutual exclusion mechanisms, improves application performance.
- Accetta et al 86.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 USENL~ Conference, pages 93-113, July 1986.Google Scholar
- Anderson et al 89.Anderson, T., Lazowska, E., and Levy, H. The Performance Implications of Thread Management Alternatives for Shared-Memory Multiprocessors. IEEE Transactions on Computers, 38(12):1631-1644, December 1989. Google ScholarDigital Library
- Anderson et al 91.Anderson, T., Levy, H., Bershad, B., and Lazowska, E. The interaction of Architecture and Operating System Design. In Proceedings o/the Fourth Symposium on Architectural Support for Programming Languages and Operating Systems (ASPLOS), April 1991. Google ScholarDigital Library
- Anderson et al 92.Anderson, T. E., Bershad, B. N., Lazowska, E. D., and Levy, H. M. Scheduler Activations: Effective Kernel Support for the User- Level Management of Parallelism. ACM Transactions on Computer Systems, 9(1), February 1992. Google ScholarDigital Library
- Bershad et al 88.Bershad, B. N., Lazowska, E. D., and Levy, H. M. PRESTO: A System for Object- Oriented Parallel Programming. Software: Practice and Experience, 18(,8):713-732, August 1988. Google ScholarDigital Library
- Bershad et al 92.Bershad, B. N., Draves, R. P., and Forin, A. Using Microbenchmarks to Evaluate System Performance. Ill Proceedings of the hird Workshop on Workstation Operating Sysems, April 1992.Google ScholarCross Ref
- Birrell 91.Birrell, A. An Introduction to Programming with Threads. Prentice HM1, 1991.Google Scholar
- Bose et al 89.Bose, S., Clarke, E., Long, D., and Michaylov, S. Parthenon: A Parallel Theorem Prover for Non-Horn Clauses. In Proceedings o/ the Fourth Annual Symposium on Logic ,n Computer Science, 1989. Google ScholarDigital Library
- Cheriton 88.cheriton, D. R. The V Distributed System. Communications of the ACM, 31(3):314- 333, March 1988. Google ScholarDigital Library
- Cooper & Draves 88.Cooper, E. C. and Draves, R. P. C threads. Technical Report CMU-CS-88-54, School of Computer Science, Carnegie Mellon University, February 1988.Google Scholar
- Dijkstra 68a.Dijkstra, E. W. The Structure of the "THE" Multiprogramming System. Communications o/ the ACM, 11(5), May 1968. Google ScholarDigital Library
- Dijkstra 68b.Dijkstra, E. W. Cooperating Sequential Processes, pages 43-112. Academic Press, New York, 1968.Google Scholar
- Glew & Hwu 91.Glew, A. and Hwu, W. A Feature Taxonomy and Survey of Synchronization PrimL tire Implementations. Technical Report UILU- ENG-91-2211, Center for Reliable and High- Performance Computing, University of Illinois at Urbana-Champaign, February 1991.Google Scholar
- Golub et al 90.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.Google Scholar
- Herlihy 91.Herlihy, M. Wait-free Synchronization. A CM Transactions on Programming Languages, 13(1), January 1991. Google ScholarDigital Library
- Intel386 90.386 Programmer's Reference Manual. Intel, Mt. Prospect, IL, 1990.Google Scholar
- Intel860 89.i860 6d.bit Microprocessor Programmer's Re/- erence Manual. 1989.Google Scholar
- Kane 87.Kane, G. MIPS R2000 RiSC Architecture. Prentice Hall, Englewood Cliffs, N.J., 1987.Google Scholar
- Lamport 87.Lamport, L. A Fast MutuM Exclusion Algorithm. A CM Transactions on Computer Systems, 5(1):1-11, February 1987. Google ScholarDigital Library
- Leonard 87.Leonard, T. VAX Architecture Reference Manual. Digital Equipment Corporation, 1987. Google ScholarDigital Library
- Moss & Kohler 87.Moss, J. and Kohler, W. Concurrency Features for the Trellis/Owl Language. In European Conference on Object-Oriented Programruing, June 1987. Appears in Springer-Verlag's Lecture Notes in Computer Science #276. Google ScholarDigital Library
- Motorola 88100 88.MCS 88100 RISC Microprocessor User's Manual. Phoenix, AZ, 1988.Google Scholar
- Mullender et al 90.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 Magazzne, 23(5):44-54, May 1990. Google ScholarDigital Library
- Peterson 81.Peterson, G. Myths About the Mutual Exclusion Ploblem. Information Processing Letters, 12(1), June 1981.Google Scholar
- Rovner et al 85.Rovner, P., Levin, R., and Wick, J. On Extending Modula-2 for Building Large, Integrated Systems. Technical Report # 3, Digital Equipment Corporation's Systems Research Center, Palo Alto, California, January 1985.Google Scholar
- Rozier et al 88.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.Google Scholar
- Satyanaranyanyan et al 85.Satyanaranyanyan, M., Howard, J., Nichols, D., Sidebotham, R., and Spector, A. The ITC Distributed File System: Principles and Design. In Proceedings of the l Oth A CM Symposium on Operating Systems Principles, pages 35-50, December 1985. Google ScholarDigital Library
- Thacker et al 88.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. Google ScholarDigital Library
- Weiser et al 89.Weiser, M., Demers, A., and Hauser, C. The Portable Comlnon Runtime Approach to Interoperability. In Proceedings of the 12th A CM Symposzum on Operating Systems Principles, pages 114-122, December 1989. Google ScholarDigital Library
Index Terms
- Fast mutual exclusion for uniprocessors
Recommendations
Fast mutual exclusion for uniprocessors
In this paper we describe restartable atomic sequences, an optimistic mechanism for implementing simple atomic operations (such as Test-And-Set) on a uniprocessor. A thread that is suspended within a restartable atomic sequence is resumed by the ...
A new fast-path mechanism for mutual exclusion
Several years ago, Yang and Anderson presented all N-process algorithm for mutual exclusion under read/write atomicity that has Θ(log N) time complexity, where "time" is measured by counting remote memory references. In this algorithm, instances of a ...
Comments