Scheduler Activations: Effective Kernel Support for the User-Level
Mangement of Parallelism
Thomas E. Anderson, et al. - 1992
------------------------------------------------------------------

Problem: Threads are a natural construct for parallel programs;
however, neither user-level nor kernel threads provide the correctness
and performance needed to satisfy such applications.

Problem in more detail: user-level vs. kernel threads

  - User-level threads have inherently better performance because
    kernel threads 1) require an extra boundary crossing for all
    thread operations and 2) must be general-purpose (cost of
    generality).  User threads can be made more flexible because a
    package can be customized to one user's needs.  However,
    user-level threads built on top of traditional processes or kernel
    threads can exhibit poor performance or even incorrect behavior.

  - Kernel threads exhibit correct behavior, but are too heavy-weight
    and thus suffer from poor performance. Building user-level threads
    on top of kernel threads has the problems that 1) kernel threads
    block, resume, and are preempted without the application knowing
    it and 2) kernel threads are scheduled oblviously with respect to
    the user-level thread state.  These two issues causes ineficiency
    and even incorrect behavior.  These problems are not inherent
    problems with user-level threads; rather, kernel threads are the
    wrong abstraction for providing user-level threads.

Main issue: Control and scheduling information is distributed between
the kernel and application's address space.  In order to allocate
processors, the kernel needs user-level scheduling information.  On
the other hand, the user-level package needs to be aware of kernel
events such as processor reallocations and I/O requests/completions.

Solution: scheduler activations

  - Idea: Create a user-level thread package and a kernel interface
    that achieve the functionality of kernel threads with the
    performance and flexibility of user-level threads.

  - Kernel provides each user-level thread system with its own virtual
    multiprocessor and the kernel may change the number of processors
    in that machine at any time.

  - The user-level thread system has complete control over which
    threads to run on its allocated processors.

  - Kernel notifications:

    1. Add/remove a process from a address space

    2. User-level thread blocks or wakes up in the kernel (e.g. on I/O
       or on a page fault).

  - User notifies the kernel when it needs more or fewer processors.

  - Note: see Fig 1 (page 63) and the description on pages 62 and 63
    for details of how the kernel and user-level package interact.

Performance:

  - User-level thread operations (no upcall required) perform about as
    well as normal user thread package and an order of magnitude
    better than kernel threads.

  - Upcalls are considerably slower than those for kernel threads
    (claim: this is an implementation problem).

Questions:

  - "in normal operation, threads can be created, run, and completed
    all without kernel intervention" (page 62).  Is this is true for a
    lot of applications, where there are no page faults and no
    blocking for I/O?  Is there a class of applications for which this
    is the case?

  - "the user-level thread system can ask the kernel to preempt thread
    3's processor" (page 64).  If the thread package has to cross a
    kernel boundary to perform preemption, how is this scheme
    different than kernel threads?  What boundary crossings are saved?