Information and control in gray-box systems

ABSTRACT

In modern systems, developers are often unable to modify the underlying operating system. To build services in such an environment, we advocate the use of gray-box techniques. When treating the operating system as a gray-box, one recognizes that not changing the OS restricts, but does not completely obviate, both the information one can acquire about the internal state of the OS and the control one can impose on the OS. In this paper, we develop and investigate three gray-box Information and Control Layers (ICLs) for determining the contents of the file-cache, controlling the layout of files across local disk, and limiting process execution based on available memory. A gray-box ICL sits between a client and the OS and uses a combination of algorithmic knowledge, observations, and inferences to garner information about or control the behavior of a gray-box system. We summarize a set of techniques that are helpful in building gray-box ICLs and have begun to organize a "gray toolbox" to ease the construction of ICLs. Through our case studies, we demonstrate the utility of gray-box techniques, by implementing three useful "OS-like" services without the modification of a single line of OS source code.

REFERENCES

• 1: Ramesh C. Agarwal, A super scalar sort algorithm for RISC processors, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.240-246, June 04-06, 1996, Montreal, Quebec, Canada
• 2: Thomas E. Anderson , Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, Scheduler activations: effective kernel support for the user-level management of parallelism, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.95-109, October 13-16, 1991, Pacific Grove, California, United States
• 3: Remzi H. Arpaci , David E. Culler , Arvind Krishnamurthy , Steve G. Steinberg , Katherine Yelick, Empirical evaluation of the CRAY-T3D: a compiler perspective, Proceedings of the 22nd annual international symposium on Computer architecture, p.320-331, June 22-24, 1995, S. Margherita Ligure, Italy
• 4: Andrea Carol Arpaci-Dusseau, Implicit coscheduling: coordinated scheduling with implicit information in distributed systems, ACM Transactions on Computer Systems (TOCS), v.19 n.3, p.283-331, Aug. 2001 [doi>10.1145/380749.380764]
• 5: Ö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
• 6: Mary G. Baker , John H. Hartman , Michael D. Kupfer , Ken W. Shirriff , John K. Ousterhout, Measurements of a distributed file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.198-212, October 13-16, 1991, Pacific Grove, California, United States
• 7: Hari Balakrishnan , Venkata N. Padmanabhan , Srinivasan Seshan , Randy H. Katz, A comparison of mechanisms for improving TCP performance over wireless links, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.256-269, August 28-30, 1996, Palo Alto, California, United States
• 8: 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
• 9: D. Blackwell and M. A. Girshick. Theory of Games and Statistical Decisions. John Wiley & Sons, 1954.
• 10: Edouard Bugnion , Scott Devine , Mendel Rosenblum, Disco: running commodity operating systems on scalable multiprocessors, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.143-156, October 05-08, 1997, Saint Malo, France
• 11: C. D. Cranor and G. M. Parulkar. The UVM Virtual Memory System. In USENIX '99.
• 12: John R. Douceur , William J. Bolosky, Progress-based regulation of low-importance processes, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.247-260, December 12-15, 1999, Charleston, South Carolina, United States
• 13: P. Druschel, L. L. Peterson, and N. Hutchinson. Beyond Micro-Kernel Design: Decoupling Modularity and Protection in Lipto. In ICDCS 12, 1992.
• 14: D. R. Engler , M. F. Kaashoek, Exterminate all operating system abstractions, Proceedings of the Fifth Workshop on Hot Topics in Operating Systems (HotOS-V), p.78, May 04-05, 1995
• 15: 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
• 16: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 17: D. Ghormley, D. Petrou, S. Rodrigues, and T. Anderson. SLIC: An Extensibility System for Commodity Operating Systems. In USENIX '98, June 1998.
• 18: Douglas P. Ghormley , David Petrou , Steven H. Rodrigues , Amin M. Vahdat , Thomas E. Anderson, GLUnix: a global layer Unix for a network of workstations, Software—Practice & Experience, v.28 n.9, p.929-961, July 25, 1998 [doi>10.1002/(SICI)1097-024X(19980725)28:9<929::AID-SPE183>3.0.CO;2-C]
• 19: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• 20: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 21: R. Jain. A Delay-Based Approach for Congestion Avoidance in Interconnected Heterogeneous Computer Networks. Technical Report DEC-TR-566, Digital Equipment Corporation, April 1988.
• 22: Michael B. Jones, Interposition agents: transparently interposing user code at the system interface, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.80-93, December 05-08, 1993, Asheville, North Carolina, United States
• 23: Paul C. Kocher , Joshua Jaffe , Benjamin Jun, Differential Power Analysis, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.388-397, August 15-19, 1999
• 24: Butler W. Lampson, A note on the confinement problem, Communications of the ACM, v.16 n.10, p.613-615, Oct. 1973 [doi>10.1145/362375.362389]
• 25: Butler W. Lampson, Hints for computer system design, ACM SIGOPS Operating Systems Review, v.17 n.5, p.33-48, October 1983
• 26: M. Litzkow, M. Livny, and M. Mutka. Condor - A Hunter of Idle Workstations. In ICDCS 8, June 1988.
• 27: 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]
• 28: R.V. Meter and M. Gao. Latency Management in Storage Systems. In OSDI 3, October 2000.
• 29: J. K. Ousterhout. Scheduling Techniques for Concurrent Systems. In ICDCS 3, pages 22-30, May 1982.
• 30: HweeHwa Pang , Michael J. Carey , Miron Livny, Memory-Adaptive External Sorting, Proceedings of the 19th International Conference on Very Large Data Bases, p.618-629, August 24-27, 1993
• 31: Dennis M. Ritchie , Ken Thompson, The UNIX time-sharing system, Communications of the ACM, v.17 n.7, p.365-375, July 1974 [doi>10.1145/361011.361061]
• 32: Mendel Rosenblum , John K. Ousterhout, The design and implementation of a log-structured file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.1-15, October 13-16, 1991, Pacific Grove, California, United States
• 33: Alan Jay Smith , Rafael H. Saavedra, Measuring Cache and TLB Performance and Their Effect on Benchmark Runtimes, IEEE Transactions on Computers, v.44 n.10, p.1223-1235, October 1995 [doi>10.1109/12.467697]
• 34: M. Satyanarayanan , Jason Flinn , Kevin R. Walker, Visual proxy: exploiting OS customizations without application source code, ACM SIGOPS Operating Systems Review, v.33 n.3, p.14-18, July 1999 [doi>10.1145/311124.311131]
• 35: 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
• 36: 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
• 37: Keith A. Smith , Margo I. Seltzer, File system aging—increasing the relevance of file system benchmarks, Proceedings of the 1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.203-213, June 15-18, 1997, Seattle, Washington, United States
• 38: K. A. Smith and M. I. Seltzer. A Comparison of FFS Disk Allocation Policies. In USENIX '96, 1996.
• 39: C. Staelin and L. McVoy. mhz: Anatomy of a microbenchmark. In USENIX '98, June 1998.
• 40: N. Talagala , R. Arpaci-Dusseau , D. Patterson, Micro-Benchmark Based Extraction of Local and Global Disk, University of California at Berkeley, Berkeley, CA, 2000
• 41: J. Von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, Princeton, New Jersey, second edition, 1947.
• 42: Bruce L. Worthington , Gregory R. Ganger , Yale N. Patt , John Wilkes, On-line extraction of SCSI disk drive parameters, Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.146-156, May 15-19, 1995, Ottawa, Ontario, Canada
• 43: Hansjorrg Zeller , Jim Gray, An adaptive hash join algorithm for multiuser environments, Proceedings of the sixteenth international conference on Very large databases, p.186-197, September 1990, Brisbane, Australia

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
      D.4.8 Performance

General Terms:
Performance