Inversión de prioridad

En informática , la inversión de prioridad es un escenario de programación en el que una tarea de alta prioridad es reemplazada indirectamente por una tarea de menor prioridad, invirtiendo efectivamente las prioridades asignadas a las tareas. Esto viola el modelo de prioridad según el cual las tareas de alta prioridad solo pueden evitar que se ejecuten mediante tareas de mayor prioridad. La inversión ocurre cuando hay una contención de recursos con una tarea de baja prioridad que luego es reemplazada por una tarea de prioridad media.

Consideremos dos tareas H y L , de alta y baja prioridad respectivamente, cualquiera de las cuales puede adquirir el uso exclusivo de un recurso compartido R . Si H intenta adquirir R después de que L lo haya adquirido, entonces H queda bloqueada hasta que L ceda el recurso. Compartir un recurso de uso exclusivo ( R en este caso) en un sistema bien diseñado normalmente implica que L ceda R rápidamente para que H (una tarea de mayor prioridad) no permanezca bloqueada durante períodos de tiempo excesivos. Sin embargo, a pesar del buen diseño, es posible que una tercera tarea M de prioridad media se vuelva ejecutable durante el uso de R por parte de L . En este punto, M al ser mayor en prioridad que L , preempta a L (ya que M no depende de R ), haciendo que L no pueda ceder R rápidamente, lo que a su vez hace que H —el proceso de mayor prioridad— no pueda ejecutarse (es decir, H sufre un bloqueo inesperado causado indirectamente por tareas de menor prioridad como M ).

En algunos casos, la inversión de prioridad puede ocurrir sin causar daño inmediato: la ejecución retrasada de la tarea de alta prioridad pasa desapercibida y, finalmente, la tarea de baja prioridad libera el recurso compartido. Sin embargo, también hay muchas situaciones en las que la inversión de prioridad puede causar problemas graves. Si la tarea de alta prioridad se queda sin recursos, puede provocar un mal funcionamiento del sistema o la activación de medidas correctivas predefinidas, como un temporizador de vigilancia que restablezca todo el sistema. El problema experimentado por el módulo de aterrizaje Mars Pathfinder en 1997 ^{[1] [2]} es un ejemplo clásico de problemas causados ​​por la inversión de prioridad en sistemas de tiempo real .

La inversión de prioridades también puede reducir el rendimiento percibido del sistema. Las tareas de baja prioridad suelen tener una prioridad baja porque no es importante que finalicen rápidamente (por ejemplo, pueden ser un trabajo por lotes u otra actividad no interactiva). De manera similar, una tarea de alta prioridad tiene una prioridad alta porque es más probable que esté sujeta a restricciones de tiempo estrictas: puede proporcionar datos a un usuario interactivo o actuar sujeto a garantías de respuesta en tiempo real. Debido a que la inversión de prioridades da como resultado que la ejecución de una tarea de menor prioridad bloquee la tarea de alta prioridad, puede conducir a una menor capacidad de respuesta del sistema o incluso a la violación de las garantías de tiempo de respuesta.

Un problema similar, llamado intercambio de fechas límite , puede ocurrir dentro de la programación de fecha límite más temprana (EDF).

La existencia de este problema se conoce desde los años 70. Lampson y Redell ^[3] publicaron uno de los primeros artículos en señalar el problema de la inversión de prioridad. Sistemas como el núcleo UNIX ya abordaban el problema con la primitiva splx(). No existe un método infalible para predecir la situación. Sin embargo, existen muchas soluciones, de las cuales las más comunes son:

Deshabilitar todas las interrupciones para proteger secciones críticas

Cuando se deshabilitan las interrupciones para evitar la inversión de prioridades, solo hay dos prioridades: preemptible e interrupciones deshabilitadas. Sin una tercera prioridad, la inversión es imposible. Dado que solo hay una pieza de datos de bloqueo (el bit de habilitación de interrupciones), es imposible ordenar incorrectamente el bloqueo y, por lo tanto, no pueden ocurrir bloqueos. Dado que las regiones críticas siempre se ejecutan hasta completarse, no se producen bloqueos. Tenga en cuenta que esto solo funciona si se deshabilitan todas las interrupciones. Si solo se deshabilita la interrupción de un dispositivo de hardware en particular, la inversión de prioridad se reintroduce mediante la priorización de interrupciones del hardware. En las primeras versiones de UNIX, una serie de primitivas llamadas splx(0) ... splx(7) deshabilitaban todas las interrupciones hasta la prioridad dada. Al elegir correctamente la prioridad más alta de cualquier interrupción que alguna vez ingresara en la sección crítica, el problema de inversión de prioridad podría resolverse sin bloquear todas las interrupciones. Los techos se asignaron en orden monótono de velocidad , es decir, los dispositivos más lentos tenían prioridades más bajas.

En los sistemas con varias CPU, se utiliza una variación sencilla, el "bloqueo con un único indicador compartido". Este esquema proporciona un único indicador en la memoria compartida que utilizan todas las CPU para bloquear todas las secciones críticas entre procesadores con una espera activa . Las comunicaciones entre procesadores son caras y lentas en la mayoría de los sistemas con varias CPU. Por lo tanto, la mayoría de estos sistemas están diseñados para minimizar los recursos compartidos. Como resultado, este esquema funciona realmente bien en muchos sistemas prácticos. Estos métodos se utilizan ampliamente en sistemas integrados simples , donde son apreciados por su fiabilidad, simplicidad y bajo uso de recursos. Estos esquemas también requieren una programación inteligente para mantener las secciones críticas muy breves. Muchos ingenieros de software los consideran poco prácticos en ordenadores de uso general. ^{[ cita requerida ]}

Protocolo de techo de prioridad

Con el protocolo de techo de prioridad , el proceso mutex compartido (que ejecuta el código del sistema operativo) tiene una prioridad característica (alta) propia, que se asigna a la tarea de bloquear el mutex. Esto funciona bien, siempre que las otras tareas de alta prioridad que intentan acceder al mutex no tengan una prioridad mayor que la prioridad del techo.

Herencia prioritaria

Según la política de herencia de prioridad , siempre que una tarea de alta prioridad tiene que esperar algún recurso compartido con una tarea de baja prioridad en ejecución, a la tarea de baja prioridad se le asigna temporalmente la prioridad de la tarea con mayor prioridad en espera durante el tiempo que utilice el recurso compartido, lo que evita que las tareas de prioridad media se apropien de la tarea de baja prioridad (originalmente) y, por lo tanto, también afecten a la tarea de alta prioridad que está en espera. Una vez que se libera el recurso, la tarea de baja prioridad continúa con su nivel de prioridad original.

Impulso aleatorio

Las tareas listas que tienen bloqueos reciben una prioridad aleatoria hasta que salen de la sección crítica. Esta solución se utiliza en Microsoft Windows . ^[4]

Evitar bloqueos

Debido a que la inversión de prioridad implica que una tarea de baja prioridad bloquea una tarea de alta prioridad, una forma de evitar la inversión de prioridad es evitar el bloqueo, por ejemplo, utilizando algoritmos no bloqueantes como lectura-copia-actualización .

• Agradable (Unix)
• Sincronización sin bloqueo
• Multitarea preventiva

• Descripción de FOLDOC
• Citas de CiteSeer
• Documento sobre la herencia de prioridades del IEEE de Sha, Rajkumar y Lehoczky
• Introducción a la inversión de prioridades por Michael Barr