Today's dynamic language systems have grown to include features that resemble features of operating systems. It may be possible to improve on both by unifying a language system with an operating system. Complete unification does not appear possible in the near-term, so an intermediate system is described. This intermediate system uses a common call graph to allow components in arbitrary languages to interact as easily as components in the same language. Potential benefits of such a system include significant improvements in interoperability, improved reusability and backward compatibility, simplification of debugging and some administrative tasks, and distribution over a cluster without any changes to application code.

In this thesis, we investigate the applicability of the process algebraic formal method Communicating Sequential Processes (CSP) [Hoa85] to the development and analysis of safetycritical systems. We also investigate how these tasks might be aided by mechanical verification, which is provided in the form of the proof tool Failures-Divergences Refinement (FDR) [Ros94]. Initially, we build upon the work of [RWW94, Ros95], in which CSP treatments of the security property of non-interference are described. We use one such formulation to define a property called protection, which unifies our views of safety and security. As well as applying protection to the analysis of safety-critical systems, we develop a proof system for this property, which in conjunction with the opportunity for automated analysis provided by FDR, enables us to apply the approach to problems of a sizable complexity. We then describe how FDR can be applied to the analysis of mutual exclusion, which is a specific form of non-interference. We investigate a number of well-known solutions to the problem, and illustrate how such mutual exclusion algorithms can be interpreted as CSP processes and verified with FDR. Furthermore, we develop a means of verifying the faulttolerance of such algorithms in terms of protection. In turn, mutual exclusion is used to describe safety properties of geographic data associated with Solid State Interlocking (SSI) railway signalling systems. We show how FDR can be used to describe these properties and model interlocking databases. The CSP approach to compositionality allows us to decompose such models, thus reducing the complexity of analysing safety invariants of SSI geographic data. As such, we describe how the mechanical verification of Solid State Interlocking geographic data, which was previously considered to be an intractable problem for the current generation of mechanical verification tools, is computationally feasible using FDR. Thus, the goals of this thesis are twofold. The first goal is to establish a formal encapsulation of a theory of safety-critical systems based upon the relationship which exists between safety and security. The second goal is to establish that CSP, together with FDR, can be applied to the modelling of Solid State Interlocking geographic databases. Furthermore, we shall attempt to demonstrate that such modelling can scale up to large-scale systems.

Modern offices are crowded with personal computers. While studies have shown these to be idle most of the time, they remain powered, consuming up to 60% of their peak power. Hardware based solutions engendered by PC vendors (e.g., low power states, Wake-on-LAN) have proven unsuccessful because, in spite of user inactivity, these machines often need to remain network active in support of background applications that maintain network presence. Recent solutions have been proposed that perform consolidation of idle desktop virtual machines. However, desktop VMs are often large requiring gigabytes of memory. Consolidating such VMs, creates large network transfers lasting in the order of minutes, and utilizes server memory inefficiently. When multiple VMs migrate simultaneously, each VM’s experienced migration latency grows, and this limits the use of VM consolidation to environments in which only a few daily migrations are expected per VM. This thesis introduces partial VM migration, an approach that transparently migrates only the working set of an idle VM, by migrating memory pages on-demand. It creates a partial replica of the desktop VM on the consolidation server by copying only VM metadata, and transferring pages to the server, as the VM accesses them. This approach places desktop PCs in low power state when inactive and resumes them to running state when pages are needed by the VM running on the consolidation server. Jettison, our software prototype of partial VM migration for off-the-shelf PCs, can deliver 78% to 91% energy savings during idle periods lasting more than an hour, while providing low migration latencies of about 4 seconds, and migrating minimal state that is under an order of magnitude of the VM’s memory footprint. In shorter idle periods of up to thirty minutes, Jettison delivers savings of 7% to 31%. We present two approaches that increase energy savings attained with partial VM migration, especially in short idle periods. The first, Context-Aware Selective Resume, expedites PC resume and suspend cycle times by supplying a context identifier at desktop resume, and initializing only devices and code that are relevant to the context. CAESAR, the Context-Aware Selective Resume framework, enables applications to register context vectors that are invoked when the desktop is resumed with matching context. CAESAR increases energy savings in short periods of five minutes to an hour by up to 66%. The second approach, the low power page cache, embeds network accessible low power hardware in the PC, to enable serving of pages to the consolidation server, while the PC is in low power state. We show that Oasis, our prototype page cache, addresses the shortcomings of energy-oriented on-demand page migration by increasing energy savings, especially during short idle periods. In periods of up to an hour, Oasis increases savings by up to twenty times.

Modern offices are crowded with personal computers. While studies have shown these to be idle most of the time, they remain powered, consuming up to 60% of their peak power. Hardware based solutions engendered by PC vendors (e.g., low power states, Wake-on-LAN) have proven unsuccessful because, in spite of user inactivity, these machines often need to remain network active in support of background applications that maintain network presence. Recent solutions have been proposed that perform consolidation of idle desktop virtual machines. However, desktop VMs are often large requiring gigabytes of memory. Consolidating such VMs, creates large network transfers lasting in the order of minutes, and utilizes server memory inefficiently. When multiple VMs migrate simultaneously, each VM’s experienced migration latency grows, and this limits the use of VM consolidation to environments in which only a few daily migrations are expected per VM. This thesis introduces partial VM migration, an approach that transparently migrates only the working set of an idle VM, by migrating memory pages on-demand. It creates a partial replica of the desktop VM on the consolidation server by copying only VM metadata, and transferring pages to the server, as the VM accesses them. This approach places desktop PCs in low power state when inactive and resumes them to running state when pages are needed by the VM running on the consolidation server. Jettison, our software prototype of partial VM migration for off-the-shelf PCs, can deliver 78% to 91% energy savings during idle periods lasting more than an hour, while providing low migration latencies of about 4 seconds, and migrating minimal state that is under an order of magnitude of the VM’s memory footprint. In shorter idle periods of up to thirty minutes, Jettison delivers savings of 7% to 31%. We present two approaches that increase energy savings attained with partial VM migration, especially in short idle periods. The first, Context-Aware Selective Resume, expedites PC resume and suspend cycle times by supplying a context identifier at desktop resume, and initializing only devices and code that are relevant to the context. CAESAR, the Context-Aware Selective Resume framework, enables applications to register context vectors that are invoked when the desktop is resumed with matching context. CAESAR increases energy savings in short periods of five minutes to an hour by up to 66%. The second approach, the low power page cache, embeds network accessible low power hardware in the PC, to enable serving of pages to the consolidation server, while the PC is in low power state. We show that Oasis, our prototype page cache, addresses the shortcomings of energy-oriented on-demand page migration by increasing energy savings, especially during short idle periods. In periods of up to an hour, Oasis increases savings by up to twenty times.

Kernel patches are frequently released to fix security vulnerabilities and bugs. However, users and system administrators often delay installing these updates because they require a system reboot, which results in disruption of service and the loss of application state. Unfortunately, the longer an out-of-date system remains operational, the higher is the likelihood of a system being exploited. Approaches, such as dynamic patching and hot swapping, have been proposed for updating the kernel. All of them either limit the types of updates that are supported, or require significant programming effort to manage. We have designed a system that checkpoints application-visible state, updates the kernel, and restores the application state. By checkpointing high-level state, our system no longer depends on the precise implementation of a patch and can apply all backward compatible patches. The results show that updates to major kernel releases can be applied with minimal changes.

Patches to modern operating systems, including bug fixes and security updates, and the reboots and downtime they require, cause tremendous problems for system users and administrators. The aim of this research is to develop a model for dynamic update of operating systems, allowing a system to be patched without the need for a reboot or other service interruption. In this work, a model for dynamic update based on operating system modularity is developed and evaluated using a prototype implementation for the K42 operating system. The prototype is able to update kernel code and data structures, even when the interfaces between kernel modules change. When applying an update, at no point is the system's entire execution blocked, and there is no additional overhead after an update has been applied. The base runtime overhead is also very low. An analysis of the K42 revision history shows that approximately 79% of past performance and bug-fix changes to K42 could be converted to dynamic updates, and the proportion would be even higher if the changes were being developed for dynamic update. The model also extends to other systems such as Linux and BSD, that although structured modularly, are not strictly object-oriented like K42. The experience with this approach shows that dynamic update for operating systems is feasible given a sufficiently-modular system structure, allows maintenance patches and updates to be applied without disruption, and need not constrain system performance.

Energy is a critical resource in all types of computing systems from servers, where energy costs dominate data centre expenses and carbon footprints, to embedded systems, where the system's battery life limits the device's functionality. In their efforts to reduce the energy use of these system's hardware manufacturers have implemented features which allow a reduced energy consumption under software control. This thesis shows that managing these settings is a more complex problem than previously considered. Where much (but not all) of the previous academic research investigates unrealistic scenarios, this thesis presents a solution to managing the power on varying hardware. Instead of making unrealistic assumptions, we extract a model from empirical data and characterise that model. Our models estimate the effect of different power management settings on the behaviour of the hardware platform, taking into account the workload, platform and environmental characteristics, but without any kind of a-priori knowledge of the specific workloads being run. These models encapsulate a system's knowledge of the platform. We also developed a \emph{generalised energy-delay} policy which allows us to quickly express the instantaneous importance of both performance and energy to the system. It allows us to select a power management strategy from a number of options. This thesis shows, by evaluation on a number of platforms, that our implementation, Koala, can accurately meet energy and performance goals. In some cases, our system saves 26\% of the system-level energy required for a task, while losing only 1\% performance. This is nearly 46\% of the dynamic energy. Taking advantage of all energy-saving opportunities requires detailed platform, workload and environmental information. Given this knowledge, we reach the exciting conclusion that near optimal power management is possible on real operating systems, with real platforms and real workloads.

This dissertation is dedicated to the problem of device driver reliability. Software defects in device drivers constitute the biggest source of failure in operating systems, causing significant damage through downtime and data loss. Previous research on driver reliability has concentrated on detecting and mitigating defects in existing drivers using static analysis or runtime isolation. In contrast, this dissertation presents an approach to reducing the number of defects through an improved device driver architecture and development process. In analysing factors that contribute to driver complexity and induce errors, I show that a large proportion of errors are due to two key shortcomings in the device-driver architecture enforced by current operating systems: poorly-defined communication protocols between drivers and the operating system, which confuse developers and lead to protocol violations, and a multithreaded model of computation, which leads to numerous race conditions and deadlocks. To address the first shortcoming, I propose to describe driver protocols using a formal, state-machine based, language, which avoids confusion and ambiguity and helps driver writers implement correct behaviour. The second issue is addressed by abandoning multithreading in drivers in favour of a more disciplined event-driven model of computation, which eliminates most concurrency-related faults. These improvements reduce the number of defects without radically changing the way drivers are developed. In order to further reduce the impact of human error on driver reliability, I propose to automate the driver development process by synthesising the implementation of a driver from the combination of three formal specifications: a device-class specification that describes common properties of a class of similar devices, a device specification that describes a concrete representative of the class, and an operating system interface specification that describes the communication protocol between the driver and the operating system. This approach allows those with the most appropriate skills and knowledge to develop specifications: device specifications are developed by device manufacturers, operating system specifications by the operating system designers. The device-class specification is the only one that requires understanding of both hardware and software-related issues. However writing such a specification is a one-off task that only needs to be completed once for a class of devices. This approach also facilitates the reuse of specifications: a single operating-system specification can be combined with many device specifications to synthesise drivers for multiple devices. Likewise, since device specifications are independent of any operating system, drivers for different systems can be synthesised from a single device specification. As a result, the likelihood of errors due to incorrect specifications is reduced because these specifications are shared by many drivers. I demonstrate that the proposed techniques can be incorporated into existing operating systems without sacrificing performance or functionality by presenting their implementation in Linux. This implementation allows drivers developed using these techniques to coexist with conventional Linux drivers, providing a gradual migration path to more reliable drivers.

Energy is a critical resource in all types of computing systems from servers, where energy costs dominate data centre expenses and carbon footprints, to embedded systems, where the system's battery life limits the device's functionality. In their efforts to reduce the energy use of these system's hardware manufacturers have implemented features which allow a reduced energy consumption under software control. This thesis shows that managing these settings is a more complex problem than previously considered. Where much (but not all) of the previous academic research investigates unrealistic scenarios, this thesis presents a solution to managing the power on varying hardware. Instead of making unrealistic assumptions, we extract a model from empirical data and characterise that model. Our models estimate the effect of different power management settings on the behaviour of the hardware platform, taking into account the workload, platform and environmental characteristics, but without any kind of a-priori knowledge of the specific workloads being run. These models encapsulate a system's knowledge of the platform. We also developed a \emph{generalised energy-delay} policy which allows us to quickly express the instantaneous importance of both performance and energy to the system. It allows us to select a power management strategy from a number of options. This thesis shows, by evaluation on a number of platforms, that our implementation, Koala, can accurately meet energy and performance goals. In some cases, our system saves 26\% of the system-level energy required for a task, while losing only 1\% performance. This is nearly 46\% of the dynamic energy. Taking advantage of all energy-saving opportunities requires detailed platform, workload and environmental information. Given this knowledge, we reach the exciting conclusion that near optimal power management is possible on real operating systems, with real platforms and real workloads.

Thesis (Ph. D.)--Ohio University, August, 1997. / Title from PDF t.p.