(NUMBER)
"THE REALTIME SYSTEM

 PER BRINCH HANSEN

 INFORMATION SCIENCE
 CALIFORNIA INSTITUTE OF TECTHNOLOGY
 PASADENA, CALIFORNIA 91125

 20 OCTOBER 1975"


"#############
#  IO TYPES  #
#############"


TYPE IODEVICE =
  (TYPEDEVICE, DISKDEVICE);

TYPE IOOPERATION =
  (INPUT, OUTPUT, MOVE, CONTROL);

TYPE IORESULT =
  (COMPLETE, INTERVENTION, TRANSMISSION, FAILURE,
   ENDFILE, ENDMEDIUM, STARTMEDIUM);

TYPE IOPARAM = RECORD
                 OPERATION: IOOPERATION;
                 STATUS: IORESULT;
                 ARG: INTEGER
               END;

CONST
NUL = '(:0:)';  BEL = '(:7:)';  NL = '(:10:)';

CONST LINELENGTH = 72;
TYPE LINE = ARRAY (.1..LINELENGTH.) OF CHAR;


"###############
#  TYPEWRITER  #
###############"


TYPE TYPEWRITER =
CLASS


PROCEDURE ENTRY WRITE(C: CHAR);
VAR PARAM: IOPARAM; X: CHAR;
BEGIN
  X:= C; PARAM.OPERATION:= OUTPUT;
  IO(X, PARAM, TYPEDEVICE);
END;

PROCEDURE ENTRY READ(VAR C: CHAR);
VAR PARAM: IOPARAM;
BEGIN
  PARAM.OPERATION:= INPUT;
  IO(C, PARAM, TYPEDEVICE);
END;

BEGIN END;


"#############
#  TERMINAL  #
#############"


TYPE TERMINAL =
CLASS

VAR DEVICE: TYPEWRITER;

PROCEDURE ENTRY WRITE(C: CHAR);
BEGIN DEVICE.WRITE(C) END;

PROCEDURE ENTRY WRITETEXT(TEXT: LINE);
VAR I: INTEGER; C: CHAR;
BEGIN
  I:= 1; C:= TEXT(.1.);
  WHILE C <> NUL DO
  BEGIN
    DEVICE.WRITE(C);
    I:= I + 1;
    C:= TEXT(.I.);
  END;
END;

PROCEDURE ENTRY WRITEINT(INT: UNIV INTEGER);
VAR DIGITS: ARRAY (.1..6.) OF CHAR;
    REM, LENGTH: INTEGER;
BEGIN
  REM:= INT; LENGTH:= 0;
  REPEAT
    LENGTH:= LENGTH + 1;
    DIGITS(.LENGTH.):= CHR(REM MOD 10 + ORD('0'));
    REM:= REM DIV 10;
  UNTIL REM = 0;
  FOR LENGTH:= LENGTH DOWNTO 1 DO
    DEVICE.WRITE(DIGITS(.LENGTH.));
END;

PROCEDURE ENTRY READ(VAR C: CHAR);
BEGIN DEVICE.READ(C) END;

BEGIN INIT DEVICE END;


"############
#  BELLKEY  #
############"


TYPE BELLKEY =
CLASS

VAR PARAM: IOPARAM;

PROCEDURE ENTRY AWAIT;
BEGIN IO(PARAM, PARAM, TYPEDEVICE) END;

BEGIN PARAM.OPERATION:= CONTROL END;


"#########
#  FIFO  #
#########"


TYPE FIFO =
CLASS(LIMIT: INTEGER);

VAR HEAD, TAIL, LENGTH: INTEGER;

FUNCTION ENTRY ARRIVAL: INTEGER;
BEGIN
  ARRIVAL:= TAIL;
  TAIL:= TAIL MOD LIMIT + 1;
  LENGTH:= LENGTH + 1;
END;

FUNCTION ENTRY DEPARTURE: INTEGER;
BEGIN
  DEPARTURE:= HEAD;
  HEAD:= HEAD MOD LIMIT + 1;
  LENGTH:= LENGTH - 1;
END;

FUNCTION ENTRY EMPTY: BOOLEAN;
BEGIN EMPTY:= (LENGTH = 0) END;

FUNCTION ENTRY FULL: BOOLEAN;
BEGIN FULL:= (LENGTH = LIMIT) END;

BEGIN HEAD:= 1; TAIL:= 1; LENGTH:= 0 END;


"#############
#  RESOURCE  #
#############"


CONST PROCESSCOUNT = 10;
TYPE PROCESSINDEX = 1..PROCESSCOUNT;
     PROCESSQUEUE = ARRAY (.PROCESSINDEX.) OF QUEUE;


TYPE RESOURCE =
MONITOR

VAR FREE: BOOLEAN; Q: PROCESSQUEUE; NEXT: FIFO;

PROCEDURE ENTRY REQUEST;
BEGIN
  IF FREE THEN FREE:= FALSE
    ELSE DELAY(Q(.NEXT.ARRIVAL.));
END;

PROCEDURE ENTRY RELEASE;
BEGIN
  IF NEXT.EMPTY THEN FREE:= TRUE
    ELSE CONTINUE(Q(.NEXT.DEPARTURE.));
END;

BEGIN FREE:= TRUE; INIT NEXT(PROCESSCOUNT) END;


"##############
#  TASKQUEUE  #
##############"


CONST CALLER = 0;


TYPE TASKQUEUE =
MONITOR

VAR WAITING: PROCESSQUEUE;

PROCEDURE ENTRY PREEMPT;
BEGIN DELAY(WAITING(.ATTRIBUTE(CALLER).)) END;

PROCEDURE ENTRY RESUME(TASK: PROCESSINDEX);
BEGIN CONTINUE(WAITING(.TASK.)) END;

BEGIN END;


"############
#  TASKSET  #
############"


CONST IDLENGTH = 12;
TYPE IDENTIFIER = ARRAY (.1..IDLENGTH.) OF CHAR;


TYPE TASKSET =
MONITOR

VAR TABLE: ARRAY (.PROCESSINDEX.) OF IDENTIFIER;

PROCEDURE INITIALIZE;
VAR TASK: PROCESSINDEX;
BEGIN
  FOR TASK:= 1 TO PROCESSCOUNT DO
    TABLE(.TASK.):= '            ';
END;

FUNCTION INDEX(ID: IDENTIFIER): PROCESSINDEX;
VAR I, J: PROCESSINDEX;
BEGIN
  I:= 1; J:= PROCESSCOUNT;
  WHILE I < J DO
    IF TABLE(.I.) = ID THEN J:= I
                       ELSE I:= I + 1;
  INDEX:= I;
END;

PROCEDURE ENTRY INCLUDE(ID: IDENTIFIER; TASK: PROCESSINDEX);
BEGIN TABLE(.TASK.):= ID END;

FUNCTION ENTRY MEMBER(ID: IDENTIFIER): BOOLEAN;
BEGIN MEMBER:= (TABLE(.INDEX(ID).) = ID) END;

FUNCTION ENTRY TASK(ID: IDENTIFIER): PROCESSINDEX;
BEGIN TASK:= INDEX(ID) END;

PROCEDURE ENTRY ME(VAR ID: IDENTIFIER);
BEGIN ID:= TABLE(.ATTRIBUTE(CALLER).) END;

BEGIN INITIALIZE END;


"##########
#  CLOCK  #
##########"


CONST ONEMIN  =    60.0 "SECONDS";
      ONEHOUR =  3600.0 "SECONDS";
      HALFDAY = 43200.0 "SECONDS";
      ONEDAY  = 86400.0 "SECONDS";


TYPE CLOCK =
MONITOR

VAR SECONDS: REAL;

FUNCTION ENTRY VALUE: REAL;
BEGIN VALUE:= SECONDS END;

PROCEDURE ENTRY CORRECT(TIME: REAL);
BEGIN SECONDS:= TIME END;

PROCEDURE ENTRY TICK;
BEGIN
  SECONDS:= SECONDS + 1.0;
  IF SECONDS >= ONEDAY THEN
    SECONDS:= SECONDS - ONEDAY;
END;

BEGIN SECONDS:= 0.0 END;


"################
#  TASKPROCESS  #
################"


TYPE TASKPROCESS =
PROCESS
  (TYPEUSE: RESOURCE; WAITING: TASKQUEUE;
   TASKLIST: TASKSET; WATCH: CLOCK);

VAR OPERATOR: TERMINAL; ID: IDENTIFIER;

PROCEDURE WRITEID(ID: IDENTIFIER);
VAR I: INTEGER;
BEGIN
  WITH TASKLIST, OPERATOR DO
  BEGIN
    FOR I:= 1 TO (TASK(ID) - 2)*24 DO
      WRITE(' ');
    FOR I:= 1 TO IDLENGTH DO
      WRITE(ID(.I.));
    WRITE(' '); WRITE(BEL);
  END;
END;

PROCEDURE WRITETIME(TIME: REAL);
VAR HOUR, MIN, SEC: INTEGER; REM: REAL;
BEGIN
  HOUR:= TRUNC(TIME/ONEHOUR);
  REM:= TIME - CONV(HOUR) * ONEHOUR;
  MIN:= TRUNC(REM/ONEMIN);
  SEC:= TRUNC(REM - CONV(MIN) * ONEMIN);
  WITH OPERATOR DO
  BEGIN
    WRITEINT(HOUR); WRITE(':');
    WRITEINT(MIN); WRITE(':');
    WRITEINT(SEC); WRITE(NL);
  END;
END;

BEGIN
  INIT OPERATOR; TASKLIST.ME(ID);
  CYCLE
    WAITING.PREEMPT;
    TYPEUSE.REQUEST;
    WRITEID(ID);
    WRITETIME(WATCH.VALUE);
    TYPEUSE.RELEASE;
  END;
END;


"##############
#  TIMETABLE  #
##############"


TYPE TASKSCHEDULE = RECORD
                      ACTIVE: BOOLEAN;
                      START, PERIOD: REAL
                    END;


TYPE TIMETABLE =
MONITOR(WAITING: TASKQUEUE);

VAR TABLE: ARRAY (.PROCESSINDEX.) OF TASKSCHEDULE;

PROCEDURE INITIALIZE;
VAR TASK: PROCESSINDEX;
BEGIN
  FOR TASK:= 1 TO PROCESSCOUNT DO
    TABLE(.TASK.).ACTIVE:= FALSE;
END;

FUNCTION REACHED(TIME, START: REAL): BOOLEAN;
VAR DIFF: REAL;
BEGIN
  DIFF:= TIME - START;
  IF ABS(DIFF) >= HALFDAY
    THEN REACHED:= (DIFF < 0.0)
    ELSE REACHED:= (DIFF >= 0.0);
END;

PROCEDURE ENTRY START(TASK: PROCESSINDEX; TIME: REAL);
BEGIN
  WITH TABLE(.TASK.) DO
  BEGIN ACTIVE:= TRUE; START:= TIME END;
END;

PROCEDURE ENTRY PERIOD(TASK: PROCESSINDEX; TIME: REAL);
BEGIN TABLE(.TASK.).PERIOD:= TIME END;

PROCEDURE ENTRY STOP(TASK: PROCESSINDEX);
BEGIN TABLE(.TASK.).ACTIVE:= FALSE END;

PROCEDURE ENTRY EXAMINE(TIME: REAL);
VAR TASK: PROCESSINDEX; LATE: REAL;
BEGIN
  FOR TASK:= 1 TO PROCESSCOUNT DO
  WITH TABLE(.TASK.) DO
  IF ACTIVE THEN
    IF REACHED(TIME, START) THEN
    BEGIN
      WAITING.RESUME(TASK);
      START:= START + PERIOD;
      IF START >= ONEDAY THEN
        START:= START - ONEDAY;
    END;
END;

BEGIN INITIALIZE END;


"#################
#  CLOCKPROCESS  #
#################"


TYPE CLOCKPROCESS =
PROCESS(WATCH: CLOCK; SCHEDULE: TIMETABLE);

BEGIN
  WITH WATCH, SCHEDULE DO
  CYCLE WAIT; TICK; EXAMINE(VALUE) END;
END;


"####################
#  OPERATORPROCESS  #
####################"


TYPE OPERATORPROCESS =
PROCESS
  (TYPEUSE: RESOURCE; TASKLIST: TASKSET;
   WATCH: CLOCK; SCHEDULE: TIMETABLE);

VAR OPERATOR: TERMINAL; BELL: BELLKEY;
    LETTERS, DIGITS: SET OF CHAR;
    OK: BOOLEAN; CH: CHAR; COMMAND: IDENTIFIER;

PROCEDURE HELP;
BEGIN
  IF OK THEN
  WITH OPERATOR DO
  BEGIN
    WRITE(NL);
    WRITETEXT('TRY AGAIN (:10:)(:0:)');
    WRITETEXT('     START(TASK, HOUR:MIN:SEC)(:10:)(:0:)');
    WRITETEXT('     PERIOD(TASK, HOUR:MIN:SEC) (:10:)(:0:)');
    WRITETEXT('     STOP(TASK) (:10:)(:0:)');
    WRITETEXT('     TIME(HOUR:MIN:SEC) (:10:)(:0:)');
    WRITETEXT('     SOLO (:10:)(:0:)');
    OK:= FALSE;
  END;
END;

PROCEDURE NEXTCHAR;
BEGIN
  IF OK THEN
  REPEAT OPERATOR.READ(CH) UNTIL CH <> ' ';
END;

PROCEDURE SKIPCHAR(DELIM: CHAR);
BEGIN
  IF CH = DELIM THEN NEXTCHAR ELSE HELP;
END;

PROCEDURE READINT(VAR INT: INTEGER);
CONST MAXINT = 32767;
VAR DIGIT: INTEGER;
BEGIN
  INT:= 0;
  IF NOT (CH IN DIGITS) THEN HELP ELSE
  WHILE (CH IN DIGITS) & OK DO
  BEGIN
    DIGIT:= ORD(CH) - ORD('0');
    IF INT > (MAXINT - DIGIT) DIV 10
      THEN HELP ELSE
      INT:= 10* INT + DIGIT;
    NEXTCHAR;
  END;
END;

PROCEDURE READID(VAR ID: IDENTIFIER);
VAR LENGTH: INTEGER;
BEGIN
  ID:= '            ';
  IF NOT (CH IN LETTERS) THEN HELP ELSE
  BEGIN
    LENGTH:= 0;
    WHILE (CH IN (LETTERS OR DIGITS)) & (LENGTH < IDLENGTH) DO
    BEGIN
      LENGTH:= LENGTH + 1; ID(.LENGTH.):= CH;
      NEXTCHAR;
    END;
  END;
END;


PROCEDURE READTIME(VAR TIME: REAL);
VAR HOUR, MIN, SEC: INTEGER;
BEGIN
  READINT(HOUR); SKIPCHAR(':');
  READINT(MIN); SKIPCHAR(':');
  READINT(SEC);
  IF (HOUR > 23) OR (MIN > 59) OR (SEC > 59) THEN HELP;
  IF OK THEN
    TIME:= ONEHOUR*CONV(HOUR) + ONEMIN*CONV(MIN) + CONV(SEC);
END;

PROCEDURE START;
VAR ID: IDENTIFIER; TIME: REAL;
BEGIN
  SKIPCHAR('('); READID(ID);
  SKIPCHAR(','); READTIME(TIME);
  SKIPCHAR(')');
  IF OK THEN
  WITH TASKLIST, SCHEDULE, OPERATOR DO
  IF MEMBER(ID) THEN START(TASK(ID), TIME)
                ELSE WRITETEXT(' TASK UNKNOWN (:10:)(:0:)');
END;

PROCEDURE PERIOD;
VAR ID: IDENTIFIER; TIME: REAL;
BEGIN
  SKIPCHAR('('); READID(ID);
  SKIPCHAR(','); READTIME(TIME);
  SKIPCHAR(')');
  IF OK THEN
  WITH TASKLIST, SCHEDULE, OPERATOR DO
  IF MEMBER(ID) THEN PERIOD(TASK(ID), TIME)
                ELSE WRITETEXT(' TASK UNKNOWN (:10:)(:0:)');
END;

PROCEDURE STOP;
VAR ID: IDENTIFIER;
BEGIN
  SKIPCHAR('('); READID(ID);
  SKIPCHAR(')');
  IF OK THEN
  WITH TASKLIST, SCHEDULE, OPERATOR DO
  IF MEMBER(ID) THEN STOP(TASK(ID))
                ELSE WRITETEXT(' TASK UNKNOWN (:10:)(:0:)');
END;

PROCEDURE CORRECT;
VAR TIME: REAL;
BEGIN
  SKIPCHAR('('); READTIME(TIME);
  SKIPCHAR(')');
  IF OK THEN WATCH.CORRECT(TIME);
END;

PROCEDURE SOLO;
CONST SOLOADDR = 24;
VAR PARAM: IOPARAM;
BEGIN
  WITH PARAM DO
  BEGIN
    OPERATION:= CONTROL;
    ARG:= SOLOADDR;
  END;
  IO(PARAM, PARAM, DISKDEVICE);
END;

BEGIN
  INIT OPERATOR, BELL;
  LETTERS:= (.'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
              'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
              'U', 'V', 'W', 'X', 'Y', 'Z', '_'.);
  DIGITS:= (.'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'.);
  WITH TYPEUSE, OPERATOR, BELL DO
  CYCLE
    AWAIT;
    REQUEST;
    OK:= TRUE;
    WRITETEXT('TYPE COMMAND (:10:)(:7:)(:0:)');
    NEXTCHAR;
    READID(COMMAND);
    IF COMMAND = 'START       ' THEN START ELSE
    IF COMMAND = 'PERIOD      ' THEN PERIOD ELSE
    IF COMMAND = 'STOP        ' THEN STOP ELSE
    IF COMMAND = 'TIME        ' THEN CORRECT ELSE
    IF COMMAND = 'SOLO        ' THEN SOLO ELSE
                                     HELP;
    WRITE(NL);
    RELEASE;
  END;
END;


"####################
#  INITIAL PROCESS  #
####################"


VAR
TYPEUSE: RESOURCE; WAITING: TASKQUEUE;
TASKLIST: TASKSET; WATCH: CLOCK;
SCAN, FLOW, LOG: TASKPROCESS;
SCHEDULE: TIMETABLE;
CLOCKPULSE: CLOCKPROCESS; OPERATOR: OPERATORPROCESS;

BEGIN
  INIT TYPEUSE, WAITING, TASKLIST, WATCH;
  WITH TASKLIST DO
  BEGIN
    INCLUDE('SCAN        ', 2);
    INIT SCAN(TYPEUSE, WAITING, TASKLIST, WATCH);
    INCLUDE('FLOW        ', 3);
    INIT FLOW(TYPEUSE, WAITING, TASKLIST, WATCH);
    INCLUDE('LOG         ', 4);
    INIT LOG(TYPEUSE, WAITING, TASKLIST, WATCH);
  END;
  INIT SCHEDULE(WAITING), CLOCKPULSE(WATCH, SCHEDULE),
       OPERATOR(TYPEUSE, TASKLIST, WATCH, SCHEDULE);
END.