lock - synchronization java
Escribe un programa que seguramente entrará en un punto muerto (13)
Hace poco recibí estas preguntas en una entrevista.
Respondí que el punto muerto ocurre si el entrelazado sale mal, pero el entrevistador insistió en que se puede escribir un programa que siempre entrará en un punto muerto, independientemente del entrelazado.
¿Podemos escribir un programa así? ¿Puedes indicarme algún ejemplo de programa como ese?
ACTUALIZACIÓN: esta pregunta fue el tema de mi blog en enero de 2013 . Gracias por la gran pregunta!
¿Cómo podemos escribir un programa que siempre entrará en un punto muerto sin importar cómo estén programados los hilos?
Aquí hay un ejemplo en C #. Tenga en cuenta que el programa parece no contener bloqueos ni datos compartidos. Tiene solo una sola variable local y tres declaraciones, y sin embargo, bloquea con 100% de certeza. Uno tendría dificultades para encontrar un programa más simple que bloquee con certeza.
Ejercicio para el lector n. ° 1: explica cómo se bloquea esto. (Una respuesta está en los comentarios).
Ejercicio para el lector n. ° 2: demuestre el mismo punto muerto en Java. (Una respuesta está aquí: https://.com/a/9286697/88656 )
class MyClass
{
static MyClass()
{
// Let''s run the initialization on another thread!
var thread = new System.Threading.Thread(Initialize);
thread.Start();
thread.Join();
}
static void Initialize()
{ /* TODO: Add initialization code */ }
static void Main()
{ }
}
Aquí hay un ejemplo de Java siguiendo el de Eric Lippert:
public class Lock implements Runnable {
static {
System.out.println("Getting ready to greet the world");
try {
Thread t = new Thread(new Lock());
t.start();
t.join();
} catch (InterruptedException ex) {
System.out.println("won''t see me");
}
}
public static void main(String[] args) {
System.out.println("Hello World!");
}
public void run() {
try {
Thread t = new Thread(new Lock());
t.start();
t.join();
} catch (InterruptedException ex) {
System.out.println("won''t see me");
}
}
}
Aquí hay un ejemplo:
dos subprocesos se están ejecutando, cada uno esperando que otro cierre la cerradura
la clase pública ThreadClass extends Thread {
String obj1,obj2;
ThreadClass(String obj1,String obj2){
this.obj1=obj1;
this.obj2=obj2;
start();
}
public void run(){
synchronized (obj1) {
System.out.println("lock on "+obj1+" acquired");
try {
Thread.sleep(3000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("waiting for "+obj2);
synchronized (obj2) {
System.out.println("lock on"+ obj2+" acquired");
try {
Thread.sleep(3000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
Ejecutar esto llevaría a un punto muerto:
clase pública SureDeadlock {
public static void main(String[] args) {
String obj1= new String("obj1");
String obj2= new String("obj2");
new ThreadClass(obj1,obj2);
new ThreadClass(obj2,obj1);
}
}
Aquí hay una muestra en la que un bloqueo de mantenimiento de hilo inicia otro hilo que desea el mismo bloqueo y luego el motor de arranque espera hasta que finalice ... para siempre:
class OuterTask implements Runnable {
private final Object lock;
public OuterTask(Object lock) {
this.lock = lock;
}
public void run() {
System.out.println("Outer launched");
System.out.println("Obtaining lock");
synchronized (lock) {
Thread inner = new Thread(new InnerTask(lock), "inner");
inner.start();
try {
inner.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
class InnerTask implements Runnable {
private final Object lock;
public InnerTask(Object lock) {
this.lock = lock;
}
public void run() {
System.out.println("Inner launched");
System.out.println("Obtaining lock");
synchronized (lock) {
System.out.println("Obtained");
}
}
}
class Sample {
public static void main(String[] args) throws InterruptedException {
final Object outerLock = new Object();
OuterTask outerTask = new OuterTask(outerLock);
Thread outer = new Thread(outerTask, "outer");
outer.start();
outer.join();
}
}
El seguro aquí asegura que ambos bloqueos se mantienen cuando cada hilo intenta bloquear al otro:
import java.util.concurrent.CountDownLatch;
public class Locker extends Thread {
private final CountDownLatch latch;
private final Object obj1;
private final Object obj2;
Locker(Object obj1, Object obj2, CountDownLatch latch) {
this.obj1 = obj1;
this.obj2 = obj2;
this.latch = latch;
}
@Override
public void run() {
synchronized (obj1) {
latch.countDown();
try {
latch.await();
} catch (InterruptedException e) {
throw new RuntimeException();
}
synchronized (obj2) {
System.out.println("Thread finished");
}
}
}
public static void main(String[] args) {
final Object obj1 = new Object();
final Object obj2 = new Object();
final CountDownLatch latch = new CountDownLatch(2);
new Locker(obj1, obj2, latch).start();
new Locker(obj2, obj1, latch).start();
}
}
Interesante para ejecutar jconsole, que le mostrará correctamente el punto muerto en la pestaña Subprocesos.
Esta versión de C #, supongo que Java debería ser bastante similar.
static void Main(string[] args)
{
var mainThread = Thread.CurrentThread;
mainThread.Join();
Console.WriteLine("Press Any key");
Console.ReadKey();
}
Hay un ejemplo en Java aquí
http://baddotrobot.com/blog/2009/12/24/deadlock/
Donde un secuestrador se mete en un punto muerto cuando se niega a abandonar a la víctima hasta que obtiene el dinero en efectivo, pero el negociador se niega a ceder el dinero hasta que consigue la víctima.
He reescrito la versión en Java de Yuriy Zubarev del ejemplo del punto muerto publicado por Eric Lippert: https://.com/a/9286697/2098232 para parecerse más a la versión C #. Si el bloque de inicialización de Java funciona de manera similar al constructor estático de C # y adquiere primero el bloqueo, no necesitamos otro hilo para invocar también el método de unión para obtener un punto muerto, solo necesita invocar un método estático de la clase de bloqueo, como el C # original ejemplo. El punto muerto resultante parece confirmar esto.
public class Lock {
static {
System.out.println("Getting ready to greet the world");
try {
Thread t = new Thread(new Runnable(){
@Override
public void run() {
Lock.initialize();
}
});
t.start();
t.join();
} catch (InterruptedException ex) {
System.out.println("won''t see me");
}
}
public static void main(String[] args) {
System.out.println("Hello World!");
}
public static void initialize(){
System.out.println("Initializing");
}
}
No es la tarea de entrevista más simple que puede obtener: en mi proyecto, paralizó el trabajo de un equipo durante todo un día. Es muy fácil hacer que el programa se detenga, pero es muy difícil llevarlo al estado donde el volcado de subprocesos escribe algo así como:
Found one Java-level deadlock:
=============================
"Thread-2":
waiting to lock monitor 7f91c5802b58 (object 7fb291380, a java.lang.String),
which is held by "Thread-1"
"Thread-1":
waiting to lock monitor 7f91c6075308 (object 7fb2914a0, a java.lang.String),
which is held by "Thread-2"
Java stack information for the threads listed above:
===================================================
"Thread-2":
at uk.ac.ebi.Deadlock.run(Deadlock.java:54)
- waiting to lock <7fb291380> (a java.lang.String)
- locked <7fb2914a0> (a java.lang.String)
- locked <7f32a0760> (a uk.ac.ebi.Deadlock)
at java.lang.Thread.run(Thread.java:680)
"Thread-1":
at uk.ac.ebi.Deadlock.run(Deadlock.java:54)
- waiting to lock <7fb2914a0> (a java.lang.String)
- locked <7fb291380> (a java.lang.String)
- locked <7f32a0580> (a uk.ac.ebi.Deadlock)
at java.lang.Thread.run(Thread.java:680)
Entonces, el objetivo sería lograr un punto muerto que JVM considerará un punto muerto. Obviamente, no hay solución como
synchronized (this) {
wait();
}
funcionará en ese sentido, aunque de hecho se detendrán para siempre. Confiar en una condición de carrera tampoco es una buena idea, ya que durante la entrevista generalmente desea mostrar algo que funciona de manera comprobable, no algo que debería funcionar la mayor parte del tiempo.
Ahora, la solución sleep() está bien, en cierto sentido, es difícil imaginar una situación en la que no funcione, pero no sea justo (estamos en un buen deporte, ¿verdad?). La solución de @artbristol (la mía es la misma, solo diferentes objetos como monitores) es agradable, pero larga y usa las nuevas primitivas de concurrencia para que los hilos estén en el estado correcto, lo que no es muy divertido:
public class Deadlock implements Runnable {
private final Object a;
private final Object b;
private final static CountDownLatch latch = new CountDownLatch(2);
public Deadlock(Object a, Object b) {
this.a = a;
this.b = b;
}
public synchronized static void main(String[] args) throws InterruptedException {
new Thread(new Deadlock("a", "b")).start();
new Thread(new Deadlock("b", "a")).start();
}
@Override
public void run() {
synchronized (a) {
latch.countDown();
try {
latch.await();
} catch (InterruptedException ignored) {
}
synchronized (b) {
}
}
}
}
Recuerdo que la solución solo synchronized ajusta a 11..13 líneas de código (sin incluir los comentarios y las importaciones), pero aún no recuerdo el truco real. Se actualizará si lo hago.
Actualización: aquí hay una solución fea en synchronized :
public class Deadlock implements Runnable {
public synchronized static void main(String[] args) throws InterruptedException {
synchronized ("a") {
new Thread(new Deadlock()).start();
"a".wait();
}
synchronized ("") {
}
}
@Override
public void run() {
synchronized ("") {
synchronized ("a") {
"a".notifyAll();
}
synchronized (Deadlock.class) {
}
}
}
}
Tenga en cuenta que reemplazamos un pestillo con un monitor de objeto (usando "a" como objeto).
Una búsqueda simple me dio el siguiente código:
public class Deadlock {
static class Friend {
private final String name;
public Friend(String name) {
this.name = name;
}
public String getName() {
return this.name;
}
public synchronized void bow(Friend bower) {
System.out.format("%s: %s"
+ " has bowed to me!%n",
this.name, bower.getName());
bower.bowBack(this);
}
public synchronized void bowBack(Friend bower) {
System.out.format("%s: %s"
+ " has bowed back to me!%n",
this.name, bower.getName());
}
}
public static void main(String[] args) {
final Friend alphonse =
new Friend("Alphonse");
final Friend gaston =
new Friend("Gaston");
new Thread(new Runnable() {
public void run() { alphonse.bow(gaston); }
}).start();
new Thread(new Runnable() {
public void run() { gaston.bow(alphonse); }
}).start();
}
}
Fuente: punto muerto
Aquí hay un ejemplo de la documentación:
public class Deadlock {
static class Friend {
private final String name;
public Friend(String name) {
this.name = name;
}
public String getName() {
return this.name;
}
public synchronized void bow(Friend bower) {
System.out.format("%s: %s"
+ " has bowed to me!%n",
this.name, bower.getName());
bower.bowBack(this);
}
public synchronized void bowBack(Friend bower) {
System.out.format("%s: %s"
+ " has bowed back to me!%n",
this.name, bower.getName());
}
}
public static void main(String[] args) {
final Friend alphonse =
new Friend("Alphonse");
final Friend gaston =
new Friend("Gaston");
new Thread(new Runnable() {
public void run() { alphonse.bow(gaston); }
}).start();
new Thread(new Runnable() {
public void run() { gaston.bow(alphonse); }
}).start();
}
}
El punto muerto ocurre cuando los hilos (o lo que su plataforma llama sus unidades de ejecución) adquieren recursos, donde cada recurso solo puede ser mantenido por un hilo a la vez, y se aferra a esos recursos de tal manera que las retenciones no pueden ser apropiadas, y existe una relación "circular" entre los subprocesos de modo que cada subproceso en el interbloqueo espera para adquirir algún recurso retenido por otro subproceso.
Por lo tanto, una forma fácil de evitar un punto muerto es dar un orden total a los recursos e imponer una regla de que los recursos solo se adquieren por hilos en orden . Por el contrario, un punto muerto se puede crear intencionalmente al ejecutar subprocesos que adquieren recursos, pero no los adquieren en orden. Por ejemplo:
Dos hilos, dos bloqueos. El primer hilo ejecuta un ciclo que intenta adquirir los bloqueos en un cierto orden, el segundo hilo ejecuta un ciclo que intenta adquirir los bloqueos en el orden opuesto. Cada hilo libera ambos bloqueos después de adquirir con éxito los bloqueos.
public class HighlyLikelyDeadlock {
static class Locker implements Runnable {
private Object first, second;
Locker(Object first, Object second) {
this.first = first;
this.second = second;
}
@Override
public void run() {
while (true) {
synchronized (first) {
synchronized (second) {
System.out.println(Thread.currentThread().getName());
}
}
}
}
}
public static void main(final String... args) {
Object lock1 = new Object(), lock2 = new Object();
new Thread(new Locker(lock1, lock2), "Thread 1").start();
new Thread(new Locker(lock2, lock1), "Thread 2").start();
}
}
Ahora, ha habido algunos comentarios en esta pregunta que señalan la diferencia entre la probabilidad y la certeza del punto muerto. En cierto sentido, la distinción es un problema académico. Desde un punto de vista práctico, ciertamente me gustaría ver un sistema en ejecución que no se estanque con el código que he escrito arriba :)
Sin embargo, las preguntas de la entrevista pueden ser académicas a veces, y esta pregunta SO tiene la palabra "seguramente" en el título, por lo que lo que sigue es un programa que definitivamente se traba. Se crean dos objetos de Locker , cada uno tiene dos bloqueos y CountDownLatch usa para sincronizar entre los hilos. Cada Locker bloquea el primer candado y luego realiza una cuenta atrás del pestillo una vez. Cuando ambos hilos han adquirido un bloqueo y han contado hacia abajo el seguro, pasan por la barrera de cierre e intentan adquirir un segundo bloqueo, pero en cada caso el otro hilo ya tiene el bloqueo deseado. Esta situación produce un punto muerto determinado .
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class CertainDeadlock {
static class Locker implements Runnable {
private CountDownLatch latch;
private Lock first, second;
Locker(CountDownLatch latch, Lock first, Lock second) {
this.latch = latch;
this.first = first;
this.second = second;
}
@Override
public void run() {
String threadName = Thread.currentThread().getName();
try {
first.lock();
latch.countDown();
System.out.println(threadName + ": locked first lock");
latch.await();
System.out.println(threadName + ": attempting to lock second lock");
second.lock();
System.out.println(threadName + ": never reached");
} catch (InterruptedException e) {
throw new RuntimeException(e);
}
}
}
public static void main(final String... args) {
CountDownLatch latch = new CountDownLatch(2);
Lock lock1 = new ReentrantLock(), lock2 = new ReentrantLock();
new Thread(new Locker(latch, lock1, lock2), "Thread 1").start();
new Thread(new Locker(latch, lock2, lock1), "Thread 2").start();
}
}
import java.util.concurrent.CountDownLatch;
public class SO8880286 {
public static class BadRunnable implements Runnable {
private CountDownLatch latch;
public BadRunnable(CountDownLatch latch) {
this.latch = latch;
}
public void run() {
System.out.println("Thread " + Thread.currentThread().getId() + " starting");
synchronized (BadRunnable.class) {
System.out.println("Thread " + Thread.currentThread().getId() + " acquired the monitor on BadRunnable.class");
latch.countDown();
while (true) {
try {
latch.await();
} catch (InterruptedException ex) {
continue;
}
break;
}
}
System.out.println("Thread " + Thread.currentThread().getId() + " released the monitor on BadRunnable.class");
System.out.println("Thread " + Thread.currentThread().getId() + " ending");
}
}
public static void main(String[] args) {
Thread[] threads = new Thread[2];
CountDownLatch latch = new CountDownLatch(threads.length);
for (int i = 0; i < threads.length; ++i) {
threads[i] = new Thread(new BadRunnable(latch));
threads[i].start();
}
}
}
El programa siempre se bloquea porque cada subproceso está esperando en la barrera para los otros subprocesos, pero para esperar la barrera, el subproceso debe mantener el monitor en BadRunnable.class .