Operating systems represent large pieces of complex software that are carefully tested and broadly deployed. Despite this, developers frequently have little more than their source code to understand how they behave. This static representation of a system results in limited insight into execution dynamics, such as what code is important, how data flows through a system, or how threads interact with one another. We describe Tralfamadore, a system that preserves complete traces of machine execution as an artifact that can be queried and analyzed with a library of simple, reusable operators, making it easy to develop and run new dynamic analyses. We demonstrate the benefits of this approach with several example applications, including a novel unified source and execution browser.

Program source is an intermediate representation of software; it lies between a developer's intention and the hardware's execution. Despite advances in languages and development tools, source itself and the applications we use to view it remain an essentially static representation of software, from which developers can spend considerable energy postulating actual behavior.

In densely packed 802.11 environments, access-point domains significantly overlap and wireless hosts interfere with each other in complex ways. Knowing which devices interfere is an essential first step to minimizing this interference, improving efficiency and delivering quality connectivity throughout the network. This knowledge, however, is extremely difficult to obtain without either taking a running network offline for measurements or having client hosts monitor and report airspace anomalies, something typically outside the control of network administrators.

Parallax is a distributed storage system that uses virtualization to provide storage facilities specifically for virtual environments. The system employs a novel architecture in which storage features that have traditionally been implemented directly on high-end storage arrays and switches are relocated into a federation of storage VMs, sharing the same physical hosts as the VMs that they serve. This architecture retains the single administrative domain and OS agnosticism achieved by array- and switch-based approaches, while lowering the bar on hardware requirements and facilitating the development of new features. Parallax offers a comprehensive set of storage features including frequent, low-overhead snapshot of virtual disks, the 'gold-mastering' of template images, and the ability to use local disks as a persistent cache to dampen burst demand on networked storage.

In typical file systems, valuable data is vulnerable to being accidentally or maliciously deleted or overwritten. Versioning file systems protect data from accidents by transparently retaining old versions, but do less well in protecting data from malicious attack. These systems remain vulnerable to attackers who gain unauthorized access to prune old file versions, who bypass the file system to directly manipulate storage, or who exploit bugs in any part of the operating system.

It is well known that 802.11 suffers from both inefficiency and unfairness in the face of competition and interference. This paper provides a detailed analysis of the impact of topology and traffic type on network performance when two flows compete with each other for airspace. We consider both TCP and UDP flows and a comprehensive set of node topologies. We vary these topologies to consider all combinations of the following four node-to-node interactions: (1) nodes unable to read or sense each other, (2) nodes able to sense each other but not able to read each other's packets and nodes able to communicate with (3) weak and with (4) strong signal. We evaluate all possible cases through simulation and show that the cases can be reduced to 9 UDP and 10 TCP 802.1 Ig models with similar efficiency/fairness characteristics. We also validate our simulation results with extensive experiments conducted in a laboratory testbed. These more detailed models improve on previous work such as hidden-Zexposed-terminal categorization and are thus better suited as a basis for adaptive techniques to improve performance in 802.11 multi-hop WLAN or Mesh Networks.

As the disks typically found in personal computers grow larger, protecting data by replicating it on a collection of "peer" systems rather than on dedicated high performance storage systems can provide comparable reliability and availability guarantees but at reduced cost and complexity. In order to be adopted, peer-to-peer storage systems must be able to replicate data on hosts that are trusted, secure, and available. However, recent research has shown that the traditional model, where nodes are assumed to have identical levels of trust, to behave independently, and to have similar failure modes, is over simplified. Thus, there is a need for a mechanism that automatically and efficiently selects replica nodes from a large number of available hosts with varying capabilities and trust levels. In this paper we present an algorithm to handle replica node selection either for new replica groups or to replace failed replicas in a peer-to-peer storage system. We show through simulation that our algorithm maintains the node inter-connection topology minimizing the cost of recovery from a failed replica, measured by the number of nodes affected by the failure and the number of inter-node messages

Recent work has demonstrated a peer-to-peer storage system that locates data objects using O(logN) messages by placing objects on nodes according to pseudo-randomly chosen IDs. While elegant, this approach constrains system functionality and flexibility: files are immutable, directories and symbolic names are not supported, data location is fixed, and access locality is not exploited. This paper presents Mammoth, a peer-to-peer hierarchical file system that, unlike alternative approaches, supports a traditional file-system API, allows files and directories to be stored on any node, and adapts storage location to exploit locality, balance load, and ensure availability. Our approach handles all coordination at the granularity of files instead of nodes. In effect, the nodes that store a particular file act as its server independently of other nodes in the system. The resulting system is highly available and robust to failure. Our experiments with our prototype have yielded good results, but an important question remains: how the system will perform on a massive scale. We discuss the key issues, some of which we have addressed and others that remain open.

Operating system structure is important; it leads to understandable, maintainable, 'pluggable' code. But despite our best efforts, some system elements have been difficult to structure. We propose a new analysis of this problem, and a new technology that can structure these elements. Aspect-oriented programming (AOP) (G. Kiczales et al., 1997) uses linguistic mechanisms to support the separation of crosscutting elements, or aspects of the system, from primary functionality. We have developed a proof-of-concept AOP implementation of prefetching in FreeBSD (www.cs.ubc.ca/labs/spl/aspects/aspectc.html). In our implementation, we have been able to modularize prefetching.

Layered architecture in operating system code is often compromised by execution path-specific customizations such as prefetching, page replacement and scheduling strategies. Pathspecific customizations are difficult to modularize in a layered architecture because they involve dynamic context passing and layer violations. Effectively they are vertically integrated slices through the layers. An initial experiment using an aspect-oriented programming language to refactor prefetching in the FreeBSD operating system kernel shows significant benefits, including easy (un)pluggability of prefetching modes, independent development of prefetching modes, and overall improved comprehensibility. Keywords aspect-oriented programming, software modularity, operating system design 1.

The benefits of Markov-based predictive prefetching have been largely overshadowed by the overhead required to produce high-quality predictions. While both theoretical and simulation results for prediction algorithms appear promising, substantial limitations exist in practice. This outcome can be partially attributed to the fact that practical implementations ultimately make compromises in order to reduce overhead. These compromises limit the level of algorithm complexity, the variety of access patterns and the granularity of trace data that the implementation supports. This paper describes the design and implementation of GMS-3P (Global Memory System with Parallel Predictive Prefetching), an operating system kernel extension that offloads prediction overhead to idle network nodes. GMS-3P builds on the GMS global memory system, which pages to and from remote workstation memory. In GMS-3P, the target node sends an online trace of an application's page faults to an idle node that is running a Markov-based prediction algorithm. The prediction node then uses GMS to prefetch pages to the target node from the memory of other workstations in the network. Our preliminary results show that predictive prefetching can reduce the remote-memory page fault time by 60% or more and that, by offloading prediction overhead to an idle node, GMS-3P can reduce this improved latency by between 24% and 44%, depending on the Markov model order.

Advances in network technology continue to improve the communication performance of workstation and PC clusters, making high-performance workstation-cluster computing increasingly viable. These hardware advances, however, are taxing traditional host-software network protocols to breaking point. A modern gigabit network can swamp a host's IO bus and processor, limiting communication performance and slowing computation unacceptably. Fortunately, host-programmable network processors used by these networks present a potential solution. Offloading selected host processing to these embedded network processors lowers host overhead and improves latency. This paper examines the use of embedded network processors to improve the performance of workstation-cluster global memory management. We have implemented a revised version of the GMS global memory system that eliminates host overhead by as much as 29% on active nodes and improves page fault latency by as much as 39%.

Modern file systems associate the deletion of a file with the immediate release of storage, and file writes with the irrevocable change of file contents. We argue that this behavior is a relic of the past, when disk storage was a scarce resource. Today, large cheap disks make it possible for the file system to protect valuable data from accidental delete or overwrite.This paper describes the design, implementation, and performance of the Elephant file system, which automatically retains all important versions of user files. Users name previous file versions by combining a traditional pathname with a time when the desired version of a file or directory existed. Storage in Elephant is managed by the system using file-grain user-specified retention policies. This approach contrasts with checkpointing file systems such as Plan-9, AFS, and WAFL that periodically generate efficient checkpoints of entire file systems and thus restrict retention to be guided by a single policy for all files within that file system.Elephant is implemented as a new Virtual File System in the FreeBSD kernel.

This paper presents cooperative prefetching and caching --- the use of network-wide global resources (memories, CPUs, and disks) to support prefetching and caching in the presence of hints of future demands. Cooperative prefetching and caching effectively unites disk-latency reduction techniques from three lines of research: prefetching algorithms, cluster-wide memory management, and parallel I/O. When used together, these techniques greatly increase the power of prefetching relative to a conventional (non-global-memory) system. We have designed and implemented PGMS, a cooperative prefetching and caching system, under the Digital Unix operating system running on a 1.28 Gb/sec Myrinet-connected cluster of DEC Alpha workstations. Our measurements and analysis show that by using available global resources, cooperative prefetching can obtain significant speedups for I/O-bound programs. For example, for a graphics rendering application, our system achieves a speedup of 4.9 over a non-prefetching version of the same program, and a 3.1-fold improvement over that program using local-disk prefetching alone.

New high-speed networks greatly encourage the use of network memory as a cache for virtual memory and file pages, thereby reducing the need for disk access. Because pages are the fundamental transfer and access units in remote memory systems, page size is a key performance factor. Recently, page sizes of modern processors have been increasing in order to provide more TLB coverage and amortize disk access costs. Unfortunately, for high-speed networks, small transfers are needed to provide low latency. This trend in page size is thus at odds with the use of network memory on high-speed networks.This paper studies the use of subpages as a means of reducing transfer size and latency in a remote-memory environment. Using trace-driven simulation, we show how and why subpages reduce latency and improve performance of programs using network memory. Our results show that memory-intensive applications execute up to 1.8 times faster when executing with 1K-byte subpages, when compared to the same applications using full 8K-byte pages in the global memory system. Those same applications using 1K-byte subpages execute up to 4 times faster than they would using the disk for backing store. Using a prototype implementation on the DEC Alpha and AN2 network, we demonstrate how subpages can reduce remote-memory fault time; e.g., our prototype is able to satisfy a fault on a 1K subpage stored in remote memory in 0.5 milliseconds, one third the time of a full page.

Advances in network and processor technology have greatly changed the communication and computational power of local-area workstation clusters.However, operating systems still treat workstation clusters as a collection of loosely-connected processors,where each workstation acts as an autonomous and independent agent.This operating system structure makes it difficult to exploit the characteristics of current clusters, such as low-latency communication, huge primary memories, and high-speed processors, in order to improve the performance of cluster applications.This paper describes the design and implementation of global memory management in a workstation cluster.Our objective is to use a single, unified, but distributed memory management algorithm at the lowest level of the operating system.By managing memory globally at this level, all system-and higher-level software, including VM, file systems, transaction systems, and user applications, can benefit from available cluster memory.We have implemented our algorithm in the OSF/1 operating system running on an ATM-connected cluster of DEC Alpha workstations.Our measurements show that on a suite of memory-intensive programs, our system improves performance by a factor of 1.5 to 3.5.We also show that our algorithm has a performance advantage over others that have been proposed in the past.

This article explores memory sharing and protection support in Opal, a single-address-space operating system designed for wide-address (64-bit) architectures. Opal threads execute within protection domains in a single shared virtual address space. Sharing is simplified, because addresses are context independent. There is no loss of protection, because addressability and access are independent; the right to access a segment is determined by the protection domain in which a thread executes. This model enables beneficial code-and data-sharing patterns that are currently prohibitive, due in part to the inherent restrictions of multiple address spaces, and in part to Unix programming style. We have designed and implemented an Opal prototype using the Mach 3.0 microkernel as a base. Our implementation demonstrates how a single-address-space structure can be supported alongside of other environments on a modern microkernel operating system, using modern wide-address architectures. This article justifies the Opal model and its goals for sharing and protection, presents the system and its abstractions, describes the prototype implementation, and reports experience with integrated applications.

Distributed Object Memory (DOM) is an abstraction that represents a distributed-memory system as a single shared container of language-level objects. The goal of DOM is to simplify programming of parallel applications for such systems. All accesses to shared memory are made relative to objects that reside in one or more node-local memories. For example, in Amber, a DOM system for a network of workstations, remote references are transparent at the language level and are implemented using either remote procedure call or object replication and migration. While DOM can greatly simplify distribution for many application classes, it is not well suited for all domains (parallel-scientific codes, in particular). To address the shortcomings of DOM for such domains, we introduce Versioned DOM (VDOM). In VDOM a version number is associated with each object. Multiple versions of objects can coexist and may be cached in local memories as needed to in- This work was supported in part by the Nationa...

Idle workstationsin a network represent a significant computing potential.In particular, their processing power can be used by parallel-distributed programs that treat the network as a loosely-coupled multiprocessor.Our experiments with Amber show that node reconfiguration can be implemented easily and efficiently in a runtime library.work speed will substantially reduce the cost