Information and Control in Gray-Box SystemsAndrea C. Arpaci-DusseauDepartment of Computer SciencesUniversity of Wisconsin–[email protected] H. Arpaci-DusseauDepartment of Computer SciencesUniversity of Wisconsin–[email protected] modern systems, developers are often unable to modifythe underlying operating system. To build services in suchan environment, we advocate the use of gray-box techniques.When treating the operating system as a gray-box, one recog-nizes that not changing the OS restricts, but does not com-pletely obviate, both the information one can acquire aboutthe internal state of the OS and the control one can imposeon the OS. In this paper, we develop and investigate threegray-box Information and Control Layers (ICLs) for deter-mining the contents of the file-cache, controlling the layout offiles across local disk, and limiting process execution based onavailable memory. A gray-box ICL sits between a client andthe OS and uses a combination of algorithmic knowledge,observations, and inferences to garner information about orcontrol the behavior of a gray-box system. We summarize aset of techniques that are helpful in building gray-box ICLsand have begun to organize a “gray toolbox” to ease the con-struction of ICLs. Through our case studies, we demonstratethe utility of gray-box techniques, by implementing three use-ful “OS-like” services without the modification of a singleline of O S source code.1. INTRODUCTIONModern operating systems are large, complex bodies ofcode, in which hundreds of programmer-years have been in-vested. As a result, modifying an operating system is a dif-ficult, costly, and often impractical endeavor. In an extremebut perhaps realistic view, some researchers have noted thattraditional operating systems are so rigid that to most theOS is simply “hardware masquerading as software” [14].Viewing the operating system as an immutable object isclearly at od ds with the bulk of operating systems research,which seeks to develop and integrate new ideas into operat-ing systems themselves. Thus, to reduce the efforts requiredto change the OS, a large body of research has investigatedhow the operating system should be restructured so that itis extensible [8, 13, 15, 35]. In these systems, new functional-To appear in the 18th Symposium on Operating Systems Principles (SOSP18), October 21-24, 2001, Chateau Lake Louise, Banff, Canada.ity or performance improvements can easily be added, oftentailored to the desires of particular applications. However,the limitation of these approaches is that t hey too requirechanges to the operating system; even those efforts that tryto minimize OS modifications require that the OS be alteredin at least some minor way [17, 22].Unfortunately, requiring a change to even a single line ofOS code can make th e deployment of an innovation muchless likely. For commercial operating systems, the prob-lem is an obvious one, as many non-technical hurdles mustbe overcome to persuade a large company to incorporatea new idea. Even if accepted by a single vendor (or intoan open-source base), without wide-spread adoption, inno-vations are likely to go unused, since applications that runcross-platform must use the existing interfaces on oth er sys-tems. For example, consider a transactional database thatmanages raw disk to obtain high performance; even if one OSimplements an optimized “database-oriented” file system,there is little incentive to use that fi le system on the sin-gle platform, since doing so complicates the database sourcecode. Thus, only the rare idea gets incorporated widely, anda large range of good ideas are orphaned.Thus, we believe that a remaining challenge is how to dis-seminate OS research ideas without requiring any changesto the underlying OS. Some projects, particularly in dis-tributed computing, have addressed building system serviceson top of unmodified, commodity operating systems [18, 26];however, this approach may appear to be constricting as itseemingly stifles the implementation of new functionality.The thesis of this paper is that a surprisingly large class of“OS-like” services can be provided to applications withoutany modification to th e OS itself. Specifically, it is oftenpossible to acquire information about the state of th e OSand to control its behavior in unexpectedly powerful way s,even when no explicit interfaces to do so exist. With thisapproach, the OS is treated as a gray box, in which thegeneral characteristics of the algorithms employed by th eOS are known. By combining this knowledge with run-timeobservations of how t he OS reacts to various commands andqueries, many new services can be implemented.We term a software layer that provides interfaces to gatherinformation about and to control a gray-box system a gray-box Information and Control Layer (a gray-box ICL). AnICL, residing between clients (e.g., applications) and a gray-box system (e.g., the O S), presents clients with traditional orenhanced interfaces. The interfaces in the ICL allow clientsto learn about the state of the underlying system (e.g., whatdata is in the file cache?), and to control its behavior (e.g.,place these files near one another on disk). Internally, toobtain information, the ICL may observe the existing clientinteractions with the gray-box system or it may itself insertprobes into the system; in either case, combining these ob-servations with statistical analyses and a priori knowledge ofhow the OS behaves may allow the ICL to infer the currentstate of th e OS.Experienced programmers tend to exploit their knowl-edge of the behavior of the underlying system; we believethat this knowledge should be encapsulated in ICLs, so thatthese techniques can be used by all programmers. H owever,gray-box systems go one step further by combining knowl-edge with measurements and observations, a technique com-monly found in microbenchmarks [3, 33, 39, 40, 42]. Webelieve there exists a strong duality between microbench-marks and gray-box techniques. First, ICLs often requirethat underlying components be benchmarked to configureinternal thresholds and parameters. Second, understandingthe beh avior of ICLs requires understanding the behavior ofthe OS; thus, ICLs often reveal surprising behavior in theOS, much as a microbenchmark might also do.In th is paper, we exp lore the challenges of building gray-box ICLs by developing and studying three services. Thefirst is a file-cache