t3-2011-1gab

Prévia do material em texto

MAB-515 Avaliação e Desempenho (2011-1) 
Terceiro Teste, 2 horas , SEM CONSULTA, 100 pontos, 28/06/2011 
 
 
1ª. Questão (30 pontos) (Cadeia de Markov, CTMC, CTMD, visitas a estado) 
a) (5) Mostre como podemos calcular a taxa média de visitas a um estado qualquer numa 
CMTC. A taxa é medida em visitas/s. Assuma que as probabilidades de estado em equilíbrio 
i
 e as taxas de transição entre estados 
jiij ,
, são conhecidas. 
b) (5) Mostre como podemos calcular numa CMTD a taxa média de visitas a um estado 
qualquer. As probabilidades de estado em equilíbrio 
i
e as probabilidades de transição 
entre estados 
jipij ,,
, são conhecidas. 
c) (10) Assuma uma CMTC representando uma fila M/M/1, com taxa de chegada 

, taxa de 
serviço 

, e probabilidade de estado
,0),1(  iii 
com 
 /
. Calcule quantos 
estados em média (≠ de E0 ) são visitados entre visitas ao estado E0, em função de 

. 
d) (10) Desenhe a CMTD embutida na CMTC, quando analisamos apenas os instantes de 
transição de estado na CMTC. A CTMD embutida fará transições de estado com as mesmas 
probabilidades de transição de estado observadas na CMTC. Resolva a CMTD para as 
probabilidades de estado em equilíbrio e calcule o # médio de estados visitados nesta cadeia 
entre visitas ao estado E0. Mostre que este resultado é igual ao obtido no item anterior. 
 
Solução: 
 
a) (5) Na CMTC: 
E[# de visitas a Ei num tempo T]= 
][][ i
i
i TE
T
RE
T 

 
E[taxa de visitas a Ei]= 



ij
iji
i
i
i TERTE
T 
][][
estadodosaídadetaxaxi
 
 
b) (5) Na CMTD: 
E[# de visitas a Ei em T transições]= 
T
ME
T
i
i

][
. 
E[taxa de visitas a Ei]= 
i
iMTE
T

][
 
 
. 
c) (10) O tempo médio entre visitas ao estado E0 será dado por
][ 0RE
, tempo médio de recorrência 
do estado E0. O tempo médio gasto visitando outros estados entre visitas ao estado será dado por 
][][ 00 TERE 
= 
000
0
0
0
0 1)1(][
][




 

 TE
TE
. Como o tempo médio visitando 
um estado qualquer, diferente de E0, é dado por 
 
1
, podemos concluir que o número médio de 
estados visitados será dado por 

























1
1
1
0
0 = 





1
1
. 
 
 
d) (10) A CTMD embutida será: 
 
 
 
 
 
 
 
 
 
A solução desta cadeia será dada por: 
2
1
1
1
)1(
)1(
0,)1(
)1()1(
11
)1()1)((
1
)1(
1
0
0
0
1
0
1
0
0
0
1
0
2
123
31
2
0012
2
01
01
1
0












































i
i
i
i
i
i i

 
Para esta cadeia, o número de estados visitados entre visitas ao estado 
0E
será dado por 


 


1
1
1
1
1][
0
0ME
, igual ao obtido no item anterior, C.Q.D. 
 
2ª. Questão (20 pontos) (Classificação de Estados) 
Classifique cada estado das cadeias de Markov abaixo, se transiente, recorrente nulo ou 
recorrente não nulo. Se periódico, forneça o período. Se ergódico, indique. Justifique a 
classificação de cada estado. 
a) (10) b) (10) 
 
 
 ... 
 
 
 
 
Solução: 
 
a) (10) Pelo desenho da CM, que apresenta transições para o próprio estado, estamos tratando de 
0 1 2 
 
4 
1 
1
1
 
 3 
1
1
 
1
1
 
1
1
 


1
 


1
 


1
 
0 1 2 
1/4 1/4 
1/4 3/4 1/4 
1/2 
3/4 0 1 2 
1/4 
1/4 1 
1 
1/2 
3 
1/2 
1/4 
1/4 1/4 
CMTD irredutível e homogênea. Podemos aplicar o princípio de Foster e resolver a CM em equilíbrio 
usando  = P e 
1
0


i
i
. Fazendo isso, temos: 
3,2
...
2
3
16
424
2
3
8
424
2
3
4
424
2
3
2
444
344
34
3
4
3
1
5
0
6
645
5
4
0
5
534
4
3
0
4
423
3
2
0
3
310
2
0
2
20
1
0
1
10
0







 iii 




























 
 
E não haverá solução estacionária que satisfaça 
1
0


i
i
. Logo, os estados não podem ser 
recorrentes positivos. Como o ganho médio a cada transição é de ¼ , então a tendência é 
que a cadeia em um número muito grande de transições não mais retorne ao estado de onde 
partiu e os estados serão transientes. 
 
b) (10) Temos uma cadeia CMTD(com transição para o próprio estado), irredutível, finita e 
homogênea. Logo, os estados são recorrentes positivos. Como existe também transição para 
o próprio estado, os estados são aperiódicos, pois 
.1,0)1(00  np
 Logo são ergódicos. 
 
3ª. Questão (50 pontos) (CMTC) 
 
Um sistema tem 2 UCPs e 2 módulos de memória. Um programa para rodar necessita 
inicialmente de uma UCP e um módulo. 
Ao final de um tempo de execução exponencial com taxa 
1
 (estágio 1), o programa com 
probabilidade p finaliza, ou, com probabilidade (1-p), requer mais um módulo de memória, 
para executar por mais um tempo exponencial com taxa 
2
 (estágio 2). 
Ao final do estágio 2, o programa termina e libera a UCP e os dois módulos. Se não houver 
módulos de memória disponível, o programa fica aguardando bloqueado. Se o sistema entrar 
em deadlock, um dos programas é aleatoriamente abortado, e seu módulo transferido ao 
outro programa, para que este finalize sua execução. O programa abortado é perdido. Os 
programas chegam ao sistema segundo um processo Poisson com taxa 

. 
 
Use apenas os seguintes estados (nem todos são necessários em certo item) em sua 
resposta: 00, 01, 10, 20, 11b. 
O estado 00 indica que o sistema está ocioso. O estado 01 indica um programa rodando no 
estágio 2. O estado 10 indica um programa rodando no estágio 1. O estado 20 indica dois 
programas rodando no estágio 1. O estado 11b indica que dois programas estão rodando, 
sendo que um está bloqueado aguardando memória para rodar o estágio 2. 
a) (5) Desenhe a cadeia de Markov do sistema, quando somente um programa roda por 
vez, e não existe a possibilidade de deadlock, ou seja, haverá apenas um programa 
rodando por vez. 
b) (5) Obtenha as probabilidades de estado em equilíbrio. 
c) (5) Obtenha a vazão (programas terminados OK por segundo), no esquema sem 
deadlock. 
d) (10) Desenhe a cadeia de Markov do sistema, quando até dois programas rodando, 
mas podendo ocorrer bloqueio e deadlock. No caso de deadlock, elimine um dos 
programas aleatoriamente. Cuidado com as taxas de transição, pois elas dependem 
do número de programas rodando e das decisões dos programas em solicitar mais 
módulos ou não. Explique as transições entre estados e justifique com os eventos 
exponenciais que as acrretam. Sem justificativa a questão não receberá os pontos 
integrais. 
e) (5) Escreva as equações que permitem obter as probabilidades em equilíbrio, mas 
não resolva. 
f) (5) Supondo que as probabilidades foram obtidas, indique a vazão (programas 
terminados OK por segundo), neste caso onde deadlock pode ocorrer. 
g) (5) Num tempo longo T, quantos deadlocks em média ocorrerão? 
h) (5) Qual a probabilidade de um programa ser descartado? Pense na porcentagem do 
total de programas que entram e são descartados. 
i)(5) Qual o tempo médio gasto por um programa no sistema? Considere o universo de 
todos os programas, tanto os que forma descartado como os que terminaram OK. 
 
Solução: 
 
a) (5) 
 
 
 
 
 
 
 
 
b) (5) 
00 10 01 
 1(1-p) 
1p 
2 
1221
21
21
00
21
00
00
2
00
12
1
01012101
00
1
1010100
011000
)1()1(
1
1
1
)1(
1
)1()1(
)1(
1























pp
p
pp
p







 






 







 
 
c) (5) 
vazão = 
00012101  p
 
 
d) (10) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Explicação: 
00 – sistema ocioso 
10 – um programa rodando no estágio 1 
01 – um programa rodando no estágio 2 e usando os dois módulos de memória. Neste 
estado nenhum outro programa pode ser admitido, pois não há módulo de memória 
disponível. 
20 – dois programas rodando, ambos no estágio 1. A taxa de término é então 2
1
 e o 
programa que termina pode pedir mais um módulo ou não. Se solicitar mais um módulo, ele 
fica bloqueado, esperando a liberação do módulo pelo outro programa, e a cadeia 
transiociona para o estado (1,1b). 
11b – Neste estado, há um programa rodando no estágio 1 e outro bloqueado esperando 
módulo para rodar no estágio 2. A taxa de saída deste estágio é dada pelo término do 
estágio 1. Se o programa que terminou solicitar mais um módulo de memória, então estamos 
em deadlock e um dos programas é abortado e transicionamos para o estado 01, onde um 
programa roda no estágio 2 com os dois módulos de memória Se o programa que estava 
rodando no estágio 1 simplesmente terminar, então o programa bloqueado pode agora rodar 
com os dois módulos. Neste caso, a transição continua para o estado 01, mas indica um 
término de programa OK. 
 
 
 
 
 
00 10 01 
1p 
 1(1-p) 
2 
20 
 21p 
11B 
1p 
1(1-p) 
21(1-p) 
e) (5) 
10201
111201
20100101
10101200
1101201000
2
)1(2
2)(
1










B
B
p
p
p
 
 
f) (5) 
vazão = 
201111012101 2  ppp B 
 
g) (5) 
# de deadlocks = T
Bp 111 )1(  
 
 
h) (5) 
Probabilidade de descarte = # de deadlocks/(# términos OK + # de deadlocks) = taxa 
de deadlocks/ taxa de entrada de entrada de programas = 
)/()1( 1000111   Bp
 
 
i) (5) Usamos Little 
E[N] = E[T]/taxa de entrada de programas 
E[T] = 
)( 1000  
(
b11012010 2.2  
)