Maisie is a C-based language for simulation, or more specifically, it is a language for parallel discrete event simulation. This tutorial provides an interactive introduction to Maisie. The remainder of this introduction provides an overview of discrete event simulation and parallel simulation. This section can be skipped if the reader is familiar with simulation concepts. The Maisie Language begins describing the Maisie language constructs interactively building a small example program. More complex examples are shown in the next section, followed by execution instructions (which are described more fully in the User's Manual), and advanced Maisie facilities.
A simulation model may be used to predict the behavior of a physical system under a variety of operating conditions. In the process-interaction approach to simulation, a physical system is assumed to consist of a set of physical processes that interact with each other at discrete points in time; these interactions are refered to as events. In its simulation model, a logical process (LP) is used to model one or more physical processes (PP); the events in the physical system are modeled by message exchanges among the corresponding logical processes in the model.
Consider a bank teller as a simple example of a physical system. We assume that the bank has n teller windows that are open. A teller is said to be idle if it is not servicing a customer and is otherwise said to be busy. Customers arrive at the bank and wait for service in a common queue. The customer at the head of the queue goes to any teller that is idle. After receiving the desired service the customer leaves the bank. We are interested in measuring the average and maximum time that is spent by a customer in the bank. We may be interested in using the model to examine how these metrics change as the number of tellers, the service rate of the teller, or the arrival rate of customers is modified. The processes in this system are the tellers and the queue of waiting customers; interesting events are the arrival of a customer at the queue (henceforth called the arrival event), departure of a customer form the queue, arrival of a customer at a teller (the begin-service event), and departure of a customer from a teller (the end-service event). We will ignore the time spent by a customer in walking from the head of the queue to a teller window; thus the departure of a customer from the queue and his/her arrival at the teller are really the same event.
In its simulation model, we can define logical processes to model the teller and queue processes in the physical system. The logical processes are refered to as teller and queue respectively. Although the model will contain n tellers, for simplicity we will use teller to refer to a specific teller process. We also define a source process that creates customers. The customers in the physical system are abstracted via the events and need not be modeled as explicit logical processes. The model defines a source process that generates customers and a sink process that collects statistics on the time spent by a customer in the bank. The arrival event can now be modeled by sending a message from the source process to the queue process; the message contains the arrival time of the customer and perhaps a unique id that is used to track the customer. Similarly the begin-service event is simulated by sending a message from the queue to a teller and the end-service event by sending a message from the teller to the sink. The Maisie constructs to define LPs and their interactions via messages are described in the next section The Maisie Language.
A primary activity in a simulation model is the scheduling of future events. For instance, the source must schedule the arrival of future customers and a teller must schedule the end-service event. Some of these events simulate the passage of time in the physical system, whereas others are assumed to occur instantaneously. Messages used to simulate physical events are associated with a send time and a receive time. By default, the send and receive time of a message are set to the simulation time of the sender LP. In general, the receive time of a message can be explicitly set to any future value greater than or equal to its send time. An LP may also suspend itself for a specific interval of simulation time to simulate passage of physical time in performing an activity. For instance, assume that the service time for a client at a teller is t units. On receiving a begin-service message at say time T, a teller may either immediately send an end-service message with a receive time of T+t to the sink LP or it may suspend itself for t time units and then send an end-service message with receive and send times of T+t to the sink. The Maisie constructs to schedule events are described in the Events section.
A Maisie model can be executed using sequential or parallel simulation algorithms. The sequential algorithm typically uses an ordered data structure called the global event list which stores all events that are generated in the system in their timestamp order. Details on the commands to compile and execute a model on a sequential platform are contained in the manual.
For parallel execution, each LP or entity in the model is mapped to a specific processor. Each processor, say P, has its own event list which stores the events for the entities that are mapped to P. Parallel synchronization algorithms have been defined to ensure that events in the event lists stored on different processors are executed in their global timestamp order. In particular each LP must eventually process incoming messages in their global timestamp order. Enforcing this requirement, referred to as the causality constraint, is the central problem in efficient execution of parallel simulations. Two primary approaches have been suggested to solve the synchronization problem: conservative and optimistic.
Conservative algorithms do not permit any causality error: each object in the simulation processes an incoming message only when the underlying synchronization algorithm can guarantee that it will not subsequently receive a message with a smaller timestamp. This constraint may introduce deadlocks, which are typically avoided by using null messages. A null message is a timestamped signal sent by an LP to indicate to other LPs a lower bound on the timestamp of its future messages. If an LP sends a null message with timestamp T+la at simulation time T, we say that the LP has a lookahead of la, (the LP is looking la units ahead in its future). In general, the larger the lookahead of an LP, the better its performance with conservative protocols. Efficient implementation of null messages is also facilitated if each LP maintains the set of its source and/or destination LPs. Maisie provides a set of constructs to specify the lookahead and topology of a model and thus improve its performance with conservative implementations. These constructs are described in detail in the Optimizing for Parallel Execution section.
In optimistic protocols, an LP is allowed to process events in any order; however, the underlying synchronization protocol must detect and correct violations of the causality constraint. The simplest mechanism for this is to have each LP periodically save (or checkpoint) its state. Subsequently, if it is discovered that the LP processed messages in an incorrect order, it can be rolled back to an appropriate checkpointed state, following which the events are processed in their correct order. The rollback may also require that the LP unsend or cancel the messages that it had itself sent to other LPs in the system. An optimistic algorithm is also required to periodically compute a lower bound on the timestamp of the earliest global event, also called the Global Virtual Time or GVT. As the model is guaranteed to not contain any events with a timestamp smaller than GVT, all checkpoints timestamped earlier than GVT can be reclaimed. Maisie provides a set of facilities that can be used to control the various parameters that affect the performance of an optimistic implementation. These include setting the frequency of checkpointing, and GVT computation among others. For a detailed description of these facilities, the reader is refered to the Optimizing for Parallel Execution section.
Details on the commands to compile and execute a Maisie model on different parallel platforms using a variety of synchronization algorithms are contained in the manual.
Maisie is a C-based language that was designed to cleanly separate the simulation model from the underlying algorithm (sequential or parallel) that may be used to execute the model. A program written in Maisie is independent of any synchronization algorithm. When it is compiled, the analyst can indicate the specific simulation algorithm that is to be used to synchronize execution of the model: sequential, parallel conservative, or parallel optimistic. The compiler generates the appropriate code to interface the model with the corresponding run-time system: a splay-tree based implementation of the global event-list algorithm for the sequential implementation, a null-message or conditional event implementation of the parallel conservative synchronization algorithm, or a space-time implementation of the optimistic synchronization algorithm. The compilation of the Maisie program to optimize performance with respect to a specific synchronization algorithm is described in [Maisie 1994].
Maisie has been implemented on a variety of sequential workstations and laptop machines, on networks of workstations and on scalable MPP platforms like the distributed memory IBM SP2 and on symmetric multiprocessor (SMP) platforms like the shared memory SparcStation 1000. It has been used for the parallel simulation of a number of applications in diverse areas including queueing networks, VLSI designs, parallel programs, mobile wireless multimedia networks, ATM networks, and high-speed communication switches and protocols.
Maisie adopts the process interaction approach to discrete-event simulation. An object (also referred to as a PP for physical process) or set of objects in the physical system is represented by a logical process or LP. Interactions among PPs (events) are modeled by message exchanges among the corresponding LPs. We first describe the Maisie primitives to define processes and the interprocess communication primitives and subsequently indicate how they are used to describe events.
A Maisie program is a collection of entity definitions and C functions. An entity definition (or an entity type) describes a class of objects. An entity instance, called simply an entity, represents a specific object in the physical system. Every Maisie program must have a driver entity. This entity initiates execution of the simulation program and serves essentially the same purpose as the main function in C.
The declaration of an entity is syntactically similar to that of a C function; the key difference is that unlike a function, an entity does not return a value. An entity type consists of a heading that declares the name and formal parameters of the entity type and a body that declares local variables and the message types that may be received by the entity type and defines its actions. For instance, the entity type declared in Figure 1 describes an object that models a resource manager. This entity type will be used as a running example to illustrate various Maisie constructs. The heading in lines 1 and 2 of the figure indicates that the entity type is called Manager and has one integer parameter called num_resources. The body of the entity is contained within curly braces in lines 3--16. The body is a compound C statement that may include message declarations (described in the next section) together with standard C declarations. The body may also include constructs to send and receive messages as described subseqeuntly.
An entity is created by the execution of a new statement and is automatically assigned a unique id on creation. Maisie defines a type called ename which is used to store entity-identifiers. The following statement will create an instance of entity type Manager and store its identifier in variable manager, which must be declared to be of type ename.
manager = new Manager{10};
An entity can internally refer to its id using the keyword self. An entity instance terminates itself by `falling off the end'.
1 entity Manager {num_resources}
2 int num_resources;
3 {
4 int resources = num_resources;
5 message Request {ename requester;};
6 message Release;
7 for (;;)
8 wait until {
9 mtype(Request) st (resources > 0) {
10 resources--;
11 invoke msg.Request.requester with Resource;
12 }
13 or mtype(Release)
14 resources++;
15 }
16 }
|
Entities communicate with each other using buffered message passing. Every entity has a unique message buffer; asynchronous send and receive primitives are provided to respectively deposit and remove messages from the buffer.
Maisie uses typed messages. An entity type must define the types of messages that may be received by its instances. A message type is similar to a struct in C and consists of a name and a (possibly empty) parameter list. For instance, two message types are defined for the Manager entity type(lines 5--6): Request which has one parameter of type ename, and Release which has no parameters.
An entity sends a message by executing an invoke statement. Each message is transparently timestamped with the current simulation time and is deposited in the destination buffer at the same (simulation) time at which it is sent. The invoke statement has the following form:
invoke destination with message_type;
where destination is a variable of type ename and message_type is a message whose type has been declared by the destination entity destination. For instance, execution of the invoke statement in line 11 of the Manager will deposit a message of type Resource in the message buffer of the entity identified by requester. Message type declarations are necessary only within the entity type of the destination entity (although for software engineering reasons, message types should be declared in a common header file).
An entity accepts messages from its message-buffer by executing a Maisie wait statement. In its most commonly used version, the wait statement has the following syntactic form:
wait until {
mtype(m_1) [st b_1] statement_1;
or mtype(m_2) [st b_2] statement_2;
.
.
.
or mtype(m_n) [st b_n] statement_n};
where m_i is a message-type, b_i an optional boolean expression referred to as a guard, and statement_i is any C or Maisie statement. The guard is a side-effect free boolean expression that may refer to local variables or message parameters. If omitted, the guard is assumed to be the constant true. The message-type and guard are together referred to as a resume condition and the resume condition together with the statement is refered to as a resume statement. A resume condition with message-type m_i and guard b_i is said to be enabled if the message buffer contains a message of type m_i, which if delivered to the entity would cause b_i to evaluate to true; the corresponding message is called an enabling message. A resume condition that is not enabled is said to be disabled.
For instance, the wait statement in line 8 of the Manager entity consists of two resume statements. The resume condition (line 9) in the first statement ensures that the entity accepts a Request message only if enough resources are available (resources > 0). If so, the resource is allocated to the requesting entity (line 10-11). Keyword msg is used to refer to the last message that was removed from its buffer and delivered to the entity. The second resume statement (line 13) accepts a Release message simply increments the count of available resources. As discussed subsequently, the resume condition in a wait statement may include multiple message-types, each with its own boolean expression. This allows many complex enabling conditions to be expressed directly, without requiring the programmer to describe the buffering explicitly.
If two or more resume conditions in a wait statement are enabled, the timestamps on the corresponding enabling messages are compared and the message with the earliest timestamp is removed and delivered to the entity. By default, if all resume conditions in the wait statement are disabled, the corresponding entity is suspended until it receives an enabling message. A timeout mechanism is also supported as described in the following section.
Each event in a discrete-event simulation model simulates some activity of interest in the physical system and may involve one or more objects. Every event is associated with a time stamp that indicates the time at which the corresponding event occurs in the system. Execution of a discrete-event simulation model requires that all events in the system be executed in their strict time stamp order.
As an event is modeled by a message in a Maisie program, each message carries a timestamp. By default, the timestamp placed on a message is the (simulation) time of the entity that sends the message. A message may be explicitly timestamped with a future time as described later.
The simulation time of an entity can be advanced only when it receives a message or when it executes a hold statement (described next). When an entity with a simulation time t_s, receives a message with time stamp t_e, the simulation time of the entity is set to the larger of t_s or t_e. This ensures that the simulation time of an entity increases monotonically.
A hold statement is used to suspend the entity for a given duration in simulation time. For instance, the following statement will cause the entity executing the statement to suspend until the simulation time of the system advances by t time units. In other words, if the the simulation time of the entity was t_s prior to execution of the hold statement, it will be t_s + t when the entity executes the statement following the hold statement.
hold(t);
As explained earlier, advances in simulation time such as this are used to represent the processing time required by some activity in the physical system being simulated.
As an example, consider the Job entity in Figure 2. The entity periodically sends a request for a resource to the manager and waits to receive the Resource message indicating availability of the resource. It simulates use of the resource by executing the hold statement (line 11) which causes the simulation time for the entity to advance by the specified time interval. It then returns the resource to the pool by sending a Release message to the manager (line 12).
1 entity Job{processing_time, manager}
2 int processing_time;
3 ename manager;
4 {
5 message Resource;
6 for (;;) {
7 hold(processing_time);
8 invoke manager with Request{self};
9 wait until
10 mtype(Resource) {
11 hold(processing_time);
12 invoke manager with Release;
13 }
14 }
15 }
|
Maisie also provides constructs to schedule conditional future events. These are events that may be canceled after they have been scheduled. A conditional event is scheduled by using a variation of the wait statement introduced in the previous section. A wait statement may optionally specify a wait-time as follows:
wait t_c until {
mtype(m_1) [st b_1] statement_1;
...
or mtype (timeout) {
... }
}
Assume that an entity executes a wait statement with wait-time t_c at time t. This causes a message of type timeout, with timestamp t + t_c, to be conditionally scheduled for the entity. This message is cancelled if an enbaling message is available in the message buffer of the entity within the inclusive interval [t, t + t_c]; otherwise the timeout message is sent to the entity by the simulation monitor. The message type timeout is declared automatically by the compiler for every entity and must not be declared by the user. If t_c is omitted, it is set by default to an arbitrarily large number such that the corresponding entity is blocked (potentially forever) until an enabling message is available in its buffer. In particular, if t_c is specified to be 0, the statement works like a non-blocking receive: if the message buffer does not contain any enabling message, the entity will continue execution at the same simulation time at which it was suspended. It follows that a wait statement that includes a wait-time must contain a resume statement that specifies the action to be executed by the entity on receipt of a timeout message.
The event corresponding to the receipt of a timeout message is conditional because it is cancelled if an enabling message is received by the entity. Such a statement can be used to model interruptible and asynchronous activities in the physical system.
We present a series of examples that demonstrate the types of communication topologies that are commonly used in Maisie programs. The examples use a simple entity type called Delay. The entity simply waits until it receives a message of type Ping. On receipt of the message, it suspends itself for a randomly distributed interval (in simulation time) and then forwards the message to one of its communication partners. On completion of the simulation, each entity is sent an endsim message by the run-time system. This message is used by the entity to print out the total number of hops made by the message
The first example demonstrates communication between a pair of Delay entities. The simulation is run for 10000 time units and uses a single Ping message. Every Maisie program must have a driver entity. This entity is responsible for initiating the simulation (similar to the main function of a C program). (Exercise: Modify the example to use 10 ping messages; print the number of round trips made by each ping message at the end of the simulation time.)
entity driver{}
{ ename e1, e2;
e1 = new Delay{1, 10};
e2 = new Delay{2, 10};
invoke e1 with Init_Delay{e2};
invoke e2 with Init_Delay{e1};
invoke e1 with Ping{1,0};
invoke e2 with Ping{2,0};
maxclock ("10000");
}
entity Delay{id, delay_time}
int id, delay_time;
{
ename next;
message Init_Delay {ename id;};
message Ping{int id; int trips;} ping;
wait until mtype (Init_Delay)
next = msg.Init_Delay.id;
while (1)
wait until
mtype (Ping) {
ping = msg.Ping;
if (ping.id == id) {
printf("\n Message No %d: Number of round trips completed %d",
id, ping.trips);
ping.trips++;
}
hold(delay_time);
invoke next with Ping{ping.id, ping.trips};
}
}
|
The next example sets up a ring containing 5 delay entities, where each entity knows the identity of its successor entity. The code for the entity is not changed; rather only the driver is changed to modify the communication topology. (Exercise: modify the program such that each entity knows the identity of both its predecessor and successor entities)
entity driver{}
{ ename prev, next, first;
first = new Delay{10};
prev = first;
for (i = 0; i < 4; i++)
{ next = new Delay{10};
invoke prev with Init_Delay{next};
prev = next;
}
invoke prev with Init_Delay{first}
}
|
We now generalize the definition of a delay entity to allow multiple communication partners. The following entity called DelayFork is connected to N entities. On receiving a ping message, the entity forwards this message to any one of the N neighbors with equal probability. The identity of the communication partners of the DelayFork entity are sent to it using an InitDelayFork message. This message has two parameters count which refers to the number of communication partners for the entity and array id-set that contians their identifiers. The declaration of the array id-set restricts the entity to a maximum of 10 communication partners.
entity DelayFork{id, delay_time}
int id, delay_time;
{
ename next[10];
int i, N;
message InitDelayFork{int count; ename id-set[10];};
message Ping{int id, hops;} ping;
wait until mtype(InitDelayFork) {
N = msg.InitDelayFork.count;
for (i = 0; i < N; i++)
next[i] = msg.InitDelayFork.id-set[i];
}
while (1)
wait until mtype (Ping) {
ping = msg.Ping;
printf("\n Message No %d: Number of hops completed %d",
id, ping.hops);
hold(delay_time);
invoke next[urand(1,N)] with Ping{ping.id, ping.hops++};
}
}
|
The driver entity to set up a fully connected network of 5 DelayFork entities is as follows:
entity driver{}
{ ename eids[5],i;
for (i = 0; i < 5; i++)
eids[i] = new DelayFork{i, 10};
for (i = 0; i < 5; i++)
invoke eids[i] with InitDelayFork{5, eids[0]:5*sizeof(ename)};
maxclock ("10000");
}
|
entity PriorityServer{}
{
message HighPriorityJob{int processing_time;} high;
message LowPriorityJob{int processing_time;} low;
int time_left;
int current_time;
while (1) {
wait until {
mtype (HighPriorityJob) {
high = msg.HighPriorityJob;
hold high.processing_time;
/* process job */
}
or mtype (LowPriorityJob) {
low = msg.LowPriorityJob;
current_time = sclock();
time_left = low.processing_time;
while (time_left > 0) {
wait time_left until {
mtype (HighPriorityJob) {
time_left -= (sclock() - current_time);
current_time = sclock();
high = msg.HighPriorityJob;
hold high.processing_time;
/* process job */
}
or mtype (timeout) {
time_left = 0;
/* process low priority job */
}
}
}
}
}
}
}
|
Many distributed systems are structured as producer consumer systems, where a producer processes generate some data and consumer processes use the generated data for further computation. As the producer and consumer processes may proceed at different rates, applications use a fixed-size buffer for temporary storage of the data. Instead of sending data directly to the consumer, the producer deposits it in the buffer; similarly the consumer process requests data from the buffer rather than directly from the producer process. The buffer must ensure that the data is sent to the consumer in the same order that it is received form the producer. Also, a producer (consumer) process is blocked if the buffer is full (empty).
As an example, consider a system where a sattelite collects atmospheric data that is perhaps aggregated or pre-processed by an onboard computer. The satellite transmits the collected data to a ground-based computer that uses it for weather prediction in different parts of the country. The satellite may be viewed as a producer of data and the weather prediction model as the consumer, with the intermediate storage device as the bounded buffer.
We describe a Maisie model of a producer consumer system. The model parameters include produce-rate, consume-rate, and buffer-size, where the first two parameters represent the mean rates at which the producer and consumer processes generate data and the third parameter is the size of the buffer. The actual rates at which the data is generate dor consumed is determined by a random exponential distribution with the given mean. For a given set of parameters, the model computes the average, maximum, and minimum number of elements that are present in the buffer.
Animation: number of elements in the buffer
Excercises:
Computer systems are among the most common application of performance modeling studies. We consider a simple computer system with a central processing unit (cpu process) and a disk manager that controls a bank of disk drives. A job in the physical system first requests service from the cpu, which services incoming requests in a fifo order. When a job completes service at the cpu, with probability p it departs the system and with probability (1-p) it requests service from the disk-manager. The disk-manager manages a number of disks and each request identifies a specific disk for service. Each disk also services its request using a fifo service discipline. After being serviced at a disk, the job departs the system with probability p and goes back to the cpu with probability (1-p).
In our model, we use a source process to generate new job arrivals at the cpu at a given rate called arrival-rate. A sink process is used to model the departure of a job from the system. The service times of the cpu and disk are given by mean-cpu-time and mean-disk-time respectively. The model computes the average waiting time and average number of waiting jobs at the cpu and disk manager.
Animation: Number of jobs waiting at the cpu and/or disk
Excercises:
Dirty code: the example called resource.may in /r/misc1/maisie/Examples is a bit different from the one described here -- there is asingle disk and job routing is deterministic. One possibility is to start with the simple model that is described in resource.may and introduce the variation described above as a refinement ...
This problem captures the resource contention problems inherent in many distributed systems. In its original formulation, the problem postulates a set of five philosophers who are sitting at a round table. The table has a bowl of spaghetti in the center and a single fork between neighboring philosophers. Each philosopher cycles through a set of three states: thinking, hungry, and eating. Initially all philosophers are thinking; a philosopher may autonomously make a transition from the thinking to the hungry state (a thinking philosopher may never become hungry). A hungry philosopher needs the forks on both sides before s/he can eat and may only pick up one fork at a time. An eating philosopher must become thinking in finite time, at which point s/he replaces the forks to their original position.
A generalization of the dining philosophers problem can be represented by a conflict graph: The philosophers are represented by nodes in a graph. Two philosophers are neighbors (i.e. they have an edge between them) if they are potentially in conflict with each other for a resource. A philosopher can have an arbitrary number of neighbors. A unique fork is associated with each edge. A hungry philosopher must obtain the forks associated with all edges that are incident on that philosopher before s/he can eat. Initially each fork is assigned to one of the two philosophers that are situated at the two end points of the corresponding edge. A hungry philosopher requests forks that s/he doesn't currently hold by sending a request message to the corresponding neighbor. Each algorithm defines a set of rules for a philosopher to request forks and release forks in response to requests from neighbors.
In this example we will describe two different algorithms for the dining philosophers problem. For each algorithm, we will develop a model that computes the average time spent by each philosopher in the hungry state and the average number of messages exchanged between philosophers for each hungry to eating transition. The parameters to the model include mean-think-time, mean-eat-time, and delay. The first two parameters respectively refer to the mean time spent by each philosopher in the thinking and eating states. The third parameter refers to the mean time to transmit a message between any pair of phiosophers.
Algorithm 1: This algorithm works only for conflict patterns like those in the original dining philosophers problem where each philosopher has exactly two neighbors. The clockwise neighbor of a philosopher is termed C and the anti-clockwise neighbor A. One philosopher is arbitrarily designated the tie breaker. All philosophers except the tie breaker obey the following rules: on becoming hungry, a philosopher, say p, first obtains the fork shared with the C neighbor. If p does not have the fork, it sends a request for the fork to the C neighbor. On receiving the request, a philosopher sends the fork if he is thinking; otherwise the request is deferred until the philosopher is in the thinking state. Once P has the fork shared with the C neioghbor, only then does he try to obtain the fork shared with the A neighbor. The rules for requesting and releasing a fork remain the same. In contrast, the tie breaker philosopher first obtains the fork shared with the A neighbor and then the C neighbor. It is easy to show that any chain of waiting philosophers that may form in the system will always be terminated at the tie breaker philosopher. This guarantees that no philosopher will wait forever to receive a fork and hence no philosopher can stay hungry forever.
Animation: 3 colors representing philosophers in each state.
Excercises:
CLean code: Rich should have sth that can easily be adapted to include the specified parameters.
Algorithm 2: The second algorithm will work with an arbitrary conflict graph. Each fork can be in one of two states: dirty or clean. Initially each fork is dirty. A fork that is used for eating by a philosopher becomes dirty. A dirty fork becomes clean when it is sent from one philosopher to its neighbor. When a philosopher becomes hungry, he simultaneously requests all forks that are not currently owned by him by sending a request message to the corresponding neighbor. On receiving a request, a philosopher must satisfy the request if he is thinking or if he is hungry and the fork is dirty. Thus a philosopher will defer a request only if he is eating or if he is hungry and the fork is clean. In the first case, he must eventually stop eating and send the fork to the neioghbor. It is possible to show that a chain of waiting philosophers can never form a cycle and that every hungry philosopher will eventually eat.
Excercises:
Show that an initial fork placement that causes a cycle in the graph can lead to deadlock.
Code: The version provided by Galles should be easily adaptable.
Maisie programs are executed just as normal C programs are executed. Please see the Maisie User's Manual for details on compilation and execution of Maisie Programs.
A Maisie program is a collection of entity and function definitions. Each program must include an entity called driver. This entity plays a role similar to the main function of a C program -- execution of a Maisie model begins by executing the first statement in the body of the driver entity.
A Maisie simulation terminates when the simulation clock exceeds the specified simulation horizon (the time period over which the model is to be simulated). (Rich: pls add a pointer to the description of the maxclock function).
By default, the timestamp placed on a message is the (simulation) time of the entity that sends the message. A message may be explicitly timestamped with a future time using the following variation of the invoke statement:
invoke destination with message_type after t
The preceding statement will cause the message message_type to carry a timestamp of clock+t, where clock refers to the current simulation time of entity destination.
For instance, the body of the job entity in Figure 2 could be written as shown in Figure 7 where both invoke statements use the after clauses to store explicit future timestamps on the messages. However, there is one significant difference between using a hold statement followed by an invoke and directly specifying the timestamp in the invoke statement: in the former case, the hold statement causes the simulation time of the entity to advance; not so in the latter. In particular, the hold statement is used to simulate processing time within the entity, while the invoke ... after construct is used to simulate a transmission delay.
1 entity Job{processing_time, transmission_delay, manager}
2 int processing_time;
3 int transmission_delay;
4 ename manager;
5 {
6 message Resource;
7 for (;;) {
8 invoke manager with Request{self} after transmission_delay;
9 wait until
10 mtype(Resource) {
11 hold(processing_time);
12 invoke manager with Release after transmission_delay;
13 }
14 }
15 }
|
Several Maisie Facilities are available for specifying more complex resume conditions in wait statements, such as using message parameters in guards, rankers, compound resume statements, etc. Most of these facilities are more useful to the parallel programmer. In simulation, it is usually appropriate for the message with the lowest time-stamp to be chosen. Nevertheless, some of these features will be described briefly.
The guard in a resume statement can reference both local variables of the entity and message parameters. For instance, assume that the manager in our running example receives requests for one or more printer units and that incoming requests are serviced using the first-fit discipline. The following fragment shows how the resume condition is modified to ensure that a Request message is accepted only if the requested number of units are available.
message Request {ename requester; int count; };
.
.
.
wait until {
mtype(Request) st (msg.Request.count <= resources)
.
.
.
Maisie also provides a number of pre-defined functions that may be used by an entity to inspect its message buffer. For instance, the function qsize(m_t) returns the number of messages of type m_t in the buffer. A special form of this function called qempty(m_t) is defined, which returns true if the buffer does not contain any messages of type m_t, and returns false otherwise. This function may be used to impose priorities on incoming messages. Assume that the manager is to be modified such that a request message is accepted only if no Release messages are present in the buffer. A simple way to do this is to strengthen the guard for the Request message as follows:
wait until {
mtype(Request) st (qempty(Release) && (msg.Request.count <= resources))
The ranker facility gives the user the ability to select a message to process by comparing some parameter value of all available messages. If the message buffer contains exactly one enabling message, then that message is delivered to the entity. If the buffer contains more than one enabling message of a given type, the ranker is used to select a unique enabling message: if keyword max (min) is used, the enabling message with the largest (smallest) value for parameter is delivered to the entity.
This ranking supersedes the default time-stamp ranking, so it may be advisable not to use rankers in a simulation context.
The following example (taken from the Maisie User's Manual) illustrates simple wait statements with a single resume statement. The resume condition in the first wait statement is enabled if the message-buffer contains a req message. The resume condition in the second wait statement is enabled only if the buffer contains a req message whose parameter units is not greater than the entity variable units. Note, since the value of the mvar oldreq is not modified until an enabling message is received, msg must be used in the guard to reference the message being inspected. The last example causes req messages to be sorted and received in increasing order of the message parameter units.
wait until mtype (req);
wait until oldreq = mtype (req)
st (msg.req.units <= units); /* First-Fit */
wait until oldreq = mtype (req) min units
st (msg.req.units <= units); /* Least-Fit */
At times, we would like to not process an event until two or more enabling conditions are met. For example, in the Dining Philosophers problem, the Philosopher cannot eat until he acquires two forks. This can be specified in Maisie using a compound resume, in which the keyword and is used to conjoin multiple resume conditions. The following is a generic example of its use.
wait until
mvara = mtype (ma) [max va] [st ba]
and mvarb = mtype (mb) [max vb] [st bb]
and mvarn = mtype (mn) [max vn] [st bn]
{
statement;
}
Friend functions may very well be removed from the next release of the Maisie compiler. To ensure compatibility, we recommend that you not use them.
Executing in parallel requires that the program be linked with one of the parallel runtime systems. See the Maisie User's Manual for details on compilation options. However, to run effectively in parallel, a number of additional guidelines should be followed, and in some cases are explicitly required.
Parallel Maisie programs must conform to the following restrictions. These restrictions apply to almost any message-based parallel language and are not specific to Maisie. The Maisie compiler will not generate errors or warnings for the following problems because the same compiler is used whether the simulation is run sequentually or in parallel. (Simulation algorithms are switched by linking in another simulation runtime library.) When a program violating these rules runs in parallel it will most likely abort or produce incorrect results.
There are exceptions to this rule. Read-only variables initialized at the beginning of the simulation can be global. The problem with this on distributed memory machines is that the initial values assigned on one node are not propagated to any other nodes. Thus each node's global variables must be initialized individually. One way to solve this problem in a portable fashion would be to initialize the globals when they are first used by reading the proper values from a centrally accessible file.
For parallel implementations, the simulation model must be partitioned by allocating entities among the processors. Maisie allows the programmer to specify the specific node on which an entity will be created by using the at option during entity creation. In general, the model should be partitioned (entity to node map) such that message communication between nodes is minimized. Also, there must be some parallelism in the simulation, i.e. multiple nodes should be doing work on the simulation concurrently. For example, a simulation with a single packet bouncing around a network will not have any parallelism. Depending on whether the parallel execution uses conservative or optimistic algorithms, further refinements, described in the next sections, may be needed to the model to improve its performance.
There are two main changes that need to be made to a simulation program written in Maisie, in order to enable it to run using conservative protocols: communication topology and lookahead.
The runtime system needs to be informed about the communication topology between the entities in the system. This information is used by the system to do the necessary synchronization. The runtime system implicitly maintains a source-set and a destination-set for each entity. source-set is the set of all the entities that a given entity can receive messages from, and destination-set is the set of all the entities that it can send messages to. Every entity needs to inform the runtime system of the entities in its source or destination set. This is done by using the following maisie system calls:
Exceptions:
For the conservative runtime, the sparser the topology, the better the performance. Therefore, only add the sources and destinations that are actually going to be used. If you have more links than you are going to use, e.g. a completely connected network, it is not going to create an error situation - it is only going to make the simulation more inefficient (note that you have to ensure that lookahead is non-zero in every cycle of links -- see the next section. Introducing unnecessary links may make this job tougher).
Whenever an entity issues a wait in Maisie, there is a possibility that it may be suspended (for instance, if the message buffer does not contain any messages of the type specified by the wait statement). Before being suspended, an entity can inform the runtime about the minimum timestamp increment (i.e. the difference between the timestamp on an outgoing message and the timestamp on the preceding input message) on the earliest output that the entity may generate. This value is called lookahead, and is expressed using the function call zzcla(v) , where v is the value of the lookahead.
Lookahead is used by the runtime to ensure that the parallel simulation does not deadlock, and to improve its performance. A sufficient condition (weaker conditions also exist, but we will not discuss them, in order to keep discussion simple) to avoid deadlock is as follows: In every cycle of the simulation model, there should be at least one entity that always issues a zzcla(v) with a positive v before going into a wait statement. In general, the larger the lookahead in the system, the better the performance (simulation speed).
Consider the following situation: A pre-emptive priority server entity has scheduled a timeout after timestamp t, corresponding to a tentative departure of a low priority job, if no high priority job arrives before the timeout. The entity, therefore, is suspended waiting for a high message, or a timeout message. Suppose the precomputed service time for the high job is s. If the next job that leaves the entity is in response to a high job received (which will pre-empt the current job), then the timestamp increment would be equal to s. But, if the next job goes out in response to the timeout message (i.e. if the current job is not pre-empted), the timestamp increment is zero. Therefore, according to the definition of lookahead given above, the lookahead that the entity can express before going into the wait would be only zero. Another lookahead construct zzmaxla(v) is provided to help in such situation. In the above described situation, before going into wait, user can say zzcla(s) and zzmaxla(sclock() + t) which means that the lookahead of the entity is equal to s, subject to a maximum value of sclock() + t. Whenever max lookahead is not relevant, the programmer needs to say zzmaxla(MAXINT) before every wait statement.
Both zzcla(v), zzmaxla(v) need to be explicitly set before issuing a new wait because these values are reset after each message receive.
Examples:
Variables
This is an optimization in the memory management: when the program calls mayc_Fmalloc(nbytes), the runtime will get a block of memory, partition this block into small pieces, and put them into the free memory pool in the runtime.
The remaining two functions are used to allocate memory blocks of variable sizes and are analogous to the standard dynamic memory allocation function provided by UNIX.
Variable-size memory operations are supposed to be used infrequently
and for larger data structures.
NOTE: Memory allocated by standard C libraries (malloc() etc.) should not be freed at the end of the simulation with the free() function, because this will prevent rollback.
Messages
entity Distributor{} {
for(;;)
wait until {
mtype(request_from_A) {
assign a job to A;
}
or mtype(request_from_B) {
assign a job to B;
}
}
}
If both a request_from_A and a request_from_B messages arrive at the same simulation time, but the request_from_B arrives earlier in real time, the distributor will give job1 to B, and later give job2 to A. However, if the distributor entity is rolled back, it may assign job1 to A and job2 to B because both requests are in its input queue after the rollback. This kind of non-determinism will confuse the optimistic runtime system into reporting an error. This is a subtle error which requires careful design to avoid.
message mymsg { int k;} output;
wait until mtype(mymsg) {
output = msg.mymsg;
output.k += 3;
invoke other_entity with output;
}
Input and Output
FILE *fin;
char line[LSIZE];
while( fgets( line, LSIZE, fin ) != NULL ) {
wait until mtype(mymsg) {
process mymsg according to the context of the array "line".
}
} /* while */
The correct way of programming is:
FILE *fin;
char line[LSIZE];
int f_offset = 0;
while(1) {
fseek(fin, f_offset, 0);
if( fgets(line, LSIZE, fin) == NULL ) break;
f_offset += strlen(line);
wait until mtype(mymsg) {
process mymsg according to the context of the array "line".
}
} /* while */
System Parameters
In order to assign values to these parameters, users need to create a file called mayc_opt_parameters . Users can insert "parameter value" pairs in the file. If a parameter is not specified by users or the file "mayc_opt_parameters" does not exist in the current working directory, the runtime system chooses default values.
File mayc_opt_parameters contains:
------------------------
save_interval 30
throttle_window 4000
gvt_window 300
------------------------
This is the output generated by the optimistic runtime system:
------------------------------------------------------------------------- | Total nodes | xth node | ftime | clock | max sim_t | f_minu | | 2 | 1 | 52.61 | 4.01 | 168001 | 38.55 | ------------------------------------------------------------------------- | Save_inter | Send_ev | Wait_w | sync_ev | garbage_w | throttle_w | | 60 | 1 | 1 | 500 | 0 | 4000 | ------------------------------------------------------------------------- |Ent_exe_t|State_sve_t| Block_t | Rlback_t |Garbage_t| Wait_t | Send_t | | 31.10 | 1.98 | 1.46 | 0.39 | 0.12 | 15.24 | 2.58 | | 4056 | 76 | 33 | 12 | 69 | 248 | 123 | ------------------------------------------------------------------------- |True_comp| msg_out |canceled | resent |remote_srh| sys_srh| event_q| | 96.83% | 123 | 1 | 0 | 2.20 | 0.02 | 1.35 | -------------------------------------------------------------------------
Misc