Introduction
What Simulua isSimulua is a discrete-event simulation (DES) library for Lua, in the same tradition and flavor of the SIMULA family of programming languages. The simulation in Simulua is process-oriented, that is, the operation path of a simulated system is obtained from interactions of processes running in parallel. Events are then implicitly managed through process management and scheduled through an event list. Processes are implemented in Simulua using property tables and their corresponding coroutines as execution threads.
The Simulation section gives more details about the simulation engine, Processes explains processes, Control describes how the simulation is managed, and section Examples provides some examples. The examples, in particular, are very helpful in understanding the concepts. Containers, accumulators and other important auxiliary routines are described in Facilities.
Simulua is licensed under the same license as Lua—the MIT license—and so can be freely used for academic and commercial purposes. Please refer to the Installation section for more details.
Simulation
Process-oriented DES in LuaThe main concept in Simulua is the process, represented by a pair: a table that stores properties—the process "object" itself—and a corresponding coroutine that creates and manages events. The sequence of events that composes a simulation run is executed through an event list that is implemented as a binomial heap with event times as priorities. The event list, and hence process execution, is managed by an implicit scheduler/dispatcher coroutine. The scheduler advances the simulation time to the next event time of the latest retrieved process from the list. Note that it is possible for two processes to execute in "parallel", that is, at the same simulation time.
The currently active process and current simulation time can be queried
with simulua.current
and simulua.time
:
simulua.current()
Returns the process that is currently executing.
simulua.time([proc])
If proc
is nil
returns the current simulation
time, otherwise returns the event time of process proc
.
Processes
The main actorsA process is created with simulua.process
:
simulua.process(exec [, prop])
Returns a process that executes function exec
and has optional
property table prop
.
A process resumes execution when it is retrieved from the event list at the current time. If a process is not in the event list it is said to be idle. A process is inserted into the event list when it is activated; the activation can occur after either some time delay or process in the event list. A process can cancel the execution of another process, effectively removing the latter from the event list; if the process cancels itself it is said to passivate. A hold operation reschedules a process to resume after a time delay. A process can also wait for a container, like a queue: in this case the process is inserted, or pushed, into the container and passivates. The relevant Simulua process methods are listed below.
simulua.idle(proc)
Returns true
if process proc
is idle.
simulua.activate(proc [, delay [, after]])
Activates process proc
if it is idle, inserting it into the
event list, or reactivates it by changing its event time in the list.
Parameter delay
can be either a number, in which case
proc
receives priority time simulua.time() + delay
in the event list, or a process, when proc
acquires event
time simulua.time(proc)
. If delay
is
nil
or delay < 0
, then delay
is set
to zero. If delay
is an idle process, proc
is
canceled.
If after
is true
the insertion or change
operation has no priority, that is, proc
is positioned
after processes with the same priority time in the event list. Note
that heap operations assume priority by default.
simulua.cancel(proc)
Removes process proc
from the event list (it has no effect if
proc
is not scheduled).
simulua.passivate()
Equivalent to simulua.cancel(simulua.current())
.
simulua.hold(delay)
Reschedules the current process to event time
simulua.time() + delay
. If delay
is
nil
or negative, delay
is set to zero.
simulua.wait(cont, ...)
Inserts current process into container cont
and passivates. A
valid container must have a method into
for insertions. Any
extra parameters to simulua.wait
are passed to
cont.into
.
Control
Managing simulation executionThere are only two methods that control the simulation:
simulua.start
and simulua.stop
. The simulation
itself is run by a main process that is created and scheduled at time
zero by simulua.start
. The simulation ends when the main process
finishes executing.
simulua.start(exec)
Starts the simulation by creating the main process having exec
as function. simulua.start
initializes the event priority heap,
creates the main process, and resumes the scheduler.
simulua.stop()
Stops the simulation. It is equivalent to
simulua.cancel(main)
.
Examples
Understanding simulationThe following examples are adapted from Chapter 19 of Rob Pooley's book, An introduction to programming in Simula (we strongly recommend reading—and referring to—this chapter to better understand the examples and the simulation concepts from SIMULA). The main methods from Simulua are highlighted in bold in the code.
The first example implements a simple, deterministic simulation of a mill
worker day. We have two processes, mill
and worker
,
that run concurrently after worker
is first activated by the main
process: the worker loads the mill in five units of time, activates the mill
and checks regularly for it to finish its load, and finally unloads the mill;
the mill simply processes its load at two time units per component and
finishes when it is empty.
-- Mill model, example 19.1 from -- Pooley, R., "An introduction to programming in Simula" local simulua = require "simulua" -- variables local count = 0 -- processes local mill = {components = 0} mill = simulua.process(function() while true do print("Machine starts", simulua.time()) while mill.components > 0 do simulua.hold(2) -- machining time for one component mill.components = mill.components - 1 end simulua.passivate() end end, mill) local worker = simulua.process(function() while simulua.time() < 400 do print("Loading starts", simulua.time()) count = count + 1 -- keep a tally simulua.hold(5) mill.components = mill.components + 50 -- load up simulua.activate(mill) -- restart machine while mill.components > 0 do simulua.hold(0.5) end -- check regularly simulua.cancel(mill) -- switch off simulua.hold(10) -- unloading takes longer print("Unloading finishes", simulua.time()) end simulua.passivate() end) -- simulation simulua.start(function() -- main simulua.activate(worker) print(string.format("count = %d", count)) simulua.hold(800) print("Simulation ends", simulua.time()) end)
The main methods in this example are simulua.activate
,
simulua.hold
and simulua.cancel
(also implicit in
simulua.passivate
) as they control process cooperation and thus
the simulation execution. Note that simulua.time()
is used to
check for the end of a worker's day, the end of the simulation, and to report
activities. Chapter 19 of Rob Pooley's book gives more details about the
simulation run.
The next example models an employment office with two interviewers and a
shared receptionist. We again refer to Chapter 19 for a better description of
the simulation, but the concepts and methods should be getting more familiar.
The new resources in this example are the queue container and
simulua.wait
: the main process pushes four job hunters, each of
different skill, through the system, where they should wait for the
receptionist in queue receptionist.Q
and then for their
respective interviewer in either manual.Q
or
skilled.Q
.
-- Employment office queuing model, example 19.2 from -- Pooley, R., "An introduction to programming in Simula" local simulua = require "simulua" local queue = require "queue" -- variables local MANUAL = 1 -- skill category -- processes local manual, skilled -- interviewers local receptionist local function interviewer (title) local interviewerQ = queue() return simulua.process(function() while true do if not interviewerQ:isempty() then simulua.hold(3.5) -- interview time taken as 3.5 minutes local next = interviewerQ:retrieve() simulua.activate(next, simulua.current(), true) -- after current simulua.hold(3) -- 3 minutes to clear desk else simulua.hold(5) -- wait 5 minutes before checking queue again end end end, {Q = interviewerQ}) end local function jobhunter (skill) return simulua.process(function() print(string.format( "Job hunter %d joins receptionist queue at time %.1f", skill, simulua.time())) simulua.wait(receptionist.Q) print(string.format( "Job hunter %d joins interview queue at time %.1f", skill, simulua.time())) simulua.hold(1) -- 1 minute to join new queue if skill == MANUAL then simulua.wait(manual.Q) else simulua.wait(skilled.Q) end print(string.format( "Job hunter %d leaves employment office at time %.1f", skill, simulua.time())) end) end do -- receptionist local receptionistQ = queue() receptionist = simulua.process(function() while true do if not receptionistQ:isempty() then simulua.hold(2) local customer = receptionistQ:retrieve() simulua.activate(customer) else simulua.hold(1) end end end, {Q = receptionistQ}) end -- simulation simulua.start(function() simulua.activate(receptionist) manual = interviewer"Manual" simulua.activate(manual) skilled = interviewer"Skilled" simulua.activate(skilled) for _, skill in ipairs{1, 2, 2, 1} do simulua.activate(jobhunter(skill)) simulua.hold(2) end simulua.hold(100) end)
All three examples in Chapter 19 can be found in the examples
folder of the Simulua distribution.
Facilities
Containers, accumulators, and probabilitiesWe have already seen a container, a queue, in the last section.
The motivation behind containers in Simulua is to provide mechanisms for
process scheduling through simulua.wait
. To this end we provide
three containers: queues, that implement a
LIFO policy (module
queue
); stacks, for
FIFO policy (module
stack
); and binomial heaps for priority based policy (module
binomial
). For a container to be used by
simulua.wait
it needs to provide a into
method for
insertion.
Sometimes we want to report the mean of a variable in the
simulation. In this case, another useful facility is an
accumulator, that updates the value of the mean as requested during a
simulation run. The mean of a variable as tracked by an accumulator
accum
can be recovered in accum.mean
.
simulua.accumulator()
Returns an accumulator, a table with keys last
storing the
last updated time and mean
representing the last updated
mean.
accum:update(value [, last])
Updates accumulator accum
at time last
according
to last observed value
. If last
is nil it is set to
simulua.time()
.
For convenience, Simulua also includes libraries for random number
generation (module rng
) and cumulative distribution functions
(module cdf
), both borrowed from
Numeric Lua.
The next example simulates a warehouse where both batch arrival and processing times are exponentially distributed. Batches can be rejected if the number of units exceeds warehouse storage. We also keep track of the number of items in the warehouse and report its mean along with the proportion of rejected batches at the end of the simulation.
-- The "versatile warehouse model" from Section 3.1 of -- Mitrani, I. (1982), "Simulation techniques for discrete event systems" local simulua = require "simulua" local rng = require "rng" local queue = require "queue" -- variables local r = rng() -- note: change seed for different runs local warehouse = simulua.accumulator() -- for number of items local n = 0 -- number of current items in warehouse local arrived, rejected = 0, 0 -- number of items -- parameters local arr, rem = 20, 10 -- arrival and removal means local in1, in2 = 3, 5 -- range for arrivals local out1, out2 = 4, 6 -- range for removals local m = 10 -- units of storage local simperiod = 1000 -- simulation period -- processes local arrivals, worker do -- arrivals local number -- of items in batch arrivals = simulua.process(function() while true do simulua.hold(r:exp(arr)) arrived = arrived + 1 number = r:unifint(in1, in2) if number > m - n then rejected = rejected + 1 else warehouse:update(n) n = n + number if simulua.idle(worker) then simulua.activate(worker) end end end end) end do -- worker local size, number -- size of outgoing batch and number removed worker = simulua.process(function() while true do while n > 0 do simulua.hold(r:exp(rem)) warehouse:update(n) size = r:unifint(out1, out2) number = size < n and size or n n = n - number end simulua.passivate() -- warehouse is now empty end end) end -- simulation simulua.start(function() simulua.activate(arrivals) simulua.activate(worker) simulua.hold(simperiod) print(string.format("Proportion of rejected batches: %.2f", rejected / arrived)) print(string.format("Average no. of items in warehouse: %.2f", warehouse.mean)) end)
Installation
How to obtain and install SimuluaSimulua is distributed as a source package and can be obtained at
Luaforge. Depending on how
Lua 5.1 is installed in your system you might have to edit the Makefile and
copy the modules to their suitable places. Alternatively, you can use
LuaRocks and install from the rockspec
also available in Luaforge. Simulua can also be built standalone from folder
etc
in the distribution.
License
Copyright (c) 2008 Luis Carvalho
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.