Deadlocks & Livelocks: ¿Cómo evitar la concurrencia en el mundo real?

Los puntos muertos solo pueden ocurrir en programas concurrentes (multiproceso) donde los hilos sincronizan (usan bloqueos) el acceso a uno o más recursos compartidos (variables y objetos) o conjunto de instrucciones (sección crítica).

Los bloqueos en vivo se producen cuando intentamos evitar los puntos muertos mediante el bloqueo asincrónico, donde varios subprocesos compiten por los mismos bloqueos establecidos, evitamos adquirir los bloqueos para permitir que otros subprocesos vayan primero con el bloqueo y, finalmente, nunca lleguen a adquirir un bloquear y continuar; causando hambre. Consulte a continuación para comprender cómo un bloqueo de aysnc, que es una estrategia para evitar Deadlock, puede ser la razón de un Livelock

Estas son algunas de las soluciones teóricas para Deadlocks, y una de ellas (la segunda) es la razón principal de Livelocks.

Enfoques teóricos

No uses cerraduras

No es posible cuando se deben sincronizar dos operaciones, por ejemplo, una transferencia bancaria simple, donde debita una cuenta antes de poder acreditar la otra cuenta, y no permita que ningún otro hilo toque el saldo en las cuentas hasta que se complete el hilo actual.

No bloquee los bloqueos, si un hilo no puede adquirir un bloqueo, debe liberar los bloqueos adquiridos anteriormente para volver a intentarlo más tarde.

Es engorroso de implementar y puede causar inanición (Livelocks) donde un hilo siempre deja que los bloqueos se activen solo para intentarlo de nuevo y hacer lo mismo. Además, este enfoque puede tener gastos generales en el cambio frecuente de contexto de subproceso, lo que reduce el rendimiento general de un sistema. Además, no hay forma de que el planificador de la CPU implemente la imparcialidad, ya que no sabe qué subproceso ha estado esperando realmente los bloqueos durante más tiempo.

Deje que los hilos siempre soliciten bloqueos en un orden estricto

Más fácil decirlo que hacerlo, por ejemplo. Si estamos escribiendo una función para transferir dinero de la Cuenta A a la B, podemos escribir algo como

// en tiempo de compilación, bloqueamos el primer argumento y luego el segundo
transferencia pública nula (Cuenta A, Cuenta B, dinero largo) {
  sincronizado (A) {
    sincronizado (B) {
      A.add (cantidad);
      B. sustrato (cantidad);
    }
  }
}
// en tiempo de ejecución no podemos rastrear cómo se llamarán nuestros métodos
public void run () {
  Hilo nuevo (() -> this.transfer (X, Y, 10000)). start ();
  Hilo nuevo (() -> this.transfer (Y, X, 10000)). start ();
}
// este run () creará un punto muerto
// el primer hilo se bloquea en X, espera Y
// el segundo hilo se bloquea en Y, espera X

Solución del mundo real

Podemos combinar enfoques de orden de bloqueo y bloqueos programados para llegar a una solución de palabra real

Pedido de bloqueo de negocios determinado

Podemos mejorar nuestro enfoque discriminando entre A y B según el número de cuenta mayor o menor.

// en tiempo de ejecución, primero tenemos en cuenta el bloqueo con una identificación más pequeña
transferencia pública nula (Cuenta A, Cuenta B, dinero largo) {
  Cuenta final primero = A.id 
  sincronizado (primero) {
    sincronizado (segundo) {
      first.add (cantidad);
      segundo.sustrato (cantidad);
    }
  }
}
// en tiempo de ejecución no podemos rastrear cómo se llamarán nuestros métodos
public void run () {
  Hilo nuevo (() -> this.transfer (X, Y, 10000)). start ();
  Hilo nuevo (() -> this.transfer (Y, X, 10000)). start ();
}

Por ejemplo, si X.id = 1111 e Y.id = 2222, dado que tomamos en cuenta primero como el que tiene una identificación de cuenta más pequeña, el orden de bloqueo para las ejecuciones de transferencia (Y, X, 10000) y transferencia (X, Y, 10000) será lo mismo. X tiene un número de cuenta menor que Y, ambos hilos intentarán bloquear X antes de Y y solo uno de ellos tendrá éxito y procederá a bloquear Y finalizará y liberará bloqueos en X e Y antes de que los otros hilos adquieran bloqueos y puedan continuar.

Solicitudes de bloqueo de tiempo de espera determinadas por el negocio tryLock / async

La solución de usar un orden de bloqueo determinado por el negocio funciona solo si se trata de relaciones asociativas donde una lógica en una transferencia de lugar (...), como en nuestro método, determina cómo se coordinan los recursos.

Podemos terminar teniendo otros métodos / lógica, que termina usando una lógica de ordenamiento que es incompatible con la transferencia (...). Para evitar Deadlock en tales casos, es aconsejable usar el bloqueo asíncrono, donde intentamos bloquear un recurso por tiempo finito / realista (tiempo máximo de transacción) + Tiempo de espera pequeño aleatorio para que todos los hilos no intenten Adquirir demasiado pronto y no todos al mismo tiempo, respectivamente, evitando Livelocks (inanición debido a intentos inviables de adquirir bloqueos)

// supongamos que la cuenta # getLock () nos da el bloqueo de la cuenta (java.util.concurrent.locks.Lock)
// La cuenta podría encapsular el bloqueo, proporcionar bloqueo () / desbloquear ()
public long getWait () {
/// devuelve el promedio móvil de los tiempos de transferencia para las últimas n transferencias + sal pequeña aleatoria en milis, por lo que todos los subprocesos que esperan bloquearse no se activan al mismo tiempo.
}
transferencia pública nula (Lock lockF, Lock lockS, int cantidad) {
  Cuenta final primero = A.id 
  booleano hecho = falso;
  hacer {
    tratar {
      tratar {
        if (lockF.tryLock (getWait (), MILLISECONDS)) {
          tratar {
            if (lockS.tryLock (getWait (), MILLISECONDS)) {
              hecho = verdadero;
            }
          } finalmente {
            lockS.unlock ();
          }
        }
      } catch (InterruptedException e) {
        lanzar nueva RuntimeException ("Cancelado");
      }
    } finalmente {
      lockF.unlock ();
    }
  } while (! hecho);

}
// en tiempo de ejecución no podemos rastrear cómo se llamarán nuestros métodos
public void run () {
    Hilo nuevo (() -> this.transfer (X, Y, 10000)). start ();
    Hilo nuevo (() -> this.transfer (Y, X, 10000)). start ();
}