article

The mechanics of in-kernel synchronization for a scalable microkernel

Author:

Volkmar UhligAuthors Info & Claims

ACM SIGOPS Operating Systems Review, Volume 41, Issue 4

Pages 49 - 58

https://doi.org/10.1145/1278901.1278909

Published: 01 July 2007 Publication History

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]

Appavoo, J. Clustered Objects. PhD thesis, University of Toronto, 2005.

Digital Library

[3]

Appavoo, J., Auslander, M., Dasilva, D., Edelsohn, D., Krieger, O., Ostrowski, M., Et Al. Memory management in k42. Whitepaper, Aug. 2002.

[4]

Barham, P., Dragovic, B., Fraser, K., Hand, S., Harris, T., Ho, A., et al. Xen and the art of virtualization. In Proc. of the 19th ACM Symposium on Operating System Principles (Bolton Landing, NY, Oct. 2003).

Digital Library

[5]

Bershad, B. N., Anderson, T. E., Lazowska, L., and Levy, H. M. Lightweight remote procedure call. In 12th Symposium on Operating System Principles (Oct. 1989).

Digital Library

[6]

Bull, J. M., and O'Neill, D. A microbenchmark suite for openMP 2.0. In 3rd European Workshop on OpenMP (Sept. 2001).

Digital Library

[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]

Engler, D. R., Kaashoek, M. F., and O'Toole, J. W. Exokernel: An operating system architecture for application-level resource management. In Proc. of the 15th ACM Symposium on Operating System Principles (Copper Mountain Resort, CO, Dec. 1995), ACM SIGOPS, pp. 251--266.

Digital Library

[11]

Gabber, E., Small, C., Bruno, J., Brustoloni, J., and Silberschatz, A. The Pebble component-based operating system. In Proceedings of the 1999 USENIX Annual Technical Conference (Monterey, CA, USA, June 1999).

Digital Library

[12]

Gamsa, B., Krieger, O., Appavoo, J., and Stumm, M. Tornado: Maximizing locality and concurrency in a shared memory multiprocessor operating system. In Proc. of the 3rd Symposium on Operating Systems Design and Implementation (1999).

Digital Library

[13]

Goodman, J. R., Vernon, M. K., and Woest, P. J. Efficient synchronization primitives for large-scale cache-coherent multiprocessors. In 3rd International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) (Boston, MA, Apr. 1989).

Digital Library

[14]

Härtig, H., Wolter, J., and Liedtke, J. Flexible-sized page-objects. In Proceedings of 5th International Workshop on Object-Orientation in Operating Systems (IWOOOS) (Washington, DC, 1996), IEEE Computer Society, pp. 102--106.

Digital Library

[15]

Heiser, G., Uhlig, V., and LeVasseur, J. Are virtual-machine monitors microkernels done right? Operating System Review 40, 1 (Jan. 2006), 95--99.

Digital Library

[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]

Leierson, C. E. Fat-trees: Universal networks for hardware-efficient supercomputing. IEEE Transactions on Computers c-34 (Oct. 1985), 892--901.

Digital Library

[19]

Lenoski, D., Laudon, J., Gharachorloo, G., Weber, W.-D., Gupta, A., Hennessy, J., Horowitz, M., and Lam, M. S. The Stanford Dash multiprocessor. IEEE Computer 25, 3 (Mar. 1992).

Digital Library

[20]

Levasseur, J., Uhlig, V., Stoess, J., and Götz, S. Unmodified device driver reuse and improved system dependability via virtual machines. In Proc. of the 6th Symposium on Operating Systems Design and Implementation (San Francisco, CA, Dec. 2004).

Digital Library

[21]

Liedtke, J. On μ-kernel construction. In Proc. of the 15th ACM Symposium on Operating System Principles (Copper Mountain Resort, CO, Dec. 1995).

Digital Library

[22]

Lim, B.-H. Reactive synchronization algorithms for multiprocessors. PhD thesis, Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1995.

Digital Library

[23]

Mckenney, P. E. Selecting locking primitives for parallel programming. Communications of the ACM 39, 10 (1996), 75--82.

Digital Library

[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]

Mellor-Crummey, J. M., and Scott, M. L. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems 9, 1 (Feb. 1991), 21--65.

Digital Library

[26]

Rajwar, R., and Goodman, J. R. Speculative lock elision: Enabling highly concurrent multithreaded execution. In Proceedings of the 34th Annual International Symposium on Microarchitecture (Austin, Texas, Dec. 1--5, 2001).

Digital Library

[27]

Ritchie, S. The Raven kernel: a microkernel for shared memory multiprocessors. Tech. Rep. TR-93-36, University of British Columbia, Department of Computer Science, 30 Apr. 1993.

Digital Library

[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]

Shapiro, J. S., Smith, J. M., and Farber, D. J. Eros: a fast capability system. In Proc. of the 17th ACM Symposium on Operating System Principles (Kiawah Island, SC, 1999).

Digital Library

[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]

Uhlig, V., Levasseur, J., Skoglund, E., and Dannowski, U. Towards scalable multiprocessor virtual machines. In Proceedings of the 3rd Virtual Machine Research and Technology Symposium (San Jose, CA, May 6--7 2004), pp. 43--56.

Digital Library

[33]

Unrau, R. Scalable Memory Management through Hierarchical Symmetric Multiprocessing. Ph.D. thesis, University of Toronto, Toronto, Ontario, Jan. 1993.

Digital Library

[34]

Unrau, R. C., Krieger, O., Gamsa, B., and Stumm, M. Experiences with locking in a NUMA multiprocessor operating system kernel. In Symposium on Operating Systems Design and Implementation (Nov. 1994).

Digital Library

[35]

Wulf, W., Cohen, E., Corwin, W., Jones, A., Levin, R., Pierson, C., and Pollack, F. Hydra: The kernel of a multiprocessor operating system. Commun. ACM 17, 6 (June 1974).

Digital Library

Cited By

ZHENG ZQI DZHOU NWANG XYU M(2018)Improving Per-Node Computing Efficiency by an Adaptive Lock-Free Scheduling ModelIEICE Transactions on Information and Systems10.1587/transinf.2018EDP7038E101.D:10(2423-2435)Online publication date: 1-Oct-2018
https://doi.org/10.1587/transinf.2018EDP7038
Zheng ZQi DYu MWang XZhou NShen YGuo J(2018)Optimizing Job Coscheduling by Adaptive Deadlock-Free SchedulerMathematical Problems in Engineering10.1155/2018/14387922018(1-18)Online publication date: 15-Aug-2018
https://doi.org/10.1155/2018/1438792
Cucinotta TLipari GSchubert L(2017)Operating System and Scheduling for Future Multicore and Many‐Core PlatformsProgramming multi‐core and many‐core computing systems10.1002/9781119332015.ch22(451-473)Online publication date: 27-Jan-2017
https://doi.org/10.1002/9781119332015.ch22
Show More Cited By

Index Terms

The mechanics of in-kernel synchronization for a scalable microkernel
1. General and reference
  1. Cross-computing tools and techniques
    1. Performance
    2. Reliability
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Communications management
    2. Extra-functional properties
      1. Software performance
      2. Software reliability

Recommendations

Comprehensive formal verification of an OS microkernel

We present an in-depth coverage of the comprehensive machine-checked formal verification of seL4, a general-purpose operating system microkernel.

We discuss the kernel design we used to make its verification tractable. We then describe the functional ...
Towards a scalable microkernel personality for multicore processors
Euro-Par'13: Proceedings of the 19th international conference on Parallel Processing

With a steady trend from singe-core to multicore processors, scalability has become a significant design issue for the Operating Systems (OS), as many critical OS functions must be re-designed in order to achieve scalable performance. While numerous ...
A Scalable Physical Memory Allocation Scheme for L4 Microkernel
COMPSAC '12: Proceedings of the 2012 IEEE 36th Annual Computer Software and Applications Conference

L4 microkernel family has become very successful on mobile devices. However, with the rapid shift from uniprocessor to multicore and manycore processor, many critical OS functions including physical memory allocator (PMA) must be re-designed in order to ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGOPS Operating Systems Review

ACM SIGOPS Operating Systems Review Volume 41, Issue 4

July 2007

86 pages

ISSN:0163-5980

DOI:10.1145/1278901

Issue’s Table of Contents

Copyright © 2007 Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2007

Published in SIGOPS Volume 41, Issue 4

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
655
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

ZHENG ZQI DZHOU NWANG XYU M(2018)Improving Per-Node Computing Efficiency by an Adaptive Lock-Free Scheduling ModelIEICE Transactions on Information and Systems10.1587/transinf.2018EDP7038E101.D:10(2423-2435)Online publication date: 1-Oct-2018
https://doi.org/10.1587/transinf.2018EDP7038
Zheng ZQi DYu MWang XZhou NShen YGuo J(2018)Optimizing Job Coscheduling by Adaptive Deadlock-Free SchedulerMathematical Problems in Engineering10.1155/2018/14387922018(1-18)Online publication date: 15-Aug-2018
https://doi.org/10.1155/2018/1438792
Cucinotta TLipari GSchubert L(2017)Operating System and Scheduling for Future Multicore and Many‐Core PlatformsProgramming multi‐core and many‐core computing systems10.1002/9781119332015.ch22(451-473)Online publication date: 27-Jan-2017
https://doi.org/10.1002/9781119332015.ch22
Wang QStamler TParmer GCadar CPietzuch PKeeton KRodrigues R(2016)Parallel sectionsProceedings of the Eleventh European Conference on Computer Systems10.1145/2901318.2901356(1-15)Online publication date: 18-Apr-2016
https://dl.acm.org/doi/10.1145/2901318.2901356
Clements AKaashoek MZeldovich NHanzálek ZHärtig HCastro MKaashoek M(2013)RadixVMProceedings of the 8th ACM European Conference on Computer Systems10.1145/2465351.2465373(211-224)Online publication date: 15-Apr-2013
https://dl.acm.org/doi/10.1145/2465351.2465373
Xian FSrisa-an WJiang H(2008)Contention-aware schedulerACM SIGPLAN Notices10.1145/1449955.144977843:10(163-180)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1449955.1449778
Xian FSrisa-an WJiang HHarris GKiczales GRiehle DBlack A(2008)Contention-aware schedulerProceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications10.1145/1449764.1449778(163-180)Online publication date: 19-Oct-2008
https://dl.acm.org/doi/10.1145/1449764.1449778

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