Unidad 2.4 Concurrencia y secuenciabilidad.

Procesos concurrentes.

 Los procesos son concurrentes si existen simultáneamente. Los procesos concurrentes pueden funcionar en forma totalmente independiente unos de otros, o pueden ser asíncronos, lo cual significa que en ocasiones requiere cierta sincronización y cooperación.
 Las siguientes definiciones son esenciales para comprender los conceptos de concurrencia y secuencialidad.

* Actividad.
 . Procesos: Es un programa en ejecución.

 . Tarea:      Son las distintas partes de un proceso que se ejecutan simultáneamente.

* Sistemas:
. Multiprogramación: Admiten varias actividades que comparten el procesador, pero sólo
            una puede estar ejecutándose en un momento dado.
. Multiproceso:          Las actividades se ejecutan en sus propios procesadores, conectados
          a través de una red de comunicaciones.

* Paralelismo:
 Es la ejecución de diversas actividades simultáneamente en varios procesadores. Si sólo existe un procesador gestionando multiprogramación, se puede decir que existe pseudo-paralelismo. Se trata de un concepto físico producido por la existencia de varios procesadores.

* Concurrencia:
 Es la existencia de varias actividades ejecutándose simultáneamente, y necesitan sincronizarse para actuar conjuntamente. Se trata, en este caso, de un concepto lógico, ya que sólo hace referencia a las actividades, sin importar el número de procesadores presentes.

 Para que dos actividades, sean concurrentes, es necesario que tengan relación entre sí, como puede ser la cooperación en un trabajo determinado o el uso de información compartida.

 En un sistema monoprocesador, la existencia de multiprogramación es condición necesaria, pero no suficiente para que exista concurrencia, ya que los procesos pueden ejecutarse independientemente. Por ejemplo, un editor y un compilador pueden estar ejecutándose simultáneamente en una computadora sin que exista concurrencia entre ellos. Por otro lado si un programa se está ejecutando y se encuentra grabando datos en un archivo, y otro programa también en ejecución está leyendo datos de ese mismo archivo, sí existe concurrencia entre ellos, pues el funcionamiento de uno interfiere en el funcionamiento de otro.
 Si un sistema es multiprocesador, también pueden presentarse situaciones de concurrencia siempre y cuando las actividades necesiten actuar entre sí, bien por utilizar información común, o por cualquier otra causa.

 Los procesos del sistema pueden ejecutarse concurrentemente, puede haber múltiples tareas en el CPU con varios procesos. Existen varias razones para permitir la ejecución concurrente:

* Compartir recursos físicos.

 Ya que los recursos del hardware de la computadora son limitados, nos podemos ver obligados a compartirlos en un entorno multiusuario.

* Compartir recursos lógicos.

Puesto que varios usuarios pueden interesarse en el mismo elemento de información (por ejemplo un archivo compartido), debemos proporcionar un entorno que permita el acceso concurrente a estos tipos de recursos.


* Acelerar los cálculos.

 Si queremos que una tarea se ejecute con mayor rapidez, debemos dividirla en subtareas, cada una de las cuales se ejecutara, en paralelo con las demás.

* Modularidad.

 Podremos construir el sistema en forma modular, dividiendo las funciones del sistema en procesos separados.

* Comodidad.

 Un usuario puede tener que ejecutar varias tareas a la vez, por ejemplo puede editar, imprimir y compilar en paralelo.

 La ejecución concurrente que requiere la cooperación entre procesos necesita un mecanismo para la sincronización y comunicación de procesos, exclusión mutua y sincronización.
http://eduadis.itlapiedad.edu.mx/~hocegueras/so1/so1_212.html
Problemas de Concurrencia
En los sistemas de tiempo compartido (aquellos con varios usuarios, procesos, tareas, trabajos que reparten el uso de CPU entre estos) se presentan muchos problemas debido a que los procesos compiten por los recursos del sistema. Imagine que un proceso está escribiendo en la unidad de cinta y se le termina su turno de ejecución e inmediatamente después el proceso elegido para ejecutarse comienza a escribir sobre la misma cinta. El resultado es una cinta cuyo contenido es un desastre de datos mezclados. Así como la cinta, existen una multitud de recursos cuyo acceso debe der controlado para evitar los problemas de la concurrencia.
El sistema operativo debe ofrecer mecanismos para sincronizar la ejecución de procesos: semáforos, envío de mensajes, 'pipes', etc. Los semáforos son rutinas de software (que en su nivel más interno se auxilian del hardware) para lograr exclusión mutua en el uso de recursos. Para entender este y otros mecanismos es importante entender los problemas generales de concurrencia, los cuales se describen enseguida.
• Condiciones de Carrera o Competencia: La condición de carrera (race condition) ocurre cuando dos o más procesos accesan un recurso compartido sin control, de manera que el resultado combinado de este acceso depende del orden de llegada. Suponga, por ejemplo, que dos clientes de un banco realizan cada uno una operación en cajeros diferentes al mismo tiempo.
• El usuario A quiere hacer un depósito. El B un retiro. El usuario A comienza la transacción y lee su saldo que es 1000. En ese momento pierde su turno de ejecución (y su saldo queda como 1000) y el usuario B inicia el retiro: lee el saldo que es 1000, retira 200 y almacena el nuevo saldo que es 800 y termina. El turno de ejecución regresa al usuario A el cual hace su depósito de 100, quedando saldo = saldo + 100 = 1000 + 100 = 1100. Como se ve, el retiro se perdió y eso le encanta al usuario A y B, pero al banquero no le convino esta transacción. El error pudo ser al revés, quedando el saldo final en 800.
• Postergación o Aplazamiento Indefinido(a): Esto se mencionó en el apartado anterior y consiste en el hecho de que uno o varios procesos nunca reciban el suficiente tiempo de ejecución para terminar su tarea. Por ejemplo, que un proceso ocupe un recurso y lo marque como 'ocupado' y que termine sin marcarlo como 'desocupado'. Si algún otro proceso pide ese recurso, lo verá 'ocupado' y esperará indefinidamente a que se 'desocupe'.
• Condición de Espera Circular: Esto ocurre cuando dos o más procesos forman una cadena de espera que los involucra a todos. Por ejemplo, suponga que el proceso A tiene asignado el recurso 'cinta' y el proceso B tiene asignado el recurso 'disco'. En ese momento al proceso A se le ocurre pedir el recurso 'disco' y al proceso B el recurso 'cinta'. Ahi se forma una espera circular entre esos dos procesos que se puede evitar quitándole a la fuerza un recurso a cualquiera de los dos procesos.
• Condición de No Apropiación: Esta condición no resulta precisamente de la concurrencia, pero juega un papel importante en este ambiente. Esta condición especifica que si un proceso tiene asignado un recurso, dicho recurso no puede arrebatársele por ningún motivo, y estará disponible hasta que el proceso lo 'suelte' por su voluntad.
• Condición de Espera Ocupada: Esta condición consiste en que un proceso pide un recurso que ya está asignado a otro proceso y la condición de no apropiación se debe cumplir. Entonces el proceso estará gastando el resto de su time slice checando si el recurso fue liberado. Es decir, desperdicia su tiempo de ejecución en esperar. La solución más común a este problema consiste en que el sistema operativo se dé cuenta de esta situación y mande a una cola de espera al proceso, otorgándole inmediatamente el turno de ejecución a otro proceso.
• Condición de Exclusión Mutua: Cuando un proceso usa un recurso del sistema realiza una serie de operaciones sobre el recurso y después lo deja de usar. A la sección de código que usa ese recurso se le llama 'región crítica'. La condición de exclusión mutua establece que solamente se permite a un proceso estar dentro de la misma región crítica. Esto es, que en cualquier momento solamente un proceso puede usar un recurso a la vez. Para lograr la exclusión mutua se ideo también el concepto de 'región crítica'. Para logar la exclusión mutua generalmente se usan algunas técnicas para lograr entrar a la región crítica: semáforos, monitores, el algoritmo de Dekker y Peterson, los 'candados'. Para ver una descripción de estos algoritmos consulte
• Condición de Ocupar y Esperar un Recurso: Consiste en que un proceso pide un recurso y se le asigna. Antes de soltarlo, pide otro recurso que otro proceso ya tiene asignado.
Los problemas descritos son todos importantes para el sistema operativo, ya que debe ser capaz de prevenir o corregirlos. Tal vez el problema más serio que se puede presentar en un ambiente de concurrencia es el 'abrazo mortal', también llamado 'trabazón' y en inglés deadlock. El deadlock es una condición que ningún sistema o conjunto de procesos quisiera exhibir, ya que consiste en que se presentan al mismo tiempo cuatro condiciones necesarias: La condición de no apropiación, la condición de espera circular, la condición de exclusión mutua y la condición de ocupar y esperar un recurso. Ante esto, si el deadlock involucra a todos los procesos del sistema, el sistema ya no podrá hacer algo productivo. Si el deadlock involucra algunos procesos, éstos quedarán congelados para siempre.
2.10.1 Exclusión mutua de secciones criticas.
Exclusión Mutua.

 Consiste en garantizar que durante la ejecución de una región crítica los recursos compartidos solo se asignen a uno y solo a uno de los procesos.

 Si un recurso compartido es una variable, la exclusión mutua asegura que a lo más un proceso a la vez ha accedido a ella durante la actualización crítica que conduce a valores temporalmente inestables. Consecuentemente los otros procesos ven solamente valores estables de las variables compartidas. Con los dispositivos compartidos la necesidad para la exclusión mutua puede ser incluso más obvia cuando uno considera el problema que puede provocar sus usos.
 Por ejemplo, supongamos que en el sistema existe un archivo formado por registros compuestos por 5 campos, figura # 18:



Figura # 18.  Registro de 5 campos.


Para que un registro sea valido debe estar totalmente actualizado, es decir, si se modifica el valor del campo A, el resto de los campos deben ser coherentes con el nuevo valor de dicho campo, ya que de otro modo el registro sería inconsistente.
 Si en el momento en que un proceso escribe o modifica un registro y existe otro proceso que realiza la lectura de ese mismo registro, y el primero de ellos sólo hubiese tenido tiempo de modificar el campo A, la información obtenida por el segundo proceso seria inconsistente. Para evitar esto se deben sincronizar los procesos de manera que mientras uno escribe, otro pueda leer.

 Esto no ocurre en aquellos casos en que dos procesos tratan de leer en el mismo archivo, aún coincidiendo en el mismo registro.

 Generalizando. Supongamos que los dos procesos que coinciden en el mismo registró, uno esta escribiendo y el otro leyendo, llamados ESCRIBIR y LEER,  se encuentran en un sistema monoprocesador multiprogramado y son los únicos presentes en ese momento, ver figura # 19



Figura  # 19.  Concurrencia

En el momento de un cambio de proceso del uno al otro se pueden producir las siguientes situaciones:

. Sin sincronización entre procesos. Puede darse el caso de que ESCRIBIR esté actualizando un registro y se quede a medías, sorprendiéndole el cambio de proceso, por tanto, terminará de escribirlo cuando vuelva a hacer uso del procesador. Con el cambio le tocará el turno al proceso LEER, que accederá a dicho registro pudiendo leerlo completamente. Es evidente que los datos leídos serán inconsistentes.

. Con sincronización entre procesos.  Supongamos algún mecanismo que prohíba la lectura (bloqueo de registros) a cualquier proceso, mientras el proceso ESCRIBIR esté realizando alguna operación. En este caso, LEER, al hacer uso del procesador que se encuentra bloqueado, quedaría en espera de que el registro quede totalmente escrito y se proceda a su desbloqueo, LEER pasaría a estado bloqueado, ESCRIBIR terminaría su trabajo sobre el registro y en el siguiente cambio LEER procedería a hacer el suyo.

 Esta sincronización por la cual una actividad impide que otras puedan tener acceso a un dato mientras se encuentra realizando una operación sobre el mismo es lo que se conoce como exclusión mutua.
 La zona de código de un proceso que no puede ser interrumpida por otro, por los motivos expuestos anteriormente se le llama Región Crítica.

http://eduadis.itlapiedad.edu.mx/~hocegueras/so1/so1_214.html

Regiones críticas.


Es el conjunto de actividades elementales cuya ejecución exige el monopolio de recursos. Por ejemplo, para indicar que alguna acción se realizará con acceso exclusivo a ciertos datos compartidos.

    Región  datos - compartidos   do   acción


 ¿Como evitar la región critica?. La clave para prevenir el problema aquí y en muchas otras situaciones en que interviene la memoria compartida, archivos compartidos y todo lo que se comparte, consiste en determinar alguna manera de prohibir que un proceso lea y escriba los datos compartidos al mismo tiempo.


De otra manera lo que se necesita es la sincronización. Una manera de asegurar de que si un proceso ésta utilizando una variable o archivo compartido, es que los otros procesos no pueden hacer lo mismo.


 Para tener una solución adecuada a la región crítica se necesita que se cumplan cuatro condiciones:


1. Nunca dos procesos pueden encontrarse simultáneamente dentro de sus regiones críticas.

2. No se hacen suposiciones acerca de las velocidades relativas de los procesos o del
     Número  de CPU.

3. Ningún proceso suspendido fuera de la región crítica debe bloquear a otros procesos.

4. Nunca un proceso debe querer entrar en forma arbitraria en su región crítica.


Representación de regiones criticas, observe figura # 17 



Figura # 17.   Representación de regiones criticas


Cuando se diseña un  proceso que debe contener una o varias regiones críticas se deben  de tomar en cuenta las siguientes consideraciones:

 . La región crítica debe ser ejecutada lo más rápido posible.
 . Un programa no debe ínter bloquearse en una región crítica.
 . Las regiones críticas deben ser programadas con mucho cuidado (no se permiten
              Ciclos indefinidos).
 . Mientras un proceso está en su región crítica otros procesos pueden continuar
              Ejecutándose  fuera de las regiones críticas.
 . Cuando se tienen procesos que comparten datos, si un proceso deja la región
              Crítica otro de los procesos que espera a entrar en su región crítica puede proceder.


 Cuando el proceso termina, voluntaria o involuntariamente, el sistema operativo debe de realizar la limpieza propia de fin de proceso y liberar la exclusión mutua de otros procesos.
http://eduadis.itlapiedad.edu.mx/~hocegueras/so1/so1_213.html
La exclusión mutua: Forma de asegurar que si un proceso está usando una variable o archivo compartido, los otros procesos quedarán excluidos de hacer lo mismo.
Los procesos pueden tener en su código secciones en que realizan cálculos internos y operaciones que no dan lugar a condiciones de competencia. Sin embargo existen secciones de programa en que el proceso está accediendo a recursos compartidos que pueden dar pié a condiciones de competencia.
La parte del programa en que se accede a un recurso compartido se denomina sección o región crítica (requisito necesario, pero no suficiente). Los requisitos para que procesos paralelos cooperen de manera correcta usando datos compartidos son los siguientes:
 Dos procesos nunca pueden estar simultáneamente dentro de sus regiones críticas.
 No se puede suponer nada acerca de las velocidades de ejecución de los procesos o el número de las CPU.
 Ningún proceso que se ejecute fuera de su región crítica puede bloquear a otros procesos.
 Ningún proceso deberá tener una espera indefinida para entrar en su región crítica.
La exclusión mutua debe ponerse en práctica sólo cuando los procesos obtienen acceso a datos compartidos modificables; cuando los procesos realizan operaciones que no entran en conflicto con otras, deben permitirse que procedan concurrentemente. Cuando un proceso obtiene acceso a datos compartidos modificables, se dice que se encuentra en una sección crítica. Es evidente que, para evitar la clase de problemas observados en la sección anterior, debe asegurarse que cuando un proceso se encuentre en una sección crítica, los demás procesos (o al menos los que tengan acceso a los datos compartidos) no pueden entrar a sus propias secciones críticas.
Mientras un proceso se encuentra en su sección crítica, otros procesos pueden, claro está, seguir ejecutándose fuera de sus secciones críticas. Cuando un proceso abandona su región crítica, otro proceso que espera entrar en su propia sección crítica (si existe algún proceso en espera). Lograr que se cumpla la exclusión mutua es uno de los problemas fundamentales de la programación concurrente. Se han propuesto muchas soluciones, algunas de software y otras de hardware, algunas sencillas y otras complejas, y algunas que requieren la cooperación voluntaria de los procesos y otras que exigen un escrito ajuste a rígidos protocolos.
Encontrarse dentro de una región crítica es un estado especial concedido a un proceso. El proceso tiene acceso exclusivo a los datos compartidos y los demás procesos que requieran acceso a los datos en ese momento deben esperar. Así pues, las secciones críticas deben ejecutarse tan rápido como sea posible; un proceso no se debe bloquear dentro de su propia sección crítica y las secciones críticas deben codificarse con mucho cuidado (para evitar, por ejemplo, la posibilidad de ciclos infinitos).
Si un proceso de una sección crítica termina, ya sea voluntaria o involuntariamente, el sistema operativo, al realizar su mantenimiento de terminaciones, debe liberar la exclusión mutua de manera que otros procesos puedan entrar en sus regiones críticas.
El problema de la Sección Crítica
• n procesos compitiendo para utilizar algún dato compartido.
• Cada proceso tiene un segmento de código, llamado sección crítica, en el que se accede al dato compartido.
• Problema – asegurarse de que cuando un proceso esta ejecutándose en su sección crítica, a ningún otro proceso se le permite ejecutar la suya.
• Estructura del proceso Pi
repeat
entry section
sección crítica
exit section
sección restante
until false;

Solución al problema de la Sección Crítica
 Una solución al problema de la sección crítica debe satisfacer los siguientes tres requerimientos:
1. Exclusión Mútua. Si un proceso Pi esta ejecutandose en su sección crítica, entonces ninguno de los otros procesos puede estar en su sección crítica
2. Progreso. Si ningún proceso esta ejecutándose en su sección crítica y existen procesos que quieren entrar en su sección crítica, entonces la selección del próximo proceso que entrará a la sección crítica no puede ser pospuesta indefinidamente.
3. Espera limitada. Debe existir un límite del número de veces que se les permite a otros procesos entrar en sus secciones críticas en el intervalo entre que un proceso ha hecho un requerimiento para entrar en su sección crítica y que se le concede el permiso.
 Se supone que cada proceso se ejecuta a velocidad distinta de cero.
 Ninguna suposición respecto a la velocidad relativa de los n procesos.
Intentos iniciales para resolver el problema
 Inhibir las interrupciones.
 Solo dos procesos, P0 and P1
 Estructura general del proceso Pi
repeat
entry section
sección crítica
exit section
sección restante
until false;
 Los procesos pueden compartir algunas variables comunes para sincronizar sus acciones.
Algoritmo 1
Variables compartidas:
– var turn: (0..1);
inicialmente turn = 0
– turn = i ? Pi puede entrar en su sección crítica
Proceso Pi
repeat
while turn ? i do no-op;
sección crítica
turn := j;
sección restante
until false;
Satisface la condición de exclusión mútua, pero no la de progreso (si turn=0 y P1 esta listo para entrar en su sección crítica, P1 no puede hacerlo, incluso aunque P0 este en la sección restante)
Algoritmo 2
Variables compartidas
– var flag: array [0..1] of boolean;
inicialmente flag [0] = flag [1] = false.
– flag [i] = true ? Pi listo para entrar en su sección crítica
Proceso Pi
repeat
flag[i] := true;
while flag[j] do no-op;
sección crítica
flag [i] := false;
sección restante
until false;
Satisface la exclusión mútua, pero no el requerimiento de progreso. (P0 pone flag[0 ] =true y P1 pone flag[1 ] =true; cada uno esperando al otro indefinidamente)
Algoritmo 3
- Combinación de las variables compartidas de los algoritmos 1 y 2.
- Proceso Pi
repeat
flag [i] := true;
turn := j;
while (flag [j] and turn = j) do no-op;
sección crítica
flag [i] := false;
sección restante
until false;
- Cumple los tres requerimientos; resuelve el problema de la sección crítica para dos procesos.

Algoritmo del panadero
• Antes de entrar a su sección crítica, los procesos reciben unnúmero. El que posea el número menor entra en la sección crítica.
• Si los procesos Pi y Pj reciben el mismo número, si i < j, entonces Pi es servido primero; si no lo es Pj .
• El esquema de numeración siempre genera números en orden creciente; por ejemplo 1,2,3,3,3,3,4,5...

2.10.2 Sincronización de procesos en S.C.
Sincronización.

 En procesos concurrentes, la ejecución de un proceso se desarrolla en forma asíncrona respecto a los otros. Sin embargo cuando dos,  o más procesos necesitan entrar en región crítica, es necesario que exista una sincronización entre ellos a fin de garantizar que al menos uno y solo un proceso entrará en región crítica.

 Si una actividad desea impedir que otra acceda a ciertos datos compartidos, mientras no se cumpla una determinada condición, debemos sincronizar las actividades con dicha condición. Por tanto, la sincronización es un elemento necesario para asegurar la exclusión mutua.


Existen tres algoritmos diseñados para este fin, son los siguientes:


• Espera Activa.

• Espera no Activa

• Mecanismos de Hardware.



Algoritmo de Espera activa.

  Estos algoritmos establecen la espera de entrada a la región crítica con un bucle que será roto en el momento en que se cumpla una determinada condición. Se, les llama así por que el proceso no queda bloqueado en su ejecución, sino que constantemente compite por el procesador. Entre los distintos algoritmos de este tipo existentes podemos citar:

. Espera con mutex.    Algoritmo  que utiliza un  switch (MUTEX)  a  través del cual se produce la sincronización.
 . Alternancia.    Ligeramente mejor que el anterior, utiliza también una
variable turno para realizar el sincronismo entre los
Procesos.
 . Algoritmo de DEKKER.    Resuelve el problema mediante la solución propuesta
                                                           por DEKKER, basando su funcionamiento en una
Tabla unidimensional de dos elementos lógicos
(Switches).

   Algoritmo de Espera no activa.

 Son los algoritmos que establecen la espera para entrar en la región crítica bloqueando, el proceso, haciendo que deje de competir por el procesador hasta que se cumpla la condición de desbloqueo.

 Entre estos algoritmos existen los siguientes:

. Semáforos: Para eliminar los problemas que se producen con los algoritmos de espera activa, fundamentalmente los referidos a la sobrecarga que producen en el sistema, Dijkstra(1965) diseño un mecanismo basado en una variable entera utilizada como contador de peticiones de entrada a una sección crítica. Esta variable es compartida por todos los procesos del sistema. Este nuevo tipo de variable se denominó semáforo, por su capacidad de gestionar el tráfico de los proceso que desean acceder a datos compartidos.

 Con este sistema,  cuando un proceso intente entrar en una región crítica mientras otro está accediendo a los datos compartidos, se bloqueará  de igual manera que cuando un proceso accede a un recurso que está ocupado.
Un semáforo se define como una variable entera que puede inicializarse y su valor no debe ser negativo y solo puede ser manipulada por las operaciones P y V.

. Operaciones P y V. Estas operaciones son  indivisibles, es decir que cuando un proceso ejecuta una de ellas no puede ser interrumpida.

Operación V: Esta operación consiste en incrementar en uno el valor del semáforo sobre el que actúa, también es conocida como signal. Es una operación de liberación.
 Así, si se tiene un semáforo S, V de S  V(S)  o signal(S)   causara  S=S+1. V(MUTEX)  - libera

Operación P: Bloqueo, decrementa en uno el valor del semáforo sobre el que actúa siempre y cuando el valor del semáforo es   >=0  (positivo) también se le conoce en la literatura inglesa como Wait.  Por ejemplo si tenemos P(S), Wait(S)  si  S=S-1. P(MUTEX) - Espera el proceso.

De las definiciones anteriores se puede observar que el valor de un semáforo esta relacionado con el número de veces que se ejecutan, dichas operaciones es decir, el valor del semáforo S es igual a su valor inicial más número de operaciones V menos número de operaciones P realizadas por ese semáforo.

  VAL(S) = C(S) + NV(S) - NP(S)  NP( ) <= NV( ) +1

  VALOR            VALOR INICIAL

 Por definición se tiene que el valor del semáforo debe ser mayor que cero, VAL(S)>0. En el caso cuando el valor del semáforo es cero que relación nos queda:

  NP(S) = C(S) + NV(S)

 Es importante señalar que la relación anterior será siempre valida independientemente del número de operaciones P y V ejecutadas sobre el semáforo.


. Regiones críticas: Son sistemas que permiten establecer protecciones contra una mala utilización de los usuarios. Para ello sólo permiten que los datos compartidos se puedan acceder desde determinadas regiones quedando transparentes desde el resto.

Tiene inconvenientes relacionados con la sincronización y no permite que varias actividades puedan realizar operaciones de lectura simultánea.

. Regiones criticas condicionales:  Es una mejora del método anterior tratando de resolver algunos problemas de sincronización que se presentan.

. Monitores: Uno de los problemas en los mecanismos anteriores es que el programador tiene que proporcionar de forma explícita el modo de sincronización. Para evitarlo B. Hansen y C.A.R. Hoare desarrollarón un nuevo mecanismo denominado Monitor, que debe ser soportado por el lenguaje correspondiente.

 Un monitor permite compartir, segura y eficientemente, datos entre varias actividades, garantizando la exclusión mutua, sin necesidad de que el programador tenga que suministrarla explícitamente.
 Se basa en dos premisas: la primera es la abstracción de datos consistente en una técnica capaz de separar las operaciones a ejecutar sobre los datos, de los detalles de diseño propio de los mismos (los lenguajes Modula y Ada soportan este tipo de estructuras). La segunda es que realizan la exclusión mutua de forma implícita.

 La finalidad más útil de los monitores es reunir todas las funciones que operan sobre un conjunto de datos compartidos en un sólo módulo, de manera que todos los accesos a esos datos estarán forzados a utilizar dichas funciones.

. Contadores de eventos: Es un mecanismo para sincronizar actividades sin que sea necesario forzar la exclusión mutua, ya sea por que no deseamos limitar la concurrencia de las actividades, o simplemente porque no lo necesitamos. Se basa en una variable entera que cuenta determinadas operaciones.

. Mensajes: Mecanismo que permite intercambiar información necesaria durante el desarrollo normal de un proceso en ejecución. Es más un mecanismo de cooperación que de sincronización.


Existen dos  tipos de comunicación entre procesos:

- Directa:      Envió y recepción de mensajes entre si; de manera que se asocia un enlace vi direccional único entre cada dos procesos.

- Indirecta: Mensajes enviados y recibidos a través de mail boxees o buzones de correo. Con este método cada proceso puede estar relacionado con tantos buzones como desee consiguiendo comunicarse con tantos procesos como sea necesario.

Mecanismos de Hardware

 Son instrucciones hardware que aseguran la exclusión mutua. Entre las más utilizadas son las siguientes:

. Deshabilitar interrupciones.
 Se puede forzar la exclusión mutua deshabilitando las interrupciones mientras haya alguna actividad en la región crítica. De este modo, dicha actividad no podrá ser interrumpida y, por tanto, no se podrá producir ningún cambio de proceso. La habilitación y deshabilitación se realiza con una instrucción máquina, es una operación rápida.

. Instrucción TEST-AND-SET.
 Forza la exclusión mutua. La ventaja es que no puede ser interrumpida por que no muchas computadoras la poseen.

. Lock.
 Se basa en la instrucción anterior y permite el acceso a la región crítica a un proceso en caso de no existir otra actividad dentro de su región crítica, no permitiendo en caso contrario.

¿Como resolver la exclusión mutua usando semáforos?.

 Para resolver el problema de debe hacer lo siguiente:

 1.- Identificar todas las regiones críticas.
 2.- Definir tantos semáforos como regiones críticas se tengan, dichos semáforos se
      inicializarán con 1.
 3.- C/U de las regiones críticas será antecedida por la operación P y precedida por la
       operación V.
   Ejemplo:  MUTEX es el semáforo
     Región crítica.

Con lo anterior solo un proceso podrá entrar a la región crítica con lo que se esta asegurando la exclusión mutua.
      MUTEX = 1

* Que pasa si se tiene:

A) P(MUTEX)   Entra el proceso, se decrementa en uno el semáforo
  SECCION CRITICA pero no libera, por lo tanto hay un dead lock, no
 P(MUTEX)   hay sincronización entre procesos ni exclusión
mutua

B)  V(MUTEX)   Sale el proceso se incrementa en uno el semáforo
 SECCION CRITICA libera el proceso, por lo tanto no hay dead lock, no
 V(MUTEX)   origina proceso de exclusión mutua.

C)  V(MUTEX)   Sale el proceso se incrementa en uno el semáforo
 SECCION CRITICA pero no libera, por lo tanto no hay dead lock.
 P(MUTEX)

D) P(MUTEX)   Entra el proceso consume y libera, por lo tanto no
 SECCION CRITICA hay dead lock, y da solución a la exclusión mutua
 V(MUTEX)   y a la sincronización.

Pregunta. * Varios procesos actualizan en forma concurrente a una lista ligada.

a) Que problema se puede producir.
 R.- Se puede producir un problema de sincronización y no hay exclusión mutua.
b) Es un problema de exclusión mutua.
 R.- Exclusión mutua.
c) Como resolver el problema.
 R.- Dando solución a la exclusión mutua.
* Si las operaciones P y V no fueran atómicas, la exclusión mutua seria violada.
 R.- Si por que los procesos pueden tomar el mismo valor y  no se incrementa dos veces sino  solo una.

http://eduadis.itlapiedad.edu.mx/~hocegueras/so1/so1_215.html

Problemas clásicos de sincronización.
 Este tipo de problemas constituyen ejemplos de una amplia clase de problemas de control  de concurrencia. Estos problemas se utilizan para probar casi todos los esquemas de sincronización propuestos. En las soluciones se emplean semáforos para la solución.

* El problema de buffer limitado.
 Supongamos que el depósito consiste en n buffers, cada uno capaz de almacenar un elemento. El semáforo MUTEX proporciona la exclusión mutua para los accesos al depósito de buffers y se le asigna un valor inicial de 1. Los semáforos vacíos y llenos cuentan el número de buffers vacíos y llenos, respectivamente. El semáforo vacío recibe 1 un valor inicial n; al semáforo lleno se le asigna el valor inicial 0.

* El problema de los lectores y escritores.
 Un objeto de datos (como un archivo o un registro) va a ser compartido por  varios procesos concurrentes. Algunos de estos procesos sólo quieren leer el contenido del objeto compartido, mientras que otros quieren actualizarlos  (o sea, leerlo y escribirlo), hacemos una distinción entre estos dos tipos de procesos refiriéndonos a los procesos interesados sólo en leer como lectores y escritores y a los demás como escritores. Obviamente, el que dos lectores tengan acceso simultáneo al objeto de datos compartido no tendrá ningún efecto adverso; sin embargo, si un escritor y otro proceso (ya sea lector o escritor) tiene acceso simultáneo al objeto compartido, puede surgir el caos.
 Para asegurar que no surjan estas dificultades, es necesario que los escritores tengan acceso exclusivo al objeto compartido. A este problema de sincronización se le conoce como problema de los lectores y escritores, el cual es ha utilizado para probar casi todas las nuevas primitivas de sincronización.

* El problema de los filósofos comensales.
 Cinco filósofos pasan su vida comiendo u pensando. Los filósofos comparten una mesa circular rodeada por cinco sillas, una para cada uno de ellos. En el centro de la mesa se encuentra una fuente de arroz, y también sobre la mesa hay cinco palillos chinos. Cuando un filósofo piensa, no interactúa con sus colegas. Ocasionalmente, un filósofo tiene hambre y trata de coger los dos palillos que están más cerca de él (los palillos colocados entre él y sus vecinos de la derecha y de la izquierda). Un filósofo sólo puede coger un palillo a la vez y, obviamente, no puede ser el que esta en la mano de un vecino. Cuando un filósofo ambiento tiene sus dos palillos al mismo tiempo come sin soltarlos. Cuando termina de comer, coloca ambos palillos sobre la mesa y comienza a pensar otra vez.

* Problema del productor consumidor. 
 En un contexto de procesos concurrentes, se tiene un conjunto de procesos productores de mensajes y otro conjunto de procesos consumidores de mensajes. La zona donde se depositarán y recogerán los mensajes es un buffer de tamaño n (n localidades).

 Tanto productores como consumidores ejecutaran cíclicamente los siguientes algoritmos. Ver figura # 20.


Figura # 20. Productor consumidor.


El recurso que se va a compartir es el buffer por lo tanto la sección critica será el acceso y  manipulación de dicho  buffer.


*  Para resolver el problema de exclusión mutua será necesario definir un semáforo para controlar el acceso al buffer, figura # 21.


Figura # 21.  Definición  de  un  semáforo   para   controlar   el   accedo  a  buffer.

- Cuando el consumidor se apodera del buffer P ( ) !Sorpresa  esta vacío ¡

   Productor gana
   se apodera del buffer
   ¡¡¡sorpresa el buffer   esta lleno!!!
   no va a poder depositar
   y por lo tanto va a liberar el buffer
   nunca hace V( ).

• Productor consumidor utilizando espera activa, figura # 22.

   Productor    Consumidor

  Produce msg.     Lock (existe msg.)
  Lock (espacio disponible)   Lock (acceso a buffer)
  Lock (acceso a buffer)   extrae msg.
  Deposita msg.    Unlock (acceso a buffer)
  Unlock (acceso a buffer)   Unlock (espacio disponible)
  Unlock (existe msg.)    Consume msg.
 Figura # 22.
 Problema de sincronización. La sincronización entre productor y consumidor es necesaria debido a lo siguiente: Los productores no deben depositar mensajes si el buffer se encuentra lleno y los consumidores no deben accesar el buffer cuando este se encuentre vació.
 Para resolver el problema de definirá un semáforo que defina el espacio disponible y será inicializado con un valor igual a n y un semáforo que defina la existencia de mensaje el cual será  inicializado con un 0.

  Productor     Consumidor
  produce msg.     P (existe msg.)    
      X P (espacio disponible)       P (acceso s buffer)
  P (acceso a buffer)      extrae msg.
 *   deposita msg    V (acceso a buffer)
  V (acceso a buffer)    V (espacio disponible)
            X V (existe msg)       Consume msg.


             Solución   a  la   exclusión  mutua  X –

- Solución de la sincronización
    
    - Buffer lleno  Espacio disponible=N, existe msg=0.
Casos críticos
  - Buffer vacío

http://eduadis.itlapiedad.edu.mx/~hocegueras/so1/so1_216.html

2.10.2.1 Mecanismo de semáforos.
Semáforos
Son una herramienta de sincronización. Es una variable protegida que solo puede ser modificada por la rutina de inicialización y por otras dos operaciones atómicas:
P( ) <- wait
V( ) <- signal
Las operaciones a las cuales se puede acceder son:
Inicialización: Crea un nuevo semáforo asignándole un valor inicial
P(s): while (s=0) do no_op ATÓMICA
s:=s-1
V(s): s:=s+1 ATÓMICA
Existen básicamente dos tipos de semáforos:
• Semáforos contadores: Toman valores positivos mayores o iguales a 0. Se utilizan para sincronización de procesos.
• Semáforos binarios: Toman los valores 0 ó 1 y se utilizan para exclusión mutua.
A continuación se presenta una solución mediante semáforos del problema productor/consumidor.
#define N 100
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
void productor(void)
int item;
while(1)
produce_item(item);
down(empty);
down(mutex);
enter_item(item);
up(mutex);
up(full);

void consumidor(void)
 int item;
while(1)
down(full);
down(mutex);
remove_item(&item);
up(mutex);
up(empty);
consume_item(item);

En este caso tenemos la utilización de 3 semáforos, uno destinado al control de la exclusión mutua y los otros dos destinados a la sincronización de los procesos para el control de buffer lleno y vacío.
Podríamos utilizar semáforos para un algoritmo de espera ocupada con n procesos, pero los n procesos que están ejecutando el while de la función P(s) van a la cola de ready en un instante de tiempo reduciendo la performance general del equipo.
Para evitar la espera ocupada se crea un semáforo que sea un registro de un nuevo tipo:
Semáforo = Record
Valor:Integer
L:Lista_de_Procesos
End
P(s)
s.Valor:= s.valor - 1
if s.Valor < 0 then agregar este proceso a s.L
bloquear;
end
V(s)
s.Valor:=s.Valor + 1
if s.Valor  0 then quitar un proceso y a s.L
despertar(y)
Semáforos
Un semáforo es un tipo de datos abstracto que permite el uso de un recurso de manera exclusiva cuando varios procesos están compitiendo.
El tipo de datos abstracto cumple la siguiente semántica:
• El estado interno del semáforo cuenta cuantos procesos todavía pueden utilizar el recurso. Se puede realizar, por ejemplo, con un número entero que nunca llega a ser negativo.
• Exiten tres operaciones con un semáforo: init(), wait(), y signal() que realizan lo siguiente:
init()
: Inicializa el semáforo antes de que cualquier proceso haya ejecutado ni una operación wait() ni una operación signal() al límite de número de procesos que tengan derecho a acceder el recurso. Si se inicializa con 1, se ha contruido un semáforo binario.
wait()
: Si el estado indica cero, el proceso se queda atrapado en el semáforo hasta que sea despertado por otro proceso. Si el estado indica que un proceso más puede acceder el recurso se decrementa el contador y la operación termina con exito.
La operación wait() tiene que estár implementada como una instrucción atómica. Sin embargo, en muchas implementaciones la operación wait() puede ser interrumpida. Normalmente existe una forma de comprobar si la salida del wait() es debido a una interrupción o porque se ha dado acceso al semáforo.
signal()
: Una vez se ha terminado el uso del recurso, el proceso lo señaliza al semáforo. Si queda algún proceso bloqueado en el semáforo uno de ellos sea despertado, sino se incrementa el contador.
La operación signal() también tiene que estár implementada como instrucción atómica. En algunás implementaciones es posible comprobar si se haya despertado un proceso con exito en caso que hubiera alguno bloqueado.
Para despertar los procesos se puede implementar varias formas que se destinguen en sus grados de justicia, por ejemplo con un simple sistema tipo FIFO.
El acceso mutuo a regiones críticas se arregla con un semáforo que permita el acceso a un sólo proceso
S.init(1)

P1                         P2
a: loop                        loop
b:   S.wait()                    S.wait()
c:   critical region             critical region
d:   S.signal()                  S.signal()
e:   non-critical region         non-critical region
f: endloop                     endloop
Observamos los siguiente detalles:
• Si algún proceso no libera el semáforo, se puede provocar un bloqueo.
• No hace falta que un proceso libere su propio recurso, es decir, la operación signal() puede sea ejecutada por otro proceso.
• Con simples semáforos no se puede imponer un orden en los procesos accediendo a diferentes recursos.
Si existen en un entorno solamente semáforos binarios, se puede simular un semáforo general usando dos semáforos binarios y un contador, por ejemplo, con las variables delay, mutex y count.
La operación init() inicializa el contador al número máximo permitido. El semáforo mutex asegura acceso mutuamente exclusivo al contador. El semáforo delay atrapa a los procesos que superan el número máximo permitido.
La operación wait() se implementa de la siguiente manera:
  delay.wait()
  mutex.wait()
  decrement count
  if count greater 0 then delay.signal()
  mutex.signal()
y la operación signal() se implementa de la siguiente manera:
  mutex.wait()
  increment count
  if count equal 1 then delay.signal()
  mutex.signal()
Unas principales desventajas de semáforos son:
• no se puede imponer el uso correcto de los wait()s y signal()s
• no existe una asociación entre el semáforo y el recurso
• entre wait() y signal() el usuario puede realizar cualquier operación con el recurso
http://trevinca.ei.uvigo.es/~formella/doc/cd04/node64.html

2.10.2.2 Mecanismo de monitores.
Monitores
Todas las estructuras que hemos visto hasta ahora siguen provocando problemas para el programador:
• el control sobre los recursos está distribuido por varios puntos de un programa
• no hay protección de las variables de control que siempre fueron globales
Por eso se usa el concepto de monitores que implementan un nivel aún más alto de abstracción facilitando el acceso a recursos compartidos.
Un monitor es un tipo de datos abstracto que contiene
• un conjunto de procedimientos de control de los cuales solamente un subconjunto es visible desde fuera
• un conjunto de datos privados, es decir, no visibles desde fuera
El acceso al monitor está permitido solamente a través de los procedimientos públicos y el compilador garantiza exclusión mutua para todos los procedimientos. La implementación del monitor controla la exclusión mutua con colas de entrada que contengan todos los procesos bloqueados. Pueden existir varias colas y el controlador del monitor elige de cual cola se va a escoger el siguiente proceso para actuar sobre los datos. Un monitor no tiene acceso a variables exteriores con el resultado de que su comportamiento no puede depender de ellos.
Una desventaja de los monitores es la exclusividad de su uso, es decir, la concurrencia está limitada si muchos procesos hacen uso del mismo monitor.
Un aspecto que se encuentra en muchas implementaciones de monitores es la sincronización condicional, es decir, mientras un proceso está ejecutando un procedimiento del monitor (con exclusión mutua) puede dar paso a otro proceso liberando el cerrojo. Estas operaciones se suele llamar wait() o delay(). El proceso que ha liberado el cerrojo se queda bloqueado hasta que otro proceso le despierta de nuevo. Este bloqueo temporal está realizado dentro del monitor (dicha técnica se refleja en Java con wait() y notify()).
La técnica permite la sincronización entre procesos porque actuando sobre el mismo recurso los procesos pueden cambiar el estado del recurso y pasar así información de un proceso al otro.
Lenguajes de alto nivel que facilitan la programación concurrente suelen tener monitores implementados dentro del lenguaje (por ejemplo refJavaMonitoresJava usa el concepto de monitores para realizar el acceso mutuamente exclusivo a sus objetos).
El uso de monitores es bastante costoso, porque se pierde eficiencia por tanto bloqueo de los prosesos. Por eso se intenta aprovechar de primitivas más potentes para aliviar este problema, como vemos en la siguiente sección.
http://trevinca.ei.uvigo.es/~formella/doc/cd04/node67.html

Monitores
Es un tipo de procedimientos, variables y estructuras de datos que se agrupan en un tipo de modulo especial. Tienen una propiedad importante: solo un proceso puede estar activo en un monitor en un instante de tiempo.
Los monitores proveen un nuevo tipo de variables de condición con dos operaciones que operan sobre el (solo se usan dentro del procedimiento de el monitor).
Wait -> wait(a) : produce que el proceso que ejecuta la instrucción sea interrumpido y removido de la cola de ready hasta que otro proceso lo habilite ejecutando la instrucción signal( )con la misma variable de condición.
Signal -> signal(a) : Habilita la ejecución de algún proceso en espera por la ejecución de la instrucción wait con la misma variable de condición.

2.10.3 Interbloqueo (DeadLock).
Deadlocks
Si un conjunto de procesos esta en estado de espera por recursos y nunca cambia de estado porque los recursos por los que espera están siendo utilizados por otros procesos en estado de espera tenemos un DEADLOCK. Los recursos son la memoria, dispositivos de E/S, semáforos, archivos, etc. La forma en que un proceso hace uso de un recurso es:
Solicitud: si el recurso esta disponible se le otorga, si no el proceso pasa a estado de espera.
Uso: El proceso utiliza el recurso
Liberación: el proceso debe liberar el recurso.
Condiciones Necesarias para que se produzca DEADLOCK
Si se presentan simultáneamente las cuatro siguientes condiciones el sistema esta en DEADLOCK.
1. EXCLUSION MUTUA: Por lo menos un proceso que tenga otorgado un recurso en forma exclusiva.
2. USO Y ESPERA: Debe existir al menos un proceso que este haciendo uso de un recurso y que este esperando por otros recursos asignados a otros procesos.
3. NO INTERRUPCION: Los recursos no pueden ser retirados al proceso. Si un proceso hace uso de un recurso no le podrá ser retirado hasta que voluntariamente el proceso lo libere.
4. ESPERA CIRCULAR: Debe existir un conjunto de procesos P1.....Pn tal que P1 espera por un recurso utilizado por P2,......,Pn espera por un recurso utilizado por P1.
Resourse Allocation Graph(Grafo de utilizacion de recursos)
Conjunto de Vértices: U =P U R
P=P1,P2,....,Pn
R=R1,R2,...,Rn
Conjunto de Aristas:
Una arista de un proceso Pi a un Recurso Rj significa que el proceso i esta haciendo una solicitud por el recurso Rj.
Una arista del recurso Rj al proceso Pi, significa que el recurso esta asignado al proceso.
Si un RAG no tiene ciclos el sistema no esta en DEADLOCK, sis si los tiene no se puede afirmar nada.
Mecanismos para tratar con Deadlocks
Evasion de Deadlocks
Si se tiene cuidado al en la forma de asignar los recursos se pueden evitar situaciones de Deadlock. Supongamos un ambiente en el que todos los procesos declaren a priori la cantidad máxima de recursos que habá de usar.
Estado Seguro: un estado es seguro si se pueden asignar recursos a cada proceso (hasta su máximo) en algún orden sin que se genere Deadlock. El estado es seguro si existe un ordenamiento de un conjunto de procesos P1...Pn tal que para cada Pi los recursos que Pi podrá utilizar pueden ser otorgados por los recursos disponibles mas los recursos utilizados por los procesos Pj,j<i. Si los recursos solicitados por Pi no pueden ser otorgados, Pi espera a que todos los procesos Pj hayan terminado.
Algoritmo del banquero de Dijkstra
Asigna peticiones de recursos siempre que las mismas den como resultado estados seguros. Solicitudes que den como resultado estados inseguros serán negadas hasta que puedan ser satisfechas. Este algoritmos evita situaciones de Deadlock asignando los recursos en forma correcta.
Las debilidades del algoritmo son: que requiere que la cantidad de recursos del sistema sea constante, requiere una cantidad de procesos constante y requiere que los procesos garanticen que los recursos van a ser devueltos en un intervalo finito de tiempo.

En el área de la informática, el problema del deadlock ha provocado y producido una serie de estudios y técnicas muy útiles, ya que éste puede surgir en una sola máquina o como consecuencia de compartir recursos en una red.
En el área de las bases de datos y sistemas distribuidos han surgido técnicas como el 'two phase locking' y el 'two phase commit' que van más allá de este trabajo. Sin embargo, el interés principal sobre este problema se centra en generar técnicas para detectar, prevenir o corregir el deadlock.
Las técnicas para prevenir el deadlock consisten en proveer mecanismos para evitar que se presente una o varias de las cuatro condiciones necesarias del deadlock. Algunas de ellas son:
• Asignar recursos en orden lineal: Esto significa que todos los recursos están etiquetados con un valor diferente y los procesos solo pueden hacer peticiones de recursos 'hacia adelante'. Esto es, que si un proceso tiene el recurso con etiqueta '5' no puede pedir recursos cuya etiqueta sea menor que '5'. Con esto se evita la condición de ocupar y esperar un recurso.
• Asignar todo o nada: Este mecanismo consiste en que el proceso pida todos los recursos que va a necesitar de una vez y el sistema se los da solamente si puede dárselos todos, si no, no le da nada y lo bloquea.
• Algoritmo del banquero: Este algoritmo usa una tabla de recursos para saber cuántos recursos tiene de todo tipo. También requiere que los procesos informen del máximo de recursos que va a usar de cada tipo. Cuando un proceso pide un recurso, el algoritmo verifica si asignándole ese recurso todavía le quedan otros del mismo tipo para que alguno de los procesos en el sistema todavía se le pueda dar hasta su máximo. Si la respuesta es afirmativa, el sistema se dice que está en 'estado seguro' y se otorga el recurso. Si la respuesta es negativa, se dice que el sistema está en estado inseguro y se hace esperar a ese proceso.
Para detectar un deadlock, se puede usar el mismo algoritmo del banquero, que aunque no dice que hay un deadlock, sí dice cuándo se está en estado inseguro que es la antesala del deadlock. Sin embargo, para detectar el deadlock se pueden usar las 'gráficas de recursos'. En ellas se pueden usar cuadrados para indicar procesos y círculos para los recursos, y flechas para indicar si un recurso ya está asignado a un proceso o si un proceso está esperando un recurso. El deadlock es detectado cuando se puede hacer un viaje de ida y vuelta desde un proceso o recurso. Por ejemplo, suponga los siguientes eventos:
evento 1: Proceso A pide recurso 1 y se le asigna.
evento 2: Proceso A termina su time slice.
evento 3: Proceso B pide recurso 2 y se le asigna.
evento 4: Proceso B termina su time slice.
evento 5: Proceso C pide recurso 3 y se le asigna.
evento 6: Proceso C pide recurso 1 y como lo está ocupando el proceso A, espera.
evento 7: Proceso B pide recurso 3 y se bloquea porque lo ocupa el proceso C.
evento 8: Proceso A pide recurso 2 y se bloquea porque lo ocupa el proceso B.
En la figura 5.1 se observa como el 'resource graph' fue evolucionando hasta que se presentó el deadlock, el cual significa que se puede viajar por las flechas desde un proceso o recurso hasta regresar al punto de partida. En el deadlock están involucrados los procesos A,B y C.
Una vez que un deadlock se detecta, es obvio que el sistema está en problemas y lo único que resta por hacer es una de dos cosas: tener algún mecanismo de suspensión o reanudación [Deitel93] que permita copiar todo el contexto de un proceso incluyendo valores de memoria y aspecto de los periféricos que esté usando para reanudarlo otro día, o simplemente eliminar un proceso o arrebatarle el recurso, causando para ese proceso la pérdida de datos y tiempo.
Deadlock
• Un S.O. tiene un número limitado de recursos y procesos que solicitan los recursos.
• ¶Como diseñador de un sistema operativo, ¿cuál es el problema para ti si algunos procesos un tu sistema están en deadlock esperando recursos?
• Los recursos retenidos por los procesos en deadlock no están disponibles para otros procesos, y los procesos en deadlock no pueden avanzar (es mal para los dueños de los procesos).
• Muchos SS.OO. modernos no tienen apoyo especial para prevenir deadlock (porque cuesta), pero es común en programación de sistemas en general (e.g., en programación distribuida).
Características de deadlock
• El sistema tiene recursos de varios tipos: memoria, archivos, grabadores, impresoras, etc. Podemos tener más de un ejemplar de un tipo de recurso (e.g., tres impresoras). Cada uno de los ejemplares pueden satisfacer un solicitud de un proceso para el recurso.
• Los recursos son compartibles y permiten acceso a muchos procesos (e.g., los archivos de sólo lectura) o no compartibles (e.g., un grabador).
• Ejemplo: Tres procesos en un sistema con tres grabadores, cada proceso tiene un grabador y cada uno necesita uno más.
• Condiciones necesarias de deadlock:
o ¶ Exclusión mutua. Por lo menos un recurso debe retenerse no compartido. ¿Por qué?
o Retención y espera. Debe haber un proceso que retenga por lo menos un recurso y espere adquirir más recursos retenidos por otros.
o No apropiación. Los recursos no se pueden expropiar. Los procesos liberan recursos sólo voluntariamente.
o Espera circular. Debe haber un conjunto P0, P1, ..., Pn de procesos en espera tales que P0 espere un recurso de P1, P1 un recurso de P2, ..., y Pn un recurso de P0.
• Podemos usar un grafo de asignación de recursos para describir deadlock. Tenemos procesos (círculos), recursos (rectángulos con un punto para cada ejemplar), aristas de solicitud y de asignación (cambio instantáneamente).
• Un grafo sin ciclos implica que no hay deadlock. Si hay un ciclo, es posible que exista deadlock. Un ciclo es una condición necesaria pero no suficiente para deadlock.
http://www.cs.virginia.edu/~knabe/iic2332/notes07.html
Análisis.
 Definición. Abraso Mortal (Dead lock) o también llamado ínter bloqueo. En un contexto de procesos concurrentes, si el análisis de recursos a compartir no se hace cuidadosamente, se puede tener el riesgo de que dos o más procesos acaparen algún recurso y que se pongan en espera de que otro u otros liberen los recursos para poder continuar su ejecución, de tal manera que cada proceso permanecerá en una espera indefinida (infinita), observe el ejemplo de la figura # 23 Ejemplo: Se tienen 2 procesos P1 y P2. Se tiene 2 recursos Impresora y Unidad de disco:


Figura # 23.    Dead Lock.
 Cuando un proceso espera un evento que nunca se va a dar y el otro también lo espera Dead lock de un recurso simple.
 Muchos de los dead lock se deben a que un proceso retiene un recurso que debe ser usado en forma exclusiva. Es decir, el proceso tiene un recurso que sólo puede ser usado por un usuario a la vez. A estos recursos se les conoce como reutilizables en serie.

Dead lock en sistemas de spool.

 Los sistemas de spool suelen ser los más propensos al dead lock. Varios trabajos parcialmente complejos que generan líneas de impresión a un archivo de spool pueden interbloquearse si el espacio disponible para trabajar se llena antes de completarse alguno de esos trabajos. La solución más común es limitar los spoolers de entrada de modo que no se lean más archivos cuando se llega al límite de su capacidad.

Postergación indefinida.
 En los sistemas que mantienen procesos en espera mientras realizan la asignación de recursos y/o procesan la planificación de decisiones, es posible que un proceso sea postergado de manera indefinida mientras otro reciben la atención del sistema. A esta situación se le conoce como postergación indefinida,  es diferente del dead lock pero sus consecuencias son igual de negativas.
 En algunos sistemas la postergación indefinida se evita aumentando la prioridad de un proceso mientras espera por un recurso, a esto se le llama envejecimiento.

Conceptos sobre recursos.
 Un sistema operativo es sobre todo un administrador de recursos, existen básicamente dos tipos de recursos:

* Recursos no apropiativos.   Un  recurso  que  no  se puede liberar antes de completar su  actividad sin perder la validez del proceso que lo usa, se dice que un recurso no apropiativo. Una impresora o una unidad de cinta no pueden ser liberados hasta que no termine su trabajo.
* Recursos apropiativos.  Un  recurso  que  puede  ser  usado  temporalmente  por  varios procesos sin comprometer el correcto funcionamiento de dichos procesos se dice que es un  recurso  apropiativo. El CPU y la memoria principal  (mediante las técnicas de paginación) son   recursos que pueden ser asignados temporalmente por varios procesos. La apropiatividad de recursos es extremadamente importante en los sistemas de multiprogramación.

 Los datos y los programas son recursos que tienen características especiales. En un sistema multiusuario donde se pueden compartir editores, compiladores y programas en general, es ineficiente cargar una copia de ellos para cada usuario que lo solicite. En lugar de ello se carga una sola vez a la memoria y se hacen varias copias de los datos, una por cada usuario.
 El código que no cambia mientras está  en uso se llama código reéntrate. El código que puede ser cambiado pero que se inicializa cada vez que se usa se llama  reutilizable en serie. El código reéntrate puede ser compartido simultáneamente por varios procesos mientras que el reutilizable en serie sólo puede ser usado por un proceso a la vez.

Métodos para manejar los Dead Lock, figura # 24.

        -  Prevención
  - No permitirlos
        - Evitarlos

        - Difícil y caro
  - Permitirlos y recuperarlos    - Por perdida
        - de información

Figura # 24.  Prevención de Dead Lock.


En principio existen cuatro áreas importantes en la investigación del dead lock, a saber:


1) Prevención: 
 En las técnicas de prevención el interés se centra en condicionar un sistema para que elimine toda probabilidad de que ocurra un dead lock (normalmente a costa de recursos).

2) Evitación:
 En las técnicas para evitar, la idea es poner condiciones menos estrictas que la prevención, para lograr una mejor utilización de los recursos, pero procurando no caer en un dead lock.

3) Detección:
 Los métodos de detección se usan en sistemas que permiten la ocurrencia de un dead lock de forma voluntaria o involuntaria.

4) Recuperación:
 Los métodos de recuperación se usan para romper los dead lock en un sistema, para poder liberarlo de ellos y los procesos estancados pueden continuar y llegar a su fin.
http://eduadis.itlapiedad.edu.mx/~hocegueras/so1/so1_311.html
Modelo del sistema.

 Un sistema se compone de un número finito de recursos que se distribuyen entre varios procesos que compiten por ellos. Los recursos se dividen en varios tipos, cada uno de los cuales consiste en varios ejemplares idénticos. Los ciclos del UCP, el espacio de memoria, los archivos y los dispositivos de E/S (como impresoras y unidades de cinta) son ejemplos de tipos de recursos.

 Un proceso debe solicitar un recurso antes de usarlo, y liberarlo al terminar su uso. Un proceso puede solicitar cuantos recursos quiera para llevar a cabo su tarea. Obviamente, el número no puede exceder del total de recursos disponibles del sistema. En otras palabras, un proceso no puede solicitar tres impresoras si el sistema solo dispone de dos.

 En el modo de operación normal, un proceso solo puede utilizar un recurso en la secuencia siguiente:

1. Solicitud. Si la solicitud no puede atenderse de inmediato (por ejemplo, otro proceso  está utilizando ese recurso), entonces el proceso solicitante debe esperar hasta que pueda adquirir el recurso.
2.  Utilización. El proceso puede trabajar con el recurso (por ejemplo, si el recurso es una impresora, el proceso puede imprimir en ella).
3. Liberación. El proceso libera el recurso.

 La solicitud y liberación de recursos son llamadas al sistema. Algunos ejemplos son las llamadas Solicitar y Liberar dispositivos, Abrir y Cerrar archivos, y Asignar y Liberar memoria. La solicitud y liberación de otros recursos puede lograrse atreves de las operaciones espera (P) y señal (V) sobre semáforos. Además la utilización de recursos solo puede conseguirse mediante llamadas al sistema (por ejemplo, para leer o escribir en un archivo o dispositivo de E/S), de modo que para cada utilización, el sistema operativo verifica que el proceso que dispone del recurso ya lo había solicitado y ya se le había asignado. Una tabla del sistema registra si cada uno de los recursos está libre o asignado y, de estar asignado, a qué proceso. Si un proceso solicita un recurso que se encuentra asignado a otro, puede añadirse a la cola de procesos que esperan tal recurso.

 Un conjunto de procesos se encuentra en estado de bloqueo mutuo cuando cada uno de ellos espera un suceso que sólo puede originar otro proceso del mismo conjunto. 
http://eduadis.itlapiedad.edu.mx/~hocegueras/so1/so1_312.html
Caracterización.

 Debe ser obvio que los bloqueos mutuos son indeseables, pues cuando se dan, los procesos nunca terminan su ejecución y los recursos del sistema se paralizan, impidiendo que se inicien otros procesos. Antes de analizar los distintos métodos para tratar el problema del bloqueo mutuo  se describirán las circunstancias que los caracterizan.

Condiciones  necesarias  para  que  ocurra  un   Dead Lock.

 Coffman, Elphick y Shoshani. Establecieron las cuatro condiciones necesarias para que se produzca un dead lock.

1.- Los procesos reclaman control exclusivo de los recursos que solicitan (exclusión mutua).

2.- Los procesos mantienen los recursos que se les han asignado mientras esperan por recursos adicionales (condición de espera).

3.- No se pueden tomar los recursos que los procesos tienen hasta su completa utilización (condición de no apropiatividad).

4.- Existe una cadena circular de procesos en la cual cada uno de ellos mantiene uno o más recursos que son requeridos por el siguiente proceso de la cadena (condición de espera circular).

 Se deben presentar las cuatro condiciones para que puede aparecer un Dead Lock. La condición de espera circular implica la condición de retención y espera, por lo que las cuatro condiciones no son completamente independientes.
 http://eduadis.itlapiedad.edu.mx/~hocegueras/so1/so1_313.html

2.10.3.1 Prevención.
Prevención.

 En las estrategias de prevención de dead Locks, los recursos son otorgados a los procesos solicitados, de tal manera que la solicitud de un recurso nunca llega a un Dead Lock.  Esta estrategia se cerciora de que cuando menos una de cuatro condiciones de Dead Lock nunca llegue a ocurrir.

* Exclusión mutua.
 La condición de exclusión mutua debe conservarse para recursos no compartibles. Los recursos compartibles, no requieren acceso mutuamente excluyente y, por tanto, no pueden participar en un dead lock. Los archivos de  sólo lectura son un buen ejemplo de recursos compartibles. Si varios procesos tratan de abrir  al mismo tiempo un archivo de sólo lectura, se les puede otorgar accesos simultáneos al archivo, por lo general no es posible evitar dead lock`s  negando la condición de exclusión mutua. Por su naturaleza algunos recursos no pueden compartirse.


* Negación de la condición de "espera por".

 La primera estrategia de Havender requiere que todos los recursos que va a necesitar un proceso sean pedidos de una sola vez. El sistema deberá asignarlos según el principio "todo o nada". Si el conjunto de recursos que necesita un proceso está disponible se le asigna (todo) y se le permite entrar en ejecución. Si no es así, el proceso deberá esperar hasta que su conjunto de recursos esté disponible. Mientras un proceso espera. No podrá tener ningún recurso.


Esta estrategia presenta las siguientes desventajas:

* Puede llevar a la postergación indefinida, ya que quizá todos los recursos   requeridos estén disponibles al mismo tiempo (costos de operación altos).

* Puede llevar  un serio desperdicio de recursos, se requiere tener una gran cantidad de  recursos para poder responder a cumplir petición.

* Es ineficiente por que decrementa la concurrencia del sistema.
Una variante consiste en dividir el programa en bloques que puedan ser ejecutados con relativa independencia uno del otro. Esto reduce el desperdicio, pero implica un trabajo extra en el diseño de las aplicaciones.

* Negación de la condición de "no apropiatividad".
 Cuando un sistema cuenta con los recursos suficientes para que los procesos puedan funcionar sin problemas (bloqueos). Cuando el sistema permite compartir los recursos y los procesos mantienen  los que otros necesitan sucede un dead lock.
 La segunda estrategia sugiere que cuando a un proceso que mantiene recursos se le niegue una petición de recursos adicionales deberá liberar sus recursos y, si es necesario, pedirlos de nuevo, junto con los adicionales.

 Al retirar los recursos a un proceso que no puede avanzar se niega la condición de "no apropiatividad".  Un problema de esta política es la postergación indefinida.

* Negación de la condición de "espera circular".
 Si se da a los recursos una manera exclusiva y se obliga a los procesos a pedirlos en forma  ascendente es imposible que ocurra una espera circular. Esta propuesta considera:

+ Los recursos deben ser numerados reflejando el orden en el cual la mayoría de los trabajos los usan, figura # 25.
+ Los procesos deben pedir los recursos en forma ascendente, figura # 25.
+ Para los procesos que requieren de los recursos en un orden diferente, los recursos deberán ser tomados y retenidos mucho antes de su utilización. (Implica el desperdicio de los recursos mantenidos pero no usados).


Figura # 25.  Ordenamiento lineal  del recurso.
El ordenamiento lineal elimina la posibilidad de la espera circular, pero, obliga al diseñador a trabajar más con sus códigos. Además, los números de recursos son asignados por la instalación y hay que vivir con ellos durante largos periodos (meses o años). Si  los  números  cambian  se tienen  que rescribir los programas y los sistemas existentes.

 La forma  más simple de prevenir un  Dead Lock  es obteniendo todos los recursos necesarios antes que el proceso continué y así se elimine la  "condición de espera".

 En otro método de prevención de dead lock, un proceso bloqueado devuelve los recursos solicitados por un proceso activo, al igual que elimina la condición de "no apropiatividad"

Rosenkrantz  et al.  Ha propuesto la siguiente optimización de este método. Todos los procesos son asignados a prioridades únicas que pueden ser totalmente ordenadas. Un proceso de retención cede el derecho de prioridad a otro proceso que sostiene el recurso necesario solo si el proceso de retención tiene el recurso necesario solo si el proceso de retención tiene mayor prioridad.
 Este método reduce los derechos de prioridad  al 50% al igual que previene los dead locks. En el ordenamiento de Havender's todos los recursos son ordenados de manera única y todos los procesos solicitan los recursos de manera ascendente.
 Únicamente eliminando la condición de "espera circular". Si un proceso ya sostiene algunos recursos, entonces puede pedir solo aquellos acomodos en un rango superior en el orden. Obteniendo recursos, de ésta forma, previene la formación de un ciclo o de un "knot".
http://eduadis.itlapiedad.edu.mx/~hocegueras/so1/so1_314.html
Prevenir
Se puede prevenir el bloqueo siempre y cuando se consiga que alguna de las condiciones necesarias para la existencia de un bloqueo no se produzca.
1. los procesos tienen que compartir recursos con exclusión mutua:
o No se de a un proceso directamente acceso exclusivo al recurso, si no se usa otro proceso que realiza el trabajo de todos los demás manejando una cola de tareas (por ejemplo, un demonio para imprimir con su cola de documentos por imprimir).
2. los procesos quieren acceder a un recurso más mientras ya tienen acceso exclusivo a otro:
o Se exige que un proceso pida todos los recursos que va a utilizar al comienzo de su trabajo
3. los recursos no permiten ser usados por más de un proceso al mismo tiempo:
o Se permite que un proceso aborte a otro proceso con el fin de obtener acceso exclusivo al recurso. Hay que tener cuidado de no caer en livelock
4. existe una cadena circular entre peticiones de procesos y alocación de recursos:
o Se ordenan los recursos línealmente y se fuerza a los procesos que accedan a los recursos en el orden impuesto. Así es imposible que se produzca un ciclo.
En las prácticas aplicamos dicho método para prevenir bloqueos en la lista concurrente.
http://trevinca.ei.uvigo.es/~formella/doc/cd04/node71.html
Prevención de Deadlocks
La estrategia consiste en anular alguna de las cuatro condiciones necesarias para que se produzca un Deadlock.
1. No puede ser anulada porque existen recursos que deben ser usados en modalidad exclusiva.
2. La alternativa sería hacer que todos los procesos solicitaran todos los recursos que habrán de utilizar antes de utilizarlos al momento de su ejecución lo cual sería muy ineficiente.
3. Para anular esta condición cuando un proceso solicita un recurso y este es negado el proceso deberá liberar sus recursos y solicitarlos nuevamente con los recursos adicionales. El problema es que hay recursos que no pueden ser interrumpidos.
4. Espera Circular: esta estrategia consiste en que el sistema operativo numere en forma exclusiva los recursos y obligue a los procesos a solicitar recursos en forma ascendente. El problema de esto es que quita posibilidades a la aplicación.
Prevención de deadlock
• ¶ Deadlock no puede occurir a menos que tenemos todas las cuatro condiciones. Si aseguramos que no puede occurir por lo menos una de las condiciones, no podemos tener deadlock.
• ¶ Exclusión mutua. En general, no podemos eliminar esta condición. Hay recursos como impresoras que no son compartibles.
• ¶ Retención y espera. Para no occurir esta condición, cuando un proceso solicita recursos, no puede retener otros. Protocolos:
o Un proceso puede solicitar recursos solamente si no tiene ningunos.
o Un proceso tiene que solicitar todos los recursos antes de la ejecución.
¶ Problemas:
o La utilización de recursos puede ser baja.
o Starvation (bloqueo indefinido) si se necesitan algunos recursos populares.
• No apropiación. Si un proceso retiene varios recursos y solicita otro que no está disponible, se le expropian todos los recursos que retiene. El proceso tiene que recuperar todos los recursos antes de ejecutar otra vez.
Pero en general no podemos exproprian recursos como impresoras y grabadores.
• Espera circular. Hacemos una ordenación de los tipos de recursos en el sistema (R1, R2, ...). Un proceso tiene que solicitar sus recursos en orden (y todos los ejemplares de un tipo al mismo tiempo). Si necesita un tipo de recurso más baja en la ordenación, tiene que liberar los otros que retiene.
• Problemas con la prevención de deadlock: Utilización baja de recursos y reducción de la productividad del sistema.
http://www.cs.virginia.edu/~knabe/iic2332/notes07.html
Evitar
El sistema no da permiso de acceso a recursos si es posible que el proceso se bloquee en el futuro. Un método es el algoritmo del banquero (Dijkstra) que es un algoritmo centralizado y por eso posiblemente no muy practicable en muchas situaciones.
Se garantiza que todos los procesos actuan de la siguiente manera en dos fases:
1. primero se obtiene todos los cerrojos necesarios para realizar una tarea, eso se realiza solamente si se puede obtener todos a la vez,
2. despues se realiza la tarea durante la cual posiblemente se liberan recursos que no son necesarias.
Ejemplo:
Asumimos que tengamos 3 procesos que actuan con varios recursos. El sistema dispone de 12 recursos.
proceso recursos pedidos recursos reservados
A 4 1
B 6 4
C 8 5
suma 18 10
es decir, de los 12 recursos disponibles ya 10 están ocupados. La única forma que se puede proceder es dar el acceso a los restantes 2 recursos al proceso B. Cuando B haya terminado va a liberar sus 6 recursos que incluso pueden estar distribuidos entre A y C, así que ambos también pueden realizar su trabajo.
Con un argumento de inducción se verifica fácilmente que nunca se llega a ningún bloqueo.
http://trevinca.ei.uvigo.es/~formella/doc/cd04/node70.html
Evitación.

 Un método para evitar los Dead Lock`s consiste en requerir información adicional sobre cómo se solicitarán los recursos. Por ejemplo en un sistema con una unidad de cinta y una impresora, podríamos saber que el proceso P solicitará primero la unidad de cinta y luego la impresora, antes de liberar ambos recursos. El proceso Q, por otra parte, solicitará primero la impresora y después la unidad de cinta. Con este conocimiento de la secuencia completa de la solicitud y liberación para cada proceso para cada solicitud requiere que el sistema considera los recursos disponibles en ese momento, los actualmente asignados a cada proceso y las futuras solicitudes y liberaciones de cada proceso para decidir si puede satisfacer la solicitud presente o debe esperar para evitar un posible dead lock futuro.
Los diversos algoritmos difieren en la cantidad y tipo de información que requieren. 

El modelo más sencillo y útil requiere que cada proceso declare el número máximo de recursos de cada tipo que puede necesitar. Con información a priori para cada proceso es posible construir un algoritmo que asegure que el sistema nunca entrará en estado de dead lock. Este algoritmo define la estrategia de evitación de dead lock`s.

 El estado de asignación de recursos viene definido por el número de recursos disponibles  y asignados, y por la demanda máxima de los procesos. Un estado es seguro si el sistema puede asignar recursos a cada proceso (hasta el máximo) siguiendo algún orden u aun así evitar el dead lock.
 Más formalmente, un sistema se encuentra en estado seguro sólo si existe una secuencia segura. Si no existe esta secuencia, se dice que el estado del sistema es inseguro.

 Un estado seguro no es un estado de dead lock, y un estado de dead lock es un estado inseguro; pero no todos los estados inseguros son dead lock`s.

http://eduadis.itlapiedad.edu.mx/~hocegueras/so1/so1_315.html

2.10.3.2 Detección.
Detectar y actuar
Se implementa un proceso adicional que vigila si los demás forman una cadena circular.
Más preciso, se define el grafo de asignación de recursos:
• Los procesos y los recursos representan los nodos de un grafo.
• Se añade cada vez una arista entre un nodo tipo recurso y un nodo tipo proceso cuando el proceso ha obtenido acceso exclusivo al recurso.
• Se añade cada vez una arista entre un nodo tipo recurso y un nodo tipo proceso cuando el proceso está pidiendo acceso exclusivo al recurso.
• Se eliminan las aristas entre proceso y recurso y al revés cuando el proceso ya no usa el recurso.

Cuando se detecta en el grafo resultante un ciclo, es decir, cuando ya no forma un grafo acíclico, se ha producido una posible situación de un bloqueo.
Se puede reaccionar de dos maneras si se ha encontrado un ciclo:
• No se da permiso al último proceso de obtener el recurso.
• Sí se da permiso, pero una vez detectado el ciclo se aborta todos o algunos de los procesos involucrados.
Sin embargo, las técnicas pueden dar como resultado que el programa no avance, incluso, el programa se puede quedar atrapado haciendo trabajo inútil: crear situaciones de bloqueo y abortar procesos continuamente.
http://trevinca.ei.uvigo.es/~formella/doc/cd04/node69.html
Detección y Recuperación de Deadlocks
Algoritmos de Detección de Deadlock
1. Cuando hay una única ocurrencia de cada recurso. (variante del grafo de "wait for graph"). Consiste en reducir el grafo, retirando las aristas que van de recursos a procesos y de procesos a recursos, colocando nuevas aristas que reflejan la situación de espera entre procesos. Si el grafo reducido tiene ciclos el sistema esta en Deadlock. Orden de operaciones = n^2 , n = cantidad de aristas.
2. Cuando hay múltiples ocurrencias de cada recurso
Procedure detecta_deadlock
var Disponible:array[1..n] of integer //# de recursos
Usados:array[1..n] of integer
Solicitados:array[1..n] of integer
Finalizado:array[1..n] of boolean
Begin
Work:=Disponibles;
For i:=1..n do if(usados[i]≠0) then finish[i]:=false
Else finish[i]:=true;
While(encontrar_indice_i = true) do
Work:=work + usados[i];
Finish[i]:=true;
If ((finish[i] = false) para algun i), 1≤i≤n then  El sistema esta en Deadlock.
End
Function encontrar_indice_i : Boolean
Begin
If (existe i tal que (Finish[i]=false && solicitados[i] ≤ work)
Then -> true
Else -> false
End
Detección de deadlock
• La evitacíon de deadlock tiene un costo porque todos los estados inseguros no son estados de deadlock. Esto implica que hay tiempos cuando algunos procesos tienen que esperar y recursos están desocupados sin que es necesario.
• El sistema operativo puede chequear de vez en cuando si hay un deadlock. ¿Cuán frecuentemente debieramos chequear si hay deadlock?
o El costo de algoritmo vs. el número de procesos en deadlock.
o Saber quien creó el deadlock.
o ¶ Cuando la utilización de la CPU es baja.
• Tenemos que eliminar los deadlocks que encontramos. Posibilidades:
o Abortar todos los procesos en deadlock. ¡Esto es un método común!
o Abortar procesos uno a la vez hasta que no haya deadlock.
o Retroceder los procesos a algún punto y reiniciar. El deadlock puede reocurrir.
o Expropiar recursos de procesos hasta que no haya deadlock. Retrocedemos los procesos expropiados.
•
• Tenemos que seleccionar un proceso para abortar o retroceder. Factores:
o La prioridad
o El tiempo que el proceso ha corrido
o El número y tipo de los recursos adquiridos
o La clase de proceso (batch o interactiva)
• La starvation es un problema.
http://www.cs.virginia.edu/~knabe/iic2332/notes09.html
Detección y Recuperación.

 Es el hecho de determinar si existe o no un Dead Lock, e identificar cuales son los procesos y recursos implicados en él. El uso de algoritmos de detección de interbloqueo implica una sobrecarga en el tiempo de ejecución. Para ser correcto, un algoritmo de detección de interbloqueo debe de cumplir dos criterios:

 1) Debe detectar todos los dead lock´s   existentes en un tiempo finito.

 2) No debe reportar "falsos" Dead Lock's.

Grafo de asignación de recursos.
 Los Dead Lock pueden describirse con mayor precisión en función de un grafo dirigido llamado grafo de asignación de recursos, que consiste en un conjunto de vértices V y aristas A. El conjunto de vértices V se divide en dos tipos, P = P1,P2, ... , Pn, el conjunto formado por  todos los procesos del sistema,  y   R =R1,R2, ... ,Rn, el conjunto integrado por todos los tipos de recursos del sistema.


Representación mediante grafos del estado del sistema.

 El estado de un sistema es dinámico; esto es,  los procesos del sistema toman y liberan recursos continuamente.  La  representación del dead lock requiere la representación del estado  de la interacción  procesos - recursos, la representación se hace mediante un grafo dirigido que se conoce como gráfica de asignación de recursos .

En los sistemas de bases de datos distribuidos (DDBS) está representación se conoce como gráfica de espera de transacción (Transaction Wait-For TWF).

 Los dead lock`s pueden describirse con mayor precisión en función de un grafo dirigido llamado grafo de asignación de recursos.
La simbologia es la siguiente de acuerdo a las figura # 26.  a, b, c y d.


Figura # 26.   Gráfica de asignación y petición de recursos  

La técnica para la reducción de gráficas implica las consideraciones siguientes:

*  Si las peticiones de recursos de un proceso piden ser concedidas, entonces la gráfica puede
            ser reducida.
* La reducción de una gráfica consiste en retirar las flechas que van de los recursos a los procesos y retirar las flechas que van del proceso al recurso.
*  Si una gráfica puede ser reducida para todos sus procesos entonces no hay dead lock.
*  Si una gráfica no puede ser reducida para todos sus procesos, entonces los procesos
irreducibles constituyen la serie de procesos interbloqueados de la gráfica.
*  Detección de interbloqueo mediante grafos.

Un grafo G consiste de un conjunto finito no vacío.

V = C(G)   de:     P puntos (vértices) conjunto X de q parejas desordenadas de puntos de V(aristas).

 cada par X = U,V de puntos en X y una línea de G  por lo tanto X = UV.
 Un grafo de p puntos y q líneas se denomina un grafo (p,q), el grafo (1,0) es trivial.

 Petición  =   Proceso - Recurso
            Pi

 Rx             Ry     El proceso Pi tiene el recurso Rx y solicita el recurso Ry.

 Para determinar si existe un ciclo en un grafo se puede usar la representación matricial del grafo dirigido. Dado que se tienen parejas ordenadas Rx, Ry, la matriz se construye colocando un 1 en la diagonal en (x,x) y (y,y) y un 1 en la posición (x,y) de la matriz. Ejemplo figura # 27.  

Figura # 27.  Representación matricial del grafo.
Reducción de la matriz del grafo  de la figura  # 27 (b). Observe figura # 28.


Figura # 28.  Reducción de la matriz del grafo.

Reducción de la matriz de un grafo correspondiente. No existen vértices terminales; los vértices 1 y 2 son iniciales y pueden ser eliminados; existe un Inter bloqueo.

Ejemplo, figura # 29. Grafo.


Figura # 29.       a) Representación matricial         b)  Reducción de la matriz del grafo.


Representación vectorial que solo almacena la información que presenta el grafo, de la figura # 29.  Ejemplo figura  # 30.  
Figura #  30.  Representación vectorial
Un vértice terminal sólo aparece en la columna requiere y un vértice inicial sólo aparece en la columna Tiene. Para reducir esta representación se recorren de arriba a abajo los vectores y se buscan los vértices terminales e iniciales y se elimina su renglón.
 El proceso se repite hasta:
 1) No existen renglones o
 2) No se pueden eliminar renglones.

 Si no se pueden eliminar renglones las transiciones producen un Dead Lock.

 Para el grafo de la (figura # 30 (a) ) en el primer paso se eliminan los procesos P1 (vértice inicial), P2 y P3 (vértice terminal). En el segundo paso se elimina el proceso P4 (vértice terminal),  inicial.

 Para el grafo de la (figura # 30 (b)) el primero se eliminan los procesos P1,P2,P3 (vértices iniciales), P4(vértice inicial al eliminar el proceso P1), Los procesos restantes no pueden ser eliminados, por lo tanto existe un dead lock. El resultado de la reducción es, observe figura # 31.


Figura # 31.   Reducción del vector del grafo.


2.10.3.3 Recuperación.
Recuperación ante Deadlocks
1. Cancelación de procesos
a. Cancelación de todos los procesos involucrados. Esto resuelve la situación de Deadlock pero tiene un costo muy alto de reprocesamiento.
b. Cancelacion de un proceso por vez hasta resolver la situación de Deadlock. La ventaja de esto es que el costo de reprosesamiento de la información es menor pero cada vez que se cancela un proceso debe ejecutarse el algoritmo de detección de deadlock. Los criterios para elegir el candidato a ser cancelado son: por prioridad, por tiempo de uso de CPU, por cantidad de recursos utilizados y por cuantos recursos adicionales habrá de utilizar.
2. Obtención de recursos (resourse Preemption). El sistema operativo selecciona un proceso y le quita los recursos otorgados. Los criterios para seleccionar el candidato son los mismos que para la cancelación. El proceso seleccionado se le quitan los recursos y se le lleva a un estado consistente (Rollback).
Recuperación de un Dead Lock.

 La única forma en que el sistema operativo puede recuperarse de  un interbloqueo es retirando uno o más procesos y reclamar sus recursos para que otros procesos puedan terminar. Normalmente varios procesos perderán una parte o la totalidad del trabajo realizado hasta ese momento. Este puede parecer un precio pequeño comparado con dejar que el interbloqueo se complique por  varios factores.

*  En primer lugar, puede no estar claro que el sistema este bloqueado o no.
*  Muchos sistemas tienen medios pobres para suspender un proceso por tiempo   indefinido y reanudarlo más tarde.
*  Aún cuando existan medios efectivos de suspensión /reanudación, con toda seguridad, estos   implicarán una sobrecarga, considerable y pueden requerir la atención de un  operador  altamente calificado. No siempre se dispone de tales operadores.
*  Recuperarse de un interbloqueo de proporciones modestas puede suponer una cantidad razonable de trabajo.

Una  forma  de  elegir los procesos que pueden ser retirados es de acuerdo a las prioridades de los procesos. Pero esto también tiene sus dificultades.

*  Las prioridades de los procesos bloqueados pueden no existir, así que el operador deberá tomar una decisión arbitraria.
*  Las prioridades pueden ser incorrectas, o un poco confusas debido a consideraciones especiales.
*  La decisión óptima de cuáles procesos retirar pueden requerir de un esfuerzo considerable para determinarla.

 El enfoque más deseable a la recuperación del Dead Lock están un mecanismo efectivo de
Suspensión / reanudación. Esto permitirá detener temporalmente los procesos y después reanudarlos sin pérdida del trabajo.
http://eduadis.itlapiedad.edu.mx/~hocegueras/so1/so1_316.html

MECANISMOS PARA EVITARLOS.

 Havender llegó a la conclusión de que si no se cumple una de las cuatro condiciones necesarias para el interbloqueo es posible que éste ocurra.

 Para evitarlo sugirió:

*  Cada proceso deberá pedir todos los recursos requeridos de una sola vez y no podrá proceder hasta que le hayan sido asignados todos.
*  Si un proceso que mantiene ciertos recursos se le niega una nueva petición, este proceso deberá liberar sus recursos originales y en caso necesario pedirlos de nuevo con los recursos adicionales.
*  Se impondrá la ordenación lineal de los tipos de recursos en todos los procesos, es decir, si a un proceso le han sido asignados recursos de un tipo dado, en lo sucesivo sólo podrá pedir aquellos recursos de los tipos que siguen en el ordenamiento.


Otra alternativa, para manejar los dead lock, es tener información acerca de como los recursos se van a requerir, el modelo más simple y más útil requiere que en cada proceso declare el máximo número de recursos que van a requerir con lo cual es posible construir un algoritmo que asegure que el sistema no entrara en dead lock.

 Un estado es  seguro si el sistema puede asignar recursos a cada proceso en algún orden evitando el dead lock.
 Formalmente un sistema esta en estado seguro solamente si existe una secuencia segura. Una secuencia de procesos < P1, P2, ... Pn> esta en secuencia segura si para cada  Pi,  los recursos que Pi pueda requerir pueden ser satisfechos por los recursos disponibles más los recursos que tuvieron los Pj  donde  j < i.  Si no se puede satisfacer Pi entonces Pi espera hasta que los Pj terminen.
 Cuando Pi termine  Pi+1 puede obtener sus recursos y así sucesivamente.
Ejemplo, figura # 32.   Se tienen 12 unidades de cinta  se tiene 3 procesos ¿Ese sistema esta  en estado seguro o no?.


Figura #  32.    Requerimiento procesos - recursos.

Requerimiento máximo - Necesidad actual = Necesidad más  (Disponible).

Se tiene 12 recursos por lo tanto 12-9 = 3, entonces la secuencia es segura.
 La secuencia segura es  < P1,P0,P2>
Haga una situación en la cual el sistema estaría es estado inseguro.

Un estado seguro esta libre de dead lock y un estado de dead lock, es un estado inseguro pero no todos los estados inseguros producen dead lock.
 Si se esta en un estado seguro se puede pasar a un estado inseguro.

http://eduadis.itlapiedad.edu.mx/~hocegueras/so1/so1_317.html

Estrategias para evitarlos.
 Evitación del interbloqueo y el algoritmo de Dijkstra. Si las condiciones necesarias para que tenga lugar un interbloqueo están en su lugar, aún es posible evitar el interbloqueo teniendo cuidado al asignar los recursos.
 El algoritmo de planificación que pueda evitar los interbloqueos fue ideado por Dijkstra (1965) y se le conoce como algoritmo del banquero. En ese algoritmo se modela la forma en que un banquero puede tratar a un grupo de clientes a quienes les ha otorgado líneas de crédito. en la (figura # 36 (a)) se observan cuatro clientes, a cada uno de los cuales se le ha otorgado cierto número de unidades de crédito. El banquero sabe que los clientes no necesitan su límite de crédito máximo de inmediato, de manera que sólo ha reservado 10 unidades en lugar de 22 para darles servicio.
 Los clientes emprenden sus respectivos negocios, haciendo solicitudes de préstamo de cuando en cuando.  En cierto momento, la situación es como la que se muestra en la (figura # 33). A una lista de clientes que muestra el dinero que ya se presentó y el máximo del crédito disponible se le llama estado del sistema.


Figura # 33.   Tres estados de asignación de recursos
(a) Seguro.   (b) Seguro.   (c) Inseguro.
Un estado es seguro si existe una secuencia de estados que lleva a todos los clientes que obtienen préstamos hasta sus límites de crédito. El  estado de la (figura #33 (b) ) es seguro por que con las dos restantes, el banquero puede demorar  cualquier solicitud salvo la de Carlos, con lo que permite que termine y devuelva sus cuatro recursos. Con cuatro unidades, el banquero puede permitir que David o Bárbara tengan las unidades que necesitan para terminar y así sucesivamente.

 Si  estando  en  el estado de la ( figura  #33 (b) ) se le otorga una unidad más a Bárbara,  
(Figura #33 (c) ), el banquero  no podrá completar ninguna de la línea de crédito de su clientes. Un estado inseguro no tiene que conducir a un interbloqueo, ya que un cliente podría  no necesitar su línea de crédito disponible, pero el banquero no puede confiar en ese comportamiento.

 Haciendo una analogía con un Sistema Operativo tenemos: El estado actual del sistema se denomina seguro, Si el Sistema Operativo puede permitir a los usuarios actuales completar sus trabajos en un intervalo de tiempo finito. De lo contrario se le denomina inseguro. En otras palabras: Un estado seguro es aquel en el cual la asignación de recursos es tal que los usuarios pueden llegar a terminar. Un estado seguro es aquel que puede llegar a terminar. Un estado inseguro es aquel que puede llegar a un dead lock, (nunca termina).

La asignación de recursos por el algoritmo del banquero es la siguiente:

*  Se permite todas las condiciones de exclusión mutua, espera por y no apropiatividad.
*  Se permite a los procesos mantener sus recursos mientras esperan por otros.
*  El sistema sólo concede peticiones que den como resultado estados seguros.

*  El algoritmo del banquero para  n  recursos (de Dijkstra).

 Sea  n  un número de proceso y  m  un número de recurso y sea disponible un vector de longitud m  que indica el número de recursos disponibles y sea máxima una matriz de ( n x  m) que define  la máxima demanda de cada proceso así por ejemplo si tuviéramos máxima ( i,j ) = k define los  recursos asignados a cada proceso, por ejemplo la asignación ( i , j ) = k quiere decir que el proceso i tiene asignado K instancias del recurso j  necesidades ( n * m ), que indica los recursos que requieren los procesos. Necesidades ( i , j ) = Máxima  ( i , j ) - Asignación ( i , j ).
 Se puede considera cada renglón de las matrices asignación y necesidades como vectores y referirnos como asignación de i y necesidades de i.


Algoritmo:

 Sea requerimiento de i un vector de requerimientos de proceso i.

 Cuando un requerimiento de un recurso es hecho por el proceso i se realizaran las siguientes acciones:

1).-   Si Requerimiento de i <= Necesidades de i  ir al segundo paso. Sino error.
2).-   Si requerimiento de  i <=  disponible  ir al tercer paso. Si no recurso no disponible Pi  debe esperar.
3).-  Hacer Disponible = Disponible - Requerimiento,
 Asignación = Asignación  +  Requerimiento,
 Necesidades = Necesidades - Requerimiento.

 Si el estado es seguro se completa la transacción de lo contrario el proceso debe esperar y el estado anterior es restablecido.

 Algoritmo para ver si el estado es seguro.

 Sea trabajo (m)  y final (n) vectores de longitud  m  y  n  respectivamente, hacer                                      Trabajo =  Disponible y final ( i ) =  falso  para i = 1,...n

1).-   Encuentre una  i  tal que final  ( i )  de i = falso y Necesidades ( i ) <= Trabajo  si no existe ir al punto tres.
2).-  Trabajo  =  Trabajo  +  Asignación ( i ), Final ( i ) = verdad  ir al paso uno.
3).- Si  final ( i)  =  verdad  para toda  i  entonces el sistema esta en estado seguro de lo contrario esta en estado inseguro.

http://eduadis.itlapiedad.edu.mx/~hocegueras/so1/so1_318.html