Transforming policies into mechanisms with infokernel

ABSTRACT

We describe an evolutionary path that allows operating systems to be used in a more flexible and appropriate manner by higher-level services. An infokernel exposes key pieces of information about its algorithms and internal state; thus, its default policies become mechanisms, which can be controlled from user-level. We have implemented two prototype infokernels based on the linuxtwofour and netbsdver kernels, called infolinux and infobsd, respectively. The infokernels export key abstractions as well as basic information primitives. Using infolinux, we have implemented four case studies showing that policies within Linux can be manipulated outside of the kernel. Specifically, we show that the default file cache replacement algorithm, file layout policy, disk scheduling algorithm, and TCP congestion control algorithm can each be turned into base mechanisms. For each case study, we have found that infokernel abstractions can be implemented with little code and that the overhead and accuracy of synthesizing policies at user-level is acceptable.

REFERENCES

• 1: Sedat Akyürek , Kenneth Salem, Adaptive block rearrangement, ACM Transactions on Computer Systems (TOCS), v.13 n.2, p.89-121, May 1995 [doi>10.1145/201045.201046]
• 2: M. Allman, H. Balakrishnan, and S. Floyd. RFC 3042: Enhancing TCP's Loss Recovery Using Limited Transmit, August 2000. Available from \textttftp://ftp.rfc-editor.org/in-notes/rfc3042.txt as of August, 2003.
• 3: Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Information and control in gray-box systems, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 4: 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
• 5: Lawrence S. Brakmo , Sean W. O'Malley , Larry L. Peterson, TCP Vegas: new techniques for congestion detection and avoidance, Proceedings of the conference on Communications architectures, protocols and applications, p.24-35, August 31-September 02, 1994, London, United Kingdom
• 6: Nathan C. Burnett , John Bent , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Exploiting Gray-Box Knowledge of Buffer-Cache Management, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.29-44, June 10-15, 2002
• 7: P. Cao, E. W. Felten, and K. Li. Implementation and Performance of Application-Controlled File Caching. In Proceedings of the 1st Symposium on Operating Systems Design and Implementation (OSDI '94), pages 165--177, Monterey, California, November 1994.
• 8: N. Cardwell and B. Bak. A TCP Vegas Implementation for Linux. Available from http://flophouse.com/~neal/uw/linux-vegas/ as of August, 2003.
• 9: David R. Cheriton , Willy Zwaenepoel, The distributed V kernel and its performance for diskless workstations, Proceedings of the ninth ACM symposium on Operating systems principles, p.129-140, October 10-13, 1983, Bretton Woods, New Hampshire, United States
• 10: H.-T. Chou and D. J. DeWitt. An Evaluation of Buffer Management Strategies for Relational Database Systems. In Proceedings of the 11th International Conference on Very Large Data Bases (VLDB 11), pages 127--41, Stockholm, Sweden, August 1985.
• 11: Edsger W. Dijkstra, The structure of the “THE”-multiprogramming system, Communications of the ACM, v.11 n.5, p.341-346, May 1968 [doi>10.1145/363095.363143]
• 12: P. Druschel , V. Pai , W. Zwaenepoel, Extensible Kernels are Leading OS Research Astray, Proceedings of the 6th Workshop on Hot Topics in Operating Systems (HotOS-VI), p.38, May 05-06, 1997
• 13: D. Ely, S. Savage, and D. Wetherall. Alpine: A User-Level Infrastructure for Network Protocol Development. In Proceedings of the 3rd USENIX Symposium on Internet Technologies and Systems (USITS '01), pages 171--184, San Francisco, California, March 2001.
• 14: 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
• 15: G. A. Gibson, D. F. Nagle, K. Amiri, F. W. Chang, H. Gobioff, E. Riedel, D. Rochberg, and J. Zelenka. Filesystems for Network-Attached Secure Disks. Technical Report CMU-CS-97-118, Carnegie Mellon University, 1997.
• 16: Janey C. Hoe, Improving the start-up behavior of a congestion control scheme for TCP, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.270-280, August 28-30, 1996, Palo Alto, California, United States
• 17: Sitaram Iyer , Peter Druschel, Anticipatory scheduling: a disk scheduling framework to overcome deceptive idleness in synchronous I/O, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 18: D. M. Jacobson and J. Wilkes. Disk Scheduling Algorithms Based on Rotational Position. Technical Report HPL-CSP-91-7, Hewlett Packard Laboratories, 1991.
• 19: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 20: Theodore Johnson , Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 20th International Conference on Very Large Data Bases, p.439-450, September 12-15, 1994
• 21: M. Frans Kaashoek , Dawson R. Engler , Gregory R. Ganger , Hector M. Briceño , Russell Hunt , David Mazières , Thomas Pinckney , Robert Grimm , John Jannotti , Kenneth Mackenzie, Application performance and flexibility on exokernel systems, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.52-65, October 05-08, 1997, Saint Malo, France
• 22: Gregor Kiczales , John Lamping , Christina Videira Lopes , Chris Maeda , Anurag Mendhekar , Gail Murphy, Open implementation design guidelines, Proceedings of the 19th international conference on Software engineering, p.481-490, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253431]
• 23: G. Kiczales, J. Lamping, C. Maeda, D. Keppel, and D. McNamee. The Need for Customizable Operating Systems. In Proceedings of the 4th Workshop on Workstation Operating Systems (WWOS-IV), pages 165--169, Napa, California, October 1993.
• 24: Butler W. Lampson, Hints for computer system design, Proceedings of the ninth ACM symposium on Operating systems principles, p.33-48, October 10-13, 1983, Bretton Woods, New Hampshire, United States
• 25: R. Levin , E. Cohen , W. Corwin , F. Pollack , W. Wulf, Policy/mechanism separation in Hydra, Proceedings of the fifth ACM symposium on Operating systems principles, p.132-140, November 19-21, 1975, Austin, Texas, United States
• 26: J. Liedtke, On micro-kernel construction, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.237-250, December 03-06, 1995, Copper Mountain, Colorado, United States
• 27: C. Lumb, J. Schindler, G. Ganger, D. Nagle, and E. Riedel. Towards Higher Disk Head Utilization: Extracting "Free" Bandwidth From Busy Disk Drives. In Proceedings of the 4th Symposium on Operating Systems Design and Implementation (OSDI '00), pages 87--102, San Diego, California, October 2000.
• 28: Christopher R. Lumb , Jiri Schindler , Gregory R. Ganger, Freeblock Scheduling Outside of Disk Firmware, Proceedings of the Conference on File and Storage Technologies, p.275-288, January 28-30, 2002
• 29: Jeanna Neefe Matthews , Drew Roselli , Adam M. Costello , Randolph Y. Wang , Thomas E. Anderson, Improving the performance of log-structured file systems with adaptive methods, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.238-251, October 05-08, 1997, Saint Malo, France
• 30: Marshall K. McKusick , William N. Joy , Samuel J. Leffler , Robert S. Fabry, A fast file system for UNIX, ACM Transactions on Computer Systems (TOCS), v.2 n.3, p.181-197, Aug. 1984 [doi>10.1145/989.990]
• 31: J. Nugent, A. C. Arpaci-Dusseau, and R. H. Arpaci-Dusseau. Controlling your PLACE in the File System with Gray-box Techniques. In Proceedings of the USENIX Annual Technical Conference (USENIX '03), pages 311--324, San Antonio, Texas, June 2003.
• 32: Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum, The LRU-K page replacement algorithm for database disk buffering, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.297-306, May 25-28, 1993, Washington, D.C., United States
• 33: J. K. Peacock, A. Kamaraju, and S. Agrawal. Fast Consistency Checking for the Solaris File System. In Proceedings of the USENIX Annual Technical Conference (USENIX '98), pages 77--89, New Orleans, Louisiana, June 1998.
• 34: David J. Pearce , Paul H. J. Kelly , Tony Field , Uli Harder, GILK: A Dynamic Instrumentation Tool for the Linux Kernel, Proceedings of the 12th International Conference on Computer Performance Evaluation, Modelling Techniques and Tools, p.220-226, April 14-17, 2002
• 35: F. I. Popovici, A. C. Arpaci-Dusseau, and R. H. Arpaci-Dusseau. Robust, Portable I/O Scheduling with the Disk Mimic. In Proceedings of the USENIX Annual Technical Conference (USENIX '03), pages 297--310, San Antonio, Texas, June 2003.
• 36: J. Postel. RFC 793: Transmission Control Protocol, September 1981. Available from \textttftp://ftp.rfc-editor.org/in-notes/rfc793.txt as of August, 2003.
• 37: Erik Riedel , Mahesh Kallahalla , Ram Swaminathan, A Framework for Evaluating Storage System Security, Proceedings of the Conference on File and Storage Technologies, p.15-30, January 28-30, 2002
• 38: M.-C. Rosu and D. Rosu. Kernel Support for Faster Web Proxies. In Proceedings of the USENIX Annual Technical Conference (USENIX '03), pages 225--238, San Antonio, Texas, June 2003.
• 39: C. Ruemmler and J. Wilkes. Disk Shuffling. Technical Report HPL-91-156, Hewlett Packard Laboratories, 1991.
• 40: J. Schindler and G. Ganger. Automated Disk Drive Characterization. Technical Report CMU-CS-99-176, Carnegie Mellon University, November 1999.
• 41: M. Seltzer, P. Chen, and J. Ousterhout. Disk Scheduling Revisited. In Proceedings of the USENIX Winter Technical Conference (USENIX Winter '90), pages 313--324, Washington, D.C, January 1990.
• 42: Margo I. Seltzer , Yasuhiro Endo , Christopher Small , Keith A. Smith, Dealing with disaster: surviving misbehaved kernel extensions, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.213-227, October 29-November 01, 1996, Seattle, Washington, United States
• 43: Prashant J. Shenoy , Harrick M. Vin, Cello: a disk scheduling framework for next generation operating systems, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.44-55, June 22-26, 1998, Madison, Wisconsin, United States
• 44: Yannis Smaragdakis , Scott Kaplan , Paul Wilson, EELRU: simple and effective adaptive page replacement, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.122-133, May 01-04, 1999, Atlanta, Georgia, United States
• 45: C. Staelin and H. Garcia-Mollina. Smart Filesystems. In Proceedings of the USENIX Winter Technical Conference (USENIX Winter '91), pages 45--51, Dallas, Texas, January 1991.
• 46: Michael Stonebraker, Operating system support for database management, Communications of the ACM, v.24 n.7, p.412-418, July 1981 [doi>10.1145/358699.358703]
• 47: 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
• 48: R. Van Meter and M. Gao. Latency Management in Storage Systems. In Proceedings of the 4th Symposium on Operating Systems Design and Implementation (OSDI '00), pages 103--117, San Diego, California, October 2000.
• 49: Robbert van Renesse, Masking the overhead of protocol layering, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.96-104, August 28-30, 1996, Palo Alto, California, United States
• 50: Arun Venkataramani , Ravi Kokku , Mike Dahlin, TCP Nice: a mechanism for background transfers, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060320]
• 51: Robert Wahbe , Steven Lucco , Thomas E. Anderson , Susan L. Graham, Efficient software-based fault isolation, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.203-216, December 05-08, 1993, Asheville, North Carolina, United States
• 52: Brian White , Jay Lepreau , Leigh Stoller , Robert Ricci , Shashi Guruprasad , Mac Newbold , Mike Hibler , Chad Barb , Abhijeet Joglekar, An integrated experimental environment for distributed systems and networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060313]
• 53: M. Young , A. Tevanian , R. Rashid , D. Golub , J. Eppinger, The duality of memory and communication in the implementation of a multiprocessor operating system, Proceedings of the eleventh ACM Symposium on Operating systems principles, p.63-76, November 08-11, 1987, Austin, Texas, United States

INDEX TERMS

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

General Terms:
Design, Experimentation, Performance

Keywords:
information, mechanism, policy