From: Gail Rahn (gail_at_screaminggeek.com)
Date: Wed Jan 28 2004 - 10:59:29 PST
Review of "Scheduler Activations" by Anderson, Bershad, Lazowska and Levy
The "Scheduler Activations" paper introduces a user-level thread-management
architecture that provides the performance benefits of kernel threads and
the flexibility of user threads. Threads, of greatly increasing importance
at the time of this paper, can be considered lightweight processes. They
selarate process execution from memory and are a significant performance
advantage over single-process program design.
In contemporary operating systems, both kernel-mode and user-mode threads
have been implemented poorly. User-level threads rely on thread-management
systems that can exhibit poor or incorrect behavior in the face of certain
OS activity patterns. Kernel threads always behave consistently, but
consistently too slow and heavy, even an order of magnitude slower than
user-level thread management. User-level threads have significant advantages
that must be preserved in an improved thread-management system. User threads
incur less cost than threads implemented in the kernel.
For the kernel to effectively support user-level thread management, the
kernel incurs the burden of supporting arbitrary threading features desired
by "reasonable applications". This is overhead best left out of an
operating system kernel. The kernel also perform thread-management operation
(block, resume, schedule) with no consideration of the user-level thread
state. This information could drive more relevant scheduling. When
threading is implemented at the kernel leve, the kernel is often forced to
decide between user threads to run with no context about the *best*
selection. User-level threads are able to choose and influence thread
scheduling, but at a performance cost.
This paper presents a user-mode thread management system that provides the
stability of kernel-mode threading and the performance of user-mode
threading, while ensurind that threads always behave correctly in critical
sections, page faults and other operating system activities. The system,
deemed "Scheduler Activations", provides an application with a
virutal-multiprocessor interface. The application receives a variant number
of (virtual) multiprocessors. The user thread-management system controls
what threads are run on each virtual processor. The kernel and thread
system communicate to notify the other about events that affect the address
space and scheduling decisions. These behavior changes are transparent to
the application programmer, using the same interface as the
thread-management platform shipped with the operating system.
Scheduler activations are data structures created by the kernel and passed
between the kernel and user levels to manage threads. A program receives one
scheduler activation structure per virtual processor. The kernel calls into
the application when each scheduler activation has been created and is ready
for use. Scheduler activations are also passed from the kernel to the
user-level system to notify for blocking, pre-emption and unblocking. These
events are generally precursors to kernel scheduling decisions, so the
user-level code has an opportunity to make scheduling decisions based on
information vectored in from the kernel. The user-level system notifies the
kernel only of thread operations that affect physical processor allocation
decisions (i.e. this virtual processor is idle).
Because scheduler activation is a thread-management system implemented at
the user level, the kernel must be able to handle a dishonest user-level
system, processes that attempt to hoard processing time by requesting
support for more threads than necessary. Clever processor-allocation
algorithms can assign prioritiies based on the process's thread-usage
history to mitigate this factor.
This system was implemented and shown to have the same performance as
FastThreads, the best existing user-level threading implementation. When an
application frequently accesses kernel services, the performance of
scheduler activations is shown to be more efficient than FastThreads.
Gail Rahn
grahn_at_cs.washington.edu
This archive was generated by hypermail 2.1.6 : Wed Jan 28 2004 - 11:46:19 PST