Speculative execution within a commodity operating system.
Jason Flinn, Edmund B. Nightingale · Deep Blue (University of Michigan) · 2007
Commodity operating systems are traditionally tuned to improve performance, but in the pursuit of faster operation, reliability is sacrificed. Therefore, common abstractions, such as asynchronous file system I/O, explicitly relax reliability guarantees (e.g., delay writes to disk by 30 seconds) in favor of better performance. The main concern of this thesis is to mitigate the performance/reliability tradeoff through the use of a general purpose mechanism, called Speculator, which implements multi-process speculative execution within the Linux kernel. Speculator is a tool for masking the latency of predictable, but slow, operations. It allows a critical, synchronous operation to be executed asynchronously. Thus, additional work is completed without sacrificing the benefits (i.e., the guarantees) of synchronous execution. Support for speculative execution is implemented using three techniques. First, Speculator tracks and propagates the causal dependencies (via speculations) of a process via inter-process communication mechanisms such as files, pipes, FIFOS and UNIX sockets. Second, Speculator buffers the output of speculative processes until the speculations upon which the output depends have been committed. Finally, should a speculation fail, Speculator can roll back each dependent kernel object and process. This dissertation shows that Speculator can be used to create new abstractions that replace synchronous abstractions within local file systems, distributed file systems and runtime security checks. Abstractions built using Speculator allow a pro grammer to develop applications for a reliable, synchronous abstraction while obtaining the performance of one that is asynchronous. Specifically, by using Speculator to build new abstractions, I can virtually eliminate the overhead of synchronous I/O for local file systems, build a distributed file system that provides strong consistency and safety guarantees while out-performing existing systems with weaker guarantees, and accelerate slow, sequential runtime security checks by parallelizing them across many cores. Finally, the speculative abstractions that I have built do not require application modification; the benefits of speculation are transparent.