From: kroe AT sbcs DOT sunysb DOT edu (KiYun Roe)
Date: Thu, 6 Feb 92 01:23:48 EST
To: DJ Delorie <dj AT ctron DOT com>
Subject: Re: Reasons not to use DJGPP :-)
Cc: djgpp AT sun DOT soe DOT clarkson DOT edu
Status: O

> I'm hoping that nothing serious will happen requiring a 1.06 version,
> as I'd like to concentrate on the 2.0 version of go32, which
> (hopefully) will include multitasking, signals, pipes, etc.

Wonderful!  How far have you gotten?  The reason I ask is that I
started thinking about how to add these very same things to go32.  I
was thinking along very simple lines; I'm sure you have something more
sophisticated in mind than what I could do.  If you've gotten pretty
far along then perhaps I'll just wait for your version, although I'd be
glad to help you if you need any assistance.

I wrote up some of my initial thoughts, and I'll include that file
here.  I haven't gotten very far, but I'd appreciate it if you could
make some comments.  I'd also very much like to hear how your scheme
differs (for the better, I'm sure).  I'm somewhat intimidated by the
prospect of dealing with a multi-threaded kernel (among other things, I
don't think I have the right debugging tools), so I was thinking of a
bare bones system that could be built on top of the existing code
without too many changes.

Here's my ideas file:
-------
I am thinking of two different ways to add multi-tasking to go32:
 
(1) The simpler is to have multiple arena tasks but only a single copy
    of the "kernel" tasks, so that we have a single-threaded kernel.  We
    use timer interrupts to preempt arena tasks, but ignore timer
    interrupts that occur when we're in the kernel.  The disadvantage of
    this scheme is that we would not get overlapping of i/o and
    processing.  The advantage is that the state of an arena task is
    pretty small: its a_tss, page directory, aout_f & areas array in
    paging.c, DOS DTA (if the task sets its own), and DOS PSP (if we
    want to be able to open more than 20 files across all tasks -- I'm
    not too familiar with this kind of stuff, but I believe that's
    true).  [I'm going to ignore graphics for the time being.  There's
    probably some state in there.] 
 
(2) A more complex kind of multi-tasking involves multi-threading the
    "kernel".  In this case, we use timer interrupts to preempt
    processes even when we're in the kernel.  This means that the
    complete state of a "process" is rather large: a copy of each tss
    (a_tss, p_tss, i_tss, etc., but maybe not c_tss), the page
    directory, aout_f & areas array in paging.g, paging buffer, perhaps
    other go32 global variables, DOS DTA, DOS PSP, and DOS SDA.  In
    addition, we have to worry about critical sections in the kernel.
    The advantage is that we get overlapping i/o and processing.
 
For the time being I'm going to concentrate on the simpler scheme with a
very simple round-robin scheduler.  Instead of making lots of little
changes to the existing go32 code, I'll start by just swapping process
state in and out of the existing data structures.
 
 
Process structures:
 
We can allocate memory for the process state with valloc.  In addition
to the state described above we may need some other minor fields to
support UNIXisms: parent process ID, group ID, information about pipes
(more on that later), etc.  For the PID we can use an index into a
little table that contains the page number of each process structure.
The process table will contain a few other bits per process for status
and who knows what else.
 
 
Paging:
 
Each process will have its own copy of the page directory.  The
processes can share second-level page tables (I'll just call them page
tables from now on), particularly for the stuff outside of the arena
memory space but also for program text (fork()) and data (vfork()).  To
keep things simple, I'm going to have all processes page against the
whole system; that is, when we need to free a page frame we'll look at
all allocated page frames.
 
Currently, page directories and page tables sit in 640K memory.  I think
it's feasible to continue to do things that way.  Assuming we have on
the order of 400K available for page tables, that's good enough to map
400M of total address space (100 page tables * (2**10 * 2**12) bytes
mappable per page table).
 
I think it'll be nice to have a sort of inverted page table that maps a
physical page number in 640K space to page table information.  This will
let us avoid scanning all the page directories when we look for
something to page out, and it's also a good place to store information
about page table sharing.  An 8-bit index will suffice to identify each
physical page in 640K space.  This will index into a table of 32-bit
longs which describe how it's being used as a page table.  We'll need 10
bits to say where the page table sits in a page directory (thus page
tables can be shared only if they map the same addresses), maybe a few
bits for flags, and then the rest for a reference count (how many
processes are sharing the page table).
 
This means modifying page_out to scan the inverted page table instead of
the page directory (this makes it trivial to free up a page frame in
640K memory when valloc needs a low frame -- well, it's almost as
trivial now, too, but it's not implemented).  Page tables are allocated
in a few places.  Just remember to update the inverted page table when
allocating a page table.

 
Pipes:
 
To implement pipes we need a little table in the process structure that
maps file descriptors to DOS file descriptors or our own pipe
descriptors.  For each pipe we need a page in low memory for the buffer
and some buffer pointers.  A process will block when it fills its pipe
writing or when reading from an empty pipe (no kidding).
 
 
Signals:
 
Now we're really getting into something I know nothing about.  I imagine
to deliver signals we will want a separate signal task for each process,
call it s_tss, that sits in the process structure along with a_tss.
When we schedule a process, we will need to remember whether we're in
the signal task or the main arena task.  That's easy.  To generalize
when we have even more tasks per process, we'll save tss_ptr in the
process structure (and utils_tss when we multi-thread the kernel).
 
I think I'm going to follow _The Design and Implementation of the 4.3BSD
UNIX Operating System_ by Leffler et al., when I implement the signal
system particularly the data structures.  Of course, for the first cut
I'm only going to code the simplest cases.


Valloc:

I'm planning to use low memory pages for a variety of purposes as
described above.  We're going to have to allow for the case when there
are no more low memory pages.  Page_out will have to return an
indication that it couldn't find a low memory page frame to free, and
then valloc will likewise fail.  Eventually, we'll want to page out
page tables, too, generalizing the code that appears in
page_out_everything.  Ah, well, the thing to do is put page directories
in the inverted page table, too, so that page_out scanning will see
those pages, too, in some manner.
-------