GS Overview

Introduction

The Problem

Systems are emerging upon which applications with varied behavioral semantics run. Single systems capable of supporting co-existing application semantics offer advantages over specialized systems created for specific applications by simplifying system management, and reducing redundant computing resources. For example, multi-purpose systems may be used simultaneously for web-browing and multimedia, or in a laboratory setting a single system may be used for a wide variety of scentific applications, each requiring their own set of unique semantics. The trend of moving away from specialized systems to general purpose systems capable of supporting a variety of applicatino semantics is driven by the cost and simplicity of managing fewer systems. But as the set of co-existing behaviors on a system continues to grow, the use of shared system resources must be controlled through a unified system policy.

Software developers express the semantics of their applications through programming models using semantic mappings. A semantic mapping is a function which expresses one semantics in terms of another. A programming model expresses a semantic mapping through scheduling parameters, as well as other components of the model, such as concurrency control policy. For instance, the Linux kernel implements a hard-wired, static-priority scheduler, and exports a priority based programming model. Thus, developers using Linux are required to express the behavior of their software by mapping application smeantics onto a priority based scheduling model, regardless of the difficulty and precision involved in creating the mapping. It would be beneficial if developers were able to easily create their own programming models using clear semantic mapping functions.

Group Scheduling

Group Scheduling is a hierarchical scheduling framework used for creating thread schedulers with arbitrary semantics, by allowing applications to represent scheduling information directly within the scheduler. The direct representation of scheduling information allows a developer to choose the level at which semantic mappings are expressed. For example, Group Scheduling has been used to express progress-based semantics for a multi-tier, pipeline-based processing application, by allowing threads to publish their progress directly into the scheduler. Achieving these semantics using using only a priority-based programming model is significantly more challenging, and error prone. While Group Scheduling allows developers to create arbitrary scheduling semantics, supporting co-existing, arbitrary semantics is difficult due to the policy conflicts that arise as computations interact through their use of shared system resources.

Interaction Channels

In general, access to a shared resource is controlled by affecting the runnabilty of computations. Associated with each shared resource is thus a semantics specifying the rules by which access is granted, in terms of computation runnability. We use the term interaction channel to refer to the general idea that application interact through shared resources, and that this interaction has an associated semantics affecting the runnability of computations. Because the semantics of interaction channels affect the runnability of computations, they in turn can affect the abiilty of the system to construct schedules obeying the behavioral constraints of computations. In order to support arbitrary programming models we must be able to specify arbitrary scheduling semantics. Thus, the semantics of all system components which affect scheduability, including interaction channels, must be integrated with scheduling. While Group Scheduling facilitates the creation of arbitrary scheduling semantics, this paper presents a general solution to the problem of resolving scheduling policy conflicts for a common interaction channel, the binary sempaphore. In doing so, we successfully integrate the semantics of the binary semaphore interaction channel with the Group Scheduling framework in support of arbitrary programming models.