Resumo

  • O livelock de recepção surge quando interrupções consomem o tempo que protocolo, transmissão ou aplicação precisam para concluir o pacote; o processador trabalha, mas a vazão útil pode chegar a zero.
  • Mogul e Ramakrishnan combinaram interrupção de despertar, polling em rodízio, cota por chamada, descarte antecipado, retorno de filas posteriores e limite de ciclos. Polling sem cota também fracassou.
  • Os números vieram de um DECstation monoprocessador lento e Ethernet de 10 Mbit/s. Cinco a dez pacotes por turno eram um resultado local, não uma configuração universal.

A máquina estava ocupada e o serviço sumia

Uma interrupção deixa um evento físico passar à frente do trabalho comum. Com chegadas esparsas, isso reduz a latência. Sob uma enxurrada, a prioridade pode impedir que qualquer etapa posterior finalize o que a própria interface aceitou.

No modelo derivado do 4.2BSD, o driver retirava o pacote da interface e o colocava numa fila IP. O protocolo rodava depois e com prioridade menor, podendo ser interrompido pela próxima chegada. Quando a fila enchia, o sistema continuava gastando ciclos em pacotes descartados antes da aplicação ou da interface de saída.

Não era deadlock: ao cair a entrada, o host se recuperava. Durante a sobrecarga, porém, uso de CPU e interrupções podiam parecer vigorosos enquanto a entrega era nula. Por isso o artigo definiu vazão no consumidor final, não no contador de recepção.

A prioridade era um escalonador oculto

O escalonador normal quase não participava. Níveis fixos de interrupção davam autoridade absoluta à recepção e deixavam protocolo, conclusão de transmissão, manutenção e processos de usuário esperando.

Agrupar interrupções diminuía o custo e adiava o ponto de colapso, mas não criava uma vez para a saída. Admitir mais rápido ainda não era concluir.

A interrupção acorda; o polling distribui

O kernel alterado manteve interrupções em baixa carga. Em alta carga, o handler apenas registrava a necessidade de serviço, acordava uma thread de polling e deixava novas interrupções mascaradas.

A thread visitava fontes de recepção e transmissão em rodízio. Cada callback recebia uma cota. Ao esvaziar o trabalho, as interrupções eram reativadas. Um pacote aceito seguia o máximo possível rumo à conclusão, evitando outra fronteira de prioridade.

O desenho era híbrido: polling puro desperdiça CPU e eleva latência no silêncio; interrupção pura pode monopolizar a saturação. A primeira interrupção detectava o imprevisível, e o polling limitado administrava o fluxo contínuo.

Sem cota, o polling parou de repartir

Quando o callback de entrada ficou sem cota, sempre havia outro pacote. Ele nunca devolvia o controle, a conclusão de transmissão não rodava, descritores não eram liberados e a fila de saída enchia. A vazão voltou a quase zero.

O monopólio apenas mudara de lugar. A cota criava a vez da saída. Entre cinco e dez pacotes funcionou bem naquele hardware; lotes maiores amortizavam custo, mas aumentavam latência e risco de fome. Outro processador ou interface exigiria outro valor.

Descartar cedo e ouvir a etapa seguinte

Se nem toda oferta pode ser concluída, descartar na interface evita investir driver, protocolo e filas num pacote condenado. O retorno da fila posterior diz quando a entrada deve parar.

Com screend, a entrada era inibida a 75% da fila, retomada a 25%, com temporizador de aproximadamente um milissegundo. Os autores chamaram esses valores de arbitrários. O princípio transferível era o circuito de evidência: fila posterior sem progresso deve frear admissão.

Outro mecanismo media ciclos de rede em janelas de dez milissegundos. Ao atingir a parcela definida, a entrada parava para deixar aplicações e manutenção correrem. A interação local melhorava; a remota ainda sofria com perdas. Reservar CPU não aumenta capacidade.

O recibo inclui o laboratório

O roteador era um DECstation 3000/300 com Digital UNIX V3.2, escolhido como o Alpha mais lento disponível. Ligava duas Ethernets ociosas de 10 Mbit/s. Cada ensaio enviava 10.000 datagramas UDP de quatro bytes; a taxa era uma média, pois a fonte não tinha ritmo perfeito.

No kernel original com screend, a degradação começou acima de cerca de 2.000 pacotes/s e o livelock completo apareceu perto de 6.000. Sem screend, o pico foi cerca de 4.700. O relatório recusou extrapolar para LANs e CPUs mais rápidas, não testou SMP verdadeiro e não decidiu quais pacotes deveriam sobreviver.

A documentação atual de NAPI no Linux ainda mostra uma forma semelhante: a interrupção agenda polling, IRQs ficam mascaradas e um orçamento limita o ciclo. Isso é uma comparação, não prova de que toda sobrecarga moderna seja livelock.

O perfil do Google Research situa Mogul na DEC/Compaq WRL, HP Labs e infraestrutura de rede do Google. O trabalho permanece conjunto com Ramakrishnan. Sua regra histórica é simples: ocupação na entrada não pode ser vendida como desempenho se nada chega ao destino.

Fontes