stringtranslate.com

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 de 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.

Formulación

Considere 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 bloqueado hasta que L renuncie al recurso. Compartir un recurso de uso exclusivo ( R en este caso) en un sistema bien diseñado normalmente implica que L renuncie a R rápidamente para que H (una tarea de mayor prioridad) no permanezca bloqueado durante períodos de tiempo excesivos. Sin embargo, a pesar de un 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 tiene mayor prioridad que L , se adelanta a L (ya que M no depende de R ), lo que hace que L no pueda renunciar a R rápidamente, lo que a su vez provoca que H , el proceso de mayor prioridad, no pueda ejecutar (es decir, H sufre un bloqueo inesperado causado indirectamente por tareas de menor prioridad como M ).

Consecuencias

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, podría provocar un mal funcionamiento del sistema o la activación de medidas correctivas predefinidas, como un temporizador de vigilancia que reinicie 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 generalmente tienen baja prioridad porque no es importante que terminen 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 ser proporcionar datos a un usuario interactivo o actuar sujeto a garantías de respuesta en tiempo real. Debido a que la inversión de prioridad da como resultado la ejecución de una tarea de menor prioridad que bloquea la tarea de alta prioridad, puede provocar una reducción de la capacidad de respuesta del sistema o incluso 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 primera programación de fechas límite más temprana (EDF).

Soluciones

La existencia de este problema se conoce desde los años 1970. 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 kernel UNIX ya estaban abordando 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 utiliza la desactivación de interrupciones para evitar la inversión de prioridad, solo hay dos prioridades: preferible e interrupciones desactivadas. Sin una tercera prioridad, la inversión es imposible. Dado que solo hay un dato de bloqueo (el bit de habilitación de interrupción), es imposible realizar un bloqueo incorrecto y, por lo tanto, no pueden ocurrir interbloqueos. Dado que las regiones críticas siempre se ejecutan hasta su finalización, no se producen bloqueos. Tenga en cuenta que esto sólo funciona si todas las interrupciones están desactivadas. 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 las interrupciones del hardware. En las primeras versiones de UNIX, una serie de primitivas denominadas splx(0) ... splx(7) desactivaban todas las interrupciones hasta la prioridad dada. Al elegir adecuadamente la prioridad más alta de cualquier interrupción que alguna vez haya ingresado a la sección crítica, el problema de inversión de prioridad podría resolverse sin bloquear todas las interrupciones. Los límites máximos se asignaron en orden monótono , es decir, los dispositivos más lentos tenían prioridades más bajas.
En sistemas con múltiples CPU, se utiliza una variación simple: "bloqueo de bandera compartida única". Este esquema proporciona un indicador único en la memoria compartida que utilizan todas las CPU para bloquear todas las secciones críticas entre procesadores con una espera de ocupado . Las comunicaciones entre procesadores son costosas y lentas en la mayoría de los sistemas con múltiples CPU. Por lo tanto, la mayoría de estos sistemas están diseñados para minimizar los recursos compartidos. Como resultado, este esquema funciona bien en muchos sistemas prácticos. Estos métodos se utilizan ampliamente en sistemas integrados simples , donde son apreciados por su confiabilidad, 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 computadoras de uso general. [ cita necesaria ]
Protocolo de techo de prioridad
Con el protocolo de límite 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 superior a la prioridad máxima.
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 de mayor prioridad en espera mientras dure su propia tarea. uso del recurso compartido, evitando así que las tareas de prioridad media se adelanten a la tarea (originalmente) de baja prioridad y, por lo tanto, afectando también a la tarea de alta prioridad en espera. Una vez que se libera el recurso, la tarea de baja prioridad continúa en su nivel de prioridad original.
Impulso aleatorio
Las tareas listas que mantienen cerraduras aumentan aleatoriamente su prioridad hasta que salen de la sección crítica. Esta solución se utiliza en Microsoft Windows . [4]
evitar bloquear
Debido a que la inversión de prioridad implica que una tarea de baja prioridad bloquee una tarea de alta prioridad, una forma de evitar la inversión de prioridad es evitar el bloqueo, por ejemplo mediante el uso de algoritmos sin bloqueo como lectura-copia-actualización .

Ver también

Referencias

  1. ^ Glenn Reeves, What Really Happened on Mars, equipo JPL Pathfinder , consultado el 4 de enero de 2019
  2. ^ Explicación del problema de inversión de prioridad experimentado por Mars Pathfinder (PDF) , archivado desde el original (PDF) el 20 de febrero de 2021 , consultado el 4 de enero de 2019.
  3. ^ Lampson, B; Redell, D. (junio de 1980). "Experiencia con procesos y monitores en MESA". Comunicaciones de la ACM . 23 (2): 105-117. CiteSeerX 10.1.1.46.7240 . doi :10.1145/358818.358824. S2CID  1594544. 
  4. ^ Inversión de prioridad en MSDN

enlaces externos