# 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:
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

* Thread A chama a função F que adquire uma trava reentrante para si antes de prosseguir
* 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
* 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.
* A função F da Thread B ainda está à espera, ou atingiu o timeout e seguiu um trajeto diferente
* A função F da Thread A libera sua(s) trava(s)
* 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

* Adquirir a condição de controle.
* 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).
* 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.
* Incrementar a contagem de aquisição (sempre deve resultar em 1 para novos proprietários).
* Soltar a condição de controle.

### Liberação

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