dPool: A Reusable Scalable Data Structure for Factored Operating Systems
Speaker: David Wentzlaff , CAG-CSAIL
Date: August 31 2011
Time: 2:30PM to 4:30PM
Location: Kiva, 32-G449
Contact: Cree Bruins, 617-253-2629, cbruins@csail.mit.edu
Relevant URL:
ABSTRACT:
Future computer architectures will likely exhibit increased parallelism through the addition of more processor cores. This thesis work takes place in the context of Factored Operating Systems which leverage distributed system ideas to increase the scalability of multicore processor operating systems. fos, a Factored Operating System, explores a new design point for operating systems where traditional low-level operating system services are fine-grain parallelized while internally only using explicit message passing for communication. fos factors an operating system first by system service and then further parallelizes inside of the system service by splitting the service into a fleet of servers which communicate via messaging. Constructing parallel low-level operating system services which only internally use messaging is challenging because shared resources must be partitioned across servers and the servers must provide scalable performance when met with uneven demand.
In order to enable the construction of fos system servers, this thesis proposes splitting fos system servers into their core server functionality and Reusable Scalable Data Structures (RSDs). RSDs are generic data structure libraries which provide scalable concurrent access to shared state across multiple fos system servers while internally only using message passing for communication. RSDs encapsulate the complexity of managing shared state while providing a simple interface. RSDs also save programmer effort as they are reusable across multiple server fleets. To illustrate the RSD ideas, this thesis presents the dPool Reusable Scalable Data Structure which provides parallel access to an unordered set of elements. dPool enables building parallel low-level OS servers which only use messaging and support partitioned and uneven access to a shared resource.
This thesis describes the dPool data structure, its design, different implementations, and interfaces. The dPool data structure is shown to achieve good scalability across even and uneven workloads. dPool is reused in multiple fos service fleets. Through dPool, this thesis shows that it is possible to split fos system servers into Reusable Scalable Data Structures and core service functionality. This thesis shows that common parallel and distributed programming techniques apply to the creation of dPool and that background threads within a dPool can increase performance. Finally, this thesis evaluates different dPool implementations and demonstrates that intelligently pushing elements between dPool parts can increase scalability.
See other events that are part of
See other events happening in August 2011
