Simulua

Introduction

What Simulua is

Simulua 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 Lua

The 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 actors

A 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 execution

There 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 simulation

The 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 probabilities

We 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 Simulua

Simulua 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.