From: Brian Milnes (brianmilnes_at_qwest.net)
Date: Mon Jan 26 2004 - 15:12:14 PST
Scheduler Activations: Effective Kernel Support for the User-Level
Management of Parallelism - Anderson, Bershad, Lazowska and Levy
The authors propose, build and measure an improved model for
building user level threads. The model is Hyrda-like in that they provide a
kernel with a new scheduling abstraction, Scheduler Activations, that allows
the user level code to implement the policy of scheduling.
The strengths of user level threads have been flexibility and speed in
systems like FastThreads. Kernel level thread implementations suffer in
performance because every thread operation is a kernel boundary crossing.
Also when you build user level threads on kernel level threads, the kernel
time slices without any idea of the user thread's state. This can causes
synchronization problems and wastes CPU on lock spinning and idles
processes on IO.
The user space process is presented with an abstract virtual machine of
processors. A single scheduler activation is created and upcalled into the
user space scheduler. The scheduler activation has a control block, a user
space stack and a kernel space stack. When the kernel has free CPUs or
requires one back it upcalls the scheduler to inform it of scheduling
changes. When the user level threads block into the kernel, the kernel
upcalls back into the scheduler telling it that it has another process to
schedule. This allows the user space scheduler to make informed decisions
about its blocking and resource availability.
The most complicated aspect of this model is how synchronization problems
are handled. The kernel might interrupt a user thread holding a lock such as
the per processor ready queue causing spinning or even deadlock. Instead of
expensive communication with the kernel on a warning call or a shared
variable, when the kernel informs a scheduler that a thread has been
preempted, it checks to see if it was in a critical section and if so the
scheduler lets it run out and then preempts this. They implement this in a
compiler/assembler processing of these critical sections which produces a
fast but complicated system of code duplication.
Their implementation was rather small, only about 1KLOC (25%) increase in
kernel thread scheduling code, small changes only to FastThreads and could
coexist with Topaz threads. The overhead compared to a pure user level
FastThreads was small, but the cost of the upcalls was significant. The
authors attribute this to the non-native implementation of scheduler
activations which were keeping extra state.
This is a great improvement to pure user level thread or Solaris's kernel
threads. The Linux kernel people have not implemented, opting for native
posix threads. Their design documentation discusses why scheduler
activations are too hard to add to Linux. But they do not handle the
problems that a 1-to-1 scheduler still has such as idling when user/kernel
thread blocks on IO (http://people.redhat.com/drepper/nptl-design.pdf).
This archive was generated by hypermail 2.1.6 : Mon Jan 26 2004 - 15:12:23 PST