Tip:
Highlight text to annotate it
X
Teoria de Filas - Filas com Prioridades
Avaliação e Desempenho - UFRJ
Paulo e seu filho compartilhavam uma mesma rede em sua casa
Porém Paulo, utilizava seu computador para reuniões via skype e seu filho para baixar vídeos através do BitTorrent
Paulo, então, teve uma ideia!!!
Decidiu dar prioridade aos seus dados, porém seu filho começou a reclamar que o download de seus vídeos estava muito lento!!!
Paulo, como estudou AD na faculdade e é muito curioso, resolveu aplicar seus conhecimentos para analisar o problema
Primeiro, Paulo analisou o processo de chegadas no sistema
Para facilitar os cálculos, definiu que o processo de chegada de dados era Poisson
Sendo lambdav as chegadas de voz e lambdab as chegadas de BitTorrent
O tempo médio de serviço do roteador, por conveniência, foi adotado como exponencial
Sendo, 1/Uv para voz e 1/Ub para BitTorrent
A disciplina de atendimento do problema é FCFS, ou seja, o primeiro pacote a chegar é o primeiro a ser servido
Porém no caso do Paulo, os pacotes de voz tem prioridade sobre os pacotes de BitTorrent, sendo atendidos primeiro
Esta prioridade é não preemptiva
Que significa, que caso o pacote de voz chegue ao sistema
E encontre um pacote de BitTorrent sendo servido
Não interromperá o serviço do mesmo
Agora Paulo se faz a seguinte pergunta:
Como calcular os tempos médios de atraso dos pacotes de voz e de BitTorrent?
Bom, primeiro Paulo decide calcular o tempo médio em fila para os pacotes de voz
O tempo total em fila será dado pela vida residual dos pacotes em serviço
Podendo tanto ser um pacote de voz quanto um pacote de BitTorrent
Mais o tempo de espera correspondente aos pacotes na fila de voz que estão a sua frente
Simplificando a equação e fazendo algumas substituições
Podemos encontrar a condição de estabilidade
Ou seja, o requisito necessário para que a fila não cresça indefinidamente.
Se Paulo quisesse saber o tempo médio total no sistema de um pacote de voz
Teria que somar o tempo médio em fila calculado anteriormente com o tempo médio de serviço para voz.
Porém o filho de Paulo ainda não está satisfeito
Pois quer saber o tempo médio de atraso sofrido por seus vídeos baixados pelo BitTorrent!
A pedido de seu filho, Paulo agora irá calcular o tempo médio de atraso para BitTorrent
Porém, nesta situação
Além da vida residual de um pacote que esteja em serviço
Tanto de BitTorrent como de voz voz
Temos o agravante de que os pacotes de BitTorrent
Além de esperarem pelos pacotes que encontram-se a sua frente na sua fila
Tem de esperar todos os pacotes de voz que porventura chegarem ao sistema, enquanto estiver em espera
Serem servidos
Ou seja, como podemos visualizar
Chegadas de pacotes de voz podem ocorrer enquanto o pacote de BitTorrent aguarda em sua fila
E o mesmo tem de esperar todos os pacotes de voz serem atendidos
Para aí então entrar em serviço
Relembrando que caso o pacote de voz chegue enquanto o pacote de BitTorrent estiver sendo servido
Este não terá seu serviço interrompido
Para simplificar, inicialmente vamos considerar o caso em que, por sorte
Nenhum pacote de voz chega ao sistema enquanto o pacote de BitTorrent aguarda em fila
Neste caso, o tempo médio de espera em fila do pacote de Bit Torrent
Será a soma da vida residual do pacote que encontra-se em serviço
Quando o pacote de BitTorrent chega ao sistema
Com o tempo de espera correspondente aos pacotes que encontram-se em fila
Tanto de voz quanto de BitTorrent, quando o pacote de BitTorrent chega ao sistema
Porém, pacotes de voz podem chegar enquanto o pacote de BitTorrent estiver esperando em fila
Sendo o tempo de espera extra, decorrente das chegadas de pacotes de voz, representado em azul escuro na figura
O atendimento do pacote de BitTorrent só ocorrerá quando o sistema estiver disponível novamente
Sendo que isso só ira acontecer quando não houver mais nenhum pacote de voz no sistema
Ou seja, o pacote de BitTorrent continuará em espera enquanto o sistema estiver ocupado com pelo menos um pacote de voz.
Por este motivo a soma dos retângulos amarelo, azul claro e azul escuro é chamado de....
PERÍODO OCUPADO
Finalmente, o valor do tempo médio em fila para BitTorrent
Será obtido pela soma feita anteriormente, porém, normalizada pela divisão de 1-rho_v
Para levar em conta a extensão caracterizada pelo retângulo azul escuro
Semelhante a forma mostrada anteriormente
Simplificando a equação e fazendo algumas substituições
Podemos encontrar a condição de estabilidade
Se Paulo quisesse saber o tempo médio total no sistema de um pacote de BitTorrent
Teria que somar o tempo médio em fila calculado anteriormente ao tempo de serviço para BitTorrent
Bom, após realizar todos os cálculos
Paulo concluiu que realmente o download de vídeos realizados por seu filho estava sofrendo um grande atraso
Porém, como quem paga as contas na casa é ele, decidiu deixar tudo como está
Os conceitos aprendidos com nosso exemplo também podem ser utilizados em diversos casos reais
Como fila de banco, trânsito, etc
Existem também diversas variações deste problema
Como a disciplina de atendimento LCFS, onde o último a chegar é o primeiro a ser servido
Ou casos com preempção, onde o serviço é interrompido para o atendimento de uma classe mais prioritária
Ou através de uma chegada caso seja LCFS
Bom, esperam que tenham gostado e até a próxima!!!