OEP

111

Title

Modified ALT disabling sequence

Summary

Improve ALT disabling efficiency by checking guards in reverse order.

Owner

Fred Barnes <F.R.M.Barnes@kent.ac.uk>

Status

Accepted

Date-Accepted

2002-01-10

Keywords

vm alt etc

The ALT disabling sequence has been modified to perform a reverse disable in the case of "PRI ALT"s, and a reversed "PRI ALT" in the case of plain "ALT"s.

Three new instructions have been added to the instruction set which are now used in place of the three existing alternative-disable instructions ("DISC", "DIST" and "DISS"). These new instructions behave differently in that the guard will always be selected if it is ready, rather than being selected if it is ready and nothing had been ready previously, which was the default behavior with "DISC", etc. These new instructions are called "NDISC", "NDIST" and "NDISS". The input and output registers used are the same as the existing ones.

For example, the code:

ALT
  a ? x
    P
  b ? y
    Q
  c ? z
    R

will enable "a", "b" and "c" in that order, do the alternative wait if none were ready, then disable in the same sequence using the "NDISC" instruction. If "c" is ready, it will be be selected, since it is the last guard examined in the disable sequence, regardless of whether "a" and/or "b" were ready. The "PRI ALT" is handled in a similar way, except that the guards are examined in reverse. For example:

PRI ALT
  a ? x
    P
  b ? y
    Q
  c ? z
    R

will have the guards disabled in the order "c", "b" then "a". Thus, if "a" is ready, it will be selected regardless of whether "b" and/or "c" were ready.

For the most part, correct programs will run as they did. Programs which assume a "PRI ALT" for a regular "ALT" may behave incorrectly. There are some cases where this might not be immediately obvious though, for example:

TIMER tim:
INT t:
BOOL got.first:
SEQ
  got.first := FALSE
  tim ? t
  ALT
    tim ? AFTER (t PLUS 10000)
      got.first := TRUE
    tim ? AFTER (t PLUS 20000)
      IF
        got.first
          SKIP

will often find itself going "STOP", when "got.first" is false in the IF (last 3 lines). This is because a fine-grained timer is not guaranteed with the current run-time system (KRoC/Linux), if you ask to sleep for 10ms, it might be after 20ms when you wake up. In the old ALT disabling sequence, the first guard would always be selected, since the "DIST" on the second would not select that process. "NDIST" will select the second process, if that time has expired.

OEP/111 (last edited 2007-09-27 00:14:57 by ats1)