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