Threading, mutexes, tokens...

[Matthew Dillon]

    The problems are even worse then Joerg's example when you take into
    account the fact that the call stacks can get fairly deep.  It isn't
    just one subsystem calling another, it's subsystem A calling subsystem B
    which calls subsystem C which calls subsystem D.

    Tokens do not completely solve that problem either.   What tokens do,
    however, is make the programming model a lot more flexible.  With the
    mutex model a blind subsystem call from subsystem A to subsystem B
    requires that subsystem B not block, ever.  With the token model a
    blind subsystem call gives the target subsystem the option of blocking
    at its own whim with the only requirement that the originating subsystem
    assume that the target might block.  No further knowledge pollution is
    necessary and no further data pollution is necessary (i.e. A doesn't 
    have to pass its locked token to B).

    One major aspect of the DragonFly programming model is to avoid the
    use of tokens AND mutexes as much as possible by giving data structures
    a natural context in which they can be worked on without having to 
    worry about a conflict.

    So, for example, take signal delivery to a process.  In DragonFly
    if process A wants to deliver a signal to process B it doesn't lock
    anything... if process A is on the same cpu as process B it simply
    uses a critical section.  If process A is on a DIFFERENT cpu then
    process B then process A sends a n IPI message to process B's cpu
    to perform the action (kinda like a remote procedure call).  

    The slab allocator works the same way.  Any particular slab (block of
    memory) is owned by a particular cpu and only that cpu is allowed to
    mess with it.  If another cpu wants to mess with it the other cpu must
    send an IPI message to the owning cpu.  No mutexes, no tokens, no locks...
    just a simple critical section is sufficient for 90% of the code paths
    within the slab allocator.

    The LWKT scheduler also works that way.  In fact, it's probably one
    of the best examples in the DragonFly code base.  You can see this
    methodology in action by looking at, e.g. lwkt_deschedule() in
    kern/lwkt_thread.c.

					-Matt
					Matthew Dillon 
					<dillon at xxxxxxxxxxxxx>