Mutex recursivo

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

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. 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

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".

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.

Exemplo

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

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

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

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.