[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
occam OPUS
- To: occam-com@xxxxxxxxx, java-threads@xxxxxxxxx
- Subject: occam OPUS
- From: Oyvind Teig <Oyvind.Teig@xxxxxxxxxxxx>
- Date: Thu, 4 Jun 1998 14:03:44 +0200
- Alternate-recipient: Allowed
- X400-mts-identifier: [/PRMD=autronica/ADMD=TELEMAX/C=NO/;5143 98/06/04 14:03]
- X400-originator: Oyvind.Teig@xxxxxxxxxxxx
- X400-received: by mta mail.autronica.no in /PRMD=autronica/ADMD=TELEMAX/C=NO/; Relayed; Thu, 4 Jun 1998 14:03:44 +0200
- X400-recipients: non-disclosure:;
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&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
ALT
channel ? input
...
WHILE (w < W)
...
SEQ i = 0 FOR N
x := x + 1
timer & clock ? AFTER timeout
...</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 "passive". 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 < 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<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 < 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>