A partir de aquí, iremos haciendo un estudio progresivo sobre las posibles soluciones de todo tipo que intentarán resolver la exclusión mutua y el sincronismo entre procesos. Muchas de estas soluciones fracasarán en su intento. Otras lo lograrán, pero mostrarán ciertas deficiencias que nos llevarán a pensar en nuevas primitivas de concurrencia.

Nuestro viaje comenzará con las soluciones que utilizan memoria compartida. Dentro de este grupo, distinguiremos entre mecanismos software y hardware que emplean espera ocupada, y los que usan espera bloqueada (semáforos y monitores).

En esta sección se van a estudiar varios métodos que intentan resolver el problema de la ejecución en exclusión mutua de las secciones críticas de los procesos. En primer lugar, introduciremos algunos métodos que no producen una solución aceptable, sin embargo, nos ayudarán a comprender mejor el problema.

La solución más sencilla es que cada proceso prohiba todas las interrupciones justo antes de entrar en su región crítica y las permita de nuevo justo antes de salir. Esto funciona correctamente, pues el código del sistema operativo sólo se activa como consecuencia de la ocurrencia de interrupciones. Si el sistema operativo no puede ejecutarse mientras se ejecuta la sección crítica, es obvio que no podrá realizar un cambio de proceso en la CPU, por lo tanto, la sección crítica se ejecutará en exclusión con todo proceso.

Pero con las interrupciones prohibidas no se servirá ni la interrupción de reloj ni ninguna otra. Dado que la asignación del procesador a los diferentes procesos sólo cambia como consecuencia de una interrupción, sea de reloj o de cualquier otra clase, el prohibir interrupciones hace que no pueda conmutarse el procesador a otro proceso.

Esta solución es poco atrayente porque le da a los procesos de usuario la capacidad de prohibir las interrupciones. Si no las vuelve a habilitar, sería el fin del sistema. Además, si el computador tuviera dos o más procesadores, la desactivación de las interrupciones sólo afectaría al procesador que ejecutó la instrucción. El resto de los procesadores continuarían normalmente y podrían acceder a la memoria compartida sin mayor problema.

Sin embargo, a veces es conveniente que el propio sistema operativo prohiba las interrupciones mientras está actualizando sus variables o listas. La prohibición de interrupciones es un mecanismo adecuado para garantizar la exclusión mutua dentro del núcleo, pero poco recomendable para procesos de usuario.

Analicemos una solución mediante software. Consiste en tener una variable de cerradura compartida por los procesos. Antes de que un proceso entre en su sección crítica comprueba el valor de la cerradura. Si ésta vale 0, el proceso cambia el valor a 1 y entra en la sección crítica. Si ésta ya vale 1, el proceso espera hasta que la variable valga 0. Por lo tanto, un 0 indica que ningún proceso se encuentra en una sección crítica y un 1 indica que algún proceso está en una sección crítica. A continuación se presenta el fragmento del código (en lenguaje C) de un proceso que quiere entrar en una sección crítica. A las instrucciones, relativas a proporcionar la exclusión mutua, que se ejecutan antes de entrar en la sección crítica, se les llama protocolo de entrada; a las que se ejecutan después de ejecutar el código de la sección crítica se les llama protocolo de salida. En este caso el protocolo de entrada lo constituyen la conjunción de las instrucciones while y ‘cerrado = 1'. El protocolo de salida lo conforma la instrucción ‘cerrado = 0'.

Esta solución no funciona. Suponga que un proceso lee la cerradura y comprueba que tiene un valor 0. Antes de que pueda ponerla a 1 se planifica otro proceso. Éste comprueba el valor de cerrado, al ser 0 entra en su sección crítica. Si antes de que este proceso termine la sección crítica se vuelve a planificar al primer proceso no se habrá logrado la exclusión mutua. El problema proviene de que el protocolo de entrada es una sección crítica más, pues se dedica a modificar una variable compartida (la variable cerrado). Obsérvese que si el protocolo de entrada se pudiera ejecutar sin cambios de proceso la solución sería efectiva.

Acabamos de ver cómo el uso de una variable de cerradura fracasa en su intento. Analicemos otras posibles soluciones software. Necesitamos unas primitivas de exclusión mutua que protejan el acceso a las secciones críticas. Utilizaremos el siguiente esquema general (figura 4.2) : tendremos una pareja de construcciones entrar_exclusión_mutua y salir_exclusión_mutua que encapsulan el código de cada proceso que tiene acceso a la variable compartida. La construcción 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.

La variable compartida número_proceso, con un valor inicial 1, mantiene un registro del turno para entrar en la sección crítica. El Proceso_uno ejecuta el ciclo while do. Como en un principio número_proceso vale 1, proceso_uno entra en la sección crítica. Proceso_dos encuentra que número_proceso equivale a 1 y se mantiene dentro de su ciclo while do. Cada vez que el proceso_dos obtiene el procesador, se limita a repetir el ciclo en espera de que número_proceso valga 2, de manera que proceso_dos no entra en su sección crítica y la exclusión mutua está garantizada. El procesador está en uso mientras proceso_dos no hace nada (excepto verificar el valor de número_proceso), 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. Los procesos deben entrar y salir de su sección crítica de manera estrictamente alterna. Si un proceso es más corto que otro, la velocidad de uno de ellos condicionará al otro. Si uno de los procesos termina, el otro no podrá continuar. Esta primera solución utiliza una variable global, y ella ocasiona el problema de la sincronización con alternancia estricta.

Por ello, en la segunda versión se usan dos variables: p1dentro, que es cierta si el proceso uno está en su sección crítica y, p2dentro, que también será cierta si el proceso dos está en su sección crítica.

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.

Por tanto, en el momento en que realiza su verificación deberá estar seguro de que el otro proceso no podrá pasar su verificación.

Ahora cambiamos la bandera antes de realizar la verificación, indicando su deseo de ejecutar la sección crítica. 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.

En la anterior versión quedábamos atrapados en la verificación, por tanto, ahora intentaremos escapar de ella. Una manera de hacerlo es retardando la verificación, para comprobar si el otro también desea entrar. La exclusión mutua está garantizada y no ocurre bloqueo mutuo, pero puede ocurrir un aplazamiento indefinido. 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. Veamos cómo puede suceder: puesto que no podemos hacer suposiciones sobre sus velocidades podría suceder que se ejecutasen en tándem, esto es, uno ejecuta una instrucción y el otro, a continuación, la correspondiente. Luego, 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 (esto no se puede consentir para ciertas aplicaciones que deben ejecutar en un tiempo concreto como el software de control de vuelo, un marcapasos o un sistema de control de tráfico aéreo...).

Gestiona elegantemente la exclusión mutua. Utiliza, además de las banderas de intención de entrar, una variable turno (proceso_favorecido) que resuelve en caso de conflicto. 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 (figura 4.7).

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.

Se estudia ahora una solución que requiere apoyo del hardware. Muchos ordenadores, en particular aquellos diseñados teniendo en mente varios procesadores, tienen una instrucción TEST AND SET LOCK (TSL). Esta instrucción máquina provoca la lectura del contenido de una palabra de la memoria en un registro, y el almacenamiento de un valor distinto de cero en dicha palabra de memoria. Al ser una instrucción máquina, las operaciones de lectura y escritura de la palabra tienen la garantía de ser indivisibles (atómicas). Además, ninguno de los demás procesadores puede tener acceso a la palabra hasta terminar la instrucción. El procesador que ejecuta la instrucción TSL cierra el bus de la memoria para prohibir a los demás el acceso a la memoria hasta el término de la instrucción.

A continuación se muestra una solución al problema de la exclusión mutua que se basa en la instrucción TSL. La solución viene expresada en un lenguaje ensamblador ficticio (pero típico). Existen dos subrutinas que los procesos llamarán como protocolos de entrada y salida:

La variable cerrado es una variable compartida que se utiliza para coordinar el acceso a las secciones críticas. Cuando vale 0 se permite el acceso y cuando vale 1 no. Cuando un proceso quiera entrar a una sección crítica llamará a la subrutina entrar_sección. Esta subrutina estará ejecutando un ciclo hasta que cerrado valga 0. Obsérvese que esta solución funciona, mientras que la solución de la variable cerradura no funcionaba. La clave está en que la instrucción TSL realiza atómicamente el comprobar que cerrado vale 0 y el asignarle el valor 1.