Specialization tools and techniques for systematic optimization of system software

ABSTRACT

Specialization has been recognized as a powerful technique for optimizing operating systems. However, specialization has not been broadly applied beyond the research community because current techniques based on manual specialization, are time-consuming and error-prone. The goal of the work described in this paper is to help operating system tuners perform specialization more easily. We have built a specialization toolkit that assists the major tasks of specializing operating systems. We demonstrate the effectiveness of the toolkit by applying it to three diverse operating system components. We show that using tools to assist specialization enables significant performance optimizations without error-prone manual modifications. Our experience with the toolkit suggests new ways of designing systems that combine high performance and clean structure.

REFERENCES

• 1: ADOBE SYSTEMS. 1984. The PostScript Language Reference Manual. 1st ed. Addison-Wesley, Reading, MA.
• 2: AMARASINGHE,S.P.,ANDERSON,J.M.,LAM,M.S.,AND TSENG, C. W. 1995. The SUIF compiler for scalable parallel machines. In Proceedings of the 7th SIAM Conference on Parallel Processing for Scientific Computing (San Francisco, Feb.). SIAM, Philadelphia, PA.
• 3: Lars Ole Andersen, Binding-time analysis and the taming of C pointers, Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.47-58, June 14-16, 1993, Copenhagen, Denmark [doi>10.1145/154630.154636]
• 4: Jennifer M. Anderson , Lance M. Berc , Jeffrey Dean , Sanjay Ghemawat , Monika R. Henzinger , Shun-Tak A. Leung , Richard L. Sites , Mark T. Vandevoorde , Carl A. Waldspurger , William E. Weihl, Continuous profiling: where have all the cycles gone?, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.1-14, October 05-08, 1997, Saint Malo, France
• 5: BERNERS-LEE, T., FIELDING, R., AND FRYSTYK, H. 1996. Hypertext transfer protocol HTTP/1.0. RFC 1945. ftp:// ftp.isi.edu/in-notes/rfc1945.txt.
• 6: B. N. Bershad , S. Savage , P. Pardyak , E. G. Sirer , M. E. Fiuczynski , D. Becker , C. Chambers , S. Eggers, Extensibility safety and performance in the SPIN operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.267-283, December 03-06, 1995, Copper Mountain, Colorado, United States
• 7: CAMPBELL,R.H.,ISLAM, N., AND MADANY, P. 1992. Choices, frameworks and refinement. Comput. Syst. 5, 3, 217-257.
• 8: Shanwei Cen, A software feedback toolkit and its application in adaptive multimedia systems, Oregon Graduate Institute of Science & Technology, Beaverton, OR, 1998
• 9: Charles Consel , Olivier Danvy, Tutorial notes on partial evaluation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.493-501, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158707]
• 10: CONSEL,C.AND MARLET, R. 1998. Architecturing software using a methodology for language development. In Proceedings of the International Symposium on Programming Language Implementation, Logics and Programs (PLILP, Pisa, Italy). ACM, New York, NY.
• 11: Charles Consel , François Noël, A general approach for run-time specialization and its application to C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.145-156, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237767]
• 12: Crispin Cowan , Dylan McNamee , Andrew Black , Calton Pu , Jonathan Walpole , Charles Krasic , Perry Wagle , Qian Zhang , Renauld Marlet, A Toolkit for Specializing Production Operating System Code, Oregon Graduate Institute School of Science & Engineering, 1997
• 13: C. Cowan , T. Autrey , C. Krasic , C. Pu , J. Walpole, Fast concurrent dynamic linking for an adaptive operating system, Proceedings of the 3rd International Conference on Configurable Distributed Systems, p.108, May 06-08, 1996
• 14: Manuvir Das , Thomas Reps , Pascal van Hentenryck, Semantic foundations of binding-time analysis for imperative programs, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.100-110, June 21-23, 1995, La Jolla, California, United States [doi>10.1145/215465.215569]
• 15: Dawson R. Engler , Wilson C. Hsieh , M. Frans Kaashoek, C: a language for high-level, efficient, and machine-independent dynamic code generation, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.131-144, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237765]
• 16: 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
• 17: FIELDING, R., GETTYS, J., MOGUL, J., FRYSTYK, H., MASINTER, L., LEACH, P., AND BERNERS-LEE,T. 1999. Hypertext Transfer Protocol HTTP/1.1. RFC 2616. ftp://ftp.isi.edu/in-notes/rfc2616.txt.
• 18: Bryan Ford , Sai Susarla, CPU inheritance scheduling, ACM SIGOPS Operating Systems Review, v.30 n.SI, p.91-105, Oct. 1996
• 19: Bryan Ford , Godmar Back , Greg Benson , Jay Lepreau , Albert Lin , Olin Shivers, The Flux OSKit: a substrate for kernel and language research, ACM SIGOPS Operating Systems Review, v.31 n.5, p.38-51, Dec. 1997
• 20: Bryan Ford , Mike Hibler , Jay Lepreau , Patrick Tullmann , Godmar Back , Stephen Clawson, Microkernels meet recursive virtual machines, ACM SIGOPS Operating Systems Review, v.30 n.SI, p.137-151, Oct. 1996
• 21: GHORMLEY,D.P.,PETROU, D., ANDERSON,T.E.,AND RODRIGUES, S. H. 1998. SLIC: An extensibility system for commodity operating systems. In Proceedings of the 1998 USENIX Annual Technical Conference (New Orleans, LA, June). USENIX Assoc., Berkeley, CA, 39-52.
• 22: GOEL, A., STEERE, D., PU, C., AND WALPOLE, J. 1998. SWiFT: A feedback control and dynamic reconfiguration toolkit. Oregon Graduate Institute of Science & Technology, Beaverton, OR.
• 23: Brian Grant , Matthai Philipose , Markus Mock , Craig Chambers , Susan J. Eggers, An evaluation of staged run-time optimizations in DyC, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.293-304, May 01-04, 1999, Atlanta, Georgia, United States
• 24: Luke Hornof , Jacques Noyé, Accurate binding-time analysis for imperative languages: flow, context, and return sensitivity, ACM SIGPLAN Notices, v.32 n.12, p.63-73, Dec. 1997
• 25: Luke Hornof , Charles Consel , Jacques Noyé, Effective Specialization of Realistic Programs via Use Sensitivity, Proceedings of the 4th International Symposium on Static Analysis, p.293-314, September 08-10, 1997
• 26: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 27: Neil D. Jones , Carsten K. Gomard , Peter Sestoft, Partial evaluation and automatic program generation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 28: Neil D. Jones , Peter Sestoft , Harald Sondergaard, An experiment in partial evaluation: the generation of a compiler generator, Proc. of the first international conference on Rewriting techniques and applications, p.124-140, December 1985, Dijon, France
• 29: Gregor Kiczales, Beyond the Black Box: Open Implementation, IEEE Software, v.13 n.1, p.8-11, January 1996
• 30: KICZALES, G., LAMPING, J., MENDHEKAR, A., MAEDA, C., LOPES,C.V.,LOINGTIER, J.-M., AND IRWIN, J. 1997. Aspect-oriented programming. In Proceedings of the European Conference on Object-Oriented Programming (ECOOP '97). Springer-Verlag, New York, NY. Lecture Notes in Computer Science, vol. 1241.
• 31: LEROY, X. 1996. The LinuxThreads library. http://pauillac.inria.fr/xleroy/linuxthreads/.
• 32: Xiaoming Liu , Christoph Kreitz , Robbert van Renesse , Jason Hickey , Mark Hayden , Kenneth Birman , Robert Constable, Building reliable, high-performance communication systems from components, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.80-92, December 12-15, 1999, Charleston, South Carolina, United States
• 33: Cristina Videira Lopes , Gregor Kiczales, Recent Developments in Aspect, Workshop ion on Object-Oriented Technology, p.398-401, July 20-24, 1998
• 34: Renaud Marlet , Charles Consel , Philippe Boinot, Efficient incremental run-time specialization for free, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.281-292, May 01-04, 1999, Atlanta, Georgia, United States
• 35: H. Massalin , C. Pu, Threads and input/output in the synthesis kernal, Proceedings of the twelfth ACM symposium on Operating systems principles, p.191-201, November 1989
• 36: MCCANNE,S.AND JACOBSON, V. 1993. The BSD packet filter: A new architecture for user-level packet capture. In Proceedings of the Winter Usenix Conference (Jan.). USENIX Assoc., Berkeley, CA, 259-269.
• 37: MCVOY,L.AND STAELIN, C. 1996. lmbench: Portable tools fo performance analysis. In Proceedings of the USENIX Technical Conference. USENIX Assoc., Berkeley, CA.
• 38: MONTZ, A., MOSBERGER, D., O'MALLEY, S., PETERSON, L., PROEBSTING, T., AND HARTMAN,J. 1994. Scout: A communications-oriented operating system. In Proceedings of the 1st USENIX Symposium on Operating Systems Design and Implementation (OSDI '94, Monterey, CA, Nov.). USENIX Assoc., Berkeley, CA.
• 39: Gilles Muller , Renaud Marlet , Eugen-Nicolae Volanschi, Accurate program analyses for successful specialization of legacy system software, Theoretical Computer Science, v.248 n.1-2, p.201-210, October 2000 [doi>10.1016/S0304-3975(00)00052-9]
• 40: G. Muller , R. Marlet , E.-N. Volanschi , C. Consel , C. Pu , A. Goel, Fast, Optimized Sun RPC Using Automatic Program Specialization, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.240, May 26-29, 1998
• 41: Gilles Muller , Eugen-Nicolae Volanschi , Renaud Marlet, Scaling up partial evaluation for optimizing the Sun commercial RPC protocol, ACM SIGPLAN Notices, v.32 n.12, p.116-126, Dec. 1997
• 42: Robert O'Callahan , Daniel Jackson, Lackwit: a program understanding tool based on type inference, Proceedings of the 19th international conference on Software engineering, p.338-348, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253351]
• 43: ORR, D. 1992. OMOS An object server for program execution. In Proceedings of the International Workshop on Object-Oriented Operating Systems.
• 44: Przemysław Pardyak , Brian N. Bershad, Dynamic binding for an extensible system, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.201-212, October 29-November 01, 1996, Seattle, Washington, United States
• 45: C. Pu , T. Autrey , A. Black , C. Consel , C. Cowan , J. Inouye , L. Kethana , J. Walpole , K. Zhang, Optimistic incremental specialization: streamlining a commercial operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.314-321, December 03-06, 1995, Copper Mountain, Colorado, United States
• 46: Rick Ramsey, All about administering NIS+, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 47: RASHID,R.AND BARON, R. 1989. Mach: A foundation for open systems. In Proceedings of the 2nd IEEE Workshop on Workstation Operating Systems. IEEE Press, Piscataway, NJ.
• 48: SESTOFT,P.AND ZAMULIN, A. V. 1988. Annotated bibliography on partial evaluation and mixed computation. In Partial Evaluation and Mixed Computation. North-Holland Publishing Co., Amsterdam, The Netherlands.
• 49: Tim Sheard , Zine-el-abidine Benaissa , Emir Pasalic, DSL implementation using staging and monads, Proceedings of the 2nd conference on Domain-specific languages, p.81-94, October 03-06, 1999, Austin, Texas, United States
• 50: Mark Shields , Tim Sheard , Simon Peyton Jones, Dynamic typing as staged type inference, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.289-302, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268970]
• 51: SILICON GRAPHICS. 1999. Lockmeter: Kernel spinlock metering for Linux IA32. Silicon Graphics, Inc., Mountain View, CA.
• 52: SMALL,C.AND SELTZER, M. 1994. VINO: An integrated platform for operating system and database research. Tech. Rep. TR-30-94. Department of Electrical Engineering and Computer Science, Harvard Univ., Cambridge, MA.
• 53: SUN MICROSYSTEMS. 1998a. NFS: Network File System protocol specification. Sun Microsystems, Inc., Mountain View, CA.
• 54: SUN MICROSYSTEMS. 1998b. RPC: Remote Procedure Call protocol specification, version 2. Sun Microsystems, Inc., Mountain View, CA.
• 55: SUN MICROSYSTEMS. 1999. Solaris Naming Administration Guide. Sun Microsystems, Inc., Mountain View, CA.
• 56: TAHA, W. 1999. Multistage programming: Its theory and applications. Oregon Graduate Institute of Science & Technology, Beaverton, OR.
• 57: Walid Taha , Tim Sheard, Multi-stage programming with explicit annotations, ACM SIGPLAN Notices, v.32 n.12, p.203-217, Dec. 1997
• 58: Ariel Tamches , Barton P. Miller, Fine-grained dynamic instrumentation of commodity operating system kernels, Proceedings of the third symposium on Operating systems design and implementation, p.117-130, February 1999, New Orleans, Louisiana, United States
• 59: TENNENHOUSE, D., SMITH, J., SINCOSKIE, D., WETHERALL, D., AND MINDEN, G. 1997. A survey of active network research. IEEE Commun. Mag. 35,1,80-86.
• 60: Frank Tip, A Survey of Program Slicing Techniques., CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1994
• 61: WHITE, J. E. 1994. Telescript technology: The foundation for the electronic marketplace. General Magic, Inc., Mountain View, CA.
• 62: WOOLRIDGE,M.AND JENNINGS, N. 1995. Intelligent agents: Theory and practice. Knowl. Eng. Rev. 10,2.
• 63: YAGHMOUR, K. 1999. Linux trace toolkit. http://www.info.polymtl.ca/home/karym/www/trace/.
• 64: YOKOTE, Y., TERAOKA, F., AND TOKORO, M. 1989. A reflective architecture for an object-oriented distributed operating system. In Proceedings of the 1989 European Conference on Object-Oriented Programming (ECOOP '89, Nottingham, UK).

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Design, Performance

Keywords:
operating system specialization, optimization, software architecture