MC514 1ºs 2004 - Algoritmos clássicos de exclusão mútua

Atualizado em 19/04/04 - Prof. Célio Guimarães

Hipótese básica sobre o hardware: apenas as seguintes operações são indivisíveis:
Leitura de uma posição de memória
Escrita sobre uma posição de memória

Postulados de Dijkstra
São condições necessárias para uma solução do problema de exclusão mútua.

1. Exclusão mútua: apenas um processo de cada vez pode executar o código de Região Crítica (RC) associada a um recurso compartilhado do sistema (também se diz entrar na RC). Quando nenhum processo está numa dada RC qualquer processo que queira entrar na RC pode fazê-lo imediatamente.
2. Nenhuma hipótese pode ser feita a respeito da velocidade relativa dos processos
3. Um processo fica dentro de uma RC por um tempo finito. Fora da RC nehum processo interfere com outros processos que queiram entrar na RC.
4. Dois ou mais processos não devem se bloquear indefinidamente na entrada de uma RC (deadlock).
5. Um processo não pode ser indefinidamente impedido (por outros processos) de entrar numa RC (inanição ou starvation)

A. Dois processos P₁ e P₂ com busy wait

A.1 Algoritmo de Peterson (1981)

O código executado por um processo desde o instante em que deseja entrar na RC até o momento em que entra na RC é chamado de protocolo de entrada da RC e o código executado ao liberar a RC é chamado de protocolo de saída da RC. Normalmente eles seriam encapsulados em duas funções, digamos, enter_cs() e leave_cs(). No algoritmo acima o protocolo de entrada de P₁ começa com a atribuição q1 := 1 e termina na saída do laço loop while(). O protocolo de saída é simplesmente a atribuição q1 := 0.

A.2 Algoritmo da "padaria" restrito a 2 processos (Lamport 1974)

B. N processos P₁ . . . P_N, com busy wait:

B.1 Algoritmo da "padaria" (Lamport, 1974)

Notação:
q_i, i= 1,2, ... N: tem o mesmo objetivo que acima, vale 0 fora da RC e colocada em 1 por P_i quando P_i "quer" entrar na RC permanecendo em 1 até P_i sair da RC.
c_i, i= 1,2, ... N : vale 0 fora da RC e após P_i ter obtido o seu "bilhete"; colocada em 1 por P_i quando este está calculando o valor do seu bilhete
Observe que tanto q_i quanto c_i só sâo escritas pelo processo P_i, mas são lidas por todos os outros.

Código de Pi

loop forever

ci:= 1

qi:= 1 + max (q1, q2, ..., qN)

ci:= 0

for j =1, step 1 until N do

loop while (cj != 0)

loop while (qj != 0 and (qj, j) < (qi, i) ) (*)

endfor

RC

qi := 0

RNC

endloop

(*)   (q_j, j) < (q_i, i) se q_j < q_i ou q_j = q_i e j < i (comparação lexicográfica)

Exercícios

   Processo P1           Processo P1
loop forever             loop forever   
  q1 := 1                  q2 := 1
   loop while (q2 = 1)     loop while (q1 = 1)
      RC                      RC
   q1 := 0	        q2 := 0
endloop                  endloop

3. Analise agora a seguinte solução com apenas uma variável compartilhada q, onde q vale 0 fora da RC e recebe o valor i quando P_i quer entrar na RC:

     P1                        P2
loop forever               loop forever
loop                       loop
    loop while ( q > 0 )       loop while ( q > 0 )
    q := 1                     q := 2
while ( q != 1)             while (q != 2)
     RC                         RC
    q := 0                     q := 0
     RNC                        RNC
endloop                    endloop

     P1                        P2
loop forever               loop forever
loop                       loop
    loop while ( q > 0)       loop while ( q > 0 )
    vez := 1                  vez := 2
    q := 1                    q := 2
while ( vez # 1)            while (vez # 2)
     RC                         RC
    q := 0                     q := 0
     RNC                        RNC
endloop                    endloop

O problema do Produtor - Consumidor usando buffer circular

Produtor	Consumidor
loop forever	loop forever
Produz mensagem mp
loop while (p + 1 mod N = c) //buffer cheio	loop while (p = c ) // buffer vazio
buf[p] := mp	mc := buf[c]
p := p + 1 mod N	c := c + 1 mod N
	Consome mensagem mc
. . .	. . .
endloop	endloop

C. Soluções sem busy wait

Implementação de RC com instruções do tipo TSL

enter_cs(lock)
begin
   L1: TSL Reg, lock
       CMP Reg, 0
       JZ LIVRE
       yield()   // RC estava ocupada, libere o processador e tente mais tarde
       JMP L1
   LIVRE: return()
end

leave_cs(lock)
begin
      lock := 0
end

Solução do problema de N produtores e M consumidores usando buffer circular e função yield

           Produtor                             Consumidor
loop forever                                loop forever
   Produz mensagem mp                          
   loop                                         loop
       enter_cs(lock)                               enter_cs(lock)
       if ( p + 1 mod N = c)                        if (p = c) 
       begin                                        begin
            leave_cs(lock)                               leave_cs(lock)
            yield()                                      yield()
       end                                           end
       else break // sai do loop interno             else break
   end loop                                      end loop
   buf[p] := mp   // RC continua ocupada         mc := buf[c]
   p := p + 1 mod N                              c := c+1 mod N
   leave_cs(lock)                                leave_cs(lock)
   . . .                                         Consome mensagem mc
end loop                                      end loop

1. Re-escreva a função enter_cs(lock) utilizando a instrução xchg do 80X86.

2. Analise a seguinte solução do problema de N produtores e M consumidores comparando-a com a apresentada acima:

    Produtor                                  Consumidor
loop forever                                loop forever
   Produz mensagem mp                          
   enter_cs(lock1)                               enter_cs(lock2)
   while ( p + 1 mod N = c) yield()              while (p = c) yield() 
   buf[p] := mp   // RC continua ocupada         mc := buf[c]
   p := p + 1 mod N                              c := c+1 mod N
   leave_cs(lock1)                                leave_cs(lock2)
   . . .                                         Consome mensagem mc
end loop                                     end loop

C.1 Solução via semáforos ( Dijkstra, 1965 )

Semântica da operação P(s)
se s > 0 decrementa s senão bloqueia processo colocando-o na fila s.queue

Semântica da operação V(s)
se fila s.queue não vazia desbloqueia o 1º processo da fila, senão incrementa s

Um semáforo binário s com valor inicial 1 pode ser usado para delimitar uma RC da seguinte forma (exercício: explique porque!):

   P(s)
   RC
   V(s)

Semáforos podem ser usados também como contadores que podem ser atômicamente incrementados e decrementados, além de permitirem bloquear e desbloquear o processo que invoca P() ou V().

Implementação de operações sobre semáforos - um problema do ovo e da galinha

enter_cs(int * lock)
{
	asm("
l1:
	movl 8(%ebp),%ecx   # store lock address in ecx
	xor %eax, %eax
	inc %eax            # 1 to eax
	xchg %eax, (%ecx)   # exchange eax with lock value
	or %eax, %eax       # set flags
	jnz l1              # eax received 1, try again
	");      		
}                       // return with lock set to 1

Solução do problema de N Produtores e M Consumidores via semáforos

Deadlocks

Apesar da aparente simplicidade, quando mais de um semáforo é usado o sistema pode facilmente entrar em deadlock. Por exemplo, na solução acima se a ordem das operações no Produtor, P(full) e P(s) forem invertidas e o buffer estiver cheio (full = 0), o produtor ficará bloqueado dentro da RC delimitada pelo par P(s) V(s). Para desbloquear o produtor é preciso que um consumidor tenha acesso à RC, mas qualquer consumidor ficará bloqueado ao executar P(s). Outra possibilidade de deadlock muito comum é quando a aplicação requer mais de uma RC e elas sejam executadas em ordem inversa por dois processos. É fácil de ver que o código a seguir pode facilmente levar a um deadlock de dois processos, numa situação de corrida, utilizando dois mutexes s e t (valor inicial = 1):

     Processo 1   Processo2
     P(s)         P(t)
     ...          ...
     P(t)         P(s)
     ...          ...
     V(s)         V(t) 	
     ...          ...
     V(t)         V(s)

Exercícios

2. A implementação anterior ficaria mais eficiente caso semáforos possam tomar valores negativos na operação P(s): nesse caso | s.val | representa o número de processos bloqueados na fila s.queue. Re-escreva a solução anterior utilizando este recurso. Como mudaria a descrição da semântica das operações P e V nesse caso? Observe que processos devem ficar bloqueados ou desbloqueados exatamente nas mesmas condições de antes, ou seja, nenhuma mudança seria requerida em qualquer aplicação utilizando P e V!

3. Analise a solução do problema dos Leitores e Escritores (slide 43) e mostre que ela dá prioridade aos leitores no acesso ao recurso compartilhado (base de dados).

4. Modifique a solução do problema do "barbeiro dorminhoco", (slide 45) onde o semáforo barbers tem um valor inicial k > 0, representando o número de barbeiros que estão ociosos na barbearia e que são requisitados e liberados pelos clientes; desta forma Você terá uma solução mais natural do problema.

5. Duas classes de processos denominadas respectivamente, "homens" e "mulheres", compartilham um recurso comum denominado "banheiro", da seguine forma:

1. uma ou mais mulheres podem usar simultaneamente o banheiro;
2. um ou mais homens podem usar simultaneamente o banheiro;
3. qualquer combinação de homens e mulheres não pode usar simultaneamente o banheiro.

Sugestões:

• utilize um semáforo binário h para garantir exclusão mútua dos homens ao executar os protocolos de entrada e de saida da RC (uso do banheiro);
• utilize um semáforo binário m para garantir exclusão mútua das mulheres ao executar os protocolos de entrada e de saida da RC (uso do banheiro);
• utilize um semáforo binário b para que homens possam excluir o acesso de mulheres quando eles estão utilizando o banheiro e também para que mulheres possam excluir o acesso de homens quando elas estão usando o banheiro;
• utilize dois contadores para registrar, respectivamente, o número de homens e de mulheres presentes no banheiro.
• uma política simétrica de acesso ao banheiro que dê prioridade a mulheres enquanto há mulheres utilizando o banheiro e vice versa, dando prioridade a homens enquanto há homens utilizando o banheiro, conduz a uma solução bastante simples.

6. Escreva o código de um Monitor para resolver o problema acima, contendo os procedimentos: Homem_quer_usar_banheiro(), Homem_deixa_banheiro(), Mulher_quer_usar_banheiro() e Mulher_deixa_banheiro() . Estabeleça claramente o objetivo e as condições iniciais das variáveis utilizadas.