"Fully parallelized" file systems

[Glenn Weinberg]

In article <262 at microsoft.UUCP> w-colinp at microsoft.uucp (Colin Plumb) writes:
>I saw in the Jan. 1 Computer Design that Encore 'unveiled the first "fully
>parallelized" file system for the Mach operating system.'
>
>Does anyone know what this is talking about?

I can't speak specifically for what Encore's done to Mach, but since I did
the parallel file system for Encore's 4.2BSD port (UMAX 4.2), I can talk
about that, and my guess is that the Mach stuff is similar (if not
identical :-)

>  As far as I know, the maximum
>parallelism you can get out of a file system equals the number of drives you
>have, 

If you're equating the file system with I/O, that's true.  But a file system
(and the Un*x file system in particular) is a lot more than just I/O.  If
your buffer cache (or memory mapped file system) is working properly, you
will find the data in memory at least an order of magnitude more often than
you find it on disk.  So although it's definitely useful to be able to
parallelize the actual I/O (and I think Encore has done that), it's by
no means the only useful parallelization in the file system.

>and the place that needs work in Unix and relatives is block allocation.

This is certainly one area that could benefit from (fine-grained) parallelism.
I don't know if Encore has truly parallelized the allocation code.  (To me
in this context, "truly parallelized" means that you will be searching in
parallel for blocks to satisfy a single allocation.  The UMAX 4.2 file
system (and presumably the new Mach stuff) does allow multiple allocations
to go on in parallel, provided they are not in the same cylinder group.)

In general, the kind of parallelization we did while I was at Encore
was directed towards allowing many processes to be active in the file
system at once, rather than training multiple processor resources on a
single process' file system activity.  Although this doesn't directly
help single-stream performance when the system is lightly loaded, it
has a significant positive impact on overall system throughput and
hence improves single-stream performance under load.

As a rule, it's much easier to get better multi-user/time-sharing
performance out of a multiprocessor than it is to parallelize a
single process, and that's what we concentrated on at Encore (at
least while I was there).

So, in the sense of a multi-user system, the UMAX 4.2 file system is
"fully parallel" in that many processes can be executing file system
code in parallel.  In fact, there are many areas of the file system
(for instance, the buffer cache) in which they can be executing the same
code in parallel (although they are hopefully not executing on the
same data :-)  This is accomplished by designing the algorithms
and data structures to minimize critical sections and shared data.

Where there must be shared data, parallelism can be increased by a
variety of means, including making careful use of reader/writer locks
(since multiple readers can access the shared data simultaneously) or
partitioning data to allow simultaneous access to different pieces of
the data.

I could go into a lot more detail, but I've ranted long enough already,
and would rather let Encore's paper (which I haven't seen) speak for
itself.
-- 
Glenn Weinberg					Email: glennw at nsc.nsc.com
National Semiconductor Corporation		Phone: (408) 721-8102
(My opinions are strictly my own, but you can borrow them if you want.)