The multikernel: a new OS architecture for scalable multicore systems

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.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design

General Terms:
Design, Experimentation, Performance

Keywords:
message passing, multicore processors, scalability