This chapter concludes the dissertation by summarizing its contributions and discussing some possible avenues for future work.
HLS is the first general, heterogeneous hierarchical scheduling system to be implemented in a general-purpose operating system. The thesis that this dissertation has supported is that extending a general-purpose operating system with general, heterogeneous hierarchical scheduling is feasible and useful.
The feasibility of HLS was demonstrated by
presenting a design of the hierarchical scheduler infrastructure
that is based on a novel extension of the virtual processor
abstraction that was developed for the work on scheduler activations [3],
and also by implementing it in the Windows 2000 kernel. Basic
mode-change operations such as moving a thread between schedulers,
creating and destroying a scheduler, and beginning and ending a CPU
reservation were shown to be fast, taking less than 40 
s on a 500 MHz Pentium
III. We also showed that although HLS increases the cost of a
context switch slightly, the performance penalty caused by a
context switch to a thread in terms of re-establishing its working
set in the processor cache can easily be two orders of magnitude
greater than the cost added by HLS.
The usefulness of HLS was established in the following ways. First, by surveying a number of scheduling behaviors that have been developed to support multimedia applications, and the diverse requirements of multimedia and other soft real-time applications, it was concluded that at least three types of scheduling behavior are useful: time-sharing scheduling for batch and interactive applications, CPU reservations with a precise granularity and minimum amount to support real-time applications whose value does not degrade gracefully, and best-effort real-time scheduling for applications whose value degrades gracefully. Second, using three application scenarios it was shown that different ways of using a general-purpose operating system can benefit from distinct types of scheduling. Third, it was shown that the guarantees provided by a broad class of multimedia scheduling algorithms can be reasoned about in a formal way, and a novel method was presented for verifying that scheduling hierarchies are guaranteed to be correct in the sense that application threads receive guaranteed scheduling behavior. Fourth, it was shown that a number of complex, idiomatic scheduling behaviors can be composed using small hierarchical schedulers as components. Fifth, the design of a user-level resource manager was presented in order to show that a resource manager can make good use of the flexible scheduling provided by HLS to enforce high-level policies about the allocation of CPU time. Finally, two novel schedulers were presented that can help increase application predictability when a general-purpose operating system steals CPU time from a running application.
The value provided by HLS is that it allows a computer running a general-purpose operating system to be used in situations where the inflexibility of the CPU scheduler had previously prevented it from being used. Rather than statically adding scheduling behaviors to the operating system, we have created a dynamic architecture for extending the scheduling subsystem, allowing future improvements in scheduling algorithms to be easily incorporated into the OS.
A useful area of further research in scheduler composition would be, for each existing real-time scheduler, to find the (provably) weakest guarantee that allows it to still provide the desired guarantees to its children. To do this it may be necessary to develop guarantee types other than the ones described in Chapter 5 , that are a better match for the scheduling semantics provided by particular real-time schedulers. It would be interesting to investigate the theoretical and practical differences between “static” guarantees like CPU reservations, whose scheduling behavior requires no information other than rate and granularity, and “dynamic” guarantees such as the uniformly slower processor, that require fine-grained information about deadlines in order to be useful.
There are many global computations over the scheduling hierarchy and set of running applications that would be desirable to perform. For example, when worst-case semaphore hold times are known, global schedulability analysis could be performed in the presence of synchronizing tasks. Also, it would be useful to be able to test arbitrary scheduling hierarchies for desirable global properties such as good processor affinity behavior and low overall expected context switches.
Since the HSI is a very general tool for building scheduling behaviors, it would be desirable to release it to other research groups, who could then spend more time developing and using interesting schedulers and less time understanding the internals of general-purpose operating systems or running schedulers in simulated operating systems.
A useful extension to the HSI would be to design a version that is compatible with medium- and large-sized multiprocessor machines where it is infeasible to serialize scheduling decisions across all processors. A straightforward space-sharing approach would be to have different scheduling hierarchies control processor allocation on disjoint subsets of the processor pool. Although scheduler operations within each hierarchy would be serialized, no synchronization across hierarchies would be required. To migrate a thread between hierarchies, it would suffice to unregister a thread from one hierarchy and register it with another. Extending the HLS scheduling model to support relaxed synchronization within a single scheduling hierarchy would be a more difficult task.
Although HLS lowers the barrier for implementing a new scheduler, writing a scheduler is still more difficult than it seems like it should be. It would be interesting to develop a restricted domain specific language for schedulers that, along with run-time support from the HSI, (1) ensures that each scheduler invocation terminates in a bounded (and short) amount of time, (2) prevents schedulers from leaking resources, (3) is type-safe, preventing schedulers from reading or writing forbidden memory areas, (4) ensures that schedulers obey the HLS protocol, (5) ensures that schedulers cannot divide by zero, generate a page fault, corrupt processor floating point state, or perform other destructive actions, and (6) validates or automates the tedious and error-prone updates to the states of virtual processors, ready queues, and other data structures. Perhaps model checking techniques, in addition to language- and system-based techniques, could be used to verify some of these properties, at least for schedulers with a small state space. The “holy grail” for a domain specific scheduler language would be for it to ensure that the scheduler actually provides the guarantees that it promises to provide. This, in combination with the properties listed above, could lead to provable scheduling behavior under weak assumptions (i.e., that the hardware is not faulty) rather than the strong assumptions that were presented in Section 5.1.3 . The Bossa framework [6] is addressing a number of these issues using a domain-specific language for writing schedulers.
The current implementation of the hierarchical scheduler infrastructure is a prototype, and there are many ways in which it could be improved. It should be profiled and optimized, in order to narrow or close the gap between the context switch time of the native Windows 2000 scheduler and a context switch within a single, well-implemented HLS scheduler. A solution to the problem of priority inversion would be a desirable feature for the HSI, as would a mechanism permitting schedulers to send notifications to user-level applications. Finally, a precisely settable interrupt mechanism would make Windows 2000 into a more viable real-time operating system for applications with deadlines on the order of a small number of milliseconds.
The obvious future work for the resource manager is to implement it. Beyond that, there are fertile grounds for future work in the areas of parameter estimation for real-time applications, especially those with data-dependent CPU requirements, and GUI-based resource control interfaces that end-users can understand and manipulate. Also, it would be useful to develop a better understanding of how to tune the degree of pessimism in resource reservations for applications in order to balance the requirements of high overall utilization and low deadline misses. Finally, it would be interesting and useful to develop rules for the resource manager that implement a number of complex scheduling behaviors, and to ensure that these complex behaviors compose correctly.
The augmented reservation schedulers can be viewed as a necessary evil: if general-purpose operating systems did not have the bad behavior of stealing time, augmented reservations would not be necessary. A useful project would be to move the Windows 2000 DPC mechanism into thread context, eliminating this source of stolen time. This project is ambitious because it would be difficult to avoid reducing the throughput of DPC-intensive workloads, and because scheduling DPCs begs the question of what their scheduling parameters are. In other words, if DPC threads are scheduled at the highest priority, then there is no advantage to scheduling them as threads. If they do not have the highest priority, then we must know for how long their execution can be delayed.