Graphics Programs Reference
In-Depth Information
The system behaviour can thus be modeled with a five-state discrete-time
process. Again, 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 5-state DTMC with
transition probability matrix
2
4
(1
−
p
A
) (1
−
p
B
)
p
A
(1
−
p
B
)
(1
−
p
A
) p
B
p
A
p
B
q
A
(1
−
p
B
)
(1
−
q
A
) (1
−
p
B
)
(1
−
q
A
) p
B
q
A
p
B
(1
−
p
A
) q
B
(1
−
p
A
) (1
−
q
B
)
P =
p
A
q
B
0
p
A
(1
−
q
B
)
(1
−
q
A
)
0
0
q
A
0
q
B
0
0
(1
−
q
B
)
Note that in the case of two simultaneous common memory access requests,
priority is given to processor A.
The chain is irreducible and aperiodic, hence ergodic, under the condition
that p
A
, p
B
, q
A
, and q
B
are all greater than zero.
A.4
Continuous-Time Markov Chains
By specializing the Markov property to the continuous-time, discrete-space
case we obtain the definition of a CTMC
DEFINITION
The stochastic process
{
X(t),t
≥
0
}
is a CTMC provided that
P
{
X(t
n+1
) = x
n+1
|
X(t
n
) = x
n
, X(t
n−1
) = x
n−1
,
···
, X(t
0
) = x
0
}
= P
{
X(t
n+1
) = x
n+1
|
X(t
n
) = x
n
}
t
n+1
> t
n
>
···
> t
0
(A.26)
∀
n
∈
IN ,
∀
x
k
∈
S, and all sequences
{
t
0
,t
1
,
···
,t
n+1
}
such that t
0
< t
1
<
···
< t
n+1
.
This definition is the continuous-time version of (
A.8)
, and also in this case
the right-hand side of the equation is the transition probability of the chain.
We use the notation
p
ij
(t,θ) = P
{
X(θ) = j
|
X(t) = i
}
(A.27)
to identify the probability that the process be in state j at time θ, given that
it is in state i at time t, assuming θ > t. When θ = t we define
(
1,
i = j
p
ij
(t,t) =
(A.28)
0,
otherwise
Search WWH ::
Custom Search