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):
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).
- Canal:
- 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)
(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
// 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 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
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
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
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
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
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
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
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()
main()
// Fim do programa