ALGORITMO DE DEKKER.
INTRODUCCION:
SECCIONES CRITICAS:La exclusión mútua debe ponerse en practica sólo cuando los procesos obtienen acceso a datos compartidos modificables; cuando los procesos realizan operaciones que no entran en conflicto con otras, debe permitirse que procedan concurrentemente. Cuando un proceso obtiene acceso a datos compartidos modificables, se dice que se encuentra en una sección crítica.
Mientras un proceso se encuentra en su sección crítica, otros procesos pueden, claro está, seguir ejecutándose fuera de sus secciones críticas.
El matemático holandés Dekker fue el primero en presentar una elegante realización en software para la esclusión mútua:
___________________________________________________________________________________________________
___________________________________________________________________________________________________
PRIMERA VERSION DE LAS PRIMITIVAS DE EXCLUSION MUTUA:
Este es un primer intento por especificar el código que permite poner en práctica la Exclusión Mutua en el contexto de un programa concurrente con dos procesos. La construccion parbegin/parend hace que proceso_uno y proceso_dos operen como procesos concurrentes. Cada uno de estos procesos se encuentra dentro de un ciclo infinito, entrando una y otra vez en sus secciones críticas.
Si usted observa en la siguiente página, verá que se pone en práctica entrar_ewxclusión_mutua mediante un simple ciclo while que se repite hasta que numero_proceso es igual al numero del proceso; salir_exclusión mutua se pone en practica con una sola instrucción que asigna a número_proceso el numero del otro proceso
Proceso_uno ejecuta el ciclo while do. Como en un principio numero_proceso vale 1, proceso_uno entra en su sección crítica. Proceso_dos encuentra que numero_proceso equivale a 1 y se mantiene dentro de su ciclo while do. Cada vez que proceso_dos obtiene el procesador, se limita a repetir el ciclo en espera de que numero_proceso valga 2, de manera que proceso_dos no entra en su sección crítica y la exclusión mutua está garantizada. Como el procesador esta en uso mientras proceso_dos no hace nada (excepto verificar el valor el valor de numero_proceso), esto se conoce como espera activa. La espera activa se considera una técnica aceptable cuando las esperas anticipadas son cortas; de lo contrario, la espera activa puede resultar costosa.
______________________________________________________________________________________________________
SEGUNDA VERSION DE LAS PRIMITIVAS DE EXCLUSION MUTUA:
En la primera versión había solamente una variable global y ello ocasionó el problema de la sincronización en Tandem. Por eso, en la segunda versión se usan dos variables: p1adentro, que es cierta si proceso_uno se encuentra en su sección crítica y p2adentro que es cierta si proceso_dos se encuentra a su vez en su sección crítica. Ahora proceso_uno permanece bloqueado en una espera activa mientras sea cierta p2adentro. Con el tiempo proceso_dos abandona su sección crítica y ejecuta su propio código de salida de exclusión mutua, asignando a p2adentro el valor falso. En ese momento, proceso_uno asigna a p1 adentro el valor cierto y entra en su sección crítica.
De nuevo surgen las sutilezas de la programación concurrente. Como proceso_uno y proceso_dos son procesos concurrentes, podrían intentar ejecutar simultaneamente sus códigos de entrada a exclusión mutua. En un principio p1adentro y p2adentro son falsas. Proceso_uno podría verificar el valor de p2adentro y encontrar que es falso; entonces, antes que proceso_uno pueda asignar a p1adentro y encontrar que es falso. En ese instante proceso_uno asigna el valor cierto a p1adentro y entra en su sección crítica; por su parte, proceso_dos asigna el valor cirto a p2adentro y entra en su sección crítica. Ambos procesos están simulataneamente en sus secciones críticas, de manera que la versión dos ni siquiera garantiza la exclusión mutua.
______________________________________________________________________________________________________
TERCERA VERSION DE LAS PRIMITIVAS DE EXCLUSION MUTUA:
La versión trata de resolver el problema de la segunda haciendo que cada proceso asigne el valor cierto a su bandera antes de realizar la verificación. Así, proceso_uno indica su deseo de entrar en su sección crítica asignando el valor cierto ap1deseantrar. Si p2deseaentrar es falso, entonces proceso_uno entra en su sección crítica y hace que proceso_dos espere, si acaso desea entrar en su sección crítica. De esta manera se garantiza la exclusión mutua y se tiene al parecer una solución correcta.
Se ha resuelto un problema pero se ha creado otro. Si cada proceso asigna el valor cierto a su bandera antes de realizar la verificación, entonces cada proceso podrá encontrar la bandera del otro con valor cierto y los dos entrarán en un ciclo infinito. Este es un ejemplo de bloqueo mutuo de dos procesos.
______________________________________________________________________________________________________
CUARTA VERSION DE LAS PRIMITIVAS DE EXCLUSION MUTUA:
El problema de la version tres, es que cada proceso puede bloquearse en su verificación respectiva. Se necesita una forma de "escapar" de estas verificaciones. La cuarta versión resuelve el problema ligando a un proceso que se encuentre dentro del ciclo a asignar repetidamente el valor falso a su bandera por periodos cortos; esto permitirá que el otro proceso salga de su ciclo while, con el valor cierto todavía en su propia bandera.
La exclusión mutua esta garantizada y no se puede producir un bloqueo mutuo, pero puede originarse otro problema potencialmente grave: un aplazamiento indefinido. Los procesos podrían ejecutarse en tandem, es decir, cada proceso puede asignar el valor cierto a su bandera, realizar la verificación, entrar en el cuerpo del ciclo while, asignar el valor falso a su bandera, asignar el valor cierto a su bandera y después repetir la secuencia comenzando con la verificación. Mientras ocurre esto, las condiciones verificadas s siguen cumpliendo.
Es claro que esta situación tiene muy pocas posibilidades de ocurrir, pero podría darse el caso. Por tanto la versión cuatro resulta inaceptable. Si un sistema que usara este tipo de exclusión mutua se empleara para controlar un vuelo espacial, un marcapasos o un sistema de control de tráfico aéreo, estarían latentes la posibilidad de un aplazamiento indefinido y la consiguiente falla del sistema.
______________________________________________________________________________________________________
ALGORITMO DE DEKKER
El algoritmo de Dekker resuelve la posibilidad de aplzamiento indefinido de la versión cuatro. Procesi_uno indica su deseo de entrar en su sección crítica. Si la bandera de proceso_dos tiene el valor cierto a su bandera. En seguida realiza la verficación, en la cual comprueba si proceso_dos también desea entrar en su seción crítica. Si la bandera de proceso_dos tiene el valor falso, proceso_uno pasa por alto el cuerpo del ciclo y entra en su sección crítica.
Supongase empero que cuando proceso_uno realiza su verificación descubre que la bandera de proceso_dos tiene el valor cierto. Esto hace que proceso_uno ejecute el cuerpo de su ciclo while. Dentro del ciclo examina la variable proceso_favorecido que simultaneamente en sus secciones críticas. Si proceso_uno es el favorecido, pasa por alto el cuerpo de la condicional y ejecuta repetidamente el ciclo while en espera de que proceso_dos asigne el valor falso a su bandera.
JORGE DURAN ZEPEDA Y SERGIO O. AGUILAR QUIRART