Redes elétricas como sistema de filas. rede de filas. Fator de utilização de QS

4 - Fundamentos da teoria das filas.

Definição 1. Seja algum sistema físicoS, que muda seu estado ao longo do tempo (transições de um estado para outro), além disso, de forma previamente desconhecida e aleatória. Então diremos que no sistemaSocorre um processo aleatório.

Qualquer coisa pode ser entendida como um “sistema físico”: um dispositivo técnico, uma empresa, um organismo vivo, etc.

Exemplo. S – um dispositivo técnico que consiste em vários nós que falham de tempos em tempos, são substituídos ou restaurados. O processo no sistema é aleatório. Em geral, se você pensar bem, é mais difícil dar um exemplo de um processo "não aleatório" do que um aleatório. Até mesmo o processo do relógio - um exemplo clássico de trabalho preciso e estritamente ajustado ("funcionar como um relógio") está sujeito a mudanças aleatórias (avançar, ficar para trás, parar).

Definição 2. Um processo aleatório em um sistema é chamado de processo de Markov se para qualquer momento de tempot 0 as características probabilísticas do processo no futuro dependem apenas de seu estado no momentot 0 e não dependem de quando e como o sistema chegou a esse estado.

Deixe no momentot 0 o sistema está em um determinado estadoS 0 . Observamos o processo de lado e no momentot 0 conhecer o estado do sistemaS 0 e toda a história do processo, tudo o que aconteceu durantet< t 0 . Nós, naturalmente. Interessados ​​no futuro:t> t 0 . Podemos prever isso? Exatamente - não. Nosso processo é aleatório, portanto imprevisível. Mas podemos encontrar algumas características probabilísticas do processo no futuro. Por exemplo, a probabilidade de que depois de algum tempot sistema Sserá capazS 1 ou salve o estadoS 0 etc.

Se o processo for Markov, é possível prever apenas levando em consideração o estado atual do sistemaS 0 e esquecendo de sua "pré-história" (comportamento do sistema quandot< t 0 ). O próprio estadoS 0 , é claro, depende do passado, mas uma vez alcançado, o passado pode ser esquecido. Aqueles. no processo de Markov "o futuro depende do passado apenas através do presente".

Exemplo. Sistema S– Contador Geiger, que é atingido por partículas cósmicas de tempos em tempos; o estado do sistema em um ponto no tempotcaracterizado pelas leituras do contador - o número de partículas que chegaram até este ponto. Deixe no momentot 0 contador mostraS 0 . A probabilidade de que no momentot> t 0 o contador mostrará este ou aquele número de partículasS 1 (ou menos S 1 ) depende de S 0 , mas não depende dos momentos exatos em que as partículas chegaram antes do momentot 0 .

Na prática, muitas vezes existem processos que, se não exatamente markovianos, podem ser considerados markovianos em alguma aproximação. Por exemplo,S ­ - um grupo de aeronaves envolvidas em combate aéreo. O estado do sistema é caracterizado pelo número de aeronaves "vermelhas" -x e "azul" y, preservado (não abatido) até certo ponto. No momentot 0 sabemos o número de partidosx 0 e y 0 . Estamos interessados ​​na probabilidade de que em algum momentot 0 + ta superioridade numérica estará do lado dos “vermelhos”. De que depende essa probabilidade? Primeiro de tudo, em que estado o sistema está em um determinado momentot 0 , e não em quando e em que sequência aqueles abatidos morreram até o momentot 0 aeronave.

Em essência, qualquer processo pode ser considerado como Markov, se todos os parâmetros do "passado", dos quais o "futuro" depende, forem transferidos para o "presente". Por exemplo, seja sobre o funcionamento de algum dispositivo técnico; em algum momentot 0 ainda é útil, e estamos interessados ​​na probabilidade de que funcione por mais algum tempot. Se por enquanto considerarmos simplesmente “o sistema está funcionando”, então o processo certamente não é Markov, porque a probabilidade de não falhar a tempot, depende, no caso geral, de quanto tempo já funcionou e quando foi o último reparo. Se ambos os parâmetros (tempo de atividade total e tempo desde o reparo) estiverem incluídos no estado atual do sistema. Esse processo pode ser considerado Markov.

Definição 3. Um processo é chamado de estado discreto se seus estados possíveisS 1 , S 2 ,... pode ser enumerado (renumerado) antecipadamente, e a transição do sistema de estado para estado ocorre em um “salto”, quase instantaneamente.

Definição 4. Um processo é chamado de processo com tempo contínuo se os momentos das possíveis transições de estado para estado não são fixados antecipadamente, mas são incertos, aleatórios, se a transição pode ocorrer, em princípio, a qualquer momento.

Consideraremos apenas processos com estados discretos.

Exemplo. Dispositivo técnicoSconsiste em dois nós. Cada um dos quais em um momento aleatório de tempo pode falhar (fail), após o qual o reparo do nó começa imediatamente, continuando também por um tempo aleatório desconhecido.

Fig.4.1

Possíveis estados do sistema:

S 0 - ambos os nós estão funcionando;

S 1 - o primeiro nó está sendo reparado, o segundo está em manutenção;

S 2 - o segundo nó está sendo reparado, o primeiro pode ser reparado;

S 3 Ambas as unidades estão em reparo.

Seta apontando para foraS 0 dentro S 1 significa o momento de falha do primeiro nó, etc. Não há seta na figura do estadoS 0 em um estado S 3 , pois a probabilidade de dois dispositivos falharem ao mesmo tempo tende a zero.

Definição 5. Um fluxo de eventos é uma sequência de eventos homogêneos que se seguem um após o outro em algum momento aleatório (por exemplo, um fluxo de falhas em um computador, um fluxo de chamadas em uma central telefônica).

A característica mais importante do fluxo de eventos é sua intensidade.eué o número médio de eventos por unidade de tempo. a vazão pode ser constante (eu= const), bem como uma variável dependente do tempo. Por exemplo, o fluxo de carros que circulam pela rua é mais intenso durante o dia do que à noite, e o fluxo de carros das 14h às 15h pode ser considerado constante.

Definição 6. Um fluxo de eventos é chamado de regular se os eventos seguem um após o outro em intervalos regulares de tempo iguais.

Definição 7. Um fluxo de eventos é chamado de estacionário se suas características probabilísticas não dependem do tempo. Em particular, a intensidadeeufluxo estacionário deve ser constante. Isso não significa que o número real de eventos que aparecem por unidade de tempo seja constante - não, o fluxo inevitavelmente (a menos que seja regular) tem algumas concentrações e rarefações aleatórias. É importante que, para um fluxo estacionário, essas concentrações e rarefações não sejam de natureza regular: um segmento de comprimento 1 pode ter mais eventos e o outro pode ter menos eventos, mas o número médio de eventos por unidade de tempo é constante e não depende do tempo.

Por exemplo, o fluxo de chamadas que chegam ao PBX entre 13:00 e 14:00. É praticamente estacionário, mas o mesmo fluxo durante o dia não é mais estacionário.

Definição 8. Um fluxo de eventos é chamado de fluxo sem efeito posterior se para quaisquer dois intervalos de tempo não sobrepostost 1 e t 2 o número de eventos que atingem um deles não depende de quantos eventos atingem o outro. Em essência, isso significa que os eventos que formam o fluxo aparecem em determinados momentos independentemente uns dos outros, cada um causado por suas próprias causas.

Por exemplo, o fluxo de passageiros que entra no metrô quase não tem efeito colateral. Mas o fluxo de clientes que saem do balcão com mercadorias compradas já tem um efeito colateral (até porque o intervalo de tempo entre clientes individuais não pode ser menor que o tempo mínimo de atendimento para cada um deles).

Definição 9. Um fluxo de eventos é chamado de ordinário se os eventos nele aparecem um por um, e não em grupos de uma só vez.

Por exemplo, o fluxo de clientes ao dentista costuma ser normal. O fluxo de trens que se aproximam da estação é comum, e o fluxo de vagões é extraordinário.

Definição 10. Um fluxo de eventos é chamado de Poisson mais simples (ou estacionário) se tiver três propriedades ao mesmo tempo: é estacionário, comum e não tem efeito posterior, e o fluxo de entrada em si é distribuído de acordo com a lei de Poisson ( ).

Para descrever um processo aleatório ocorrendo em um sistema com estados discretosS 1 , S 2 , ..., S ngeralmente usam probabilidades de estadop 1 ( t),..., p n( t) , Onde pk( t) é a probabilidade de que no momentoto sistema está em um estadoSk. Probabilidades pk( t) satisfaz a condição: .

Se o processo que ocorre em um sistema com estados discretos e tempo contínuo é Markoviano, então para as probabilidades de estadop 1 ( t), ..., p n( t) pode-se compor um sistema de equações diferenciais lineares. Ao compilar essas equações, é conveniente usar o gráfico de estados do sistema, no qual, contra cada seta que leva de estado a estado, é afixada a intensidade do fluxo de eventos, transferindo o sistema ao longo da seta (Fig. 4.2) :

Fig.4.2 eueu jé a intensidade do fluxo de eventos que transfere o sistema do estadoSi em um estado S j. Regra de criação sistemas de equações diferenciais lineares para encontrar as probabilidades de estados. Cada estado tem sua própria equação. No lado esquerdo de cada equação há uma derivada, e no lado direito há tantos termos quantos as setas estão diretamente relacionadas ao estado dado; se a seta leva a um determinado estado, então o termo tem um sinal “+”, caso contrário, tem um sinal “–”. Cada termo é igual à intensidade do fluxo de eventos que leva o sistema ao longo da seta dada, multiplicada pela probabilidade do estado do qual a seta sai. Este. o sistema de equações diferenciais lineares no nosso caso tem a forma:

As condições iniciais para integrar tal sistema refletem o estado do sistema no momento inicial. Se, por exemplo, o sistemat=0 foi capazSk, então . Essas equações podem ser resolvidas analiticamente, mas isso é conveniente apenas quando o número de equações não excede dois (às vezes três). No caso de existirem mais equações, são utilizados métodos numéricos.

O que acontecerá com as probabilidades dos estados em ? Vaip 1 ( t), ..., p n( t) lutar por alguns limites? Se esses limites existem e não dependem do estado inicial do sistema, eles são chamados de probabilidades do estado final: . pié o tempo médio de residência relativa do sistema emeu-º estado.

Como encontrar as probabilidades finais? Já que tudopi= const, então as derivadas do lado esquerdo de cada equação são iguais a zero. Este. obtivemos um sistema de equações algébricas lineares. Como nenhuma equação neste sistema tem um termo livre, o sistema é degenerado (ou seja, todas as variáveis ​​serão expressas por meio de um). Para evitar isso, é necessário usar a condição de normalização (), enquanto qualquer equação pode ser descartada.

Classificação de sistemas de filas

De acordo com o número de dispositivos de serviço, os QS são divididos em canal único e multicanal. O QS multicanal consiste em vários dispositivos e cada um deles pode atender a uma solicitação.

Também os QS são subdivididos em sistemas sem espera e com espera. Primeiro, a solicitação sai da fila se, no momento em que chegar, não houver pelo menos um canal capaz de iniciar imediatamente o atendimento a essa solicitação. Estes últimos, por sua vez, são divididos em sistemas sem restrições e com restrições quanto ao comprimento da fila.

QS também são divididos em sistemas com e sem prioridades. Por sua vez, os sistemas com prioridade são divididos em QS com e sem interrupção.

QS de canal único com fila ilimitada

Fig.4.3

Vamos encontrar as probabilidadespk:

Para o estado S 0 : , por isso ;

Para o estado S 1 n: , substituímos o valor obtido porp 1 : . Da mesma maneira, .

Probabilidade p 0 encontramos a partir da condição de normalização:

, é uma progressão geométricar<1 converge. - a probabilidade de não haver aplicações.

é a probabilidade de que o dispositivo esteja ocupado atendendo a solicitação.r= eu/ mé uma medida do carregamento de um QS de canal único.

No momento atual, o sistema pode ter 0, 1, 2, ...,k, ... aplicações com probabilidadesp 0 , p 1 p 2 , ... Expectativa matemática do número de aplicações:

dado que , Nós temos:

O comprimento médio da fila é igual à diferença entre o número médio de aplicativos no sistema e o número médio de aplicativos em serviço: .

Pequenas fórmulas

Fig.4.4

A primeira fórmula de Little permite determinar o tempo de resposta do QS (o tempo que o aplicativo permanece no sistema).

Deixar X( t) é o número de solicitações recebidas pelo QS até o momentot, S( t) – aqueles que deixaram o CMO antes t . Ambas as funções são aleatórias e aumentam em um no momento da chegada e saída dos clientes. Em seguida, o número de aplicativos no sistema por veztpode ser definido como: . Considere um período de tempo muito longoT e calcule o número médio de solicitações no sistema:

.

A integral é igual à área da figura escalonada delimitada pelas funçõesX( t) e S( t) , essa soma consiste em retângulos cuja largura é igual a um, e o comprimento é o tempo de permanênciaeu-th aplicação no sistema. O valor se aplica a todos os pedidos recebidos pelo sistema durante o períodoT. Multiplique o lado direito e divida poreu: . Teu- o número médio de pedidos recebidos durante o períodoT. Dividindo a soma de todos os temposeusobre o número médio de aplicações, obtemos o tempo médio de permanência da aplicação no sistema: .

Da mesma forma, você pode obter o tempo médio que o aplicativo permanece na fila: .

QS multicanal com fila ilimitada

Fig.4.5

Vamos encontrar as probabilidadespk:

Para o estado S 0 : ;

Para estados S 1 – S n: ;

Por S n +1 : ; ...

Por Sn+s-1: ;

Por Sn+s: .

Desde o primeiro n +1 equações obtemos:

Da última equação expressamos: e substituir na penúltima: , . Então .

Continuando a analogia: .

Agora vamos encontrar p 0 , substituindo as expressões resultantes na condição de normalização (): . Daqui .

Indicadores de desempenho de QS

– Probabilidade de perda de sinistro em QS. Especialmente muitas vezes é usado no estudo de questões militares. Por exemplo, ao avaliar a eficácia da defesa aérea de um objeto, caracteriza a probabilidade de romper alvos aéreos até o objeto. Aplicado a um QS com perdas, é igual à probabilidade de que todos os requisitos estejam ocupados com a manutençãondispositivos de sistema. Na maioria das vezes, essa probabilidade ép n ou pabrir.

– A probabilidade de que os requisitos no sistema estejam ocupadosk dispositivos, é igual a pk.

– Número médio de dispositivos ocupados: caracteriza o grau de carregamento do sistema de serviço.

– Número médio de dispositivos livres de serviço: .

– Fator de tempo de inatividade do instrumento: .

– Taxa de ocupação dos equipamentos: .

– Comprimento médio da fila: , pké a probabilidade de o sistema terk requisitos.

– Número médio de pedidos no setor de serviços: .

– A probabilidade de que o número de solicitações na fila aguardando o início do serviço seja maior que um determinado númerom: . Este indicador é especialmente útil ao avaliar a possibilidade de colocação de requisitos com tempo de espera limitado.

Além dos critérios listados, ao avaliar a eficácia do QS, os indicadores de custo podem ser usados:

qcerca de– o custo de manutenção de cada requisito no sistema;

qoh– o custo das perdas associadas a solicitações ociosas na fila por unidade de tempo;

qno– perdas associadas à saída do sistema de aplicação;

q- o custo de operação de cada dispositivo por unidade de tempo;

qetc- o custo do tempo de inatividade por unidade de tempokº dispositivo do sistema.

Ao escolher os parâmetros ótimos do QS de acordo com os indicadores econômicos, podemos usar a função do custo das perdas no sistema (para QS com expectativa):T- intervalo de tempo.

Para QS com falhas: .

Para misto: .

Critério de eficiência econômica do QS: , Com- o efeito econômico obtido pela manutenção de cada aplicação.

QS tipo fechado

Exemplo. C1, C2, C3 - máquinas; NC - armazenamento central; B - manipulador. O carrinho de transporte (manipulador) transporta a peça usada da máquina para a loja e a coloca lá, pega uma peça nova (em branco), transporta-a para a máquina e a coloca na posição de trabalho para fixação. Durante todo o período necessário para descarregar e carregar, a máquina fica ociosa. TempoThtroca da peça de trabalho e há tempo de serviço.

A intensidade de manutenção das máquinas é definida como , - o tempo médio de manutenção da máquina, que é calculado como , Onden- o número de aplicações. A intensidade da máquina preenchendo uma solicitação de serviço é definida como (onde é o tempo médio de processamento da peça pela máquina).

O sistema de máquina-ferramenta com manipulador single-grip é um sistema de espera com organização interna FIFO : cada aplicação da máquina para manutenção é satisfeita, caso o manipulador esteja ocupado, a aplicação é enfileirada e a máquina espera que o manipulador fique livre. Este processo é markoviano, ou seja. emissão aleatória de uma solicitação de serviço em um determinado momentot 0 não depende de aplicações anteriores, ou seja, do curso do processo no período anterior. A duração da execução do aplicativo pode ser diferente e é uma variável aleatória que não depende do número de aplicativos enviados. Todo o processo não depende do que aconteceu antes de um ponto no tempot 0 .

Em um sistema de máquina-ferramenta, o número de solicitações de serviço pode ser 0, 1, 2, ...m, Onde mé o número total de máquinas. Então os seguintes estados são possíveis:

S 0 - todas as máquinas estão funcionando, o manipulador está de pé.

S 1 - todas as máquinas, exceto uma, estão funcionando, o manipulador atende a máquina da qual foi recebido o pedido de troca de peças.

S 2 - trabalhar m-2 máquina, uma máquina está trocando a peça de trabalho, a outra está esperando.

S 3 - trabalhar m-2 máquina, uma máquina é operada por manipulador, duas máquinas estão esperando na fila.

S m- todas as máquinas estão paradas, uma é atendida por um manipulador, as demais aguardam a execução da ordem.

Fig.4.6.

Probabilidade de Transição de EstadoSkde um dos estados possíveisS 1 , S 2 , ... S mdepende da chegada aleatória de solicitações de serviço e é calculado como:

p 0 é a probabilidade de que todas as máquinas estejam funcionando.

O manipulador opera sob estados do sistema deS 1 antes da S m­ . Então a probabilidade de seu carregamento é igual a: .

O número de máquinas na fila está relacionado aos estadosS 2 , – S m, enquanto uma máquina é atendida, e ( k -1) - esperando. Então, o número médio de máquinas na fila: .

Relação de tempo de inatividade de máquina única (devido à espera pela manutenção de várias máquinas): .

Uso médio por máquina:

Aplicação do método de Monte Carlo para resolução de problemas,

relacionado com a teoria das filas

Para descrever o fluxo de eventos homogêneos, basta conhecer a lei da distribuição dos momentos de tempo t 1 , t 2 , ..., kkk, ... para os quais os eventos são recebidos.

Para conveniência de outras considerações, é aconselhável a partir dos valorest 1 , t 2 , ..., mudar para variáveis ​​aleatóriasz 1 , z 2 , ..., zm, ... , de modo a:

variáveis ​​aleatóriaszksão os intervalos de tempo entre momentos sucessivoskkk.

Conjunto de variáveis ​​aleatóriaszeué considerado dado se a função de distribuição conjunta for definida: . Normalmente, apenas variáveis ​​aleatórias contínuas são consideradaszk, então a função de densidade correspondente é frequentemente usadaf( z 1 , z 2 ,..., z k) .

Normalmente, a teoria QS considera fluxos de eventos homogêneos sem efeito posterior, para os quais variáveis ​​aleatóriaszkindependente. É por isso . Funçõesfi( z eu) no eu>1 são funções condicionais da densidade, desde que no momento inicial do intervalozk ( eu>1) pedido foi recebido. Em contrapartida, a funçãof 1 ( z 1 ) é uma função densidade incondicional, pois não são feitas suposições sobre o aparecimento ou não aparecimento da reclamação no momento inicial.

Os chamados fluxos estacionários são amplamente utilizados, para os quais seu regime probabilístico não muda no tempo (ou seja, a probabilidade de ocorrênciakpedidos por um período de tempo (t 0 , t 0 + t) não depende t 0 , mas depende apenas det e k). Para fluxos estacionários sem efeito posterior, as relações ocorrem:

onde eu é a densidade do fluxo estacionário.

Um pedido inserido no sistema só pode ocupar linhas livres. Várias suposições podem ser feitas em relação à ordem em que as linhas são ocupadas:

a) as linhas são engatadas na ordem de seus números. Uma linha com um número mais alto não pode estar envolvida na manutenção de um aplicativo se houver uma linha livre com um número mais baixo;

b) as linhas são ocupadas alternadamente. A linha liberada entra na fila e não inicia o serviço de aplicativos até que todas as linhas liberadas anteriormente sejam usadas;

c) as linhas são ocupadas em ordem aleatória de acordo com as probabilidades dadas. Se no momento do recebimento do próximo pedido houvernSt.linhas livres, então no caso mais simples a probabilidade de ocupar uma determinada linha pode ser igual a . Em casos mais complexos, as probabilidadessão considerados dependentes do número de linhas, dos momentos de sua liberação e de outros parâmetros.

Suposições semelhantes podem ser feitas em relação à ordem de aceitação das solicitações de atendimento no caso de se formar uma fila de solicitações no sistema:

a) As inscrições são aceitas por ordem de chegada. A linha desocupada passa a atender a solicitação que foi inserida anteriormente no sistema por outra;

b) os pedidos de atendimento são aceitos de acordo com o tempo mínimo para recebimento da recusa. A linha desocupada passa a atender o pedido, que pode ser indeferido no menor tempo possível;

c) os pedidos de atendimento são aceitos por ordem aleatória de acordo com as probabilidades dadas. Se no momento da liberação da linha houvermpedidos na fila, então, no caso mais simples, a probabilidade de escolher algum pedido específico para atendimento pode ser igual aq=1/ m. Em casos mais complexos, as probabilidadesq 1 , q 2 ,..., qmsão considerados dependentes do tempo de permanência do pedido no sistema, do tempo restante até o recebimento da recusa e de outros parâmetros.

· Para resolver vários problemas aplicados, é necessário levar em consideração um fator tão importante quanto a confiabilidade dos elementos do sistema de serviço. Vamos supor que, do ponto de vista da confiabilidade, cada linha em um determinado momento pode estar funcionando ou com defeito. A confiabilidade da linha é determinada pela probabilidade de operação sem falhasR= R( t) , dado em função do tempo. Também assumiremos que uma linha que falhou devido à confiabilidade incompleta pode ser colocada em operação (reparada), o que requer tempotp. O valor que tpvamos considerar uma variável aleatória com uma dada lei de distribuição.

Várias suposições podem ser feitas em relação ao destino do pedido, durante o serviço em que a linha falha, várias suposições podem ser feitas: o pedido é recusado; o aplicativo permanece no sistema (com um tempo total gasto no sistema não superior atn) como requerente de serviço fora de turno; o aplicativo entra na fila e é atendido em uma base geral, etc.

A essência do método de teste estatístico aplicado a problemas de filas é a seguinte. São construídos algoritmos, com os quais é possível desenvolver realizações aleatórias de determinados fluxos de eventos homogêneos, bem como "simular" os processos de funcionamento de sistemas de serviços. Esses algoritmos são usados ​​para reproduzir repetidamente implementações de um processo de serviço aleatório sob condições fixas do problema. As informações resultantes sobre os estados do processo são submetidas a processamento estatístico para fins de avaliação, que são indicadores da qualidade do serviço.

O método de testes estatísticos permite investigar de forma mais completa, em comparação com fórmulas assintóticas, a dependência da qualidade de serviço das características do fluxo de solicitações e dos parâmetros do sistema de atendimento.

Isto é conseguido devido a duas circunstâncias. Primeiro, ao resolver problemas na teoria das filas pelo método de testes estatísticos, informações mais extensas sobre o processo podem ser usadas do que normalmente é possível fazer usando métodos analíticos.

Por outro lado, os valores dos indicadores de qualidade de serviço obtidos a partir de fórmulas assintóticas, a rigor, referem-se a pontos temporais suficientemente distantes do início do processo. Na verdade, para os momentos próximos ao início do processo, quando o modo estacionário ainda não foi definido, os valores dos indicadores de qualidade de serviço no caso geral diferem significativamente dos valores assintóticos. O método de testes estatísticos permite estudar os modos transitórios com suficiente detalhe.

Para muitos problemas aplicados, as suposições sob as quais as fórmulas analíticas são válidas acabam sendo muito restritivas. Ao resolver problemas pelo método de testes estatísticos, algumas suposições podem ser significativamente enfraquecidas.

Em primeiro lugar, isso se aplica ao serviço multifásico (ou seja, são considerados sistemas de serviço, consistindo em várias unidades operando sequencialmente, no caso geral, heterogêneas).

Outra generalização importante do problema é a suposição sobre a natureza do fluxo de solicitações que chegam para atendimento. É permitido considerar fluxos de eventos homogêneos com uma lei de distribuição praticamente arbitrária. A última circunstância é significativa pelas duas razões seguintes. Primeiro, os fluxos reais de aplicações em alguns casos diferem marcadamente dos mais simples. Para esclarecer a segunda razão, vamos supor que o fluxo inicial de solicitações seja aproximado com bastante precisão pelo fluxo mais simples. Ao mesmo tempo, o fluxo de pedidos atendidos na primeira fase não será, a rigor, o mais simples. Como o fluxo que é a saída para a primeira fase será o fluxo de entrada para o agregado atendendo as solicitações na segunda fase, novamente chegamos ao problema de atender fluxos que não são os mais simples.

· A estrutura da modelagem do algoritmo

processo de serviço de aplicativo

Considere um QS monofásico comnlinhas para as quais os pedidos são recebidos em horários aleatórioseu. Se no momento do recebimento do pedido houver linhas livres (seu númeronSt.), o aplicativo ocupa um deles por um tempotp. Caso contrário, o aplicativo fica no sistema até o momentot nesperando para ser atendido. Em t t tempo de espera, algumas linhas podem ficar livres (seu númerom), e neste caso será possível atender o pedido. Se até o momentot nnenhuma das linhas é liberada (m=0 ), o pedido é rejeitado.

Assumiremos que, devido à confiabilidade insuficientemente alta do sistema, as linhas que atendem ao aplicativo podem falhar, o aplicativo é recusado e a linha pode ser reparada mesmo após um período de tempo. t pem colocar em operação.

Para estudar a qualidade das solicitações de serviço, é fornecidoN * modelagem múltipla do processo de funcionamento do sistema no intervalo (0, T) . No processo de modelagem, o número de implementações examinadas será denotado porN.

Algoritmo:

1. O momento é determinadoeurecebimento da próxima aplicação no sistema.

2. Se eu< T, em seguida, vá para a etapa 3, caso contrário, vá para a etapa 11.

3. Verificando a capacidade de atender a solicitação recebida: senSt.>0 , então vá para a etapa 4, caso contrário vá para a etapa 12. (O valor da hora de chegada da solicitaçãoeu comparado com tosvpara todas as linhas, ou seja, aparecem linhas livres.)

4.Se nSt.>1 , em seguida, vá para a etapa 5, caso contrário, vá para a etapa 6.

5. O número da linha livre é selecionado de acordo com regras especiais.

6. A linha selecionada é atribuída.

7. Verifique: há interrupção do serviço por falta de confiabilidade? Se sim, vá para a etapa 8, caso contrário, vá para a etapa 10.

8. Tempotremreparação de uma linha quebradatremtem uma certa lei de distribuição).

9. Nabrir= Nabrir+1 . Vá para a etapa 1.

10. Determinação do horário de picotha linha que é designada para atender a solicitação (alguma variável aleatória com uma certa lei de distribuição) e o tempo de liberação da linha:tosv= eu+ th. Transição para a próxima aplicação (passo 1).

11. Verifique: seN< N * , então N= N+1 e vá para a etapa 1, caso contrário - processando os resultados do experimento e o final.

12. Determinar:

Um tempo t npermanência do aplicativo no sistema;

B) o número de canais livresm durante t n.

13. Se m>0 , em seguida, vá para a etapa 14, caso contrário, vá para a etapa 9.

14. Se m>1 , em seguida, vá para a etapa 15, caso contrário, vá para a etapa 6.

15. Uma determinada linha é selecionada de acordo com as regras aceitas e vá para a etapa 6.

AULA 2 (4 horas). SIMULAÇÃO DE VS COM BASE EM SISTEMAS E REDES DE FILA.

2.1 Definição de sistemas e redes de filas.

Um sistema de filas (QS) é um objeto no qual uma sequência de operações é executada. O sistema pode realizar um número finito de operações de vários tipos. O elemento do sistema no qual as operações ocorrem é chamado de dispositivo de serviço. A essência física e algorítmica das operações é ignorada.

As operações são realizadas em dispositivos mediante solicitação. As aplicações podem ser externas (incluídas no sistema pelo lado de fora) e internas (surgidas no final da operação). Filas de aplicativos podem aparecer no QS. Uma fila é uma coleção de aplicativos esperando para serem atendidos no momento em que o servidor está ocupado.

De acordo com o número de dispositivos de serviço, os QS são divididos em monocanal e multicanal (Fig. 2.1.).

DIV_ADBLOCK33">

A rede de filas é especificada pelo seguinte conjunto de parâmetros:

Parâmetros de origem da solicitação;

Uma estrutura que determina a configuração dos links e as probabilidades de transferência de aplicativos entre os nós da rede;

Parâmetros de nós de rede (sistemas de enfileiramento): disciplina de serviço, o número de dispositivos de serviço idênticos (canais) em cada nó, a distribuição da duração das solicitações de serviço em cada nó de rede.

O funcionamento da rede de filas é determinado por uma combinação de características nodais e de rede. As características nodais avaliam o funcionamento de cada QS e incluem as características do fluxo de aplicações que entram no nó e todo o conjunto de características inerentes ao QS. O desempenho da rede avalia o desempenho da rede como um todo e inclui:

Carga - o número de tempo médio de aplicativos atendidos pela rede e, ao mesmo tempo, o número médio de canais ocupados pelo serviço;

O número de aplicativos esperando para serem atendidos na rede;

O número de aplicativos na rede (no estado de espera e serviço);

Tempo total de espera de uma aplicação na rede;

O tempo total gasto pelo aplicativo na rede.

Definição de redes estocásticas

As redes de filas são muitas vezes complementadas com nós especiais com elementos de aleatoriedade, que ampliam as possibilidades de reproduzir várias formas de organizar o funcionamento da aeronave. Por exemplo, os modelos de rede incluem nós de memória que simulam a operação de dispositivos de armazenamento. A manutenção de um aplicativo recebido na entrada de um nó de memória é reduzida à alocação da capacidade de memória solicitada. Caso não haja área do tamanho necessário na memória, a entidade é colocada em uma fila e aguarda a liberação da memória fornecida às entidades previamente recebidas. As capacidades da rede podem ser expandidas introduzindo nós que controlam as rotas das aplicações: enviando uma aplicação simultaneamente por várias rotas; sincronizar o movimento dos aplicativos; alterando os atributos do aplicativo. As redes de filas com esses nós adicionais são chamadas de redes estocásticas.

As redes estocásticas reproduzem os processos de atendimento multiestágio, quando a solicitação é atendida por acesso sequencial a recursos, inclusive múltiplos. A vantagem de uma rede é sua semelhança estrutural com um sistema real. A composição dos nós e a configuração das conexões entre eles corresponde à composição dos dispositivos e à ordem de sua interação em um sistema real. Devido a isto, o processo de construção de modelos de rede é bastante simplificado e assegurada a adequação do funcionamento das redes e dos sistemas que modelam.

Para descrever a aeronave, são utilizadas redes estocásticas abertas e fechadas. Em uma rede aberta (aberta), a intensidade do fluxo de entrada de solicitações https://pandia.ru/text/78/299/images/image004_1.gif" width="614" height="134 src=">. gif" largura="16 "altura="19 src=">

Uma variação de uma rede aberta é uma cadeia serial de QS de canal único ou multicanal. Tal sistema, no qual as aplicações são atendidas sequencialmente por vários QS, é chamado de sistema multifásico.

Em uma rede fechada, a intensidade de recebimento de solicitações depende do estado da rede: a próxima solicitação entra na rede somente após a conclusão do serviço completo de uma das solicitações anteriores. Portanto, em uma rede fechada, o número de requisições é constante e igual ao número que pode ser atendido simultaneamente pela rede. Neste caso, podemos falar de uma fonte fictícia DIV_ADBLOCK34">

Se houver um QS com duas ou mais saídas em uma rede estocástica, ou seja, tal QS, após o atendimento ao qual o fluxo de solicitações se ramifica, então as regras para ramificação do fluxo são definidas. Nesse caso, geralmente são indicadas as probabilidades de transferência do aplicativo por um caminho ou outro.

Vamos considerar vários tipos privados de modelos de rede usados ​​para reproduzir vários aspectos do funcionamento do CS.

2.2. Redes de filas determinísticas.

Consideremos um sistema caracterizado pela presença de canais de acesso direto à memória do lado de drives de fita (NML) e drives de disco (NMD), bem como dos terminais do objeto de controle. O esquema do sistema é mostrado na fig. 2.3.(a)..gif" width="19" height="17 src=">, para canais, para cada um dos NMD e NML. Os sistemas operacionais multiprograma modernos suportam o processamento simultâneo de tarefas dividindo os recursos do sistema entre eles. atinge o máximo de tarefas de aplicação de sobreposição dos usuários ao alternar o processamento no processador central e periféricos.

Para o sistema multiprograma em consideração, construímos um modelo de interação entre o sistema e os programas aplicativos ao realizar tarefas. O sistema é modelado por uma rede de nós de serviço, cada um dos quais corresponde a uma determinada função dos recursos do sistema. O processo de resolução do problema pode ser representado pela rota de sua passagem pelos diversos nós da rede. Se todas as tarefas de uma mistura de multiprogramas forem as mesmas e não interagirem umas com as outras, as mesmas rotas correspondem a esses processos. A estrutura do roteiro do programa aplicativo é determinada pela composição das operações realizadas e dos recursos utilizados nesta.

Na fig. A Figura 2.3(b) mostra o fluxo do processo, visto do ponto de vista do programador do problema. As operações do programa aplicativo são organizadas na ordem de execução e incluem: 1 – operação do programa aplicativo (conta 1); 2 – impressão de dados; 3 – intercâmbio com NMD; 4 - trabalho do programa aplicativo (conta 2); 5 - emissão de informações para o objeto de controle. Os comandos macro da solicitação de impressão, troca com o NMD e o objeto de controle são interpretados pelos programas de controle do SO e iniciam a operação dos canais correspondentes. Essas operações são numeradas com os seguintes números: 6 - execução do programa de gerenciamento de impressão; 7 - implantação do programa de gestão do NMD; 8 - ações de controle no terminal do objeto. Da fig. 2.3.(b) verifica-se que a execução das operações do programa aplicativo e do SO alterna e os pedidos de serviços de diversos tipos são colocados na fila do processador.

https://pandia.ru/text/78/299/images/image009_1.gif" width="13" height="15 src=">.gif" width="12" height="15 src="> - NMD..gif" width="15" height="19 src=">, que não possui fila, pois o número de terminais é igual ao número de processos no sistema. O conjunto de nós e filas está conectado por arcos, cada um dos quais indica os possíveis caminhos de movimento dos processos Um processo pode ocupar um recurso de nó ou ser enfileirado nele..gif" width="15" height="19 src=">.gif" width="13 " height="19 src=">, que é a origem das solicitações. No arco conectando os nós e https://pandia.ru/text/78/299/images/image017_0.gif" width="40" height ="19 src=">, que indica a formação do valor inicial da operação-atributo, que se torna 1..gif" width="13" height="15 src=">.gif" width="41" altura="19 src=">. Essa entrada indica o caminho adicional do processo após a operação 1 e o novo valor de seu atributo de operação..gif" width="13" height="19 src=">..gif" width="13" height=" 15 src =">.gif" width="12" height="13 src=">.gif" width="13" height="15 src=">, 6.gif" width="13" height=" 15 src=">, 7.gif" width="13" height="15 src=">.gif" width="15" height="19 src=">.gif" width="13" height=" 13 src =">.gif" largura="57" height="27 src=">.gif" height="17 src=">º nó.

2.3. Redes de filas estocásticas

Tais modelos incluem redes com filas, nós nos quais contêm elementos de aleatoriedade. Em sua forma natural, tais redes surgem se apenas parte da rota do processo for predeterminada, ou seja, quando elementos de aleatoriedade estiverem presentes nos algoritmos de controle ou processamento, ou quando for dada a probabilidade de falha de algum recurso do sistema, a probabilidade de um determinado estado do objeto de controle ou sistema de controle que determina a ordem na qual o recurso é usado. A parte gráfica do modelo é construída da mesma forma que para o caso determinístico. Adicionalmente, são indicados os vetores de tempos de atendimento, tipos de dispositivos de atendimento, bem como a matriz que descreve as probabilidades de transições internodais do processo.

O modelo de rede com elementos de aleatoriedade é mostrado na fig. 2.4. O modelo do processador é representado pela entrada de dados" href="/text/category/vvod_dannih/" rel="bookmark"> nó de entrada/saída de dados com NMD são descritos em dois estágios sucessivos: abordagem da cabeça do drive e recuperação de informações são representados por os nós https://pandia.ru /text/78/299/images/image011_0.gif" width="12" height="15 src="> e trocar pelo canal node.gif" width="15" height="19 src=">.gif " width="15" height="17 src=">.gif" width="15 height=17 src=" height="17">.gif" width="19 " height="17 src=">. gif" width="21" height="24 src="> processo criado..gif" width="19" height="17 src=">. Se durante a execução do programa (operação 1) ocorrer uma solicitação ao banco de dados, o processo prosseguirá para a operação 2 (transição 1https://pandia.ru/text/78/299/images/image007_1.gif" width=" 19" height=" 17 src="> pode ser direcionado para uma das mídias de armazenamento..gif" width="13" height="19 src=">,.gif" width="15" height="19 src =">.gif" width="13" height="19 src=">), receberá o serviço de posicionar as cabeças de leitura-gravação no cilindro e setor necessários..gif" width="13" height= "15 src="> garante os dados de criação passados ​​para o programa do canal..gif" width="19" height="17 src=">, onde recebe o serviço necessário para sair da interrupção do programa do canal e agendar um retorno ao the problem program..gif" width=" 20" height="15 src=">1) Assim, o ciclo de execução das operações do sistema para organizar a troca de dados entre a memória principal e o disco está concluído.

https://pandia.ru/text/78/299/images/image027_0.gif" width="15" height="17 src=">.gif" width="20" height="15 src=">. gif" width="13" height="15 src=">.gif" width="20" height="15 src=">.gif" width="20" height="2 src=">Considere redes com recursos ativos (nós), cuja complexidade de execução da aplicação é caracterizada pelo tempo vir, onde r = 1, R é o tipo de aplicação e sua cadeia. após o serviço, a rede é chamada de aberta (aberta) em relação à cadeia r. Uma rede que não possui fontes externas é chamada de fechada. Em redes mistas, existem cadeias de aplicativos abertas e fechadas.

Dependendo da área de aplicação, as redes com vários tipos de declarações são chamadas de multi-cadeia ou multi-produto. Nos circuitos fechados, é atribuído um nó, possivelmente até fictício, que é tomado como início e fim da rota. Alguns dos nós podem ser repetidos várias vezes na cadeia de rotas. O número αir, que caracteriza o número de visitas ao nó i de requisições da rota r, é chamado de coeficiente de visita (transferência).

A taxa de atendimento no modo de atendimento estacionário pode ser determinada a partir da relação:

αir = λir / λ0r, (2.1)

onde λ0r é a intensidade do fluxo de r-reivindicações do nó inicial da cadeia de rotas de reivindicações.

λir - a intensidade do fluxo de solicitações para o nó i.

Para um circuito aberto, o valor λ0r é dado. Para um circuito fechado, o valor λ0r é determinado por um conjunto de parâmetros da rede e caracteriza seu desempenho (capacidade).

Em uma rede estocástica, o movimento de r-reivindicações é descrito por uma matriz de rotas de probabilidades de transição Pr = | pijr |, onde pijr é a probabilidade de que o r-cliente, após ser atendido no nó i, vá para o nó j.

No modo de serviço estacionário, para cada um dos nós, é registrada a seguinte condição de equilíbrio de fluxo:

λir = ∑λjir (2.2)

Aqui https://pandia.ru/text/78/299/images/image035_0.gif" width="308" height="138 src=">.gif" width="25" height="2 src="> λir = ∑pjir λjr, eu=0,N. (2.4)

Como o fluxo de uma fonte externa λ0r e a matriz de roteamento Pr são dados para um circuito aberto, então λir e αir podem ser encontrados nas equações (2.1) e (2.4).

Para um circuito fechado, a equação de equilíbrio de fluxo (2.4) é representada como um sistema homogêneo com um conjunto infinito de soluções. Portanto, para calcular processos em circuitos fechados, os valores λir são tomados como dados iniciais. Como o cliente visita o nó inicial da rota uma vez em um ciclo completo, o coeficiente de visita ao nó zero é igual a um. Considerando que λ0r=1 e substituindo λir = αir λ0r (de (2.1)) nas partes esquerda e direita do sistema de equações (2.4), obtemos equações para calcular os coeficientes de visita a um circuito fechado:

https://pandia.ru/text/78/299/images/image039_0.gif" width="132" height="49 src="> eu=0,N, ou seja, temos um sistema de equações semelhante a (2.4) para calcular αir,

https://pandia.ru/text/78/299/images/image041_0.gif" width="90" height="45 src="> eu=0,N.

Para a especificação (descrição) da rota do processo no modelo de rede, é necessário especificar o vetor de coeficiente de visita ou a matriz de probabilidade de transição. Se a rota da solicitação for determinística, ela é imediatamente descrita por coeficientes de visita, pois é determinado o número de visitas a cada um dos nós. A rota estocástica é representada pela matriz P.

Rede multiclasse

https://pandia.ru/text/78/299/images/image042_0.gif" width="29" height="26 src="> |. Elementos DIV_ADBLOCK37">

O estado da requisição dentro de cada cadeia é caracterizado por um par (i, q), que permite usar a ajuda para refletir as trajetórias complexas do movimento das requisições e construir modelos de sistemas reais mais confiáveis ​​que os de classe única.

Denote a intensidade do fluxo de requisições na classe s do sistema i de outros sistemas da rede por λis. As equações de equilíbrio de fluxo para o modo estacionário da rede têm a forma:

https://pandia.ru/text/78/299/images/image044_0.gif" width="144" height="49 src="> (2.6)

Métodos eficientes para calcular redes que implementam as seguintes disciplinas de serviço em nós foram desenvolvidos:

Atendimento por ordem de chegada (FiFo);

divisão de tempo (PS), que assume que se houver n requisições em um nó, então cada uma delas será apresentada com um quantum de serviço de comprimento 1/n por unidade de tempo;

· interrupção por prioridades absolutas com pós-atendimento na ordem inversa (P);

atendimento sem espera (D)

Os três primeiros métodos representam nós de serviço de espera (nós de primeiro tipo). Os nós do segundo tipo representam recursos individuais atribuídos a um processo.

Vamos introduzir a notação:

niq - número médio de aplicações da classe q no nó i;

ni = ∑q niq é o número médio de sinistros no nó i;

Kr = ∑i ni - o número médio de aplicações na cadeia r;

K = ∑r Kr é o número de requisições na rede.

Gif" width="14" height="2 src=">.gif" width="14" height="2 src=">.gif" width="14" height="2 src=">O estado da rede é vetor descrito n = (n1 ,n2 ,…,ni,…,nN), onde ni é o estado do nó eu.

Gif" largura="14" altura="2 src=">.gif" largura="10" altura="2 src=">.gif" largura="19" altura="26 src="> ,…, SN) = (P1(S1), P2(S2),…, Decomposição" href="/text/category/dekompozitciya/" rel="bookmark">decomposição (estruturação). A base dos algoritmos clássicos para calcular G(K) é a operação de convolução de vários vetores, que podem ser representados como expressões recursivas de acordo com o esquema multidimensional de Horner.

Ao calcular redes fechadas, os procedimentos recorrentes também são usados ​​em características como o comprimento médio da fila, o tempo médio de espera. Essa abordagem é chamada de método de análise de médias (MAS). Os algoritmos de convolução interpretam mal o significado significativo (aplicado). O MAC é baseado em interpretações claras e significativas e é projetado para resolver problemas numéricos que surgem em algoritmos de convolução.

redes abertas. Vamos apresentar um software matemático para cálculo de redes exponenciais homogêneas com diversos fluxos de requisições. Os modelos matemáticos da classe nomeada são descritos pelos seguintes dados iniciais:

· intensidade de fontes externas de fluxos de Poisson – λ0r;

· intensidade de trabalho exponencialmente distribuída no i-ésimo nó – vi = 1/μ, onde μ é a intensidade de serviço;

taxas de visita em eu–e nós - αir.

Está provado que nestas condições a rede é matematicamente decomposta em um conjunto de nós desconectados.

As características da rede são calculadas da seguinte forma. Carregando o nó i do fluxo de solicitações do tipo r:

https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src=">= λi/µi, vi = 1/µi, https://pandia.ru/text/78/299/images/image052.gif" width="20 height=26 src=" height="26"> =https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src="> vi/(1- https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src=">).

Usando a fórmula de Little (ni = λiVi), encontramos o número de requisições de cada tipo no nó i:

nir = λir Vir = https://pandia.ru/text/78/299/images/image055.gif" width="67" height="39 src=">.

redes fechadas. Algoritmo para calcular a rede através das probabilidades de estados.

Para redes fechadas de Markov, as probabilidades de estado são determinadas a partir de soluções representáveis ​​na forma de um produto (2.7). Se a rede consiste em nós FiFo, então as probabilidades de estado são:

P(n1 n2…nN) =1/G(K) * Π https://pandia.ru/text/78/299/images/image052.gif" width="20" height="26 src=">= λi/μi - carregamento do i-ésimo sistema, igual à razão entre a vazão e a vazão de serviço no i-ésimo sistema: m =1,K1; n = 1,K2; i = 1,N.Vi2(K1,K2) = vi2. (2.13)

As dependências acima estão corretas se o tempo de serviço nos nós FIFO não depender do circuito, ou seja, vi1 = vi2. Nos nós PS, pode ser diferente. Se necessário, através de G, você pode encontrar as probabilidades de estados e outras características.

A principal desvantagem do algoritmo é a grande faixa do valor G, que leva a erros de overflow, underflow e arredondamento.

Método de análise de médias (MAS)

O MAC pode ser facilmente obtido a partir do algoritmo de convolução e das fórmulas de Little (ni = λiVi) para os nós da cadeia e da rede. Assim, no caso de uma rede de circuito único com K1 = K, da expressão (2.13) temos:

Vi(K) = vi. (2.14)

tpreb. serviço esperar vi

Com base na fórmula de Little para a cadeia e dado que o tempo do ciclo completo da aplicação na rede,

C(K) = ∑i αiVi(K), (2.15)

Nós temos:

λ0(K) = K/C, (2.16)

e da fórmula de Little para o nó encontramos:

ni(K) = αiλ0(K)Vi(K). (2.17)

Observe que ni(0) =0. Cálculos recursivos de acordo com as fórmulas (2.13) - (2.16) fornecem imediatamente as características desejadas dos processos e nós da rede. A carga é encontrada a partir da razão:

https://pandia.ru/text/78/299/images/image067.gif" width="88" height="39 src="> (2.15)

Considere um caso mais geral de serviço em nós. Introduzimos o valor bi(j), que caracteriza a capacidade do nó i quando nele há j clientes. Para servidores de canal único com taxa de serviço constante, bi(j) =1. Para nós D bi(j) =j. Para nós onde a taxa de serviço depende da carga, temos 0< bi(j)<∞. Обычно bi(j) - монотонная неубывающая функция j, т. е.

bi(j) > bi(j-1) e bi(j+1) - bi(j) ≤ bi(j) - bi(j-1).

Por exemplo, se houver um servidor de dois canais no nó, então bi(1) =1, bi(j) =2 para todo j ≥2.

A capacidade do nó (capacidade de carga) é determinada pela razão:

bi(j) = μi(j)/μi(1), (2.19)

onde μi(j) é a intensidade de serviço no nó i, se houver j solicitações, e μi(1) - se houver uma solicitação.

Se a taxa de serviço no nó depende da carga, conforme descrito pela fórmula (2.19), então o tempo de residência pode ser calculado pela fórmula:

Vi(K) = vi, (2.20)

onde bm é a capacidade máxima de carga do nó i, bm≤K.

https://pandia.ru/text/78/299/images/image069.gif" width="614" height="87 src=">

https://pandia.ru/text/78/299/images/image071.gif" width="26" height="62 src="> Vir(K) = vir,

1 - para nós FIFO-, PS-;

0 - para nós D.

3. λ0r(K) = Kr/ ∑i αar esquerda">

Arroz. 2.5. A ordem de ignorar os nós ao calcular uma rede de cadeia dupla com uma população de K = (2,2). ↓ - direção do movimento da linha de frente.

O gráfico mostrado na figura não é um diagrama de estados da rede, mas um diagrama dos possíveis volumes de requisições na rede, contendo um número de vértices incomparavelmente menor que o diagrama de estados. O número de vértices em um grafo não depende do número de nós na rede.

A complexidade computacional dos algoritmos de convolução, MAC e equilíbrio local é da mesma ordem. No entanto, dependendo das características dos dados iniciais, um ou outro dos algoritmos pode dar menos erros, o que não pode ser evitado devido à natureza recorrente do cálculo. Em essência, vários esquemas de processos computacionais são implementados aqui, mas é difícil preferir qualquer um por razões de estabilidade numérica. Em pesquisas e cálculos de engenharia, algoritmos MAC significativamente claros são preferíveis. Para o controle numérico dos resultados, podem ser usados ​​cálculos simultâneos usando vários algoritmos diferentes.

Aplicação de vários métodos matemáticos à formalização. Ênfase em um sistema complexo - imprevisível. Operadora incerteza é o homem.

Um exemplo típico de problemas estocásticos (aleatórios, probabilísticos) são os modelos de sistemas de filas.

SMOs são onipresentes. São redes telefônicas, postos de gasolina, serviços ao consumidor, bilheterias, eventos comerciais, etc.

Da posição de modelagem do processo de enfileiramento, surgem as situações em que se formam filas de requisições (requisitos) para atendimento, conforme segue. Tendo entrado no sistema de atendimento, o requisito se junta à fila de outros requisitos (recebidos anteriormente). O canal de serviço seleciona um requisito entre os que estão na fila para começar a atendê-lo. Após a conclusão do procedimento de atendimento da próxima solicitação, o canal de atendimento passa a atender a próxima solicitação, caso haja alguma no bloco de espera. O ciclo de funcionamento de um QS deste tipo é repetido muitas vezes durante todo o período de funcionamento do sistema de serviço. Supõe-se que a transição do sistema para atender o próximo requisito após a conclusão do atendimento ao requisito anterior ocorra instantaneamente, em momentos aleatórios.

Exemplos de SMOs são:

postos de manutenção de automóveis;

postos de reparação automóvel;

firmas de auditoria, etc.

O fundador da teoria das filas, em particular, a teoria das filas, é o famoso cientista dinamarquês A.K. Erlang (1878-1929), que estudou os processos de atendimento em centrais telefônicas.

Os sistemas nos quais os processos de serviço ocorrem são chamados de sistemas de filas (QS).

Para descrever um sistema de filas, você deve especificar:

- fluxo de entrada de aplicações;

- disciplina de serviço;

- tempo de serviço

- o número de canais de atendimento.

fluxo de entrada requisitos (aplicativos) é descrito pela identificação tanto probabilística lei de distribuição momentos de recebimento de requisitos no sistema, e número de requisitos em cada entrada.

Quando perguntado disciplinas de serviço(DO) é necessário descrever as regras para enfileirar os requisitos e atendê-los no sistema. O comprimento da fila pode ser limitado e ilimitado. No caso de restrições no comprimento da fila, o pedido recebido na entrada do QS é recusado. Os DOs mais usados ​​são definidos pelas seguintes regras:

primeiro a chegar, primeiro a ser servido;

veio por último - servido primeiro; (caixa para bolas de tênis, empilhar na técnica)

seleção aleatória de aplicativos;

selecção das candidaturas por critério de prioridade.

Tempo de serviço aplicações em QS é uma variável aleatória. A lei de distribuição mais comum é a lei exponencial.  - velocidade de serviço. =número de solicitações/unidades de serviço. Tempo.

Canais de atendimento, podem ser colocados em paralelo ou em série. Com um arranjo sequencial de canais, cada aplicativo é atendido em todos os canais sequencialmente. Com um arranjo paralelo de canais, o atendimento é realizado em todos os canais simultaneamente à medida que ficam livres.

A estrutura generalizada do QS é mostrada na fig.

Sujeito teoria das filasé estabelecer a relação entre os fatores que determinam a funcionalidade do QS e a eficácia do seu funcionamento.

Problemas de projeto QS.

As tarefas de determinar as características da estrutura QS incluem o problema de escolher o número de canais de atendimento (elementos básicos (F eu)), o problema de determinar o método de conexão de canais (um conjunto de elementos de conexão (Hj)), bem como o problema de determinar a taxa de transferência dos canais.

1). Seleção de estrutura. Se os canais operam em paralelo, então o problema de escolher Str se reduz a determinar o número de canais na parte de serviço com base na condição para garantir a operacionalidade do QS. (A menos que a fila esteja crescendo infinitamente).

Observe que ao determinar o número de canais do sistema, no caso de seu arranjo paralelo, é necessário observar condição de saúde do sistema. Indicar:  - o número médio de solicitações recebidas por unidade de tempo, ou seja, intensidade do fluxo de entrada;  - o número médio de pedidos atendidos por unidade de tempo, ou seja, intensidade de serviço; S - número de canais de atendimento. Então a condição para a operacionalidade do QS será escrita

ou
. O cumprimento desta condição permite calcular o limite inferior do número de canais.

Se
, o sistema não pode lidar com a fila. A fila cresce indefinidamente.

2). É necessário determinar o critério para a eficácia do funcionamento QS, tendo em conta o custo das perdas de tempo tanto por parte das aplicações como por parte da parte de serviço.

Os três grupos principais de indicadores a seguir são considerados indicadores da eficácia do funcionamento do QS:

1. Indicadores da eficácia do uso de QS.

A taxa de transferência absoluta do QS é o número médio de aplicativos que o QS pode atender por unidade de tempo.

A taxa de transferência relativa do QS é a razão entre o número médio de aplicativos atendidos pelo QS por unidade de tempo e o número médio de solicitações recebidas durante esse período.

A duração média do período de emprego do SMO.

A taxa de utilização do QS é o compartilhamento médio de tempo durante o qual o QS está ocupado atendendo aplicativos.

2. Indicadores da qualidade das aplicações de serviço.

Tempo médio de espera para um aplicativo na fila.

Tempo médio de residência de um pedido na OCM.

Probabilidade da solicitação ser negada sem esperar.

A probabilidade de que uma solicitação recebida seja imediatamente aceita para serviço.

A lei da distribuição do tempo de espera para um aplicativo na fila.

A lei de distribuição do tempo gasto por um aplicativo no QS.

O número médio de aplicativos na fila.

O número médio de solicitações na OCM.

3. Indicadores da eficácia do funcionamento do par "QS - consumidor".

Ao escolher um critério para a eficiência do funcionamento do QS, é necessário levar em consideração a dupla abordagem na consideração dos sistemas de filas. Por exemplo, o trabalho de um supermercado, como um CMO, pode ser visto de lados opostos. Por um lado, tradicionalmente aceito, o comprador, na fila do caixa, é um pedido de atendimento, e o caixa é um canal de atendimento. Por outro lado, um caixa que está à espera de clientes pode ser considerado como um pedido de serviço, e um cliente é um dispositivo de serviço capaz de satisfazer o pedido, i.e. vá ao caixa e pare o tempo de inatividade forçado do caixa. (tradicionalmente - compradores > que caixas, se caixas > que compradores, eles estão esperando por compradores).

A PARTIR DE
Com isso em mente, é conveniente minimizar ambas as partes do QS simultaneamente.

A utilização de tal abordagem dual implica a necessidade de levar em consideração, na formação do critério de eficiência, não apenas os indicadores acima separadamente, mas também vários indicadores simultaneamente, refletindo os interesses dos subsistemas de QS servidos e atendidos. Por exemplo, mostra-se que o critério de eficiência mais importante nas tarefas de enfileiramento é o tempo total gasto pelo cliente na fila, por um lado, e canais de atendimento ociosos, por outro.

Classificação de sistemas de filas

1. Pela natureza do serviço, distinguem-se os seguintes tipos de QS:

1.1. Sistemas de espera ou sistemas de filas. Os requisitos que entraram no sistema e não são aceitos imediatamente para atendimento são acumulados em uma fila. Se os canais estiverem livres, a solicitação será atendida. Se todos os canais estiverem ocupados no momento do recebimento da solicitação, a próxima solicitação será atendida após a conclusão do atendimento da anterior. Tal sistema é chamado de totalmente acessível (com fila ilimitada).

Existem sistemas com serviço autônomo, quando o serviço inicia em determinados momentos;

Sistemas com fila limitada. (reparação de garagem)

Sistemas com falhas. Todas as solicitações que chegaram no momento do atendimento da solicitação são rejeitadas. (GTS)

Sistemas com fluxo de entrada de grupo e serviço de grupo. Nesses sistemas, os aplicativos chegam em grupos em pontos de tempo e a manutenção também ocorre em grupos.

2. De acordo com o número de canais de atendimento, os QSs são divididos nos seguintes grupos.

QS de canal único.

QS multicanal. O atendimento da próxima solicitação pode começar antes do término do atendimento da solicitação anterior. Cada canal atua como um servidor independente.

3. De acordo com a gama de objetos atendidos, distinguem-se dois tipos.

QS Fechado. Um sistema de filas em malha fechada é um sistema de filas no qual os clientes atendidos podem retornar ao sistema e ser atendidos novamente. Exemplos de um SMO fechado são oficinas, bancos de poupança.

CMOs abertos.

4. Pelo número de estágios de serviço, distinguem-se QS monofásicos e multifásicos.

Fase única QS são sistemas homogêneos que realizam a mesma operação de serviço.

Polifásico QS são sistemas em que os canais de atendimento são dispostos em série e realizam diversas operações de atendimento. Um exemplo de um QS multifásico são as estações de serviço de automóveis.

A classificação de QS acima é condicional. Na prática, na maioria das vezes, os QSs atuam como sistemas mistos. Por exemplo, as aplicações aguardam até um determinado momento para o início do serviço, após o qual o sistema passa a funcionar como um sistema com falhas.

Em muitas áreas da economia, finanças, produção e vida cotidiana, um papel importante é desempenhado por sistemas de filas(SMO), ou seja, tais sistemas em que, por um lado, existem solicitações maciças (requisitos) para a execução de quaisquer serviços e, por outro lado, essas solicitações são atendidas.

Como exemplos de QS na esfera financeira e econômica, podemos citar sistemas que são: bancos de diversos tipos, seguradoras, inspetorias fiscais, serviços de auditoria, diversos sistemas de comunicação (incluindo estações telefônicas), complexos de carga e descarga (estações de commodities), postos de gasolina, empresas e organizações diversas do sector dos serviços (lojas, estabelecimentos de restauração, balcões de informação, cabeleireiros, bilheteiras, casas de câmbios, oficinas, hospitais).

Sistemas como redes de computadores, sistemas de coleta, armazenamento e processamento de informações, sistemas de transporte, locais de produção automatizados, linhas de produção também podem ser considerados como um tipo de QS.

No comércio, muitas operações são realizadas no processo de mover a massa de mercadorias da esfera da produção para a esfera do consumo. Tais operações são: carga e descarga de mercadorias, transporte, acondicionamento, acondicionamento, armazenagem, lay out, venda, etc. operações de natureza aleatória. Tudo isso cria não uniformidade no trabalho das organizações e empresas comerciais, gera subcargas, paralisações e sobrecargas. As filas ocupam muito tempo, por exemplo, de compradores em lojas, motoristas de carros em depósitos de mercadorias, aguardando descarregamento ou carregamento.

Nesse sentido, surgem as tarefas de analisar o trabalho de, por exemplo, um departamento comercial, uma empresa comercial ou uma seção, para avaliar suas atividades, identificar deficiências, reservas e, finalmente, tomar medidas destinadas a aumentar sua eficiência. Além disso, existem problemas associados à criação e implementação de formas mais econômicas de realizar operações dentro de uma seção, departamento, empresa comercial, base vegetal, departamento comercial, etc. Portanto, na organização do comércio, os métodos da teoria das filas tornam é possível determinar o número ideal de pontos de venda de um determinado perfil, o número de vendedores, a frequência de entrega de mercadorias e outros parâmetros.

Armazéns ou bases de organizações de suprimentos e marketing podem servir como outro exemplo típico de sistemas de filas, e a tarefa da teoria das filas é estabelecer a relação ótima entre o número de requisitos de serviço que chegam à base e o número de dispositivos de atendimento, nos quais o os custos totais de manutenção e as perdas decorrentes do tempo de inatividade do transporte seriam mínimos. A teoria das filas também pode encontrar aplicação no cálculo da área dos armazéns, enquanto a área do armazém é considerada como um dispositivo de serviço, sendo a chegada de veículos para descarga um requisito.

Principais características do QS

QS inclui o seguinte elementos: fonte de requisitos, fluxo de entrada de requisitos, fila, dispositivo de serviço (canal de serviço), fluxo de saída de requisitos (solicitações atendidas).

Cada QS é projetado para atender (executar) um determinado fluxo de aplicações (requisitos) que entram no sistema, principalmente não regularmente, mas em momentos aleatórios. O serviço de aplicativos também dura não por um tempo constante e predeterminado, mas por um tempo aleatório, que depende de muitos motivos aleatórios. Após atender a solicitação, o canal é liberado e está pronto para receber a próxima solicitação.

A natureza aleatória do fluxo de pedidos e o tempo do seu atendimento leva a uma carga de trabalho desigual do QS: em alguns intervalos de tempo, os pedidos não atendidos podem se acumular na entrada do QS, o que leva a uma sobrecarga do QS, enquanto em alguns outros intervalos de tempo, com canais livres na entrada do QS, não há solicitações. à ociosidade de seus canais. Os aplicativos que se acumulam na entrada do QS ou "tornam-se" na fila, ou, por algum motivo, a impossibilidade de continuar na fila, deixam o QS sem atendimento.

O esquema QS é mostrado na Figura 5.1.

Figura 5.1 - Esquema do sistema de filas

Cada QS inclui em sua estrutura um certo número de dispositivos de serviço, que são chamados de canais de atendimento. O papel dos canais pode ser desempenhado por vários dispositivos, pessoas que realizam determinadas operações (caixas, operadores, vendedores), linhas de comunicação, veículos, etc.

Cada QS, dependendo de seus parâmetros: a natureza do fluxo de aplicações, o número de canais de atendimento e seu desempenho, bem como as regras de organização do trabalho, possui uma certa eficiência operacional (throughput), o que permite mais ou menos lidar com sucesso com o fluxo de aplicativos.

QS é o objeto de estudo teoria das filas.

Objetivo da teoria das filas- desenvolvimento de recomendações sobre a construção racional do QS, a organização racional do seu trabalho e a regulação do fluxo de aplicações para garantir uma elevada eficiência do QS.

Para atingir este objetivo, são definidas as tarefas da teoria das filas, que consistem em estabelecer as dependências da eficiência do funcionamento do QS em sua organização (parâmetros).

Como características da eficácia do funcionamento do QS Existem três grupos principais de indicadores (geralmente médios) para escolher:

1. Indicadores da eficácia do uso do QS:

1.1. A taxa de transferência absoluta do QS é o número médio de solicitações que o QS pode atender por unidade de tempo.

1.2. A taxa de transferência relativa do QS é a razão entre o número médio de aplicativos atendidos pelo QS por unidade de tempo e o número médio de solicitações recebidas no mesmo tempo.

1.3. A duração média do período de emprego do SMO.

1.4. A taxa de utilização do QS é o compartilhamento médio de tempo durante o qual o QS está ocupado atendendo solicitações.

2. Indicadores de qualidade de serviço do aplicativo:

2.1. Tempo médio de espera para um aplicativo na fila.

2.2. Tempo médio de residência de um pedido na OCM.

2.3. A probabilidade de recusa do pedido em serviço sem espera.

2.4. A probabilidade de que o pedido recebido seja imediatamente aceito para serviço.

2.5. A lei da distribuição do tempo de espera para um aplicativo na fila.

2.6. A lei de distribuição do tempo gasto por um aplicativo no QS.

2.7. O número médio de aplicativos na fila.

2.8. O número médio de aplicações no QS, etc.

3. Indicadores de desempenho do par "SMO - consumidor", onde "consumidor" significa todo o conjunto de aplicações ou parte de sua fonte (por exemplo, a renda média trazida pelo QS por unidade de tempo, etc.).

A natureza aleatória do fluxo de aplicativos e a duração de seu serviço gera no QS processo aleatório. Porque momentos no tempo Ti e intervalos de tempo para recebimento de pedidos T, duração das operações de serviço Obs, na fila T och, comprimento da fila l och são variáveis ​​aleatórias, então as características do estado dos sistemas de filas são probabilísticas. Portanto, para resolver os problemas da teoria das filas, é necessário estudar esse processo aleatório, ou seja, construir e analisar seu modelo matemático.

O estudo matemático do funcionamento do QS é bastante simplificado se o processo aleatório que ocorre nele for Markoviano. Para que um processo aleatório seja markoviano, é necessário e suficiente que todos os fluxos de eventos, sob a influência dos quais o sistema transita de estado para estado, sejam (os mais simples) Poisson.

O fluxo mais simples tem três propriedades principais: ordinário, estacionário e sem efeitos colaterais.

Fluxo normal significa a impossibilidade prática de recebimento simultâneo de 2 ou mais requisitos. Por exemplo, a probabilidade de várias caixas registradoras em uma loja de autoatendimento falharem ao mesmo tempo é bem pequena.

Estacionárioé um fluxo para o qual a expectativa matemática do número de requisitos que entram no sistema por unidade de tempo (denotamos λ ) não muda com o tempo. Assim, a probabilidade de um certo número de requisitos entrar no sistema durante um determinado período de tempo ?T depende de seu valor e não depende da origem de sua referência no eixo do tempo.

Sem efeito colateral significa que o número de reclamações recebidas pelo sistema antes do momento T, não determina quantas solicitações entrarão no sistema durante o tempo (T + ?T). Por exemplo, se uma caixa registradora tiver uma quebra na caixa registradora no momento e for eliminada pelo caixa, isso não afeta a possibilidade de uma nova quebra nessa caixa no momento seguinte, e mais ainda a probabilidade de uma quebra em outras caixas registradoras.

Para o fluxo mais simples, a frequência de recebimento de requisitos no sistema obedece à lei de Poisson, ou seja, a probabilidade de chegada ao longo do tempo T suave k requisitos é dado pela fórmula

Onde λ — intensidade do fluxo de aplicação, ou seja, o número médio de pedidos que chegam ao QS por unidade de tempo,

Onde τ - o valor médio do intervalo de tempo entre duas aplicações vizinhas.

Para tal fluxo de requisições, o tempo entre duas requisições vizinhas é distribuído exponencialmente com uma densidade de probabilidade

O tempo de espera aleatório na fila de início de serviço também pode ser considerado distribuído exponencialmente:

Onde ν — intensidade do tráfego da fila, ou seja, o número médio de pedidos que chegam para atendimento por unidade de tempo,

Onde T oché o tempo médio de espera na fila.

O fluxo de saída das requisições está associado ao fluxo de serviço no canal, onde a duração do serviço Obsé uma variável aleatória e em muitos casos obedece à lei de distribuição exponencial com densidade

Onde μ — taxa de fluxo de serviço, ou seja, o número médio de solicitações atendidas por unidade de tempo,

Uma característica importante do QS, que combina indicadores λ e μ , é intensidade de carga, que mostra o grau de coordenação dos fluxos de aplicativos especificados:

Indicadores listados k, τ, λ, l och, Toch, ν, T obs, μ, ρ, Р k são os mais comuns para QS.

Na modelagem analítica, o estudo de processos ou objetos é substituído pela construção de seus modelos matemáticos e pelo estudo desses modelos. O método baseia-se na identidade da forma das equações e na unicidade das relações entre as variáveis ​​nas equações que descrevem o original e o modelo. Uma vez que os eventos que ocorrem em redes de computadores locais são de natureza aleatória, os modelos matemáticos probabilísticos da teoria das filas são os mais adequados para o seu estudo.

O modelo analítico da rede é um conjunto de relações matemáticas que interligam as características de entrada e saída da rede. Ao derivar tais relacionamentos, deve-se negligenciar alguns detalhes ou circunstâncias sem importância.

Uma rede de telecomunicações, com alguma simplificação, pode ser representada como um conjunto de processadores (nós) conectados por canais de comunicação. Uma mensagem que chegou a um nó espera algum tempo antes de ser processada. Isso pode criar uma fila dessas mensagens esperando para serem processadas. Tempo de transmissão ou tempo total de atraso da mensagem:

onde são o tempo de propagação, o tempo de serviço e o tempo de espera, respectivamente. Uma das tarefas da modelagem analítica é determinar o valor médio D. Com grandes cargas, a principal contribuição vem da espera pelo atendimento 4. Para descrever as filas no futuro, será usada a notação de D. J. Kendell:

Onde MAS– processo de chegada; NO - processo de atendimento; A PARTIR DE– número de servidores (nós); Para– tamanho máximo da fila (padrão – ∞);

dentro– número de clientes (padrão – sim); z – esquema de operação do buffer (FIFO por padrão).

Cartas MAS e NO representam os processos de chegada e atendimento e geralmente são substituídos pelas seguintes letras que caracterizam a lei correspondente à distribuição de eventos:

Os esquemas de buffer mais comuns são

FIFO (First-In-First-Out), LIFO (Last-In-First-Out) e FIRO (First-In-Random-Out). Por exemplo, a entrada M/M/2 significa uma fila para a qual os tempos de chegada e serviço são distribuídos exponencialmente, existem dois servidores, o comprimento da fila e o número de clientes podem ser arbitrariamente grandes e o buffer funciona de acordo com o esquema FIFO.

Comprimento médio da fila Q dada a taxa média de mensagens de entrada λ e o tempo médio de espera Cé definido com base no teorema de Little (1961):

Para opção de fila M/G/ 1, o processo de entrada é caracterizado por uma distribuição de Poisson com uma taxa de chegada de mensagens λ. Probabilidade de admissão para mensagens de login por vez té igual a:

(3.3)

Deixar N– número de clientes no sistema, Qé o número de clientes na fila e deixe a probabilidade de que um cliente de entrada detecte j outros clientes é igual a:

Então o tempo médio de espera é:

onde σ é o desvio padrão para a distribuição do tempo de serviço.

Para opção de fila (Η – função

distribuição do tempo de serviço). Onde deveria.

Para opção de fila M/D/ 1 tempo de atendimento é constante e o tempo médio de espera é:

Considere uma variante de uma rede Ethernet baseada em um hub-switch com o número de canais N. Neste caso, será assumido que as mensagens na entrada de todos os nós possuem uma distribuição Poisson com intensidade média, a distribuição das mensagens ao longo do comprimento é arbitrária. As mensagens são enviadas na mesma ordem em que chegaram. O tráfego na rede é considerado simétrico. A fila tem um modelo. O tempo médio de espera neste caso é:

Onde

(3.9)

onde, é igual à probabilidade de que a mensagem do remetente /" seja enviada ao destinatário. O requisito de estabilidade exige isso. Para maiores n isso leva a

A operação de uma rede Ethernet é caracterizada por uma série de parâmetros, incluindo a probabilidade de captura do canal e a eficiência. O primeiro parâmetro é determinado pela expressão

Onde Ρ – a probabilidade de exatamente uma estação tentar transmitir um quadro durante um ciclo e adquirir o canal; Q- o número de estações tentando adquirir um canal para transmitir um quadro de dados.

A eficiência de uma LAN Ethernet é definida como segue. O uptime total de uma rede Ethernet é dividido entre intervalos de transmissão e intervalos de contenção. Para enviar um quadro de dados, você precisa L/C segundos, onde eu– comprimento do quadro em bits, A PARTIR DE– taxa de transferência de dados em bits/s. Tempo médio Τ necessário para capturar o canal é igual a:

Onde Cé o número médio de ciclos que se passaram no intervalo de contenção até a estação tomar o canal para transmitir um quadro de dados; NO– duração do relógio ou tempo até que a colisão seja detectada após o início da transmissão do quadro.

Número médio de ciclos C calculado da seguinte forma:

Tendo em conta os indicadores introduzidos, a eficiência Ε A operação Ethernet LAN é definida da seguinte forma:

Os seguintes tipos de QS são usados ​​com mais frequência para modelagem de LAN:

• 1. QS de canal único com espera. Eles representam um dispositivo de serviço com uma fila interminável. Este QS é o mais comum em modelagem. Com algum grau de aproximação, pode ser usado para simular quase qualquer nó de LAN.
• 2. QS de canal único com perdas. Represente um dispositivo de serviço com um número finito de lugares na fila. Se o número de aplicativos exceder o número de lugares na fila, os aplicativos extras serão perdidos. Este tipo de QS pode ser usado para modelar canais de transmissão em uma LAN.
• 3. QS multicanal com expectativa. São vários dispositivos operacionais paralelos com uma fila interminável comum. Este tipo de QS é frequentemente usado ao modelar grupos de terminais de assinante LAN operando em modo on-line.
• 4. QS multicanal com perdas. São vários dispositivos de serviço paralelo com uma fila comum, cujo número de lugares é limitado. Esses QSs, assim como aqueles com perdas de canal único, são frequentemente usados ​​para modelar canais de comunicação em uma LAN.
• 5. QS de canal único com recebimento de aplicativos em grupo. Eles representam um dispositivo de serviço com uma fila interminável. Antes da manutenção, os aplicativos são agrupados em pacotes de acordo com uma determinada regra.
• 6. QS de canal único com atendimento em grupo de aplicativos. Eles representam um dispositivo de serviço com uma fila interminável. Os aplicativos são atendidos por pacotes compilados de acordo com uma determinada regra. Os dois últimos tipos de QS podem ser usados ​​para modelar esses nós de LAN como centros de comutação (nós).

A rede local como um todo pode ser representada como uma rede de filas. Distinguir abrir, fechado e misturado redes.

abrir é chamado de sistema de filas que consiste em Μ nós, e pelo menos um dos nós da rede recebe um fluxo de entrada de solicitações de fora e há uma drenagem de solicitações da rede. Para redes abertas, é característico que a intensidade das requisições que entram na rede não dependa do estado da rede, ou seja, do número de requisições que já chegaram na rede. Redes abertas são usadas para simular LANs offline. Cada aplicação chega à entrada do nó de comutação correspondente, onde é determinado o local de seu processamento. Em seguida, o pedido é transmitido para o "seu" servidor ou através de um canal de comunicação para um "vizinho", onde é processado, após o que retorna à fonte e sai da rede.

Fechadas chamada de rede de filas com muitos nós Μ sem fonte e coletor, no qual circula um número constante de aplicativos. QS fechados são usados ​​para simular tais LANs, cujas fontes de informação são terminais de usuário operando em modo on-line. Neste caso, cada grupo de terminais de usuário é representado como um sistema de fila multicanal com espera e está incluído nos dispositivos de rede.

Distinguir simples e difícil modos de operação dos assinantes de diálogo. No modo simples, os assinantes não fazem nada, exceto enviar trabalhos para a LAN e considerar a resposta que recebem.

Os assinantes dos terminais enviam solicitações que são enviadas por meio de canais de comunicação para os nós de comutação e, de lá, para processamento para o servidor "próprio" ou "vizinho". O processamento adicional é realizado da mesma maneira que na rede aberta.

Em um modo de diálogo complexo, o trabalho dos assinantes se apresenta como um conjunto de operações de um determinado processo denominado tecnológico. Cada operação do processo tecnológico é modelada pelo QS correspondente. Algumas operações fornecem acesso à LAN e algumas operações podem não fornecer tal recurso. O algoritmo de operação da própria LAN é o mesmo de uma rede fechada.

Uma rede mista é uma rede de filas na qual circulam vários tipos diferentes de solicitações (gráficos), sendo a rede fechada em relação a alguns tipos de solicitações e aberta em relação a outras. Com a ajuda de QS mistos, essas LANs são modeladas, algumas das quais assinantes trabalham em modo interativo e outras em modo off-line. Para assinantes interativos, também é distinguido um modo de operação simples e complexo. Muitas vezes, QSs mistos modelam LANs, nas quais o servidor é carregado adicionalmente com tarefas que são executadas no contexto da operação da própria rede.

O algoritmo de operação de rede para assinantes interativos é semelhante ao algoritmo de operação de rede fechada e o algoritmo de operação de rede para assinantes não operacionais é semelhante ao algoritmo de operação de rede aberta.

Existem modelos de LAN exponenciais e não exponenciais. Modelos Exponenciais são baseados na suposição de que os fluxos de requisições que entram na LAN são Poisson, e o tempo de serviço nos nós da LAN tem uma distribuição exponencial.

Para tais redes, métodos exatos foram obtidos para determinar suas características; a complexidade de obter uma solução depende principalmente da dimensão da rede.

No entanto, na maioria das redes (e redes locais em particular) os fluxos não são Poisson. Os modelos dessas redes são chamados não exponencial. Na análise de redes não exponenciais, no caso geral, não existem soluções exatas, por isso os métodos aproximados são os mais utilizados aqui.

Um desses métodos é método de aproximação de difusão. O uso da aproximação de difusão permitiu obter dependências analíticas aproximadas para determinar as características de todos os tipos de QS considerados acima.

Isso não requer o conhecimento exato das funções de distribuição das variáveis ​​aleatórias associadas a um determinado QS (intervalos entre chegadas de requisições por tempo de atendimento nos dispositivos), mas apenas o conhecimento da primeira (expectativa matemática) e da segunda (dispersão ou quadrado do coeficiente de variação - ΚΚΒ) momentos dessas quantidades é suficiente.

O uso da aproximação de difusão na análise de LVS é baseado no seguinte:

• para cada tipo de requisições, a intensidade de recebimento de requisições deste tipo aos nós da rede é calculada como se esse fluxo de requisições circulasse na rede apenas um;
• de acordo com uma certa regra, dependendo do tipo de QS e da disciplina de serviço, os fluxos de aplicativos de todas as fontes são adicionados;
• de acordo com uma certa regra, o tempo médio de serviço em cada nó da LAN é determinado;
• os valores obtidos são substituídos na fórmula de difusão correspondente e as características dos nós da LAN são determinadas;
• as características da LAN como um todo são determinadas.

A declaração do problema de análise da LAN terá então a seguinte forma. Dado:

• número de nós da LAN;
• tipo de cada nó da LAN (tipo de QS modelando este nó);
• disciplina de serviço em cada nó da LAN;
• o número total de tipos de origem de solicitação operando no modo online;
• o número total de tipos de origem de declaração operando no modo não em tempo real;
• para fontes interativas no caso de um modo de operação complexo, o número de processos tecnológicos de cada tipo, o número de operações em cada processo tecnológico, a média e ΚΚΒ do tempo de execução de cada operação, a matriz de probabilidade de transferências entre operações , e a presença ou ausência de acesso à LAN em cada operação;
• para as fontes de diálogo no caso de um modo de operação simples, o número de fontes (terminais) de cada tipo, a média e ΚΚΒ do tempo de reação do assinante à resposta da rede;
• para assinantes não operacionais - a intensidade média de recebimento de pedidos e ΚΚΒ tempo entre os recebimentos de pedidos; para cada tipo de solicitação (online e não operacional) a intensidade média de serviço em cada nó LAN, ΚΚΒ tempo de serviço em nós LAN e a matriz de probabilidade de transmissões entre nós. Necessário para encontrar:
• o valor médio e a variação (ou desvio padrão) do tempo de atraso de cada tipo de solicitação na LAN como um todo;
• a média e variância (ou desvio padrão) do tempo de atraso nos nós da LAN;
• carregando nós de LAN;
• a probabilidade de perder uma reclamação em um nó de LAN (para nós modelados por um QS com perdas).

As restrições podem ser as seguintes:

a probabilidade de perder um pedido não deve exceder 1;

todas as características devem ser positivas.

Às vezes, é interessante determinar um indicador como o tempo máximo de atraso para cada tipo de solicitação na LAN. O tempo máximo é o tempo que só pode ser excedido para uma porcentagem predeterminada de solicitações de cada tipo. Para determinar o tempo máximo, utiliza-se uma técnica baseada na aproximação da função de distribuição do tempo de atraso na rede pelo Erlang ou distribuição hypsexponencial, enquanto é necessário definir o compartilhamento (porcentagem) das requisições para as quais o tempo máximo é calculado.