Pesquisa de site

Algoritmo baseado em árvore de Raymond


O algoritmo baseado em árvore de Raymond é usado para proteger os sistemas distribuídos da ocorrência de seções pelo método de bloqueio. Sistemas distribuídos são redes com vários números de nós que envolvem o fluxo de mensagens de um nó para outro. Quando o processo está bloqueado ou na seção crítica, apenas um thread ou processo pode ser permitido dentro e outros threads estarão no estado de espera. Como há muitos nós envolvidos nos sistemas distribuídos, isso pode ser reduzido através da geração de árvores.

Algoritmo baseado em árvore de Raymond

Definição

O Algoritmo segue o método de que apenas threads com tokens são permitidos dentro da seção crítica. Cada nó da rede pode ter no máximo um nó pai e que é responsável por gerar os tokens

Algoritmo Nodal

Na estrutura em árvore, cada nó pode ter apenas um nó pai ou raiz para o qual todas as solicitações de outros nós são enviadas. O nó pai segue o mecanismo First in First out (FIFO) para responder às solicitações dos nós filhos, sempre que o token é recebido.

Exclusão mútua

Um token é usado por este algoritmo para garantir a exclusão mútua. Nesta abordagem, cada site é organizado em uma árvore direcionada com bordas apontando na direção do site que contém o token. Se um site tiver o token, ele poderá acessar a parte vital. Isso garante que apenas um site por vez possa acessar a área importante, enquanto todos os outros devem aguardar a liberação do token.

Mecanismo de algoritmo de árvore de Raymond

  • O nó que entra na seção crítica é considerado que possui um token. Vamos considerar o nó A como o nó pai e os nós filhos são B, C e D.

  • Um nó entra na seção crítica com base na solicitação.

  • Quando a fila do site pai é nula, ele move o nó filho para a fila Primeiro a entrar, primeiro a sair e, com base na solicitação, o token é atribuído

  • Quando o nó pai não está vazio ou a fila está cheia, ele empurra o nó filho solicitado para a fila.

  • Quando qualquer nó filho com o token receber outro token, ele moverá o token para o nó filho que precisa de tokens.

Propriedades do algoritmo baseado em árvore de Raymond

Algumas das propriedades principais do algoritmo são,

  • Ele garante propriedade de exclusão mútua usando um token. Se um site tiver o token, ele poderá acessar a parte vital.

  • Todos os sites são organizados como uma árvore direcionada, com as bordas voltadas para o site que contém o token.

  • Existe apenas um pai para cada nó, que recebe solicitações e as encaminha.

  • Cada vez que um nó encontra um token, ele mantém uma fila FIFO de solicitações.

Exemplo do Algoritmo

O algoritmo é implementado no sistema distribuído usando a seguinte estrutura em árvore,

  • No exemplo acima, o site A é o nó primário que contém o token. Os sites abaixo do nó A são os sites B e C que são considerados nós filhos. Esses sites solicitam que o site A entre na seção crítica. O site C é novamente dividido em duas subdivisões como nós D e E.

  • Como na etapa acima, o nó C é o nó primário com dois subnós como D e E. Esses nós enviam a solicitação ao nó pai com base em seus requisitos. Como a solicitação levantada pelos nós B e C já está presente, a solicitação atual será colocada na fila.

  • Com base no token recebido dos nós primários para os secundários, os sites entram na seção crítica.

Complexidade temporal do algoritmo

A seção Crítica do sistema distribuído fornece uma complexidade de tempo de O(log n). É obrigatório que cada nó do processo contenha pelo menos O(log n) bits.

Desvantagem do Algoritmo de Raymond

  • Fome  O algoritmo de Raymond dá origem à fome. A fome é uma condição que pode ocorrer em um sistema simultâneo quando um processo ou thread tem os recursos de que precisa para ser perpetuamente negados. Isso pode acontecer quando um algoritmo de escalonamento prioriza consistentemente outros processos ou threads em detrimento do processo faminto, fazendo com que ele espere indefinidamente por recursos. A falta de energia pode levar à redução do desempenho do sistema e pode até fazer com que o sistema pare de responder.

  • Estratégia gananciosa  O algoritmo de Raymond dá origem à fome. A fome é uma condição que pode ocorrer em um sistema simultâneo quando um processo ou thread tem os recursos de que precisa para ser perpetuamente negados. Isso pode acontecer quando um algoritmo de escalonamento prioriza consistentemente outros processos ou threads em detrimento do processo faminto, fazendo com que ele espere indefinidamente por recursos. A falta de energia pode levar à redução do desempenho do sistema e pode até fazer com que o sistema pare de responder.

Conclusão

O algoritmo é usado com base nas solicitações enviadas pelos nós filhos ao nó pai. O procedimento é seguido pela solicitação do nó pai, executando os nós de acordo com as filas após o nó ser liberado da seção crítica e os nós podem ser escolhidos entre vazios ou não vazios.

Artigos relacionados: