[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1629575.1629579acmconferencesArticle/Chapter ViewAbstractPublication PagessospConference Proceedingsconference-collections
research-article

The multikernel: a new OS architecture for scalable multicore systems

Published: 11 October 2009 Publication History

Abstract

Commodity computer systems contain more and more processor cores and exhibit increasingly diverse architectural tradeoffs, including memory hierarchies, interconnects, instruction sets and variants, and IO configurations. Previous high-performance computing systems have scaled in specific cases, but the dynamic nature of modern client and server workloads, coupled with the impossibility of statically optimizing an OS for all workloads and hardware variants pose serious challenges for operating system structures.
We argue that the challenge of future multicore hardware is best met by embracing the networked nature of the machine, rethinking OS architecture using ideas from distributed systems. We investigate a new OS structure, the multikernel, that treats the machine as a network of independent cores, assumes no inter-core sharing at the lowest level, and moves traditional OS functionality to a distributed system of processes that communicate via message-passing.
We have implemented a multikernel OS to show that the approach is promising, and we describe how traditional scalability problems for operating systems (such as memory management) can be effectively recast using messages and can exploit insights from distributed systems and networking. An evaluation of our prototype on multicore systems shows that, even on present-day machines, the performance of a multikernel is comparable with a conventional OS, and can scale better to support future hardware.

References

[1]
AMD. AMD64 Architecture Programmer's Manual Volume 2: System Programming, Sept. 2007. Publication number 24593.
[2]
C. Amza, A.L. Cox, S. Dwarkadas, P. Keleher, H. Lu, R. Rajamony, W. Yu, and W. Zwaenepoel. TreadMarks: Shared memory computing on networks of workstations. IEEE Computer, 29(2), 1996.
[3]
T.E. Anderson, B.N. Bershad, E.D. Lazoswka, and H.M. Levy. Scheduler activations: Eective kernel support for the user-level management of threads. ACM Transactions on Computer Systems, 10:53--79, 1992.
[4]
J. Appavoo, D. Da Silva, O. Krieger, M. Auslander, M. Ostrowski, B. Rosenburg, A. Waterland, R.W. Wisniewski, J. Xenidis, M. Stumm, and L. Soares. Experience distributing objects in an SMMP OS. ACM Transactions on Computer Systems, 25(3), 2007.
[5]
K.R. Apt and M.G. Wallace. Constraint Logic Programming using ECLi PSe . Cambridge University Press, 2007.
[6]
H.E. Bal, R. Bhoedjang, R. Hofman, C. Jacobs, K. Langendoen, T. Rühl, and M.F. Kaashoek. Performance evaluation of the Orca shared-object system. ACM Transactions on Computer Systems, 16(1):1--40, 1998.
[7]
P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. Warfield. Xen and the art of virtualization. In Proceedings of the 19th ACM Symposium on Operating Systems Principles, pages 164--177, Oct. 2003.
[8]
A. Baumann, S. Peter, A. Schüpbach, A. Singhania, T. Roscoe, P. Barham, and R. Isaacs. Your computer is already a distributed system. Why isn't your OS? In Proceedings of the 12th Workshop on Hot Topics in Operating Systems, May 2009.
[9]
B.N. Bershad, T.E. Anderson, E.D. Lazowska, and H.M. Levy. Lightweight remote procedure call. ACM Transactions on Computer Systems, 8(1):37--55, 1990.
[10]
B.N. Bershad, T.E. Anderson, E.D. Lazowska, and H.M. Levy. User-level interprocess communication for shared memory multiprocessors. ACM Transactions on Computer Systems, 9(2):175--198, 1991.
[11]
S. Blightman. Auspex Architecture -- FMP Past&Present. Internal document, Auspex Systems Inc., September 1996. http://www.bitsavers.org/pdf/auspex/eng-doc/848_Auspex_ Architecture_FMP_Sep96.pdf.
[12]
S. Borkar. Thousand core chips: a technology perspective. In Proceedings of the 44th Annual Design Automation Conference, pages 746--749, 2007.
[13]
S. Boyd-Wickizer, H. Chen, R. Chen, Y. Mao, F. Kaashoek, R. Morris, A. Pesterev, L. Stein, M. Wu, Y. Dai, Y. Zhang, and Z. Zhang. Corey: An operating system for many cores. In Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation, pages 43--57, Dec. 2008.
[14]
E. Bugnion, S. Devine, K. Govil, and M. Rosenblum. Disco: running commodity operating systems on scalable multiprocessors. ACM Transactions on Computer Systems, 15(4):412--447, 1997.
[15]
C. Ca¸caval, J.G. Castaños, L. Ceze, M. Denneau, M. Gupta, s D. Lieber, J.E. Moreira, K. Strauss, and H.S. Warren, Jr. Evaluation of a multithreaded architecture for cellular computing. In Proceedings of the 8th IEEE Symposium on High-Performance Computer Architecture, pages 311--322, 2002.
[16]
P. Charles, C. Grotho, V. Saraswat, C. Donawa, A. Kielstra, K. Ebcioglu, C. von Praun, and V. Sarkar. X10: an object-oriented approach to non-uniform cluster computing. In Proceedings of the ACM Symposium on Object-Oriented Programming Systems, Languages, and Applications, pages 519--538, 2005.
[17]
E.M. Chaves, Jr., P.C. Das, T.J. LeBlanc, B.D. Marsh, and M.L. Scott. Kernel--Kernel communication in a shared-memory multiprocessor. Concurrency: Practice and Experience, 5(3):171--191, 1993.
[18]
P. Conway and B. Hughes. The AMD Opteron northbridge architecture. IEEE Micro, 27(2):10--21, 2007.
[19]
J. Dean and S. Ghemawat. MapReduce: simplified data processing on large clusters. In Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation, pages 137--150, 2004.
[20]
D. Dice and N. Shavit. TLRW: return of the read-write lock. In Proceedings of the 4th ACM SIGPLAN Workshop on Transactional Computing, Feb. 2009.
[21]
M. Dobrescu, N. Egi, K. Argyraki, B.-G. Chun, K. Fall, G. Iannaccone, A. Knies, M. Manesh, and S. Ratnasamy. RouteBricks: Exploiting Parallelism to Scale Software Routers. In Proceedings of the 22nd ACM Symposium on Operating Systems Principles, Oct. 2009.
[22]
D.R. Engler, M.F. Kaashoek, and J. O'Toole, Jr. Exokernel: An operating system architecture for application-level resource management. In Proceedings of the 15th ACM Symposium on Operating Systems Principles, pages 251--266, Dec. 1995.
[23]
M. Fähndrich, M. Aiken, C. Hawblitzel, O. Hodson, G.C. Hunt, J.R. Larus, and S. Levi. Language support for fast and reliable messagebased communication in Singularity OS. In Proceedings of the EuroSys Conference, pages 177--190, 2006.
[24]
B. Gamsa, O. Krieger, J. Appavoo, and M. Stumm. Tornado: Maximising locality and concurrency in a shared memory multiprocessor operating system. In Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation, pages 87--100, Feb. 1999.
[25]
K. Govil, D. Teodosiu, Y. Huang, and M. Rosenblum. Cellular Disco: resource management using virtual clusters on shared-memory multiprocessors. In Proceedings of the 17th ACM Symposium on Operating Systems Principles, pages 154--169, 1999.
[26]
M. Gschwind. The Cell Broadband Engine: exploiting multiple levels of parallelism in a chip multiprocessor. International Journal of Parallel Programming, 35(3):233--262, 2007.
[27]
D. Guniguntala, P.E. McKenney, J. Triplett, and J. Walpole. The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with Linux. IBM Systems Journal, 47(2):221--236, 2008.
[28]
S.M. Hand. Self-paging in the Nemesis operating system. In Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation, pages 73--86, Feb. 1999.
[29]
J. Held, J. Bautista, and S. Koehl. From a few cores to many: A tera-scale computing research overview. White paper, Intel, Sept. 2006. ftp://download.intel.com/research/platform/terascale/terascale_overview_paper.pdf.
[30]
J.N. Herder, H. Bos, B. Gras, P. Homburg, and A.S. Tanenbaum. MINIX 3: A highly reliable, self-repairing operating system. Operating Systems Review, 40(3):80--89, July 2006.
[31]
M.D. Hill and M.R. Marty. Amdahl's law in the multicore era. IEEE Computer, 41(7):33--38, 2008.
[32]
P. Homburg, M. van Steen, and A. Tanenbaum. Distributed shared objects as a communication paradigm. In Proceedings of the 2nd Annual ASCI Conference, pages 132--137, June 1996.
[33]
Intel Corporation. QuickPath architecture white paper, 2008.
[34]
E. Ipek, M. Kirman, N. Kirman, and J.F. Martinez. Core fusion: accommodating software diversity in chip multiprocessors. In Proceedings of the 34th International Symposium on Computer Architecture, pages 186--197, 2007.
[35]
M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly. Dryad: distributed data-parallel programs from sequential building blocks. In Proceedings of the EuroSys Conference, pages 59--72, 2007.
[36]
H. Jin, M. Frumkin, and J. Yan. The OpenMP implementation of NAS parallel benchmarks and its performance. Technical Report NAS-99011, NASA Advanced Supercomputing Division, Moett Field, CA, USA, Oct. 1999.
[37]
A.R. Karlin, K. Li, M.S. Manasse, and S. Owicki. Empirical studies of competitve spinning for a shared-memory multiprocessor. In Proceedings of the 13th ACM Symposium on Operating Systems Principles, pages 41--55, 1991.
[38]
M. Kistler, M. Perrone, and F. Petrini. Cell multiprocessor communication network: Built for speed. IEEE Micro, 26(3):10--23, 2006.
[39]
G. Klein, K. Elphinstone, G. Heiser, J. Andronick, D. Cock, P. Derrin, D. Elkaduwe, K. Engelhardt, R. Kolanski, M. Norrish, T. Sewell, H. Tuch, and S. Winwood. seL4: Formal verification of an OS kernel. In Proceedings of the 22nd ACM Symposium on Operating Systems Principles, Oct. 2009.
[40]
P. Kongetira, K. Aingaran, and K. Olukotun. Niagara: A 32-way multithreaded Sparc processor. IEEE Micro, 25(2):21--29, 2005.
[41]
M. Krohn, E. Kohler, and M.F. Kaashoek. Events can make sense. In Proceedings of the 2007 Annual USENIX Technical Conference, pages 1--14, 2007.
[42]
R. Kumar, D.M. Tullsen, P. Ranganathan, N.P. Jouppi, and K.I. Farkas. Single-ISA heterogeneous multi-core architectures for multithreaded workload performance. In Proceedings of the 31st International Symposium on Computer Architecture, pages 64--75, 2004.
[43]
H.C. Lauer and R.M. Needham. On the duality of operating systems structures. In 2nd International Symposium on Operating Systems, IRIA, 1978. Reprinted in Operating Systems Review, 13(2), 1979.
[44]
J. Liedtke. On µ-kernel construction. In Proceedings of the 15th ACM Symposium on Operating Systems Principles, pages 237--250, Dec. 1995.
[45]
lighttpd webserver. http://www.lighttpd.net/.
[46]
Linux scalability eort. http://lse.sourceforge.net/.
[47]
lwIP. http://savannah.nongnu.org/projects/lwip/.
[48]
B.D. Marsh, M.L. Scott, T.J. LeBlanc, and E.P. Markatos. Firstclass user-level threads. In Proceedings of the 13th ACM Symposium on Operating Systems Principles, pages 110--121, Oct. 1991.
[49]
T.G. Mattson, R. Van der Wijngaart, and M. Frumkin. Programming the Intel 80-core network-on-a-chip terascale processor. In Proceedings of the 2008 International Conference on Supercomputing, pages 1--11, 2008.
[50]
P.E. McKenney and J. Walpole. Introducing technology into the Linux kernel: A case study. Operating Systems Review, 42(5):4--17, July 2008.
[51]
J.M. Mellor-Crummey and M.L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Transactions on Computer Systems, 9:21--65, 1991.
[52]
Microsoft. Receive-side Scaling enhancements in Windows Server 2008. http://www.microsoft.com/whdc/device/network/ndis_rss.mspx.
[53]
D. Mosberger and L.L. Peterson. Making paths explicit in the Scout operating system. In Proceedings of the 2nd USENIX Symposium on Operating Systems Design and Implementation, pages 153--167, Oct. 1996.
[54]
D. Mosberger and J. Tin. httperf: A tool for measuring web server performance. Performance Evaluation Review, 26(3):31--37, Dec. 1998.
[55]
E.B. Nightingale, O. Hodson, R. McIlroy, C. Hawblitzel, and G. Hunt. Helios: Heterogeneous multiprocessing with satellite kernels. In Proceedings of the 22nd ACM Symposium on Operating Systems Principles, 2009.
[56]
J. Protić, M. Tomaaević, and V. Milutinović. Distributed shared memory: Concepts and systems. IEEE Parallel and Distributed Technology, 4(2):63--79, 1996.
[57]
M. Russinovich. Inside Windows Server 2008 kernel changes. Microsoft TechNet Magazine, Mar. 2008.
[58]
M. Russinovich. Inside Windows 7. Microsoft MSDN Channel 9, Jan. 2009.
[59]
K. Sankaralingam, R. Nagarajan, H. Liu, C. Kim, J. Huh, D. Burger, S.W. Keckler, and C.R. Moore. Exploiting ILP, TLP, and DLP with the polymorphous TRIPS architecture. In Proceedings of the 30th International Symposium on Computer Architecture, pages 422--433, 2003.
[60]
A. Schüpbach, S. Peter, A. Baumann, T. Roscoe, P. Barham, T. Harris, and R. Isaacs. Embracing diversity in the Barrelfish manycore operating system. In Proceedings of the Workshop on Managed Many-Core Systems, June 2008.
[61]
L. Seiler, D. Carmean, E. Sprangle, T. Forsyth, M. Abrash, P. Dubey, S. Junkins, A. Lake, J. Sugerman, R. Cavin, R. Espasa, E. Grochowski, T. Juan, and P. Hanrahan. Larrabee: a many-core x86 architecture for visual computing. ACM Transactions on Graphics, 27(3):1--15, 2008.
[62]
D. Shelepov and A. Fedorova. Scheduling on heterogeneous multicore processors using architectural signatures. In Proceedings of the Workshop on the Interaction between Operating Systems and Computer Architecture, 2008.
[63]
Stanford parallel applications for shared memory (SPLASH-2). http: //www-flash.stanford.edu/apps/SPLASH/.
[64]
SQLite database engine. http://www.sqlite.org/.
[65]
D. Tam, R. Azimi, and M. Stumm. Thread clustering: sharing-aware scheduling on SMP-CMP-SMT multiprocessors. In Proceedings of the EuroSys Conference, pages 47--58, 2007.
[66]
A.S. Tanenbaum and R. van Renesse. Distributed operating systems. ACM Computing Surveys, 17(4):419--470, 1985.
[67]
V. Uhlig. Scalability of Microkernel-Based Systems. PhD thesis, Computer Science Department, University of Karlsruhe, Germany, June 2005.
[68]
S. Vangal, J. Howard, G. Ruhl, S. Dighe, H. Wilson, J. Tschanz, D. Finan, P. Iyer, A. Singh, T. Jacob, S. Jain, S. Venkataraman, Y. Hoskote, and N. Borkar. An 80-tile 1.28TFLOPS network-on-chip in 65nm CMOS. In International Solid-State Circuits Conference, pages 98--589, Feb. 2007.
[69]
D. Wentzla and A. Agarwal. Factored operating systems (fos): The case for a scalable operating system for multicores. Operating Systems Review, 43(2), Apr. 2009.
[70]
D. Wentzla, P. Griffin, H. Homann, L. Bao, B. Edwards, C. Ramey, M. Mattina, C.-C. Miao, J.F. Brown, III, and A. Agarwal. Onchip interconnection architecture of the Tile Processor. IEEE Micro, 27(5):15--31, 2007.
[71]
I. Wienand and L. Macpherson. ipbench: A framework for distributed network benchmarking. In AUUG Winter Conference, Melbourne, Australia, Sept. 2004.

Cited By

View all
  • (2024)BrickOS: specialized kernels for heterogeneous hardware resourcesSCIENTIA SINICA Informationis10.1360/SSI-2022-041354:3(491)Online publication date: 11-Mar-2024
  • (2024)Bridge: A Leak-Free Hardware-Software Architecture for Parallel Embedded SystemsProceedings of the 2nd Workshop on Kernel Isolation, Safety and Verification10.1145/3698576.3698765(16-22)Online publication date: 4-Nov-2024
  • (2024)Eliminating eBPF Tracing Overhead on Untraced ProcessesProceedings of the ACM SIGCOMM 2024 Workshop on eBPF and Kernel Extensions10.1145/3672197.3673431(16-22)Online publication date: 4-Aug-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SOSP '09: Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles
October 2009
346 pages
ISBN:9781605587523
DOI:10.1145/1629575
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 October 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. message passing
  2. multicore processors
  3. scalability

Qualifiers

  • Research-article

Conference

SOSP09
Sponsor:

Acceptance Rates

Overall Acceptance Rate 174 of 961 submissions, 18%

Upcoming Conference

SOSP '25
ACM SIGOPS 31st Symposium on Operating Systems Principles
October 13 - 16, 2025
Seoul , Republic of Korea

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)504
  • Downloads (Last 6 weeks)41
Reflects downloads up to 11 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)BrickOS: specialized kernels for heterogeneous hardware resourcesSCIENTIA SINICA Informationis10.1360/SSI-2022-041354:3(491)Online publication date: 11-Mar-2024
  • (2024)Bridge: A Leak-Free Hardware-Software Architecture for Parallel Embedded SystemsProceedings of the 2nd Workshop on Kernel Isolation, Safety and Verification10.1145/3698576.3698765(16-22)Online publication date: 4-Nov-2024
  • (2024)Eliminating eBPF Tracing Overhead on Untraced ProcessesProceedings of the ACM SIGCOMM 2024 Workshop on eBPF and Kernel Extensions10.1145/3672197.3673431(16-22)Online publication date: 4-Aug-2024
  • (2024)Toast: A Heterogeneous Memory Management SystemProceedings of the 2024 International Conference on Parallel Architectures and Compilation Techniques10.1145/3656019.3676944(53-65)Online publication date: 14-Oct-2024
  • (2024)HPCnix: make HPC Apps more easier like shell scriptProceedings of the International Conference on High Performance Computing in Asia-Pacific Region Workshops10.1145/3636480.3637231(83-86)Online publication date: 11-Jan-2024
  • (2024)Enoki: High Velocity Linux Kernel Scheduler DevelopmentProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3629569(962-980)Online publication date: 22-Apr-2024
  • (2024)Loupe: Driving the Development of OS Compatibility LayersProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3617232.3624861(249-267)Online publication date: 27-Apr-2024
  • (2024)Reboot-Based Recovery of Unikernels at the Component Level2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN58291.2024.00017(15-28)Online publication date: 24-Jun-2024
  • (2024)AppSteer: Framework for Improving Multicore Scalability of Network Functions via Application-aware Packet Steering2024 IEEE 24th International Symposium on Cluster, Cloud and Internet Computing (CCGrid)10.1109/CCGrid59990.2024.00012(18-27)Online publication date: 6-May-2024
  • (2024)Parallel Assembly SynthesisLogic-Based Program Synthesis and Transformation10.1007/978-3-031-71294-4_1(3-26)Online publication date: 9-Sep-2024
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media