(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, 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 the
corresponding coroutine. 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)
(off *Rt) # Realtime mode off
(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: *Next -> ((229 . Kant) ((201 . Spinoza) ((198 . Russell) ((194 . Marx) ((180 . Aristotle)))))) 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 40 (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 07:41 Kant hungry 07:41 Kant eating 07:47 Spinoza hungry 07:47 Spinoza waiting 08:00 Russell thinking 08:01 Kant thinking 08:01 Spinoza eating 08:21 Spinoza thinking 09:57 Aristotle hungry 09:57 Aristotle eating 10:17 Aristotle thinking 10:41 Marx hungry 10:41 Marx eating 11:01 Marx thinking 11:45 Spinoza hungry 11:45 Spinoza eating 11:50 Russell hungry 11:50 Russell eating 11:52 Kant hungry 11:52 Kant waiting 12:05 Spinoza thinking 12:05 Kant eating 12:10 Russell thinking 12:25 Kant thinking 13:57 Aristotle hungry 13:57 Aristotle eating 14:02 Marx hungry 14:02 Marx eating 14:17 Aristotle thinking 14:22 Marx thinking 15:40 Russell hungry 15:40 Russell eating 15:46 Spinoza hungry 15:46 Spinoza eating 15:52 Kant hungry 15:52 Kant waiting 16:00 Russell thinking 16:06 Spinoza thinking 16:06 Kant eating 16:26 Kant thinking 17:52 Aristotle hungry 17:52 Aristotle eating 18:12 Aristotle thinking 18:22 Marx hungry 18:22 Marx eating -> NIL dining: