Monte um programa em português estruturado que siga o protocolo CSMA-CD.

Passo 1

Você pediu: “Monte um programa em português estruturado que siga o protocolo CSMA-CD.”
O que exatamente o programa deve fazer (lista clara de pedidos):
  • Implementar (simular) o comportamento de estações que usam CSMA-CD para acessar um meio compartilhado.
  • Incluir detecção de portadora (carrier sense), detecção de colisão (collision detect), envio de jam, e algoritmo de backoff exponencial binário.
  • Ser escrito em Português estruturado (pseudocódigo / Portugol), com nomes e comentários em Português.
  • Ser suficientemente claro para eu entender e adaptar para rodar numa implementação real ou simulação.
Informações fornecidas pelo enunciado:
  • Apenas o pedido para montar o programa; não há mais restrições (por ex. número de estações, granularidade temporal, persistência). Então farei escolhas razoáveis e documentadas nas próximas etapas.

Passo 2

Breve explicação do protocolo CSMA-CD (o que preciso saber para entender o programa):
  • Carrier Sense (CS): antes de transmitir, a estação “ouve” o meio; se o meio estiver ocupado, ela espera; se estiver ocioso, ela transmite. No modo 1-persistent, assim que detecta ocioso começa a transmitir imediatamente.
  • Multiple Access (MA): várias estações compartilham o mesmo meio.
  • Collision Detect (CD): durante a transmissão a estação continua monitorando o meio. Se perceber sinais que indicam que outra estação está transmitindo ao mesmo tempo (colisão), ela interrompe a transmissão e executa procedimento de recuperação.
  • Após detectar colisão: a estação envia um sinal de “jam” para garantir que todas as estações saibam da colisão, para de transmitir, e entra em procedimento de backoff.
  • Backoff exponencial binário: após a i-ésima colisão para um mesmo quadro, a estação escolhe aleatoriamente um inteiro r uniformemente em {0, 1, …, 2^k - 1} onde k = min(i, Kmax) (em Ethernet Kmax = 10 normalmente). O tempo de espera é r * slot_time. Se exceder número máximo de tentativas (por ex. 16), o quadro é descartado.
  • Parâmetros importantes: slot_time (tempo mínimo para detecção de colisão, p.ex. 512 bit-times em Ethernet), jam_time, tempo de propagação, duração do quadro.

Passo 3

Decisões de modelagem e suposições para o programa (explico porque escolhi):
  • Vou escrever um simulador por tempo discreto (ticks), com unidade de tempo igual a um “slot” pequeno (p.ex. 1 unidade = tempo suficientemente pequeno para representar propagação). Isso simplifica implementação e entendimento.
  • Canal terá estados: ocioso, ocupado (com 1 transmissor), colisão (quando >1 transmissor). O canal mantém lista de transmissões em andamento.
  • Cada estação é um processo com estados: ocioso, transmitindo, jam, backoff, esperando. Cada estação tem fila de quadros (frames).
  • Usarei 1-persistent CSMA: se o canal está ocioso a estação começa a transmitir imediatamente. Essa é a versão clássica da Ethernet.
  • Parametrizarei: NUM_ESTACOES, DURAÇÃO_FRAME (em ticks), SLOT_TIME (em ticks), JAM_TIME (em ticks), MAX_ATTEMPTS. Esses parâmetros facilitam testes.
  • O simulador gera logs para entender o que ocorreu (quando começa transmissão, colisão, backoff, sucesso, descarte).

Passo 4

Definição das variáveis e constantes principais (explico o significado de cada uma):
  • Constantes:
    • NUM_ESTACOES: número de estações na rede.
    • DURAÇÃO_FRAME: tempo necessário para transmitir um quadro (em ticks).
    • SLOT_TIME: unidade de backoff (em ticks). Representa o “slot time” usado no backoff exponencial.
    • JAM_TIME: duração do jam signal (em ticks).
    • MAX_ATTEMPTS: número máximo de tentativas antes de descartar o quadro (p.ex. 16).
    • TEMPO_TOTAL: tempo total de simulação (em ticks).
  • Estruturas:
    • Canal:
      • transmitindo: lista de ids de estações que estão transmitindo neste tick.
      • estado: ‘OCIOSO’ | ‘OCUPADO’ | ‘COLISAO’ (derivado de transmitindo).
    • Estacao:
      • id: identificador.
      • fila_frames: fila (lista) de frames pendentes.
      • estado: ‘OCIOSA’ | ‘TRANSMITINDO’ | ‘JAM’ | ‘BACKOFF’ | ‘ESPERANDO’.
      • tempo_restante: tempo restante na ação atual (ticks).
      • tentativa_corrente: contador de tentativas para o frame atual.
      • inicio_transmissao: tick em que começou a transmitir (para diagnosticar).
  • Funções auxiliares:
    • rand_int(a,b): retorna inteiro aleatório entre a e b inclusive.
    • escolher_backoff(tentativa): retorna r * SLOT_TIME com r uniformemente entre 0 e 2^k - 1, k = min(tentativa, 10).

Passo 5

Descrição das operações principais (cada uma será traduzida no programa):
  • Ouvindo o canal (carrier sense): a estacao verifica canal.transmitindo; se vazio, canal é ocioso. No instante que detecta ocioso começa a transmitir imediatamente (1-persistent).
  • Início da transmissão: a estação entra em estado TRANSMITINDO, tempo_restante = DURAÇÃO_FRAME, adiciona seu id em canal.transmitindo.
  • Enquanto transmitindo: a cada tick, depois de atualizar transmissões, checa se canal.transmitindo.size > 1. Se sim e se ainda não detectou colisão, então detectou colisão -> entrar em jam.
  • Jam: toda estação que detectou colisão executa jam durante JAM_TIME (ainda considera o canal em colisão). Após jam, retira-se do canal e calcula backoff. A transmissão é abortada.
  • Backoff: tentativa_corrente += 1; se tentativa_corrente > MAX_ATTEMPTS então descarta frame; caso contrário calcula espera = escolher_backoff(tentativa_corrente) e fica em estado BACKOFF com tempo_restante = espera. Ao final do backoff, vai para estado ESPERANDO, que é um pequeno período de escuta; na nossa modelagem, assim que sair do backoff, faz carrier sense de novo (se o canal estiver ocioso transmite; se ocupado, espera até ocioso e transmitirá imediatamente).
  • Sucesso: se uma estação termina sua DURAÇÃO_FRAME e canal.transmitindo.size == 1 (ou seja, não houve colisão), o frame é entregue com sucesso, tenta resetar tentativa_corrente e remove frame da fila.

Passo 6

Pseudocódigo do programa em Português estruturado. Comentários explicam passo a passo como o protocolo é implementado.
(este bloco é o código que você pode copiar; está em Portugol-estruturado)

Resposta

programa CSMA_CD_Simulador
// Simulador estruturado em Português do protocolo CSMA-CD (1-persistent)
// Parâmetros e configurações
const NUM_ESTACOES <- 5
const DURAÇÃO_FRAME <- 200 // ticks necessários para transmitir um quadro
const SLOT_TIME <- 51 // unidade de backoff (em ticks)
const JAM_TIME <- 48 // duração do jam (em ticks)
const MAX_ATTEMPTS <- 16 // máximo de tentativas antes de descartar
const TEMPO_TOTAL <- 5000 // duração total da simulação em ticks
// Estruturas de dados
registro Canal
transmitindo : lista de inteiro // ids das estações transmitindo no tick atual
fimregistro
registro Estacao
id : inteiro
fila_frames : fila de inteiro // cada elemento representa um frame (pode ser apenas um contador)
estado : cadeia // ‘OCIOSA’|‘TRANSMITINDO’|‘JAM’|‘BACKOFF’|‘ESPERANDO’
tempo_restante : inteiro // ticks restantes na ação atual
tentativa_corrente : inteiro // número de colisões ocorridas para o frame atual
inicio_transmissao : inteiro // tick em que começou a transmissão (para logs)
fimregistro
// Função auxiliar: inteiro aleatório entre a e b inclusive
funcao rand_int(a : inteiro, b : inteiro) : inteiro
// use o gerador da linguagem alvo; aqui é conceitual
retorne (a + (inteiro)(aleatorio() * (b - a + 1)))
fimfuncao
// Função de backoff exponencial binário
funcao escolher_backoff(tentativa : inteiro) : inteiro
k : inteiro
r : inteiro
k <- tentativa
se k > 10 entao
k <- 10
fimse
// r uniformemente em {0, …, 2^k - 1}
r <- rand_int(0, (2 ^ k) - 1)
retorne r * SLOT_TIME
fimfuncao
// Inicialização
var canal : Canal
var estacoes : vetor [1…NUM_ESTACOES] de Estacao
var tick : inteiro
procedimento inicializar_simulador()
canal.transmitindo <- lista vazia
para i de 1 até NUM_ESTACOES faca
estacoes[i].id <- i
estacoes[i].fila_frames <- fila vazia
// Para testar, colocamos 1 frame inicial em cada estação (ajuste conforme desejado)
enfileirar(estacoes[i].fila_frames, 1)
estacoes[i].estado <- ‘OCIOSA’
estacoes[i].tempo_restante <- 0
estacoes[i].tentativa_corrente <- 0
estacoes[i].inicio_transmissao <- -1
fimpara
fimprocedimento
// Rotina executada a cada tick para atualizar canal e estações
procedimento simular_tick(tick_atual : inteiro)
// 1) Resetar a lista de transmissões do canal para recomputar no tick atual
canal.transmitindo <- lista vazia
// 2) Primeiro, processar decisões locais das estações (início de transmissão, etc.)
para i de 1 até NUM_ESTACOES faca
    est := estacoes[i]
    se est.estado = 'OCIOSA' entao
        // Se tem frame para enviar, faz carrier sense (escuta)
        se nao fila_vazia(est.fila_frames) entao
            // Carrier sense: se o canal estava ocioso no tick anterior, começamos a transmitir.
            // Aqui usamos a lista canal.transmitindo atual (ainda vazia), portanto iniciamos transmissão.
            // Em modelo mais detalhado verificar propagação; aqui adotamos detecção imediata.
            est.estado <- 'TRANSMITINDO'
            est.tempo_restante <- DURAÇÃO_FRAME
            est.inicio_transmissao <- tick_atual
            // registra transmissão no canal (será contado abaixo)
            // não remove o frame ainda; só remove em caso de sucesso
        fimse
    fimse

    se est.estado = 'ESPERANDO' entao
        // Estado de espera breve depois de backoff: vamos tentar ouvir e possivelmente transmitir
        se canal.transmitindo = lista vazia entao
            // canal ocioso -> inicia transmissão (1-persistent)
            se nao fila_vazia(est.fila_frames) entao
                est.estado <- 'TRANSMITINDO'
                est.tempo_restante <- DURAÇÃO_FRAME
                est.inicio_transmissao <- tick_atual
            senao
                est.estado <- 'OCIOSA'
            fimse
        fimse
    fimse

    // Estações em BACKOFF não tomam ação até seu tempo acabar (tempo_restante controla)
fimpara

// 3) Agora, compor o canal com quem está transmitindo neste tick (depois das decisões de início)
para i de 1 até NUM_ESTACOES faca
    se estacoes[i].estado = 'TRANSMITINDO' entao
        adicionar_ao_fim(canal.transmitindo, estacoes[i].id)
    fimse
fimpara

// 4) Detectar colisão: se mais de uma estação estiver transmitindo no mesmo tick
se comprimento(canal.transmitindo) > 1 entao
    // Marca colisão no canal; cada estacao que estava transmitindo deve reagir
    // Entram em estado JAM (enviam jam signal) e reiniciam contadores de tempo
    para cada id em canal.transmitindo faca
        est <- estacoes[id]
        // Se ainda está transmitindo (não entrou já em JAM neste tick)
        se est.estado = 'TRANSMITINDO' entao
            // detectou colisão
            est.estado <- 'JAM'
            est.tempo_restante <- JAM_TIME
            // A transmissão aborta; tentativa será incrementada após o jam
            // (não removemos o frame da fila ainda, será tentado novamente após backoff)
        fimse
    fimpara
fimse

// 5) Para cada estação, avançar tempo das ações em curso e reagir ao término
para i de 1 até NUM_ESTACOES faca
    est := estacoes[i]

    se est.estado = 'TRANSMITINDO' entao
        // Enquanto transmite, pode ser que a colisão tenha ocorrido; se não, decrementa tempo
        est.tempo_restante <- est.tempo_restante - 1
        // Se terminou transmissão sem colisão: sucesso (garantimos que canal.transmitindo.size == 1)
        se est.tempo_restante <= 0 entao
            // Verificar se houve colisão neste intervalo:
            // se canal.transmitindo contém apenas esta estacao, então sucesso
            se comprimento(canal.transmitindo) = 1 entao
                // Transmissão bem-sucedida
                desenfileirar(est.fila_frames) // quadro transmitido com sucesso
                est.tentativa_corrente <- 0
                est.estado <- 'OCIOSA'
                est.tempo_restante <- 0
                // Log de sucesso (substitua por impressão na implementação)
                // ex: imprimir("tick", tick_atual, "Estacao", est.id, "transmissao SUCESSO")
            senao
                // Se chegou aqui e canal tinha >1, então colisão já foi tratada no passo 4
                // Apenas asseguramos que esta estação entrará em JAM no tratamento de colisão
            fimse
        fimse
    fimse

    se est.estado = 'JAM' entao
        est.tempo_restante <- est.tempo_restante - 1
        se est.tempo_restante <= 0 entao
            // Jam terminou: abandonar a transmissão atual, incrementar tentativa e calcular backoff
            est.tentativa_corrente <- est.tentativa_corrente + 1
            se est.tentativa_corrente > MAX_ATTEMPTS entao
                // Descartar quadro
                desenfileirar(est.fila_frames)
                est.estado <- 'OCIOSA'
                est.tempo_restante <- 0
                est.tentativa_corrente <- 0
                // Log de descarte
                // ex: imprimir("tick", tick_atual, "Estacao", est.id, "DESCARTOU quadro apos tentativas")
            senao
                // Calcular backoff
                espera <- escolher_backoff(est.tentativa_corrente)
                se espera = 0 entao
                    // Se espera zero, vamos imediatamente para estado ESPERANDO para tentar de novo
                    est.estado <- 'ESPERANDO'
                    est.tempo_restante <- 0
                senao
                    est.estado <- 'BACKOFF'
                    est.tempo_restante <- espera
                fimse
            fimse
        fimse
    fimse

    se est.estado = 'BACKOFF' entao
        est.tempo_restante <- est.tempo_restante - 1
        se est.tempo_restante <= 0 entao
            // Após backoff, tenta novamente; estado passa para ESPERANDO (para fazer carrier sense)
            est.estado <- 'ESPERANDO'
            est.tempo_restante <- 0
        fimse
    fimse
fimpara

// 6) Fim do tick: (no modelo real poderíamos atualizar logs do canal)
fimprocedimento
// Rotina principal
procedimento main()
inicializar_simulador()
para tick de 0 até TEMPO_TOTAL faca
simular_tick(tick)
// (Opcional) imprimir estado resumido a cada N ticks para inspeção
fimpara
// (Opcional) imprimir estatísticas finais: frames entregues, descartados, colisões totais, etc.
fimprocedimento
// Iniciar simulação
main()
// Fim do programa

Exercícios relacionados