Graphics Programs Reference
In-Depth Information
derives from the folding of t (0)
r0 ,t (1)
r0 ,t (2)
r0 , and t (3)
r0 .
An analogous folding is
done for timed transitions and places.
The GSPN model in Fig. 9.5 comprises only one ECS of immediate tran-
sitions, obtained from the folding of the four ECSs of Fig. 9.4. Five P-
semiflows cover all the GSPN places, similarly to what happened in the
GSPN of Fig. 9.4. Four of them refer to individual queues and have the same
support as the first four P-semiflows described for the GSPN in Fig. 9.4. The
resulting P-invariants have a token count equal to one. This guarantees that
places p (q a , p (q)
q , p (q s , with q = 0, 1, 2, 3 are 1-bounded. The fifth P-semiflow
covers places p (q p , p (q s , with q = 0, 1, 2, 3, and places p r , p w0 , p w1 , p w2 , p w3 .
The token count for the resulting P-invariant is S. As a result, the GSPN
model is bounded. A number of T-semiflows cover all transitions, so that the
structural characteristics of the GSPN fulfil the necessary condition given in
Chapter 2 for the model to be live and reversible. The reachability analysis
shows that the GSPN model indeed is live and reversible.
It should be emphasized that the GSPN model in Fig. 9.5 actually entails
an abstraction with respect to the operations in the real system. Indeed,
in the real system, servers do not join in a single place from which they
are routed to the next queue to be visited; this feature is introduced in the
model in order to obtain a simplified description (and thus a smaller number
of states) that is equivalent to the detailed one from the point of view of
the present study. It can be proven that this simplification does not alter
customer delays, waiting times, and queue throughputs.
9.3.1
Walking before choosing?
In the GSPN model in Fig. 9.5, since the same exponentially distributed
random variable with mean ω −1 can describe the walk times from any queue
to any other queue, the timed transitions T w0 ,T w1 ,T w2 , and T w3 all have the
same rate ω and the same infinite-server semantics.
We can now observe that a server arriving at place p r in Fig. 9.5 makes a
choice depending on the weights of the immediate transitions, and then, in-
dependently of the choice, walks for an amount of time that is exponentially
distributed with parameter ω. Since the walk time is independent of the
chosen queue, the choice can be postponed after the walk (we informally say
that we “invert” the firing order of immediate and timed transitions). The
resulting GSPN model is shown in Fig. 9.6.
If we interpret the inversion in terms of the model, it corresponds to the
rather unrealistic situation of a multiserver random polling system where
servers leaving a queue first walk, and then decide which queue they actually
want to reach; in a system in which walk times are equal, choosing before
a walk is equivalent to choosing after a walk. In other words, if the walk
time is interpreted as a cost that the server must pay to move from the
present queue to the next one, the fact that the cost is independent of the
 
 
Search WWH ::




Custom Search