Appendix A
Glossary

Definitions are collected here for easy reference. In general, the accepted definitions for terms are used, although some terms are used in a more restricted sense than their usual interpretation. For example, scheduler always refers to a CPU scheduler.

adaptive application
A broad term for applications that can adjust their resource usage to compensate for variations in the level of service that they receive. Adaptation can be on a long time scale, for example, if an application can make use of different guarantees, or on a short time scale if an application sheds load in response to a transient shortage of a resource (for example, a video player application can drop frames to “catch up” after being starved).
admission control
A first-come first-serve resource allocation policy in which requests for guarantees are rejected if the resulting total utilization would exceed some threshold.
application
A user-level program designed to serve a specific purpose. Although applications may be implemented by multiple processes, in this dissertation it may be assumed that an application is implemented by a single process.
best effort
A resource allocation policy in which no request for scheduling is rejected. Consequently, no level of service is guaranteed.
bottom-half activity
Low-level operating system activity that has higher priority than, and is invisible to, the thread scheduler of a general-purpose operating system.
closed system
Describes a way of using an operating system characterized by knowledge of the set of applications that will be run, and their relative importances. This permits a priori schedulability analysis.
deadline
A time, usually externally imposed, by which a real-time computation must complete.
dispatch latency
The time between when a thread is scheduled and when it begins to execute. Theoretically, in a preemptive OS the dispatch latency for a high-priority thread should be very low. However, in practice preemptive OSs are non-preemptive at times; for example, while running an interrupt handler. The duration of the longest possible non-preemptive interval is said to be the worst-case dispatch latency of an OS.
earliest deadline first
(EDF) A scheduling algorithm that always runs the task with the earliest deadline. EDF is optimal in the sense that if any algorithm is able to schedule a task set, EDF will be able to schedule it.
enforcement
The mechanism by which isolation and guarantees are implemented. By enforcing limits on the CPU utilization of one application, processor time can be guaranteed to other applications.
general-purpose operating system
(GPOS) An operating system designed to meet a variety of goals, including protection between users and applications, fast response time for interactive applications, high throughput for batch and server applications, and high overall resource utilization. Unix and Unix-like operating systems are general-purpose operating systems, as are members of the Microsoft Windows family.
graceful degradation
Characterizes an application whose utility decreases smoothly, rather than sharply, when it receives insufficient CPU time. The opposite is non-graceful degradation, which characterizes applications that produce little or no value when their full requirements are not met.
guarantee
In general, a contract between the operating system and a resource consumer (thread, application, user, etc.) promising that the consumer will receive a guaranteed level of service with respect to some resource for the duration of the reservation. In this dissertation the resource being guaranteed is always CPU time. Guarantees are considered to be long-lived entities (i.e. lasting for seconds, minutes, or longer) when compared to the amount of time between scheduling decisions (i.e. milliseconds).
hard real-time system
Characterization of a system where meeting application deadlines is the primary metric for success.
hard real-time task
A task that loses all value (or generates negative value) if it is not completed by its deadline.
hierarchical scheduling
A generalization of scheduling in which schedulable entities may themselves be schedulers.
HLS
Abbreviation for Hierarchical Loadable Schedulers. A general term for the scheduling architecture presented in this dissertation.
HSI
Abbreviation for hierarchical scheduler infrastructure. A software library implemented as part of an operating system kernel that allows a hierarchy of schedulers to allocate CPU time. An important part of the HLS architecture.
isolation
An application is isolated from other applications if it is guaranteed to receive a certain level of service regardless of the behavior of other applications.
loadable scheduler
An implementation of a scheduler that can be dynamically loaded into an operating system kernel, where instances of it may become part of a scheduling hierarchy.
monolithic scheduler
A scheduling algorithm that is not implemented in a hierarchical way. Although monolithic schedulers lack flexibility, they are equivalent to hierarchical schedulers in the sense that every scheduling hierarchy could also be implemented as a monolithic scheduler.
multimedia operating system
An operating system that supports multimedia applications. The connotation is that applications are soft real-time and that the system is an open system. Most multimedia operating systems are general-purpose operating systems that have been extended to better support soft real-time applications. A few operating systems, such as BeOS, were specifically designed to support multimedia.
multimedia
Literally, the class of applications that brings together different media; for example, sound, still images, video, and text. Colloquially (and in this dissertation) multimedia refers to applications that perform ongoing computations to handle audio, video, or other streaming data. Multimedia applications are often soft real-time applications.
multi-threaded application
An application that is structured as a group of cooperating threads. For example, a video player application might have a thread for each of the following jobs: reading data from disk, decoding data, displaying frames of decoded data to the screen, and updating the user interface.
non-preemptive scheduler
A scheduler that may switch contexts only when a thread explicitly yields the processor.
open system
Describes a way of using an operating system that is characterized by a lack of advance knowledge about either the set of applications that will be run or their relative importances to the user or users. General-purpose operating systems are often used as open systems, meaning that users are free to install and run a new application at any time, with the expectation that all running applications will work properly as long as no resource (for example, memory, disk bandwidth, or CPU bandwidth) is oversubscribed.
Pentium timestamp counter
A counter present on Pentium-class x86 processors that stores the number of cycles since the machine was turned on, as a 64-bit integer. It can be efficiently read using the rdtsc instruction. On a 500 MHz machine, for example, the timestamp counter has a resolution of 2 ns.
period
The rate at which a real-time application requires computations to be performed. In the general case deadlines do not need to be equal to period boundaries. However, for multimedia applications it is usually the case that they are.
preemptible operating system
An operating system that may preempt a thread even when it is executing in the kernel. Solaris, BeOS, and Windows 2000 are preemptible, but Linux, FreeBSD, and Windows 95/98/Me are not.
preemptive operating system
An operating system whose scheduler is preemptive. Nearly all general-purpose operating systems are preemptive (as of version 9, the Macintosh OS is not preemptive).
preemptive scheduler
A scheduler that may switch between threads at any time.
priority inheritance
An algorithm that eliminates some classes of priority inversions  [76].
priority inversion
The condition in which a high-priority thread is kept from running by a low-priority thread. For example, priority inversion occurs when a low-priority thread is executing inside of a critical section and a high-priority thread is waiting to enter the critical section. If a medium-priority thread preempts the low-priority thread (while still inside of the critical section), the result is unbounded priority inversion--the low- and medium-priority threads can indefinitely prevent the high-priority thread from running.
processor affinity
A scheduling heuristic that attempts to keep from moving threads between processors on a multiprocessor to avoid incurring the cost of moving the thread’s working set between processor caches.
rate monotonic
(RM) A scheduling algorithm that assigns priorities to periodic tasks in order of increasing period length. RM is optimal among static-priority scheduling algorithms in the sense that if any static-priority scheduler can schedule a task set without missing deadlines, then RM can also.
real-time operating system
An operating system designed to support real-time tasks. The connotation is that the applications are hard real-time and that the system is not an open system.
real-time
The class of computations whose correctness depends not only on whether the result is the correct one, but also on the time at which the result is delivered. Real-time applications are those that perform any real-time computations.
resource management
A broad term, most often used to describe resource allocation policies more sophisticated than admission control or best effort.
resource manager
A software entity that performs resource management.
scheduler
Either an algorithm or an implementation of an algorithm that multiplexes a resource among different entities that all require access to the resource. In this dissertation scheduler and CPU scheduler are used synonymously.
schedulability analysis
The process of deciding whether or not a scheduler can schedule a particular set of tasks without missing any deadlines. Schedulability analysis is often quite simple; for example, in the most restricted case the schedulability of a task set by an EDF scheduler may be performed by summing up the utilizations of all tasks: if the total is less than or equal to one the task set is feasible, otherwise it is infeasible. Schedulability analysis for complex task sets, particularly on multiprocessors, can be difficult or intractable.
scheduling hierarchy
A tree (or directed acyclic graph) of schedulers. Besides the root scheduler, every scheduler in the hierarchy has one (and occasionally, more than one) parent--the scheduler(s) adjacent to the scheduler in the direction of the root of the scheduling hierarchy. Each scheduler that is not a leaf scheduler has one or more child schedulers--schedulers that are adjacent in the direction away from the root.
server call
A remote procedure call (RPC) based mechanism for providing an operating system service to a thread.
soft real-time system
Characterization of a system designed to support soft real-time tasks. The implication is that other system design goals (such as achieving high average throughput) may be as important, or more important, than meeting application deadlines.
soft real-time task
A task that has no fixed deadline or that retains some value after its deadline has passed. For example, interactive applications are soft real-time: the user may become increasingly irritated as the application fails to respond, but there is no clearly defined time at which the application loses all value.
stolen time
Time that is “stolen” from a user-level application by bottom-half operating system activity such as interrupt handlers or deferred procedure calls. The time is stolen because, in most general-purpose operating systems, it is invisible to the scheduler and therefore not accounted for.
system call
A coroutine-based mechanism for providing an operating system service to a thread. In a preemptible operating system it is irrelevant to the scheduler whether a thread is executing a system call or not.
task
A single instance of a real-time computation that must complete by a certain time. A real-time application may be comprised of several threads, each of which may perform many tasks. Also, in the context of real-time scheduling theory, “task” is often used to refer to an entity with real-time requirements.
thread
A flow of control. Kernel threads are supported by the operating system, while user-level threads are implemented outside of the kernel. In this dissertation all threads are assumed to be kernel threads.
usage scenario
The way a particular computer is used, viewed at a high level. Example usage scenarios include: supporting interactive and multimedia applications for a single user, serving web pages, or supporting interactive applications for more than one user.
utility
The subjective benefit generated by an application, running at a particular time, to a particular user. Synonymous with value.
utilization
The fraction of a resource’s total capacity that is being used.