Event executed at time 0
Event executed at time 1.2565807751267555
Event executed at time 1.6047558843805958
Event executed at time 2.0617445910150107
Event executed at time 4.549777455169493
Event executed at time 6.142924789039473
Event executed at time 6.831783799132048
Event executed at time 8.86991221834774
Event executed at time 9.591020838051998
Event executed at time 11.182474240259053
Event executed at time 11.916513694135645
Event executed at time 13.101324384282467
Event executed at time 13.271118153857092
Event executed at time 13.538340693508719
Event executed at time 13.676024698037342
Event executed at time 14.557948337899093
Event executed at time 15.032198418495422
Event executed at time 16.505715118943602
Event executed at time 17.13128793323082
Event executed at time 17.866723195852238
Event executed at time 18.82479225048173
Event executed at time 19.66662289298722
Event at time 0: Some("Scheduled another event")
Event at time 1.2565807751267555: Some("Scheduled another event")
Event at time 1.6047558843805958: Some("Scheduled another event")
Event at time 2.0617445910150107: Some("Scheduled another event")
Event at time 4.549777455169493: Some("Scheduled another event")
Event at time 6.142924789039473: Some("Scheduled another event")
Event at time 6.831783799132048: Some("Scheduled another event")
Event at time 8.86991221834774: Some("Scheduled another event")
Event at time 9.591020838051998: Some("Scheduled another event")
Event at time 11.182474240259053: Some("Scheduled another event")
Event at time 11.916513694135645: Some("Scheduled another event")
Event at time 13.101324384282467: Some("Scheduled another event")
Event at time 13.271118153857092: Some("Scheduled another event")
Event at time 13.538340693508719: Some("Scheduled another event")
Event at time 13.676024698037342: Some("Scheduled another event")
Event at time 14.557948337899093: Some("Scheduled another event")
Event at time 15.032198418495422: Some("Scheduled another event")
Event at time 16.505715118943602: Some("Scheduled another event")
Event at time 17.13128793323082: Some("Scheduled another event")
Event at time 17.866723195852238: Some("Scheduled another event")
Event at time 18.82479225048173: Some("Scheduled another event")
Event at time 19.66662289298722: Some("Scheduled another event")
A First Prototype of A Simple DES Environment in Rust
Rust
Discrete Event Simulation
Simulation
Software Design
Prototyping
Introduction
In this post I explain the current state of prototype for discrete event simulation (DES) environment I created in Rust.
Design
The approach I took to implementing DES in this prototype was to focus on defining some core components in a system/state independent way.
There are always going to be implementation choices when it comes to converting something mathematically general like DES systems, but I didn’t want to mention specific business processes or even queueing systems in the core logic. A lot of things that usually come with the territory of DES are actually system-dependent terms and concepts that fall within what DES can usefully represent. So while ‘state’ is always an essential part of DES, I have written the other core components with the assumption that they, especially events, can be coupled to any state of interest (especially state transitions).
The clock is an important parameter for DES as it is the single source of truth on what position events get placed onto the event schedule. My implementation is agnostic to the choice of units of time. A simulated unit of time on the DES clock could be a nanosecond, an hours, a day, a year, or a billion years.
The event schedule itself is the ordered collection of events that have yet to ellapse, and it is where new events get placed when we say that an event was “scheduled”. The events on the event schedule are ordered by time primarily, and secondarily by the order in which they were added. Although it is not the case in my implementation, it is possible to have other priority rules for specifying the order of events that are scheduled for the same time. This can be important for some simulations where the events trigger state transitions that do not commute as operators on the simulation state.
Implementation
The first aspect of this prototype is to include any needed dependencies.
use std::collections::{BinaryHeap, HashMap};
use std::cmp::Ordering;The BinaryHeap is the data structure used for the event schedule. The “binary” part of the name alludes to the implementation using a binary tree. We can use this data structure such that events are added to the schedule in the correct order such that we can simply pop them off the schedule in the correct order, which can be more efficient than appending and then sorting each time an element is added.
The HashMap is used within the implementation of events to store any contextual data. The contextual data is primarily intended for logging purposes.
Ordering is used is to define the ordering of events in terms of their elapse times, which is essential for scheduling them.
Next we can define events themselves as structs.
struct Event {
time: f64,
action: Box<dyn FnMut(&mut EventScheduler) -> Option<String>>,
context: HashMap<String, String>,
active: bool,
}Events have four properties. The first is time, which is the time that the event gets scheduled to elapse. This is a 64-bit float, which I generally expect to be precise enough for this purpose.
The action attribute will point to a function which is responsible for some state transition in the simulation. The fact that this can take some general function like this and call it later means we can inject and lazily execute whatever state transitions make sense for the system being implemented. This is one of the key ways in which the implementation is designed to be agnostic about the sort of state that you’re implementing elsewhere. The type is more subtle than actually just being a function. Rather, it is a box closure which means that our function is going to be heap-allocated. These function s are expected to optionally return a string (otherwise ()).
The context property is primarily used to attach any associated data to the event, which can be useful for logging and providing valuable data for downstream analysis.
Lastly, every event contains the active property which is simply a true or false value. The role that it supplies is to control whether an event’s action will run when an event elapses. This provides a general way of ‘cancelling’ the effect of an event on the state without removing it from the schedule, which can be useful for logging purposes. If an event is not active when it ellapses, then action will not be called.
I took an approach to creating new events such that they can be copied when needed. The action is given as a closure that simply returns None because it cannot be cloned directly, so Box::new(|| None) is just a placeholder. The other properties are just copied over to the new instance.
impl Clone for Event {
fn clone(&self) -> Self {
Event {
time: self.time,
action: Box::new(|_| None),
context: self.context.clone(),
active: self.active,
}
}
}There are a couple of methods that need to be implemented for Event so that they can be initialized and so that the state transitions are triggered by running the events action.
impl Event {
fn new(time: f64, action: Option<Box<dyn FnMut(&mut EventScheduler) -> Option<String>>>, context: Option<HashMap<String, String>>) -> Self {
Event {
time,
action: action.unwrap_or_else(|| Box::new(|_| None)),
context: context.unwrap_or_default(),
active: true,
}
}
fn run(&mut self, scheduler: &mut EventScheduler) -> Option<String> {
if self.active {
(self.action)(scheduler)
} else {
None
}
}
}The new method will take the time that the event is to be scheduled, the the optional boxed closure for transitioning the state, and the context. Note that the boxed closure will by default use a closure which does and returns nothing if nothing is given. The context will be the () is nothing is given. This method provides the constructor for all events, which are active by default.
The run method is responsible for calling an event’s action, which is intended to implement some sort of state transition for a simulation. This method will only call an event’s action if it is active.
It is not sufficient to assume that events having times would mean that they will be ordered by there times on the event schedule. We must define how they are to be ordered. Defining the ordering properties of events can be achieved by defining trait implementations for Event. The cmp method defines the ordering on the binary heap that is key to scheduling events.
impl PartialEq for Event {
fn eq(&self, other: &Self) -> bool {
self.time == other.time
}
}
impl Eq for Event {}
impl PartialOrd for Event {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Event {
fn cmp(&self, other: &Self) -> Ordering {
other.time.partial_cmp(&self.time).unwrap()
}
}So far I have been focusing on the implementation for events, but we also need to consider the event scheduler which will work with the clock and event schedule. In this implementation the clock and event schedule are properties of the event scheduler. There is also an event log which is used to collect a record of events that have elapsed.
struct EventScheduler {
current_time: f64,
event_queue: BinaryHeap<Event>,
event_log: Vec<(Event, Option<String>)>,
}The current_time is current state of the simulation’s clock. The event_queue is the schedule of the events that have yet to elapse, which is going to contain events ordered by time. The event_log is a Rust vector of events along with the results from calling their run methods.
There are a few things we need to implement for EventScheduler. We need to be able to construct a new instance of it. We need to be able to schedule events onto the event schedule. In this implementation the event scheduler is also responsible for running the simulation itself, which includes logic for elapsing events, updating the clock, logging, and having a stop condition so that the simulation program knows when to stop. I also added a timeout function inspired by SimPy’s timeouts so that scheduling an event is a little easier in simple cases.
impl EventScheduler {
fn new() -> Self {
EventScheduler {
current_time: 0.0,
event_queue: BinaryHeap::new(),
event_log: Vec::new(),
}
}
fn schedule(&mut self, event: Event) {
self.event_queue.push(event);
}
fn timeout(&mut self, delay: f64, action: Option<Box<dyn FnMut(&mut EventScheduler) -> Option<String>>>, context: Option<HashMap<String, String>>) {
let event = Event::new(self.current_time + delay, action, context);
self.schedule(event);
}
fn run(&mut self, stop: Box<dyn Fn(&Self) -> bool>, log_filter: Option<Box<dyn Fn(&Event, &Option<String>) -> bool>>) -> Vec<(Event, Option<String>)> {
let log_filter = log_filter.unwrap_or_else(|| Box::new(|_, _| true));
while !stop(self) {
if let Some(mut event) = self.event_queue.pop() {
self.current_time = event.time;
let event_result = event.run(self);
if log_filter(&event, &event_result) {
self.event_log.push((event, event_result));
}
} else {
break;
}
}
self.event_log.clone()
}
fn run_until_max_time(&mut self, max_time: f64) -> Vec<(Event, Option<String>)> {
self.run(Box::new(stop_at_max_time_factory(max_time)), None)
}
}
fn stop_at_max_time_factory(max_time: f64) -> Box<dyn Fn(&EventScheduler) -> bool> {
Box::new(move |scheduler: &EventScheduler| {
scheduler.current_time >= max_time
|| scheduler.event_queue.peek().map_or(true, |event| event.time >= max_time)
})
} You can see that the implementation of run above also includes a function which allows us to filter which events we wish to log. While this has some performance overhead, it can reduce the memory overhead when you are elapsing a large number of events but you’re also only interesed in using data from a smaller subset of them.
The conditions in which the simulation is stopped is also specified by a function that will be iteratively called on the instance of the event scheduler. I expect the most common use case is to simulate until a maximum time is completed, which I wrote a function factory for. Using function factories like this allows us to provide custom stop conditions which we might write and provide for our particular project but are not meant to be used in all projects. At least, that’s the general idea anyway.
Example
The above code covers the core implementation, but let’s see a simple example of how to actually use it. Below I define a simple example of scheduling a single event which will return a non-empty string. Then I schedule the event to elapse at whatever time is five in the simulation, which in turn schedules another event which will return nothing. I simulate for ten units of time, so we’ll expect our event to elapse. The for each event, we’re only expecting the one, we’ll print its elapsed time and its result.
fn main() {
let mut scheduler = EventScheduler::new();
let action = Box::new(|scheduler: &mut EventScheduler| {
println!("Event executed at time {}", scheduler.current_time);
scheduler.timeout(1.0, None, None);
Some(String::from("Scheduled another event"))
});
scheduler.timeout(5.0, Some(action), None);
let log = scheduler.run_until_max_time(10.0);
for (event, result) in log.iter() {
println!("Event at time {}: {:?}", event.time, result);
}
}Ideally we would have some domain-specific problem where action would represenent scheduling some function that would change the state of the simulation. Events can schedule other events, which allow for indefinite behaviour, limited to the simulation max time, such as arrivals of agents/jobs/packets into a network. In such a context we would want to give more informative names.
Conclusions
While this is only a first prototype of the core components of DES, it shows some promise in being the starting point for a flexible simulation framework. Although queueing systems with servers and resources are not an inherent component of DES, they are commonly used because many realistic systems have such subsystems. Further development into testing and packaging the current state is required to move forward, but also implementing some ready-to-use components for such queueing systems would provide useful utilities for using this core simulation logic.