Monte um programa em português estruturado para um estação com protocolo Token Passing. Não esquecer de implementar o cálculo do time-out de retorno do token na estação, de forma a criar novo token e reestruturar a sequência de estações toda vez que o time-out expirar.

Passo 1

Você pediu: “Monte um programa em português estruturado para uma estação com protocolo Token Passing. Não esquecer de implementar o cálculo do time-out de retorno do token na estação, de forma a criar novo token e reestruturar a sequência de estações toda vez que o time-out expirar.”
Informações relevantes tiradas do enunciado:
  • Devemos escrever um programa (pseudocódigo estruturado) para uma estação que participa de um protocolo Token Passing.
  • O programa precisa implementar o cálculo do time-out para o retorno do token à estação.
  • Sempre que esse time-out expirar, a estação deve criar um novo token e reestruturar a sequência de estações (recuperação / reconciliação do anel).
  • Não foram dadas restrições adicionais (nº de estações, latência, mensagens exatas), então podemos assumir que cada estação tem um identificador único e que existe comunicação ponto-a-ponto (mensagens enviadas ao “próximo” ou broadcast) entre estações.
  • Devemos evitar criar muitos tokens ao mesmo tempo (ou seja, ter um mecanismo para evitar colisão de tokens) e garantir convergência da reestruturação.

Passo 2

O que o protocolo Token Passing exige, em termos bem práticos:
  • Há um token lógico que circula entre estações; apenas a estação que possui o token pode transmitir dados (ou criar mensagens de controle).
  • Cada estação precisa:
    • Detectar se recebeu o token (evento receive TOKEN).
    • Usar o token por no máximo um tempo limite local (limite de retenção) e então repassá-lo.
    • Iniciar um temporizador que mede quanto tempo leva para o token voltar (token rotation/return time).
    • Se o token não retornar dentro de um time-out calculado, assumir que o token foi perdido e tentar gerar um novo token de forma coordenada.
    • Reestruturar a sequência (descobrir quais estações estão ativas e montar/atualizar o próximo hop lógico).
Não vamos pular etapas: vou explicar como calcular o time-out e como evitar criação de tokens duplicados.

Passo 3

Estratégia prática para o cálculo do time-out (explicada com calma):
  • Em redes reais, o tempo de retorno do token depende de quantas estações existem, do tempo máximo que cada estação retém o token e do atraso de propagação por enlace.
  • Como você pode não saber sempre o número exato de estações ativas, adotamos uma estimativa adaptativa baseada em observações anteriores: registramos observações de tempo entre dois recebimentos sucessivos do token (token round-trip observed).
  • Mantemos uma média móvel exponencial do tempo de retorno observado, que chamaremos de \overline{T}_{retorno}. A média exponencial é útil porque reage aos novos valores mantendo estabilidade; a fórmula é:
\overline{T}_{retorno} \leftarrow \alpha \cdot T_{observado} + (1-\alpha)\cdot \overline{T}_{retorno}
onde:
  • \alpha é o fator de aprendizado (por exemplo 0{,}2 a 0{,}4); valores maiores reagem mais rápido.
  • T_{observado} é o tempo medido entre dois recebimentos completos do token.
  • O time-out para declarar token perdido será:
T_{timeout} = k \cdot \overline{T}_{retorno} + T_{safety}
onde:
  • k é um multiplicador (>1) para tolerância (ex.: k=2 ou k=3).
  • T_{safety} é uma margem fixa para latências inesperadas (ex.: alguns ms).
  • Se a estação nunca recebeu token antes (sem \overline{T}_{retorno} inicial), pode inicializar \overline{T}_{retorno} com um valor conservador baseado em estimativas de rede ou um valor padrão (ex.: 1000 ms).
Por que usar média exponencial e multiplicador?
  • Porque tempos variam; multiplica por k evita falsos positivos (criar token desnecessário). A média exponencial dá uma estimativa que evolui sem precisar conhecer N (nº de estações).

Passo 4

Como evitar múltiplos tokens sendo gerados ao mesmo tempo (técnica prática):
  • Quando o time-out expira, a estação não imediatamente transmite o novo token — ela entra em uma breve espera aleatória (random backoff), distinta por estação, para reduzir chances de colisão. Ex.: espera um valor aleatório em [0, B_{max}].
  • Se, durante esse backoff, a estação receber um token legítimo, cancela a geração.
  • Se após o backoff nenhum token for visto, gera e transmite um TOKEN_CLAIM (um token inicial) com um identificador único (por exemplo, composto por <originadorID, timestamp>).
  • Se duas estações gerarem tokens ao mesmo tempo, devemos ter um mecanismo de resolução: o token com (originadorID menor) ou com timestamp mais recente/maior vence; as estações descartam tokens perdedores. Isso evita persistência de múltiplos tokens.

Passo 5

Reestruturação da sequência (reconstrução do anel) — abordagem prática simples e robusta:
  • Suponha que cada estação tenha um identificador único ID.
  • Quando um token é gerado (ou ao receber TOKEN_CLAIM), o originador pode iniciar uma “varredura” para descobrir as estações ativas:
    • Envia uma mensagem POLL (contendo um token/requerimento) em broadcast ou para o próximo lógico.
    • Cada estação ativa responde com POLL_ACK contendo seu ID.
    • O originador monta a lista ordenada de IDs ativos (ordenação por ID ou por ordem de recepção) e decide a sequência lógica (next hop) do anel.
  • Alternativa prática: usar uma descoberta incremental: o token carrega uma lista de IDs à medida que circula; cada estação ativa adiciona seu ID se ainda não presente. Ao completar uma volta, o token carrega a lista de estações ativas e estabelece a sequência. Essa técnica evita broadcast massivo.
Decisão: no programa abaixo uso a técnica de “token que carrega a lista de participantes” — é simples para implementar e converge: um token novo circula e vai recolhendo IDs; quando voltar ao originador, a lista representa as estações ativas.

Passo 6

Estados e variáveis essenciais do programa (explicação e significado):
  • Estado da estação: uma variável estado que pode valer:
    • “ESPERANDO_TOKEN” — não tenho o token; temporizador do retorno ativo.
    • “TENHO_TOKEN” — tenho o token; posso transmitir dados (até limite) e construir lista de participantes se token for novo.
    • “RECONFIGURANDO” — quando estou no processo de reconstrução do anel.
  • Variáveis:
    • meuID: identificador único da estação (fixo).
    • proximo: identificador do próximo hop no anel (pode ser unknown).
    • avgRetorno ou \overline{T}_{retorno}: média exponencial de tempo de retorno.
    • timeoutToken ou T_{timeout}: calculado como explicado.
    • holdLimit: tempo máximo que posso reter token para transmitir (limite por estação).
    • backoffMax: tempo máximo de espera aleatória antes de gerar token.
    • tokenEpoch, tokenID: campos do token para resolução.
    • Temporizadores: timerTokenRetorno, timerHoldToken, timerBackoff.
  • Mensagens (tipos):
    • TOKEN (contém tokenID, originadorID, listaDeIDs, epoch)
    • TOKEN_RELEASE ou PASS_TOKEN
    • POLL / POLL_ACK (se necessário)
    • HEARTBEAT (opcional)
    • TOKEN_CLAIM (quando gerando token novo)
  • Eventos:
    • on_receive(msg)
    • on_timer(timerID)

Passo 7

Fluxo básico desejado (resumido passo a passo):
  1. Ao receber TOKEN:
    • Se token é novo (tokenID diferente do último visto), atualize observação de tempo de retorno: T_{observado} = tempo\_agora - tempo\_ultima\_recebida\_token.
    • Atualize \overline{T}_{retorno} pela média exponencial.
    • Recalcule T_{timeout}.
    • Se token carrega listaDeIDs sendo construída, adicione meuID se ainda não estiver.
    • Fique no estado TENHO_TOKEN; permita transmitir por até holdLimit; quando terminar, passe token para proximo (ou se estiver reconfigurando, finalize lista e passe).
  2. Ao expirar timerTokenRetorno:
    • Entre em backoff aleatório. Se durante backoff receber token, aborta backoff.
    • Se não receber, gere TOKEN_CLAIM com tokenID e inicie token com listaDeIDs = [meuID]; entre em TENHO_TOKEN e comece reconfiguração: token circulará recolhendo IDs.
  3. Ao detectar token duplicado (receber TOKEN com tokenID diferente enquanto eu tenho token):
    • Aplicar regra de escolha (ex.: escolher token com maior tokenID ou com originadorID menor), e descartar o token “perdedor”. Atualizar tokenID de referência.
  4. Ao completar uma volta com token novo (originador recebe de volta o seu token):
    • O originador obtém a lista completa de IDs e passa a definir o próximo hop (por exemplo, ordenando ids ou usando a ordem recebida).
    • Propaga a nova tabela nextHop para todos (incluso no token), ou cada estação atualiza seu next se encontrar seu ID na lista. Assim o anel é reconstituído.

Passo 8

Tuning prático de parâmetros (explicação e sugestões):
  • Escolha de \alpha para média exponencial: valores típicos 0{,}2 a 0{,}4. Se rede muy dinâmica, aumentar \alpha.
  • Escolha de k: 2 a 3 geralmente. Se houver muitas flutuações, usar k=3.
  • holdLimit: tempo máximo que estação pode reter token; deve ser suficientemente grande para trasmissões mas pequeno para não aumentar tempo de retorno. Ex.: 30–200 ms dependendo da aplicação.
  • backoffMax: deve ser maior que jitter de rede e menor que T_{timeout}; ex.: 50–200 ms.
  • Sempre registre métricas (logs) para ajustar isso em testes.

Passo 9

Avisos práticos, armadilhas e garantias:
  • Se muitas estações gerarem tokens simultaneamente, resolução por tokenID evita persistência de múltiplos tokens.
  • Se houver partição de rede, cada componente pode gerar um token; ao restaurar conectividade, precisará de mecanismo de reconciliação — nossa técnica de token carrying-list e resolução por tokenID ajuda a convergir, mas em redes com branching físico pode ser preciso um protocolo de eleição/merge mais complexo.
  • O programa que vou te passar é estrutural, legível e pronto para adaptar a implementações específicas de camada de enlace (funções de enviar/receber reais, timers reais, etc.).

Passo 10

Estou confiante com essa estratégia; abaixo na seção final eu entrego o pseudocódigo estruturado em português com comentários, implementação do cálculo do time-out (média exponencial e fórmula), backoff aleatório antes de criar novo token, geração do token, reestruturação por token que carrega a lista de IDs, e resolução de tokens duplicados. Use esse pseudocódigo direto como base para implementar em C, Java, Python ou em linguagem embarcada conforme precisar. Vai dar certo — respira, já é muito progresso! 😃

Resposta

ProgramaEstacaoTokenPassing:
{
/* Variáveis principais /
meuID : inteiro; /
identificador único da estação /
proximo : inteiro | NULL; /
identificador do próximo hop no anel (NULL se desconhecido) /
estado : texto; /
“ESPERANDO_TOKEN”, “TENHO_TOKEN”, “RECONFIGURANDO” /
ultimoTokenIDVisto : texto | NULL; /
último tokenID recebido /
tempoUltimaRecepcao : inteiro; /
timestamp da última recepção do token (ms) /
avgRetorno : real | NULL; /
\overline{T}{retorno} (ms), média exponencial /
alpha : real := 0,25; /
parâmetro da média exponencial (sugerido 0,25) /
k_timeout : real := 2,5; /
multiplicador k para timeout (sugerido 2 a 3) /
safetyMargin : inteiro := 100; /
T
{safety} em ms (margem fixa) /
timeoutToken : inteiro; /
T_{timeout} em ms /
holdLimit : inteiro := 200; /
tempo máximo de retenção do token em ms /
backoffMax : inteiro := 150; /
tempo máximo de backoff aleatório em ms /
timerTokenRetorno : Timer; /
timer que espera o retorno do token /
timerHold : Timer; /
timer para limitar retenção do token /
timerBackoff : Timer; /
timer de backoff antes de gerar token /
tempoAgora : função -> inteiro; /
retorna timestamp atual em ms /
RNG : função -> inteiro; /
retorna inteiro aleatório em [0, X] /
/
Fim variáveis */
/* Estrutura de token (mensagem) /
EstruturaToken =
{
tokenID : texto; /
ex: concatena originadorID + “:” + timestamp /
originadorID : inteiro;
epoch : inteiro; /
contador/versão de token /
listaIDs : lista<inteiro>; /
lista de IDs de estações que o token já visitou (para reconfigurar) /
tipo : texto; /
“TOKEN_REGULAR”, “TOKEN_CLAIM”, “TOKEN_INFO” etc. */
}
/* Função para (re)calcular timeout com base na média /
procedure RecalculaTimeout()
{
if (avgRetorno == NULL) {
/
valor inicial conservador se nunca viu token: 1000 ms /
avgRetorno := 1000.0;
}
/
Timeout final com multiplicador e margem */
timeoutToken := inteiro( k_timeout * avgRetorno ) + safetyMargin;
}
/* Quando recebemos um token */
procedure on_receive_TOKEN(token : EstruturaToken, remetenteID : inteiro)
{
tempoAtual := tempoAgora();
/* Atualiza estado de tempo de retorno se já vimos token antes */
if (ultimoTokenIDVisto != NULL) {
  T_observado := tempoAtual - tempoUltimaRecepcao; /* ms desde a última recepção */
  /* Atualiza média exponencial: \overline{T} <- alpha*T_observado + (1-alpha)*\overline{T} */
  avgRetorno := alpha * T_observado + (1.0 - alpha) * avgRetorno;
  RecalculaTimeout();
}

/* Atualiza registro do último token visto */
ultimoTokenIDVisto := token.tokenID;
tempoUltimaRecepcao := tempoAtual;

/* Se recebemos um token enquanto estávamos em backoff para gerar um novo, cancelar backoff */
cancelar_timer(timerBackoff);

/* Se token carrega lista de IDs para reconfigurar, adiciona meuID se ainda não presente */
if (token.listaIDs.naoContem(meuID)) {
  token.listaIDs.adicionar(meuID);
}

/* Se token é reconstrutor e eu sou o originador e token voltou completo, finalizo reconfiguração */
if (token.originadorID == meuID && token.tipo == "TOKEN_CLAIM") {
  /* Originador recebeu seu token de volta: a lista representa as estações ativas */
  ReconstruirAnelAPartirLista(token.listaIDs);
  /* Agora token se torna token regular e recomeça circulação */
  token.tipo := "TOKEN_REGULAR";
  token.epoch := token.epoch + 1;
  /* Atualiza proximo conforme a nova lista (cada estação ajusta localmente no ReconstruirAnel) */
}

/* Entrar no estado TENHO_TOKEN e permitir transmissões por holdLimit */
estado := "TENHO_TOKEN";
iniciar_timer(timerHold, holdLimit);

/* Guardar token em variável local (se necessário) e enviar dado se houver */
/* Envia/Processa dados locais - aqui representado por procedure TransmitirSeHouver() */
TransmitirSeHouver();

/* Ao fim da retenção (tratado em on_timer(timerHold)), passaremos o token adiante */
/* Se quisermos atualizar o token com nova lista ou informação, fazemos antes de passar */
almacenar_token_local(token);
}
/* Quando o timer de retenção expira (passar token adiante) /
procedure on_timer_timerHold()
{
/
Obter token local armazenado /
tokenLocal := recuperar_token_local();
if (tokenLocal == NULL) {
/
Não tenho token em buffer -> nada a fazer */
estado := “ESPERANDO_TOKEN”;
iniciar_timer(timerTokenRetorno, timeoutToken);
return;
}
/* Passar o token ao próximo hop conhecido. Se proximo desconhecido, inicia reconfiguração */
if (proximo != NULL) {
  EnviarMensagem(proximo, mensagemTokenParaEnvio(tokenLocal));
  /* Após passar, entro em esperando token e inicio timer de retorno */
  estado := "ESPERANDO_TOKEN";
  iniciar_timer(timerTokenRetorno, timeoutToken);
} else {
  /* Se proximo desconhecido, manter token e entrar em RECONFIGURANDO: forçar circular e construir lista */
  estado := "RECONFIGURANDO";
  tokenLocal.tipo := "TOKEN_CLAIM";
  if (!tokenLocal.listaIDs.contem(meuID)) tokenLocal.listaIDs.adicionar(meuID);
  /* Passa token "claim" para o meio (se não houver next, broadcast) */
  EnviarBroadcast(mensagemTokenParaEnvio(tokenLocal));
  /* originador espera retornar para montar anel */
  iniciar_timer(timerTokenRetorno, timeoutToken);
}
}
/* Quando o timer de retorno do token expira (podemos ter perdido o token) /
procedure on_timer_timerTokenRetorno()
{
/
Não recebemos token no tempo esperado -> vamos tentar gerar token, porém com backoff aleatório /
estado := “ESPERANDO_TOKEN”;
backoff := RNG(0, backoffMax); /
ms aleatório */
iniciar_timer(timerBackoff, backoff);
}
/* Quando o backoff para geração de token expira (e ainda não chegaram tokens), geramos um token /
procedure on_timer_timerBackoff()
{
/
Se recebemos token em algum momento, timerBackoff teria sido cancelado; verificar /
if (ultimoTokenIDVisto != NULL && (tempoAgora() - tempoUltimaRecepcao) < timeoutToken) {
/
Recebemos token recentemente, aborta geração */
return;
}
/* Gerar token claim */
novoToken := EstruturaToken();
novoToken.originadorID := meuID;
novoToken.tokenID := concat(string(meuID), ":", string(tempoAgora())); /* único suficiente */
novoToken.epoch := 1;
novoToken.listaIDs := listaVazia();
novoToken.listaIDs.adicionar(meuID);
novoToken.tipo := "TOKEN_CLAIM";

/* Guardar como ultimoTokenIDVisto */
ultimoTokenIDVisto := novoToken.tokenID;
tempoUltimaRecepcao := tempoAgora();
estado := "TENHO_TOKEN";

/* Iniciar processo de circular token para reconstruir anel */
/* Se tenho próximo conhecido, uso; senão broadcast para rede e token vai recolher IDs */
if (proximo != NULL) {
  EnviarMensagem(proximo, mensagemTokenParaEnvio(novoToken));
} else {
  EnviarBroadcast(mensagemTokenParaEnvio(novoToken));
}

/* Começo a reconfigurar e espero retorno */
iniciar_timer(timerTokenRetorno, timeoutToken);
}
/* Ao receber qualquer TOKEN enquanto eu tenho token, resolver duplicatas /
procedure on_receive_TOKEN_enquantoTenho(token : EstruturaToken)
{
/
Se tokenID diferente do meu token local, aplico regra de resolução /
tokenLocal := recuperar_token_local();
if (tokenLocal == NULL) {
/
não tenho token em buffer; processa normalmente */
on_receive_TOKEN(token, remetenteID);
return;
}
if (token.tokenID == tokenLocal.tokenID) {
  /* mesmo token (por exemplo circulando), ignorar duplicação */
  return;
}

/* Regra de escolha: escolho token com maior tokenID lexicograficamente (ou outra regra definida) */
if (token.tokenID > tokenLocal.tokenID) {
  /* Abrir mão do token local: adotar o token recebido */
  armazenar_token_local(token);
  ultimoTokenIDVisto := token.tokenID;
  tempoUltimaRecepcao := tempoAgora();
  /* cancelar meu token e continuar com o token vencedor */
  cancelar_timer(timerHold);
  estado := "TENHO_TOKEN";
  iniciar_timer(timerHold, holdLimit); /* posso reter por holdLimit */
} else {
  /* descartar token recebido (envia mensagem de descartado se quiser) */
  /* opcional: enviar mensagem de TOKEN_REJECTED para originador do token recebido */
}
}
/* Função que monta os next hops a partir da lista de IDs do token (originador chama ao receber seu claim) /
procedure ReconstruirAnelAPartirLista(lista : lista<inteiro>)
{
/
Simples política: ordenar a lista (por ID) e estabelecer next como próximo na lista circular /
/
Observação: poderíamos manter a ordem de chegada para preservar localidade; aqui escolhemos ordenar para determinismo /
listaOrdenada := ordenar(lista); /
ordena em ordem crescente por ID /
tam := tamanho(listaOrdenada);
for i de 0 até tam-1 passo 1 do
{
idAtual := listaOrdenada[i];
idProx := listaOrdenada[ (i+1) mod tam ];
/
Enviar instrução para cada estação atualizar seu ‘proximo’ pode ser feito via token: /
/
Aqui assumimos que o token que voltou ao originador carrega listaOrdenada; originador inclui essa tabela no token e circula novamente para propagar /
}
/
Após originador ter definido a tabela, ele dissemina no próximo round via TOKEN_INFO ou via broadcast. */
}
/* Funções auxiliares para envio/recepção (implementação depende da camada física) /
procedure EnviarMensagem(destinoID : inteiro, msg : qualquer)
{
/
envia ponto-a-ponto /
}
procedure EnviarBroadcast(msg : qualquer)
{
/
envia broadcast na rede local /
}
procedure mensagemTokenParaEnvio(token : EstruturaToken) : qualquer
{
/
serializa token para enviar como mensagem */
return token;
}
/* Transmitir dados locais se a estação tem algo a enviar (exemplo simples) /
procedure TransmitirSeHouver()
{
/
Se houver buffer de dados, transmitir até que o holdLimit acabe.
Implementação: transmite e atualiza tempo de transmissão, mas aqui é uma abstração. */
}
/* Handlers genéricos de recebimento de mensagens /
procedure on_receive(msg : qualquer, remetenteID : inteiro)
{
if (msg.ehToken()) {
if (estado == “TENHO_TOKEN”) {
on_receive_TOKEN_enquantoTenho(msg, remetenteID);
} else {
on_receive_TOKEN(msg, remetenteID);
}
} else {
/
tratar mensagens de dados, POLL, POLL_ACK, etc. */
}
}
/* Inicialização da estação (startup) /
procedure InicializaEstacao(id : inteiro)
{
meuID := id;
proximo := NULL;
estado := “ESPERANDO_TOKEN”;
ultimoTokenIDVisto := NULL;
avgRetorno := NULL;
RecalculaTimeout();
/
iniciar timerTokenRetorno para tentar gerar token caso nunca venha (opcional) */
iniciar_timer(timerTokenRetorno, timeoutToken);
}
/* Implementações de timers (placeholders que devem ser adaptados ao ambiente) /
procedure iniciar_timer(timer : Timer, duracao_ms : inteiro)
{
/
agenda evento on_timer correspondente /
}
procedure cancelar_timer(timer : Timer)
{
/
cancela se estiver ativo */
}
/* Armazenamento e recuperação de token local (buffer) /
procedure almacenar_token_local(token : EstruturaToken)
{
/
guarda token para usar quando for passar adiante /
}
function recuperar_token_local() : EstruturaToken
{
/
retorna token guardado ou NULL */
return NULL;
}
/* Função main / loop de eventos /
procedure main()
{
/
configurar timers, callbacks de rede, etc. /
InicializaEstacao(receberIDConfiguracao());
/
loop de eventos: on_receive e on_timer são disparados pelo sistema */
}
}

Exercícios relacionados