t3-2011-2gab

Prévia do material em texto

MAB-515 Avaliação e Desempenho (2011-2) 
Terceiro Teste , 2 horas , SEM CONSULTA, 75 pontos, 24/11/2011 
Prof. Paulo Aguiar -GABARITO 
 
1ª Questão: (30 pontos) (CMTC, CMTD) 
Queremos construir uma CMTD que acompanhe a evolução do estado de uma CMTC 
correspondente a uma fila M/M/2, com taxa de chegada 

e taxa de serviço 

. 
a) (5) Construa a matriz de probabilidades de transição de um passo P 
 ijp
 para 
a CMTD. Observe que, neste caso, o tempo gasto num estado é irrelevante e 
somente estamos interessados nas transições. Desenhe a CMTD correspondente. 
O estado é o número total de pessoas na fila. 
b) (5) Calcule 
0
, para a CMTD, em função de 
 2/
. Monte o sistema de 
equações e resolva para as probabilidades de estado em equilíbrio, indicando 
passo a passo o uso das equações do sistema. Se resolver sem indicar o que está 
sendo feito a cada passo perde pontos. Resposta apenas com 

. 
c) (5) Estando inicialmente no estado E0, quantas transições em média têm que 
ocorrer para retornarmos novamente a E0? 
d) (5) Desenhe agora a CMTC correspondente à fila M/M/2. Monte o sistema de 
equações e resolva para as probabilidades de estado em equilíbrio, indicando 
passo a passo o uso das equações do sistema. Se resolver sem indicar o que está 
sendo feito a cada passo perde pontos. 
e) (5) Usando agora a CMTC, calcule o tempo entre retornos ao estado 
0E
. 
f) (5) Calcule o número médio de chegadas entre visitas ao estado
0E
 e a partir 
deste valor calcule o número médio de transições de estado necessárias para, 
saindo de 
0E
, retornar novamente a 
0E
, como já feito no item c usando a CMTD. 
Você tem que usar apenas a CMTC e mostrar a igualdade dos dois resultados. 
 
Solução: 
a) A CTMC para a M/M/2 é 
 
 
 
 
 
 
A CMTD correspondente é: 
 
 
 
O 1 2 3 

  
… 
O 1 2 3 





… 


2
2




2
2








2

 
Em função de temos: 
 
 
 
 
 
b) (5) Para solução da CMTD, usamos as equações 
1
0
 

i
ieP 
. 
.
)1(2
1
12,)1(2
)1(2
121
2
)1(2
1
)21(
21
0
0
0
1
0
2
3
31
2
02
2
01
01
1
0



































i
i
i
i ei

 
 
c) (5)


 


1
)1(21
][
0
0ME
 
 
d) (5) 
 
 
 
 
 
Para a solução da CMTC, usamos as equações de equilíbrio de fluxo. Para simplificar, 
usaremos equações parciais de equilíbrio. 
.
1
1
11,2
22
22
2
0
0
0
0
3
2332
0
2
1221
0110














i
i
i
i ei
 
 
e) (5) Considerando um ciclo como o tempo entre retornos ao estado 
0E
, podemos 
desenhar a figura abaixo: 
 
 
 
 
 
O 1 2 3 

… 


21
2




1

21
1


1
1

1
1

O 1 2 3 

  
… 
E0 Ei≠E
0 
Ei≠E
0 
 E0 Ei≠E
0 
][ 0ME
 
][][ 00 TEME 
 
 
)1(
1][
][
0
0
0 

 


TE
RE
. 
f)(5) O número médio de chegadas entre visitas ao estado 
0E
 é dado por 
][ 0RE
. Mas 
para que retornemos ao estado
0E
haverá a necessidade de termos um número de 
partidas igual ao número de chegadas, e portanto o número médio de transições será 
de
)1(
)1(2
][2 0 



RE
 , que é igual ao obtido anteriormente no item c usando a 
CMTD. 
 
OBS. Outro raciocínio para este item seria pensando em taxa de transição: 
Taxa média de transições = 
10210 2)2()2()(   . 
# médio de transições entre retornos a E0 = taxa média de transições x E[R0]= 
  








1
)1(2
2)2(
)1(
1
10
, que é o resultado procurado e igual ao 
obtido anteriormente. 
 
 
2ª Questão (25 pontos): (CMTC) 
 
Suponha que N (valor fixo) pessoas estão em terminais de acesso a um processador 
central. Essas pessoas, após um tempo de reflexão que é exponencial com taxa 

, geram 
tarefas ao processador. As tarefas são processadas, uma por vez, com atendimento FCFS 
e tempo de execução exponencial com taxa 

. 
Após a execução, o resultado da tarefa retorna a quem gerou e esta pessoa passa por um 
novo momento de reflexão, também exponencial com taxa 

, antes de enviar uma nova 
tarefa. Enquanto uma tarefa está sendo processada, a pessoa que a gerou fica ociosa. 
 
Este é um modelo de sistema de time-sharing. Este comportamento se repete 
indefinidamente. 
 
Queremos obter o tempo de resposta médio do sistema 
][TE
, medido do instante em 
que uma tarefa é enviada até instante do retorno do resultado de sua execução (coincide 
com o final de execução do processador). 
 
a) (5) Modele a execução das tarefas como uma cadeia de Markov, onde o estado 
kE
representa 
k
tarefas em processamento (inclui as tarefas em espera e aquela sendo 
eventualmente servida) e monte o sistema de equações que permita obter 
k
. NÃO 
RESOLVA O SISTEMA. ASSUMA QUE VOCÊ RESOLVEI E OBTEVE 
Nkk 0,
. 
 
b) (5) Calcule a taxa de tarefas processadas executadas pelo processador central (em 
tarefas/segundo), em função de 
0
. 
 
c) (5) Calcule 
][ME
, o número médio de usuários pensando, isto é, aqueles que 
receberam a resposta da tarefa e estão decidindo que nova tarefa enviar, em função de 

, 

 e 
0
, apenas. 
 
d) (5) Calcule 
][TE
, o tempo médio de resposta definido no enunciado, em função de 
][ME
 e de parâmetros dados (

, 

, 
N
). 
 
e) (5) Qual a probabilidade de se encontrar uma determinada pessoa ociosa? 
 
Solução: 
 
a) (5) 
 
 
 
 
 
 
 
Usando equações parciais de equilíbrio temos: 


 
N
i
iNNNN
0
12110 1,,...,)1(, 
 
com solução 

















N
oi
i
i
i
iN
NiN
N





)!(
!
1
,
)!(
!
00
 
 
b) (5) A taxa de tarefas executadas = 
)1( 0
1
 

N
i
i
. Esta taxa é também igual à 
taxa média de chegada de tarefas à fila do processador que é igual a 
)1(
)1(
...)1(
0
1
110
110



























N
i
i
N
N
NN
NN 
 
c)(5) M = Número de pessoas pensando. Como cada pessoa pensando gera tarefas a 
uma taxa 

, então a taxa média de tarefas enviadas ao processador é 
][ME
 e deve 
ser igual à taxa de tarefas executadas, calculadas acima. 
Portanto
)1(][ 0 ME
e 
 /)1(][ 0ME
. 
 
Outra forma de se obter a resposta é observar que 








)1(
)2()1(
)2()1(
.0)2()1(][
0
3211210
1210
1210











NN
N
NN
NNN
NNN
NNNME



 
 
0 
2 
  
1 N-2 N 
  
N-1 
    
d) (5) Para encontrar o tempo médio de resposta do processamento, podemos 
calcular o número médio de tarefas em processamento 



N
i
i MENi
1
][
 e usar 
Little: 
][
][
)1(
][
][
]
][
0
1
ME
MENMEN
taxaE
i
TE
N
i
i







 . 
 
e) (5) Usando a teoria da renovação, e sabendo que o usuário passa por ciclos 
ociosos (média 
][TE
) e pensando (média 
/1
, a fração do tempo que uma pessoa 
fica ociosa é 
][/1
][
TE
TE

=.(N-E[M])/N=E[pessoas ociosas]/N 
 
 
3ª Questão: (20 pontos) (classificação de estados) 
 
Considere a cadeia de Markov abaixo, onde p+q=1. 
 
 
 
a) (5) Para quais valores de q os estados desta cadeia são recorrentes positivos? 
Justifique. 
b) (5) ) Para quais valores de q os estados desta cadeia são recorrentes nulos? 
Justifique. 
c) (5) ) Para quais valores de q os estados desta cadeia são transientes? Justifique. 
d) (5) O que é o critério de Foster? Explique. 
 
 
Solução: 
 
Para q=0 a cadeia é redutível com o conjunto fechado formado pelos estados 0 e 1; 
para q=1, todos os estados são transientes e a cadeia passa a ser formada por duas 
cadeias triviais, já que p=0. Iremos assumir 0<q<1 para avaliar apenas a situacão 
da cadeia irredutível. 
 
Sendo a cadeia é homogênea e irredutíve,l todos os estados terão a mesma 
classificação. O tipo de estado será função do valor do ganho médio dos estados à 
direita E[GD] e do ganho médio dos estados à esquerda E[GE]. 
E[GD]=q-p e E[GE]=(p-q/2-q)=(2-5q)/2. 
 
a) (5) Para que os estados sejam recorrentes positivos é necessário que a cadeia 
tenda a retornar ao estado 0 quando passar pelos estados à direita, isto é, E[GD]<0, 
e quando passar pelos estados à esquerda, E[GE]>0. 
E[GD] <0  q<p  q<0,5. 
E[GE]>0 2>5q q<0,4. 
Portanto, q<0,4, que é mais restritivo, garante que todos os estados sejam 
recorrentes positivos. 
b) (5) Para que os estados sejam recorrentes nulos é suficiente que o ganho médio 
seja 0 para um dos dois lados do estado 0. Para os estados à esquerda, q=0,4 garante 
ganho nulo para estes estados e ao mesmo tempo implica em ganho negativo para os 
estados à direita, garantindo que eles não serão transientes, pois a tendência será de 
retornar ao estado 0 com ganho negativo. O fato de termos um número de estados 
infinito à direita com ganho negativo não importa. O comportamento da cadeia não é 
determinado por estes estados à direita, mas pelos estados à esquerda. Caso não 
houvesse estados à direita e simplesmente retornássemos do estado 0 para o estado -1 
com probabilidade 1, a condição dos estados serem recorrentes nulos continuaria a 
mesma, ou seja, , q=0,4 . 
c) (5) Quando q>0,4, E[GE]<0, implicando que a cadeia tenderia na média a ir 
sempre para a esquerda após visitar estados à esquerda, e haverá uma probabilidade 
positiva de não mais retornar ao estado 0, o que força todos os estados a serem 
transientes. 
Quando 0,4< q<0,5, E[GE]<0 e E[GD]<0 e, embora os estados à direita tenham 
ganho médio negativo, a cadeia ao ir para a esquerda do estado 0 dali não mais 
retorna com probabilidade positiva, fazendo com que todos os estados sejam 
transientes. 
Para q=0,5, E[GE]<0 e E[GD]=0, onde não haveria uma tendência quando a cadeia 
estivesse do lado direito, ao retornar ao estado 0 e ir para a esquerda, a 
probabilidade de não mais retornar será positiva e portanto os estados continuam a 
ser transientes. 
Para q>0,5, E[GE}<0 e E[GD]>0, o que reforça a tendência da cadeia não mais 
retornar ao estado 0 tanto se for a direita como a esquerda, o que torna os estados 
transientes. 
 
d) (5) ) O critério de Foster afirma que, para uma cadeia irredutível e homegênea, se 
acharmos a solução de 
,1,
2
 

i
iP 
que não seja a solução trivial com todas as 
probabilidades nulas, então a solução representa as probabilidades em equilíbrio 
para a cadeia de Markov e os estados serão recorrentes positivos. Se forem 
aperiódicos, eles serão ergódicos. 
Na cadeia dada, para q<0,4, teremos estados recorrentes positivos, como explicado. 
O critério de Foster poderia ser aplicado para comprovar isso. Todavia, para 
cadeias com transições entre estados não adjacentes, nem sempre apenas ter as 
equações em equilíbrio pode não ser suficiente para resolver completamente para as 
probabilidades de estado em equilíbrio e outras propriedades como a analiticidade 
de transformadas têm que ser usadas para eliminar indeterminações como visto em 
exemplo da lista. Portanto, tentar resolver esta cadeia dada aplicando Foster não 
será tão simples. Para uma CMTC, basta analisar a CMTD correspondente, pois 
ambas terão estados com a mesma classificação. Se for obtida uma solução trivial 
nula, então os estados ou serão todos transientes ou recorrentes nulos.