jueves, 31 de mayo de 2012

Métodos de exclusión mutua con espera ocupada

Solución de Peterson


En 1981. G. L. Peterson descubrió una forma más sencilla para conseguir la exclu-sión mutua, lo cual hizo obsoleta la solución de Dekker. Este algoritmo consta de dos procedimientos escritos en ANSÍ C, lo que indica que hay que proporcionar prototipos de función para todas las funciones definidas y utilizadas. Es convencional la agrupación de dichos prototipos en archivos de encabezado. El primer renglón; de la figura incluye todos esos prototi-pos. Los detalles no son importantes por lo que no se enlistan en este libro.

Antes de utilizar las variables compartidas (es decir, antes de entrar a su región cri-tica). cada proceso llama a enter_region con su propio número de procesos. O o 1, como parámetro. Esta llamada provoca una espera, en caso necesario hasta que pueda entrar.


indude "prototypes.h" . .

#define false 0

#define true 1

#define N 2 . /• Numero de procesos */

int turn: /* ¿de quién es e1 turno? */

int interested[N) /• todos los valores Iniciales son 0(FALSE) •/

void enter_region(int process) /* proceso: quién entra (0 O 1) */

{

int other; . /* numero de los otros procesos •/

other = 1 - process: /* el opuesto de proceso ••I

interested(process) - TRUE: /• muestra que usted esta interesado */

turn = process: . /* establece bandera */

while (turn — proceess && interested[otherl -- TRUE) /* enunciado-null '.'



void 1eave_region(int process) /• proceso: quién sale (0 6 1) •/

intereseted(process) - FALSE: " 7* indica 1a salida de la región critica */



Después de terminar con las variables compartidas. el proceso llama a leave_region para indicar que ha terminado y permitir la entrada de otro proceso, si así lo desea.

Veamos cómo funciona esta solución. En principio, ningún proceso esta en su re-gión critica- Ahora, el proceso 0 llama a enter_region. Indica su interés por determinar el elemento de su arreglo y hace turn=0. Puesto que el proceso 1 no está interesado. enier_region regresa en forma inmediata. Si el proceso 1 llama ahora a enter_region. esperará hasta que interested[0}=FALSE. evento que sólo ocurre cuando el proceso O llama a leave_region.

Consideremos ahora el caso en que ambos procesos llaman a enter_region de for-ma casi simultánea- Ambos almacenarán su número de proceso en turn. Sólo cuenta la última operación; la primera se pierde. Supongamos que el proceso 1 almacena el nú-mero en último lugar, por lo que turn=1. Cuando ambos procesos lleguen al enunciado while. el proceso O se ejecuta O veces y entra a su región critica. El proceso 1 hace un ciclo y no entra a su región critica.




Instrucción TSL


Analizaremos ahora una propuesta que requiere poca ayuda del hardware. Muchas computadoras, en particular aquellas diseñadas teniendo en mente varios procesadores. tienen una instrucción TEST AND SET LOCK; (TSL) que funciona como sigue. Lee el contenido de una palabra de memoria en un registro para después almacenar un valor distinto de cero en esa dirección de memoria Las operaciones de lectura y almacenamiento de la palabra tienen la garantía de ser indivisibles: ninguno de los de más procesadores puede tener acceso a la palabra hasta terminar la instrucción. La CPU que ejecuta la instrucción TSL cierra el bus de memoria para prohibir a las demás CPU el acceso a la memoria hasta terminar.

Para utilizar la instrucción TSL, se emplea una variable compartida, fiag, la cual coordina el acceso a la memoria compartida. Cuando f1ag=0, cualquier proceso puede darle el valor de 1 mediante la instrucción TSL y después leer o escribir en la memoria compartida. Al terminar, el proceso vuelve a hacer flog=0 mediante una instrucción normal move.

¿Cómo puede utilizarse esta instrucción para evitar que dos procesos entren en for-ma simultánea a sus regiones criticas? La solución aparece en la figura. En ella se muestra una subrutina de cuatro instrucciones en un lenguaje ensamblador ficticio (pe-ro típico). La primera instrucción copia el valor anterior de flag en un registro y des-pués hace flag=l. Después, el valor anterior se compara con 0. Si es distinto de cero. la cerradura ya estaba establecida, por lo que el programa regresa al principio y realiza de nuevo la prueba. Tarde o temprano, valdrá O (cuando salga de su región critica el proceso que &e encuentra en ese momento en dicha región) y la subrutina regresa con la cerradura establecida. La eliminación de la cerradura es sencilla: el programa sólo tiene que almacenar un O fag. No se requieren instrucciones especiales.

Ahora se dispone de una solución directa al problema de la sección crítica- Ante» de entrar a su sección crítica, un proceso Dama a enter_region, que hace una espera ocupada basta que se elimina la cerradura- para entonces retomar la cerradura y repisar.

Al salir de la sección crítica, el proceso llama a leave_region. que almacena O en fag. Como con todas las soluciones basadas en las regiones criticas, tos procesos deben llamar a enter_region y leave_region en los instantes correctos para que el método funcione. Si un proceso hace un engaño, la exclusión mutua fallara.

enter_region:


ts1 register.flac copia fag al registro y hace fag=1;


cr.r register.#0 ¿fag=0?


jn.í enter_region: si era distinto de cero , la cerradura estaba establecida, por lo que hay que hacer un ciclo


reg regresa a quien hizo la llamada


entra a la region critica


leave_region:


mov fag.#0 almacena un 0 en flag


ret regresa a quien hizo la llamada

No hay comentarios:

Publicar un comentario en la entrada