5. Sistemas Operativos. Deadlocks.

 Deadlocks

Cuaderno completo con este tema:

https://notebooklm.google.com/notebook/5166988a-ebaf-4298-a06b-2f1fbc7bcc61

Por qué estudiar los deadlocks a nivel del sistema operativo ?

Puede haber deadlocks en todas las capas: arquitectura, SO, red, SGBD, etc

Provienen de errores de programación donde no se tuvo en cuenta todos los aspectos de la concurrencia y sincronización.

Un proceso que está participando de un deadlock no puede ejecutar. Y en particular no devuelve los recursos que tiene, tornándolos indisponibles para el resto de los procesos.

Nos interesa estudiar este tema desde la óptica del SO. Qué hacer para minimizar la ocurrencia de estas situaciones?

Nos interesa minimizarlos por ser un desperdicio de recursos.

Queremos minimizar las situaciones donde tenemos recursos trancados o directamente el sistema trancado.

A veces pasa… que las ventanas no responden pero el mouse si…

Si el mouse se mueve……………… entonces arquitectura OK, CPU OK, memoria OK, etc

Pero si aun así está trancado, puede haber una situación de deadlock subyacente.

Nos interesa este tema entonces por tres razones:

• Cuando varios procesos participan de un deadlock, se trancan, es decir no avanzan en su ejecución, y en particular, no devuelven los recursos que ya tuvieran, dejándolos indisponibles para todo el mundo y para siempre.
• Si un deadlock afecta procesos vitales, dejaría inútil al sistema.
• Los deadlocks ocurren por esperas por recursos. El gestor de recursos es el SO y por tanto debe ocuparse de este asunto.

Un conjunto de procesos está en deadlock cuando c/u está en estado bloqueado, y c/u está asociado a una situación de bloqueo que depende de otro proceso del conjunto. Con lo cual nunca van a poder salir de esa situación por sí mismos. Sin embargo, llegaron a esta situación tan sólo ejecutando líneas como las que siguen.

Por ejemplo

PROCESO 1

1 pedir impresora 1

2 pedir impresora 2

 PROCESO 2

1’ pedir impresora 2

2’ pedir impresora 1

Si justo se intercalan 1 1’ 2 2’ tenemos deadlock

1……….. el proceso 1 pide la impresora 1 y ésta le es dada.

2……… el proceso 2 pide la impresora 2 y ésta le es dada.

1’……. El proceso 1 pide la impresora 2 y ésta está asignada, debe esperar, bloqueo.

2’---- El proceso 2 pide la impresora  1 y ésta está asignada, debe esperar, bloqueo.

Quedan acá trancados los dos procesos hasta el admin mate a uno.

Con matar a uno de los dos alcanza, pues ese va a devolver el recurso que tenía acaparado, y de ese modo lo toma el otro y ejecuta.

A está esperando por B, que está esperando por C, que está esperando por A.

Ese ciclo es característico de los deadlocks.

Puede un proceso sólo estar en deadlock ? Técnicamente no, deberían ser al menos 2. Pero puede ocurrir que un proceso queda esperando un evento, ya sea un evento que jamás ocurrirá o un evento que ocurre pero no tenemos como señalizar su ocurrencia.

En general los deadlocks ocurren entre varios procesos.

Un concepto relacionado al de deadlock es el de aplazamiento indefinido o posposición indefinida. Un proceso cae en AI cuando producto de una política de prioridades poco afortunada, o muy agresiva, todos los demás procesos se le cuelan al proceso con AI. No es un deadlock pero es igual de inconveniente.

Por qué es tan molesto ? Por la misma razón que los procesos en deadlock. Tienen recursos, no avanzan, y no los devuelven. Entonces dejan indisponibles los recursos y encima no ejecutan lo que se pretendía que ejecutaran.

Cómo se soluciona ?

Con las técnicas llamadas de aging, envejecimiento. Cada vez que un proceso es desplazado por otro de mayor prioridad, aumentamos en una unidad la prioridad del proceso desplazado. De esta forma no será infinita su espera.

Los procesos en deadlock están en estado bloqueado, por tanto no consumen CPU. Sí ocupan memoria.

Lo que es cierto es que al avanzar, si tienen asignados recursos, y justo se trancan, esos recursos no quedan disponibles para nadie. El gran problema de la ocurrencia de un deadlock es que el/los procesos involucrados en él, acaparan determinados recursos que quedan inutilizados, indisponibles.

El bloqueo al que se someten los procesos que están formando parte de un deadlock, puede ser seguramente por espera por algún RSR.

El SISTEMAS OPERATIVO es el administrador de recursos del sistema. Por tanto debe ocuparse de los deadlocks. Estudiaremos en qué medida podremos hacerlo… Aparecerán consecuencias muy interesantes como por ejemplo escenarios libres de deadlocks garantizados.

Tenemos 4 asuntos en torno a los deadlocks:

• Prevenir: vamos a configurar nuestro sistema de modo de garantizar la no existencia de deadlocks.
• Evitar: vamos a revisar asignación por asignación y prohibiremos las riesgosas. Algoritmo del banquero por ejemplo.
• Detectar: vamos a dejar que ocurran y saldremos a detectar un ciclo en un grafo de asignación de recursos que estudiaremos.
• Recuperar: una vez detectado el deadlock, qué procesos matar para rehacernos haciendo el menor daño posible.

Ejemplo:

Lo más curioso es que se meten en el deadlock yendo hacia adelante.

• Para cada auto de los participantes del atascamiento, existe un auto que está en su camino y le impide avanzar.
• Como tienen otros autos atrás, no pueden retroceder.
•  Ese deadlock no tiene solución sin intervención de una grúa u otro agente externo.

Un caso de deadlock simple de recursos:

• En general los deadlocks en los SOs ocurren por competencia de los procesos por RSRs.
•  RSRs (o recursos dedicados) son recursos que sólo pueden ser usados por un proceso a la vez.
• Hasta los datos y los programas pueden ser vistos como recursos y lo haremos!.

• El proceso A tiene asignado el recurso 1.
•  El proceso B tiene asignado el recurso 2.
•  El Proceso A pide (y se bloquea a esperar por) el recurso 2.
•  El Proceso B pide (y se bloquea a esperar por) el recurso 1.

• No hay forma de desbloquear ni el proceso 1 ni el proceso 2.
•  Esa espera circular es característica de los procesos en deadlock.

El aplazamiento indefinido está emparentado, en tanto un proceso no logra avanzar en su ejecución.

• A veces la ejecución de un proceso (no necesariamente bloqueado) puede postergarse indefinidamente mientras otros procesos reciben la atención del sistema.
•  Esta situación se conoce como aplazamiento indefinido.
•  Se deriva de las políticas de planificación de recursos del sistema, que bajo determinadas circunstancias tienen ciertas predisposiciones que perjudican la ejecución de ciertos procesos.
• Por ejemplo cuando existe una planificación por prioridad, es posible que a cierto proceso se le adelanten indefinidamente procesos de mayor prioridad.
•  Esto puede evitarse por ejemplo aumentando la prioridad de los procesos mientras esperan, política llamada “envejecimiento”.

El aging o envejecimiento, consiste en subir en 1 la prioridad de un proceso cada vez que alguno de mayor prioridad se le adelante.

Respecto a los deadlocks, interesa clasificar los recursos en apropiables y no apropiables. Un recurso apropiable es aquel que puede ser arrebatado, por el SO o por algún otro proceso.

La CPU es el recurso más apropiable del sistema. También puede serlo la memoria.

Los RSRs son claramente no apropiables y deben ser gestionados en consecuencia. NO pueden ser arrabatados. Ej. Una cinta de backup que realiza un proceso de backup que no puede ser interrumpido. Idem una impresora imprimiendo , etc.

El código y los datos pueden ser compartidos. Basta gestionar su concurrencia. Muchas veces tenemos procesos que trabajan sobre la misma copia DEL código. Y en ese caso este código se dice REENTRANTE y NO PUEDE SER MODIFICADO.

• Cuando se dice que ciertos recursos son compartidos, debe decirse si van a ser usados por varios procesos de manera simultánea o si pueden ser utilizados por varios procesos pero sólo uno a la vez (RSRs).
•  Estos últimos, los RSRs, son los que tienden a participar de bloqueos mutuos.

Las 4 condiciones necesarias para la ocurrencia de deadlock:

Son necesarias pero no son suficientes. Podrían estar dadas y simplemente llegar una nueva unidad de recurso y ya no tendríamos deadlock.

La exclusión mutua no es negociable, no puedo desactivarla. Sería un caos.

Pero me quedan 3 estategias, derivadas de este análisis, que son:

• Negación de la condición de espera
• Negación de la condición de no apropiación
• Negación de la condición de espera circular.

Daremos una especie de fórmula para cada una…

Serán las 3 técnicas de prevención del deadlock que analizaremos.

Técnica 1: Negación de la espera.

Consiste en pedir todos los recursos al TODO o NADA. Me tienen que dar todos los recursos juntos.

Si esto se programa así, queda garantizada la ausencia de deadlocks.

Si son muchos recursos, y están muy solicitados, es muy difícil pedirlos todos de una vez.

Y cuando los damos todos de una vez, es ineficiente que estén sin utilizar!

Si hacemos este “pequeño” sacrificio al programar, estamos garantizando la ausencia de deadlocks.

Podemos caer en aplazamiento indefinido, esperando por todos los recursos juntos.

En qué escenario esto podría funcionar bien? Si son pocos procesos, pocos recursos y en cantidades fijas o casi fijas. Este escenario se puede dar en los STR. No se da en un SO.

Técnica 2: Negación de la no apropiación.

Se vienen otorgando los recursos uno a uno, pero cuando se niega uno, se devuelven los demás…. TODOS. Y vuelve a pedir.

Claramente no genera trancas.

La devolución de recursos implica pérdida de cómputo…, esto hay que recomputarlo… es ineficiente.

El problema es que si la situación es de alta carga del sistema, este “devolver todos los recursos” puede darse con relativa frecuencia. Y esto degrada muchísimo la performance del sistema.

Puede derivar en aplazamiento indefinido.

En qué escenario esto podría funcionar bien? Si son pocos procesos, pocos recursos y en cantidades fijas o casi fijas. Este escenario se puede dar en los STR. No se da en un SO.

Técnica 3: negación de la espera circular.

 En este caso numeramos los recursos y autorizamos pedidos en forma estrictamente ascendente o descendente. Esto evita la formación del ciclo, no es posible cerrarlo.

Cuando se van devolviendo los recursos, se ajusta el nivel de permiso.

Notemos que un recurso libre puede ser negado, por el riesgo futuro de deadlock.

Al ser un orden estrictamente ascendente (o descendente) no hay forma de cerrar un ciclo en el grafo, con lo cual no habrá deadlocks.

Ej

Impresora 1 es el 1, impresora 2 es el 2, cinta 1 es el 3

Pedir impresora2

Sólo lo podré autorizar, si voy ascendiendo y pasaría por él.

Una vez que lo hago, no puedo pedir la impresora 1, que queda atrapada. Debe esperar a que la impresora 2 sea devuelta, para ahí autorizar la impresora 1.

Se garantiza un sistema sin deadlocks.

En qué escenario esto podría funcionar bien? Si son pocos procesos, pocos recursos y en cantidades fijas o casi fijas. Este escenario se puede dar en los STR. No se da en un SO.

Cuál es el problema de estas 3 estrategias de prevención? Siempre viene dado de la ponderación de la probabilidad de ocurrencia de estos eventos que generan por ejemplo devolución anticipada de recursos sin llegarlos a usar.

Paréntesis. Los SO y los STR.

Sistemas Operativos:

Misión: Gestionar recursos.

Objetivo global: Maximizar el uso del sistema, del hardware.

Absolutamente genérico. No sabemos qué ejecutaremos sobre él (juegos, herramientas de office, server, etc)

Por ejemplo Linux es el mismo para una máquina individual de escritorio que para un server.

Puedo crear nuevos procesos? SI; todo el tiempo.

Podemos castigar/beneficiar en función de prioridades: muy poco.

Cantidad de procesos y de recursos incierta y no acotada.

SISTEMA DE TIEMPO REAL:

Misión: Gestionar recursos

Objetivo global: Minimizar tiempos de respuesta.

Absolutamente específico.

Por ejemplo el software de control de tracción de un auto ejecuta él y más nada y en un entorno que él controla en absoluto.

Puedo crear nuevos procesos? NO.

Podemos castigar/beneficiar en función de las prioridades: SI.

Cantidad de procesos y de recursos conocida, y fija o casi fija.

SISTEMA OPERATIVO DE TIEMPO REAL:

Ej. Android.

Se comporta como un SO pero tiene características y requisitos de tiempo real.

Algunos dispositivos mutan de STR a SOTR… ejemplo el celular, la Tablet, el Smart tv, etc. El SOTR brinda mayor abstracción y mejores herramientas de desarrollo.

Los métodos de prevención vistos, requieren de pocos procesos, pocos recursos, en cantidades fijas o casi fijas. Los SO no satisfacen esa hipótesis pero algunos STR sí.

EVITAR LOS DEADLOCKS. El algoritmo del Banquero.

Este algoritmo no prohíbe a priori aspectos tan pesados como las estrategias de prevención recién vistas.

En cambio, permite las asignaciones de recursos hasta JUSTO ANTES de una situación de riesgo.

El algoritmo define estados seguros y va evolucionando de estado seguro a estado seguro. Una petición que llega, se analiza, se simula, y en caso de conducir a un estado inseguro, se rechaza su ejecución.

Lo destacable, igual que antes, es que el algoritmo puede negar un recurso libre.

Lo trabajaremos a través de un ejemplo.

Sea un total t de unidades de cinta.

Y sean n procesos corriendo, p1, p2, …pn.

Vamos a pedirle a cada proceso que manifieste su necesidad máxima de cintas.

Sean m1, m2, … mn dichas magnitudes.

mi <=t para todo i. Si algún proceso pide más unidades de cintas que las que disponemos, entonces lo expulsa el SO, no lo deja ejecutar.

Las unidades de cinta son todas iguales.

Sea ai  i=1,2,…n la cantidad de cintas que tiene el proceso i en un momento dado (las cintas que le han sido otorgadas).

Entonces ai<=mi para todo y entre 1 y n.

Todos los procesos, luego de que se les da el máximo requerido de recursos, o sea ai=mi… a partir de ahí no le queda otra más que devolver todos sus recursos.

Vamos a pedir y a devolver de a una unidad.

En un momento dado, los diferentes procesos tendrán satisfacción parcial de su pedido de recurso.

Sean ai las unidades asignadas al proceso i.

a1, a2, a3 , a4 , a5, …. ,an cada uno ellas ai <=mi<=t

Vamos a tener estados seguros e inseguros. Un estado seguro es aquel en el cual el banquero puede pagarle a todos sin riesgos.

Un estado inseguro será aquel en el cual podría ocurrir deadlock.

No hay riesgo de deadlock, todos pueden terminar su ejecución..

El estado inseguro no necesariamente lleva a un deadlock. Porque tal vez el proceso u1 decía necesitar 10 unidades y necesitó capaz 9 y ya devuelve, y ya se destranca todo.

En este estado inseguro podría ocurrir un deadlock ya que quedan esperando por recursos que no tengo cómo darles.

Podemos pasar con UNA SOLA ASIGNACION de un estado seguro a un estado inseguro.

Por ejemplo al hacer en el estado seguro anterior, dar una unidad de cinta al proceso u3.

El algoritmo del banquero consistirá en:

RECIBIR PETICION

SIMULAR NUEVO ESTADO CON LA PETICIÓN HECHA

SI ES SEGURO ENTONCES LA AUTORIZA

SI NO ES SEGURO ENTONCES SE DESAUTORIZA LA PETICIÓN.

De este modo el algoritmo pasará de estado seguro a estado seguro.

Críticas:

• Supone fijo el número  de recursos.
• Supone fijo el número de procesos.
• Supone que al satisfacer la petición máxima, los procesos devuelven los recursos.
• Supone que la declaración de necesidad es correcta.

Todo esto lo aleja de los Sistemas Operativos y de los SOTR, y eventualmente lo acerca a ALGUNOS STR.

De nuevo bajo condiciones de procesos y recursos en cantidades fijas o casi fijas, este algoritmo puede tener sentido.

OTRO ENFOQUE: detección del deadlock.

No parametrizamos ni ajustamos el sistema para prevenir deadlocks.

No revisamos exhaustivamente cada asignación de recursos.

Solamente dejamos que ocurra el deadlock y salimos a detectarlo.

Cómo detectarlo ? Generando el grafo de asignación de recursos y buscando en él un ciclo.

Este algoritmo es O(n**2).

Reducción de un grafo de asignación de recursos:

• Si pueden atenderse las peticiones de un proceso, se dice que el grafo puede ser reducido por ese proceso.
•  Esta reducción equivale a mostrar el grafo como si el proceso hubiera terminado su ejecución y hubiera devuelto sus recursos al sistema.
•  Si un grafo puede ser reducido por todos sus procesos, entonces no hay deadlock.
•  Los procesos irreductibles constituyen el subconjunto de procesos en deadlock.

Este algoritmo podríamos ejecutarlo cada vez que queramos detectar un deadlock.

Es pesado, n**2, pero detecta.

La pregunta es……………. Cuándo?

Si lo ejecuto en cada asignación …………. Es demasiado.

Cada cierto tiempo? SI es poco tiempo degrada performance. Si es mucho es inútil.

Este algoritmo es absolutamente impertinente. No hay cuándo ejecutarlo.

Por eso no se utiliza.

Tal vez podría en algún sistema muy pequeño tipo algún sistema de tiempo real.

RECUPERACIÓN LUEGO DE UN DEADLOCK

Supongamos que el deadlock se ha detectado, o se cree que hay uno, debido a la ausencia de resultados o avance de algún algoritmo, así como también a la indisponibilidad de algunos recursos.

Eso lleva a pensar en procesos trancados en alguna dinámica de este tipo que capaz es un deadlock.

Vamos a tener que matar alguno de los procesos participantes del ciclo.

Puede no estar del todo claro qué procesos son.

Si salimos a matar procesos, vamos a tener que pagar un precio: el del cómputo perdido.

No hay otra opción que matar procesos y arrebatarle los recursos, de la forma más prolija posible.

En Unix/Linux podríamos probar con un kill proceso. Y si no se muere mandarle kill -9 proceso (arrebata recursos y mata el proceso). Ahí seguro baja pero puede dejar secuelas. Puede dejar índices o tablas o archivos corruptos, etc.

Vamos a perder cómputo. Se trata de optimizar caso a caso.

Todo precio es razonable respecto a tener el sistema trancado.

Usualmente es el operador (no el sysadmin y no el programador) quien termina decidiendo qué procesos matar primero para destrancar el sistema y/o liberar recursos. Lo hará con información parcial, y probablemente en base a su conocimiento y percepción del problema y de las prioridades de los programas a matar, lo cual es altamente sesgado.

Los sistemas operativos aportan información y comandos para el manejo explícito de los procesos:

Unix/Linux ---------- PS y KILL

Windows --------------- Manejador de procesos

Resolver por el camino óptimo puede ser muy costoso con lo cual todo esto queda en manos del operador quien en base a algunas prioridades y a su conocimiento del sistema decidiría a quienes matar primero.

Continuaremos con el tema Schedulling de procesos, donde vamos a estudiar cómo repartir el recurso más importante de la arquitectura: el procesador. Y esa forma de repartir va a tener que garantizar la ilusión más potente que provee el sistema operativo: la multitarea.

Vamos ver requisitos, insumos y estrategias para ello. Y vamos a separar los STR de los SO.

Vamos a tener dos familias de objetivos muy diferentes:

• En los SO, maximizar el uso del hardware.

En los STR, minimizar el tiempo de respuesta.