Please enable JavaScript.
Coggle requires JavaScript to display documents.
Eliminando Receive Livelock en un Kernel controlado por Interrupciones -…
Eliminando Receive Livelock
en un Kernel controlado por Interrupciones
Aplicaciones que motivaron
la investigación del paper
Hay varias aplicaciones que sufren a causa del Livelock, como las siguientes
Host-based routing
Passive network monitoring
Network File Service
La mayor parte de los SO utilizan interrupts para planificar el rendimiento de las tareas relacionadas con I/O. Esto ayuda a evitar el
Polling
, que puede llegar a ser muy caro y puede aumentar la latencia de respuesta.
Los SO modernos utilizan los mismos mecanismos de interrupción para network y dipositivos I/O. Además muchas aplicaciones multimedia no son flow controlled. Estos dos factores pueden hacer que ocurra un colapso por congestión creando un overload temporal.
Requisitos para planificar
tareas de red
Rendimiento
Este es el ritmo en el que el sistema envía los paquetes a los clientes finales. Estos pueden ser aplicaciones o el host.
Latencia y Jitter
Aplicaciones como los sistemas distribuidos y multimedia dependen en comunicación de baja latencia y bajo jitter.
Fair Allocation
y Recursos
Si un host está overloaded con el network, debe ser capaz de seguir procesando otras tareas. El subsistema de planificación debe ser capaz de manejar los recursos para esto.
Estabilidad
Un host que no se comporte correctamente cuando overloaded puede afectar la estabilidad de otros sistemas.
Planificación por interrupciones
y consecuencias
Los mecanismos de planificación afectan el rendimiento y la latencia de un sistema en overload. En un sistema de interrupciones, las interrupciones deben ser consideradas parte del sistema de planificación.
Receive Livelock
En un sistema de interrupciones, receiver interrupts deben tener la mayor prioridad. Si los paquetes llegan muy rápido, el sistema utiliza todos los recursos en procesar los receiver interrupts y no le quedan recursos para los paquetes entrantes de aplicaciones.
Latencia bajo
overload
Los sistemas de interrupción usualmente son una forma de bajar la latencia de un sistema, pero en ocasiones pueden aumentar esta. Si un grupo paquetes llega muy rápido, el sistema primero procesará de forma básica
todo
el grupo antes de procesar de manera más detenida el primer paquete. A causa de esto el procesamiento del primer paquete va a tener que esperar a que primero se procese todo el grupo haciendo que la latencia de procesamiento del primer paquete sea casi igual al tiempo que toma en procesar todo el grupo de paquetes.
Starvation y transmisión
bajo overload
La transmisión de paquetes tiene una prioridad más baja que la recepción de paquetes, esto evita que haya perdida de paquetes. Pero cuando el sistema está bajo overload esto causa que se caiga el rendimiento y en ocasiones que la transmisión de paquetes se detenga por completo.
Evitar livelock con una
mejor planificación
Limitación de la tasa de
llegada de interrupciones
El sistema chequea si el procesamiento de interrupciones está tomando más que los recursos disponibles, en caso que si, entonces limita la entrada de nuevos paquetes. De esta forma se puede evitar el livelock.
Uso de Polling
La limitación de la llegada de paquetes ayuda a la sobre-saturación, pero puede no ayudar a que haya progreso. Para ayudar a esto se emplea un sistema híbrido de polling e interrupts en donde el sistema solo hace polling cuando triggered por un interrupt, y los interrupts solo ocurren cuando el polling está suspendido.
Evitar Prioridades
Livelocks ocurren porque el procesamiento de los interrupts tiene prioridad sobre todos los otros procesamientos. Esto se puede evitar haciendo que el procesamiento a nivel más detenido de paquetes no se pueda dejaer en stand-by por prioridad de procesamiento de otro paquete.
Livelock en routers
basados en BSD
¿Porqué ocurren los Livelocks
en el modelo BSD?
En este modelo la capa IP tiene un nivel de prioridad más bajo que la capa de driver de dispositivos. Cuando la entrada sobrepasa el límite en el que el driver de dispositivos es capaz de sacar nuevos paquetes de la interfaz y añadirlos a la cola de entrada del IP, el código del IP se queda estancado y no corre. A causa de esto el IP no puede remover paquetes de la cola de entrada, la cual se llena y no puede recibir más paquetes.
Solucionando el problema
de Livelock
Este problema se solucionó trabajando en el hilo de kernel y eliminando la cola de entrada del IP, y todos los procesos de software relacionados con esta cola.
Garantizar el progreso de
los procesos a nivel de usuario
El polling y estado de colas garantiza que todas las fases de procesamiento de paquetes sigan funcionando bajo overload. Sin embargo, procesos a nivel de usuario pueden afectar los ciclos del CPU.
Rendimiento de los protocolos
de transporte del sistema
El mecanismo de no utilizar la cola de IP para los paquetes pocedentes del driver de dispositivos mejora el rendimiento de la taza de transporte. Polling no debería afectar el rendimiento, ya que usualmente solo se ejecuta durante overload.
Sistema de colas + Polling + Ciclos del CPU = Mejor progreso del sistema bajo overload
Mediciones utilizando trazas
de ejecución del Kernel
Para probar que tan bien funcionaban distintas soluciones, se analizó la ejecución del kernel para ver como este estaba distribuyendo el tiempo y así medir la latencia de diferentes opciones. Esto permite ver como funciona el sistema bajo distintas cantidades de procesamiento de paquetes y permite determinar la eficiencia de las modificaciones implementadas.
Evitar Livelock en
un monitor de red
Problema
Aplicaciones LAN usualmente requieren que el host se ponga en "modo promiscuo", haciendo que se reciban todos los paquetes en la LAN, no solo los que van dirigidos al host. Usualmente con pocos paquetes grandes esto no es un problema, pero si hay muchos paquetes pequeños, el host no es capaz de seguir el ritmo.
Cuando ocurre este overload, el kernel lo que hace es descartar paquetes porque hay demasiados y es imposible procesarlos todos.
Solución
El kernel de polling se modificó para que implementara un sistema de cola con capacidad para 32 paquetes. Cada vez que la cola tiene espacio para menos de 8 paquetes adicionales, el Polling se desactiva. Tambien se implementó un time-out para reactivar el Polling.
Los sistemas basados en interrupciones no funcona bien bajo overload, esto hace que ocurra el
Receive Livelock
en donde el sistema no está totalmente bloqueado, pero no hace progreso en ninguna tarea.