Entities communicate with each other via buffered message-passing. Every entity is associated with a unique message buffer. Asynchronous send and receive primitives are provided to respectively deposit and remove messages from the message buffer of an entity. The receive primitive may also be used to advance the simulation clock.
Maisie uses typed messages. A message-type consists of a name and a parameter list. Every entity must define the types of messages that may be received by it. The following syntax is used to define a message-type:
message-def ::= message ident [{ declarations }] [ident]... ;
declarations ::= [type ident [,ident]...;]...
type ::= ename | clocktype | message ident | any C type declaration
Message definition is syntactically similar to the declaration of C structs. Message parameters may be viewed as fields defined within a struct and are referenced using the same `.' operator as used to reference fields within a C struct. A message-type with an empty parameter-list is used to define signals (e.g. acknowledgments).
In the following example, we elaborate the entity type manager to include definition of two message types: release with an integer parameter and message-type request with two parameters: id of type ename and an integer parameter called units. Variable oldrequest is declared to store messages of type request.
Example:Three message types timeout, endsim, and trace_msg are implicitly defined by the system for every entity. Trace_msg is used to initiate the tracing mode in an entity (section 5.2) and a timeout message is used by an entity to delay itself for a specified time interval (section 3.2). An endsim signal is delivered by the Maisie runtime system to each entity in the system when a Maisie simulation is terminated (section 4.3.)entity manager { max_printers } int max_printers; { int units; message release { int units; }; message request { int units; ename id;} oldrequest; ... }
Remarks:
An entity sends a message to another by using an invoke statement. This statement has the following syntax:
invoke-st ::= invoke ename-expr with msg-type [msg-expr] [after time-expr];
ename-expr ::= an expression of type ename
msg-expr ::= { [arg]...} | = msg-ident
time-expr ::= an integer expression whose value is >= 0
arg ::= array-param | C expression
array-param ::= a pointer expression[:: a positive integer-valued expression]
msg-type ::= a message type defined for entity ename-expr
msg-ident ::= a variable of type msg-type
The invoke statement performs an asynchronous send: the sending entity copies the message parameters into a memory block, delivers the message to the underlying communication network, and resumes execution. Every message is implicitly timestamped with the current value of the simulation clock. The programmer may specify a different timestamp by using the optional ``after time-expr'' attribute---this causes the timestamp of the message to be set to the current simulation time plus time-expr. A message is delivered to the destination buffer at the simulation time specified by its timestamp. The following examples demonstrate several ways of sending a request message to entity s1 (which is an instance of the entity type manager defined previously). The first statement specifies the message parameters explicitly; the second specifies that the message be copied from variable oldrequest. The last example will cause the request message to be delivered to the message buffer of the destination entity after 5 time units.
Example:invoke s1 with request { 10, self }; invoke s1 with request = oldrequest; invoke s1 with request = oldrequest after 5;
A message may include array parameters which are passed by value. If a formal parameter of a message is declared to be an array, the corresponding actual parameter will be treated as an array. The actual parameter may specify an array slice by specifying the position of the first element followed by an optional size that specifies the number of bytes to be transmitted. If the size is omitted, it will default to the size declared for the corresponding formal parameter. The following example passes a message value with elements x[10]..x[14] to entity e2.
Example:In receiving entity(entity declaration for e2): message value { int count; int a[10]; }; In sending entity: int x[20]; ... invoke s1 with value { 5, &x[10]::5*sizeof(int) }; /* Send 5 integers from x[10]..x[14] */ ...
Remarks:
An entity accepts messages from its message-buffer by executing a wait statement, which has the following syntax:
wait-st ::= wait [wait-time] [until resume-block];
resume-block ::= resume-st | { [declarations] resume-st [or resume-st]...}
resume-st ::= resume-cond statement
resume-cond ::= [mvar=] mtype(msg-type) [max/min ranker] [st (guard)]
wait-time ::= a C expression of type int
guard ::= a C expression without side-effects
mvar ::= a variable of type msg-type
ranker ::= a formal parameter declared in msg-type
declarations ::= [type ident [,ident]...;]...
type ::= ename | clocktype | message ident | a C type declaration
statement ::= any C or Maisie statement
The wait statement has two components: an optional wait-time(
) and a resume-block. The resume
block is a set of resume statements, each of which consists of a
resume condition followed by a C or Maisie statement. The resume
condition consists of a message type, an optional ranker, and
an optional guard.
and guard 
is said
to be enabled if the message buffer contains a message of
type and evaluates to true ( is evaluated only if the buffer contains a
message of type ); the
corresponding message is called an enabling message. In
general, the buffer may contain many enabling messages.
If the message buffer contains exactly one enabling message, the message is removed from the buffer and delivered to the entity in variable mvar, which then resumes its execution. The variable mvar is often omitted, in which case the enabling message is returned in a system defined variable msg. 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 ranker is delivered to the entity. If the ranker is omitted, the messages are ranked in increasing order of their timestamps. The selected message is removed from the buffer and delivered to the entity either in the corresponding variable mvar or, if mvar is not specified, in variable msg. Note that a mvar specified in a resume condition is modified only if a corresponding enabling message is selected for delivery to the entity.
The following example 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 request message (as defined in entity manager at the beginning of this section). The resume condition in the second wait statement is enabled only if the buffer contains a request message whose parameter units is not greater than the entity variable units. Note, since the value of the mvar oldrequest 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 request messages to be sorted and received in increasing order of the message parameter units.
wait until mtype (request); wait until oldrequest=mtype (request) st (msg.request.units<=units); /* First-Fit */ wait until oldrequest=mtype (request) min units st (msg.request.units<=units); /* Least-Fit */
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. If the message timestamps are equal, and neither one of the messages is a timeout, an enabling message is selected non-deterministically for delivery to the entity (timeouts are discussed subsequently). Consider the manager entity type in Figure 1. The entity receives messages of type request and release. Both resume conditions in the wait statement of the entity will be enabled if the buffer contains a release message and also a request message that satisfies the corresponding guard. Note that when the keyword msg is used in a guard, it refers to an arbitrary message in the message buffer; when used in a statement, it refers to the most recent message delivered to the entity.
entity manager { max_printers }
int max_printers;
{ int units = max_printers;
message release {int units;};
message request {int units; ename id;} oldrequest;
for (;;)
wait until
{ mtype (request) st (msg.request.units <= units)
{ units -= msg.request.units;
invoke msg.request.id with done;}
or mtype (release)
units += msg.request.units;
}
}
An entity is said to be suspended if none of its resume conditions are enabled. A suspended entity resumes execution if it receives an enabling message. However, if an entity executes a wait statement that includes only local guards and all guards evaluate to false, the entity is in deadlock. The runtime system will detect such an error, print out a warning message, and skip the corresponding wait statement.
If a wait statement executed by an entity specifies a wait time (),
execution of the statement schedules a timeout message for the entity.
This is a conditional message which is sent to the entity if it does not receive an
enabling message prior to expiration of ; otherwise the message
is canceled. Thus, the timeout message is delivered only if the
entity's buffer does not contain any other enabling message with the
same (or smaller) timestamp. Assume that the following
wait statement is executed by an entity at (simulation) time T:
The entity will resume execution with an ack message if it receives such a message with timestamp at most T+max_round_trip_delay. Otherwise, it resumes execution at simulation time T+max_round_trip_delay with a timeout message. Note that if both resume conditions are enabled (that is if the earliest ack message in the buffer has timestamp T+max_round_trip_delay ), the ack message will be delivered to the entity and the timeout message canceled.wait max_round_trip_delay until { oldack=mtype (ack) process acknowledgement.. or mtype (timeout) resend the message; }
The next wait statement contains a single resume condition that is enabled if a timeout message is available. It follows that the entity will resume execution on receipt of a timeout message after 5 units of simulation time have elapsed.
wait 5 until mtype (timeout);
The preceding wait statement is used in a simulation to suspend an entity unconditionally for a specified duration to simulate activities like servicing a request. Such a wait statement may be abbreviated by a hold statement. This statement has the following syntax:
hold-st ::= hold (wait-time); wait-time ::= a C expression of type int
A hold statement is translated by the Maisie compiler into an equivalent wait statement; this is not a new statement but simply a notational convenience. Thus the following hold statement will have exactly the same semantics as the preceding wait statement.
hold(5);
When an entity executes a wait statement, it may be suspended if its buffer does not contain an enabling message. If the wait-time in the wait statement is specified to be 0, the entity will resume execution at the current simulation time. In the following example, if the message buffer of the entity does not contain any request message, a timeout message will be delivered to the entity with the current simulation time. This ensures that the entity will not be blocked indefinitely.
Example:Note that the lower priority of the timeout message ensures that this message is delivered to the entity only if no other enabling message is available.wait 0 until { mtype (request) process-this-message; or mtype (timeout) /* request message unavailable */ do-something-else; }
Remarks:
Example:We recommend that the enabling message either be saved in a variable in the resume-condition or be copied explicitly by copying variable msg to a local entity variable.wait until mtype (request) process-this-message; hold(1); invoke msg.request.id with done; /* ERROR!! */
and guard , if
references message parameters
(as in the request message in the preceding example), the
corresponding resume condition is enabled if any message of type in the buffer satisfies the guard.
In particular if the first message in the buffer, requests a large
number of units, it is possible that it may never be satisfied as
smaller subsequent requests are serviced continuously. The first wait
statement in the following fragment illustrates this situation.
Alternately, it is sometimes desirable to define the resume condition
such that it is enabled only if the first message of type in the buffer is an enabling
message, and is disabled otherwise. Among other things, this may be
used to prevent the kind of starvation scenarios outlined in the
preceding situation. Maisie provides a function called
qhead() where parameter
is a message type. The
function returns a copy of the first message of type in the message buffer; if the buffer does not
contain any messages, the
return value is undefined. The second resume condition in the
following fragment uses function qhead() to serve incoming
request messages in the order of their arrival.
wait until mtype (request) st (msg.request.units<=units); /* first-fit service discipline */ wait until mtype (request) st ((qhead(request)).units<=units); /* FCFS */
). The
function returns true if the buffer does not contain any messages, and returns
false otherwise. For instance, the following wait statement
gives higher priority to release messages---it receives
request messages only when no release messages is
available.
wait until mtype (request) st (!qempty(release) && msg.request.units<=units) ... or mtype (release) units += msg.release.units;
In its most general form, a resume statement may include resume conditions associated with multiple message types as follows:
= mtype (
) [max
] [st
] and
= mtype (
) [max
] [st
] ... and
= mtype (
) [max
] [st
]
statement;
The resume-statement is enabled if the message buffer contains a different enabling message for each conjunct resume condition. If the statement is enabled, the corresponding set of enabling messages is removed from the buffer and delivered to the entity in the specified message variables, and the keyword msg will reference an arbitrary enabling message. The and operator in the compound resume condition is a short circuit operator; the various conjuncts are evaluated in a left-to-right order and a conjunct is evaluated only if the message buffer contains an enabling message for each of the preceding conjuncts in the resume condition. The sequence of enabling messages for a compound resume condition is referred to as the enabling sequence. The largest timestamp of all messages in this sequence is referred to as the timestamp of the enabling sequence. If a compound resume condition is enabled together with other resume conditions in a wait statement, the timestamp of the enabling sequence is used in selecting a unique message (sequence) for delivery to the entity.
In a compound resume condition, the enabling message of a conjunct
resume condition may be referenced in the guards of the resume
conditions appearing to its right. For example, in a compound
condition of the form
=r1 and
=r2, the guard in resume condition r2 may reference
message variable as the
enabling message associated with r1. However, the value of
variable is modified only if
the corresponding enabling sequence is delivered to the entity;
otherwise the value of a message variable is left unchanged. Note, if
the guard in r1 references , it would refer to the value of before the execution of the wait
statement.
We illustrate the use of compound resume statements by modifying the manager entity type to include channel resources. Assume that requests for a channel are satisfied only in pairs that match a sending process with a receiving process. The sender process requests a channel using a chnls message and the receiver process uses a chnlr message. A process requests access to a specific channel that is identified by a unique id. A chnls request is said to match a chnlr request only if both messages contain the same channel id. Manager grants the requests for a channel only when it has received matching requests and the desired channel is available. Similarly a channel becomes available only when it has been released by both the sender and receiver processes. The modified entity type is described in Figure 2. Message types for requesting a channel are defined in lines 5--6 and those used for releasing a channel in lines 7--8. The wait statement is augmented to include a resume statement (lines 20--21) to handle channel allocation: the entity accepts a pair of matching requests only if the requested channel is not being used. Because the and operator is a short-circuit operator, the specified condition gives priority to the chnls message; that is, if the buffer contains many matched pairs, the pair with the earliest chnls message will be removed first. In case no pairs of enabling messages are identified, the value of variables csend and crecv remains unchanged. Similarly messages to release a channel are also accepted only when a matched pair is available.
1 entity manager { max_printers }
2 int max_printers;
3 {
4 int i, units = max_printers, cfree[MAXC];
5 message chnls {ename hisid; int cno;} csend;
6 message chnlr {ename hisid; int cno;} crecv;
7 message free_s {int cno;} fsend;
8 message free_r {int cno;};
9 message release {int units;};
10 message request {int units; ename id;} oldrequest;
11 for (i = 0; i < MAXC; i++)
12 cfree[i] = 1;
13 for (;;)
14 wait until
15 { mtype (request) st (msg.request.units <= units)
16 { units -= msg.request.units;
17 invoke msg.request.id with done;}
18 or mtype (release)
19 units += msg.request.units;
20 or csend = mtype (chnls) st (cfree[msg.chnls.cno])
21 and crecv = mtype (chnlr) st (msg.chnlr.cno == csend.cno)
22 { cfree[csend.cno] = 0;
23 invoke csend.hisid with alloc{cno};
24 invoke csend.hisid with alloc{cno}; }
25 or fsend = mtype (free_s) and mtype (free_r) st (msg.free_r.cno == fsend.cno)
26 cfree[fsend.cno] = 1;
27 }
28 }
Remarks:
In the following example, line 2 is incorrect because message-type m1 is used twice in a compound resume condition. The rankers in line 3 and 4 are in conflict because they specify different orders (max and min). Similary, both line 5 (different ranker time) and line 6 (time-stamp order) are inconsistent with line 2 and 3.
Example:1 wait until { 2 mtype (m1) and mtype (m1); /* Error: m1 specified twice */ 3 or mtype (m2) max value; 4 or mtype (m2) min value; /* Error: different order */ 5 or mtype (m2) min time; /* Error: different ranker */ 6 or mtype (m2); /* Error: different order */ 7 }
Next: Miscellaneous Features
Previous: Entity
Up: Contents