I started thinking about send/receive message passing
microkernels again instead of the migraring thraad/protection
ring ideas that I've often considered.  This lead me to think
about how to add concurrency to a single threaded filesystem.
From reading old posts I gather there was a multithreaded
filesystem for Minix but couldn't find out anything about it.

So a few ways I thought:

1) State machine.. FS queues messages and handle them
like a state machine, but that gets omplicated espeically
with lots of places to block, nesting and looping in each
request.

2) Multithreaded FS.  Each thread handles a different request,
needs kernel-mode threads and a number of sync primitives.

3) Migrating Threads.  Allow a thread to cross from one
protection domain to another.  More or less like call-gates and
protection rings.  This is what I tended to concentrate on.  It still
needs sync primitives like mutexes/condvars or sleep/wakeup
mechanisms.

So last night I did some reading of old posts hoping to find info
about Minix's multithreaded FS when I thought of cooperative
multitasking on a single server thread.

Filesystem runs on single thread but uses separate stacks for each
request and cooperatively schedules them by yielding.  Filesystem
then acts like a giant monitor/condition variable.  Might be similar
to Unix's sleep()/wakeup() and having only one thread in the
kernel at a time.

Having a stack is much easier than a state machine and storing
state in a separate structure for each request, makes it easier
to have loops and nesting of code.   In Pseudocode it might
look something like this:

// Main co-op thread, responsible for receiving messages
// from clients and sending and receiving requests to
// device drivers.  Manages a list of io requests created
// by

void Main()
{
    for (;;)
    {
        msg = Receive(RECEIVE_ANY);

        if (msg.type == client_request)
        {
                // Alloc co-op thread and stack, simple
                // with a static table of Threads/stacks,
                //
                // Copy msg onto stack
                // Initialse thread
                // Place thread on co-op list of threads.

                Yield();    // Starts running co-op threads.

                // Optimization would run only this new
                // co-op thread instead of all
        }
        else if (msg.type == driver_reply)
        {
            // Start running the co-op threads that handle the
            // requests.

            Yield();
        }

        // Process list of  IORequests (read_block/write_block etc)
        // created by the other co-op threads.
        // Could remove redundant IORequests wantint to read
        // same block.

        for (each IO Request)
        {
                Send (driver, IORequst);        // Non blocking Send.
        }
    }

// A co-op thread/stack is created to handle a Read request

void Read (struct Msg msg)
{
     // Used for sending ReadBlock/WriteBlock requests to
    // main() which then deals with sending the real requests
    // to the devices.

    struct IORequest ioreq;

    if (block->in_cache == true)
    {
        MemCopy_To_Client();
        ReplyMsg();
    }
    else
    {
        ioreq.device = xyz;
        ioreq.block = block_nr;
        EnqueueIORequest (&ioreq);

        While (block->in_cache == false)
        {
            Yield();
        }

        MemCopy_To_Client();
        ReplyMsg();
    }

    // The wrapper code upon return will remove this
    // thread from the co-op list and free the stack.

It is pseudo-code so things like Read() would be more
complicated,  it would be a loop until nbytes are read
for example.

Needs co-op thread for each filesystem request,  so possibly
statically allocate co-op thread/stack for each real thread/
process supported by OS.  Could possibly do it with fewer
co-op threads,  just need to figure out where to queue the
requests.

Some optimizations possible,  don't run through all threads when
placing new thread on co-op list.  Code above wakes up
all co-op threads when a message is returned from a driver,
they then have to see if the message was from them, otherwise
they Yield().  It is analogous to dealing with level-triggered
interrupts or a monitor/condition-variable using CondBroadcast()
to wake up all threads.

Could maintain queues of threads for each cache block and
only wake up those co-op threads whose data has arrived,
a bit like having a condition variable for each cache block.

Maybe it is still a bottleneck with only one real thread running
lots of cooperative threads.  Maybe it is possible to share some
of the cooperative threads among several kernel threads, but that
would get a lot more complicated and need more sync primitives.

PS: Haven't thought it through completely,  thought about it last
night and wrote it down  :)

--
Marv