unidad3 admon del procesador

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

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.

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

concurrencia e interbloqueo deadlock

DEADLOCK

Los procesos no son ejecutados constantemente desde que se inician hasta que son finalizados.

Un proceso puede estar identificado con tres estados diferentes: leyendo (ready), ejecutando (running) o bloqueado (blocked). En el estado de lectura, un proceso está parado, concediendo que otro proceso sea ejecutado; en el estado de ejecución, un proceso está utilizando algún recurso; y en el estado de bloqueo, el proceso está parado y no se ejecutará mientras algo lo restaure.

Una condición común no deseable es descripta como deadlock, que es cuando dos procesos están en un estado de ejecución, y requieren intercambiar recursos entre sí para continuar. Ambos procesos están esperando por la liberación del recurso requerido, que nunca será realizada; como no hay ningún resultado, tomará un camino que llevará a un estado de deadlock.

Muchos escenarios han sido construidos para ilustrar las condiciones de deadlock, siendo el más popular el Problema de Comida de los Filósofos. Cinco filósofos tienen cinco platos de fideos enfrente suyo y cinco tenedores, uno a cada lado del plato. Los filósofos necesitan ambos tenedores (derecha e izquierda) para comer. Durante la comida realizarán solo dos operaciones mutuamente excluyentes, pensar o comer. El problema es un paralelismo simplista entre procesos (los filósofos) tratando de obtener recursos (tenedores); mientras están en estado de ejecución (comiendo) o de lectura (pensando). Una condición posible de deadlock puede ocurrir, si todos los filósofos quieren coger el tenedor de la derecha y, a la vez, el de la izquierda: la comida terminará en estado de deadlock.

Se dice que dos procesos se encuentran en estado de deadlock (interbloqueo, bloqueo mutuo o abrazo mortal) cuando están esperando por condiciones que nunca se van a cumplir. Se podría hablar de deadlock como el estado permanente de bloqueo de un conjunto de procesos que están compitiendo por recursos del sistema.

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- 1- Condición de exclusión mutua: Cada recurso esta asignado a un único proceso o esta disponible.

2- 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- 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- 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

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

Demanda = exigencias de recursos para cada proceso

Asignación = asignación actual

La matriz Demanda indica las exigencias máximas de recursos para cada proceso, con una fila para cada uno. Es decir, Cij = demanda del recurso j por parte del proceso i. Esta información debe declararse por adelantado para que funcione la predicción de interbloqueo.

De forma similar, Aij = asignación del recurso j al proceso i. Se puede ver que se cumplen las siguientes relaciones:

1. Para todo i, Ri = Di + Σ Aki : todos los recursos están asignados o disponibles.

2. Para todo k e i, Cki <= Ri: ningún proceso puede demandar más recursos que la cantidad total de recursos del sistema

3. Para todo k e i, Aki <= Cki: ningún proceso tiene asignados más recursos de cualquier tipo que los que ha declarado necesitar.

Con estas tres cantidades, se puede definir una política de predicción del interbloqueo que rechace iniciar un nuevo proceso si sus exigencias de recursos pueden conducir a un intebloqueo. Un nuevo proceso Pn+1 comenzará sólo si:

Ri >= C(n+1)i + Σ Cki, para todo i

Es decir, un proceso comenzará sólo si puede servirse la demanda máxima de todos los procesos actuales más la del nuevo proceso. Esta estrategia es poco óptima, puesto que asume el caso peor: que todos los procesos expresen su demanda máxima a la vez.

Negativa de asignación de recursos.-La estrategia de negar la asignación de recursos, denominada algoritmo del banquero, fue propuesta por primera vez por Dijkstra, que usó este nombre por la analogía de este problema con el de un banco cuando los clientes quieren obtener dinero prestado. Los clientes sería los procesos y el dinero a prestar, los recursos. Si se enuncia de esta manera, el banco tiene una reserva limitada de dinero para prestar y un conjunto de clientes con líneas de crédito. Un cliente puede elegir pedir dinero a cargo de la línea de crédito en un instante dado y no hay garantía de que el cliente realice ninguna reposición hasta después de sacar la cantidad máxima. El banquero puede rechazar un préstamo a un cliente si hay riesgo de que el banco no tenga fondos suficientes para hacer préstamos futuros que los clientes finalmente repondrán.

Para empezar se definen los conceptos de estado y de estado seguro. Considérese un sistema con un número fijo de procesos. Así pues, el estado estará formado por los dos vectores, Recursos y Disponible, y las dos matrices, Demanda y Asignación, definidas anteriormente. Un estado seguro es un estado en el cual existe al menos una secuencia que no lleva al interbloqueo ( es decir, todos los procesos pueden ejecutarse hasta el final). Un estado inseguro es, naturalmente, un estado que no es seguro.

El algoritmo del banquero 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.

Los algoritmos siguientes muestran una versión abstracta de la logica de predicción del interbloqueo. Con el estado del sistema definido por la estructura de datos estado, solicitud [*] es un vector que define los recursos pedidos por el proceso i. En primer lugar, se hace una comprobación para asegurar que la solicitud no excede la demanda inicial del proceso. Si la solicitud es válida, el paso siguiente es determinar si es posible satisfacer la solicitud, esto es, si hay suficientes recursos disponibles. Si no es posible, el proceso se suspende. Si es posible, el paso final es determinar si es seguro satisfacer la solicitud. Para hacer esto, se prueba a asignar los recursos al proceso i desde nuevo_estado. Después, se realiza un test d seguridad usando el algoritmo del banquero.

Estructura de datos globales

struct estado { int recursos [m]; int disponible [m]; int demada [n] [m]; int asignación [n] [m]; }

Algoritmo de asignación de recursos

if (asignación[i, ] + solicitud [*] > demanda [I, *]) { <>; /*-- solicitud total > demanda */ } else if (solicitud [*] > disponible [*]) { <> ; } else /*-- simular asignación */ { <>; } if (seguro (nuevo_estado)) { <>; } else { <>; <>; }

Algoritmo de comprobación de estado seguro (algoritmo del banquero)

booleano seguro (estado S) { int disponible_actual [m]; proceso resto [<>]; disponible_actual = disponible; resto = {todos los procesos}; posible = true; while (posible) { encontrar un PK en resto tal que demanda [k, *] – asignación [k, *] < = disponible_actual; if (encontrado) /*-- simular ejecución de P */ { disponible_actual = dispible_actual + asignación [k, *]; resto = resto – {PK}; } else posible = falso; } seguro (resto = = null); }

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:

1. La prioridad del proceso. Se elimina el proceso de menor prioridad.

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

3. Tipos de recursos utilizados. Si los recursos son muy necesarios y escasos será preferible liberarlos cuanto antes.

4. Cuántos recursos más necesita el proceso. Es conveniente eliminar a aquellos procesos que necesitan un gran número de recursos.

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

PRIMITIVAS DE SINCRONIZACIÓN DE HILOS EN SOLARIS

Además de los mecanismos de concurrencia de UNIX SVR4, Solaris soporta cuatro primitivas de sincronización de hilos:

- - Cierres de exclusión mutua (mutex, mutual exclución).

- - Semáforos.

- - Cierre de múltiples lectores, un escritor (lectoress escritores).

- - Variables de condición.

Solaris implementa estas primitivas para los hilos de núcleo dentro del núcleo; tambien las ofrece en la biblioteca de hilos para los hilos de usuario. La ejecución de una primitiva crea una estructura de datos que contiene parámetros especificados por el hilo creador (figura 6.13). Una vez que está creado el objeto de sincronización, hay dos operaciones, fundamentalmente, que se puedan realizar: entrar(adquirir, bloquear) y salir (desbloquear). El núcleo o la biblioteca de hilos no incluyen mecanismos para hacer cumplir la exclusión mutua o prevenir el interbloqueo. Si un hilo intenta accder a datos un fragmento de código o que se supone protegido pero no utiliza la primitiva de sincronización correspondiente, se produce ese acceso. Si un hilo bloquea un objeto y, después, falla al desbloquearlo, el núcleo no hace nada.

(a) Cierre MUTEX

(b) Cierre de lectores/escritores

© Semáforo

(d) Variable de condición

Cierre de exclusión mutua Un cierre mutex impide que ejecute más de un hilo cuando el cierre está activo. El hilo que bloquea el mutex debe ser el que lo desbloquea. Un hilo intenta adquirir un cierre mutex ejecutando la primitiva mutex_enter. Si mutex_enter no puede activar el cierre (debido a que ya está activado por otro hilo), la acción mediante la que se bloquea el hilo depende de la información específica de tipo almacenada en el objeto mutex. La política de bloqueo por defecto es un cierre circular, un hilo bloqueado comprueba el estado del cierre mientras ejecuta en un bucle de espera. Opcionalmente se aplica un mecanismo de bloqueo basado en interrupciones. En este último caso, el mutex un id de torno que identifica una cola de hilos dormidos en este cierre.

Las primitivas asociadas a un cierre mutex son: mutex_enter() Adquiere el cierre; potencialmente se bloquea si ya está adquirido.

mutex_exit() Libera el cierre; potencialmente desbloquea a uno que espera.

mutex_tryenter() Adquiere el cierre si aún no está adquirido.

La primitiva mutex_tryenter() proporciona un modo no bloqueador de ejecutar la función de exclución mutua. Esto permite al programador utilizar un metodo de espera activa para hilos de usuario, lo que evita que se bloquee el proceso completo debido al bloqueo de un hilo.

Semáforos Solaris ofrece semáforos enteros clásicos, con las siguientes primitivas:

sema_p () Disminuye el semáforo, potencialmente bloquea el hilo.

sema_v () Incrementa el semáforo, potencialmente desbloquea un hilo que espera.

sema_tryp () Si nos es necesario bloquearse, disminuye el semáforo.

De nuevo, la primitiva sema_tryp () permite espera activa.

Cierre lectores/escritores El cierre lectores/escritores permite a múltiples hilos tener accesos sólo-lectura simultáneos a un objeto protegido por el cierre. También permite a un solo hilo acceder, en un instante dado, al objeto pàra escritura, excluyendo a todos los lectores. Cuando se adquiere el cierre para escritura, pasa al estado de cerradura-escritura. todos los hilos que intenten acceder para leer o escribir deben esperar. Si uno o más lectores adquieren el cierre, su estado pasa a cerrado-lectura. Las primitivas son como sigue:

rw_enter() Intenta adquirir un cierre como lector o escritor.

rw_exit() Libera un cierre como lector escritor.

rw_tryenter() Si no es necesario bloquearse, adquiere el cierre.

rw_downgrade() Un hilo que ha adquirido un cierre de escritura lo convierte en cierre de lectura. Cualquier escritor que estuviese esperando continúa esperando hasta que el hilo libere el cierre. Si no hay escritores esperando, la primitiva despierta a los lectores que esperan.

rw_tryupgrade() Intenta convertir un cierre de lectura en un cierre de escritura.

Variables de condición Una variable de condición se utiliza para esperar hasta que sea cierta una determinada condición. Las variables de condición deben usarse junto con un cierre mutex. Las primitivas son como sigue:

c_wait() Bloquea hasta que se señaliza la condición.

cv_signal() Despierta un hilo bloqueado en en c_wait().

cv_broadcast() Despierta todos los hilos bloqueados en c_wait()

c_wait() libera el mutex asociado antes de bloquearse y lo readquiere antes de retornar. Puesto que la readquisisción del mutex puede estar bloqueada por otro hilo que espera en el mutex, se debe reevaluar la condición de espera, de este modo un uso habitual es el siguiente:

mutex_enter(&m); . . . while (alguna condición) { cv_wait (&cv , &m); } . . . mutex_exit (&m);

Esto permite que la condición sea una expresión compleja, puesto que está protegida por el mutex.

MECANISMOS DE CONCURRENCIA EN WINDOWS 2000

Windows 2000 (W2K) ofrece sincronización entre los hilos como parte de la arquitectura de objetos. El mecanismo usado por el ejecutor de W2K para implementar los servicios de sincronización es la familia de objetos de sincronización, que esta formada por los siguientes:

- - Proceso. - - Hilo. - - Archivo. - - Entrada de consola. - - Notificación de cambio de archivo. - - Mutante. - - Semáforo. - - Suceso. - - Temporizador.

Cada caso de objeto de sincronización puede estar en estado señalizado o no señalizado. Un hilo puede estar suspendido por un objeto en estado no señalizado: el hilo es liberado cuando el objeto pasa a estado señalizado. El mecanismo es sencillo: un hilo genera una solicitud de espera al ejecutor de W2K por medio del descriptor (handle) del objeto de sincronización. Cuando un objeto pasa a estado señalizado, el ejecutor de W2K libera todos los objetos hilo que estaban esperando por dicho objeto de sincronización. El objeto mutante se utiliza para hacer cumplir la exclusión mutua en el acceso a un recurso, permitiendo que sólo un objeto hilo obtenga el acceso en cada instante. Por lo tanto, funciona como un semáforo binario. Cuando el objeto mutante pasa a estado señalizado, sólo se libera uno de los hilos que esperan. Los objetos mutante pueden utilizarse para sincronizar hilos que ejecutan en distintos procesos.

Al igual que los mutantes, hilos de diferentes procesos pueden compartir semáforos. El semáforo de W2K es un semáforo entero clásico.

El temporizador en esencia, señala determinado momento o intervalos regulares.

Objetos de sincronización de Windows 2000 (Resume los sucesos que hacen que cada tipo de objetos pase a estado señalizado y el efecto que tiene en los hilos que esperan)

Tipo de objeto Definición Pasa a estado señalado cuando Efectos sobre los hilos que esperan Proceso Invocación a un programa, incluyendo el espacio de direcciones y los recursos Termina el ultimo hilo Todos se liberan Hilo Entidad ejecutable dentro de un proceso Termina el hilo Todos se liberan Archivo Caso particular de un archivo abierto o de un dispositivo de E/S Se completa la operación de E/S Todos se liberan

Entrada de consola Un buffer de pantalla para ventana de texto (por ejemplo, se utiliza para gestionar una pantalla de E/S de una aplicación MS-DOS) La entrada esta disponible Se libera un hilo Notificación de cambio de archivo

  Una notificación de que cambia cualquier sistema de archivos. El cambio se produce en un sistema de archivos que asocia un criterio de filtrado a ese objeto Se libera un hilo

Mutante Mecanismo que proporciona exclusión mutua a los entornos Win32 y OS/2 El hilo propietario u otro hilo libera al mutante Se libera un hilo Semáforo Contador que regula el numero de hilos que pueden emplear un recurso El contador del semáforo llega a cero Todos se liberan Suceso Anuncio de que ha ocurrido un suceso del sistema Un hilo activa el suceso Todos se liberan Temporiza-dor Contador que registra el paso del tiempo Llega el tiempo de activación o expira el intervalo de guarda

Paso de mensajes

El paso de mensajes es una técnica empleada en programación concurrente para aportar sincronización entre procesos y permitir la exclusión mutua, de manera similar a como se hace con los semáforos, monitores, etc.

Su principal característica es que no precisa de memoria compartida, por lo que es muy importante en la programación para sistemas distribuidos.

Los elementos principales que intervienen en el paso de mensajes son el proceso que envía, el que recibe y el mensaje.

monitores

Un monitor encapsula el código relativo a un recurso compartido en un solo módulo de programa; ventajas:

• mantenimiento más simple

• menos errores de programación

La interfaz del monitor es un conjunto de funciones que representan las diferentes operaciones que pueden hacerse con el recurso

La implementación del monitor garantiza la exclusión mutua

• mediante semáforos o algún otro mecanismo

• o implícitamente en los lenguajes concurrentes

semaforos

Semáforos es un algoritmo de control de procesos, que tiene solo dos operaciones básicas, las cuales son:

Wait.- Pregunta a los procesos si su contador es > ó = que cero, en caso de no ser así, los decrementa. El proceso que cambia en este caso a negativo (−1) desde la cola de procesos Listos a ser ejecutados es el que automáticamente toma el control del procesador.

Signal.- A partir de un tiempo t definido por el despachador se ejecuta, y pregunta a los procesos si su contador es <>

concurrencia exclusion mutua y sincronizacion

Concurrencia: exclusión mutua y sincronización

Los temas fundamentales del diseño de sistemas operativos están relacionados con la gestión de procesos e hilos:

• Multiprogramación: consiste en la gestión de varios procesos dentro de un sistema mono-procesador.

• Multiprocesamiento: consiste en la gestión de varios procesos, dentro de un sistema multiprocesador.

• Procesamiento distribuido: consiste en la gestión de varios procesos, ejecutándose en sistemas de computadores múltiples y distribuidos. La reciente proliferación de las agrupaciones es el principal ejemplo de este tipo de sistemas.

La concurrencia es fundamental en todas estas áreas y para el diseño sistemas operativos. La concurrencia comprende un gran número de cuestiones de diseño, incluida la comunicación entre procesos, compartición y competencia por los recursos, sincronización de la ejecución de varios procesos y asignación del tiempo de procesador a los procesos. Se verá que estas cuestiones no solo surgen en entornos de multiprocesadores y proceso distribuido, sino incluso en sistemas multiprogramados con un solo procesador.

La concurrencia puede presentarse en tres contextos diferentes:

• Múltiples aplicaciones: la multiprogramación se creó para permitir que el tiempo de procesador de la máquina fuese compartido dinámicamente entre varias aplicaciones activas.

• Aplicaciones estructuradas: como ampliación de los principios del diseño modular y la programación estructurada, algunas aplicaciones pueden implementarse eficazmente como un conjunto de procesos concurrentes.

• Estructura del sistema operativo: las mismas ventajas de estructuración son aplicables a los programadores de sistemas y se ha comprobado que algunos sistemas operativos están implementados como un conjunto de procesos o hilos.

PRINCIPIOS GENERALES DE LA CONCURRENCIA

En un sistema multiprogramado con un único procesador, los procesos se intercalan en el tiempo aparentando una ejecución simultánea. Aunque no se logra un procesamiento paralelo y produce una sobrecarga en los intercambios de procesos, la ejecución intercalada produce beneficios en la eficiencia del procesamiento y en la estructuración de los programas.

La intercalación y la superposición pueden contemplarse como ejemplos de procesamiento concurrente en un sistema monoprocesador, los problemas son consecuencia de la velocidad de ejecución de los procesos que no pueden predecirse y depende de las actividades de otros procesos, de la forma en que el sistema operativo trata las interrupciones surgen las siguientes dificultades:

Compartir recursos globales es riesgoso Para el sistema operativo es difícil gestionar la asignación óptima de recursos. Las dificultades anteriores también se presentan en los sistemas multiprocesador.

El hecho de compartir recursos ocasiona problemas, por esto es necesario proteger a dichos recursos.

Los problemas de concurrencia se producen incluso cuando hay un único procesado

LABORES DEL SISTEMA OPERATIVO

Elementos de gestión y diseño que surgen por causa de la concurrencia:

1) El sistema operativo debe seguir a los distintos procesos activos

2) El sistema operativo debe asignar y retirar los distintos recursos a cada proceso activo, entre estos se incluyen:

_Tiempo de procesador

_Memoria

_Archivos

_Dispositivos de E/S

3) El sistema operativo debe proteger los datos y los recursos físicos de cada proceso contra injerencias no intencionadas de otros procesos.

4) Los resultados de un proceso deben ser independientes de la velocidad a la que se realiza la ejecución de otros procesos concurrentes.

Para abordar la independencia de la velocidad debemos ver las formas en las que los procesos interactúan.

INTERACCIÓN ENTRE PROCESOS

Se puede clasificar los en que interactúan los procesos en función del nivel de conocimiento que cada proceso tiene de la existencia de los demás. Existen tres niveles de conocimiento:

1) Los procesos no tienen conocimiento de los demás: son procesos independientes que no operan juntos. Ej: la multiprogramación de procesos independientes. Aunque los procesos no trabajen juntos, el sistema operativo se encarga de la “competencia” por los recursos.

2) Los procesos tienen un conocimiento indirecto de los otros: los procesos no conocen a los otros por sus identificadores de proceso, pero muestran cooperación el objeto común.

3) Los procesos tienen conocimiento directo de los otros: los procesos se comunican por el identificador de proceso y pueden trabajar conjuntamente.

Competencia entre procesos por los recursos

Los procesos concurrentes entran en conflicto cuando compiten por el uso del mismo recurso; dos o más procesos necesitan acceder a un recurso durante su ejecución .Cada proceso debe dejar tal y como esté el estado del recurso que utilice.

La ejecución de un proceso puede influir en el comportamiento de los procesos que compiten. Por Ej. Si dos procesos desean acceder a un recurso, el sistema operativo le asignará el recurso a uno y el otro tendrá que esperar.

Cuando hay procesos en competencia, se deben solucionar tres problemas de control: la necesidad de exclusión mutua. Suponiendo que dos procesos quieren acceder a un recurso no compartible. A estos recursos se les llama “recursos críticos” y la parte del programa que los utiliza es la “sección crítica” del programa. Es importante que sólo un programa pueda acceder a su sección crítica en un momento dado.

Hacer que se cumpla la exclusión mutua provoca un interbloqueo.

Otro problema es la inanición si tres procesos necesitan acceder a un recurso, P1 posee al recurso, luego lo abandona y le concede el acceso al siguiente proceso P2, P1 solicita acceso de nuevo y el sistema operativo concede el acceso a P1 YP2 alternativamente, se puede negar indefinidamente a P3 el acceso al recurso.

El control de competencia involucra al sistema operativo, porque es el que asigna los recursos.

Cooperación entre procesos por compartimiento Comprende los procesos que interactúan con otros sin tener conocimiento explícito de ellos. Ej. : Varios procesos pueden tener acceso a variables compartidas.

Los procesos deben cooperar para asegurar que los datos que se comparten se gestionan correctamente. Los mecanismos de control deben garantizar la integridad de los datos compartidos.

Cooperación entre procesos por comunicación Los distintos procesos participan en una labor común que une a todos los procesos.

La comunicación sincroniza o coordina las distintas actividades, está formada por mensajes de algún tipo. Las primitivas para enviar y recibir mensajes, vienen dadas como parte del lenguaje de programación o por el núcleo del sistema operativo

REQUISITOS PARA LA EXCLUSIÓN MUTUA

Sólo un proceso, de todos los que poseen secciones críticas por el mismo recurso compartido, debe tener permiso para entrar en ella en un momento dado. Un proceso que se interrumpe en una sección no crítica debe hacerlo sin interferir con los otros procesos. Un proceso no debe poder solicitar acceso a una sección crítica para después ser demorado indefinidamente, no puede permitirse el interbloqueo o la inanición. Si ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin demora. No se debe suponer sobre la velocidad relativa de los procesos o el número de procesadores. Un proceso permanece en su sección crítica por un tiempo finito. Una manera de satisfacer los requisitos de exclusión mutua es dejar la responsabilidad a los procesos que deseen ejecutar concurrentemente. Tanto si son programas del sistema como de aplicación, los procesos deben coordinarse unos con otros para cumplir la exclusión mutua, sin ayuda del lenguaje de programación o del sistema operativo. Estos métodos se conocen como soluciones por software.

EXCLUSIÓN MUTUA: SOLUCIONES POR SOFTWARE

Pueden implementarse soluciones de software para los procesos concurrentes que se ejecuten en máquinas monoprocesador o multiprocesador con memoria principal compartida.

ALGORITMO DE DEKKER

La solución se desarrolla por etapas. Este método ilustra la mayoría de los errores habituales que se producen en la construcción de programas concurrentes.

Primer intento

Cualquier intento de exclusión mutua debe depender de algunos mecanismos básicos de exclusión en el hardware. El más habitual es que sólo se puede acceder a una posición de memoria en cada instante, teniendo en cuenta esto se reserva una posición de memoria global llamada turno. Un proceso que desea ejecutar su sección crítica primero evalúa el contenido de turno. Si el valor de turno es igual al número del proceso, el proceso puede continuar con su sección crítica. En otro caso el proceso debe esperar. El proceso en espera, lee repetitivamente el valor de turno hasta que puede entrar en su sección crítica. Este procedimiento se llama espera activa.

Después de que un proceso accede a su sección crítica y termina con ella, debe actualizar el valor de turno para el otro proceso.

Segundo intento:

Cada proceso debe tener su propia llave de la sección crítica para que, si uno de ellos falla, pueda seguir accediendo a su sección crítica; para esto se define un vector booleano señal. Cada proceso puede evaluar el valor de señal del otro, pero no modificarlo. Cuando un proceso desea entrar en su sección crítica, comprueba la variable señal del otro hasta que tiene el valor falso (indica que el otro proceso no está en su sección crítica). Asigna a su propia señal el valor cierto y entra en su sección crítica. Cuando deja su sección crítica asigna falso a su señal.

Si uno de los procesos falla fuera de la sección crítica, incluso el código para dar valor a las variables señal, el otro proceso no se queda bloqueado. El otro proceso puede entrar en su sección crítica tantas veces como quiera, porque la variable señal del otro proceso está siempre en falso. Pero si un proceso falla en su sección crítica o después de haber asignado cierto a su señal, el otro proceso estará bloqueado permanentemente.

Tercer intento

El segundo intento falla porque un proceso puede cambiar su estado después de que el otro proceso lo ha comprobado pero antes de que pueda entrar en su sección crítica.

Si un proceso falla dentro de su sección crítica, incluso el código que da valor a la variable señal que controla el acceso a la sección crítica, el otro proceso se bloquea y si un proceso falla fuera de su sección crítica, el otro proceso no se bloquea.

Si ambos procesos ponen sus variables señal a cierto antes de que ambos hayan ejecutado una sentencia, cada uno pensará que el otro ha entrado en su sección crítica, generando así un interbloqueo.

Cuarto intento

En el tercer intento, un proceso fijaba su estado sin conocer el estado del otro. Se puede arreglar esto haciendo que los procesos activen su señal para indicar que desean entrar en la sección crítica pero deben estar listos para desactivar la variable señal y ceder la preferencia al otro proceso.

Existe una situación llamada bloqueo vital, esto no es un interbloqueo, porque cualquier cambio en la velocidad relativa de los procesos rompería este ciclo y permitiría a uno entrar en la sección crítica. Recordando que el interbloqueo se produce cuando un conjunto de procesos desean entrar en sus secciones críticas, pero ninguno lo consigue. Con el bloqueo vital hay posibles secuencias de ejecución con éxito.

Una solución correcta

Hay que observar el estado de ambos procesos, que está dado por la variable señal, pero es necesario imponer orden en la actividad de los procesos para evitar el problema de “cortesía mutua”. La variable turno del primer intento puede usarse en esta labor, indicando que proceso tiene prioridad para exigir la entrada a su sección crítica.

ALGORITMO DE PETERSON

El algoritmo de Deker resuelve el problema de la exclusión mutua pero mediante un programa complejo, difícil de seguir y cuya corrección es difícil de demostrar. Peterson ha desarrollado una solución simple y elegante. Como antes, la variable global señal indica la posición de cada proceso con respecto a la exclusión mutua y la variable global turno resuelve los conflictos de simultaneidad.

Considérese el proceso P0. Una vez que ha puesto señal[0] a cierto, P1 no puede entrar en su sección crítica. Si P1 esta aun en su sección crítica, entonces señal[1] = cierto y P0 está bloqueado en su bucle while. Esto significa que señal[1] es cierto y turno = 1. P0 puede entrar en su sección crítica cuando señal[1] se ponga a falso o cuando turno se ponga a 0. Considérense ahora los siguientes casos exhaustivos:

P1 no está interesado en entrar en su sección crítica. Este caso es imposible porque implica que señal[1] = falso. P1 está esperando entrar en su sección crítica. Este caso es también imposible porque si turno = 1, P1 podría entrar en su sección crítica. P1 entra en su sección crítica varias veces y monopoliza el acceso a ella. Esto no puede pasar porque P1 está obligado a dar a P0 una oportunidad poniendo turno a 0 antes de cada intento de entrar en su sección crítica. Así pues, se tiene una solución posible al problema de la exclusión mutua para dos procesos. Es más, el algoritmo de Peterson se puede generalizar fácilmente al caso de n procesos.

Disciplina de cola

La disciplina de cola mas simple es la de primero en llegar/ primero en salir, pero ésta puede no ser suficiente si algunos mensajes son mas urgentes que otros. Una alternativa es permitir la especificación de prioridades de los mensajes, en función del tipo de mensaje o por designación del emisor. Otra alternativa es permitir al receptor examinar la cola de mensajes y seleccionar el mensaje a recibir a continuación.

Exclusión mutua

Supóngase que se usan primitivas receive bloqueantes y send no bloqueantes. Un conjunto de procesos concurrentes comparten un buzón, exmut, que puede ser usado por todos los procesos para enviar y recibir. El buzón contiene inicialmente un único mensaje, de contenido nulo. Un proceso que desea entrar en su sección crítica intenta primero recibir el mensaje. Si el buzón está vacío, el proceso se bloquea. Una vez que un proceso ha conseguido el mensaje, ejecuta su sección crítica y, después, devuelve el mensaje al buzón. De este modo, el mensaje funciona como testigo que se pasa de un proceso a otro.

Esta técnica supone que si hay más de un proceso ejecutando la acción receive concurrentemente, entonces:

Si hay un mensaje, se entrega sólo a uno de los procesos y los otros se bloquean. Si el buzón está vacío, todos los procesos se bloquean; cuando haya un mensaje disponible, sólo se activará y tomará el mensaje uno de los procesos bloqueados.

EXCLUSIÓN MUTUA: SOLUCIONES POR HARDWARE

INHABILITACIÓN DE INTERRUPCIONES

En una máquina monoprocesador, la ejecución de procesos concurrentes no puede superponerse; los procesos solo pueden intercalarse. Es más, un proceso continuará ejecutándose hasta que solicite un servicio el sistema operativo o hasta que sea interrumpido. Por lo tanto, para garantizar la exclusión mutua, es suficiente con impedir que un proceso sea interrumpido. Esta capacidad puede ofrecerse en forma de primitivas definidas por el núcleo del sistema para habilitar o inhabilitar las interrupciones. Un proceso puede hacer cumplir la exclusión mutua del siguiente modo:

While (cierto)

{

/*inhabilitar interrupciones */;

/* sección critica */;

/* habilitar interrupciones */;

/* resto */;

}

Puesto que la sección crítica no puede ser interrumpida, la exclusión mutua está garantizada. Sin embargo, el precio de esta solución es alto. La eficiencia de la ejecución puede verse notablemente degradada debido a que se limita la capacidad del procesador para intercalar programas. Un segundo problema es que está técnica no funciona en arquitecturas de multiprocesador. Cuando el sistema tenga más de un procesador, es posible (y habitual) que haya más de un proceso ejecutándose al mismo tiempo. En este caso, inhabilitar las interrupciones no garantiza la exclusión mutua.

INSTRUCCIONES ESPECIALES DE MAQUINA

En configuraciones multiprocesador, varios procesadores comparten el acceso a una memoria principal común. En este caso, no hay relación maestro/esclavo, sino que los procesadores funcionan independientemente en una relación de igualdad. No hay un mecanismo de interrupciones entre los procesadores en el que se pueda basar la exclusión mutua.

A nivel de hardware, como se ha mencionado, los accesos a posiciones de memoria excluyen cualquier otro acceso a la misma posición. Con esta base, los diseñadores han propuesto varias instrucciones de máquina que realizan dos acciones atómicamente, tales cono leer y escribir o leer y examinar, sobre una misma posición de memoria en un único ciclo de lectura de instrucción.

Puesto que estas acciones se realizan en un único ciclo de instrucción, no están sujetas a injerencias por parte de otras instrucciones.

-La instrucción COMPARAR Y FIJAR (TS, Test and Set)puede definirse de la siguiente forma:

booleano TS(int i)

{

if (I==0)

{

I=1;

return cierto;

}

else

{

return falso;

}

}

La instrucción examina el valor de su argumento i. Si el valor es 0 , lo cambia por 1 y devuelve cierto. En otro caso, el valor no se modifica y se devuelve falso. La función Comparar y Fijar se ejecuta atómicamente en su totalidad, es decir, no esta sujeta a interrupciones.

La instrucción INTERCAMBIAR se puede definir como sigue:

void intercambiar (int registro, int memoria)

{

int temp;

temp = memoria;

memoria = registro;

registro = temp;

}

Esta instrucción intercambia el contenido de un registro con el de una posición de memoria. Durante la ejecución de la instrucción, se bloquea el acceso a la posición de memoria de cualquier otra instrucción que haga referencia a la misma posición.

Propiedades de las soluciones con instrucciones de maquina

El uso de instrucciones especiales de la maquina para hacer cumplir la exclusión mutua tiene varias ventajas:

Es aplicable a cualquier número de procesos en sistemas con memoria compartida, tanto de monoprocesador como de multiprocesador. Es simple y fácil de verificar. Puede usarse para disponer de varias secciones críticas; cada sección crítica puede definirse con su propia variable. Algunas desventajas importantes son las siguientes:

SE EMPLEA ESPERA ACTIVA. Así pues, mientras un proceso está esperando para acceder a la sección crítica, continúa consumiendo tiempo del procesador. PUEDE PRODUCIRSE INANICIÓN. Cuando un proceso abandona la sección crítica y hay más de un proceso esperando, la selección es arbitraria. Así pues se podría denegar el acceso a algún proceso indefinidamente. PUEDE PRODUCIRSE INTERBLOQUEO. Supóngase la siguiente escena en un sistema monoprocesador. El proceso “P1″ ejecuta una instrucción especial (sea TS o Intercambiar) y entra su sección crítica. Se interrumpe a “P1″ para dar el procesador a “P2″, que tiene mayor prioridad. Si “P2″ intenta ahora usar el mismo recurso que “P1″, se le negará el acceso por el mecanismo de exclusión mutua. De este modo, “P2″ entrará en un bucle de espera activa. Sin embargo, “P1″ nunca será expedido porque su prioridad es menor que la del proceso listo “p2″.

SEMÁFOROS

Para solucionar problemas de procesos concurentes, se diseño un S.O. como un conjunto de procesos secuenciales, eficiente y fiables para dar soporte a la cooperación. Los procesos de usuario podrían utilizar estos mecanismos si el procesador y el S.O. los hacían disponible.

El principio fundamental es el siguiente, 20+ procesos pueden cooperar por medio de simples señales, de manera que se pueda obligar a un proceso a detener en una posición determinada hasta que reciba una señal específica. Para la señalización se usan variables especiales llamadas semáforos “S”, los procesos ejecutan las primitivas wait(s) si la señal aun no se transmitió, el proceso se suspende hasta que tiene lugar la transmisión.

A los semáforos se los contemplan como variables que tienen un N° entero sobre el que se definen las siguientes operaciones:

un semáforo puede iniciarse con un valor negativo la operación wait disminuye el valor del semáforo. Si el valor no es positivo el proceso que ejecuta wait se bloquea. las operaciones signal incrementa el N° del semáforo. Si el valor es positivo se desbloquea el proceso bloqueado por una operación wait. No hay forma de examinar o manipular los semáforos aparte de estas tres operaciones.

Las primitivas wait y signal se suponen atómicas, es decir no pueden ser interrumpidas y cada rutina puede considerarse como un peso indivisible.

Un semáforo solo puede tomar los valores 0 y 1. Son más sencillos de implantar y pueden demostrarse que tienen la misma potencia de expresión que los semáforos generales.

En ambos semáforos se emplean una cola para mantener los procesos en espera, la cuestión reside en el orden en que se retiran los procesos de la cola. La política utilizada el la de FIFO; el proceso que estuvo bloqueado durante mas tiempo se libera de la cola, se denomina semáforo robusto (incluye esta estrategia). Un semáforo débil no especifica el orden en que se retiran los procesos de la cola.

Los semáforos robustos garantizan la inexistencia de inanición en el algoritmo de exclusión mutua, pero no así en los semáforos débiles, se supone que los semáforos son siempre robustos ya que son los más adecuados y porque son los tipos de semáforos que más incluyen los S.O.

Implementación de los semáforos. Como se menciono anteriormente es impredecible que las operaciones wait y signal sean implementadas como primitivas atómicas.

La esencia del problema del productor/consumidor, es la exclusion mutua: solo 1 proceso puede manipular un semáforo a la vez, en una operación wait o signal. Se pueden utilizar cualquier esquema de software con los algoritmos de Dekker o Peterson los que suponen una sobrecarga de procesos sustancial. Otra alternativa es usar uno de los esquemas de soporte del hardware p/la exclusion mutua..

En sistemas monoprocesador procesador, se pueden inhibir las interrupciones durante una operación wait o signal.

MONITORES

Los monitores son estructuras de un lenguaje de programación que ofrecen una funcionalidad equivalente a las de los semáforos pero son más fáciles de controlar. El concepto de monitor fue definido por primera vez en [HOAR 74] . La estructura de monitor se ha implementado en varios lenguajes de programación como: Pascal concurrente, Modulo-2, Java, etc.

En concreto, para una lista enlazada se puede necesitar un cierre que bloquee todas las listas enlazadas o bien un cierre por cada elemento de una lista.

Monitores con Señales: ( definición de Hoare )

Un monitor es un modulo de software que consta de uno o más procedimientos, una secuencia de inicio y uno datos locales. Sus características son las siguientes:

Solo los procedimientos del monitor acceden a variables de datos locales. Un proceso entra en el monitor invocando a uno de sus procedimientos. En el monitor solo un proceso puede ser ejecutado en un momento dado; cualquier otro proceso quedara suspendido esperando la disponibilidad del monitor. Al ser un proceso por vez, el monitor puede ofrecer un servicio de exclusión mutua fácilmente. Así una estructura de datos puede protegerse situándola dentro de un monitor.

Los monitores deben ofrecer herramientas de sincronización. Por ejemplo: si un proceso llama a un monitor y una vez dentro de él el proceso queda suspendido esperando alguna condición, hará falta un servicio que libere al monitor y lo deje disponible para el siguiente proceso. Mas tarde cuando la condición se cumpla el proceso suspendido podrá regresar al monitor y ejecutarse desde el momento de la suspensión.

El monitor proporciona variables de condición que son accesibles solo desde dentro del monitor.

Hay dos funciones para operar variables de condición:

cwait ©: suspende la ejecución del proceso que llama bajo la condición “c”. El monitor está ahora disponible para otro proceso. csignal ©: retorna la ejecución de un proceso suspendido después de un cwait, bajo la misma condición. Si hay varios procesos elige uno de ellos. Si un proceso de monitor ejecuta un csignal y no hay tareas esperando entonces el csignal de pierde.

Aunque un proceso puede entrar al monitor llamando a cualquiera de sus procedimientos, se puede decir que el monitor tiene un solo punto de acceso, custodiado para que solo un proceso este en el monitor en un instante dado. Si existen otros procesos tratando de entrar al monitor, estos se colocan en una cola de procesos suspendidos esperando la disponibilidad del monitor.

Un proceso dentro de un monitor puede suspenderse a sí mismo, temporalmente, bajo la condición X ejecutando cwait(x), entonces se coloca en una cola de procesos que esperan que cambie la condición X entonces ejecuta un csignal(x) que avisa a la cola de condición correspondiente de que la condición a cambiado.

En el código se puede apreciar la solución al problema de productor / consumidor usando monitores:

El modulo monitor, buffers_acotado, controla el buffer para almacenar y retirar caracteres. El monitor incluye dos variables de condición:

No-lleno es verdadero su hay lugar para agregar al menos un carácter.

No-vació es verdadero si hay al menos un carácter en el buffer.

Un productor solo puede agregar caracteres al buffer mediante el procedimiento añadir del monitor; el productor no tiene acceso directo al buffer. El procedimiento comprueba si hay espacio en el buffer, mediante la condición no-lleno, si no lo hay el proceso queda suspendido y cualquier otro proceso (consumidor o productor) puede entrar al monitor. Luego, cuando el buffer ya no esta lleno, el proceso se retira de la cola y es reactivado. Luego de añadir un carácter el proceso activa la condición no-vació.

La estructura misma del monitor garantiza la exclusión mutua (solo un proceso por vez puede acceder al buffer). Sin embargo, el programador debe situar correctamente las primitivas cwait( ) y csignal( ) en el monitor para evitar que los procesos depositen elementos en un buffer lleno o los extraigan de uno vació.

Un proceso sale del monitor inmediatamente después de ejecutar csignal( ).

Si csignal( ) se ejecuta antes del final entonces ese proceso libera el monitor y esta colocado en una lista de procesos suspendidos. Un nuevo proceso puede entrar el monitor.

Si no hay procesos esperando en la condición X, la ejecución de csignal (x) no tiene efecto.

Es posible cometer errores en la sincronización de los monitores, por ejemplo, si se omite cualquiera de las funciones csignal() en el monitor buffer _ acotado los procesos que entran en la cola de condición permanecen colgados permanentemente. Sin embargo la ventaja de los monitores es que todas las funciones de sincronización están incluidas dentro del monitor, lo que permite una fácil detección y corrección de fallas de sincronización.

Monitores con Notificación y Difusión (definición de Lampson y Redell)

Son varios los inconvenientes que presenta la solución de Hoare:

-Si el proceso que ejecuta el csignal( ) no ha terminado en el monitor, se necesitaran dos cambios de procesos adicionales: uno para suspender el proceso y otro para reanudarlo.

-La planificación de procesos asociados con las señales debe ser muy fiable. Si un proceso ejecuta un csignal ( ), el proceso de la cola de condición correspondiente debe activarse de inmediato, antes de que ingrese otro proceso del exterior o cambie la condición bajo la que se activó el proceso. Otro caso seria que un proceso productor escribe un carácter en el buffer y falla antes de dar la señal, entonces la cola de condición no-vacía se colgaría para siempre.

Lampson y Redell desarrollaron una definición de monitores para el lenguaje MESA [Lamp 80]. La estructura de mesa reemplaza la primitiva csignal( ) por cnotify( ). Cuando un proceso ejecuta cnotify(x) envía una notificación a la cola de condición X, lo cual no significa que el proceso que esta ocupando el monitor vaya a detenerse, simplemente el cnotify(x) avisa al proceso de la cola de condición correspondiente de que será reanudado en un futuro cercano. Puesto que esta no garantiza que un proceso exterior entre al monitor, el proceso debe comprobar la condición nuevamente.

En el código, la sentencia IF se reemplaza por un bucle While, lo cual genera una evaluación extra de la variable, pero sin embargo no hay cambios de procesos extra.

Una modificación útil seria asociar un temporizador de guardia a cnotify( ) que permitiría que un proceso que ha esperado durante el intervalo máximo sea situado en estado de listo, independientemente de sí se ha notificado la condición.

Con la norma de notificar a los procesos en lugar de reactivarlos, es posible añadir una primitiva de difusión cbroadcast. La difusión provoca que todos los procesos que están esperando por una condición se coloquen en el estado de listo. Esto es útil cuando un proceso no sabe cuantos procesos deben reactivarse.

El método Lampson/Redell es menos propenso a errores debido a que cada procedimiento comprueba la condición luego de ser despertado, por medio de la instrucción while, un proceso puede realizar una señal o una difusión incorrectamente sin provocar un error en el programa que la recibe.

Además este modelo presta un método mas modular de construcción de programas.

Hay dos niveles de condición que deben satisfacerse para los procesos secuenciales cooperantes.

Estructura de datos consistentes: significa que el monitor hace cumplir la exclusión mutua y concluye la operación de entrada o salida antes de permitir cualquier otra operación sobre el buffer. La misma condición del nivel 1 y, además disponer de suficiente memoria para que este proceso pueda completar su solicitud de asignación. PASO DE MENSAJES

Son 2 los requisitos básicos que deben satisfacerse cuando los procesos interactúan entre si.

Ellos son:

La sincronización La comunicación Los procesos tienen que sincronizarse para cumplir la exclusión mutua, los procesos cooperantes pueden necesitar intercambiar información.

El paso de mensajes es un método que permite que se realice ambas funciones. Este método tiene la ventaja de que es de fácil implementación en sistemas distribuidos y también es sistemas de multiprocesador y monoprocesador de memoria compartida.

La funcionalidad real del paso de mensajes, generalmente, se da por medio de un par de primitivas:

send(destino, mensaje)

receive(origen, mensaje)

Este es el conjunto mínimo de operaciones necesarias para que los procesos puedan dedicarse al paso de mensajes.

SINCRONIZACION

La comunicación de un mensaje entre 2 procesos implica cierto nivel de sincronización entre ambos. El receptor no puede recibir un mensaje hasta que sea enviado por otro proceso. Además hace falta especificar que le sucede a un proceso después de ejecutar una primitiva SEND o RECEIVE.

Considérese en primer lugar la primitiva send. Cuando se ejecuta una primitiva send en un proceso, hay 2 posibilidades: o bien el proceso emisor se bloquea hasta que recibe el mensaje o no se bloquea. Igualmente cuando un proceso ejecuta una primitiva RECEIVE, existen 2 opciones:

1) Si previamente se ha enviado algún mensaje, este es recibido y continua la ejecución.

2) Si no hay ningún mensaje esperando entonces:

a) el proceso se bloquea hasta que llega un mensaje o,

b) el proceso continúa ejecutando, abandonando el intento de recepción.

El emisor y el receptor pueden ser bloqueantes o no bloqueantes.

Existen 3 tipos de combinaciones pero un sistema solo implementa uno o dos.

I) Envío bloqueante, recepción bloqueante: tanto el emisor como el receptor se bloquean hasta que llega el mensaje; esta técnica se conoce como rendezvous.

II) Envío no bloqueante, recepción bloqueante: aunque el emisor puede continuar, el receptor se bloquea hasta que llega el mensaje solicitado. Es la combinación más útil.

III) Envío no bloqueante, recepción no bloqueante: nadie debe esperar.

El send no bloqueante es la forma más natural para muchas tareas de programación concurrente. Un posible riesgo del send no bloquente es que por error puede llevar a una situación en la que el proceso genere mensajes repetidamente.

Para el receive, la versión bloqueante es la mas natural para muchas tareas de programación concurrente. En general, un proceso que solicita un mensaje necesitara la información esperada antes de continuar.

DIRECCIONAMIENTO

Es necesario disponer de alguna forma de especificar en la primitiva send que proceso va a recibir el mensaje. La mayoría de las implementaciones permiten a los procesos receptores indicar el origen del mensaje que se va a recibir.

Los distintos esquemas para hacer referencia a los procesos en las primitivas send y receive se encuadran dentro de 2 categorías:

1) Direccionamiento directo: la primitiva send incluye una identificación específica del proceso de destino.

La primitiva receive se puede gestionar de 2 formas:

Una posibilidad requiere que el proceso designe explícitamente un proceso emisor. El proceso debe conocer de antemano de que proceso espera un mensaje. En otros casos es imposible especificar el proceso de origen por anticipado. 2) Direccionamiento indirecto: los mensajes no se envían directamente del emisor al receptor, sino a una estructura de datos compartidos formada por colas, que pueden guardar los mensajes temporalmente, que se denominan BUZONES (mailboxes). Para que 2 procesos se comuniquen, uno envía mensajes al buzón apropiado y el otro los retira. Una ventaja de este tipo de direccionamiento es que se desacopla a emisor y receptor, asegurando mayor flexibilidad en el uso de mensajes.

Relación entre emisores y receptores

UNO A UNO: permite que se establezca un enlace privado entre 2 procesos. Aísla su interacción de injerencias erróneas de otros procesos. MUCHOS A UNO: resulta útil para interacciones cliente-servidor. En este caso el buzón se llama puerto. UNO A MUCHOS: permite un emisor y varios receptores. La asociación de procesos a buzones puede ser ESTATICA o DINAMICA. Los puertos suelen estar asociados estáticamente con algún proceso en particular. El puerto se crea y se asigna al proceso permanentemente. Una relación de UNO A UNO se define de forma estática y permanentemente. Cuando hay varios emisores, la asociación a un BUZON puede realizarse dinámicamente. Se pueden utilizar primitivas como CONECTAR o DESCONECTAR.

Propiedad del buzón. en el caso de 1 puerto, normalmente pertenece y se crea por el RECPTOR. Entonces cuando se destruye el proceso, también se destruye el puerto.

Para los buzones en general el S.O. ofrece un servicio de creación de buzones. Son considerados como propiedad del proceso creador en cuyo caso se destruyen junto con el proceso, o como propiedad del S.O., en este caso se necesita una orden explicita para destruir el buzón.

FORMATO DE MENSAJES

Para algunos S.O. los diseñadores han elegido mensajes cortos y tamaños fijos para minimizar procesamiento y coste de almacenamiento. Si se van a pasar una gran cantidad de datos, estos pueden ponerse en un archivo y el mensaje simplemente hará referencia a este archivo. Una solución más flexible es utilizar mensajes de longitud variable.

DISCIPLINA DE COLA

La disciplina de cola más simple es FIFO, pero esta puede no ser suficiente para mensajes más urgentes que otros. Una opción es habilitar la especificación de prioridades de los mensajes, en función del tipo de mensajes o por designación del emisor. Otra es permitir al receptor examinar la cola de mensajes y seleccionar el mensaje a recibir a continuación.

EXCLUSION MUTUA

Con el siguiente algoritmo de muestra una forma de usar el PASO DE MENSAJES para cumplir la exclusión mutua.

Se usan RECEIVE bloqueantes y SEND no bloqueantes. Unos procesos concurrentes comparte un BUZON, EXMUT, que puede ser usado por todos los procesos. EXMUT (buzón) tiene inicialmente un único mensaje nulo. Un proceso que requiere entrar en su sección crítica intenta:

1) recibir el mensaje. Si el EXMUT(buzón) esta vacío, se bloquea el proceso.

2) Una vez que consiguió el mensaje, ejecuta su sección crítica y devuelve el mensaje al buzón.

El mensaje funciona como un testigo(TOKEN) que se pasa de proceso a otro.

Esta técnica supone que si hay más de un proceso ejecutando la acción RECEIVE concurrentemente, entonces:

Si hay un mensaje, se entrega solo a uno de los procesos y los demás se bloquean. Si el buzón esta vacío, todos se bloquean cuando hay un mensaje, solo se activara y tomara el mensaje uno de los procesos bloqueados. PROBLEMA DE LOS LECTORES/ESCRITORES

Descripción del problema:

Existe un área de datos compartida entre una serie de procesos, algunos sólo leen los datos (lectores) y otros sólo escriben datos (escritores). El problema es satisfacer las siguientes condiciones:

1. Cualquier número de lectores puede leer el archivo simultáneamente.

2. En el archivo sólo puede escribir un escritor en cada instante.

3. Si un escritor está accediendo al archivo, ningún lector puede leerlo.

El problema general de exclusión mutua, consiste en permitir a cualquiera de los procesos (lectores o escritores) leer o escribir en el área de datos. Esto hace necesario declarar cualquier acceso como una sección crítica donde los procesos tendrían que acceder uno a uno produciéndose intolerables retrasos, además se debe impedir que los escritores interfieran unos con otros y también que se realicen consultas mientras se llevan a cabo modificaciones

Aplicar la solución general al problema de los lectores/escritores sería inaceptablemente lenta. En este caso más restrictivo es posible crear soluciones más eficientes.

A continuación se examinan dos soluciones al problema:

PRIORIDAD A LOS LECTORES Es una solución que utiliza semáforos para respetar la exclusión mutua. Se permite el acceso a varios lectores, pero mientras que un escritor está accediendo a los datos compartidos, no se permite acceder a ningún escritor o lector.

El primer lector que intenta acceder debe esperar en el semáforo, Cuando haya al menos un lector, los lectores siguientes no necesitan esperar para entrar, se les da prioridad. El problema es que un escritor estará esperando mientras que haya al menos un lector leyendo, que luego podría dar paso a otro lector, en este caso el lector estará sujeto a inanición.

Se utiliza una variable global contlect para mantener el número de lectores y el semáforo x para que la actualización de contlect sea consistente. El semáforo esem controla el acceso al recurso compartido.

/* program lectores_escntores*/

int contlect;

semáforo x = 1, esem=1;

void lector()

{

while (cierto)

{

wait(x);

contlect++;

If (contlect==1)

wait(esem);

signal(x);

LEER_UNIDAD();

wait(x);

contlect—;

If (contlect==0)

signal(esem);

signal(x);

}

}

void escritor()

{

while (cierto)

{

wait(esem);

ESCRIBIR_UNIDAD();

signal(esem);

}

}

vold main() {

contlect = 0;

parbegln(tector, escritor);

}

Una solución al problema de los lectores/escritores por medio de semáforos; los lectores tienen prioridad.

2. PRIORIDAD A LOS ESCRITORES

Esta solución garantiza que no se permitirá acceder a los datos a ningún nuevo lector una vez que, al menos, un escritor haya declarado su deseo de escribir. Se utilizan los mismos semáforos que en la solución anterior y se añaden otros más:

• Un semáforo Isem que inhibe todas las lecturas cuando al menos un escritor desea acceder

• Una variable contesc que controla la activación de Isem

• Un semáforo y que controla la actualización de contesc

• Un semáforo y que controla la actualización de contesc

• Un semáforo z donde se encolan los lectores cuando ya hay uno en lsem

/* program lectores_escritores */

Int contlec, contesc;

semáforo x=1, y =1, z=1, esem=1, lsem=1;

void lector()

{

while (cierto)

{

wait(z);

wait(lsem);

wait(x);

contlect++;

if (contlect = = 1)

{

wait(esem);

}

signal(x);

signal(lsem);

signal(z);

LEER_UNIDAD();

wait(x);

contlect—;

if (contlect == 0)

signal(esem);

signal(x);

}

}

void escritor()

{

while (cierto)

{

wait(y);

contesc++;

if (contesc = = 1)

wait(lsem) ;

signal(y);

wait(esem);

ESCRIBIR_UNIDAD();

signal(esem);

wait(y);

contesc—;

If (contesc== 0)

signal(lsem);

signal(y);

}

}

void mailn()

{

contlect = contesc = 0;

parbegin (lector, escritor);

}