tfc descripcion


Ejercicio Exclusión Mutua.

Protocolo de exclusión mutua basado en variables de estado.

Problema 1. Considere “n” procesos (P0, P1, … , Pn-1) interconectados por unanillo
bidireccional. En cada sitio “i” existe una variable local Si. Cada proceso Pi puede leer y
escribir su propia variable Si, y además, mediante intercambio demensajes puede
consultar (modo solo lectura) la variable Si-1 de su vecino Pi-1 (P0 puede leer la variable
de Pn-1).

Sea “Ei” una función booleana que represente el derecho dePi a entrar en la sección
crítica en exclusión mutua. La idea básica del algoritmo es encontrar una función que
permita expresar “Ei” en términos de Si y Si-1 y que cumplala propiedad:

Ei(Si, Si-1) ⇒ ∀ j ≠ i ¬ Ej(Sj, Sj-1)

es decir, cuando la función “E” sea verdadera para el proceso “i”, será falsa para los
demás procesos diferentesde “i”.

Una implementación simple de esta idea consiste en hacer:

Ei(Si, Si-1) ≡ (Si – Si-1 = k) (considere que Si toma valores enteros)

¬ Ej(Sj, Sj-1) ≡ (Sj –Sj-1 = k’)

Una red desea aplicar este algoritmo y asigna inicialmente en todos los sitios Si = i
asumiendo que al inicio el P0 es el único que tendrá el privilegio deacceso a la sección
crítica.

1. ¿Cuáles son los valores de k y k’?

2. ¿Qué tiene que hacer un proceso Pi para liberar la sección crítica y que Pi+1 pueda
tomarla?3. Analiza las características de este algoritmo en cuanto a las condiciones de
Seguridad, Vitalidad y Orden, mensajes necesarios para la asignación y liberación de lasección crítica, y en cuanto a la tolerancia a fallas de comunicación.

4. Haz una comparación de las características con el algoritmo basado en anillo
unidireccional.