Sistemas Operativos
Por: 21-04-2009 por jhoanita | Categorías asociadas: Mecanismos de sincronización, Paralelo "A"

Nombre: Jhoana María Rojas Granda

SINCRONIZACION DE PROCESOS

Un proceso cooperativa es aquel que puede afectar o verse afectado por otros procesos que estén ejecutándose en el sistema. Los procesos cooperativos pueden compartir directamente un espacio de direcciones lógico o compartir los datos solo a través de archivos o mensajes.

El problema de la sección critica

Considere un sistema que consta de n procesos (P0, P1, ….Pn-1), cada proceso tiene un segmento de código, llamado sección critica, en el que el proceso puede modificar variables comunes, actualizar una tabla, escribir en un archivo. La característica importante del sistema es que, cuando un proceso esta ejecutando su sección critica, ningún otro proceso puede ejecutar su correspondiente sección crítica, es decir dos procesos no pueden ejecutar su sección crítica al mismo tiempo. El problema de la sección critica consiste en diseñar un protocolo que los procesos puedan usar para cooperar de esta forma, cada proceso debe solicitar permiso para entrar en su sección critica, la sección de código que implementa esta solicitud es la sección de entrada. La sección crítica puede ir seguida de una sección de salida.

Cualquier solución al problema de la sección crítica deberá satisfacer los tres requisitos:

Exclusión mutua.- Si el proceso P esta ejecutándose en una sección crítica, los demás procesos no pueden estar ejecutando sus secciones críticas.

Progreso.- Si ningún proceso esta ejecutándose su sección crítica y algunos procesos desean entrar en sus correspondientes secciones.

Espera limitada.- Existe un límite en el número de veces que se permite que otros procesos entren en sus secciones críticas después de que un proceso haya hecho una solicitud para entrar en su sección.

Si dos procesos abrieran archivos simultáneamente, las actualizaciones de la lista podrían llevar a una condición de carrera, otras estructuras de datos del kernel propensas a posibles condiciones de carrera son aquellas empleadas para controlar la asignación de memoria, las listas de procesos y para gestionar las interrupciones. Es responsabilidad de los desarrolladores del kernel asegurar que el sistema operativo este libre de tales condiciones de carrera.

Se usan dos métodos generales para gestionar las secciones críticas en los sistemas operativos, los kernel apropiativos y los kernel no apropiativos. Un kernel apropiativo permite que un proceso sea desalojado mientras se esta ejecutando en modo kernel, un kernel no apropiativo no permite que un proceso que se este ejecutando en modo kernel sea desalojado, el proceso en modo kernel se ejecutara hasta que salga de dicho modo, hasta que se bloquee o hasta que ceda voluntariamente el control de la CPU.

Solución de Peterson

La solución de Peterson se restringe a dos procesos que van alternando la ejecución de sus secciones críticas y de sus secciones restantes. Los procesos se numeran como P0 y P1. Por conveniencia, cuando hablemos de Pi, usaremos Pj para referirnos al otro proceso, es decir j es igual a 1-i.

La solución de Peterson requiere que los dos procesos compartan dos elementos de datos:

Int turn;

Boolean flag

La variable turn indica que proceso va a entrar en su sección crítica. La matriz flag se usa para indicar si un proceso esta preparado para entrar en su sección critica.

Ahora vamos a demostrar que esta solución es correcta. Necesitamos demostrar que:

1. La exclusión mutua se conserva.

2. El requisito de progreso se satisface.

3. El requisito de espera limitada se cumple.

Hardware de Sincronización

En general, podemos afirmar que cualquier solución al problema de la sección crítica requiere una herramienta muy simple, un cerrojo. Es decir, un proceso debe adquirir un cerrojo antes de entrar en una sección crítica y liberarlo cuando salga de la misma.

El soporte hardware puede facilitar cualquier tarea de programación y mejorar la eficiencia del sistema.

Semáforos

La diversas soluciones hardware al problema de la sección crítica, basadas en las instrucciones TestAndSet() y Swap().

Un semáforo S es una variable entera a la que, dejando aparte la inicialización, solo se accede mediante dos operaciones atómicas estándar wait() y signal().

Utilización

Los sistemas operativos diferencian a menudo entre semáforos contadores y semáforos binarios. El valor de un semáforo contador puede variar en un dominio no restringido, mientras que el valor de un semáforo binario solo puede ser 0 o 1. En algunos sistemas, los semáforos binarios se conocen como cerrojos mutex, ya que son cerrojos que proporcionan exclusión mutua.

Podemos usar semáforos binarios para abordar el problema de la sección crítica en el caso de múltiples procesos. Cuando la cuenta del semáforo llega a 0, todos los recursos estarán en uso.

Implementación

La principal desventaja de la definición de semáforo dada aquí es que requiere una espera activa. Mientras un proceso esta en su sección critica, cualquier otro proceso que intente entrar en su sección critica debe ejecutar continuamente un bucle en el código de entrada.

La espera activa desperdicia ciclos de CPU que algunos otros procesos podrían usar de forma productiva. Este tipo de semáforo también se denomina cerrojo mediante bucle sin fin, ya que el proceso permanece en un bucle sin fin en espera de adquirir un cerrojo.

Un proceso bloqueado, que esta esperando en un semáforo S, debe reiniciarse cuando algún otro proceso ejecuta una operación signal(). El proceso se reinicia mediante una operación wakeup(), que cambia al proceso de estado de espera al estado de preparado.

La lista de procesos en espera puede implementarse fácilmente mediante un campo de enlace en cada bloque de control de proceso. Cada semáforo contiene un valor entero y un puntero garantice un tiempo de espera limitado consiste en usar una cola FIFO, donde el semáforo contenga punteros a ambos extremos de la cola.

El aspecto critico de los semáforos es que se deben ejecutar atómicamente, tenemos que garantizar que dos procesos no puedan ejecutar al mismo tiempo sendas operaciones wait() y signal() sobre el mismo semáforo.

Interbloqueos e inanición

La implementación de un semáforo con una cola de espera puede dar lugar a una situación en la que dos o más procesos estén esperando indefinidamente a que se produzca un suceso que solo puede producirse como consecuencia de las operaciones efectuadas por otro de los procesos en espera. El suceso en cuestión es la ejecución de una operación signal(). Cuando se llega a un estado así, se dice que estos procesos se han interbloqueado.

Los sucesos que más nos interesan aquí son los de adquisición y liberación de recursos, pero también hay otros tipos de sucesos que pueden dar lugar a interbloqueos.

Otro problema relacionado con los interbloqueos es el del bloqueo indefinido o muerte por inanición, una situación en la que algunos procesos esperan de forma indefinida dentro del semáforo. El bloqueo indefinido puede producirse si añadimos y eliminamos los procesos a la lista asociada con el semáforo utilizando un esquema LIFO.

Problemas clásicos de sincronización

Problema del búfer limitado

El problema del buffer limitado se ha presentado habitualmente se utiliza para ilustrar la potencia de las primitivas de sincronización.

Podemos interpretar este código como un productor que genera los búferes llenos para el consumidor o como un consumidor que genera búferes vacios para el productor.

Problema de los lectores-escritores

Algunos de estos procesos pueden simplemente querer leer la base de datos, mientras que otros pueden desear actualizarla. Diferenciamos entre estos dos tipos de procesos denominando a los primeros lectores y a los otros escritores.

Para asegurar que estos problemas no afloren, requeriremos que los procesos escritores tengan acceso exclusivo a la base de datos compartida. Este problema de sincronización se denomina problema de los lectores y escritores. Desde que se lo estableció originalmente, este problema se ha utilizado para probar casi todas las nuevas primitivas de sincronización. El problema de los lectores y escritores presenta diversas variantes, todas las cuales utilizan prioridades. El más sencillo, conocido como primer problema de los lectores-escritores, requiere que ningún lector se mantenga en espera a menos que un escritor haya obtenido ya permiso para utilizar el objeto compartido.

Una solución a cualquiera de estos problemas puede dar como resultado un problema de inanición. En el primer caso, los escritores pueden bloquearse indefinidamente en el segundo caso, son los lectores los que pueden morir de inanición. Por esta razón, se han propuesto otras variantes del problema.

Los cerrojos lector-escritor resultan especialmente útiles en las situaciones siguientes:

- En aquellas aplicaciones en las que sea fácil identificar que procesos solo desean leer los datos compartidos.

- En aquellas aplicaciones que tengan mas procesos lectores que escritores.

Problema de la cena de los filósofos

El problema de la cena de los filósofos se considera un problema clásico de sincronización, no por su importancia practica ni porque los informáticos tengan aversión a los filósofos, sino porque es un ejemplo de una amplia clase de problemas de control de concurrencia. Es una representación sencilla de la necesidad de repartir varios recursos entre varios procesos de una forma que no se produzcan interbloqueos ni bloqueos indefinidos.

Una solución sencilla consiste en representar cada palillo mediante un semáforo. Un filosofo intenta hacerse con un palillo ejecutando una operación wait() en dicho semáforo y libera sus palillos ejecutando la operación signal() en los semáforos adecuados, por tanto, los datos compartidos son donde todos los elementos de palillo se inicializan con el valor 1.

Monitores

Aunque los semáforos proporcionan un mecanismo adecuado y efectivo para el proceso de sincronización, un uso incorrecto de los mismos puede dar lugar a errores de temporización que son difíciles de detectar, dado que estos errores solo ocurren si tienen lugar algunas secuencias de ejecución concretas y estas secuencias no siempre se producen.

Utilización

Un tipo, o un tipo abstracto de datos, agrupan una serie de datos privados con un conjunto de métodos públicos que se utilizan para operar sobre dichos datos. Un tipo monitor tiene un conjunto de operaciones definidas por el programador que gozan de la característica de exclusión mutua dentro del monitor.

La representación de un tipo monitor no puede ser utilizada directamente por los diversos procesos. Así, un procedimiento definido dentro de un monitor solo puede acceder a las variables declaradas localmente dentro del monitor y a sus parámetros formales. De forma similar, a las variables locales de un monitor solo un proceso este activo cada vez dentro del monitor.

Existen dos posibilidades:

1. Señalizar y esperar.- P espera hasta que Q salga del monitor o espere a que se produzca otra condición.

2. Señalizar y continuar.- Q espera hasta que P salga del monitor o espere a que se produzca otra condición.

Sincronización en Windows Xp:

Windows Xp protege el acceso a los recursos globales utilizando bloqueos basados en bucles sin fin. Para la sincronización de hebras fuera del kernel, Windows Xp proporciona objetos despachadores, utilizando un objeto despachador, las hebras de sincronización empleando diferentes mecanismos, incluyendo mútex, semáforos, sucesos y temporizadores.

El sistema protege los datos compartidos requiriendo que una hebra adquiera la propiedad de un mútex para acceder a los datos y libere dicha propiedad cuando termine. Los sucesos son similares a las variables de condición, es decir pueden notificar a una hebra en espera que una condición deseada se ha producido.

Sincronización en Windows Linux:

El kernel de Linux proporciona bloqueos mediante bucles sin fin y semáforos para establecer bloqueos en kernel. En una maquina SMP, el mecanismo fundamental de bloqueo es el que se basa en el uso de bucles sin fin, y el kernel se diseña de modo que dicho tipo de bloqueo se mantenga durante periodos de tiempo corto.

Las maquinas con un solo procesador, los bloqueos mediante bucle sin fin no resultan apropiados y se reemplazan por un mecanismo de activación y desactivación de la función de apropiación en el kernel.

Sincronización en Windows Pthreads:

Este proporciona cerrojos mútex, las variables de condición y cerrojos de lectura-escritura para la sincronización de hebras. Esta API está disponible para los programadores y no forma parte de ningún kernel.

Los cerrojos mútex representan la técnica fundamental de sincronización utilizada en Pthreads. Un cerrojo mutex se utiliza para proteger las secciones críticas de código.


      Leer más


Usted debería Ingresar para comentar.