From: Manish Mittal (manishm_at_microsoft.com)
Date: Mon Jan 26 2004 - 17:15:17 PST
This paper analyzes the problems caused by implementing thread in kernel
level or user level. Based on analysis, the paper describes a protocol,
including both kernel interface and user level thread package, to
combine the functionality of kernel threads and flexibility of user
threads.
Both kernel threads and user-level threads can not satisfy the
requirements of parallel programming. Author argues that performance of
kernel threads is inherently worse than that of user level threads. For
ex 1) Kernel threads block, resume, and are preempted without
notification to the user level 2) Kernel-based synchronization is
expensive 3) Application has little control over thread scheduling.
User level threads provide much faster thread primitives and support
fine grain parallelism but they also suffer from certain issues such as:
1) User level threads have the problem that the expected performance is
not achieved in the presence of multiprogramming, I/O, page faults
2) If a user-level thread executes a kernel call that blocks, the kernel
thread becomes disabled.
3) Kernel thread may become blocked in a critical section, preventing
user-level threads from running even though there may be other kernel
threads to run them.
The proposed solution is to have the kernel communicate with the
user-level thread system via scheduler activations.
Scheduler activations serve three roles:
* serves as a vessel for running user-level threads the same way that a
kernel thread does
* notifies the user-level thread of a kernel event
* provides space in the kernel for saving the processor context of the
current user thread.
A scheduler activations data structures contains two stacks: kernel
stack and user-level stack. When user-level thread calls the kernel, it
uses it activation's kernel stack. The user-level thread scheduler runs
on the activation's user-level stack. The user-level selects and
executes a thread in the context of the scheduler activation.
The basic idea of scheduler activations is very simple. When a processor
is allocated to a process the user level thread manager is notified
through an upcall and the process is free to schedule another thread.
When a thread blocks inside the kernel (for I/O say) then the kernel
again notifies the user level thread manager that the thread is blocked
(but the processor is still available to the user level process). Thus
the free processor is used by the user level process the way it desires.
In case when thread is preempted inside the kernel (and the processor
for that thread is given to another process) the kernel preempts another
thread of the same process (to which the first preempted thread
belonged) since the kernel needs a processor to run the upcall and sends
a notification to the user level thread manager that two threads have
been preempted but only one processor is now available, the user level
thread can do whatever it wants with this free processor. If a thread is
preempted within a critical section, then the user level thread manager
receives the upcall and then re-runs the thread (by removing another of
its own threads) so that the critical section can be completed.
The usefulness of the approach has been shown through a prototyping
effort on DEC SRS Firefly Multiprocessor Workstation and by Modification
of FastThreads and kernel threads of Topaz (the OS of the Firefly). The
paper presents some measurement results that show that the 'virtual
multiprocessor' thread system exhibits performance that is typical of
user level thread systems while at the same time avoiding the system
integration problems exhibited by these systems. The idea of activations
is very appealing, however it is not clear whether these activations are
destroyed after each use or kept in a free list for performance
benefits.
This archive was generated by hypermail 2.1.6 : Mon Jan 26 2004 - 17:15:24 PST