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.
- 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).
- A first-come first-serve resource
allocation policy in which requests for guarantees are rejected if
the resulting total utilization would exceed some threshold.
- 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.
- A resource allocation policy in which no
request for scheduling is rejected. Consequently, no level of
service is guaranteed.
- Low-level operating system activity that
has higher priority than, and is invisible to, the thread scheduler
of a general-purpose operating 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
- A time, usually externally imposed, by
which a real-time computation must complete.
- 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
- (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.
- 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
- (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
- 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.
- 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
- hard real-time
- Characterization of a system where meeting
application deadlines is the primary metric for success.
- hard real-time
- A task that loses all value (or generates
negative value) if it is not completed by its deadline.
- A generalization of scheduling in which
schedulable entities may themselves be schedulers.
- Abbreviation for Hierarchical Loadable
Schedulers. A general term for the scheduling architecture
presented in this dissertation.
- 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.
- 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.
- 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.
- 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
- 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.
- 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.
- 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.
- A scheduler that may switch contexts only
when a thread explicitly yields the processor.
- 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
- Pentium timestamp
- 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
- 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
- preemptible operating
- 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
- An operating system whose scheduler is
preemptive. Nearly all general-purpose operating systems are
preemptive (as of version 9, the Macintosh OS is not
- A scheduler that may switch between threads
at any time.
- An algorithm that eliminates some classes
of priority inversions .
- 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.
- 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.
- (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
- 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.
- 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
- A broad term, most often used to describe
resource allocation policies more sophisticated than admission
control or best effort.
- A software entity that performs resource
- 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.
- 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.
- 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
- A remote procedure call (RPC) based
mechanism for providing an operating system service to a
- soft real-time
- 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
- soft real-time
- 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
- 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.
- 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.
- 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
- 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
- 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
- The subjective benefit generated by an
application, running at a particular time, to a particular user.
Synonymous with value.
- The fraction of a resource’s total
capacity that is being used.