Mecanismos de exclusión mutua

Exclusión mutua

Estos trozos de código reciben el nombre de secciones o regiones críticas, pudiéndose asimilar el concepto de exclusión mutua en el uso de estos recursos a la idea de exclusión mutua en la ejecución de las secciones críticas. Idear soluciones que garanticen la exclusión mutua es uno de los problemas fundamentales de la programación concurrente. Muchas son las alternativas y tipos de mecanismos que se pueden adoptar. Existen diferentes soluciones software y algún hardware. Al menos, una solución apropiada debería cumplir las condiciones siguientes:

-Que no haya en ningún momento dos procesos dentro de sus respectivas secciones críticas. -Que no hagan suposiciones a priori sobre las velocidades relativas de los procesos o el número de procesadores disponibles. -Que ningún proceso que esté fuera de su sección crítica pueda bloquear a otros. -Que ningún proceso tenga que esperar un intervalo de tiempo arbitrariamente grande para entrar en su sección crítica. -Que exista un límite en el número de veces que se permite que otros procesos entren en sus secciones críticas después de que un proceso haya hecho una solicitud para entrar en su sección crítica y antes de que la misma haya sido concedida.

Soluciones Software

Se necesitan unas primitivas de exclusión mutua que protejan el acceso a las secciones críticas, para ello, se utilizará el siguiente esquema general:

Primera tentativa: alternancia

La exclusión mutua está garantizada. El procesador está en uso mientras proceso_dos no hace nada (excepto verificar el valor de turno), esto se conoce como espera ocupada o 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. La exclusión mutua está garantizada, pero a un precio alto. Esta primera solución utiliza una variable global, y ella ocasiona el problema de la sincronización con alternancia estricta.

Segunda tentativa: falta de exclusión

Se utilizarán dos variables. P1 y P2 son concurrentes e intentarán entrar simultáneamente en su sección crítica. No está garantizada la exclusión mutua. El problema se debe a que, entre el momento en que un proceso determina que puede seguir y el momento en que se asigna cierto a su bandera (variable centinela), hay tiempo suficiente para que el otro verifique su bandera y entre en su sección crítica.

Tercera tentativa: espera infinita

Se actuará a la inversa; es decir, cuando un proceso quiera utilizar el recurso, primero indica que quiere hacerlo y luego se esperará hasta que quede libre. Se puede producir un bloqueo mutuo, los dos procesos entrarán en un ciclo infinito. Esto se debe a que cada uno de los procesos se puede bloquear en su verificación.

Cuarta tentativa: aplazamiento indefinido

En la anterior versión los procesos quedaban atrapados en la verificación, por tanto, ahora se intentará escapar de ella. Una manera de hacerlo es retardando la verificación, para comprobar si el otro también desea entrar. Se introduce un tratamiento de cortesía. Cuando un proceso ve que el otro quiere utilizar el recurso, le cede el turno cortésmente. La exclusión mutua está garantizada y no ocurre bloqueo mutuo, pero puede ocurrir un aplazamiento indefinido debido al retraso [delay(random)]. Un aplazamiento indefinido o inanición es una situación en la que se posterga indefinidamente el progreso en la ejecución de uno o más procesos.

Algoritmo de Dekker

Es una combinación de los programas Primer Intento y Cuarto Intento anteriormente descritos.Da la posibilidad de que el otro proceso entre en su sección crítica una segunda vez si lo hace antes que el proceso que acaba de dejar el bucle de espera, asigne el valor cierto a su intención de entrar. Pero cuando de nuevo tiene el procesador, realiza la asignación y es su turno, así que se ejecuta. En consecuencia, no produce aplazamiento indefinido. Esta solución asegura la exclusión mutua y está libre de interbloqueos. Este algoritmo sirve para conseguir la exclusión mutua entre dos procesos. El algoritmo utilizado para N procesos tan sólo tiene un interés teórico ya que consume demasiado tiempo.

Algoritmo de Peterson

Simplifica el algoritmo de Dekker. El protocolo de entrada es más elegante con las mismas garantías de exclusión mutua, imposibilidad de bloqueo mutuo y de aplazamiento indefinido.