Algoritmo de exclusion mutua

Parte 1: Algoritmos de exclusión mutua
Protocolo de exclusión mutua basado en variables de estado.

Problema 1. Considere “n” procesos (P0, P1, … , Pn-1) interconectados por un anillobidireccional. 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 de mensajes puede consultar (modo solo lectura) lavariable 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 de Pi a entrar en la sección crítica en exclusión mutua. La idea básica delalgoritmo es encontrar una función que permita expresar “Ei” en términos de Si y Si-1 y que cumpla la propiedad:

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

es decir, cuando la función “E” seaverdadera para el proceso “i”, será falsa para los demás procesos diferentes de “i”.

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

Ei(Si, Si-1) ≡ (Si – Si-1 = k) (considere que Sitoma 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 quetendrá el privilegio de acceso a la sección crítica.

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

K=0 y K’=1

2. ¿Qué tiene que hacer un proceso Pi para liberar la sección crítica y que Pi+1 puedatomarla?
Se le suma 1 a Si para cuando se aplique Ei(Si, Si-1) ≡ (Si – Si-1 = k) k sea igual a cero y pueda entrar y para el caso de P0 quiere entrar a Pi sea hace Si%(n-1) y luego se hace Ei(Si, Si-1) ≡(Si – Si-1 = k) para que k =0 y pueda entrar.

3. Analiza las características de este algoritmo en cuanto a mensajes necesarios para la asignación de la sección crítica, y en cuanto a la tolerancia afallas de comunicación. Haz una comparación de ambas características con el algoritmo basado en anillo unidireccional.
Se requieren de 1 a n-1 mensajes para entrar en la región crítica....