Overview
This page provides a brief introduction to discrete-event simulation, an overview of the simulation constructs as implemented in React.NET, and then proceeds to an example simulation program. The example program simulates a barber shop and demonstrates some, but definitely not all, of the capabilities of React.NET
Discrete Event Simulation
If you're reading this, you've probably got a good idea of what discrete-event simulation is all about. However, just in case you don't, here is a very brief description. See Links for a list of other resources that provide more information.
Simulation, in general, is an attempt to model some aspect of the real world and gather data about the modeled system. It's often used when directly observing the real-world system is not possible because: (1) it doesn't exist yet; or (2) it would be too costly or dangerous to test in multiple configurations/scenarios.
There are several common simulation methodologies for example continuous, linear-programming, and discrete-event. Each has strengths that make it most useful for a particular problem domain.
Continuous simulation describe systems using one or more mathematical equations or models. These models might be used to help understand a system based on rules of physics or economics.
Linear programming (and non-linear programming) are often used to solve optimization problems that involve several variables. An example might be maximizing profit on several products based on user demand, production output, production cost, and sales price.
Finally, discrete-event simulations are used to model systems composed of activities that take place at distinct moments in time. Often these activities include random elements and potentially complex interactions with other activities. Discrete-event simulations are often applicable to modeling business and manufacturing processes.
Discrete-event simulation is especially useful in understanding systems that have demand vs. capacity and queuing aspects. For example, a bank experiences demand (customers need to see tellers), has a capacity (there are only so many tellers available to service customers), and uses queuing (customers wait in line until they can see a teller).
Basic Concepts
The following subsections introduce some of the most fundamental classes and concepts used to build React.NET simulations.
The Simulation
The Simulation serves as the container for
Task instances. It also contains the clock used to
control the time. Each Task maintains a reference
to the Simulation under which it runs. This link
is called the simulation context and is available as the
Context
property.
For simple models, a single Simulation is used. For more complex models that might be executed many times (e.g. monte-carlo simulations), multiple Simulation instances can be run either sequentially or in parallel using multiple threads.
The Clock
Each Simulation maintains a clock. The clock is responsible for keeping the current simulation time. The clock maintains the time as a System.Int64 (a C# long). The unit of time represented by the clock is up to the programmer. Because the clock maintains time in integer units, choosing a time unit is important because the clock cannot represent fractional units. For example, in a simulation that requires sub-second accuracy, one time unit might represent a millisecond; therefore to schedule a Task to run two seconds in the future, the program would schedule it to run in 2,000 time units.
Tasks
A Task is executed by a Simulation to carry out some action. Often one or more Tasks are used as part of a Process (see below). Tasks can be scheduled to run at a particular simulation time or they can be passed to a blocking object such as a Resource or BoundedBuffer to be resumed when a particular condition is met during the course of a simulation run.
The work to be carried out by a Task is defined by implementing
the ExecuteTask
method.
Processes
A Process consists of a series of Tasks carried out over time. A Process is, in fact, a type of Task that yields (or returns) other Tasks to carry out certain functions. Each Task that a Process returns acts somewhat like a subroutine of the Process. The Task runs and eventually when the Task completes, the Process is resumed (or re-activated).
Process classes use the .NET 2.0 feature called an
iterator to yield Tasks. The iterator, an
IEnumerator<Task> instance, is
returned by the GetProcessSteps()
method of the
Process class.
protected virtual IEnumerator<Task> GetProcessSteps();
GetProcessSteps()
may be overridden by a derived class to implement
process-specific behavior, or a ProcessSteps
delegate may be passed
to the Process constructor to provide process-specific
behavior without deriving a new class.
Blocking Objects
A blocking object is an object that causes a Task or Process to suspend it execution until such time as a particular condition has been met. React.NET includes the following blocking objects.
- Resource
- Represents a collection or pool of items, people, etc. each of which can be used by one Task at a time. To obtain exclusive use of a resource item, a Task must acquire the item. When finished using the resource item, the owning Task must release the item back into the pool. If a resource item is not immediately available, the requesting Task is blocked until such time as an item becomes available.
- Consumable
- Similar to a Resource, a Consumable contains consumable items that, once acquired by a Task, are never released back into the pool. Consumables are essentially resources that are "used up" by the acquiring Task. An example of a consumable is fuel. The Consumable class is not derived from Resource.
- Condition
- A Condition acts as a true/false switch during the simulation run. If the Condition is false or reset, any Tasks can block on the Condition. Once the Condition becomes true or signalled, blocked Tasks are re-activated. The programmer may chose to re-activate all blocked Tasks or just a single Task when the Condition becomes signalled.
- BoundedBuffer
- A BoundedBuffer is a queue of finite size. Producer tasks put items into the buffer and consumer tasks take items out of the buffer. When the buffer is full, any producer tasks attempting to put an item into the buffer will be blocked. When the buffer is empty, any consumer tasks attempting to get an item from the buffer will be blocked.
It is also possible to add other blocking objects to the system.
Blocking behavior is implemented by methods marked with the BlockingMethod
attribute. All blocking methods return a Task instance which
contains the functionality to property interact with the blocking object. The
Task which called the blocking method blocks on the returned
Task not on the blocking object itself. A typical blocking
method looks something like what's shown below.
[BlockingMethod] public Task Acquire(Task requestor) { . . . }
Monitors
Monitors serve as observers to the running simulation. Each time a monitorable property changes, a Monitor class will record the new value and the time of the change. Monitors can aggregate observations into summary statistics (like the Mean) or they can simply record each observation for use at a later time.
Monitors that compute statistics are divided into two types: simple statisics and time-weighted statistics. Simple statistics are not affected by the time between observations (e.g. the Maximum or Minimum), while time-weighted statistics use the time between observations to weight the observation (e.g. WeightedMean).
Barber Shop Example
This example simulates a small barber shop. It uses three classes: one represents the shop; one a barber; and one a client or customer. It's operation is quite straightforeward:
- A single generator process creates a new customer (someone who wants a haircut) about once every five minutes.
- Each customer enters the shop and attempts to acquire a barber resource. If no barbers are available, the customer queues to wait for one.
- When a customer successfully acquires a barber, they activate the associated barber process to do the haircut.
- When the barber process finishes, the customer process is re-activated. At this point, the customer pays for the haircut, releases the barber resource, and leaves the shop.
This code demonstrates using a TrackedResource that contains four Process instances. Here, the tracked resource contains four Barber processes which are acquired by and service Customer processes.
The source files for this example can be found in the examples\BarberShop directory.
The Shop
Below is the complete code for the Shop class found in Shop.cs.
using System; using System.Collections.Generic; using System.Text; using React; using React.Distribution; namespace BarberShop { public class Shop : Simulation { private const long ClosingTime = 8 * 60; private Shop() {} private IEnumerator<Task> Generator(Process p, object data) { Console.WriteLine("The barber shop is opening for business..."); Resource barbers = CreateBarbers(); Normal n = new Normal(5.0, 1.0); do { long d; do { d = (long)n.NextDouble(); } while (d <= 0L); yield return p.Delay(d); Customer c = new Customer(this); c.Activate(null, 0L, barbers); } while (Now < ClosingTime); Console.WriteLine("The barber shop is closed for the day."); if (barbers.BlockCount > 0) { Console.WriteLine("The barbers have to work late today."); } yield break; } private Resource CreateBarbers() { Barber[] barbers = new Barber[4]; barbers[0] = new Barber(this, "Frank"); barbers[1] = new Barber(this, "Tom"); barbers[2] = new Barber(this, "Bill"); barbers[3] = new Barber(this, "Joe"); return Resource.Create(barbers); } static void Main(string[] args) { Shop shop = new Shop(); Task generator = new Process(shop, shop.Generator); shop.Run(generator); } } }
The Shop class is derived from the
Simulation class and contains the Main
method. Main
creates the Shop
simulation instance and a single generator task. In this case,
the generator task — conveniently named generator
—
is a Process instance whose actual functionality is
provided by a delegate — the method Shop.Generator
.
Finally, Main
starts the simulation running with the call to
shop.Run(generator)
.
static void Main(string[] args) { Shop shop = new Shop(); Task generator = new Process(shop, shop.Generator); shop.Run(generator); }
The Generator
method is used to initialize the shop's
resources (e.g. the barbers) and to generate customers. A
Normal distribution is used to create a new customer
about once every five minutes (it's a very busy barber shop).
Console.WriteLine("The barber shop is opening for business..."); Resource barbers = CreateBarbers(); Normal n = new Normal(5.0, 1.0);
The private method CreateBarbers
is used to
create and array of Barber processes named Frank,
Tom, Bill, and Joe. After creating and filling the
barbers
array, a TrackedResource is
obtained by calling Resource.Create(barbers)
. The resource is
returned to the caller (the Generator
method).
private Resource CreateBarbers() { Barber[] barbers = new Barber[4]; barbers[0] = new Barber(this, "Frank"); barbers[1] = new Barber(this, "Tom"); barbers[2] = new Barber(this, "Bill"); barbers[3] = new Barber(this, "Joe"); return Resource.Create(barbers); }
This is a good time to briefly explain the two types of resources provided by React.NET: anonymous and tracked. Anonymous resources, provided by the AnonymousResource class, represent pools of items using only counts (e.g. there are five "things" in the pool). Tracked resources, on the other hand, "track" actual .NET objects. When a resource item is acquired from a tracked resource, the task that acquired the resource item gains access to the associated object.
Returning to the Generate
method, it is now
possible to begin creating Customer instances.
Customers are continually created and activated until
closing time, which is defined as eight hours after the
start of the simulation.
do { long d; do { d = (long)n.NextDouble(); } while (d <= 0L); yield return p.Delay(d); Customer c = new Customer(this); c.Activate(null, 0L, barbers); } while (Now < ClosingTime);
Two things to note about the above code: (1) because
a Normal distribution can have long tails,
we loop until we get an acceptable value; (2) the
resource containing the four Barber processes is
passed to each customer as activation data — the third
parameter in the call to c.Activate(..., barbers)
.
Finally, once closing time is reached, a message is printed
indicating that the shop has closed for the day. In addition,
we check if the barbers have to work late because there are
still customers waiting (who arrived before closing time).
The yield break;
statement signifies the end of
the generation process. Once the generation process terminates,
no more customers will be created.
Console.WriteLine("The barber shop is closed for the day."); if (barbers.BlockCount > 0) { Console.WriteLine("The barbers have to work late today."); } yield break;
The Customer
Below is the complete code for the Customer class found in Customer.cs.
using System; using System.Collections.Generic; using System.Text; using React; namespace BarberShop { internal class Customer : Process { internal Customer(Simulation sim) : base(sim) {} protected override IEnumerator<Task> GetProcessSteps() { Resource barbers = (Resource)ActivationData; yield return barbers.Acquire(this); System.Diagnostics.Debug.Assert(barbers == Activator); System.Diagnostics.Debug.Assert(ActivationData != null); Barber barber = (Barber)ActivationData; WaitOnTask(barber); yield return Suspend(); // HINT: The above two lines of code can be shortened to // yield return barber; Console.WriteLine("Customer pays {0} for the haircut.", barber.Name); yield return barbers.Release(this); } } }
The Customer class is derived from the
Process class. The actions of the
Customer are defined by overloading the
GetProcessSteps
method.
protected override IEnumerator<Task> GetProcessSteps() { Resource barbers = (Resource)ActivationData; yield return barbers.Acquire(this); System.Diagnostics.Debug.Assert(barbers == Activator); System.Diagnostics.Debug.Assert(ActivationData != null); Barber barber = (Barber)ActivationData; WaitOnTask(barber); yield return Suspend(); // HINT: The above two lines of code can be shortened to // yield return barber; Console.WriteLine("Customer pays {0} for the haircut.", barber.Name); yield return barbers.Release(this); }
The Customer process begins by retrieving the Resource containing the four Barber objects from the activation data. It then attempts to acquire a Barber from the resource.
Resource barbers = (Resource)ActivationData; yield return barbers.Acquire(this);
Upon re-activation, the Customer should now have acquired
a Barber. A few assertions double check to
make sure. Because we don't have to deal with interrupts,
we know that barbers
(i.e. the resource) should
have been the object that re-activated the client.
System.Diagnostics.Debug.Assert(barbers == Activator); System.Diagnostics.Debug.Assert(ActivationData != null); Barber barber = (Barber)ActivationData;
The Customer can now activate the acquired
Barber to have his or her hair cut. Note how one
process gets served by another process. This is typical of a multi-agent
simulation. As the comment below indicates, the code can be shortened to a single
line (yield return barber;
). The more verbose method is shown
because it better illustrates exactly what the Customer
is doing.
WaitOnTask(barber); yield return Suspend(); // HINT: The above two lines of code can be shortened to // yield return barber;
Lastly, the Client must release the resource.
yield return barbers.Release(this);
The Barber
Below is the complete code for the Barber class found in Barber.cs.
using System; using System.Collections.Generic; using System.Text; using React; namespace BarberShop { internal class Barber : Process { internal Barber(Simulation sim, string name) : base(sim) { this.Name = name; } protected override IEnumerator<Task> GetProcessSteps() { Console.WriteLine(Name + " begins cutting customer's hair ..."); yield return Delay(22); Console.WriteLine(Name + " finishes cutting customer's hair."); yield break; } } }
The Barber class, like the
Customer class, is also a
Process. It's implementation of
GetProcessSteps
simply delays for twenty-two minutes
to simulate the time it takes to cut the customers's hair.
protected override IEnumerator<Task> GetProcessSteps() { Console.WriteLine(Name + " begins cutting client's hair ..."); yield return Delay(22); Console.WriteLine(Name + " finishes cutting client's hair."); yield break; }
Once the Barber process completes the Customer that is blocking on the Barber is automatically re-activated.