Algoritmo de alocação prioritária de processamento de solicitações

Considere os modelos existentes para a distribuição ideal de dados entre os nós de uma rede de computadores. Como critério de desempenho, usaremos a quantidade média de dados enviados pelas linhas de comunicação ao processar solicitações e distribuir atualizações, o custo total do tráfego gerado pela operação de um sistema de computação distribuído por uma unidade de tempo e o custo operacional da rede ¹. Como exemplo, consideramos um modelo de alocação ideal de arquivos em uma rede de computadores com um critério de eficiência - a quantidade média de dados enviados por linhas de comunicação ao processar solicitações e distribuir atualizações.


Considere uma rede de computadores, cada nó, que consiste em um computador, dispositivos terminais e equipamentos de transmissão de dados. Suponha que uma solicitação que chegue ao dispositivo terminal de qualquer nó implique acesso a um arquivo específico em um banco de dados distribuído, e o volume da solicitação e da mensagem correta para o mesmo arquivo dependa do nó sem o qual ele chegou. Assumimos que o esquema de processamento de solicitações é o seguinte.
A solicitação iniciada no terminal entra na fila de entrada do nó correspondente. O processador do computador processa as solicitações na ordem em que são recebidas. Se uma cópia do arquivo desejado estiver contida no banco de dados local do nó para o terminal do qual a solicitação foi recebida, a solicitação será processada e o resultado será exibido nesse terminal. Se uma cópia do arquivo necessário não estiver contida no banco de dados local do nó, primeiro, o diretório que contém a cópia do arquivo necessário será determinado a partir do diretório do banco de dados local. Em seguida, a solicitação é enviada para esse nó, lá é processada e a resposta é recebida pelo nó original. O procedimento para atender às solicitações não afeta a quantidade de dados enviados pelos canais de comunicação.

As mensagens corretivas são veiculadas na ordem de suas filas. No entanto, comparados aos pedidos de mensagens, eles têm a maior prioridade de serviço.
No processo de atender à solicitação e corrigir as mensagens, uma certa quantidade de dados é enviada pelos canais de comunicação em cada unidade de tempo, dependendo da distribuição de cópias de arquivos nos bancos de dados locais. Quanto menor a quantidade de dados enviados pelos canais de comunicação por unidade de tempo, maior a velocidade de processamento das mensagens.
Caminho
n é o número de nós da rede;
t é o número de independência dos arquivos incluídos no banco de dados distribuído;
Kj é o j-ésimo nó de comunicação;
Quinto arquivo de um banco de dados distribuído;
v - a quantidade de dados solicitados ao executar uma solicitação para um arquivo Fi a partir do nó Kj;
βv é a quantidade de dados solicitados ao executar uma solicitação para um arquivo Fi a partir do nó Kj;
Yv é o volume da mensagem de correção para o arquivo Fi do nó Kj;
λv é a intensidade das solicitações para o arquivo Fi iniciadas no nó Kj;
λ`v é a intensidade das mensagens corretivas para o arquivo Fi do nó Kj;
bj - a quantidade de nó de memória Kj, projetado para acomodar arquivos;
Vj é o número de cópias do i-ésimo arquivo (Vj é o valor fornecido i <= Vji <= n);
Xv (I = I, mj = I, n) - valores determinados pela fórmula.
{I, se uma cópia do arquivo Fi estiver localizada no nó Kj;}
{v {¸ caso contrário}

A intensidade λi gera a quantidade de dados
Vi = ΣAλ`v UVXi
5 - i
5 - j que
precisa de transferência. Se colocarmos

nk
λ` = ΣΣAV
i = jj = i

, a quantidade média de dados necessária para o encaminhamento ao processar a mensagem de correção no sistema é igual.
nkx
V` = IΣΣΣλ`v UVXI
λ i = jj = i 5 - i
5 - j

A intensidade λ`v gera a quantidade de dados λ`v (av + β) (I-v) que precisam ser transferidos. Portanto, a quantidade média de dados necessários para o envio ao executar uma solicitação no sistema é
nk
V` = IΣΣλ`v (av + β) (I-X v)
λ` i = jj = i

nk em
que λ = Σ Σλ`v
i = jj = i

Assim, o modelo matemático do problema da distribuição ótima de cópias de arquivos nos nós da rede de computadores para o critério de otimização, a quantidade média de dados transferidos pelas linhas de comunicação ao processar a solicitação e corrigir a mensagem será a seguinte: é necessário encontrar o mínimo da função linear
L, = V + V '
com restrições
n
Σ xv = yi (i = I, m)
i = j

n
ΣL, xv ≤ bi (i = I, n)
i = j

v = (o ﮞ) II, m, j = I, n)

Para melhorar o desempenho do sistema, restrições podem ser usadas como uma condição adicional o tempo esperado para concluir a solicitação de cada nó. De fato, seja aifz o tempo esperado necessário para executar a solicitação iniciada no nó Kj para o arquivo Fj que está contido no nó Kj; Tif seja o tempo máximo permitido para concluir a solicitação para o arquivo Fj iniciado no nó Kj. Então, entre as grandezas aifz e v, a relação
av5 (I-)v) 15 ≤ v vale
para j <> S, I <> i <> m.
Para obter restrições dessa relação, os valores de aifz devem ser expressos em termos das variáveis ​​Xv. No caso geral da topologia de rede, isso é muito difícil de fazer. E somente se você não usar uma série de suposições impostas às características da rede, poderá encontrar expressões simples de conhecimento aifz por meio de v.
As desvantagens dos modelos desenvolvidos podem ser atribuídas ao fato de conterem uma série de limitações e simplificações, não refletem uma característica do RDB como um fragmento.As desvantagens dos modelos desenvolvidos podem ser atribuídas ao fato de conterem uma série de limitações e simplificações, não refletem uma característica do RDB como fragmentação e também são estáticos e não levam em consideração a dinâmica dos processos que ocorrem no sistema.
Quanto aos métodos utilizados para otimizar o RDB - o método branch and bound, programação matemática - eles deram resultados positivos, pois para sistemas de informações de computador dobrados reais com DBD, a dimensionalidade do problema é grande, o que requer tempo e recursos computacionais consideráveis. Portanto, para esta tarefa, é aconselhável usar algoritmos genéticos que implementem a pesquisa aleatória direcionada com base nos mecanismos da evolução natural.
Assim, apesar de estudos anteriores, os problemas de modelagem e otimização dos DBDs dos sistemas de informações de computadores não receberam uma solução final, os modelos e métodos utilizados apresentam várias desvantagens, o que exigiu sua melhoria adicional.
Uma questão igualmente importante é o fornecimento dos dados de origem mais precisos. A implementação de qualquer modelo matemático. A colocação ideal de arquivos RBD nos nós de uma rede de computadores requer várias matrizes de informações dos dados de origem, uma parte significativa das quais só pode ser obtida de forma média ou reduzida. Essas são características como intensidades de solicitação, tempo para envio e processamento de solicitações, volumes de solicitações e respostas a solicitações. A precisão das informações estáticas coletadas afetará decisivamente o resultado final da implementação do modelo matemático selecionado e, consequentemente, o desempenho do sistema que trabalha com o RDB.
Para obter dados numéricos confiáveis, é necessário descobrir a natureza cíclica das informações no sistema. Esse período pode variar entre aplicativos de um dia a um quarto. No processamento posterior das informações coletadas, é necessário levar em consideração as explosões médias de atividade. As características numéricas do tempo de processamento, volume, remessas e probabilidades de manuseio devem ser calculadas levando em consideração o ajuste para situações de pico, a fim de proteger o sistema de atrasos significativos durante os downloads mais intensivos.
Além das características listadas, no processo de trabalhar com o banco de dados otimizado, é necessário acumular informações sobre o tipo de solicitação (leitura, pesquisa, atualização), o nome do arquivo para o qual a solicitação foi emitida, o número do nó do qual a solicitação foi emitida e o tempo da resposta real.
Uma base de conhecimento é um conjunto de unidades de conhecimento que representam a formação, usando algum método para representar o conhecimento, o reflexo de objetos em uma área problemática e seus relacionamentos, ações em objetos e, possivelmente, as incertezas com as quais essas ações são realizadas.
Como métodos para representar o conhecimento, regras ou objetos (quadros), ou uma combinação deles, são mais frequentemente usados. Então, as regras são construções.
Se <condição> Então <conclusão> CF (fator de certeza) <valor>.
Como determinantes da certeza (CF), em geral, encontramos as probabilidades condicionais da abordagem bayesiana (de 0 a 1) ou os coeficientes de confiança da lógica ímpar (de 0 a 100). Exemplos de regras são os seguintes.
Regra 1. Se a Razão de Rentabilidade>0,2
Então lucratividade = “satisfeito” CF 100.
Regra 2. Se dívida = “não” e lucratividade = “satisfeito”.
Isso é Confiabilidade da Empresa = “Satisfeito” CF 90.
A qualquer momento do sistema, existem tipos de conhecimento:
Conhecimento estruturado - conhecimento estatístico da área de assunto. Uma vez que o conhecimento é identificado, ele não muda mais.
Conhecimento dinâmico estruturado - conhecimento mutável sobre a área de assunto, eles são atualizados à medida que novas informações são descobertas.
A qualidade do ES é determinada pelo tamanho e qualidade da base de conhecimento (regras ou heurísticas). O sistema opera no seguinte modo cíclico: seleção (consulta) dos dados ou resultados das análises de observação, interpretação dos resultados, assimilação de novas informações, avanço de hipóteses temporais usando as regras e seleção da próxima parte dos dados e resultados da análise. Esse processo continua até que haja informações suficientes para uma conclusão final.
Assim, um sistema de inteligência artificial construído com base em conhecimento especializado de alta qualidade sobre uma determinada área (obtida de especialistas - especialistas neste campo) é chamado de sistema especialista. Os sistemas especialistas - um dos poucos tipos de sistemas de inteligência artificial - se espalharam e encontraram aplicação prática.

Os sistemas especialistas diferem de outros programas das seguintes maneiras:
1. Competência - em uma área específica, o sistema especialista deve atingir o mesmo nível que os especialistas humanos, ao mesmo tempo em que deve usar as mesmas técnicas heurísticas e refletir profunda e amplamente a área;
2. Raciocínio simbólico–O conhecimento em que se baseiam os sistemas especialistas representa de forma simbólica os conceitos do mundo real, o raciocínio também ocorre na forma de transformações de conjuntos simbólicos;
3. Profundidade - o exame deve resolver problemas profundos e não triviais, marcados pela complexidade, seja em termos da complexidade do conhecimento que o sistema especialista utiliza ou em termos de abundância; isso não permite o uso de busca exaustiva de opções como método de solução de problemas e o faz recorrer a métodos heurísticos, criativos e informais. ;
4. Autoconsciência - um sistema especialista deve incluir um mecanismo para explicar como se trata da solução do problema.

Literatura
1. Moiseev VB Representação do conhecimento em sistemas inteligentes. / Informática e educação, nº 2, 2003.
2. Petrov V.N. Sistemas de Informação - São Petersburgo: Peter, 2003.
3. Rastragin L.Kh. Sistemas de controle experimental. - M.: Nauka, 1974.
4. Saak A.E., Pakhomov E.V., Tyushnyakov V.N. Gerenciamento de Tecnologia da Informação: Livro didático para escolas secundárias. São Petersburgo: Peter, 2005.
5. Semenov M.I. e outros.Tecnologia da informação automatizada na economia. Livro didático. - M.: Finanças e estatística, 2003.
6. Sovetov B.Ya. Sistemas de modelagem: livro didático para universidades. - 3 - ed. reslave. e doca. - M .: Escola Superior, 2001.
7. Suvorova N. Modelagem da informação: quantidades, objetos, algoritmos. - M.: Laboratório de conhecimentos básicos, 2002.

Um pequeno pedaço do meu trabalho sobre sistemas avançados.

Source: https://habr.com/ru/post/pt387567/