General purpose operating systems have traditionally provided, and continue to provide, priority-based dynamic scheduling providing "generally good" system performance because it was a scheduling model that worked, or could be made to work, for a wide range of applications. Applications with specialized semantics have existed for many years, but were traditionally supported by expensive specialized systems. Real-Time systems are historically among the most common sytems with specialized semantics. Over the last several years, a variety of factors have called into question whether the traditional scheduler can continue to provide adequate support for the full range of next generation applications, and the range of combinations of applications which must coexist on a given computer system. Further, the power and low cost of commercial-off-the-shelf (COTS) computer systems hardware and software makes it increasingly attractive to support a wide range of applications with a wide range of semantics, thus causing a semantic explosion which challenges the capabilities of current systems.
Semantics of individual applications may be best described using progress, priority, or real-time semantics. Allocation of system resources may be best described using fixed priority, CPU share, physical partitioning, or time-division semantics. Researchers continue to experiment with a variety of scheduling algorithms for a wide range of purposes but system designers wishing to use research results have a high barrier to entry because changing system scheduling semantics is a difficult and time consuming project. Most of the work in specialized application semantics has investigated how to map them onto the priority model provided by most computer system precisely because it was common and perceived as difficult or impossible to change, and because no better way to have multiple application semantics coexist seemed possible.
The Kernel/User Systems Programming (KUSP) Project at the University of Kansas has worked on a number of projects over the years, but all were focussed on increasing the precision with which behavior of computations Linux can be controlled and measured. The Group Scheduling (GS) subsystem of KUSP is explicitly designed to permit implementation of a wide range of scheduling semantics as Scheduling Decision Functions (SDF) which can be plugged into the GS framework and organized into a hierarchy of groups, which specifies the scheduling semantics of the system as a whole. Individual groups of threads can represent computations, system service pools, or anything the developer desires. Each group can have its own SDF controlling selection among group members at scheduling time, and the ability to have groups be members of others groups permits the specification of a scheduling hierarchy for the whole system. Integration of GS with kernel concurrency control (rt-mutex), called proxy execution, permits customization of the other significant influence on computation behavior in the system beyond the scheduler.
The GS framework can reduce the cost of implementing customized programming models for individual applications, to reduce the cost of researchers wishing to experiment with specific scheudling algorithms, and to increase the precision with which the performance of different algorithms can be compared by providing a common implementation and testing framework. This paper presents the GS framework and how it can be used to implement a wide range of programming models.
Download paper as pdf file