Scheduler Activations: Effective Kernel
Support for the User-Level Management
of Parallelism
Anderson, Bershad, Lazowska, Levy (1992)
What sort of paper is this?
- Motivation
- New Idea
- Evaluation
The Problem
- Threads are needed for parallel applications.
- User-level and kernel-level threads both have problems.
- User-level threads offer good performance, but does not handle I/O
well.
- Kernel-level threads are expensive, but correct.
Goal: Kernel interface that gives performance of user threads with
semantics of kernel threads.
The big picture
- Each application has a virtual multi-processor.
- Kernel notifies applications of changes in scheduling.
- Thread system notifies kernel of its decisions that affect processor
allocation.Kernel mechanism is called a scheduler activation.
The Cost and Benefits of User-Level Threads
- Thread operations do not have to cross protection boundary.
- Parameters do not need to be copied.
- Kernel implements a single policy or pays overhead of managing
multiple policies.
- Applications can link in the correct thread management policy for
their needs.
- Performance is inherently better in user-level threads.
- User-level threads that issue blocking calls to the kernel will block an
entire kernel thread (i.e. virtual processor).
The Cost and Benefit of Kernel-Level Threads
- Kernel threads are expensive!
- Kernel does not understand application behavior.
- Deschedule a thread holding a spin lock.
- Thread priority inversion.
- May run out of kernel threads to handle all the user threads.
- "Correct" Kernel Level Support
Use scheduler activations instead of kernel threads as the context in which
to run user-level threads.
- SAs notify user-level schedulers of changes in kernel scheduling
decisions.
- SAs provide kernel space for threads that block in the kernel.
- Create one activation for each virtual processor.
- Kernel creates SAs to upcall into applications, notifying them of
scheduling events.
- Key difference between SAs and kernel threads
- When an SA blocks, the application is notified by a
different SA.
- The blocking SA's thread is marked blocked and the old
SA is freed.
- The new SA can now be scheduled.
- The number of SAs under control of the application
never changes (unless requested/told explicitly).
- Kernel level state is passed to thread system on upcall, so that
registers of the blocking thread are accessible to the user-level
scheduler.
Performance enhancements
- Locks: duplicate critical section code so that a preempted thread can
finish and return call to user-level scheduler without causing
overhead in the normal case.
- Keep a pool of SAs.
Performance
- Three questions:
- Cost of user-level operations relative to FastThreads.
- Costs of upcalls.
- Overall application effect.
- User-level operations relative to FastThreads?
- Cost of upcalls?
- Applications?
Related Work
- This is a particularly good example of a related work section.
- It explains what systems are similar, how they are similar and how
they differ.