Making Paths Explicit in the Scout Operating System David Mosberger and Larry L Peterson TR 96 05 Abstract This paper makes a case for paths as an explicit abstraction in operating system design Paths provide a unifying infrastructure for several OS mechanisms that have been introduced in the last several years including fbufs integrated layer processing packet classifiers code specialization and migrating threads This paper articulates the potential advantages of a path based OS structure describes the specific path architecture implemented in the Scout OS and demonstrates the advantages in a particular application domain receiving decoding and displaying MPEG compressed video Department of Computer Science The University of Arizona Tucson AZ 85721 1 Introduction Layering is a fundamental structuring technique with a long history in system design From early work on layered operating systems and network architectures HFC76 Zim80 to more recent advances in stackable systems Rit84 HP91 HP94 RBF 95 layering has played a central role in managing complexity isolating failure and enhancing configurability This paper describes a complementary but equally fundamental structuring technique which we call paths Whereas layering is typically used to manage complexity paths are applied to layered systems to improve their performance and to solve problems that require global context Although paths are easy to understand on the surface a path is a vertical slice through a multi layered system a concrete realization of the idea is surprisingly elusive We therefore develop a working definition of paths in an incremental fashion First consider that the term path is well entrenched in our vocabulary For example we often refer to the fast path or the critical path through a system implying that the most commonly executed sequence of instructions have been optimized As another example we sometimes talk about optimizing the end to end path meaning we are focused on the global performance of the system e g from I O source to sink rather than on the local performance of a single component As a final example we sometimes distinguish between a system s control path and its data path with the former being more relevant to latency and the latter more concerned with throughput Paths can also be loosely understood by considering specific OS mechanisms that have been proposed over the last few years Consider the following examples Fbufs DP93 are a path oriented buffer management mechanism designed to efficiently move data across a sequence of protection domains Fbufs depend on being able to identify the path through the system over which the data will flow Integrated layer processing ILP CT90 AP93 is a technique for fusing the data manipulation loops of multiple protocol layers It depends on knowing exactly what sequence of protocol modules a network packet will traverse Packet classifiers YBMM93 MJ93 BGP 94 distinguish among incoming network packets based on certain fields found in their headers In a sense a packet classifier pre computes the path that a given message will follow Specialization is sometimes used to optimize common path code sequences PAB 95 MPBO96 Specialization in turn depends on the existence of invariants that constrain the path through the code that is likely to be executed Spring defines a shuttle HK93 which is an environment that allows a thread to migrate across a sequence of protection domains others have defined similar mechanisms FL94 Like the previous examples such mechanisms recognize that programs often follow the same path through the system more than once and so establish some state that subsequent invocations can exploit Note that while all of these mechanisms either support paths or depend on the existence of paths none of them explicitly define what a path is In other words while the idea of a path running through a layered system is widely recognized to date paths have only been implicitly defined The main contribution of this paper is to show how paths are explicitly implemented in the Scout operating system MMO 94 and to demonstrate some of the advantages of this implementation by means of an example application Scout is an experimental framework that provides the means to easily produce small highly efficient stand alone kernels that are targeted at a particular I O intensive application domain Scout is designed for both non realtime and soft realtime applications A description of Scout with a focus on its architecture for paths is given in Section 3 The demonstration application which involves receiving MPEG compressed video over a network and then decoding and displaying it is described in Section 4 Although layering does not imply multiple protection domains systems often impose hardware enforced protection at layer boundaries 1 2 A Case for Paths The claim is that paths are a fundamental abstraction in system design one that provides a unifying framework for many of the mechanisms identified in the introduction Before describing how paths are implemented in Scout however this section first introduces an abstract model for paths and argues why paths are a good idea in principle A later section 4 illustrates some of these advantages in the context of a concrete example Consider a layered system that consists of a collection of modules that depend on each other in a well defined way We call these modules routers for reasons that will become clear in a moment but for now think of each router as implementing a certain functionality e g the IP protocol or MPEG decompression and having a well defined interface These routers are then connected into a graph to provide exactly the functionality required for a given application domain Paths are dynamic entities They are created and destroyed at runtime as a result of various events such as the arrival of a connection request packet on a network adapter a user hitting the return key or a timeout expiring A path traverses a sequence of routers that are connected in the router graph Figure 1 illustrates an example router graph with two distinct paths running through it think of each path as corresponding to a separate network connection for example Figure 1 Two Paths Through a Router Graph A path is created incrementally It starts at a source router and is specified with a set of invariants that will be true for all data that flows over the path The router uses these invariants to make a routing decision hence the name router if
View Full Document
Unlocking...