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. S. Akyurek and K. Salem. Adaptive Block Rearrangement. ACM Transactions on Computer Systems, 13(2):89--121, May 1995.]]
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. A. C. Arpaci-Dusseau and R. H. Arpaci-Dusseau. Information and Control in Gray-Box Systems. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP '01), pages 43--56, Banff, Canada, October 2001.]]
4. B. N. Bershad, S. Savage, P. Pardyak, E. G. Sirer, M. E. Fiuczynski, D. Becker, C. Chambers, and S. Eggers. Extensibility, Safety and Performance in the SPIN Operating System. In Proceedings of the 15th ACM Symposium on Operating Systems Principles (SOSP '95), pages 267--284, Copper Mountain Resort, Colorado, December 1995.]]
5. L. S. Brakmo, S. W. O'Malley, and L. L. Peterson. TCP Vegas: New Techniques for Congestion Detection and Avoidance. In Proceedings of SIGCOMM '94, pages 24--35, London, United Kingdom, August 1994.]]
6. N. C. Burnett, J. Bent, A. C. Arpaci-Dusseau, and R. H. Arpaci-Dusseau. Exploiting Gray-Box Knowledge of Buffer-Cache Contents. In Proceedings of the USENIX Annual Technical Conference (USENIX '02), pages 29--44, Monterey, California, June 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. D. R. Cheriton and W. Zwaenepoel. The distributed V kernel and its performance for diskless workstations. In Proceedings of the 9th ACM Symposium on Operating System Principles (SOSP '83), pages 129--140, Bretton Woods, New Hampshire, October 1983.]]
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. E. W. Dijkstra. The Structure of the THE Multiprogramming System. Communications of the ACM, 11(5):341--346, May 1968.]]
12. P. Druschel, V. Pai, and W. Zwaenepoel. Extensible Kernels are Leading OS Research Astray. In Proceedings of the 6th Workshop on Workstation Operating Systems (WWOS-VI), pages 38--42, Cape Codd, Massachusetts, May 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, and J. W. O'Toole. Exokernel: An Operating System Architecture for Application-Level Resource Management. In Proceedings of the 15th ACM Symposium on Operating Systems Principles (SOSP '95), pages 251--266, Copper Mountain Resort, Colorado, December 1995.]]
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. J. C. Hoe. Improving the Start-up Behavior of a Congestion Control Sheme for TCP. In Proceedings of SIGCOMM '96, pages 270--280, Stanford, California, August 1996.]]
17. S. Iyer and P. Druschel. Anticipatory scheduling: A disk scheduling framework to overcome deceptive idleness in synchronous I/O. In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP '01), pages 117--130, Banff, Canada, October 2001.]]
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. In Proceedings of SIGCOMM '88, pages 314--329, Stanford, California, August 1988.]]
20. T. Johnson and D. Shasha. 2Q: A Low-Overhead High Performance Buffer Management Replacement Algorithm. In Proceedings of the 20th International Conference on Very Large Databases (VLDB 20), pages 439--450, Santiago, Chile, September 1994.]]
21. M. F. Kaashoek, D. R. Engler, G. R. Ganger, H. Briceno, R. Hunt, D. Mazieres, T. Pinckney, R. Grimm, J. Jannotti, and K. Mackenzie. Application Performance and Flexibility on Exokernel Systems. In Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP '97), pages 52--65, Saint-Malo, France, October 1997.]]
22. G. Kiczales, J. Lamping, C. V. Lopes, C. Maeda, A. Mendhekar, and G. C. Murphy. Open Implementation Design Guidelines. In International Conference on Software Engineering (ICSE '97), pages 481--490, Boston, Massachusetts, May 1997.]]
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. B. W. Lampson. Hints for Computer System Design. In Proceedings of the 9th ACM Symposium on Operating System Principles (SOSP '83), pages 33--48, Bretton Woods, New Hampshire, October 1983.]]
25. R. Levin, E. Cohen, W. Corwin, P. F., and W. Wulf. Policy/mechanism separation in Hydra. In Proceedings of the 5th ACM Symposium on Operating Systems Principles (SOSP '75), pages 132--140, University of Texas at Austin, November 1975.]]
26. J. Liedtke. On micro-kernel construction. In Proceedings of the 15th ACM Symposium on Operating Systems Principles (SOSP '95), pages 237--250, Copper Mountain Resort, Colorado, December 1995.]]
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. C. R. Lumb, J. Schindler, and G. R. Ganger. Freeblock Scheduling Outside of Disk Firmware. In Proceedings of the 1st USENIX Symposium on File and Storage Technologies (FAST '02), pages 10--22, Monterey, California, January 2002.]]
29. J. N. Matthews, D. Roselli, A. M. Costello, R. Y. Wang, and T. E. Anderson. Improving the Performance of Log-Structured File Systems with Adaptive Methods. In Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP '97), pages 238--251, Saint-Malo, France, October 1997.]]
30. M. K. McKusick, W. N. Joy, S. J. Leffler, and R. S. Fabry. A Fast File System for UNIX. ACM Transactions on Computer Systems, 2(3):181--197, August 1984.]]
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. E. J. O'Neil, P. E. O'Neil, and G. Weikum. The LRU-K Page Replacement Algorithm For Database Disk Buffering. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (SIGMOD '93), pages 297--306, Washington, DC, May 1993.]]
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. D. Pearce, P. Kelly, U. Harder, and T. Field. GILK: A dynamic instrumentation tool for the Linux Kernel. In Proceedings of the 12th International Conference on Modeling Tools and Techniques for Computer and Communication System Performance Evaluation (TOOLS '02), pages 220--226, London, United Kingdom, April 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. E. Riedel, M. Kallahalla, and R. Swaminathan. A Framework for Evaluating Storage System Security. In Proceedings of the 1st USENIX Symposium on File and Storage Technologies (FAST '02), pages 14--29, Monterey, California, January 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. M. I. Seltzer, Y. Endo, C. Small, and K. A. Smith. Dealing With Disaster: Surviving Misbehaved Kernel Extensions. In Proceedings of the 2nd Symposium on Operating Systems Design and Implementation (OSDI '96), pages 213--228, Seattle, Washington, October 1996.]]
43. P. Shenoy and H. Vin. Cello: A Disk Scheduling Framework for Next-generation Operating Systems. In Proceedings of the 1998 Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS/PERFORMANCE '98), pages 44--55, Madison, Wisconsin, June 1998.]]
44. Y. Smaragdakis, S. F. Kaplan, and P. R. Wilson. EELRU: Simple and Effective Adaptive Page Replacement. In Proceedings of the 1999 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems (SIGMETRICS '99), pages 122--133, Atlanta, Georgia, May 1999.]]
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. M. Stonebraker. Operating System Support for Database Management. Communications of the ACM, 24(7):412--418, July 1981.]]
47. A. Tamches and B. P. Miller. Fine-Grained Dynamic Instrumentation of Commodity Operating System Kernels. In Proceedings of the 3rd Symposium on Operating Systems Design and Implementation (OSDI '99), pages 117--130, New Orleans, Louisiana, February 1999.]]
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. R. van Renesse. Masking the Overhead of Protocol Layering. In Proceedings of SIGCOMM '96, pages 96--104, Stanford, California, August 1996.]]
50. A. Venkataramani, R. Kokku, and M. Dahlin. Tcp-nice: A mechanism for background transfers. In Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI '02), pages 329--344, Boston, Massachusetts, December 2002.]]
51. R. Wahbe, S. Lucco, T. Anderson, and S. Graham. Efficient Software-Based Fault Isolation. In Proceedings of the 14th ACM Symposium on Operating Systems Principles (SOSP '93), pages 203--216, Asheville, North Carolina, December 1993.]]
52. B. White, J. Lepreau, L. Stoller, R. Ricci, S. Guruprasad, M. Newbold, M. Hibler, C. Barb, and A. Joglekar. An Integrated Experimental Environment for Distributed Systems and Networks. In Proceedings of the 5th Symposium on Operating Systems Design and Implementation (OSDI '02), pages 255--270, Boston, Massachusetts, December 2002.]]
53. M. Young, A. Tevanian, R. Rashid, D. Golub, J. Eppinger, J. Chew, W. Bolosky, D. Black, and R. Baron. The Duality of Memory and Communication in the Implementation of a Multiprocessor Operating System. In Proceedings of the 11th ACM Symposium on Operating Systems Principles (SOSP '87), pages 63--76, Austin, Texas, November 1987.]]

Index Terms

• Software and its engineering

  • Software creation and management

    • Designing software

  • Software organization and properties

    • Contextual software domains

      • Operating systems