2.8 EXCLUCION MUTUA: SOLUCIÓN POR HARDWARE Y SOFTWARE Publicado por 252m01so sistemas operativos , jueves, 8 de octubre de 2009 at 17:06, in

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:
1. P1 no está interesado en entrar en su sección crítica. Este caso es imposible porque implica que señal[1] = falso.
2. 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.
3. 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".