Skip to content

PDEVS

Jump to bottom
Romain Franceschini edited this page Apr 28, 2020 · 7 revisions

Atomic discrete event models are defined in Quartz by subclassing the Quartz::AtomicModel base class. They allow to model timed, reactive and autonomous systems. Their behaviour is described through state transitions and other functions, triggered by the simulator as events occur.

Which state transition is triggered depends on the type of event that occurs, which can be either:

  • an internal event, which is planned autonomously by the model to occur at a certain point in time;
  • or an external event, which may occur at any point in time. It is unplanned by the model and is used to carry one or multiple input values received through input ports so the model can react to it accordingly.

Running example

Let's take a running example to incrementally describe the behaviour of a simple system. We will model a cashier, a commonly used abstraction in Queuing theory that features a timed, autonomous and reactive behaviour.

In our abstraction, the cashier is either available waiting to process clients, busy serving a client or unavailable because he leaves. When available, the cashier have to serve clients (one at a time) as they arrive by processing a given amount of articles. He becomes busy for a while, the processing time being proportional to the number of articles to process. Once finished, the cashier outputs the processed articles and signals he is now available unless he leaves, in which case he will signal its availability later.

Before starting to define our state transitions, let's declare the state and I/O interface of our cashier model:

class Cashier < Quartz::AtomicModel
  input :articles
  output :available, :articles

  state do
    enum Phase
      Available
      Busy
      Unavailable
    end

    parameter throughput = 0.4    # articles per time unit
    var phase = Phase::Available
    var number_of_articles = 0
  end
end

Articles are received through the input port article and passed back through the output port having the same name. The available signal is sent through the output port available.

As for the state, a phase variable is used to indicate in which state phase the cashier currently is: processing articles, doing something else or waiting for clients. The variable number_of_articles indicates how many articles are to be processed. The throughput parameter indicates the mean processing time per article of the cashier. Disclaimer: the default throughput is arbitrarily chosen and may not be realistic. Choosing the right parameters is usually the task of domain experts.

Note: we didn't specified a precision for the model since it defaults to the base time unit, which is fine for our abstraction. A time unit will represent a second in our case.

Let's now define the autonomous part of the cashier behaviour.

Autonomous behaviour

When available, our cashier waits clients for a maximum amout of 5 minutes, otherwise he leaves for doing other stuff but always comes back every 15 minutes. When he is busy, he stays that way the amount of time necessary to process the articles.

We will define the time spent in each state thanks to the #time_advance method, one of the five methods you are expected to implement

Planning the duration of a state

The time advance method is used by the simulator to determine when the next internal event will be scheduled. In other words, it allows you to specify how much time you want to spend in the current state.

It is called after each state transition to give a chance the model to evolve autonomously. It is also called when the simulation is initialized, to know which models will first be scheduled. The expected return type is a Duration (see time representation).

An implementation for our requirements can be something like:

class Cashier < Quartz::AtomicModel
  # ...

  def time_advance : Quartz::Duration
    case state.phase
    when .available?
      5 * 60.time_units
    when .unavailable?
      15 * 60.time_units
    else
      Quartz.duration(state.number_of_articles / throughput)
    end
  end
end

Note: An important thing to remember is that you are not supposed to mutate the state from the time advance method, doing so may lead to an unexpected behaviour.

Congratulations! You completed an important step in the definition of a discrete event model, which is planning your future events.

So what now?

When a planned event expires, it is said to be due. The simulator will trigger an internal state transition to update the model state via the #internal_transition. Right before calling this transition, a chance is given to your model to send outputs for the expiring state through the #output method.

The simulator will always call the methods in this order, unless an external event comes perturbate the sequence (more on that later):

  1. #time_advance
  2. #output
  3. #internal_transition

Sending outputs

Given our requirements, the model should send outputs in all 3 states. The number of articles processed at the end of Busy state should be sent to the :articles output port, and a flag indicating whether the cashier may process clients for each state should be sent through the :available port.

Sending values to ports is done using the #post method:

class Cashier < Quartz::AtomicModel
  # ...

  def output
    if state.phase.busy?
      post state.number_of_articles, on: :articles
    end

    post state.phase.available?, on: :available
  end
end

Note: Like the #time_advance method, you are not supposed to mutate the state from the #output method, doing so may lead to an unexpected behaviour. Also, #post is only meant to be used in the context of the #output method.

Updating the state

Once our outputs are sent, we may change our expiring state via the #internal_transition function. The new state will depend on whether the cashier is currently available. If so, it will become unavailable because it means the cashier spent 5 minutes waiting for clients and decide to leave. If not it will become available, because it either means the cashier comes back or that he just finished processing the previous client.

class Cashier < Quartz::AtomicModel
  # ...

  def internal_transition
    state.number_of_articles = 0
    state.phase = if state.phase.available?
                    State::Phase::Unavailable
                  else
                    State::Phase::Available
                  end
  end
end

Note: you can also assign a new state using the #state= method.

Wrap-up

Congratulations! you defined your first autonomous discrete event model with Quartz.

Let's review what will happen if we simulate our cashier model as-is:

  1. In the initial state, the cashier is in the Active state phase.
  2. The simulator calls the #time_advance function, which returns a duration of 300s in our case (5min).
  3. The Active state expires (no inputs comes perturbate the model). The #output function is called, which outputs false to the :available output port. #internal_transition is called and the model goes to the Unavailable state.
  4. The #time_advance function is called again. The current state will expire after 900s (15min), and so on.

Such a simulation can go on forever unless a termination condition is set. Note that the simulation may stop on its own if the model returns an infinite duration from #time_advance.

Reactive behaviour

Let's focus on the last state transition expected to be defined by an atomic model: the external transition, which may be triggered at any point in time. In other words, no matter the current state planned duration, the external transition will perturbate the model. This is exactly what we should expect from a reactive system.

For example, when our cashier is available, he plans to become unavailable after 5min if no client shows up to avoid sitting indefinitely. If our cashier were a robot, waiting indefinitely would be modelled by planning an infinite duration for the available state. No matter the duration, what is important here is that we expect a client to interrupt this available state at some point.

External transition

In Quartz, you should define the #external_transition(messages) method to react to external inputs. The messages parameter is a Hash mapping input ports to a list of input values (Hash(InputPort, Array(Any))). This means multiple inputs can arrive at the same time, even on the same input port.

When input events occurs, the following methods are called:

  1. #external_transition(messages) to change the state according to the inputs.
  2. #time_advance to plan the new future internal event.

Output values immediately after receiving inputs

An important thing to notice is that the output function is not called before the external transition, unlike it is for the internal transition. In this sense, atomic models are closer to Moore machines than to Mealy machines because the outputs are only based on the current state, and not on the inputs.

This means that sending an output immediately after receiving an input requires the use of a transient state, which is completely fictional and only introduced for modelling purposes. The planned duration associated to this state is a duration of 0, which is allowed and triggers the output method.

In our cashier example, processing the input usually takes time, unless a client with 0 articles arrives. While the state used for this purpose (busy) is not fictional, the triggered sequence of methods is the same: #external_transition(messages), #time_advance, #output, and #internal_transition.

Elapsed time

To keep track of how much time passed since the last state change, a crucial variable is used: the elapsed time. It is available through the #elapsed method and its value is updated along with the simulation before each state transition.

Handling collisions between events

Common patterns

Initial state

Generators (purely autonomous)

Collectors (purely reactive)

Passive models

Clone this wiki locally