[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

occam OPUS



Dear occam-com and java-threads groups
4Jun98

I have an idea..
See attached htm-paper.

I am scared, I do have an opportunity to make
a fool of myself now..

Cheers, Xyvind

Oyvind Teig, Autronica, Trondheim, Norway
Oyvind.Teig@xxxxxxxxxxxx
Tel.: +47 73 58 12 68
Fax.: +47 73 91 93 20
<html>

<head>
<meta HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=ISO-8859-1">
<meta NAME="GENERATOR" CONTENT="Microsoft FrontPage 3.0">
<title>Timesliced loops</title>
</head>

<body>

<h1>Timesliced loops</h1>

<blockquote>
  <dl>
    <dt>Author:</dt>
    <dd>Xyvind Teig</dd>
    <dd>Autronica</dd>
    <dd>7005 Trondhiem Norway<br>
      <a href="mailto:oyvind.teig@xxxxxxxxxxxx";>oyvind.teig@xxxxxxxxxxxx</a></dd>
    <dt>Date:</dt>
    <dd>4June98</dd>
    <dt>Disclaimer:</dt>
    <dd>I'm throwing this paper at you in the spirit of <a
      href="http://www.redhat.com/redhat/cathedral-bazaar/cathedral-bazaar.html";>The Cathedral
      and the Bazaar</a>. This is an excuse for making it unstructured and to cover my shallow
      thinking and non-pedagogical presentation.</dd>
  </dl>
</blockquote>

<h2>Background</h2>

<blockquote>
  <p>A loop is considered harmful. It has, so far, caused the world to need preemptive
  scheduling.</p>
  <p>From studying SPoC I have learnt a lot. I have learnt that if I <em>call</em> a PROC
  (in SEQ) that would contain descheduling points, that PROC is started like a process and
  the caller is set on halt to wait for the PROC to return. I don't know why they do this,
  but I guess the state machines thus built need not be hierarchical. So it is for
  simplicity. Another reason may be that this <em>call</em>, which should have been one
  level up on the stack cannot be done since any process (that needs scheduling) must do a
  simple <em>return</em> to get back to Scheduler. So both the caller and the callee are at
  the same stack level.</p>
</blockquote>

<h2>Automatic timeslicing of loops</h2>

<blockquote>
  <p>Now consider The World as a place where preemptive scheduling, if required, is done by
  hardware. The scheme is called interrupt. Interrupt routines may send data on a channel.
  All other scheduling is done non-preemptively.</p>
  <p>The SPoC scheme for <em>calling</em> processes could be used in The World. Any loop, of
  any kind, could be considered a block to be started by the system as a separate process. </p>
  <p>The good thing is that this way we need not rewrite all the world's programs.</p>
  <p>The bad thing is that a non-terminating loop cannot be caught under a non-preemptive
  scheduling regime, only interrupts will disturb it: Scheduler is forever in shadow-lands.
  Most loops terminate within some time. I guess it is because of naughty loops that the
  world has invented preemptive scheduling: to get at least the other processes running.</p>
</blockquote>

<h2>Timesliced loops</h2>

<blockquote>
  <p>Now, let us define The World' as a subset of TheWorld: an embedded application, or a
  machine where all programs actually may run under this non-preemptive regime. We need to
  remove all non-structured loops. Non-structured in scheduling sense.</p>
  <p>One could argue that this is a dimension that should not be handled by any programmer.
  It is simply wrong. Perhaps it is time to rethink this. So much complexity is introduced
  when we start using Threads, Tasks, Processes or the sort. All we ask for is a structured
  looping scheme. The added complexity for the programmer will make multitasking so much
  simpler. Discarding how the interrupt handler would connect to this world, we wouldn't
  even need atomic test&amp;set instructions. And we would not need complex monitors with
  subtle behaviour. And CSP could be implemented easily, at least it looks like it when I
  view SPoC code. I have a feeling that the Oberon operating system has non-preemptive
  scheduling.</p>
  <p>The transputer had descheduling points at the end of every loop, since the instruction <code><samp>lend</samp></code>
  was a descheduling instruction. SPoC does not deschedule at the end of every loop, speed
  disallowing. </p>
  <p>The paragraph below describes syntactically what we're after: </p>
  <pre>WHILE TRUE
&nbsp; ALT
&nbsp;&nbsp;&nbsp; channel ? input
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ...
&nbsp;&nbsp;&nbsp; WHILE (w &lt; W)
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ...
&nbsp;&nbsp;&nbsp; SEQ i = 0 FOR N
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; x := x + 1
&nbsp;&nbsp;&nbsp; timer &amp; clock ? AFTER timeout
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ...</pre>
  <p>Fig. 1 - Looping as an ALT guard (impossible) </p>
  <p>We want looping with timeout, or looping for a certain amount of time. Semantically the
  idea above is impossible: a guard of an ALT is &quot;passive&quot;. Waiting for a channel
  and waiting for a timeout is done passively. The TRUE AND SKIP is a semi-active element of
  an ALT. The example in fig.1 would, provided the timeout could actually deactivate a
  running loop, have problems with how far the sequence counters have advanced. The syntax
  could stile give meaning if we say that, after timeout, the loop would continue from where
  it left till the loop had finished. Also, we would not like the SEQ's sequence counter not
  to be in scope at timeout, so it suites us well to have the syntax that we tried to define
  above. </p>
  <p>We need to define a timesliced loop. It could look like this: </p>
  <pre>INT time:
INT w,W:
SEQ
  clock ? time
  time := time PLUS timeout
  w, W := 0, #7fffffff
  OPUS
    WHILE (w &lt; W)
      w := w + 1 -- loop body
    clock ? AFTER time
      time := time PLUS Timeout
    FINAL
      SKIP -- Completed
    TRUE
      SKIP -- Loop not originally taken</pre>
  <p>Fig. 2 - Looping with new OPUS keyword</p>
  <p>A new keyword OPUS is introduced. It has a rather unusual semantics.</p>
  <p>The OPUS keyword will run whichever branch is valid. Above, the first thing to do is to
  run the WHILE loop. This will run until it is disturbed by the timeout. The program will
  then loop around and get up to the OPUS statement again. It will do this directly from the
  timeout statement, not via any outer scope. The OPUS statement will deschedule the
  process. Whenever the scheduler decides so, the process will be rescheduled, and the next
  part of the WHILE loop will be computed, until it is finished. Then the FINAL clause will
  run and the OPUS clause exited. If no branch is taken, the TRUE will be taken. This will
  happen if the original (w&lt;W) is not evaluated to TRUE.</p>
  <p>Semantic checks by the compiler, scope rules etc. I have not handled.</p>
</blockquote>

<h2>Nested timesliced loops</h2>

<blockquote>
  <p>Nested timesliced loops probably need to be started like SPoC called processes. Which
  reminds us that actually implementation of Fig. 2 is impossible if the OPUS statements
  does not spawn two separate processes, one for time-outs and one for the rest. This may
  kill any actual implementation, even if the idea may be sound. </p>
  <p>Another problem is how one level should tell the calling level that it has timed out
  its loop. Does it look like we need an exception handler scheme? I don't know.</p>
  <p>We could, of course, add an EXCEPTION keyword that could catch things like this.</p>
</blockquote>

<h2>User knowledge of loop</h2>

<blockquote>
  <p>A problem with this regime is that the user has to define, in some way or the other, a
  maximum running time of the loop. Adding a next timeout statement to Fig. 2 would do it:
  since we actually require non-terminated loops to be caught. Portability would suffer,
  maybe even if we invented a relative time scaling or something along that line..</p>
  <p>Maybe adding a maxium time for loops would make them more predictable, not less?</p>
</blockquote>

<h2>Syntax</h2>

<blockquote>
  <p>The syntax described in Fig. 2 could be completely different. Probably the syntax would
  need to look much more like the loop construct of particular languages, so that changing
  all loops into timesliced loops may be done by a precompiler.</p>
</blockquote>

<blockquote>
  <pre>INT w,W:
SEQ
  w, W := 0, #7fffffff
  OPUS
    WHILE (w &lt; W)
      w := w + 1 -- loop body
    TIMESLICED(100ms)
      SKIP
    TIMEOUT(60s)
      SKIP -- Automatic propagation to higher level's EXCEPTION
    COMPLETED
      SKIP -- Completed ok
    EXCEPTION
      SKIP -- From here or lower level, propagate to higher level, if necessary
    TRUE
      SKIP -- Loop not originally taken</pre>
  <p>Fig. 3 - Full timesliced looping</p>
  <p>We would probably want to introduce several more keywords to occam, to make the
  construct safer. Fig. 3 would capture some of the ideas.</p>
</blockquote>

<h2>Postscript</h2>

<blockquote>
  <p>OPUS is singular for OPERA: a kind of cooperating work.</p>
  <p>A timesliced loop like this would be needed for all loops that may hog the machine. In
  occam this would be WHILE, and SEQ i = n FOR N, but I'm uncertain about the latter. Maybe
  removing WHILE from the language would solve it for occam's case, and this paper could be
  thrown where it belongs.</p>
  <p>This whole paper probably shows that I haven't understood anything about language and
  algorithmic design. And I probably don't know that mr. NN suggested this in 196? and he's
  now definitively <em>returned</em> to <em>his</em> Scheduler.</p>
</blockquote>
</body>
</html>