Algoritmos de Exclusion Mutua

El programa pro01 muestra un primer intento de especificar el código para forzar la aplicación de la exclusión mutua, dentro del contexto de un programa concurrente con dos procesos. La construcción cobegin/coend hace que el proceso uno y el proceso dos operen como procesos concurrentes. Cada uno de estos procesos entra en un ciclo, entrando repetidamente en su sección crítica. En el programa pro01 entra exclusión mutua se implementa por un ciclo 'while' simple, que mantiene el ciclo hasta que pnumero iguala al número del proceso; saledeexclusionmutua se implementa por una instrucción simple que ajusta pnumero al número del otro proceso. 
        program pro01;
        (* primera version de las primitivas de exclusión mutua *)
        var
           pnumero: integer;
           nolineas: integer;
 
        process uno;
        var
           lin: integer;
 
        begin
           for lin := 1 to 50 do
              begin
                while pnumero = 2 do
                      null;
                nolineas := nolineas + 1;
                pnumero := 2
              end
        end;  (* uno *)
 
        process dos;
        var
           lin: integer;
 
        begin
           for lin := 1 to 50 do
              begin
                 while pnumero = 1 do
                    null;
                 nolineas := nolineas + 1;
                 pnumero := 1
              end
        end;  (* dos *)
        
        begin
           pnumero := 1;
           nolineas := 0;
           cobegin
              uno;
              dos
           coend;
           writeln('Total de líneas =',nolineas)
        end.
 
El proceso uno ejecuta el while-do. Como pnumero es inicialmente 1, el proceso uno entra a su sección crítica. El proceso dos encuentra pnumero igual a 1 y permanece encerrado en su ciclo de while-do. Cuando el proceso dos obtiene el procesador, simplemente permanece en el ciclo en espera de que pnumero se ajuste a 2, así que proceso dos no entra en su sección crítica y la exclusión mutua queda garantizada.
El proceso uno acaba por terminar la ejecución dentro de su sección crítica (ha de suponerse que no hay ciclos infinitos) y ajusta pnumero a 2, permitiendo así que el proceso dos entre en su sección crítica.
La exclusión mutua está garantizada, pero el precio es alto. El proceso uno debe de entrar primero, así es que si el proceso dos está listo para entrar en su sección crítica, deberá tardar bastante. Después de que el proceso uno entre y salga de su sección crítica, entonces el proceso dos deberá seguir, aun cuando el proceso uno desee reentrar y el proceso dos no esté listo. Entonces, los procesos deberán entrar y salir de sus secciones críticas en estricta alternancia. Si un proceso requiere hacer esto muchas más veces que el otro, está restringido a operar a una velocidad más lenta de la que requiere. El sistema no debe interbloquearse completamente; por lo menos puede proceder un proceso, si ambos intentan entrar simultáneamente en sus secciones críticas. Si uno de los proceso termina, entonces el otro no podrá continuar.

En la primera solución existe solamente una variable global simple, y esto forzaba la aparición del problema de sincronización bloqueada. Así es que, en la segunda versión (pro02), se usan dos variables: p1dentro, la cual es verdadera si el proceso uno está dentro de su sección crítica, y p2dentro, que es verdadera si proceso dos está dentro de su sección crítica. Ahora, mientras p2dentro sea verdadera, el proceso uno permanece encerrado en una espera. El proceso dos acaba abandonando su sección crítica y realiza su propio código de salida de exclusión mutua, ajustando p2dentro en falso. El proceso uno ajusta entonces p1dentro en verdadero y entra en su sección crítica. Mientras p1dentro sea verdadera, proceso dos no podrá entrar en su sección crítica.
La sutileza de la programación concurrente vuelve a salir a la superficie. como quiera que el proceso uno y el proceso dos son concurrentes, ambos podrían intentar en forma simultánea sus secuencias de código de entrada de exclusión mutua. A continuación se muestra el listado del programa pro02. 
        program pro02;
        (* segunda version de las primitivas de exclusión mutua *)
        var
           p1dentro, p2dentro: boolean;
           nolineas: integer;
 
        process uno;
        var
           lin: integer;
        
        begin
           for lin := 1 to 50 do
              begin
                 while p2dentro do
                    null;
                 p1dentro := true;
                 nolineas := nolineas + 1;
                 p1dentro := false
              end
        end;  (* uno *)
 
 
        process dos;
        var
           lin: integer;
 
        begin
           for lin := 1 to 50 do
           begin
              while p1dentro do
                 null;
              p2dentro := true;
              nolineas := nolineas + 1;
              p2dentro := false
           end
        end;  (* dos *)
 
        begin
           p1dentro := false;
           p2dentro := false;
           nolineas := 0;
           cobegin
              uno;
              dos
           coend;
           writeln('Total de líneas = ',nolineas)
        end.
En principio, tanto p1dentro como p2dentro son falsas. El proceso uno podría probar p2dentro y encontrarla falsa; entonces, antes de que el proceso uno pueda ajustar p1dentro en verdadero, el proceso dos podría probar p1dentro y encontrarla falsa. En este punto, el proceso uno coloca p1dentro en verdadero y entra a su sección crítica, y el proceso dos ajusta p2dentro en verdadero y entra a su sección crítica. Ambos procesos se encuentran en sus secciones críticas al mismo tiempo, así es que la segunda versión ni siquiera garantiza la exclusión mutua. A continuación se muestra la corrida del programa pro02. 
        - Interpreter Version P5.3 -
        Program pro02     ...  execution begins ...
 
        Total de líneas =             91
 
        Program terminated normally
        Type r and RETURN to rerun
        r
 
        Program pro02     ...  execution begins ...
 
        Total de líneas =             94
 
        Program terminated normally
        Type r and RETURN to rerun
        ^Z
        End of data file - program terminating
En la segunda versión existe una dificultad, pues entre el tiempo en que un proceso determina (en la prueba del while) que puede seguir adelante y el tiempo en que el proceso ajusta una bandera para indicar que está en su sección crítica, hay tiempo suficiente para que el otro proceso pruebe su bandera y entre en su sección crítica. Por tanto, una vez que el proceso intenta la prueba del while, debe tener la seguridad de que el otro proceso no puede ir más allá de su propia prueba del while. La tercer versión intenta resolver esto haciendo que cada proceso ajuste su bandera antes de la ejecución del while. 
        program pro03;
        (* tercer version de primitivas de exclusion mutua *)
        var
           p1quiere, p2quiere: boolean;
           nolineas: integer;
 
        process uno;
        var
           lin: integer;
 
        begin
           for lin := 1 to 20 do
           begin
              p1quiere := true;
              while p2quiere do
                 null;
              nolineas := nolineas + 1;
              p1quiere :=false
           end
        end;  (* uno *)
 
 
        process dos;
        var
           lin: integer;
 
        begin
           for lin := 1 to 20 do
           begin
              p2quiere := true;
              while p1quiere do
                 null;
              nolineas := nolineas + 1;
              p2quiere := false
           end
        end;  (* dos *)
 
        begin
           nolineas := 0;
           cobegin
              uno;
              dos
           coend;
           writeln('Total de líneas =',nolineas)
        end.
Se ha solucionado un problema pero se ha creado otro. Si cada proceso ajusta su bandera antes de proceder con la prueba del while, entonces, cada proceso se encontrará con la bandera del otro ajustada y entrarán para siempre en el ciclo while-do. Este es un ejemplo de un interbloqueo de dos procesos (la corrida de este programa causa que la máquina quede bloqueada). 
        - Interpreter Version P5.3 -
        Program pro03     ...  execution begins ...
 
        (El programa bloquea la computadora, deberá dar reset)
El problema de la tercer versión es que todos los procesos pueden encerrarse en su ciclo while-do respectivo. Es necesaria una manera de "romper" estos ciclos. La cuarta versión logra esto al forzar cada proceso de ciclo a ajustar su bandera en falso repetidamente en períodos breves; esto permitirá al otro proceso proceder más allá de su prueba del while, con su bandera todavía conectada. 
        program pro04;
        (* cuarta version de primitivas de exclusion mutua*)
        var
           p1quiere, p2quiere: boolean;
           nolineas: integer;
 
        process uno;
        var
           lin: integer;
 
 
        begin
           for lin := 1 to 20 do
           begin
              p1quiere := true;
              while p2quiere do
              begin
                 p1quiere := false;
                 sleep(random(10));
                 p1quiere := true
              end;
              nolineas := nolineas + 1;
              p1quiere := false
           end
        end;  (* uno *)
 
        process dos;
        var
           lin: integer;
 
        begin
           for lin := 1 to 30 do
           begin
              p2quiere := true;
              while p1quiere do
              begin
                 p2quiere := false;
                 sleep(random(10));
                 p2quiere := true
              end;
              nolineas := nolineas + 1;
              p2quiere := false
           end
        end;  (* dos *)
 
        begin
           nolineas := 0;
           cobegin
              uno;
              dos
           coend;
           writeln('Total de líneas =',nolineas)
        end.
A continuación se muestra una corrida para este programa. 
        - Pascal-FC for IBM PC compatibles -
        - Compiler Version P5.2
 
        G L Davies  &  A Burns, University of Bradford
 
        Compiling pro04      ...
        Compilation complete
 
        - Interpreter Version P5.3 -
        Program pro04     ...  execution begins ...
 
        Total de líneas =            50
 
        Program terminated normally
        Type r and RETURN to rerun
        ^Z
        End of data file - program terminating
La exclusión mutua queda garantizada y no puede ocurrir el interbloqueo, pero puede presentarse otro problema devastador en potencia, el de postergación indefinida. Veamos como. Debido a que no pueden hacerse suposiciones acerca de las velocidades relativas de los procesos concurrentes asincrónicos, habrá que considerar todas las secuencias de ejecución posibles. El proceso podría, por ejemplo, proceder en tándem. Cada proceso puede seguir la siguiente secuencia: ajustar su bandera en verdadero, hacer la prueba del while, entrar en el cuerpo del ciclo while, ajustar su bandera en falso, retardarse, ajustar su bandera en verdadero y, luego, repetir la secuencia, comenzando con la prueba del while. En tanto hacen esto, las condiciones de prueba permanecerán verdaderas. Desde luego que la probabilidad de que tal operación ocurra es muy baja, pero puede ocurrir. Por lo tanto, la cuarta versión es inaceptable. Si un sistema que utiliza este sistema de exclusión mutua estuviera controlando un vuelo espacial, un marcapasos cardíaco o un sistema de control de tráfico aéreo, la posibilidad de que ocurra una postergación indefinida con el consecuente fallo del sistema no es admisible.

ALGORITMO DE PETERSON.
Otro interesante algoritmo para manejar la exclusión mutua entre dos procesos, es el algoritmo de Peterson (programa ptrson), del cual presentamos el siguiente listado y corrida. 
        program peterson;
 
        (*
        Algoritmo de Peterson para la exclusión mutua de dos  procesos
        *)
 
        var
           nolineas, turno : integer;
           band1, band2: boolean;
 
        process uno;
 
        var
           lin: integer;
        begin
           for lin := 1 to 20 do
           begin
              band1:= true;    (* anuncia el intento de entrar *)
              turno:= 2;      (* le da prioridad al otro proceso *)
              while band2 and (turno = 2) do
                 null;
              nolineas := nolineas + 1;
              band1:= false
           end
        end;
 
 
        process dos;
 
        var
           lin: integer;
        begin
           for lin := 1 to 30 do
           begin
              band2:= true;    (* anuncia el intento de entrar *)
              turno:= 1;      (* le da prioridad al otro proceso *)
              while band1 and (turno = 1) do
                 null;
              nolineas := nolineas + 1;
              band2:= false
           end
        end;
 
        begin
           nolineas := 0;
           turno := 1;
           band1 := false;
           band2 := false;
           cobegin
              uno;
              dos
           coend;
           writeln('Total de Líneas: ',nolineas)
        end.
 
 
        C:\PASFC>pfc ptrson.pfc
 
        - Pascal-FC for IBM PC compatibles -
        - Compiler Version P5.2
        G L Davies  &  A Burns, University of Bradford
 
        Compiling peterson   ...
        Compilation complete
 
        - Interpreter Version P5.3 -
        Program peterson  ...  execution begins ...
 
        Total de Líneas:             50
 
        Program terminated normally
 
        Type r and RETURN to rerun
        ^Z
        End of data file - program terminating
Los procesos comparten las variables band1, band2 y turno. Inicialmente band1 = band2 = false, y el valor de turno no tiene relevancia (pero debe ser 1 o 2). En el listado de los procesos, se puede apreciar que para entrar en la sección crítica, el proceso uno primero asigna true a band1 y luego afirma que es el turno del proceso dos para entrar si así lo desea (turno=2). Si ambos procesos tratan de entrar a la vez, se asignará turno como 1 y 2 aproximadamente al mismo tiempo. Sólo una de estas asignaciones durará; la otra ocurrirá, pero será reemplazada de inmediato. El valor eventual de turno decide a cual de los dos procesos se le permitirá entrar primero en su sección crítica.
Ahora demostraremos que esta solución es correcta. Necesitamos demostrar: (1) que se conserva la exclusión mutua, (2) que se respeta el requisito de progreso y (3) que se cumple el requisito de espera limitada.
Para demostrar la propiedad (1) observamos que cada proceso entra en su sección crítica únicamente cuando band2 = false o turno = 1 para el proceso uno (band1 = false o turno = 2 para el proceso dos). Observe también que, si ambos procesos pueden estar en ejecución en sus secciones críticas al mismo tiempo, entonces band1 = band2 = true. Estas dos observaciones representan que uno y dos no pueden haber cumplido con éxito la condición del while aproximadamente al mismo tiempo, ya que el valor de turno puede ser 1 o 2, pero no los dos. Por consiguiente, uno de los procesos, digamos uno, debió ejecutar con éxito la condición while, mientras que dos tuvo que ejecutar por lo menos un enunciado adicional ("turno=2"). Sin embargo, como en ese momento band1=true y turno=2, y esta condición persistirá mientras uno se encuentre en su sección crítica, se concluye que se conserva la exclusión mutua.
Para comprobar las propiedades (2) y (3) observamos que se puede evitar que el proceso dos entre en su sección crítica únicamente cuando se queda en el ciclo while con la condición band1=true y turno = 1; éste es el único ciclo. Si uno no está listo para entrar en la sección crítica, entonces band1= false, y dos puede entrar en su sección crítica. Si uno ha establecido band1 = true y también está ejecutando su enunciado while, entonces turno = 1 o turno = 2. Si turno = 2, entonces uno entrará en la sección crítica. Empero, una vez que uno sale de su sección crítica, volverá a establecer band1=false, permitiendo que dos entre en su sección crítica. Si uno vuelve a establecer band1 como true, también deberá establecer turno=2. Por lo tanto, como dos no cambia el valor de la variable turno mientras ejecuta el ciclo while, dos entrará en la sección crítica (progreso) después de, como máximo, una entrada de uno (espera limitada).

SEMÁFOROS

Dijkstra extractó las nociones clave de la exclusión mutua en su concepto de semáforo. Un semáforo es una variable protegida cuyo valor puede ser accesado y alterado tan sólo por las operaciones wait, signal y una operación de inicialización del semáforo initial. Los semáforos binarios sólo pueden tomar los valores 0 y 1. Los semáforos contadores pueden tomar valores enteros no negativos.
La operación wait en el semáforo S, escrito wait(S), opera de la siguiente manera: 
                       if S > 0
                               then S:=S - 1
                               else (espera en S)
 
La operación signal en el semáforo S, escrito signal(S), opera de la siguiente manera: 
                       if (uno o más procesos están en espera en S)
                               then (deja proseguir a uno de estos procesos)
                               else S:=S+1
 
Supondremos que hay una diciplina de colas del primero en entrar - primero en salir para los procesos que esperan a completar un wait(S). La ejecución de las instrucciones wait y signal son indivisibles. La exclusión mutua en el semáforo, S, es aplicada en wait(S) y signal(S). Si varios procesos intentan ejecutar wait(S) al mismo tiempo, sólo uno podrá proseguir; los otros permanecerán en espera. Los semáforo y las operaciones de semáforos pueden implementarse en software o hardware. En general, se implementan en el núcleo del sistema operativo, donde se controlan los cambios de estado de un proceso. El programa sem01 que se lista a continuación, muestra como pueden utilizarse los semáforos para aplicar la exclusión mutua. 
        program sem01;
        (*
         solución por semáforos al problema de la
         exclusión mutua
        *)
 
        var
          nolineas: integer;
          mutex: semaphore;  (* declaración del semáforo *)
 
        process uno;
        var
          lin: integer;
        begin
          for lin := 1 to 20 do
       begin
            wait(mutex);               (* Espera por el semáforo  *)
            nolineas := nolineas + 1;  (* sección crítica *)
            signal(mutex)              (* libera el semáforo *)
          end
        end;  (* uno *)
 
        process dos;
        var
          lin: integer;
        begin
           for lin := 1 to 20 do
           begin
              wait(mutex);
              nolineas := nolineas + 1;
              signal(mutex)
           end
        end;  (* dos *)
 
        begin
          nolineas := 0;
          initial(mutex,1);  (* se inicializa el semáforo *)
          cobegin
            uno;
            dos
          coend;
          writeln('Total de Líneas = ',nolineas)
        end.
A continuación se muestran los resultados de la corrida del programa. 
        - Pascal-FC for IBM PC compatibles -
        - Compiler Version P5.2
        G L Davies  &  A Burns, University of Bradford
 
 
        Compiling sem01      ...
        Compilation complete
 
        - Interpreter Version P5.3 -
        Program sem01     ...  execution begins ...
 
        Total de Líneas =             40
 
        Program terminated normally
 
        Type r and RETURN to rerun
        ^Z
        End of data file - program terminating
SINCRONIZACIÓN DE PROCESOS CON SEMÁFOROS
Cuando un proceso emite una petición de entrada/salida, se bloquea a sí mismo para esperar a que termine esta operación. Algunos procesos deben despertar al proceso bloqueado. Tal interacción es un ejemplo de un protocolo de bloqueo/despertar.
En forma más general,supóngase que un proceso desee ser informado de la ocurrencia de un evento. Supóngase que otro proceso es capaz de detectar que ese acontecimiento ya ha ocurrido. El siguiente programa (sem02) muestra cómo pueden utilizarse las operaciones de semáforos para implementar un mecanismo simple de sincronización de bloqueo/despertar de dos procesos. 
        program sem02;
        (*
         Proceso de sincronización de bloqueo/despertar
         con semáforos
        *)
 
        var
          mutex: semaphore;  (* declaración del semáforo *)
 
        process uno;
        begin
            writeln('Cosas preliminares de Uno');
            wait(mutex);               (* Espera por el semáforo  *)
            writeln('Otras cosas del Uno');
        end;  (* uno *)
 
        process dos;
        begin
            writeln('Cosas preliminares del Dos');
            signal(mutex);
            writeln('Otras cosas del Dos.');
        end;  (* dos *)
 
 
        begin
          initial(mutex,0);
          cobegin
            uno;
            dos
          coend;
        end.
 
 
        Compiling sem01      ...
        Compilation complete
        - Interpreter Version P5.3 -
        Program sem01     ...  execution begins ...
 
        Cosas preliminares de Uno
        Cosas preliminares del Dos
        Otras cosas del Dos.
        Otras cosas del Uno
 
 
        Program terminated normally
        Type r and RETURN to rerun
        ^Z
        End of data file - program terminating
El proceso uno ejecuta algunas cosas preliminares y después ejecuta wait(mutex). El semáforo ha sido inicializado a cero, de modo que el proceso debe esperar. El proceso dos ejecuta signal(mutex) para señalar que el evento ha ocurrido. Esto permite proceder al proceso uno.
Obsérvese que este mecanismo trabaja incluso cuando proceso dos detecta y señala el evento antes de que el proceso uno ejecute wait(mutex); el semáforo habrá sido incrementado de 0 a 1, así es que wait(mutex), decrementa el semáforo de 1 a 0, y proceso uno proseguirá sin tener que esperar a que ocurra el evento.

MONITORES
Anteriormente presentamos algunos algoritmos para la implementación de las primitivas de exclusión mutua, y se mencionaron los semáforos de Dijkstra. Pero estos métodos tienen varias debilidades: son tan primitivos que es difícil expresar la solución de problemas de concurrencia más complejos, y su presencia en los programas concurrentes dificulta aún más el problema de probar la corrección del programa. El uso incorrecto de estas primitivas, ya sea intensionado o accidental, podría corromper la operación de un sistema concurrente. Por este motivo, los investigadores se han entregado a la tarea de buscar construcciones de exclusión mutua de más alto nivel que
  • faciliten expresar los problemas de concurrencia complejos
  • faciliten probar la corrección del programa
  • resulte muy difícil (cuando no imposible) su uso incorrecto o corrupción por parte del usuario.
Tal vez, la más importante de estas construcciones sea el monitor, sugerida por Dijkstra, después por Brinch Hansen, y luego refinada por Hoare.
MONITORES.
Un monitor es una construcción de concurrencia que contiene los datos y procedimientos necesarios para realizar la asignación de un recurso compartido determinado, o de un grupo de recursos compartidos. Para cumplir con la función de asignación de recurso, un proceso debe llamar a determinada entrada al monitor. Muchos procesos pueden tratar de entrar al monitor en diversos momentos. Pero la exclusión mutua es aplicada rígidamente en los límites del monitor. Sólo se permite la entrada a un proceso a la vez. Los procesos que deseen entrar cuando el monitor está en uso deben esperar. La espera es administrada de forma automática por el monitor. Como la exclusión mutua está garantizada, se evitan los desagradables problemas de concurrencia (como los resultados indeterminados) señalados con anterioridad.
Los datos contenidos en el monitor pueden ser globales, para todos los procedimientos dentro del monitor, o locales, para un procedimiento específico. Todos estos datos sólo son accesibles dentro del monitor, no hay forma de que un proceso de fuera del monitor pueda accesar sus datos. Esto se llama encapsulamiento de información, una técnica de estructuración del sistema que facilita en gran medida el desarrollo de sistemas de software más confiables.
Si el proceso que llama a la entrada al monitor encuentra que el recurso ha sido asignado, entonces el procedimiento del monitor llama a wait. El proceso podría permanecer dentro del monitor, pero esto violaría la exclusión mutua si en este momento entrara otro proceso al monitor. Por tanto, al proceso que llama a wait se le hace esperar fuera del monitor hasta que el recurso sea liberado.
El proceso que tiene al recurso llamará finalmente una entrada al monitor para devolver el recurso al sistema. Esta entrada tan sólo aceptaría el recurso de regreso y esperaría la llegada de otro proceso de petición. Pero puede haber varios procesos esperando por el recurso, así es que el monitor llama a signal para permitir que uno de los procesos en espera adquiera el recurso y salga del monitor. Si un proceso señala el regreso (o liberación) del recurso, y no hay otro esperando, entonces la señal no tiene efecto alguno (pero el monitor ha recapturado el recurso). Está claro que un proceso que espera un recurso debe hacerlo fuera del monitor, para permitir que otro proceso dentro del monitor regrese el recurso.
Para asegurar que un proceso en espera de un recurso acabe consiguiéndolo, el monitor le otorga prioridad sobre un nuevo proceso que pida entrar al monitor. De otra manera, el nuevo proceso toma el recurso antes de que el que está en espera vuelva al monitor. Si esta desafortunada secuencia tuviera lugar de forma repetida, entonces un proceso en espera sería postergado indefinidamente.
De hecho, los procesos podrían desear (necesitar) esperar fuera del monitor por varias razones, como veremos en los ejemplos. Así que se introduce la noción de una variable de condición. Se asocia una variable de condición individual a cada una de las razones por las que un proceso pueda necesitar esperar. Las operaciones delay y resume son entonces modificadas para incluir el nombre de la variable de condición que se está esperando o señalando.
delay(nombredelavariabledecondicion) resume(nombredelavariabledecondicion)

Las variables de condición son muy distintas de las "convencionales" con las que estamos familiarizados. Al definir una variable de condición se establece una cola. Un proceso que llama a delay se asocia a la cola y un proceso que llama a resume provoca la extracción de un proceso en espera de la cola y su entrada al monitor. Puede darse por sentada la existencia de una diciplina de colas FIFO, aunque los esquemas de prioridades pueden ser útiles en algunas situaciones.

A continuación se muestra el listado de un programa (mons01) que resuelve el mismo problema de exclusión mutua, descrito anteriormente, utilizando monitores. 
        program mons01;
        (*
           Problema de conteo de líneas usando monitores
        *)
 
           const
             nprocs = 10;
           var
             lin: integer;
 
        monitor contador;  (* se define el monitor *)
 
           export       (* define los procedimientos a exportar *)
              inc, escribe;
 
           var             (* variables locales al monitor  *)
         nolineas: integer;
 
           procedure inc;
           begin
              nolineas := nolineas + 1
           end;  (* inc *)
 
           procedure escribe;
           begin
              writeln('Total de líneas = ',nolineas:2)
           end;  (* escribe *)
 
        begin  (* cuerpo del monitor *)
 
          nolineas := 0
 
        end;  (* monitor contador *)
 
 
        process type turnos; 
          (* se define un tipo de proceso llamado turnos*)
         var
              loop: integer;
        begin
          for loop := 1 to 20 do
            contador.inc 
        (* se invoca el procedimiento inc del monitor *)
        end;  (* turnos *)
 
 
        var
          proceso: array[1..nprocs] of turnos;
 
        begin
          cobegin
             for lin := 1 to nprocs do
                proceso[lin]
          coend;
          contador.escribe
        end.
Los resultados del programa anterior obtenidos en una corrida son: 
        - Pascal-FC for IBM PC compatibles -
        - Compiler Version P5.2
 
        G L Davies  &  A Burns, University of Bradford
 
 
        Compiling mons01     ...
        Compilation complete
 
        - Interpreter Version P5.3 -
        Program mons01    ...  execution begins ...
 
        Total de líneas = 200
 
        Program terminated normally
        Type r and RETURN to rerun
        ^Z
        End of data file - program terminating
Note que el programa crea 10 procesos, cada proceso incrementa 20 veces el recurso compartido nolineas por lo que el resultado de 200 es correcto.

EL PROBLEMA DE LA CENA DE FILOSOFOS
En 1965 Dijkastra planteo y resolvio un problema de sincronizacion al que llamo problema de la cena de los filosofos.  Desde entonces, quienquiera que haya inventado una primitiva de sincronizacion mas se a sentido obligado a demostrar lo maravillosa que es mostrando la forma tan elegante en que se resuelve el problema. El problema tiene un planteamiento muy sencillo cinco filosofos estan sentados alrededor de una mesa circular. Cada filosofo tiene ante si un plato de espagueti. El espagueti es tan resbaloso que un filosofo necesita dos tenedores para comerlo. Entre cada par de platos hay un tenedor. La vida de un filosofo consiste en periodos alternantes de comer y pensar.
Cuando un filosofo siente hambre trata de adquirir sus tenedores izquierdo y derecho. Uno a la vez en cualquier orden. Si logra adquirir dos tenedores comera durante un rato, luego pondra los tenedores sobre la mesa y seguira pensando. La pregunta clave es podemos escribir un programa para cada filosofo que haga lo que se supone que debe hacer y nunca se entrampe. El procedimiento Tomar tenedor, espera que el tenedor especificado este disponible y luego se apodera de el. Desafortunadamente  la solucion obvia esta equivocada. Supongamos que todos los filosofos toman su tenedor  izquierdo simultáneamente. Ninguno podra tomar su tenedor derecho y tendremos un bloqueo mutuo. Podriamos  modificar el programa de modo que, después de tomar el tenedor izquierdo el programa verifique si el tenedor derecho esta disponible. Si no es asi, el filosofo soltara su tenedor izquierdo y esperara cierto tiempo, y repetira el proceso. Esta propuesta tambien fracasa, aunque por una razon distinta. Con un poco de mala suerte todos los filosofos podrian iniciar el algoritmo simultáneamente, tomar su tenedor izquierdo, ver que su tenedor derecho no esta disponible dejar su tenedor izquierdo, esperar tomar su tenedor izquie otra vez de manera simultanea y asi eternamente. Una situación asi en la que todos los programas continuan ejecutandose de manera indefinida pero no logran avanzar se denomina Inanición.
Ahora podemos pensar si los filosofos espera un tiempo aleatorio en lugar del mismo tiempo después de fracasar en su intento por disponer del tenedor derecho, la posibilidad de que sus acciones continuaran coordinadas durante siquiera una hora es excesivamente pequena. Esto es cierto pero en algunas aplicaciones prefeririamos una solucion  que siempre funcione y que no tenga la posibilidad de fallar debido a una serie improbable de numeros aleatorios.
Una respuesta que no esta sujeta a bloqueo ni inanición consiste en proteger las cinco instrucciones que siguen a la llamada pensar con un semáforo binario. Desde un punto de vista teorico esta solucion es adecuada. En la practica empero tiene un problema de rendimiento.

            program Filo01;
            (* Filosofos comelones - semáforos versión 1 *)
            const
               N = 5;
            var
               palillo : array [1..N] of semaphore;  (* binario *)
Suscribirse a: Entradas (Atom)