1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
|
<!--
# VIP @lib/vip/html.l
# 29jul25 Software Lab. Alexander Burger
-->
<!DOCTYPE html>
<html lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Discrete-Event Simulation</title>
<link rel="stylesheet" href="doc.css" type="text/css">
</head>
<body>
<a href="mailto:abu@software-lab.de">abu@software-lab.de</a>
<h1>Discrete-Event Simulation (DES)</h1>
<p style="text-align: right">(c) Software Lab. Alexander Burger
<p>PicoLisp has a <a
href="http://en.wikipedia.org/wiki/Discrete-event_simulation">Discrete-Event
Simulation</a> library in <code>"@lib/simul.l"</code>.
<p><ul>
<li><a href="#impl">Implementation</a>
<li><a href="#glob">Global Variables</a>
<li><a href="#fun">Functions</a>
<li><a href="#use">Usage</a>
<li><a href="#xmpl">An Example</a>
</ul>
<p><hr>
<h2><a id="impl">Implementation</a></h2>
<p>The simulated objects (often called "Agents") are implemented as separate <a
href="http://software-lab.de/doc/ref.html#coroutines">coroutines</a>. These are
created the normal way with <a
href="http://software-lab.de/doc/refC.html#co">co</a>, and the library functions
use <a href="http://software-lab.de/doc/refY.html#yield">yield</a> to transfer
control between them.
<p>Only one coroutine may be running at one point in time. All others are either
<p><ul>
<li>ready to run,
<li>waiting for the next scheduled point in time, and/or
<li>waiting for one or several specific signals (events).
</ul>
<p>A running coroutine can suspend itself, and cause another coroutine to
resume, by either
<p><ul>
<li>passing control to the next coroutine, or
<li>pausing for a given amount of time and/or waiting for signals.
</ul>
<p>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.
<p>The library consists of five global variables and four functions.
<p><hr>
<h2><a id="glob">Global Variables</a></h2>
<dl>
<dt><code>*Time</code></dt>
<dd>Simulated system time since the start of the simulation. It can be in any
unit, but should be in milliseconds if in realtime mode.</dd>
<dt><code>*Ready</code></dt>
<dd>Queue of coroutines ready to run.</dd>
<dt><code>*Next</code></dt>
<dd><a href="http://software-lab.de/doc/refI.html#idx">idx</a> tree of
coroutines pausing for a given time.</dd>
<dt><code>*Rt</code></dt>
<dd>Realtime: Either <code>NIL</code> (default), or 1 for wall clock speed, 2
for double speed etc.</dd>
<dt><code>*Keys</code></dt>
<dd>Holds possibly queued key presses (only in realtime mode).</dd>
</dl>
<p><hr>
<h2><a id="fun">Functions</a></h2>
<dl>
<dt><code>(des [. prg])</code></dt>
<dd>Performs one discrete-event simulation step. It first runs all coroutines in
<code>*Ready</code> until that queue is empty. Then - if <code>*Next</code> 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 <code>prg</code> after each
key.</dd>
<dt><code>(pause ['cnt|sym] ..) -> any</code></dt>
<dd>Waits for events (i.e. a time span elapsed or a signal arrived). For a
numeric argument, the current coroutine is scheduled in <code>*Next</code> 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.</dd>
<dt><code>(event 'sym 'exe)</code></dt>
<dd>Sends the signal <code>sym</code> to all coroutines waiting in that symbol's
event queue. As a result, these coroutines are removed from the queue and
appended to the <code>*Ready</code> queue, with the optional <code>exe</code> to
be evaluated when resumed. The current coroutine continues to run.</dd>
<dt><code>(wake 'sym 'exe)</code></dt>
<dd>Wakes up another coroutine <code>sym</code>, by appending it to the
<code>*Ready</code> queue with the optional 'exe' to be evaluated when resumed.
This means that if <code>sym</code> is currently waiting for a point in time in
<code>*Next</code>, it is removed from that index (i.e. the pause is aborted).
Also, if <code>sym</code> is waiting for signals, it is removed from those event
queues. The current coroutine continues to run.</dd>
</dl>
<p><hr>
<h2><a id="use">Usage</a></h2>
<p>A typical DES program will start some coroutines and let them perform their
initial work until they need to pause.
<p>That means, if a given operation in the simulation is supposed to take
<code>cnt</code> time units, this coroutine calls <code>pause</code> with that
number. Or, if it depends on some signals from another part of the program, it
may call <code>pause</code> with those symbols. In any case - as it has nothing
else to do - it goes to sleep.
<p>When all of them wait for a time or signal, control is returned to the main
program. All coroutines are now waiting in <code>*Next</code> or some signal
event queue (or in <code>*Ready</code> if they just gave up control with
<code>(pause)</code>).
<p>The main program may now check <code>*Next</code> and perhaps
<code>*Ready</code>. If both are empty, no further events can occur, and the
program may terminate.
<p>Otherwise, it calls <code>des</code> to continue with the next step(s).
<p>At any time, a coroutine or the main program may call <code>wake</code>, for
example to interrupt another coroutine and cause it to <a
href="http://software-lab.de/doc/refT.html#throw">throw</a> into some other
context, or have that coroutine's <code>pause</code> return a special value by
evaluating the <code>exe</code> argument.
<p><hr>
<h2><a id="xmpl">An Example</a></h2>
<p>Let's use DES to demonstrate the well-known <a
href="http://en.wikipedia.org/wiki/Dining_philosophers_problem">Dining
Philosophers Problem</a>.
<p> Put the following code into a file "dining.l".
<hr>
<pre>
# 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) ) )
</pre>
<hr>
<p>It uses five global variables <code>*ForkA</code> through <code>*ForkE</code>
and five coroutines <code>Aristotle</code>, <code>Kant</code>,
<code>Spinoza</code>, <code>Marx</code> and <code>Russell</code>. They all run
the same function <code>think</code>, with their neighboring forks as
<code>Left</code> and <code>Right</code> arguments.
<p>In <code>think</code>, 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.
<p>Now both forks are free. The philosopher puts himself into both (it could put
in fact any non-<code>NIL</code> value), then is "eating" for 20 minutes,
releases both forks by setting them to <code>NIL</code>, and sends a left and a
right fork signal to the neighboring philosophers possibly waiting for the
forks.
<p>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.
<h2>Sample Run</h2>
<pre>
$ ./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:
</pre>
</body>
</html>
|
