Newsgroups: comp.sys.m6809
Path: utzoo!lsuc!jimomura
From: jimomura@lsuc.uucp (Jim Omura)
Subject: Scheduler design
Keywords: 
Followup-To: 
Reply-To: jimomura@lsuc.UUCP (Jim Omura)
Date: Sun, 15-May-88 23:03:56 EDT
Summary: If you have the time. . . .
Message-ID: <1988May15.230357.12617@lsuc.uucp>
Expires: 
Sender: 
References: 
Organization: Consultant, Toronto


     I have too many projects going again.  As such, this is one
that I'm abandonning.  It should not be that hard, but I have no
time for it.  Gee.  Sure would be nice if somebody wrote this!
:-)

Cheers! -- Jim O.
88/05/15
A design for a Scheduling System.
Revision #1

Based on a Database of Streams.

$Stream1
 * Event1
 * Event2
 * Event3
  ^Stream2*Event10^
 * Event4
  ^Stream2*Event6^,>Stream3*Event12>
 * Event5

$Stream2
 * Event6
 * Event7
 * Event8
  ^Stream3*Event13,Stream4*Event14^
 * Event9
 * Event10
 * Event11

$Stream3
 * Event12
 * Event13

$Stream4
 *Event14

     The syntax is simple.  There are 6 main "transition" markers:

$ Stream marker
* Event marker
^ Requirement marker preceding
> Requirement marker concurrent
" Quote marker
' Comment

Streams and Events:

     For either of the first 2 transition markers ($, *) it
is presumed that a Label follows make up of the first contiguous
set of "valid label characters" following.  Valid label characters
are any alpha-numerical characters, and dot and underline.
Punctuation except for dot and underline are treated as non-printing
white space.  As such, space, tabs, EOL's and are ignored, and
any of SPC, TAB, EOL, EOF and puctuation such as comma, colon or
semi-colon can terminate a Label.  NULL's should be ignored in
either case and possibly, automatically removed from the file during
any update if a special file editor is created.

     Anything following the Label is a modifier until another
transition marker is encountered.  Syntax for modifiers vary
a bit, but fairly regularly.

     Stream are limited according to the OS.  For OS-9, 29
characters total.  For MS-DOS, 8 characters.  Event labels
are arbitrarily set at 16 characters maximum.

     NOTE:  Time is *not* treated particularly specially.  A
Stream called $TIME might be useful.  To indicate a deadline
it would be sufficient to label a specific date as requiring
the last Events in the other streams as Precedent.  If you
want to get fancy, you can have a special data format for
time, so output can be specially tailored, but otherwise,
there's no need for it to be distinguished.

Modifiers:

     Requirement are marked with either ^ or >.  These must
be preceeded by an Event and modify the preceding event by stating
what other events must occur either before or at the same time
as the event modified.  As with quotes and comments, each
set of requirements is terminated by the same mark with which
it starts.

     A Comment or Quote is terminated by another comment or
quote marker.  A Quote is intended to be printed as output
as it occurs until the closing quote is encountered.  A backslash
(\) preceding a quote mark within a quote forces the printing
of a quote marker.  A comment is for internal documentation
for the owner of the database.

Overview:

     Conceptually, a Stream is made up of a number of sequential
events.  If 2 events may occur at the same time, the 2nd event
should be assigned to a different stream.  If not, one can be made
a Quote, but that should not be necessary and is probably bad
form.
 
     If an impossibility arises, due to requirements of precedence
or concurrence of functions which cannot occur in that order, an
error is generated and the processor stops.
 
     In this sample, some redundance occurs, but that's fine.
Event4 is dependent on 2 Events, both of which *must* have
already occured before it is reached.  The 'hat' sign indicates
an event which must have occured before the current event.
Each event is identified by a Stream and Event number.

Output:

     The output is a chart, either horizontal or vertically
formatted where key precedent or concurrent events are
specially marked and events which must occur after are so
printed.

     The special transition markers should not be printed
in the default case.  Neither should comments.  Quotes are
printed with their labels.

Main Data Handler:

     First, the datafile is read in and separated into
separate stream file.  Then each stream file is read
until a requirement is reached (or EOF).  Then the
events are printed until the either a requirement
label is encountered or an event that has a requirement
is encountered.  If it's an event that needs another
event precedent or concurrent, that file stops printing
until the required event label is reached.  If the
requirement is a precedent, then it is not printed
until after the precedent is printed.  If they are
concurrent, then they are printed together, or await
any other precedent or concurrent events.

     If a required label is encountered first, it is
checked whether it's precedent or concurrent with
its associated labels.  If it is not required to
be concurrent with any other events (ie it is precedent
to one or more events) then it is printed immediately
and the flags for the associated events are cleared.
If it is required to be concurrent, then it is held
until the event requiring it is reached and it is
printed with it (or them as the case may be).

     It is clear that each flagged event label needs
at most a structure of flags and labels equal to
the number of streams less 1.
-- 
Jim Omura, 2A King George's Drive, Toronto, (416) 652-3880
ihnp4!utzoo!lsuc!jimomura
Byte Information eXchange: jimomura