Exclusión Mutua 4l461j

Exclusión Mutua Sistemas Operativos



En un sistema multiprogramado con un único procesador, los procesos se intercalan en el tiempo (Round Robin) para dar apariencia de ejecución simultánea. Aunque no se consigue un procesado en paralelo real, y aunque se produce un sobrecargado en la u por el hecho de tener que cambiar de tarea constantemente, las ventajas de todo esto son muy elevadas.



Uno de los grandes problemas que nos podemos encontrar es que el hecho de compartir recursos está lleno de riesgos. Por ejemplo, si dos procesos hacen uso al mismo tiempo de una variable global y ambos llevan a cabo tanto operaciones de lectura como de escritura sobre dicha variable, el orden en que se ejecuten estas lecturas y escrituras es crítico, puesto que se verá afectado el valor de la variable.



Los algoritmos de exclusión mutua se usan en programación concurrente para evitar el uso simultáneo de recursos comunes, como variables globales, por fragmentos de código conocidos como secciones críticas.



La mayor parte de estos recursos son las señales, contadores, colas y otros datos que se emplean en la comunicación entre el código que se ejecuta cuando se da servicio a una interrupción y el código que se ejecuta el resto del tiempo.



La técnica que se emplea por lo común para conseguir la exclusión mutua es inhabilitar las interrupciones durante el conjunto de instrucciones más pequeño que impedirá la corrupción de la estructura compartida (la sección crítica). Esto impide que el código de la interrupción se ejecute en mitad de la sección crítica.

Concepto de exclusión mutua. 

Consiste en que un solo proceso excluye temporalmente a todos los demás para usar un recurso compartido de forma que garantice la integridad del sistema.

Concepto de sección crítica. 

Es la parte del programa con un comienzo y un final claramente marcados que generalmente contiene la actualización de una o más variables compartidas.



Para que una solución al problema de la exclusión mutua sea válida, se tienen que cumplir una serie de condiciones:



Hay que garantizar la exclusión mutua entre los diferentes procesos a la hora de acceder al recurso compartido. No puede haber en ningún momento dos procesos dentro de sus respectivas secciones críticas.



No se deben hacer suposiciones en cuanto a la velocidad relativa de los procesos en conflicto.



Ningún proceso que esté fuera de su sección crítica debe interrumpir a otro para el a la sección crítica.



Cuando más de un proceso desee entrar en su sección crítica, se le debe conceder la entrada en un tiempo finito, es decir, que nunca se le tendrá esperando en un bucle que no tenga final.

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

Para solucionar el problema de la exclusión mutua vamos a tener tres tipos de soluciones: Soluciones

software.

Soluciones

hardware.

Soluciones

aportadas por el Sistema Operativo

Algunos ejemplos de algoritmos de exclusión mutua son: 

Deshabilitando interrupciones



Variables de candado



Alternancia estricta



Solución de Peterson



La instrucción TSL



Algoritmo de Dekker



Semáforos



Mutex



Pasaje de Mensajes



Barreras

Deshabilitando interrupciones 

En un sistema con un solo procesador, la solución más simple es hacer que cada proceso deshabilite todas las interrupciones justo después de entrar a su región crítica y las rehabilite justo después de salir.

Variables de candado 

Considere tener una sola variable compartida (de candado), que al principio es 0. Cuando un proceso desea entrar a su región crí- tica primero evalúa el candado. Si este candado es 0, el proceso lo fija en 1 y entra a la región crítica. Si el candado ya es 1 sólo espera hasta que el candado se haga 0. Por ende, un 0 significa que ningún proceso está en su región crítica y un 1 significa que algún proceso está en su región crítica

Alternancia estricta 

Garantiza la exclusión mutua, pero su desventaja es que acopla los procesos fuertemente, esto significa que los procesos lentos atrasan a los procesos rápidos.



Esta solución requiere que los dos procesos se alternen de manera estricta al entrar en sus regiones críticas (por ejemplo, al poner archivos en la cola de impresión). Ninguno podría poner dos archivos en la cola al mismo tiempo. 

Solución de Peterson 

El algoritmo de Peterson es un algoritmo de programación concurrente para exclusión mutua, que permite a dos o más procesos o hilos de ejecución compartir un recurso sin conflictos, utilizando sólo memoria compartida para la comunicación. 

La instrucción TSL 

Algunas computadoras, en especial las diseñadas con varios procesadores en mente, tienen una instrucción tal como TSL REGISTRO, CANDADO (Evaluar y fijar el candado) que funciona de la siguiente manera. Lee el contenido de la palabra de memoria candado y lo guarda en el registro RX, y después almacena un valor distinto de cero en la dirección de memoria candado. Se garantiza que las operaciones de leer la palabra y almacenar un valor en ella serán indivisibles; ningún otro procesador puede acceder a la palabra de memoria sino hasta que termine la instrucción.

Algoritmo de Dekker 

Es un algoritmo de programación concurrente para exclusión mutua, que permite a dos procesos o hilos de ejecución compartir un recurso sin conflictos. Fue uno de los primeros algoritmos de exclusión mutua inventados, implementado por Edsger Dijkstra.



Si ambos procesos intentan acceder a la sección crítica simultáneamente, el algoritmo elige un proceso según una variable de turno. Si el otro proceso está ejecutando en su sección crítica, deberá esperar su finalización.

Semáforos  Un

semáforo es una variable especial (o tipo abstracto de datos) que constituye el método clásico para restringir o permitir el a recursos compartidos (por ejemplo, un recurso de almacenamiento del sistema o variables del código fuente) en un entorno de multiprocesamiento (en el que se ejecutarán varios procesos concurrentemente).

Mutex 

Cuando no se necesita la habilidad del semáforo de contar, algunas veces se utiliza una versión simplificada, llamada mutex. Los mutexes son buenos sólo para istrar la exclusión mutua para cierto recurso compartido o pieza de código. Se implementan con facilidad y eficiencia, lo cual hace que sean especialmente útiles en paquetes de hilos que se implementan en su totalidad en espacio de .Unmutex es una variable que puede estar en uno de dos estados: abierto (desbloqueado) o cerrado (bloqueado).

Pasaje de Mensajes 

Este método de comunicación entre procesos utiliza dos primitivas (send y receive) que, al igual que los semáforos y a diferencia de los monitores, son llamadas al sistema en vez de construcciones del lenguaje.



La primera llamada envía un mensaje a un destino especificado y la segunda recibe un mensaje de un origen especificado (o de cualquiera, si al receptor no le importa). Si no hay un mensaje disponible, el receptor se puede bloquear hasta que llegue uno. De manera alternativa, puede regresar de inmediato con un código de error.

Barreras  Algunas

aplicaciones se dividen en fases y tienen la regla de que ningún proceso puede continuar a la siguiente fase sino hasta que todos los procesos estén listos para hacerlo. Para lograr este comportamiento, se coloca una barrera al final de cada fase. Cuando un proceso llega a la barrera, se bloquea hasta que todos los procesos han llegado a ella.