Questão 762139

Um modo simples de detectar uma situação de deadlock é através da construção de um grafo de espera. Cada transação que está normalmente sendo executada é representada por um nó. Temos um estado de deadlock, se e somente se, o grafo de espera possuir nós com arcos inibidores.

Dois esquemas que impedem o deadlock são chamados esperar-morrer (wait-die) e feri-esperar (wound-wait). Em esperar-morrer uma transação mais nova tem permissão para esperar por uma transação mais antiga, enquanto em ferir-esperar acontece o contrário, uma transação mais antiga tem permissão para esperar por uma transação mais nova.

Se um sistema estiver em uma situação de deadlock, algumas transações que causam deadlock precisam ser abortadas. Seleção de vítima é o processo de escolha de quais transições serão abortadas. O algoritmo para execução desse processo geralmente deve evitar a seleção de transações que estiverem em execução por muito tempo e que realizaram muitas atualizações.

Os algoritmos Sem Espera (NW – no waiting) e Espera Cuidadosa (CW – cautious waiting) são utilizados como protocolo para impedir o deadlock. O algoritmo Sem Espera foi proposto para tentar reduzir o número de abortos/reinícios desnecessários e no Espera Cuidadosa, se uma transação for incapaz de obter um bloqueio, ela é imediatamente abortada e, depois, reiniciada após certo atraso de tempo.