From: Richard Jackson (richja_at_expedia.com)
Date: Mon Jan 26 2004 - 13:20:20 PST
This 1992 paper by Anderson, Bershad, Lazowska and Levy gives a very
compelling argument for a new paradigm of user-managed threads. This
new concept includes both a kernel interface and a user-level thread
package that work in concert.
The paper is roughly divided into three sections: 1) discussion of
current problems with user-level and kernel-level threading schemes, 2)
proposal of a new kernel model to better support user-level threading,
3) implementation and performance analysis of the new model.
First, the paper describes the current state of the threading world. In
general, threading systems can be divided into two types: kernel-level
and user-level, or some combination of both. The kernel-level scheme
suffers from performance problems, but does not exhibit the scheduling
and resource issues inherent in user-level threads. The
strictly-user-level threads perform much better, but operate in
isolation from the underlying kernel. This often leads to problems,
such as runnable threads that are idle while another thread may be
blocked while waiting for a resource, or lack of awareness of thread
priorities. It is difficult for the user-level threads and kernel to
co-exist in an optimal fashion without a better communication mechanism.
This is the exact problem that the paper tries to address.
Next, the paper proposes a solution. The terminology is "scheduler
activations" or "upcalls", which are essentially messages between the
kernel and the user-level thread package. This communication mechanism
enables the kernel to announce the following events: 1) use this
processor, 2) processor has been preempted, 3) scheduler activation is
blocked, 4) scheduler activation is unblocked. Conversely, the
user-level thread library can communicate the following messages to the
kernel: 1)request more processors, 2) one of my processors is idle.
Via these two communication paths, it is clear that a robust system of
coordination can be supported. The kernel notifies the user-level
thread library when overall system resources have been modified, and the
user-level thread library notifies the kernel when its resource needs
have changed. Note that the user-level thread library is free to use
the kernel messages as it sees fit. For example, it could decide to
switch running threads in light of a processor being preempted, based on
relative thread priority. The whole concept just exposes more control
paths for both the kernel and the user; it is quite a novel idea. The
main drawback is that the upcalls are not free, and doing too many of
them will defeat the purpose of such a system. However, these upcalls
are kept to a minimum, and only done for the specific events mentioned
above.
Finally, the paper discusses an implementation of this system and the
resulting performance. The implementation was done by modifying an
existing kernel called Topaz and a user-level thread library called
FastThreads. Amazingly, the amount of work to do this was minimal; less
than 2000 lines of code were added. Of the various implementation
issues, one performance consideration was especially interesting. To
avoid the overhead of checking for a code branch to complete critical
section in each preemption, a second copy of the code was made with the
necessary variance to support code branching. This enables the kernel
to use the more-expensive copy, as needed, while the normal case uses
the original code version. Performance is not affected in the normal
case. Regarding performance, the general performance of upcalls was
bad; it was much worse than the authors expected. However, the overall
system performance was better than the unmodified FastThreads library or
the kernel-level threads, especially in the case of a multiprogrammed
environment. It was unclear to me how upcall performance could be so
bad while overall performance was good. They mentioned that upcall is
the infrequent case, so I assume that this is the key reason.
Overall, this paper was a compelling read. The authors presented a very
good story about the weaknesses of the current threading models. The
proposed system would solve many of the current problems, and seems to
have few limitations. The only problem I had with the paper was the
discussion of performance improvements to the upcall mechanism. I think
the authors made some unsupported predictions about the possible
performance improvements. Until these changes are verified, one can not
be sure of their impact. Also, I'd argue that these improvements should
have been included in the prototype, just to help the credibility of the
system.
This archive was generated by hypermail 2.1.6 : Mon Jan 26 2004 - 13:20:32 PST