A TIMED EVENT NETWORK SCHEDULER IN FORTH
Forth is particularly well suited to the development of real-time kernels
Gregory R.S. Ilg and R.J. Brown
Gregory Ilg and R.J. Brown are consultants involved in the development of microprocessor- and minicomputer-based real-time systems. Mr. Brown can be reached at Elijah Laboratories Inc., P.O. Box 833, Warsaw, KY 41095. Mr. Ilg can be reached at Computer Strategies, Inc., P.O. Box 180, Evon Lake, OH 44012.
The Timed Event Network Scheduler (TENS) is a scheduler we have developed that is well suited for real-time process control and industrial automation applications. One of its main features is that it has its own high-level language, which is an extension of Forth, in which dependencies among different events are specified. When any action or time duration in the system is altered, other modifications are not necessary in order to maintain and preserve these dependencies. At compilation time, the critical path through the network and its path length (measured in units of time) are displayed. Because of this approach, you can easily see which processes need to be streamlined in order to increase system throughput. The TENS paradigm was inspired by the critical path method (CPM) scheduling techniques used to manage large projects.
We implemented TENS using Laboratory Microsystems' UR/FORTH, Version 1.03, under PC-DOS 3.3 running on several XT- and AT-compatible computers. So far, TENS has been used to control the time sequencing of the fluid and pneumatic valves in a piece of complex medical equipment. Our intent was for a mechanical engineer to be able to tune the system timing without the aid of a software engineer. The results were quite favorable. The mechanical engineer quickly grasped the concepts of network sequencing and was able to develop some of the network topology without software engineering assistance and was easily able to tune the timing of the network to meet stringent design requirements.
This article describes the TENS system and provides examples of its use. The programs shown in Listings One and Two, page 92, do, however, make use of several Forth packages that, because of their length, are not reproduced here. The packages are included in the companion DDJ source disk and in the DDJ Forum on CompuServe. The TENS system can be used for any purpose as long as credit is given to Elijah Laboratories.
Description of TENS
Each node in a TENS network has associated with it an action to be performed when the node is first activated, a delay time, and an action to be performed after the delay time. The node is then exited. Both actions behave like normal Forth colon definitions and may use any number of normal Forth words.
Each node knows its immediate successors and predecessors in the network and cannot be activated until all its predecessors have exited. When a node exits, it informs all its successors that it has done so. Each node keeps track of which of its predecessors have already exited by means of a flag for each predecessor. When notified, this node examines all these flags to determine if it is now eligible to run. When the conditions for node activation have been met, all the flags are cleared before the node is activated.
Each TENS network is distinguished by a single entry and a single exit, called the head and tail, respectively. Between the network head and tail there may be zero or more nodes, subject to the constraint that there are no cycles. (A cycle would exist in the situation that an ultimate successor of a node could be that node's predecessor.) A network is known by its head, and typically the head has a name that appears as a Forth word in the dictionary. To run such a network, you execute its name as you would any other Forth word. These networks can in turn be used to construct larger networks.
A TENS Example
Let's suppose TENS were used in the development of the Egg-Master vending machine illustrated in Leo Brodie's book entitled Thinking FORTH. (Figure 1 is an adoption of the concept.) One of the networks it might use could be represented as shown in Figure 2 and Listing One. This network is responsible for handling the omelette selection available on the Egg-Master. Similar networks would handle the other selections. The word EGG_MASTER in Listing One handles the selection of which network to run and would be hooked to the power-up vector of the machine. The network in Figure 2 , whose head is Start-Cook-Omelette, runs the nodes Preheat-Griddle and Mix-Omelette in parallel. The node Pour-Mixture waits for both the nodes Mix-Omelette and Preheat-Griddle to complete before it runs. This is obviously necessary because the ingredients must be mixed and the griddle must be hot before the mixture is poured onto the griddle.
The node Mix-Omelette' in the Cook-Omelette network is itself a network that is a subnetwork of Cook-Omelette, but it can also be a subnetwork of other networks (such as a Cook-Scrambled network, should the Egg-Master Supreme ever make it out of the R&D lab). This is the network analogy to the linear-threaded concept of factoring. Because factoring is fundamental to writing good Forth code, we felt it was important to carry this practice into the parallel data-flow paradigm. TENS permits factoring of networks, thereby increasing their reusability and test-ability.
Run-Time Data Structures
Each network is implemented by a network-head data structure that contains pointers to the initial and terminal nodes of the network. The network head also provides storage for the critical path length.
Each node is implemented as a compound data structure. It is composed of a fixed area containing the CFAs of the entry and exit action words, the delay time, its path length from the start node, a pointer to a linked list of successors, and a variable-length array of pointers to its predecessors. This array is terminated with a NULL pointer. Each node in the linked list of successors is implemented as a pair of cells. The first cell points to the next node in the linked list, and the second cell points to the successor node in the TENS network (see Figure 3).
Run-Time Processing
Each TENS network is created by a CREATE DOES> word whose DOES> clause references the word TENS (see Listing Two). This word sets a trapdoor with CATCH; entry-action throws back to it when the entire network has finished executing. After this trapdoor is established, the timer is started and a pointer to the first node is passed to entry-action, which throws back to the trapdoor if the pointer is NULL. If it is not NULL, then the entry-action CFA is performed. Next, this node is put on the timer queue for the required delay time.
The timer queue is managed in accord with "An Efficient Algorithm for Large Priority Queues," by R. J. Brown (DDJ, June 1987). The priority is the dispatch time, which causes each node to be removed from the queue when its dispatch time occurs. As the flow of control proceeds through the network, there will be many nodes on the timer queue.
When a node is dispatched from the timer queue, its pointer is passed to exit-action, which causes that node's Exit-Action to be performed. At this point, the node is exiting, and its successors are notified. If there are no successors, then the entire network has finished running and the trapdoor is thrown back to. As each node receives notification, it checks to see if all its other predecessors have also exited. If they have, then that node is activated. This activation and exiting process is applied iteratively as the TENS scheduler traverses the network. When subnetworks are present, recursion occurs because more than one network is active at a time.
Although TENS implements a data-flow paradigm for parallelism, it is not a multitasking system. All of the parallelism results from having active nodes on the timer queue waiting for the delay interval between their Entry-Action and their Exit-Action. For this reason, these actions should have negligible processing time relative to the delay time.
Compile-Time Processing
During compilation the run-time data structures must be built (see Listing Two). The network head is instantiated by the defining word NETWORK, which leaves a pointer to this head on the stack for use by END-NETWORK.
Each node in the network can know only its predecessors at compile time because Forth does not generally allow forward references. After all nodes of the network have been compiled, the word END-NETWORK lexically delimits the entire network and causes additional compile-time processing to occur.
The first (and the only essential) post-processing operation is the generation of successor links. This is performed by a depth-first traversal of the network, starting at the tail and penetrating toward the head. Each pair of cells on a successor list is allocated as it is needed.
Once the successor links have been established, the length from the head to each node is computed by a similar depth-first search and then is saved with that node. Therefore, the critical path length will be found in the tail node.
The names of the nodes on the critical path are displayed starting with the tail. By choosing the predecessor with the largest path length, we are able to stay on the critical path. As each node on the critical path is encountered, its name (as stored in the dictionary header) is printed on the screen.
As a result of this compile-time post-processing, not only is the network linked in both directions but also the length of the critical path is computed and the names of the nodes it contains are displayed. The length of the critical path is a useful statistic for the designers because only those nodes that are actually on the critical path can have an effect on the critical path length. Thus, designers need direct their tuning efforts only to these nodes -- by changing the delay time of any node, they can affect the time required to run the entire network. When the duration of a node is changed, it is not necessary to change the times of any other nodes to keep the process in step. This is the beauty of the network-scheduling data-flow paradigm.
The display of the critical path and its length, together with the cell in each node to hold that node's path length, can be removed after development to produce a cross-compiled system without the extra overhead if so desired.
Conclusion
By having nontrivial processing done at compile time, a large amount of work is factored into the compilation of the network instead of into its execution. The Forth language is particularly well suited to the implementation of this approach because the full facilities of the language are available not only to execute the program but also to build that same program. Most other higher-level languages have no such facility. The C language has a limited compile-time processing facility. Most good assemblers have a macro capability, but these are separate languages distinct from the language that specifies the run-time behavior of the program. Lisp is the only other well-known language that has as good a compile-time processing facility; however, Lisp is generally too slow to be effective in real-time applications on microprocessors. Forth is deliberately designed to provide real-time performance on micros.
Bibliography
Brodie, Leo. Thinking FORTH. Engelwood Cliffs, N.J.: Prentice Hall, 1984.
Brown, Robert Jay. "An Efficient Algorithm for Large Priority Queues." DDJ 128 (June 1987).
_A Timed Event Network Scheduler in Forth_ by Gregory Ilg and R.J. Brown
[NOTE: FORTH SCREENS ACCOMPANY THESE LISTINGS]
[LISTING ONE]
Copyright © 1989, Dr. Dobb's Journal<a name="0066_000b">
\ Hypothetical Network To Handle Omelette Selection On
\ Brodie's Egg-Master
CONSULT TENS \ Timed Event Network Scheduler
184 EQU ticks/10secs \ system clock time constant
: MS ( miliseconds -- ticks ) \ time units conversion
184 10000 */ ;
: sec ( seconds -- ticks )
184 10 */ ;
: min ( minutes -- ticks )
60 * sec ;
( Define stubs for un-implemented words... )
STUB[ Break-Egg seasoning-valve open
close mixer on
off griddle pour-valve
wait-for-coins Cook-Fried Cook-Poached
Cook-Hard-Boiled Cook-Benedict ]
( Define buttons as an enumeration set... )
1 ENUM[ Fried-button
Poached-button
Hard-Boiled-button
Benedict-button
Omelette-button ]
: read-a-button Omelette-button ; \ always choose "omelette"
: None ; IMMEDIATE ( noise word to improve readability )
NETWORK Mix-Omelette \ subnetwork also used
\ in fancier omelettes
NODE Start-Mix-Omelette \ dummy for single entry
Predecessors NIL
Entry-Action None
Delay 0 sec
Exit-Action None
END-NODE
\ Wrap up subnetwork Break-Egg. Break-Egg not detailed here
NODE Crack-Egg
Predecessors Start-Mix-Omelette
Entry-Action Break-Egg
Delay 0 sec
Exit-Action None
END-NODE
\ concurrent with Crack-Egg
NODE Add-Seasoning
Predecessors Start-Mix-Omelette
Entry-Action seasoning-valve open
Delay 100 MS
Exit-Action seasoning-valve close
END-NODE
NODE Blend
Predecessors Crack-Egg
Add-Seasoning
Entry-Action mixer on
Delay 3 sec
Exit-Action mixer off
END-NODE
END-NETWORK ( Mix-Omelette )
NETWORK Cook-Omelette \ net head to process...
\ ...Omelette-button
NODE Start-Cook-Omelette \ dummy for single entry
Predecessors NIL
Entry-Action None
Delay 0 sec
Exit-Action None
END-NODE
NODE Preheat-Griddle
Predecessors Start-Cook-Omelette
Entry-Action griddle on
Delay 30 sec
Exit-Action None
END-NODE
\ subnetwork...
NODE Mix-Omelette'
Predecessors Start-Cook-Omelette
Entry-Action Mix-Omelette
Delay 0 sec
Exit-Action None
END-NODE
NODE Pour-Mixture
Predecessors Preheat-Griddle
Mix-Omelette'
Entry-Action pour-valve open
Delay 2 min
Exit-Action pour-valve close
griddle off
END-NODE
END-NETWORK ( Cook-Omelette )
\ This word is hooked to the power-up vector on the
\ Egg-Master vending machine.
: EGG_MASTER ( -- )
BEGIN wait-for-coins read-a-button CASE
Fried-button OF Cook-Fried ENDOF
Poached-button OF Cook-Poached ENDOF
Hard-Boiled-button OF Cook-Hard-Boiled ENDOF
Benedict-button OF Cook-Benedict ENDOF
Omelette-button OF Cook-Omelette ENDOF
ENDCASE AGAIN ;
<a name="0066_000c"><a name="0066_000c">
<a name="0066_000d">[LISTING TWO]<a name="0066_000d">
\ TIMED EVENT NETWORK SCHEDULER
\ Copyright (c) 1988 Elijah Laboratories Inc.
( This package makes use of a number of programs that are
not detailed here. The word CONSULT is used to load these
packages. The packages are included in the companion DDJ
source disk. )
CONSULT STRUC \ structure definitions
CONSULT PRIQUE \ priority queue manager
CONSULT MACROS \ for the evaluator
CONSULT BALLS \ for backtracking control
CONSULT XSHEETS \ transient storage words
CREATE TQ NIL , \ the timer queue
: nothing ; *MITT* SETQ nothing \ no default THROW handler
6 INFLATE BALL tens.ball \ trap door for exit
BALL te.ball \ ditto
( A timed event network is a linked data structure composed of
the following timed event nodes. )
sizeof pq struc TEnode \ a timed event node
1w TEnode word-1 \ execute before delay
1w TEnode delay \ # ticks to delay
1w TEnode path-length \ path length from start
1w TEnode word-2 \ execute after delay
1w TEnode ^Succ's \ ptr to successor list
0 TEnode Pred's \ start of predecessor list
( These words start and stop the timer cell, and fetch its
value, and add its value to the top-of-stack, thereby
converting a time interval into an absolute time value. )
VARIABLE now \ the timer cell
: start-now ( -- ) -2 now ! now TICKER DROP ; \ start the timer
: stop-now ( -- ) now -TICKER ; \ stop the timer
: now@ ( -- #tics ) now @ NEGATE ; \ fetch the timer
: now+ ( delay -- time ) now@ + ; \ add timer value
( This word defines the processing that occurs when a node is
activated. This consists of performing the entry action
routine and enqueueing for the required delay time. )
: entry-action ( node -- ) \ start up a node
>R \ save node pointer
R@ NIL = IF T tens.ball THROW THEN \ if none, we're done!
R@ BODY> >NAME CR .NAME \ display its name
R@ word-1 PERFORM \ do pre-delay stuff
R@ delay @ now+ R@ key ! \ figure dispatch time
TQ R> pq-enque ; \ put on timer queue
( This word waits until the head of the timer queue is past
its dispatch time, and then dequeues the head element from the
timer queue for subsequent processing. )
: wait-till ( -- node ) \ take next node off queue
TQ @ 0= ABORT" Empty timer queue "
BEGIN TQ @ key @ now@ < UNTIL \ wait until its time
TQ pq-deque \ then remove it
." DQ " ;
( The following structures are used in the word "notify". The
first is passed as a parameter block, and the second is SPREAD
as a SHEET. )
0 struc n.parm \ passed parameters...
1w n.parm n.pred \ ptr to predecessor
1w n.parm n.succ \ ptr to its successor
0 struc n.temp \ temporaries...
1w n.temp n.trig \ trigger indicator
( This word searches the predecessor list of a node for a
match with the cfa of a completing predecessor. When the match
is found, the low order bit of the predecessor address is set
as a flag to indicate that that predecessor has completed. If
all such flags are set, "n.trig" is set to trigger the node. )
: set-done-flag ( _n.temp -- _n.temp ) \ set pred's done fg
AT #[ parm n.parm n.succ ]+ SH@ Pred's \ pt to succ's preds
BEGIN DUP @ ?DUP WHILE \ for all preds
AT #[ parm n.parm n.pred ]+ SH@ = \ we got a match?
IF DUP 1 |! THEN \ yes, set done flag
DUP @ AT n.trig SH@ AND \ figure new trigger
AT n.trig SH! w+ REPEAT DROP ; \ save it & continue
( This word clears all the done flags that were set to trigger
the activation of a node. This word is performed just prior to
activating the node, thus preparing it for re-triggering at a
later time. )
: clear-done-flags \ clear succ's done flags
AT #[ parm n.parm n.succ ]+ \ point to successor
SH@ Pred's \ point to his predecessors
BEGIN DUP @ ?DUP WHILE \ for all predecessors
[ 1 NOT ]# AND OVER ! \ clear its done flag
w+ REPEAT ; \ loop to end of list
( The "notify" word tells a successor to a node that one of
its predecessors has completed. If all of its predecessors
have completed, then that successor node is started. )
: notify ( pred succ -- ) \ notify a successor
sizeof n.temp SPREAD \ make room for temps
1 AT n.trig SH! \ cock the trigger
set-done-flag \ set pred's done flag
AT n.trig SH@ IF \ has succ been triggered?
clear-done-flags \ yes, clear his done flags
CRUSH NIP entry-action \ & start him up!
ELSE CRUSH 2DROP THEN ; \ no, just return...
( This word is executed after a node has been removed from the
timer queue after waiting its required delay time. It causes
the exit action routine for that node to be performed, and then
notifies all the successors of that node that it has completed
execution. )
: exit-action ( node -- ) \ complete a node
DUP word-2 PERFORM \ do after delay stuff
DUP ^Succ's DUP @ NIL = \ point to successor chain
IF T tens.ball THROW THEN \ if none, we're done!
BEGIN @ ?DUP WHILE \ for all his successors
2DUP w+ @ notify \ notify them he's done
REPEAT DROP ; \ then clean up & exit
( This is the "Timed Event Network Scheduler", the entry point
for the DOES> word of a timed event network. Running such a
network is done by executing the name of the network, which
calls TENS with the address of the network list head. )
: TENS ( net -- ) \ run a timed event net
tens.ball CATCH IF \ exit via trap door?
DROP EXIT THEN \ yes, stop timer, exit
start-now @ entry-action BEGIN \ no, start first node
wait-till exit-action AGAIN ; \ wait, then finish it
( This word links a node into the successor lists of all of
its predecessors. After this has been done recursively for
all the successors of that node, ad infinitum, then the entire
event network will be linked both forwards and backwards. )
F: link-to-pred \ declare forward reference
: link-to-pred's ( node -- ) \ fix up forward lnks in network
DUP Pred's >R \ point to it predecessor list
BEGIN R@ @ ?DUP WHILE \ for all its predecessors...
OVER SWAP link-to-pred \ link this node to its pred
R> w+ >R REPEAT \ point to next pred ptr
DROP R> DROP ; \ tidy up stacks
R: link-to-pred ( node pred -- ) \ ping pongs with word above
DUP >R \ remember predecessor ptr
^Succ's \ point to successor ptr
BEGIN DUP @ ?DUP WHILE \ for all successors...
NIP DUP w+ @ 2 PICK = \ duplicate?
IF R> 3DROP EXIT THEN \ yes, skip this node
REPEAT \ until end of list
HERE SWAP ! \ append new CONS cell
NIL , \ CDR is NIL
, \ CAR is successor node
R> link-to-pred's ; \ fix his predecessors too!
( This word kicks off the action to reverse link the event
network by passing the address of the first node to the
recursive network traversal algorithm. It takes the address
of the network list head as its parameter. )
: fix-Succ's ( head -- ) \ generate successor lists
w+ @ \ point to last node
link-to-pred's ; \ link it to its predecessors
( This word recursively traverses the network accumulating the
maximum path length to each node. This length from the first
to last nodes is the critical path length, or network delay. )
: set-path-len ( ^node old-path-length -- )
SWAP >R \ save this node's pointer
R@ delay @ + \ add this delay to old len
R@ path-length @ \ get current len
MAX DUP \ new len is max of the two
R@ path-length ! \ save new len
R> Pred's >R \ point to pred ptrs list
BEGIN R> DUP w+ >R @ ?DUP WHILE \ for all predecessors...
OVER RECURSE REPEAT \ set their path length too
DROP R> DROP ; \ clean up and exit
( This word calls the recursive network traversal routine to
compute the length of the critical path through the network.
The result is stored in the network's list head. )
: set-path-lengths ( nethead -- )
DUP w+ @ \ point to last node
0 \ initial path length is zero
set-path-len \ recursively set path lengths
DUP @ path-length @ \ get computed critical path length
SWAP 2 w*+ ! ; \ save it in network head
( This word displays the name of a network and its critical
path length in milliseconds, It is used as a tuning aid. )
: .pathlen ( nethead -- ) \ display critical path length
CR \ start on a new line
." Critical path of " \ indentify it
DUP BODY> >NAME .NAME \ show network name
." is " \ more verbiage
2 w*+ @ \ fetch length in ticks
10 184 */ \ convert to seconds
. \ display the number
." seconds long. " \ more verbiage
CR ; \ and a new line
( This word displays the critical path on the screen at
compilation time to facilitate tuning. )
: .critpath ( nethead -- )
." Critical path is: " w+ @ \ point to last node
BEGIN ?DUP WHILE \ for each node on critpath
CR 4 SPACES \ indent to look pretty
DUP BODY> >NAME .NAME \ display its name
Pred's >R 0 0 BEGIN \ for each predecessor
R> DUP w+ >R @ \ get a predecessor pointer
?DUP WHILE \ as long as they exist
DUP path-length @ \ get its path length
2 PICK OVER MAX \ take maximum of old & new
OVER = IF 2SWAP THEN \ update max & ptr
2DROP REPEAT R> 2DROP \ discard excess baggage
REPEAT CR ; \ loop till done
( The Top-of-Stack is used by END-NETWORK to generate the
successor lists for all of the nodes in the network. For this
reason, the last node instantiated *MUST* be the unique
terminal node for the network. Likewise, the first node
instantiated *MUST* be the unique initial node for the
network. )
: END-NETWORK ( head first last -- )
ROT >R SWAP \ save head, put first on top
R@ ! \ save first in head
R@ w+ ! \ save last in head
R@ fix-Succ's \ generate successor lists
R@ set-path-lengths \ compute critical path length
R@ .pathlen \ display critical path length
R> .critpath ; \ display critical path
( The following word is used to begin the definition of a
timed event network. The network is terminated by the word
END-NETWORK. )
: NETWORK ( -- ) \ begin a timed event network
CREATE HERE \ give it a name and remember where
NIL , NIL , \ initialize first & last pointers
NIL NIL \ initialize 2 pointers on stack
0 , \ initialize critical path length
DOES> TENS ; \ runs the scheduler when called
( This is the format for declaring a node in a TENS network.
NODE <node-name>
Predecessor pred1 ... predn
Entry-Action word1 ... wordn
Delay n \ tics
Exit-Action word1 ... wordn
END-NODE
)
NIL EQU ^NODE \ pointer to current node
: NODE ( -- ) \ define network step node
CREATE \ make a dictionary header
HERE EQU ^NODE \ remember where it is
sizeof TEnode ALLOT \ make room for it
0 ^NODE path-length ! \ initialize path length
NIL ^NODE ^Succ's ! \ terminate successor chain
DROP ?IF ^NODE \ set 1st
ELSE ^NODE DUP THEN ; \ & last pointers
: Predecessors \ start predecessor list
DUP \ insert cushion
te.ball CATCH NIL = \ to end predecessor list
IF BEGIN DEPTH >R EVAL \ mark stack & eval token
DEPTH R> \ did eval return a value
- 1 = IF , \ yes, store it as a pred
ELSE \ no, more than one value?
T ABORT" Illegal Predecessor " \ yes, abort with a msg!
THEN \ no value, treat as comment
AGAIN THEN \ build predecessor list
DROP \ remove cushion
CP @ ^NODE word-1 ! \ make entry action header
HERE PFA, nest JMP, \ stuff cfa and pfa into it
] ; \ compile entry action
: Entry-Action NIL , T te.ball THROW ; \ end predecessor list
: Delay \ specify delay time
COMPILE EXIT \ last word in entry action
[COMPILE] [ \ set interpret state
; IMMEDIATE \ must run while compiling
: Exit-Action \ specify exit action
^NODE delay ! \ save delay time
CP @ ^NODE word-2 ! \ make exit action header
HERE PFA, nest JMP, \ stuff cfa & pfa into it
] ; \ force compile state
: END-NODE \ terminate node definition
COMPILE EXIT \ last word in exit action
[COMPILE] [ \ set interpret mode
; IMMEDIATE \ must run while compiling
