[coyotos-dev] What are Scheduler Activations

[Timothy Roscoe]

Since Shap has rather unceremoniously hurled me into the Coyotos
development list, I suppose I should elaborate a little on scheduler
activations and Nemesis' activation mechanism, which are actually
somewhat different.   Note that I'm not exactly up to speed on Coyotos
so far...

First, just scheduling and processor dispatch.  I'm also simplifying -
these are "minimalist" descriptions, and there are lots of
optimization things one could (and should, and did) do to improve
these basic schemes:

First, NEMESIS: 

Context: Multiservice mix of time-sensitive applications running on a
         desktop Alpha-based uniprocessor.

State:
 - Each domain (process) has two "context slots" to hold minimal
   processor state: the "activation slot" and the "resume slot".  Both
   are writeable by the process. 
 - There's a "activation" flag (also writeable)
 - There's a (fixed) entry point in each domain, called the activation
   handler. 
 - There's a small, fixed size stack for executing the activation
   handler.  

Behaviour:
 - If the activation flag is set:
    - When the domain is next scheduled, it's simply loaded back from
      the resume slot.
    - On a preemption, the processor state is saved in the resume
      slot.    A lot like Unix so far. 
 - If the activation flag is clear: 
    - When the domain is next scheduled, reload NO state and just
      enter the activation handler on the activation stack. 
    - On a preemption, processor state is saved in the activation
      slot, AND the activation flag is set. 

Usage: 
 - The common case is that the domain is dispatched via the activation
   handler.  This is where the user-level thread scheduler sits, and
   it selects a thread to run.
 - While in the thread scheduler, the activation flag is set, so the
   thread scheduler does not need to be reentrant. 
 - To resume a thread, the ULS has to (a) load context, including PC,
   and (b) clear the activation flag.  A moment's thought will show
   that this has to be done atomically. 
 - Nemesis used an Alpha PAL call to do this - cost is two pipeline
   drains.  You can't do this as easily on an ia32 or EMT64
   processor. 

Okey dokey?  

Second, SCHEDULER ACTIVATIONS:

Context: Multithreaded long-term compute-intensive jobs running on a 
         multiprocessor. 

State: 
 - Each process has a context slot per physical processor.
 - Each process has a (conceptually unbounded) activation stack for
   each physical processor.  
 - There's an "activation handler" entry point. 

Behaviour: 
 - When a processor is dispatched to a process, it's done via an
   upcall into the activation handler, on the activation stack.  
 - Unlike Nemesis, in the unlikely event that this happens twice, you
   get two activations on the per-processor activation stack. 
 - When a processor is preempted and descheduled, ANOTHER processor
   which is currently allocated to the process is interrupted, its
   state saved in its context slot, and immediately upcalled to notify
   the ULS that a processor has gone away. 
 - If the processor being preempted is the last one, obviously this
   notification doesn't occur until the process gets at least one
   processor back. 

Usage: 
 - Clearly, Scheduler Activations is dealing with (relative to
   Nemesis) longer-term allocations of processors to processes.  This
   is entirely appropriate for (a) the workload, and (b) a
   multiprocessor with ~16 cores.  
 - They demonstrate that the overhead of using a second processor to
   notify the ULS of a deschedule is acceptable in their case.   
 - I would conjecture (and I have no figures to justify this) that
   with manycore processors this argument becomes stronger, and
   operates on a finer time granularity than before. 

There we go - I'll post something about IPC (or IDC) in Nemesis when
I've next got a moment. 

 -- Mothy


At Wed, 18 Jan 2006 20:55:44 -0500, Coyotos development discussions <coyotos-dev at coyotos.org> wrote:
> This note will try to provide a brief introduction to scheduler
> activations. The view presented here is similar to the classical view,
> but given from a slightly different perspective. The primary papers to
> look at concerning scheduler activations (to my knowledge) are:
> 
> 
>   Scheduler Activations: Effective Kernel Support for the
>   User-Level Management of Parallelism
>   http://citeseer.ist.psu.edu/anderson92scheduler.html
>   (This is the classic paper on the subject)
> 
>   The Structure of a Multi-Service Operating System
>   http://citeseer.ist.psu.edu/roscoe95structure.html
>   (Mothy Roscoe's dissertation. Detailed, clear, well-written,
>     but long).
> 
>   First-Class User-Level Threads
>   http://citeseer.ist.psu.edu/marsh91firstclass.html
>   (An different approach that also deserves a serious look)
> 
> 
> The original idea behind scheduler activations was to find a way to let
> the kernel issue preemption events to an application in such a way that
> the application could use these to schedule user-level threads. This
> idea was rapidly generalized to other events.
> 
> In Nemesis, the basic model (if I have understood Mothy correctly from
> our discussions) is that *all* kernel operations are asynchronous: every
> process control block has some number of "event" structures as part of
> its state. In situations where a conventional kernel would block the
> process, one of these event structures is instead placed on the stall
> queue. When the queue is awakened, an "activation" is delivered to the
> associated process.
> 
> Let me first describe the activation mechanism and then return to the
> events and some crazy ideas we are contemplating this evening.
> 
> 
> ACTIVATION MECHANISM
> 
> At the most primitive level, a scheduler activation implementation
> provides a mechanism for performing an **application level** context
> switch. The mechanism is similar to the trap handling mechanism of a
> RISC processor.
> 
> The design relies on having a small number of words (practical minimum:
> four) that live in storage which is writable to both the application and
> the kernel. Processes have two states: "normal" and "activated". An
> "activated" process is comparable to a kernel with interrupts disabled:
> it is not activation preemptions.
> 
> The four shared words are used as follows:
> 
>   Saved Program Counter
>   Saved Stack Pointer
>   Activation State (0 = normal, 1 = activated)
>   Pointer to list of delivered events
>   [Possibly a few more for other saved registers, but generally not]
> 
> When the OS wishes to perform a user-level preemption on a process in
> the "normal" state, it proceeds as follows:
> 
>   - The current PC and SP are saved to the Saved Program Counter and
>     Saved Stack Pointer locations.
>   - The process state is set to "activated" by overwriting the
>     activation state location
>   - New values for PC and SP are loaded from dedicated locations
>     in the process control block (these are, respectively, the
>     Activation PC and the Activation SP)
>   - Execution resumes.
> 
> For the moment, I will ignore the "delivered events" slot.
> 
> On entry to the activation handler, the preempted PC and SP have already
> been saved. It is up to the handler code to save the rest of the
> registers and decide what (if anything) to do. Typically, the thing to
> do is process any pending delivered events, which are found by checking
> to see if the "delivered events" field is non-zero.
> 
> Eventually, the activation handler will resume execution in the "normal"
> running mode. To do so, it reloads the desired register set including
> the stack pointer. The last two instructions set the Activation State
> field to 0 and then branch to the proper instruction to resume normal
> execution. These last two instructions taken together are comparable to
> an interrupt return. In practice, an interrupt might occur just before
> the jump instruction, and either the operating system or the handler
> must know the convention in order to guarantee atomicity. Note that the
> transition from "activated" to "normal" does *not* require a re-entry
> into the kernel. It occurs entirely at user level.
> 
> There are a number of variations on the handling of the delivered events
> field. It can be a bitmap, a pointer to a linked list, or several other
> things. The general idea is that the activation handler is supposed to
> "accept" all of the pending events (in the sense that it takes notice of
> them -- it can defer handling them). No new events will be posted while
> the process remains in the "activated" state.
> 
> 
> DEPARTURES
> 
> The main issues with these event structures in the existing
> implementations are:
> 
>   1. They are not "first class" -- an event structure has no
>      existence independent of its containing process.
> 
>   2. They carry absolutely minimal state: the identity of
>      the event structure and one or two words of state.
> 
>      This is the key point that we want to look at.
> 
>   3. Some of the activations that are reported present security
>      issues. Notably: in Nemesis *all* returns from preemptions
>      of any kind are delivered to the activation handler, which
>      gives the program precise knowledge of third-party interrupt
>      rate and timing.
> 
>      This can be addressed by choosing the reported events a little
>      bit more cautiously.
> 
>   4. It appears that nobody has considered how this might be
>      integrated with an IPC-oriented design.
> 
>   5. To my knowledge, this design has not been reconciled with
>      the desire to perform *synchronous* operations.
> 
> shap
> 
> _______________________________________________
> coyotos-dev mailing list
> coyotos-dev at coyotos.org
> http://www.coyotos.org/mailman/listinfo/coyotos-dev
> 
> 
>