Em ciência da computação, um mutex reentrante (mutex recursivo, em inglês recursive mutex ou reentrant mutex) é um tipo específico de dispositivo de exclusão mútua (mutex) que pode ser bloqueado várias vezes pelo mesmo processo/thread, sem causar um deadlock.

Embora qualquer tentativa de realizar uma operação de  "travar" um mutex comum fosse falhar ou bloquear se o mutex já estivesse travado, em um mutex recursivo esta operação terá sucesso se e somente se a thread bloqueando for aquela que já detém o bloqueio. Normalmente, um mutex recursivo controla o número de vezes que foi bloqueado, e requer que a mesma quantidade de operações de desbloqueio sejam executadas antes que outras threads possam bloqueá-lo.

Motivação

editar

Mutexes recursivos resolvem o problema da não-reentrância que existe com mutexes comuns: se uma função que segura a trava executa uma função que em seguida chama a função original, ocorre um deadlock.[1] Em pseudocódigo, esta é a seguinte situação:

var m : Mutex // Um mutex não recursivo, inicialmente desbloqueado.
função lock_and_call(i : Integer)
  m.lock() // bloquear
  callback(i)
  m.unlock() // desbloquear
função de callback(i : Integer)
 if i > 0
   lock_and_call(i - 1)

Dadas essas definições, a chamada de função lock_and_call(1) causará a seguinte sequência de eventos:

  • m.lock() — mutex bloqueado
  • callback(1)
  • lock_and_call(0) — pois i > 0
  • m.lock() — deadlock, pois m já está bloqueado, então a thread em execução irá bloquear, esperando por si mesma.

Substituir o mutex com um mutex recursivo resolve o problema, porque a m.lock() final será bem-sucedida sem bloqueio.

Uso prático

editar

W. Richard Stevens nota que bloqueios recursivos são "complicados" de usar corretamente, e recomenda o seu uso para adaptar código de thread única sem alterar APIs, mas "apenas quando não há outra solução possível".[2]

O mecanismo de sincronização nativo da linguagem Java, monitor, usa bloqueios recursivos. Sintaticamente, uma lock (trava) é um bloco de código que vem depois da palavra-chave 'synchronized', e qualquer referência de objeto entre parênteses que será usado como o mutex. Dentro do bloco sincronizado, o objeto pode ser usado como uma variável de condição, fazendo um wait(), notify() ou notifyAll(). Assim, todos os Objetos são tanto mutexes recursivos quanto variáveis de condição.[3]

Exemplo

editar
  1. Thread A chama a função F que adquire uma trava reentrante para si antes de prosseguir
  2. Thread B chama a função F que tenta adquirir uma trava reentrante para si, mas não pode pois já existe uma, resultando em um bloqueio (espera), ou um tempo limite, se solicitado
  3. A função F da Thread A chama a si mesma recursivamente. Ele já possui a trava, por isso não irá se bloquear (no há deadlock). Esta é a ideia central de um mutex reentrante, e é o que o torna diferente de uma trava normal.
  4. A função F da Thread B ainda está à espera, ou atingiu o timeout e seguiu um trajeto diferente
  5. A função F da Thread A libera sua(s) trava(s)
  6. A função F da Thread B pode agora adquirir um mutex reentrante e continuar se ela ainda estava esperando

Emulação em software

editar

Emulação em software pode ser feita usando a seguinte estrutura:

  • Uma condição de "controle" usando um mutex normal
  • Identificador de proprietário, exclusivo para cada thread (predefinido como vazio / não definido)
  • Contagem de aquisição (predefinido para zero)

Aquisição

editar
  1. Adquirir a condição de controle.
  2. Se o proprietário está definido, mas não na thread atual, aguardar que a condição de controle seja notificada (isso também libera a condição).
  3. Definir a thread atual como proprietária. O identificador de proprietário já deveria ter sido resetado neste ponto, a menos que o adquirente já seja o proprietário.
  4. Incrementar a contagem de aquisição  (sempre deve resultar em 1 para novos proprietários).
  5. Soltar a condição de controle.

Liberação

editar
  1. Adquirir a condição de controle, checando que o proprietário é quem está liberando.
  2. Diminuir a contagem de aquisição, checando que a contagem é maior ou igual a zero.
  3. Se a contagem for zero, limpar as informações do proprietário e notificar a condição de controle.
  4. Soltar a condição de controle.

Referências

editar
  1. Buschmann, Frank; Henney, Kevin; Schmidt, Douglas C. (2007). Pattern-Oriented Software Architecture, A Pattern Language for Distributed Computing. [S.l.]: John Wiley & Sons. p. 374 
  2. Stevens, W. Richard; Rago, Stephen A. (2013). Advanced Programming in the UNIX Environment. [S.l.]: Addison-Wesley. p. 434 
  3. David Hovemeyer. «Lecture 17: Java Threads, Synchronization». CS 365 - Parallel and Distributed Computing. Lecture notes, York College of Pennsylvania. [S.l.: s.n.] Consultado em 4 de junho de 2015