The impact of operating system structure on memory system performance

ABSTRACT

In this paper we evaluate the memory system behavior of two distinctly different implementations of the UNIX operating system: DEC's Ultrix, a monolithic system, and Mach 3.0 with CMU's UNIX server, a microkernel-based system. In our evaluation we use combined system and user memory reference traces of thirteen industry-standard workloads. We show that the microkernel-based system executes substantially more non-idle system instructions for an equivalent workload than the monolithic system. Furthermore, the average instruction for programs running on Mach has a higher cost, in terms of memory cycles per instruction, than on Ultrix. In the context of our traces, we explore a number of popular assertions about the memory system behavior of modern operating systems, paying special attention to the effect that Mach's microkernel architecture has on system performance. Our results indicate that many, but not all of the assertions are true, and that a few, while true, have only negligible impact on real system performance.

REFERENCES

• 1: Michael J. Accetta, Robert V. Baron, William Bolosky, David B. Golub, Richard F. Rashid, Avadis Tevanian, Jr., and Michael W. Young Mach: A New Kernel Foundation for Unix Development. Proceedings of the Summer 1986 USENIX Conference, July, 1986, pp. 93-113
• 2: A. Agarwal , R. L. Sites , M. Horowitz, ATUM: a new technique for capturing address traces using microcode, Proceedings of the 13th annual international symposium on Computer architecture, p.119-127, June 02-05, 1986, Tokyo, Japan
• 3: Anant Agarwal , John Hennessy , Mark Horowitz, Cache performance of operating system and multiprogramming workloads, ACM Transactions on Computer Systems (TOCS), v.6 n.4, p.393-431, Nov. 1988 [doi>10.1145/48012.48037]
• 4: Anant Agarwal, Analysis of Cache Performance for Operating Systems and Multiprogramming, Kluwer Academic Publishers, Norwell, MA, 1989
• 5: Thomas E. Anderson , Henry M. Levy , Brian N. Bershad , Edward D. Lazowska, The interaction of architecture and operating system design, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.108-120, April 08-11, 1991, Santa Clara, California, United States
• 6: Özalp Babaoglu , William Joy, Converting a swap-based system to do paging in an architecture lacking page-referenced bits, Proceedings of the eighth ACM symposium on Operating systems principles, p.78-86, December 14-16, 1981, Pacific Grove, California, United States
• 7: Brian N. Bershad, The increasing irrelevance of IPC Performance for Micro-kernel-Based Operating Systems, Proceedings of the Workshop on Micro-kernels and Other Kernel Architectures, p.205-212, April 27-28, 1992
• 8: Brian N. Bershad , Thomas E. Anderson , Edward D. Lazowska , Henry M. Levy, Lightweight remote procedure call, ACM Transactions on Computer Systems (TOCS), v.8 n.1, p.37-55, Feb. 1990 [doi>10.1145/77648.77650]
• 9: Brian N. Bershad, Richard P. Draves, and Alessandro Forin. Using Microbenchmarks to Evaluate System Performance. The Proceedings of the Third Workshop on Workstation Operating Systems, April, 1992, pp 148-153.
• 10: Anita Borg, R.E. Kessler, Georgia Lazana, and David Wall Long Address Traces from RISC Machines: Generation and Analysis. WRL Research Report 89/14, Digital Equipment Corporation Western Research Laboratory, 1989
• 11: J. Bradley Chen. Software Methods for System Address Tracing. The Proceedings of the Fourth Workshop on Workstation Operating Systems, October, 1993
• 12: J. Bradley Chen. Memory Behavior for an X 11 Window System. The Proceedings of the Winter 1994 USENIX Conference, January, 1994.
• 13: J. Bradley Chen , Anita Borg , Norman P. Jouppi, A simulation based study of TLB performance, Proceedings of the 19th annual international symposium on Computer architecture, p.114-123, May 19-21, 1992, Queensland, Australia
• 14: Douglas W. Clark, Cache Performance in the VAX-11/780, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.24-37, Feb. 1983 [doi>10.1145/357353.357356]
• 15: Douglas W. Clark , Joel S. Emer, Performance of the VAX-11/780 translation buffer: simulation and measurement, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.31-62, Feb. 1985 [doi>10.1145/214451.214455]
• 16: M. DeMoney, J. Moore, and J. Mashey. Operating System Support on a RISC. Proceedings of the 31 st Computer Society International Conference (Spring Compcon '86), March, 1986, pp 138-143.
• 17: Digital Equipment Corporation. cord. Ultrix manual page.
• 18: Richard P. Draves , Brian N. Bershad , Richard F. Rashid , Randall W. Dean, Using continuations to implement thread management and communication in operating systems, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.122-136, October 13-16, 1991, Pacific Grove, California, United States
• 19: Richard P Draves. A Revised IPC Interface. Proceedings of the First Mach USENIX Workshop, October, 1990, pp. 101-121.
• 20: Peter Druschel, Larry L. Peterson, and Norman C. Hutchinson. Beyond Microkernel Design: Decoupling Modularity and Protection in Lipto. The Proceedings of the 12th International Conference on Distributed Computing Systems, June, 1992.
• 21: David Golub, Randall Dean, Alessandro Forin and Richard Rashid. UNIX as an Application Program. Proceedings of the Summer 1990 USENIX Conference, June. 1990, pp. 87-95.
• 22: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 23: Mark Donald Hill , Alan Jay Smith, Aspects of cache memory and instruction buffer performance, 1987
• 24: Gerry Kane, MIPS RISC architecture, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 25: R. E. Kessler , Mark D. Hill, Page placement algorithms for large real-indexed caches, ACM Transactions on Computer Systems (TOCS), v.10 n.4, p.338-359, Nov. 1992 [doi>10.1145/138873.138876]
• 26: Jay Lepreau , Mike Hibler , Bryan Ford , Jeffrey Law , Douglas B. Orr, In-Kernel Servers on Mach 3.0: Implementation and Performance, USENIX MACH III Symposium, p.39-56, April 19-21, 1993
• 27: S. McFarling, Program optimization for instruction caches, Proceedings of the third international conference on Architectural support for programming languages and operating systems, p.183-191, April 03-06, 1989, Boston, Massachusetts, United States
• 28: Jeffrey C. Mogul , Anita Borg, The effect of context switches on cache performance, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.75-84, April 08-11, 1991, Santa Clara, California, United States
• 29: David Nagle, Richard Uhlig, and Trevor Mudge. Monster: A Tool for Analyzing the Interaction Between Operating Systems and Computer Architectures. University of Michigan, November, 1992. CSE-TR-147-92.
• 30: David Nagle , Richard Uhlig , Tim Stanley , Stuart Sechrest , Trevor Mudge , Richard Brown, Design tradeoffs for software-managed TLBs, Proceedings of the 20th annual international symposium on Computer architecture, p.27-38, May 16-19, 1993, San Diego, California, United States
• 31: John K. Ousterhout. Why Operating Systems Aren't Getting Faster As Fast As Hardware. Proceedings of the Summer 1991 USENIX Conference, June, 1991, pp. 247-256.
• 32: Steven A. Przybylski, Cache and memory hierarchy design: a performance-directed approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 33: Richard Rashid , Avadis Tevanian , Michael Young , David Golub , Robert Baron, Machine-independent virtual memory management for paged uniprocessor and multiprocessor architectures, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.31-39, October 1987, Palo Alto, California, United States
• 34: M. Rozier, V. Abrossimov, F. Armand, I. Boule, M. Giend, M. Guillemont, F. Herrmann, P. Leonard, S. Langlois, and W. Neuhauser. "Chorus Distributed Operating Systems". Computing Systems 1, 4 (1988), pp. 305-370.
• 35: Josep Torrellas , Anoop Gupta , John Hennessy, Characterizing the caching and synchronization performance of a multiprocessor operating system, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.162-174, October 12-15, 1992, Boston, Massachusetts, United States
• 36: Bart C. Vashaw, Address trace collection and trace driven simulation of bus based, shared memory multiprocessors, Carnegie Mellon University, Pittsburgh, PA, 1992
• 37: David W. Wail. Systems for Late Code Modification. In Code Generation --- Concepts, Tools, Techniques, Springer- Verlag, 1992, pp. 275-293.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.0 General

          Nouns: UNIX

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing
  D.4 OPERATING SYSTEMS
      D.4.0 General

          Nouns: Mach
      D.4.2 Storage Management
          Subjects: Virtual memory
      D.4.8 Performance
          Subjects: Measurements

General Terms:
Design, Performance