PRINCIPIOS DEL INTERBLOQUEO
El interbloqueo se puede definir como el bloqueo permanente de un conjunto de procesos que compiten por los recursos del sistema o bien se comunican unos con otros. A diferencia de otros problemas de la gestión concurrente de procesos, no existe una solución eficiente para el caso general.
Todos los interbloqueos suponen necesidades contradictorias de recursos por parte de dos o más procesos.
EJEMPLOS DE INTERBLOQUEO
Ejemplo 1: Interbloqueo de tráfico
Cuatro coches llegan aproximadamente en el mismo instante a un cruce de cuatro caminos. Los cuatro cuadrantes de la intersección son los recursos compartidos sobre los que se demanda control; por tanto, si los coches desean atravesar el cruce, las necesidades de recursos son las siguientes:
- El coche que va hacia el norte necesita los cuadrantes 1 y 2.
- El coche que va hacia el oeste necesita los cuadrantes 2 y 3.
- El coche que va hacia el sur necesita los cuadrantes 3 y 4.
- El coche que va hacia el este necesita los cuadrantes 4 y 1.
La norma mas habitual en la carretera es que un coche en un cruce de cuatro caminos debe ceder el paso al coche que está a su derecha. Esta norma funciona si solo hay dos o tres coches en el cruce. Por ejemplo, si solo llegan al cruce los coches del norte y del oeste, el coche del norte esperará hasta que el del oeste pase. Sin embargo, si los cuatro coches llegan al mismo tiempo cada uno se abstendrá de entrar en el cruce, provocando interbloqueo. Si todos los coches ignoran las normas y entran (con cuidado) en el cruce, cada coche obtendrá un recurso (un cuadrante) pero no podrá continuar porque el segundo recurso que necesita ya ha sido invadido por otro coche. De nuevo, se tiene interbloqueo.
Ejemplo 2: Cruce en un puente (es parecido al interbloqueo de trafico)
En una carretera de dos direcciones, donde en un determinado cruce con la vía del ferrocarril, se ha construido un puente que solo deja pasar vehículos en un solo sentido. El bloqueo ocurre cuando dos carros intentan pasar por el puente al mismo tiempo.
Una manera de resolver el bloqueo es: el conductor situado en uno de los extremos es lo suficientemente educado que deja pasar en primer lugar al del otro extremo y luego pasa él.
Este ejemplo nos muestra como sucede el interbloqueo en nuestra vida diaria.
Ejemplo 3
Dos procesos desean imprimir cada uno un enorme archivo en cinta. El proceso A solicita el permiso para utilizar la impresora, el cual se le concede. Es entonces cuando el proceso B solicita permiso para utilizar la unidad de cinta y se le otorga. El proceso A solicita entonces la unidad de cinta, pero la solicitud es denegada hasta que B la libere. Por desgracia, en este momento, en vez de liberar unidad de cinta, B solicita la impresora. Los procesos se bloquean en ese momento y permanecen así por siempre.
RECURSOS
Un sistema se compone de un numero finito de recursos que se distribuyen entre varios tipos:
- Físicos: Ciclo de cpu, espacio en memoria, dispositivos de e/s (impresoras, unidades de cinta, etc.)
- Lógicos: Ficheros, tablas del sistemas, semáforos.
Por lo general, una computadora tiene distintos recursos que pueden ser otorgados. Algunos recursos podrán tener varias instancias idénticas, como es el caso de tres unidades de cinta. Si se tienen disponibles varias copias de un recurso, cualquiera de ellas se pude utilizar para satisfacer cualquier solicitud del recurso. Un recurso es cualquier cosa que solo puede ser utilizada por un único proceso en un instante dado.
Los recursos son de dos tipos:
- Apropiable
- No apropiables
Un recurso apropiable es aquel que se puede tomar del proceso que lo posee sin efectos dañinos. La memoria es un ejemplo de recurso apropiable.
Por el contrario, un recurso no apropiable, es aquel que no se puede tomar de su poseedor activo sin provocar un fallo de calculo. Si un proceso comienza a imprimir una salida, se toma la impresora y se le da a otro proceso, el resultado será una salida incomprensible. Las impresoras no son apropiables.
Los interbloqueos se relacionan con los recursos no apropiables. Lo usual es que los bloqueos asociados a recursos apropiables se pueden resolver, mediante la reasignación de recursos de un proceso a otro.
La secuencia de eventos necesaria para utilizar un recurso es:
- Solicitar el recurso
- Utilizar el recurso
- Liberar el recurso
Si el recurso no esta disponible cuando se le solicita, el proceso solicitante debe esperar. En algunos sistemas operativos, el proceso se bloquea de manera automática al fallar una solicitud de un recurso y se despierta cuando dicho recurso esta disponible. En otros sistemas la solicitud falla con un código de error y el proceso solicitante debe esperar un poco e intentar de nuevo.
Un proceso cuya solicitud de un recurso ha sido denegada entra por lo general en un ciclo, en el cual solicita el recurso, duerme e intenta de nuevo.
Aunque este proceso no esta bloqueado, para todos los efectos esta como bloqueado, puesto que no puede hacer ninguna labor útil.
El interbloque se puede definir entonces de la siguiente forma:
Un conjunto de procesos se encuentra en estado de interbloqueo cuando cada uno de ellos espera un suceso que solo puede originar otro proceso del mismo conjunto.
En la mayoría de los casos, el evento que espera cada proceso es la liberación de cierto recurso que posee por el momento otro miembro del conjunto. En otras palabras, cada miembro del conjunto de procesos bloqueados espera un recurso poseído por un proceso bloqueado. Ninguno de los procesos puede continuar su ejecución, ni liberar recursos, y puede ser despertado.
CONDICIONES PARA PRODUCIR INTERBLOQUEO
En la política del sistema operativo, deben darse tres condiciones para que pueda producirse un interbloqueo:
1- Condición de exclusión mutua: Cada recurso esta asignado a un único proceso o esta disponible.
2- Condición de posesión y espera: Los procesos que tienen, en un momento dado, recursos asignados con anterioridad, pueden solicitar nuevos recursos.
3- Condición de no apropiación: Los recursos otorgados con anterioridad no pueden ser forzados a dejar un proceso. El proceso que los posee debe liberarlos en forma explicita.
En la mayoría de los casos, estas condiciones son bastantes necesarias. La exclusión mutua hace falta para asegurar la consistencia de resultados y la integridad de la base de datos. De forma similar, la apropiación no se puede aplicar arbitrariamente y, cuando se encuentran involucrados recursos de datos, debe estar acompañada de un mecanismo de recuperación y reanulación, que devuelva un proceso y sus recursos a un estado previo adecuado, desde el que el proceso puede finalmente repetir sus acciones.
Puede no existir interbloqueo con solo estas tres condiciones. Para que se produzca interbloqueo, se necesita una cuarta condición:
4- Condición de espera circular (o circulo vicioso de espera): Debe existir una cadena circular de dos o mas procesos, cada uno de los cuales espera un recurso poseído por el siguiente miembro de la cadena.
Las tres primeras condiciones son necesarias, pero no suficientes, para que exista interbloqueo. La cuarta condición es, en realidad, una consecuencia potencial de las tres primeras. Es decir, dado que se producen las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en un circulo vicioso de espera irresoluble. El circulo de espera de la condición 4 es irresoluble porque se mantienen las tres primeras condiciones. Las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el interbloqueo.
PREVENCIÓN DEL INTERBLOQUEO
La estrategia básica de la prevención del interbloqueo consiste, a grandes rasgos, en diseñar su sistema de manera que esté excluida, a priori, la posibilidad de interbloqueo.
Los métodos para prevenir el interbloqueo son de dos tipos:
- Los métodos indirectos que consisten en impedir la aparición de alguna de las tres condiciones necesarias para que se de el interbloqeo.
- Los métodos directos que consisten en evitar la aparición del circulo vicioso de espera.
Exclusión mutua
Si ningún recurso se puede asignar de forma exclusiva, no se producirá interbloqueo. Sin embargo, existen recursos para los que no es posible negar la condicion de exclusión mutua. No obstante, es posible eliminar esta condicion en algunos procesos. Por ejemplo, una impresora es un recurso no compatible pues si se permite que dos procesos escriban en la impresora al mismo tiempo, la salida resulta caótica. Pero con el spooling de salida varios procesos pueden generar salida al mismo tiempo. Puesto que el spooler nunca solicita otros recuersos, se elimina el bloqueo originado por la impresora.
El inconveniente es que no todos los recursos pueden usarse de esta forma (por ejemplo, la tabla de procesos no se presenta al spooling y, ademas, la implementacion de esta técnica puede introducir nuevos motivos de interbloqueo, ya que el spooling emplea una zona de disco finita)
Retencion y espera
La condicion de retencion y espera puede prevenirse exigiendo que todos los procesos soliciten todos los recursos que necesiten a un mismo tiempo y bloqueando el proceso hasta que todos los recursos puedan concederse simultáneamente. Esta solucion resulta ineficiente por dos factores:
- En primer lugar, un proceso puede estar suspendido durante mucho tiempo, esperando que concedan todas sus solicitudes de recursos, cuando de hecho podria haber avanzado con solo algunos de los recursos.
- Y en segundo lugar, los recursos asignados a un proceso pueden permanecer sin usarse durante periodos considerables, tiempo durante el cual se priva del acceso a otros procesos.
No apropiación
La condición de no apropiación puede prevenirse de varias formas. Primero, si a un proceso que retiene ciertos recursos se le deniega una nueva solicitud, dicho proceso deberá liberar sus recursos anteriores y solicitarlos d eneuvo, cuando sea necesario, junto con el recurso adicional. Por otra parte, si un proceso solicita un recurso que actualmente esta retenido por otro proceso, el sistema operativo debe expulsar al segundo proceso y exigirle que libere sus recursos. Este ultimo esquema evitará el interbloqueo sólo si nho hay dos procesos que posean la misma prioridad.
Esta técnica es práctica sólo cuando se aplica a recursos cuyo estado puede salvarse y restaurarse más tarde de una forma facil, como es el caso de un procesador.
Circulo vicioso de espera
La condición del circulo vicioso de espera puede prevenirse definiendo una ordenación lineal de los tipos de recursos. Si a un proceso se le han asignado recursos de tipo R, entonces sólo podrá realizar peticiones posteriores sobre los recursos de los tipos siguientes a R en la ordenación.
Para comprobar el funcionamiento de esta estrategia, se asocia un índice a cada tipo de recurso. En tal caso, el recurso Ri antecede a Rj en la ordenación si i<j. Entonces, supóngase que dos procesos A y B, están interbloqueados, porque A ha adquirido Ri y solicitado Rj, mientras que B ha adquirido Rj y solicitado Ri. Esta condición es imposible porque implica que i<j y j<i.
Como en la retención y espera, la prevención del circulo vicioso de espera puede ser ineficiente, retardando procesos y denegando accesos a recursos innecesariamente.
PREDICCIÓN DEL INTERBLOQUEO
Una forma de resolver el problema del interbloqueo, que se diferencia sutilmente de la prevención, es la predicción del interbloqueo. En la prevención de interbloqueo, se obligaba a las solicitudes de recursos a impedir que sucediera , por lo menos, alguna de las cuatro condiciones de interbloqueo. Esto se hace indirectamente, impidiendo la aparición de una de las tres condiciones necesarias (exclusión mutua, retención y espera, no apropiación) o directamente, impidiendo la aparición de un circulo viciosos de espera. Se llega así a un uso ineficiente de los recursos y una ejecución ineficiente de los procesos. Con predicción del interbloqueo, por otro lado, se pueden alcanzar las tres condiciones necesarias, pero se realizan elecciones acertadas para asegurar que nunca se llega al punto de interbloqueo. La predicción, por lo tanto, permite más concurrencia que la prevención.
Con predicción del interbloqueo, se decide dinámicamente si la petición actual de asignación de un recurso podría, de concederse, llevar potencialmente a un interbloqueo. La predicción del interbloqueo necesita, por lo tanto, conocer las peticiones futuras de recursos.
Enfoques para la predicción del interbloqueo:
- No iniciar un proceso si sus demandas pueden llevar a interbloqueo.
- No conceder una solicitud de incrementar los recursos de un proceso si esta asignación puede llevar a interbloqueo.
Negativa de iniciación de procesos
Confedérese un sistemas de n procesos y m tipos diferentes de recursos. Se definen los vectores y matrices siguientes:
Recursos = (R1, R2, ... Rm) cantidad total de cada recurso en el sistema
Disponible = (D1, D2, ... Dm) cantidad total de cada recurso sin asignar a los procesos
La predicción del interbloqueo tiene la ventaja de que no es necesario expulsar y hacer retroceder procesos, como en la detección del interbloqueo, y es menos restrictiva que la prevención. Sin embargo, su uso supone una serie de restricciones como las siguientes:
- Se debe presentar la máxima demanda de recursos por anticipado.
- Los procesos a considerar deben ser independientes, es decir, que el orden en que se ejecuten no debe estar forzado por condiciones de sincronización.
- Debe haber un número fijo de recursos a repartir y un número fijo de procesos.
- Los procesos no pueden finalizar mientras retengan recursos.
DETECCIÓN DEL INTERBLOQUEO
Las estrategias de prevención de interbloqueo son muy conservadoras; resuelven el problema limitando el acceso a recursos e imponiendo restricciones sobre los procesos. En cambio, las estrategias de detección de interbloqueo, no limitan el acceso a recursos ni restringen las acciones del proceso. Con la detección del interbloqueo, se concederán los recursos que los procesos necesiten siempre que sea posible. Periódicamente, el S. O. ejecuta un algoritmo que permite detectar la condición de circulo vicioso de espera.
La detección del interbloqueo es el proceso de determinar si realmente existe un interbloqueo e identificar los procesos y recursos implicados en él. Una posibilidad detectar un interbloqueo es monitorear cada cierto tiempo el estado de los recursos. Cada vez que se solicita o se devuelve un recurso, se actualiza el estado de los recursos y se hace una verificación para observar si existe algún ciclo.
Este método está basado en suponer que un interbloqueo no se presente y que los recursos del sistema que han sido asignados, se liberarán en el momento que otro proceso lo requiera.
Algoritmo de detección del interbloqueo
Una comprobación para interbloqueo puede hacerse con igual o menor frecuencia que cada solicitud de recursos, dependiendo de que tan probable es que ocurra un interbloqueo. Comprobar cada solicitud de recursos tiene dos ventajas: Conduce a la detección temprana y el algoritmo es simple, de manera relativa porque se basa en cambios crecientes al estado del sistema. Además, las comprobaciones frecuentes consumen un tiempo considerable de procesador.
Los algoritmos de detección de bloqueos implican cierta sobrecarga en tiempo de ejecución:
surge el siguiente interrogante:
¿ compensa la sobrecarga implicita en los algoritmos de detección de bloqueos, el ahorro potencial de localizarlos y romperlos ?.
El empleo de algoritmos de detección de interbloqueo implica cierto gasto extra durante la ejecución. Así pues, se presenta de nuevo la cuestión de costeabilidad, tan habitual en los sistemas operativos. Los algoritmos de detección de interbloqueo determinan por lo general si existe una espera circular.
RECUPERACIÓN DE INTERBLOQUEO
Cuando se ha detectado que existe un interbloqueo, podemos actuar de varias formas. Una posibilidad es informar al operador que ha ocurrido un interbloqueo y dejar que el operador se ocupe de él manualmente. La otra posibilidad es dejar que el sistema se recupere automáticamente del interbloqueo. Dentro de esta recuperación automática tenemos dos opciones para romper el interbloqueo: Una consiste en abortar uno o más procesos hasta romper la espera circular, y la segunda es apropiar algunos recursos de uno o más de los procesos bloqueados.
La recuperación después de un interbloqueo se complica porque puede no estar claro que el sistema se haya bloqueado. Las mayorías de los Sistemas Operativos no tienen los medios suficientes para suspender un proceso, eliminarlo del sistema y reanudarlo más tarde.
Actualmente, la recuperación se suele realizar eliminando un proceso y quitándole sus recursos. El proceso eliminado se pierde, pero gracias a esto ahora es posible terminar. Algunas veces es necesario, eliminar varios procesos hasta que se hayan liberado los recursos necesarios para que terminen los procesos restantes.
Los procesos pueden eliminarse de acuerdo con algún orden de prioridad, aunque es posible que no existan prioridades entre los procesos bloqueados, de modo que el operador necesita tomar una decisión arbitraria para decidir que procesos se eliminarán.
Recuperación Manual
Está forma de recuperación consiste en avisarle al administrador o al operador del sistema que se ha presentado un interbloqueo, y será el administrador el que solucione dicho problema de la manera más conveniente posible, de modo que su decisión no afecte demasiado a al usuario del proceso en conflicto, y sobre todo que no afecte a los demás usuarios del sistema.
Abortar los Procesos
Para eliminar interbloqueos abortando un proceso, tenemos dos métodos; en ambos, el sistema recupera todos los recursos asignados a los procesos terminados.
1 ) Abortar todos los procesos interbloqueados. Esta es una de las soluciones más comunes, adoptada por Sistemas Operativos. Este método romperá definitivamente el ciclo de interbloqueo pero con un costo muy elevado, ya que estos procesos efectuaron cálculos durante mucho tiempo y habrá que descartar los resultados de estos cálculos parciales, para quizá tener que volver a calcularlos más tarde.
2 ) Abortar un proceso en cada ocasión hasta eliminar el ciclo de interbloqueo. El orden en que se seleccionan los procesos para abortarlos debe basarse en algún criterio de costo mínimo. Después de cada aborto, debe solicitarse de nuevo el algoritmo de detección, para ver si todavía existe el interbloqueo. Este método cae enmucho tiempo de procesamiento adicional.
Quizá no sea fácil abortar un proceso. Si éste se encuentra actualizando un archivo, cortarlo a la mitad de la operación puede ocasionar que el archivo quede en un mal estado.
Si se utiliza el método de terminación parcial, entonces, dado un conjunto de procesos bloqueados, debemos determinar cuál proceso o procesos debe terminarse para intentar romper el interbloqueo. Se trata sobre todo de una cuestión económica, debemos abortar los procesos que nos representen el menor costo posible. Existen muchos factores que determinan el proceso que se seleccionará, siendo los principales los siguientes:
- La prioridad del proceso. Se elimina el proceso de menor prioridad.
- Tiempo de procesador usado. Se abortará aquel proceso que haya utilizado menos tiempo el procesador, ya que se pierde menos trabajo y será más fácil recuperarlo más tarde.
- Tipos de recursos utilizados. Si los recursos son muy necesarios y escasos será preferible liberarlos cuanto antes.
- Cuántos recursos más necesita el proceso. Es conveniente eliminar a aquellos procesos que necesitan un gran número de recursos.
- Facilidad de suspensión / reanudación. Se eliminarán aquellos procesos cuyo trabajo perdido sea más fácil de recuperar.
Apropiación de Recursos
Para eliminar interbloqueos utilizando la apropiación de recursos, vamos quitando sucesivamente recursos de los procesos y los asignamos a otros hasta romper el ciclo de interbloqueo.
Si se utiliza la apropiación de recursos para tratar los interbloqueos, hay que considerar tres aspectos:
- Selección de la víctima
- Retroceso
- Bloqueo indefinido
La detección y recuperación es la estrategia que a menudo se utiliza en grandes computadoras, especialmente sistemas por lote en los que la eliminación de un proceso y después su reiniciación suele aceptarse.
UNA ESTRATEGIA INTEGRADA DE INTERBLOQUEO
Puede ser mas eficiente usar diferente estrategias en diferentes situaciones, una de ellas sugiere lo siguiente:
Agrupar los recursos en un numero de clases diferentes.
- Usar la estrategia de ordenación lineal definida anteriomente para la prevención de circulo viciosos de espera e impedir el interbloqueo entre clases de recursos.
- Dentro de cada clase de recursos, emplear el algoritmo mas apropiado para dicha clase.
Como ejemplo de esta técnica, considérense las siguientes clases de recursos:
- Espacio intercambiable: bloques de memoria en almacenamiento secundario para el intercambio de procesos.
- Recursos de procesos: dispositivos asignables, como unidades de cintas y archivos.
- Memoria principal: asignable a los procesos en paginas o segmentos.
- Recursos internos: como canales de E / S.
El orden en que se encuentran estas clases de recursos es el orden en que se asignan. El orden es razonable, teniendo en cuenta la secuencias de pasos que un proceso debe seguir durante su vida.
En cada clase se pueden usar las siguientes estrategias :
- Espacio Intercambiable: puede aplicarse la prevención de interbloqueos, pidiendo que todos los recursos sean asignados de una vez, como la estrategia de prevención de retención y espera. Esta estrategia es razonable si se conoce los requisitos máximo de almacenamiento, lo que suele ser habitual. Otra posibilidad es la predicción de interbloqueos.
- Recursos de Procesos: la predicción es a menudo efectiva en esta categoría, puesto que es razonable esperar que los procesos declaren por anticipados los recursos de esta clase que necesitaran. También es posible en esta clase la prevención mediante la ordenación de recursos.
- Memoria Principal: la prevención por apropiación parece ser la estrategia mas adecuada para la memoria principal. Cuando se expulsa un proceso, simplemente es trasladado a la memoria secundaria
- Recursos Internos: puede usarse la prevención por ordenación de recursos.
EL PROBLEMA DE LA CENA DE LOS FILOSOFOS
Había una vez cinco filósofos que vivían juntos. La vida de cada filósofo consistía principalmente en pensar y comer y, tras años de pensar, todos los filósofos se habían puesto de acuerdo en que la única comida que contribuía a sus esfuerzos eran los espaguetis.
Los preparativos de la comida eran simples : una mesa redonda en la que había una gran fuente de espaguetis, cinco platos, uno para cada filósofo y cinco tenedores. Un filósofo que quisiera comer iría a su lugar asignado en la mesa y, usando los dos tenedores de cada lado del plato, cogería los espaguetis y se los comería. El problema es lo siguiente : inventar un ritual (algoritmo) que permita comer a los filósofos. El algoritmo debe satisfacer la exclusión mutua (dos filósofos no pueden emplear el mismo tenedor a la vez), además de evitar el interbloqueo y la inanición (en este caso, este ultimo termino tiene un significado literal además del algorítmico).
Este problema, propuesto por Dijkstra, puede no parecer importante o relevante por si mismo. Sin embargo, sirve para ilustrar los problemas básicos del interbloqueo y la inanición. Es más, intentar desarrollar una solución revela muchas de las dificultades de la programación concurrente. Además, el problema de la cena de los filósofos puede verse como un caso representativo de los problemas relacionados con la coordinación sobre recursos compartidos, que se produce cuando una aplicación incluye hilos de ejecución concurrentes. Por consiguiente, este problema es un caso de prueba estándar para examinar soluciones a la sincronización.
Una primera solución al problema de la cena de los filósofos es:
/* program cena_filósofos */
semáforo tenedor[5] = {1};
int i;
void filosofo(int i)
{
while (cierto)
{
pensar ( );
wait (tenedor [i]);
wait (tenedor [(i + 1)mod 5];
comer ( );
signal (tenedor [(i + 1) mod 5]);
wait (tenedor [1]);
}
}
void main ( )
{
parbegin (filosofo (0), filosofo (1), filosofo (2), filosofo (3), filosofo (4));
}
Sugiere una solución por medio de semáforos. Cada filosofo toma 1º el tenedor de su izquierda , y después el de su derecha. Cuando un filosofo termina de comer, devuelve los dos tenedores a la mesa. Esta solución, desafortunadamente, produce ínterbloqueo: si todos los filósofos están hambriento al mismo tiempo, todos se sientan, todos toman el tenedor de su izquierda y todos intentan tomar el otro tenedor que no estará. Esta solución es poco decorosa, pues todos los filósofos pasan hambre.-
Para superar el riesgo de ínter bloqueo se podrían adquirir 5 tenedores adicionales ( una solución mas saludable), o enseñar a los filósofos a comer espaguetis con un solo tenedor.
Como otra solución posible , se podría considerar incorporar un sirviente que permita pasar solo a 4 cuatro filósofos a la vez al comedor. Con un máximo de 4 filósofos sentados, al menos uno de los filósofos tendrá acceso a los dos tenedores. En esta figura se muestra con semáforos. Esta solución esta libre de ínter bloqueo e inanición.
/* program cena_filósofos */
semáforo tenedor[5] = {1};
semáforo habitación = {4};
int i;
void filosofo (int i)
{
while (cierto)
pensar ( );
wait (habitación);
wait (tenedor [i]);
wait (tenedor [(i + 1) mod 5]);
comer ( );
signal (tenedor [(i +1) mod 5]);
wait (tenedor [i]);
signal (habitación);
}
void main ( )
{
parbegin (filosofo (0), filosofo (1), filosofo (2), filosofo (3), filosofo (4));
}
MECANISMOS DE CONCURRENCIA EN UNIX
Los distintos mecanismos más importantes que ofrece UNIX para la comunicación entre procesos y la sincronización son los siguientes:
- Tubos
- Mensajes
- Memoria Compartida
- Semáforos
- Señales
Los tubos, los mensajes y la memoria compartida brindan un medio de comunicación de datos entre procesos, mientras que los semáforos y las señales se utilizan para provocar acciones en otros procesos.
Tubos
Es un buffer circular que permite a dos procesos comunicarse según el modelo productor/consumidor.
Cuando se crea un tubo, se le da un tamaño fijo en bytes. Cuando un proceso intenta escribir en el tubo, la solicitud de escritura se ejecuta inmediatamente si hay suficiente espacio; de otro modo, el proceso se bloquea. De la misma manera, un proceso lector se bloquea si intenta leer mas bytes de los que tiene disponible en ese momento. El sistema operativo es el encargado de la exclusión mutua, es decir, al tubo solo puede accederlo un proceso por vez.
Hay dos tipos de tubos: con nombre y sin nombre. Los tubos sin nombre pueden ser compartidos por procesos afines y los tubos con nombre pueden ser compartidos por procesos no afines.
Mensajes
Es un bloque de texto con un tipo asociado. UNIX proporciona las llamadas al sistema msgsnd y msgrcv para que los procesos puedan enviarse mensajes. Cada proceso tiene asociada una cola de mensajes, que funciona como un buzón de correos.
El emisor del mensaje especifica el tipo de mensaje en cada envío y el receptor puede usarlo como criterio de selección. El receptor puede recuperar los mensajes tanto en orden FIFO como por el tipo asociado. Un proceso se suspenderá cuando intente leer de una cola vacía. Si un proceso intenta leer un mensaje de cierto tipo y falla, el proceso no se suspenderá.
Memoria Compartida
Es la forma más rápida de comunicación entre procesos que brinda UNIX, se trata de un bloque común de memoria virtual compartido por varios procesos. Los procesos pueden leer y escribir en la memoria compartida usando las mismas instrucciones que la maquina que emplea para leer y escribir en otras partes de su espacio de direcciones virtual. Los permisos de un proceso son solo lectura o lectura-escritura, según el proceso. Las limitaciones de exclusión mutua no forman parte del servicio de memoria compartida, sino que las debe proporcionar el proceso que hace uso del mismo.
Semáforos
Las llamadas al sistema para semáforos en el UNIX Versión V son una generalización de las primitivas "wait y signal", en estas se pueden realizar conjuntamente varias operaciones y los incrementos y disminuciones pueden ser valores mayores que 1. El núcleo ejecuta atómicamente todas las operaciones solicitadas; ningún otro proceso puede acceder al semáforo hasta que todas las operaciones hayan culminado.
Un semáforo consta de los siguientes elementos:
- Valor actual del semáforo.
- ID del ultimo proceso que opero con el semáforo.
- Numero de procesos esperando a que el valor del semáforo sea mayor que su valor actual.
- Numero de procesos esperando a que el valor del semáforo sea cero
Asociadas con cada semáforo existen colas de procesos suspendidos.
Los semáforos, se crean por conjuntos, en el cual, un conjunto tiene uno o más semáforos. Hay una llamada al sistema semctl que permite dar valores a todos los semáforos del conjunto al mismo tiempo. Además, hay una llamada al sistema sem-op que recibe como argumento una lista de operaciones sobre semáforos, cada una de ellas definida sobre uno de los semáforos del conjunto. Cuando se genera esta llamada, el núcleo realiza las operaciones indicadas una a una. Para cada operación, se especifica la función real por medio del valor sem_op. Existen las siguientes posibilidades:
- Si sem_op es mayor que 0, el núcleo incrementa el valor del semáforo y despierta a los procesos que esperaban a que el valor del semáforo se incrementase.
- Si sem_op es igual a 0, el núcleo comprueba el valor del semáforo. Si el semáforo es 0, continúa con las otras operaciones de la lista; en caso contrario, incrementa el número de procesos esperando a que este semáforo sea igual a 0 y suspende el proceso hasta que el valor del semáforo sea 0.
- Si sem_op es negativo y su valor absoluto es menor o igual que el valor del semáforo, el núcleo suma sem_op (un número negativo) al valor del semáforo. Si el resultado es 0, el núcleo despierta a todos los procesos que esperan a que el valor del semáforo sea igual a 0.
- Si sem_op es negativo y su valor absoluto es mayor que el valor del semáforo, el núcleo suspende al proceso, caso de que el valor del semáforo se incremente.
Esta generalización de los semáforos ofrece una considerable flexibilidad para realizar sincronización y coordinación de procesos.
Señales
Es un mecanismo de software que informa a un proceso que se ha producido un suceso asíncrono. Una señal es similar a una interrupción de hardware, pero no emplea prioridades. Es decir, todas las señales se tratan de igual manera; las señales que se producen en un mismo momento se presentan al proceso en el mismo instante, sin una ordenación en particular.
Los procesos pueden enviarse señales entre si y el núcleo puede enviar señales internas. Una señal se entrega actualizando un campo de la tabla de procesos del proceso al que se le envía. Dado que cada señal se mantiene como un único bit, las señales de un tipo en particular no pueden colocarse en la cola. Una señal se procesa en el instante después de que el proceso despierte para ejecutarse o cuando el proceso este dispuesto a volver de una llamada al sistema. Un proceso puede responder a una señal ejecutando alguna acción por omisión (por ejemplo, terminar), ejecutando una función de gestión de la señal o ignorando la señal.
Esta tabla enumera algunas de las señales definidas en el UNIX SVR4
Valor
|
Nombre
|
Descripción
|
01
|
Sighup
|
Colgar; se le envía a un proceso cuando el núcleo supone que el usuario de ese proceso no está realizando un trabajo útil.
|
02
|
Sigint
|
Interrumpir.
|
03
|
Sigquit
|
Salir; la envía el usuario para provocar una parada del proceso y la genración de un volcado de memoria.
|
04
|
Sigill
|
Instrucción ilegal.
|
05
|
Sigtrap
|
Seguimiento de cepo (trap); provoca la ejecución de un código de seguimiento del proceso.
|
06
|
Sigiot
|
Ejecución de la instrucción IOT.
|
07
|
Sigemt
|
Ejecución de la instrucción MT.
|
08
|
Sigfpt
|
Excepción de coma flotante.
|
09
|
Sigkill
|
Matar; terminación del proceso.
|
10
|
Sigbus
|
Error de bus.
|
11
|
Sigsev
|
Violación de segmento; un proceso intenta accedet a una posición fuera de su espacio de direcciones virtual
|
12
|
Sigsys
|
Argumentos incorrectos en una llamada al sistema.
|
13
|
Sigpipe
|
Escritura en un tubo que no tiene lectores asociados.
|
14
|
Sigalarm
|
Alarma de relog
|
15
|
Sigterm
|
Terminación por software
|
16
|
Sigusr1
|
Señal 1 definida por el usuario.
|
17
|
Sigusr2
|
Señal 2 definida por el usuario.
|
18
|
Sigcld
|
Muerte de un hijo.
|
19
|
Sigpwr
|
Corte de energía.
|
