(c) Software Lab. Alexander Burger
PicoLisp has a Discrete-Event
Simulation library in "@lib/simul.l".
The simulated objects (often called "Agents") are implemented as separate coroutines. These are created the normal way with co, and the library functions use yield to transfer control between them.
Only one coroutine may be running at one point in time. All others are either
A running coroutine can suspend itself, and cause another coroutine to resume, by either
The simulation can optionally run in realtime mode. In that case, it sleeps between the scheduled points in time, and accepts key strokes for user interaction.
The library consists of five global variables and four functions.
*Time*Ready*Next*RtNIL (default), or 1 for wall clock speed, 2
for double speed etc.*Keys(des [. prg])*Ready until that queue is empty. Then - if *Next is
not empty - advances the simulation to the next point in time, and resumes all
corresponding coroutines. In that case, if in realtime mode, it delays execution
as necessary, handles possible key presses, and runs prg after each
key.(pause ['cnt|sym] ..) -> any*Next for a
point in time after that number of time units. For symbolic arguments, the
current coroutine is queued into those symbol's event queues. In any case,
control is passed to the next coroutine.(event 'sym [. prg])sym to all coroutines waiting in that symbol's
event queue. As a result, these coroutines are removed from the queue and
appended to the *Ready queue, with the optional prg
body to be executed when resumed. The current coroutine continues to run.(wake 'sym [. prg])sym, by appending it to the
*Ready queue with the optional 'prg' body to be executed when
resumed. This means that if sym is currently waiting for a point in
time in *Next, it is removed from that index (i.e. the pause is
aborted). Also, if sym is waiting for signals, it is removed from
those event queues. The current coroutine continues to run.A typical DES program will start some coroutines and let them perform their initial work until they need to pause.
That means, if a given operation in the simulation is supposed to take
cnt time units, this coroutine calls pause with that
number. Or, if it depends on some signals from another part of the program, it
may call pause with those symbols. In any case - as it has nothing
else to do - it goes to sleep.
When all of them wait for a time or signal, control is returned to the main
program. All coroutines are now waiting in *Next or some signal
event queue (or in *Ready if they just gave up control with
(pause)).
The main program may now check *Next and perhaps
*Ready. If both are empty, no further events can occur, and the
program may terminate.
Otherwise, it calls des to continue with the next step(s).
At any time, a coroutine or the main program may call wake, for
example to interrupt another coroutine and cause it to throw into some other
context, or have that coroutine's pause return a special value by
running the prg argument.
Let's use DES to demonstrate the well-known Dining Philosophers Problem.
Put the following code into a file "dining.l".
# 07sep23 Software Lab. Alexander Burger
# Dining Philosophers
# pil dining.l -dining~main +
(load "@lib/simul.l")
(symbols 'dining 'simul 'pico)
(local) (*ForkA *ForkB *ForkC *ForkD *ForkE now think)
(de now (Str)
(prinl (tim$ (* 60 *Time)) " " (co) " " Str) )
(de think (Left Right)
(loop
(now "thinking")
(pause (rand 180 240)) # 3 to 4 hours
(now "hungry")
(while (or (val Left) (val Right))
(now "waiting")
(pause Left Right) )
(set Left (set Right (co)))
(now "eating")
(pause 20) # 20 minutes
(set Left (set Right NIL))
(event Left)
(event Right) ) )
(local) main
(de main ()
(symbols '(dining simul pico))
(co 'Aristotle
(think '*ForkA '*ForkB) )
(co 'Kant
(think '*ForkB '*ForkC) )
(co 'Spinoza
(think '*ForkC '*ForkD) )
(co 'Marx
(think '*ForkD '*ForkE) )
(co 'Russell
(think '*ForkE '*ForkA) ) )
It uses five global variables *ForkA through *ForkE
and five coroutines Aristotle, Kant,
Spinoza, Marx and Russell. They all run
the same function think, with their neighboring forks as
Left and Right arguments.
In think, each philospher is first "thinking" for a random time
between three and four hours. Then it gets "hungry", tries to pick up both
forks, and - if at least one of the forks is in use - starts "waiting" for a
left or right fork signal from another philosopher, and checks the forks again.
Now both forks are free. The philosopher puts himself into both (it could put
in fact any non-NIL value), then is "eating" for 20 minutes,
releases both forks by setting them to NIL, and sends a left and a
right fork signal to the neighboring philosophers possibly waiting for the
forks.
The simulation cannot deadlock, because both forks are picked up and released atomically, and because coroutines waiting for fork signals are always queued after the other waiting coroutines.
$ ./pil misc/dining.l -dining~main + 00:00 Aristotle thinking 00:00 Kant thinking 00:00 Spinoza thinking 00:00 Marx thinking 00:00 Russell thinking dining: (more (stack)) (Russell . 62) (Marx . 62) (Spinoza . 62) (Kant . 62) (Aristotle . 62) (T . 155) -> NIL dining: *Ready -> NIL dining: (idx '*Next) -> ((180 . Aristotle) (194 . Marx) (198 . Russell) (201 . Spinoza) (229 . Kant)) dining: (des) 03:00 Aristotle hungry 03:00 Aristotle eating -> NIL dining: (des) 03:14 Marx hungry 03:14 Marx eating -> NIL dining: (des) 03:18 Russell hungry 03:18 Russell waiting -> NIL dining: (do 10 (des)) 03:20 Aristotle thinking 03:20 Russell waiting 03:21 Spinoza hungry 03:21 Spinoza waiting 03:34 Marx thinking 03:34 Spinoza eating 03:34 Russell eating 03:49 Kant hungry 03:49 Kant waiting 03:54 Russell thinking 03:54 Spinoza thinking 03:54 Kant eating 04:14 Kant thinking 06:27 Aristotle hungry 06:27 Aristotle eating 06:47 Aristotle thinking 06:47 Marx hungry 06:47 Marx eating 07:07 Marx thinking 07:40 Russell hungry 07:40 Russell eating -> NIL dining: