4 DEVS Environment

There are two libraries, container and devs, to provide easy access to the DEVS environment. The container library, based on set theory, supports basic services to manipulate sets of entities. Container, bag, set, relation, and function classes are in the container library, including ordered lists such as stacks, queues, and lists.

The devs library supports several classes of basic models including atomic, cell, coupled, digraph, and block models. Using those predefined models, we can easily construct complex models in a hierarchical way, and build specific(user defined) models which would be expanded versions of basic models.

4.1 Container Library

The Container class, a generalized form of linked lists based on set theory, provides methods which can store, retrieve and organize interacting objects. A container object is an object containing other objects.

Figure 7 Class Hierarchy for Containers

Figure 7 depicts the Container class hierarchy. An Entity class will be the base class for all user-defined classes. It provides basically two methods, object name and a test of equality. The Container class provides basic services for the derived classes. The Bag class counts numbers of object occurrences. Only one occurrence of any object is allowed in the Set class. The Relation class consists of sets of pairs (key, value). The Function class is like the Relation except that at most one occurrence of any key is allowed. Queues, stacks, and lists maintain items in FIFO, LIFO, and ordered list respectively.

Figure 8 shows an example of a container class, specifically a message. Each content is in an element, and the elements are linked in a container. In DEVS-C++, the add method of a container,"add(entity *ent)", automatically creates a new element having entity, ent, and puts the element into the container. The code for printing contents in the message illustrates how a message is implemented as a linked list.

Figure 8 A message (container) structure with 3 contents

For (el=mail->get_head(); el!=NULL; el=elnext) {

Elnext = el->get_right();

Content *con = (content *)el->get_ent();

printf("port name: %s,", con->p);

printf("DEVS name: %s,", con->devs->get_name());

printf("address: %s,", con->addr->print());

printf("message data: %s,", con->val->print());

4.2 Devs Library

The devs class is the basic class to provide methods for the DEVS formalism. Such functions as d_ext, d_int, and l are implemented as virtual methods to be defined by user. The method for time advance (ta) and port information is also provided by this class. The inject method is useful to send external input events to a model.

Figure 9 Class Hierarchy for DEVS models in DEVS-C++

As shown in Figure 9, an atomicbase has the sigma instance variable which holds the time remaining to the next internal event. This is the time-advance value to be produced by the time-advance function. The destination for sending output message is determined by coupling methods which manipulate coupling information. An atomicbase class realizes the atomic level of the underlying model formalism. It has variables corresponding to each of the parts of this formalism: internal transition function (d_int), external transition function (d_ext), confluent function (d_con), output (out) function, and time advance function (ta). These methods are applied to the state of the model. The atomic class has a phase variable to describe model's phase.

The cellbase and cell classes are similar to atomicbase and atomic respectively. These classes are for cellular models and have address information (which atomic models do not). In this way, large numbers of cellbase or cell models can be manipulated in the same manner. Addresses are used for finding influencees.

The coupled class is the major class to support the hierarchical model composition constructs of the DEVS formalism. The digraph, block and digraphcell are specializations which enable specification of coupled models in specific ways.

Figure 10 The Structure of Hierarchical Model

Figure 11 Composition Tree

A coupled model can become a hierarchical model. The structure of a hierarchical model as shown in Figure 10 is exhibited in a composition tree of Figure 11. The root model ef-am in Figure 11, is a coupled model. It has two components, an atomic model a and a coupled model m. The coupled model m also has atomic models b and c as its components. Appendix 3 gives source code for an example of hierarchical model.

A coupled model can have coupled or atomic models as its components, while atomic models become leaves in the tree. The coupling information needed to construct a coupled model is shown as Figure 11, attached to vertical line descending from the parent node to its children nodes.

4.2 Simulation Engine

Figure 12 shows the flow chart of a simulation cycle in a coupled model. The first step of a simulation cycle is to identify which components are imminent. Each imminent atomic component then generates its output in the compute_input_output phase. A coupled model accumulates all the outputs of its components, and also determines whether each output message of its components is for the internal use (input messages) or outgoing (output messages). After all imminents produce their outputs, the coupled model tells components to execute their delta functions.

Since all the components work simultaneously, an external input may arrive at a component at the very moment when its internal transition function should be executed. Via the confluent function a user can write tie-breaking rules such as selecting the order of the external transition or the internal transition function. By default, the internal transition fuction occurs first.

Figure 12 Simulation Cycle of Coupled model

The internal transition function specifies to which next state a component will transit. For an atomic model, the effect is to place the component in a new phase and sigma, thus scheduling it for a next internal transition. Other state variables may be changed as well. The external transition function (d_ext) with inputs from its influencees also specifies how the system changes state. For an atomic model, the next state is computed on the basis of the present state, the port and value of the input (external event), and the time that has elapsed in the current state.

Figure 13 Time Advance Function of Coupled model

After all messages are transferred to their destinations and every model has changed its state, structural change to add, delete, or move models can be done by a dynamic_structure function. Next, the coupled model components update their tL (time of last event), tN (time of next event) values. The coupled model iterates the simulation cycle until the termination condition is met. Figure 13 illustrates how the time advance function works in coupled models.