operating-system priority-inversion

operating system - ¿Qué es inversión de prioridad?



operating-system priority-inversion (12)

He escuchado la frase ''inversión de prioridad'' en referencia al desarrollo de sistemas operativos.

¿Qué es exactamente inversión de prioridad?

¿Cuál es el problema que debe resolver y cómo lo resuelve?

Considere un sistema con dos procesos, H con alta prioridad y L con baja prioridad. Las reglas de programación son tales que H se ejecuta siempre que esté en estado listo debido a su alta prioridad. En un momento determinado, con L en su región crítica, H está listo para ejecutarse (por ejemplo, una operación de E / S completa). Ahora H comienza a esperar ocupado, pero como L nunca se programa mientras H está ejecutando, L nunca tiene la oportunidad de salir de la sección crítica. Así que H repite para siempre.

Esta situación se llama Priority Inversion . Porque el proceso de mayor prioridad está esperando en el proceso de menor prioridad.

Déjame hacerlo muy simple y claro. (Esta respuesta se basa en las respuestas anteriores, pero se presenta de manera nítida).

Diga que hay un recurso R y 3 procesos. L , M , H donde p(L) < p(M) < p(H) (donde p(X) es la prioridad de X ).

Decir

  • L comienza a ejecutar primero y atrapa retenciones en R (acceso exclusivo a R )
  • H viene después y también quiere acceso exclusivo a R y como L lo tiene, H tiene que esperar.
  • M viene después de H y no necesita R Y como M tiene todo lo que quiere ejecutar, obliga a L a dejarlo ya que tiene una alta prioridad en comparación con L Pero H no puede hacer esto ya que tiene un recurso bloqueado por L que necesita para la ejecución.

Ahora, aclarando el problema, la M debería esperar que H complete como p(H) > p(M) lo que no sucedió y este es el problema. Si muchos procesos como M aparecen y no permiten que la L ejecute y libere el bloqueo, H nunca se ejecutará. Que puede ser peligroso en aplicaciones de tiempo crítico

Y para las soluciones, consulte las respuestas anteriores :)

Es el problema más que la solución.

Describe la situación en la que cuando los subprocesos de baja prioridad obtienen bloqueos durante su trabajo, los subprocesos de alta prioridad tendrán que esperar a que finalicen (lo que puede llevar mucho tiempo, ya que son de baja prioridad). La inversión aquí es que el hilo de alta prioridad no puede continuar hasta que el hilo de baja prioridad lo haga, por lo que en realidad también tiene baja prioridad ahora.

Una solución común es hacer que los subprocesos de baja prioridad hereden temporalmente la alta prioridad de todos los que están esperando los bloqueos que tienen.

Imagine tres (3) tareas de diferente prioridad: tLow, tMed y tHigh. tLow y tHigh acceden al mismo recurso crítico en diferentes momentos; tMed hace lo suyo.

  1. tLow está funcionando, tMed y tHigh están actualmente bloqueados (pero no en la sección crítica).
  2. tLow viene y entra en la sección crítica.
  3. Desbloquea por primera vez y, dado que es la tarea de mayor prioridad en el sistema, se ejecuta.
  4. tHigh luego intenta ingresar al recurso crítico pero bloquea a medida que TLow está ahí.
  5. tMed se desbloquea y, dado que ahora es la tarea de mayor prioridad en el sistema, se ejecuta.

No se puede ejecutar hasta que tLow abandone el recurso. tLow no puede ejecutarse hasta que tMed bloquee o termine. La prioridad de las tareas ha sido invertida; Por encima de todo, tiene la prioridad más alta en la parte inferior de la cadena de ejecución.

Para "resolver" la inversión de prioridad, la prioridad de tLow debe aumentarse para que sea al menos tan alta como tHigh. Algunos pueden subir su prioridad al nivel de prioridad más alto posible. Tan importante como subir el nivel de prioridad de tLow, es bajar el nivel de prioridad de tLow en el momento apropiado. Los diferentes sistemas tomarán diferentes enfoques.

Cuándo descartar la prioridad de tLow ...

  1. No hay otras tareas bloqueadas en ninguno de los recursos que tLow tiene. Esto puede deberse a tiempos de espera o a la liberación de recursos.
  2. Ninguna otra tarea que contribuya a elevar el nivel de prioridad de tLow está bloqueada en los recursos que posee TLow. Esto puede deberse a tiempos de espera o a la liberación de recursos.
  3. Cuando hay un cambio en las tareas que están esperando los recursos, elimine la prioridad de tLow para que coincida con la prioridad de la tarea de nivel de prioridad más alta bloqueada en su (s) recurso (s).

El Método n. ° 2 es una mejora con respecto al método n. ° 1, ya que acorta el tiempo durante el cual tLow ha tenido su nivel de prioridad superado. Tenga en cuenta que su nivel de prioridad se mantiene en el nivel de prioridad de tHigh durante este período.

El Método # 3 permite que el nivel de prioridad de tLow disminuya en incrementos si es necesario en lugar de en un paso de todo o nada.

Los diferentes sistemas implementarán diferentes métodos según los factores que consideren importantes.

  • huella de memoria
  • complejidad
  • respuesta en tiempo real
  • conocimiento del desarrollador

Espero que esto ayude.

La Inversión de Prioridad puede evitarse si el subproceso de alta prioridad bloqueado transfiere su alta prioridad al subproceso de baja prioridad que está reteniendo el recurso.

La inversión prioritaria es cuando un proceso de menor prioridad obtiene un recurso que necesita un proceso de prioridad más alta, lo que impide que el proceso de mayor prioridad continúe hasta que se libera el recurso.

por ejemplo: FileA necesita ser accedido por Proc1 y Proc2. Proc 1 tiene una prioridad más alta que Proc2, pero Proc2 logra abrir FileA primero.

Normalmente, Proc1 se ejecutará tal vez 10 veces más que Proc2, pero no podrá hacer nada porque Proc2 está reteniendo el archivo.

Entonces, lo que termina sucediendo es que Proc1 bloquea hasta que Proc2 termina con FileA, esencialmente sus prioridades están ''invertidas'' mientras que Proc2 tiene el mango de FileA.

En lo que respecta a ''Resolver un problema'', la inversión de prioridad es un problema en sí mismo si sigue sucediendo. El peor de los casos (la mayoría de los sistemas operativos no permitirán que esto suceda) es si Proc2 no pudo ejecutarse hasta que Proc1 lo hizo. Esto provocaría que el sistema se bloquee ya que a Proc1 se le seguiría asignando tiempo de CPU, y Proc2 nunca obtendría tiempo de CPU, por lo que el archivo nunca se lanzará.

La inversión prioritaria es un problema, no una solución. El ejemplo típico es un proceso de baja prioridad que adquiere un recurso que necesita un proceso de alta prioridad, y luego es reemplazado por un proceso de prioridad media, por lo que el proceso de alta prioridad se bloquea en el recurso mientras que la prioridad media finaliza (se ejecuta efectivamente con baja prioridad).

Un ejemplo bastante famoso fue el problema experimentado por el rover Mars Pathfinder: http://www.cs.duke.edu/~carla/mars.html , es una lectura bastante interesante.

La inversión prioritaria ocurre como tal: dados los procesos H, M y L, donde los nombres representan prioridades altas, medias y bajas, solo H y L comparten un recurso común.

Digamos, L adquiere el recurso primero y comienza a funcionar. Como H también necesita ese recurso, ingresa en la cola de espera. M no comparte el recurso y puede comenzar a ejecutar, por lo tanto lo hace. Cuando L es interrumpido por cualquier medio, M toma el estado de ejecución ya que tiene mayor prioridad y se ejecuta en el instante en que ocurre la interrupción. Aunque H tiene mayor prioridad que M, dado que está en la cola de espera, no puede adquirir el recurso, lo que implica una prioridad menor que incluso M. Después de que M finalice, L asumirá de nuevo la CPU, lo que hará que H espere todo el tiempo.

Problema de inversión prioritaria:
Veamos un ejemplo: Tareas:
Alta prioridad (H)
Prioridad media (M)
Baja prioridad (L)

y un bloqueo X, puede ser un semáforo_lock (X).

Guión:
1. L corre y adquiere X
2. Entonces H intenta acceder a X mientras que L lo tiene, debido al semáforo, H duerme.
3. M llega, se adelanta a L y se ejecuta. En efecto, H & M eran dos procesos esperando para ejecutarse, pero M corría porque H estaba esperando el bloqueo y no podía correr .
4. M termina, H no puede ingresar porque L tiene el bloqueo, por lo que L se ejecuta.
5. L termina, renuncia a la cerradura. Ahora H obtiene el bloqueo y se ejecuta.

H tenía la prioridad más alta pero se ejecutó después de que se hubieran ejecutado los procesos de menor prioridad. Esta es la Inversión de Prioridad.

Ahora solución de inversión prioritaria.
Cuando un proceso de baja prioridad se está ejecutando y tiene un bloqueo, y si un proceso de alta prioridad intenta adquirir el bloqueo, la prioridad del proceso de baja prioridad se eleva a la prioridad del proceso de alta prioridad. Es decir, si L se está ejecutando y tiene el bloqueo, cuando H intente adquirirlo, la prioridad de L se elevará a la de H durante el tiempo que L retiene el bloqueo. De esta manera, M no puede adelantarse. Después, termina L, H corre y adquiere el bloqueo. Después de H, M se ejecuta conservando el orden de prioridad.

Supongamos que una aplicación tiene tres hilos:

Thread 1 has high priority. Thread 2 has medium priority. Thread 3 has low priority.

Supongamos que el Tema 1 y el Tema 3 comparten el mismo código de sección crítica

El hilo 1 y el hilo 2 están durmiendo o bloqueados al principio del ejemplo. El hilo 3 se ejecuta y entra en una sección crítica.

En ese momento, el subproceso 2 comienza a ejecutarse, adelantándose al subproceso 3 porque el subproceso 2 tiene una prioridad más alta. Entonces, el hilo 3 sigue siendo dueño de una sección crítica.

Más tarde, el subproceso 1 comienza a ejecutarse, adelantándose al subproceso 2. El subproceso 1 intenta ingresar a la sección crítica que posee el subproceso 3, pero como pertenece a otro subproceso, enhebre 1 bloque, esperando la sección crítica.

En ese punto, el subproceso 2 comienza a ejecutarse porque tiene una prioridad más alta que el subproceso 3 y el subproceso 1 no se está ejecutando. El subproceso 3 nunca libera la sección crítica que el subproceso 1 está esperando porque el subproceso 2 continúa ejecutándose.

Por lo tanto, el subproceso de mayor prioridad en el sistema, el subproceso 1, se bloquea al esperar que se ejecuten los subprocesos de menor prioridad.

Surge un desafío de programación cuando un proceso de mayor prioridad necesita leer o modificar los datos del kernel a los que actualmente se accede mediante un proceso de menor prioridad o una cadena de procesos de menor prioridad. Dado que los datos del kernel generalmente están protegidos con un bloqueo, el proceso de mayor prioridad tendrá que esperar a que uno de menor prioridad termine con el recurso. La situación se vuelve más complicada si se adelanta el proceso de menor prioridad a favor de otro proceso con mayor prioridad. Como ejemplo, supongamos que tenemos tres procesos: L, M y H, cuyas prioridades siguen el orden L <M <H. Supongamos que el proceso H requiere el recurso R, que actualmente se accede mediante el proceso L. Por lo general, el proceso H haría esperar a que L termine usando el recurso R. Sin embargo, ahora supongamos que el proceso M se vuelve ejecutable, adelantándose al proceso L. Indirectamente, un proceso con un proceso de prioridad más baja M, ha afectado cuánto tiempo el proceso H debe esperar para que L renuncie al recurso R Este problema se conoce como inversión de prioridad. Se produce solo en sistemas con más de dos prioridades, por lo que una solución es tener solo dos prioridades. Sin embargo, no es suficiente para la mayoría de los sistemas operativos de propósito general. Normalmente, estos sistemas resuelven el problema implementando un protocolo de herencia de prioridad. De acuerdo con este protocolo, todos los procesos que acceden a los recursos que necesita un proceso de prioridad más alta heredan la prioridad más alta hasta que se finalizan con los recursos en cuestión. Cuando se finalizan, sus prioridades vuelven a sus valores originales. En el ejemplo anterior, un protocolo de herencia de prioridad permitiría que el proceso L herede temporalmente la prioridad del proceso H, impidiendo así que el proceso M prevenga su ejecución. Cuando el proceso L haya terminado usando el recurso R, renunciará a su prioridad heredada de H y asumirá su prioridad original. Debido a que el recurso R ahora estaría disponible, el proceso H -no M- se ejecutará a continuación. Referencia: ABRAHAM SILBERSCHATZ

[Suponga, proceso bajo = LP, proceso medio = MP, proceso alto = HP]

LP está ejecutando una sección crítica. Al ingresar a la sección crítica, LP debe haber adquirido un bloqueo en algún objeto, digamos OBJ. LP ahora está dentro de la sección crítica.

Mientras tanto, se crea HP. Debido a una prioridad más alta, la CPU realiza un cambio de contexto, y HP ahora está ejecutando (no la misma sección crítica, sino algún otro código). En algún punto durante la ejecución de HP, necesita un bloqueo en el mismo OBJ (puede o no estar en la misma sección crítica), pero el bloqueo en OBJ todavía está en manos de LP, ya que fue bloqueado mientras se ejecutaba la sección crítica . LP no puede renunciar ahora porque el proceso está en estado LISTO, no EN EJECUCIÓN. Ahora HP pasa al estado BLOCKED / WAITING.

Ahora, MP entra y ejecuta su propio código. MP no necesita un bloqueo en OBJ, por lo que sigue ejecutándose normalmente. HP espera que LP libere el bloqueo, y LP espera a que MP finalice la ejecución para que LP vuelva al estado RUNNING (... y ejecute y suelte el bloqueo). Solo después de que LP haya liberado el bloqueo, HP puede volver a LISTO (y luego pasar a EJECUTAR al adelantarse a las tareas de baja prioridad).

Por lo tanto, efectivamente significa que hasta que MP finalice, LP no se puede ejecutar y, por lo tanto, HP no puede ejecutar. Entonces, parece que HP está esperando MP, a pesar de que no están directamente relacionados a través de bloqueos OBJ. -> Inversión de prioridad .

Una solución para la Inversión de Prioridad es Herencia de Prioridad -

aumentar la prioridad de un proceso (A) a la prioridad máxima de cualquier otro proceso en espera de cualquier recurso en el que A tenga un bloqueo de recursos.