Chapter 5 - Concurrency: Mutual Exclusion and Synchronization

Sincronização: Dekker, Peterson e Semáforo

 

1. Por que o estudo demecanismos de Mútua Exclusão é importante no contexto de processo ?

2. Considere a solução do problema de Exclusão Mútua como ilustrado abaixo. Embora esta solução garanta a exclusão mútua, ela apresenta 02 desvantagens. Descreva estas desvantagens.

  boolean turn; /* {0,1} */

  Process 0                              Process 1
    ...                                    ...
    ...                                    ...
    while( turn!=0 ) do { nothing; }       while( turn!=1 ) do { nothing; }
    ... critical region ...                ... critical region ...
    turn = 1;                              turn = 0;
    ...                                    ...
    ...                                    ...

3. Para o problema da exclusão mútua, considere agora que cada processo tenha uma variável que indique a sua intenção em entrar na região crítica. Descreva uma seqüência que mostre que esta solução é pior que a anterior, visto que não garante a exclusão mútua. Para isto, baseie-se no código dos processos 0 e 1.

  boolean turn; /* {0,1} */

  Process 0                              Process 1
    ...                                    ...
    ...                                    ...
    while( turn!=0 ) do { nothing; }       while( turn!=1 ) do { nothing; }
    ... critical region ...                ... critical region ...
    turn = 1;                              turn = 0;
    ...                                    ...
    ...                                    ...

4. Uma outra tentativa, seguindo as idéias anteriormente apresentadas, é permitir a cada processo divulgar a intenção de entrar na região crítica, mas apenas depois de ter consultado o estado do outro processo. Esta formalização pode ser descrita pelo seguinte programa:

/* Variables - Dekker's Algorithm */
  Process 0                              Process 1
  ...                                    ...
  ...                                    ...
  flag[0] := true;                       flag[1] := true;
  while flag[1] do                       while flag[0] do
  begin                                  begin
    flag[0] := false;                      flag[1] := false;
    ... delay for a short time ...         ... delay for a short time ...
    flag[0] := true;                       flag[1] := true;
  end;                                   end;
  ... critical region ...                ... critical region ...
  flag[0] := false;                      flag[1] := false;
  ...                                    ...
  ...                                    ...

Embora esteja próxima da solução correta, há ainda problemas. Embora a exclusão mútua seja garantida, há a possibilidade de nenhum processo entrar na região crítica por um período de tempo arbitrariamente grande. Mostre este cenário através de uma seqüência de eventos.

5. Tanto o Algoritmo de Dekker quanto o de Peterson são soluções que garantem a exclusão mútua, bem como constituem soluções onde não teremos "deadlock" ou "starvation". Não obstante os 02 algoritmos consideram apenas 02 processos. Escolha um dos algoritmos e proponha modificações para contemplar "n" processos, onde "n>2".

  /* Variables - Dekker's Algorithm */
  var  flag:  array [0 .. 1] of boolean;
       turn: 0 .. 1;

  Procedure P0;                             Procedure P1;
  begin                                     begin
    repeat                                    repeat
      flag[0] := true;                          flag[1] := true;
      while flag[1] do if turn = 1 then         while flag[0] do if turn = 0 then
      begin                                     begin
        flag[0] := false;                         flag[1] := false;
        while turn = 1 do { nothing };            while turn = 0 do { nothing }
        flag[0] := true;                          flag[1] := true;
      end;                                      end;
      ... critical region ...                   ... critical region ...
      turn := 1;                                turn := 0;
      flag[0] := false;                         flag[1] := false;
      ... remainder ...                         ... remainder ...
    forever;                                  forever;
  end;                                      end;

  begin   /* Main Program - Dekker's Algorithm */
    flag[0] := false;
    flag[1] := false;
    turn := 1;

    parbegin
      P0;  /* Procedure P0 */
      P1;  /* Procedure P1 */
    parend;
  end;
  /* Variables - Peterson's Algorithm */
  var  flag:  array [0 .. 1] of boolean;
       turn: 0 .. 1;

  Procedure P0;                              Procedure P1;
  begin                                      begin
    repeat                                     repeat
      flag[0] := true;                           flag[1] := true;
      turn := 1;                                 turn := 0;
      while flag[1] and turn = 1 do              while flag[0] and turn = 0 do
        { nothing };                               { nothing };
      ... critical region ...                    ... critical region ...
      flag[0] := false;                          flag[1] := false;
      ... remainder ...                          ... remainder ...
    forever;                                   forever;
  end;                                       end;

  begin   /* Main Program - Peterson's Algorithm */
    flag[0] := false;
    flag[1] := false;
    turn := 1;

    parbegin
      P0;  /* Procedure P0 */
      P1;  /* Procedure P1 */
    parend;
  end;

6. Para o Problema do Produtor/Consumidor utilizando Semáforos Binários, uma solução possível é a que considera 02 semáforos: "delay" e "s".

  /* Producer & Consumer using Semaphores */
  var n: integer;
      s: binary_semaphore (:= 1);
      delay: binary_semaphore (:= 0);

  Procedure Producer;                        Procedure Consumer;
  begin                                      begin
    repeat                                     waitB( delay );
      produce;                                 repeat
      waitB( s );                                waitB( s );
      append;                                    take;
      n := n + 1;                                n := n - 1;
      if n=1 then signalB( delay );              signalB( s );
      signalB( s )                               consume;
    forever;                                     if n=0 then waitB( delay );
  end;                                         forever;
                                           end;
  begin   /* Main Program - Producer & Consumer using Semaphores */
    n := 0;

    parbegin
      Producer;
      Consumer;
    parend;
  end;

Não obstante, há um erro neste programa que pode ser descrito pelos eventos apresentados abaixo. Explique porque isto acontece e em seguinda proponha uma solução para o problema. Isto, provavelmente, implicará na reescrita da solução proposta.

        Action                                   "n"    Delay

    1   Initially                                 0       0
    2   Producer: critical region                 1       1
    3   Consumer: waitB(delay)                    1       0
    4   Consumer: critical region                 0       0
    5   Producer: critical region                 1       1
    6   Consumer: if n=0 then waitB(delay)        1       1
    7   Consumer: critical region                 0       1
    8   Consumer: if n=0 then waitB(delay)        0       0
    9   Consumer: critical region                -1       0

 


Luís Fernando Faina
Last modified: Fri Jun 4 10:12:13 2004