Stochastic process fundamentals - Modelling with Generalised Stochastic Petri Nets - page 269

A.3.3 Example

Consider a two-processor system comprising two CPUs with their own pri-
vate memories, and one common memory that can be accessed only by one
processor at a time.
The two CPUs share the same clock, and they execute in their private
memories for a random number of cycles before issuing a common memory
access request. Assume that this random number of cycles is geometrically
distributed, so that for a processor executing in its private memory at each
cycle the probability of a common memory access requst is p, and the average
number of cycles between two common memory access requests is (1 − p) −1 .
The common memory access duration is also assumed to be a geometrically
distributed rand om variable, so that when a common memory access is in
progress, at each cycle the probability of the common memory access ter-
mination is q, and the average duration of the common memory access is
(1 − q) −1 cycles.
To start with the simplest possible environment, assume that only one pro-
cessor is operational. In this case the system can only be in one of two

states:
1. the processor is executing in its private memory;

2. the processor is accessing the common memory.
The system behaviour can thus be modeled with a two-state discrete-time
process. The assumptions introduced on the system workload are such that
no memory is present in the system, so that the behaviour is Markovian.
We can thus describe the system operations with a 2-state DTMC with
transition probability matrix

" #

1 − p

p

P =

1 − q q

Alternatively, the 2-state DTMC can be characterized with the graph shown
in Fig. A.3. This graph conveys the same information as the transition prob-
ability matrix. Indeed, each of the two representations can be derived from
the other. The graphical representation is often called the state (transition)
diagram of the DTMC.
This 2-state DTMC is obviously irreducible and aperiodic, provided that p
and q are larger than zero. Hence, under the same assumption the model
is ergodic, so that the steady-state distribution can be found by solving the
system of linear equations,

(1 − p) η 1 + q η 2 η 1 =

= p η 1 + (1 − q) η 2 η 2

1 = η 1 + η 2