The mechanics of in-kernel synchronization for a scalable microkernel

ABSTRACT

Systems with minimal kernels address the problem of ever-increasing system software complexity by strict separation of resource permission management and resource policies into different trust domains. Lately, such system structure has found wide attention in the research community and industry in the form of hypervisors and virtual machines.

With an increasing number of processors, these systems face a scalability problem. The separation eliminates semantic information about the expected parallelism for individual resources, such as memory pages or processors. Hence, the kernel is unable to optimize its synchronization primitives on a case-by-case basis---a precondition for a scalable, yet well-performing system.

In this paper we present an adaptive synchronization scheme, one of the core building block for scalable microkernels. Herewith, unprivileged components (like virtual machines) can express the degree of concurrency at the granularity of individual resources. The kernel can safely adapt and optimize its internal synchronization regime on a case-by-case basis as we show exemplary for inter-process communication and the memory management subsystem of an L4 microkernel.

REFERENCES

• 1: Accetta, M., Baron, R., Golub, D., Rashid, R., Tevanian, A., and Young, M. Mach: A new kernel foundation for UNIX development. In Proceedings of the Summer 1986 USENIX Technical Conference and Exhibition (June 1986).
• 2: Jonathan Appavoo, Clustered objects, University of Toronto, Toronto, Ont., Canada, 2005
• 3: Appavoo, J., Auslander, M., Dasilva, D., Edelsohn, D., Krieger, O., Ostrowski, M., Et Al. Memory management in k42. Whitepaper, Aug. 2002.
• 4: Paul Barham , Boris Dragovic , Keir Fraser , Steven Hand , Tim Harris , Alex Ho , Rolf Neugebauer , Ian Pratt , Andrew Warfield, Xen and the art of virtualization, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 5: B. Bershad , T. Anderson , E. Lazowska , H. Levy, Lightweight remote procedure call, Proceedings of the twelfth ACM symposium on Operating systems principles, p.102-113, November 1989
• 6: Bull, J. M., and O'Neill, D. A microbenchmark suite for openMP 2.0. In 3rd European Workshop on OpenMP (Sept. 2001).
• 7: Chaves, Jr., E. M., Leblanc, T. J., Marsh, B. D., and Scott, M. L. Kernel-kernel communication in a shared-memory multiprocessor. In The Symposium on Experiences with Distributed and Multiprocessor Systems (Atlanta, GA, Mar. 1991).
• 8: Chen, B. Multiprocessing with the Exokernel operating system. Master's thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2000.
• 9: Corp., I. IA-32 Intel Architecture Software Developer's Manual, Volume 1--3, 2004.
• 10: D. R. Engler , M. F. Kaashoek , J. O'Toole, Jr., Exokernel: an operating system architecture for application-level resource management, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.251-266, December 03-06, 1995, Copper Mountain, Colorado, United States
• 11: Eran Gabber , Christopher Small , John Bruno , José Brustoloni , Avi Silberschatz, The pebble component-based operating system, Proceedings of the annual conference on USENIX Annual Technical Conference, p.20-20, June 06-11, 1999, Monterey, California
• 12: Ben Gamsa , Orran Krieger , Jonathan Appavoo , Michael Stumm, Tornado: maximizing locality and concurrency in a shared memory multiprocessor operating system, Proceedings of the third symposium on Operating systems design and implementation, p.87-100, February 1999, New Orleans, Louisiana, United States
• 13: James R. Goodman , Mary K. Vernon , Philip J. Woest, Efficient synchronization primitives for large-scale cache-coherent multiprocessors, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.64-75, April 03-06, 1989, Boston, Massachusetts, United States
• 14: H. Hartig , J. Wolter , J. Liedtke, Flexible-sized page-objects, Proceedings of the 5th International Workshop on Object Orientation in Operating Systems (IWOOOS '96), p.102, October 27-28, 1996
• 15: Gernot Heiser , Volkmar Uhlig , Joshua LeVasseur, Are virtual-machine monitors microkernels done right?, ACM SIGOPS Operating Systems Review, v.40 n.1, p.95-99, January 2006 [doi>10.1145/1113361.1113363]
• 16: Ho, C.-T., and Johnsson, L. Distributed routing algorithm for broadcasting and personalized communication in hypercubes. In International Conference on Parallel Processing (ICPP 1986) (1986), pp. 640--648.
• 17: IEEE. IEEE Std 1596--1992: IEEE Standard for Scalable Coherent Interface. IEEE, Inc., Aug. 1993.
• 18: Charles E. Leiserson, Fat-trees: universal networks for hardware-efficient supercomputing, IEEE Transactions on Computers, v.34 n.10, p.892-901, Oct. 1985
• 19: Daniel Lenoski , James Laudon , Kourosh Gharachorloo , Wolf-Dietrich Weber , Anoop Gupta , John Hennessy , Mark Horowitz , Monica S. Lam, The Stanford Dash Multiprocessor, Computer, v.25 n.3, p.63-79, March 1992 [doi>10.1109/2.121510]
• 20: Joshua LeVasseur , Volkmar Uhlig , Jan Stoess , Stefan Götz, Unmodified device driver reuse and improved system dependability via virtual machines, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.2-2, December 06-08, 2004, San Francisco, CA
• 21: J. Liedtke, On micro-kernel construction, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.237-250, December 03-06, 1995, Copper Mountain, Colorado, United States
• 22: Beng-Hong Lim, Reactive synchronization algorithms for multiprocessors, Massachusetts Institute of Technology, Cambridge, MA, 1995
• 23: Paul E. McKenney, Selecting locking primitives for parallel programming, Communications of the ACM, v.39 n.10, p.75-82, Oct. 1996 [doi>10.1145/236156.236174]
• 24: Mckenney, P. E., and Slingwine, J. D. Read-copy update: Using execution history to solve concurrency problems. In Parallel and Distributed Computing and Systems (Las Vegas, NV, Oct. 1998).
• 25: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 26: Ravi Rajwar , James R. Goodman, Speculative lock elision: enabling highly concurrent multithreaded execution, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 27: Stuart Ritchie, The Raven Kernel: a Microkernel for shared memory multiprocessors, University of British Columbia, Vancouver, BC, Canada, 1993
• 28: Sailer, R., Valdez, E., Jaeger, T., Perez, R., Van Doorn, L., Griffin, J. L., and Berger, S. sHype: Secure hypervisor approach to trusted virtualized systems. Tech. Rep. RC23511, IBM T.J. Watson Research Center, Yorktown Heights, NY, Feb. 2005.
• 29: Jonathan S. Shapiro , Jonathan M. Smith , David J. Farber, EROS: a fast capability system, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.170-185, December 12-15, 1999, Charleston, South Carolina, United States
• 30: SYSTEM ARCHITECTURE GROUP. L4 X.2 Reference Manual, 6th ed. University of Karlsruhe, Germany, Oct. 2005.
• 31: Uhlig, V. Scalability of Microkernel-Based Systems. PhD thesis, University of Karlsruhe, Germany, May 2005.
• 32: Volkmar Uhlig , Joshua LeVasseur , Espen Skoglund , Uwe Dannowski, Towards scalable multiprocessor virtual machines, Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium, p.4-4, May 06-07, 2004, San Jose, California
• 33: Ronald Christopher Unrau, Scalable memory management through hierarchical symmetric multiprocessing, University of Toronto, Toronto, Ont., Canada, 1993
• 34: Ronald C. Unrau , Orran Krieger , Benjamin Gamsa , Michael Stumm, Experiences with locking in a NUMA multiprocessor operating system kernel, Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation, p.11-es, November 14-17, 1994, Monterey, California
• 35: W. Wulf , E. Cohen , W. Corwin , A. Jones , R. Levin , C. Pierson , F. Pollack, HYDRA: the kernel of a multiprocessor operating system, Communications of the ACM, v.17 n.6, p.337-345, June 1974 [doi>10.1145/355616.364017]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
      D.4.8 Performance

General Terms:
Design, Experimentation, Measurement, Performance