Exemplos para Monitor e Rendezvous

Monitor

Exemplos de uso de Monitores em LI2:

• Exemplo 1: Esse exemplo cria dois processos paralelos que realizam tarefas distintas. Para compreender o uso do mecanismo, deve-se atentar a execução do procedimento incA e a chamada do notify() dentro do bloco sincronizado, que é onde ocorre a sincronização da execução dos dois processos paralelos.
  
  Caso o procedimento incA execute primeiro, a variável compartilhada "a" será sincronizada (bloqueada para aquele processo). O procedimento vai incrementar "a", vai escrever "parou" e vai "dormir", cedendo então a vez a quem quiser utilizar "a". Desta forma, o segundo processo poderá somar 2 à variável "a" e então "acordar" o primeiro processo para que ele continue e escreva "continuou" e depois incremente "a".
  
  Caso o segundo processo execute primeiro, a variável "a" será somada a 2 e só depois que o primeiro processo poderá incrementar "a". Neste caso temos um problema, pois o procedimento incA vai ficar parado para sempre quando chamar o wait(), pois não terá ninguém para chamar acordá-lo usando o notify().
  

{
    var a = 0, 
    proc incA ()  {
        synch( a ) {
            a := a + 1;
            write("parou");
            wait( a );
            write("continuou");
            a := a + 1
        }
    };

    call incA()
    par
    synch( a ) {
        a := a + 2;
        notify( a )
    }
}

• Exemplo 2: Este exemplo mostra uma aplicação de Monitor em que não é possível determinar o resultado de antemão, isso porque se a primeira linha de execução conseguir a trava antes da segunda linha, o resultado final será 2. Se, ao invés disso, a segunda linha de execução conseguir a trava sobre A antes da primeira, o resultado será 1. Esse é um bom exemplo onde a aplicação de Rendezvous é mais indicada por apresentar um comportamento determinístico.

{ 
    var a  =  0, 
    proc incA () {
        synch( a ) {
            a := a + 1
        };
        write( a );
        write(" ")
    },
    proc incB () {
        synch( a ) {
            a := a + a
        };
        write( a );
        write(" ")
    };

    call incA()
    par
    call incB()
}

Rendezvous

Exemplos do uso de Rendezvous:

• Exemplo 1: Cria dois processos paralelos que escrevem suas variaveis locais no console. As duas estão em paralelo, mas a execução é determinística devido ao em paralelo e compartilham um recurso global: a variável 'x'.

{
    entry sync() {
        skip
    };

    {
        var y = 5;
        {
            accept sync;
            write(y);
        }
    }
    par
    {
        var x = 0;
        {
            write(x);
            callEntry sync();
        }
    }    
}

// Declaracao das variaveis globais
// (nao faz nada)
// ...
// .
// Bloco da primeira task
// Declaracao de suas variaveis locais
// ...
// Ponto de sincronizacao
// ...
// ...
// .
// Task1 paralela a Task2
// ...
// .
// .
// Escreve o x
// Se reune com a Task1
// .
// Fim da Task2
// Fim do Programa

• Exemplo 2: Este exemplo mostra uma típica aplicação de Rendezvous: o produtor-consumidor.
  Observe que são criadas duas tasks que utilizam uma variavel global (dobro). A segunda task entra com o valor inicial na variável dobro e invoca a primeira para fazer o processamento, em seguida ela consome o resultado, imprimindo no console o valor posterior de dobro.
  Esse é um exemplo em que a seqüência do acesso a esse recurso compartilhado tem que ser perfeitamente sincronizado. Experimente não usar os operadores de Rendezvous nesse exemplo e vejam como o resultado é inesperado.

{
    var dobro = 0,
    
    entry produza()
    {
        dobro := dobro + dobro
    };

    {
        var i = 0;
        {
            while ( not i == 11 ) do
            {
                accept produza;
                i := i + 1;
            };
        }
    }
    par
    {
        var i = 0;
        {
            while ( not i == 11 ) do
            {
                dobro := i;
                write("Dobro de "); write(i); write(": ");
                callEntry produza();
                write(dobro); write(" || ");
                i := i + 1;
            };
        }
    }
}

• Exemplo 3: Rendezvous é um mecanismo muito flexível e utilizado para diversas soluções em programação concorrente. Abaixo está um exemplo em que o Rendezvous é utilizado como escalonador de tarefas. Ele define a seqüência em que as tarefas vão executar, quando na ausência de um escalonador no sistema operacional que possa ser modificado.
  
  Neste exemplo são definidos três processos concorrentes que imprimem algo no console. Essa impressão é sempre ordenada e determinística devido aos operadores de Rendezvous.
  
  ATENÇÃO: estas tasks estão em loop infinito, portanto o programa não vai parar.

{
    var i = 1,

    entry sync1() {
        skip
    },

    entry sync2() {
        skip
    },

    entry sync3() {
        skip
    };

    {
        var y = 5;
        {
            while ( not i == 0 ) do
            {
                accept sync1;
                write("task2");
                callEntry sync3();
            };
        }
    }
    par
    {
        var x = 0;
        {
            while ( not i == 0 ) do
            {
                accept sync2;
                write("task1|");
                callEntry sync1();
            };
        }
    }
    par
    {
        while ( not i == 0 ) do
        {
            write("i: ");
            write(i);
            write("-");
            callEntry sync2();
            i := i + 1;
            accept sync3;
            write(" || ");
        };
    }
}

Observe o mesmo exemplo acima SEM o uso de Rendezvous e perceba que a seqüência das tarefas que são executadas é completamente aleatória.

{
    var i = 1;

    {
        var y = 5;
        {
            while ( not i == 0 ) do
            {
                write("task2");
            };
        }
    }
    par
    {
        var x = 0;
        {
            while ( not i == 0 ) do
            {
                write("task1|");
            };
        }
    }
    par
    {
        while ( not i == 0 ) do
        {
            write("i: ");
            write(i);
            write("-");
            i := i + 1;
            write(" || ");
        };
    }
}

Escopo Negativo

Os exemplos listados abaixo não deveriam funcionar. Para cada um, existe uma justificativa e explicação.

• Exemplo 1: Esse código a seguir mostra um exemplo de deadlock não-determinístico. Caso a execução das tasks seja 'C', 'B' e 'A', o programa trava.

{
    var a = 0, 
    proc prcA () {
        synch(a) {
            a := a + 2;
            write(" vai parar ");
            wait( a );
            write(" continuou 1 ")
        }
    },
    proc prcB () {
        synch(a) {
            a := a + 1;
            write(" vai parar ");
            write( a );
            write(" continuou 2 ")
        }
    },
    proc prcC () {
        synch( a ) {
            a:=a+1;
            write(" vai acordar ");
            notify(a)
        }
   };

    call prcA()
    par
    call prcB()
    par
    call prcC()
}
  

• Exemplo 2: No código abaixo, não há chamada ao entry point 'inc'. O comando write(z) não deve ser executado porque espera por uma sincronização de uma outra tarefa que nunca ocorre, já que não existe uma chamada ao inc (callEntry inc(z) ou algo do tipo), somente sua declaração.

{
    var x = 0,
    var z = 5,
    entry inc(int y) {
       write(y)
    };

    {
        write(x);
        accept inc;
        write(z);
    }
}