Menulis program yang pasti akan menemui jalan buntu [ditutup]

Saya baru-baru ini mendapatkan pertanyaan ini dalam sebuah wawancara.

Saya menjawab bahwa deadlock terjadi jika interleaving salah, tetapi pewawancara bersikeras bahwa program yang akan selalu menemui jalan buntu terlepas dari interleaving dapat ditulis.

Bisakah kita menulis program seperti itu? Dapatkah Anda menunjukkan kepada saya beberapa program contoh seperti itu?

PEMBARUAN: Pertanyaan ini adalah subjek blog saya pada Januari 2013 . Terima kasih atas pertanyaan bagusnya!

Bagaimana kita bisa menulis program yang akan selalu menemui jalan buntu tidak peduli bagaimana utas dijadwalkan?

Berikut adalah contoh di C #. Perhatikan bahwa program tersebut tampaknya tidak berisi kunci dan tidak ada data bersama. Ia hanya memiliki satu variabel lokal dan tiga pernyataan, namun ia menemui jalan buntu dengan kepastian 100%. Seseorang akan kesulitan untuk menghasilkan program yang lebih sederhana yang menemui jalan buntu dengan pasti.

Latihan untuk pembaca # 1: jelaskan bagaimana kebuntuan ini. (Jawaban ada di komentar.)

Latihan untuk pembaca # 2: mendemonstrasikan kebuntuan yang sama di Java. (Jawabannya ada di sini: https://stackoverflow.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() 
  { }
}

Pengunci di sini memastikan bahwa kedua kunci ditahan saat setiap utas mencoba mengunci yang lain:

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();

   }

}

Menarik untuk menjalankan jconsole, yang akan menunjukkan jalan buntu dengan benar di tab Threads.

Terjadi kebuntuan ketika utas (atau apa pun yang disebut platform Anda sebagai unit eksekusinya) memperoleh sumber daya, di mana setiap sumber daya hanya dapat disimpan oleh satu utas pada satu waktu, dan menyimpan sumber daya tersebut sedemikian rupa sehingga penangguhan tidak dapat dilakukan sebelumnya, dan terdapat beberapa hubungan "melingkar" antara utas sedemikian rupa sehingga setiap utas di jalan buntu menunggu untuk memperoleh beberapa sumber daya yang dipegang oleh utas lain.

Jadi, cara mudah untuk menghindari kebuntuan adalah dengan memberikan beberapa pengurutan total ke sumber daya dan menerapkan aturan bahwa sumber daya hanya dapat diperoleh dengan utas secara berurutan . Sebaliknya, kebuntuan dapat dibuat dengan sengaja dengan menjalankan utas yang memperoleh sumber daya, tetapi tidak mendapatkannya secara berurutan. Sebagai contoh:

Dua utas, dua kunci. Utas pertama menjalankan putaran yang mencoba mendapatkan kunci dalam urutan tertentu, utas kedua menjalankan putaran yang mencoba mendapatkan kunci dalam urutan yang berlawanan. Setiap utas melepaskan kedua kunci setelah berhasil memperoleh kunci.

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();
    }
}

Sekarang, ada beberapa komentar dalam pertanyaan ini yang menunjukkan perbedaan antara kemungkinan dan kepastian deadlock. Dalam beberapa hal, perbedaan adalah masalah akademis. Dari sudut pandang praktis, saya pasti ingin melihat sistem yang berjalan tidak mengalami kebuntuan dengan kode yang saya tulis di atas :)

Namun, pertanyaan wawancara terkadang bisa bersifat akademis, dan pertanyaan SO ini memang memiliki kata "pasti" di judulnya, jadi berikut ini adalah program yang pasti menemui jalan buntu. Dua Lockerobjek dibuat, masing-masing diberi dua kunci dan CountDownLatchdigunakan untuk menyinkronkan antar utas. Masing-masing Lockermengunci kunci pertama lalu menghitung mundur kait satu kali. Ketika kedua utas telah memperoleh kunci dan menghitung mundur kait, mereka melanjutkan melewati penghalang kait dan mencoba mendapatkan kunci kedua, tetapi dalam setiap kasus utas lainnya sudah memegang kunci yang diinginkan. Situasi ini menghasilkan kebuntuan tertentu .

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();
    }
}

Berikut adalah contoh Java dengan mengikuti salah satu 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() {           
        Lock lock = new Lock();      
    }

}

Berikut adalah Contoh dari dokumentasinya:

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();
    }
}

Saya telah menulis ulang contoh deadlock versi Java Yuriy Zubarev yang diposting oleh Eric Lippert: https://stackoverflow.com/a/9286697/2098232 agar lebih mirip dengan versi C #. Jika blok inisialisasi Java berfungsi mirip dengan konstruktor statis C # dan pertama kali memperoleh kunci, kita tidak memerlukan utas lain untuk juga memanggil metode gabungan untuk mendapatkan kebuntuan, ia hanya perlu memanggil beberapa metode statis dari kelas Lock, seperti C # asli contoh. Kebuntuan yang terjadi tampaknya mengkonfirmasi hal ini.

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");
    }

}

Ini bukan tugas wawancara paling sederhana yang bisa Anda dapatkan: dalam proyek saya, itu melumpuhkan kerja tim sepanjang hari. Sangat mudah untuk membuat program Anda berhenti, tetapi sangat sulit untuk mencapai keadaan di mana thread dump menulis sesuatu seperti,

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)

Jadi tujuannya adalah untuk mendapatkan jalan buntu yang akan dianggap JVM sebagai jalan buntu. Jelas, tidak ada solusi seperti itu

synchronized (this) {
    wait();
}

akan bekerja dalam pengertian itu, meskipun mereka memang akan berhenti selamanya. Mengandalkan kondisi ras juga bukan ide yang baik, karena selama wawancara Anda biasanya ingin menunjukkan sesuatu yang terbukti berhasil, bukan sesuatu yang seharusnya berhasil di sebagian besar waktu.

Sekarang, sleep()solusinya baik-baik saja dalam arti sulit membayangkan situasi di mana itu tidak berhasil, tetapi tidak adil (kami dalam olahraga yang adil, bukan?). Solusi oleh @artbristol (milik saya sama, hanya objek yang berbeda seperti monitor) bagus, tetapi panjang dan menggunakan primitif konkurensi baru untuk mendapatkan utas dalam keadaan yang benar, yang tidak terlalu menyenangkan:

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) {
            }
        }
    }
}

Saya ingat bahwa synchronizedsolusi -hanya cocok dengan 11..13 baris kode (tidak termasuk komentar dan impor), tetapi belum mengingat trik yang sebenarnya. Akan diperbarui jika saya lakukan.

Pembaruan: inilah solusi buruk tentang 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) {
            }
        }
    }
}

Perhatikan kami mengganti kait dengan monitor objek (menggunakan "a"sebagai objek).

Versi C # ini, saya kira java seharusnya sangat mirip.

static void Main(string[] args)
{
    var mainThread = Thread.CurrentThread;
    mainThread.Join();

    Console.WriteLine("Press Any key");
    Console.ReadKey();
}

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();
        }
    }
}

Program selalu menemui jalan buntu karena setiap utas menunggu di penghalang untuk utas lainnya, tetapi untuk menunggu penghalang, utas harus menahan monitor BadRunnable.class.

Ada contoh di Jawa di sini

http://baddotrobot.com/blog/2009/12/24/deadlock/

Dimana penculik menemui jalan buntu ketika dia menolak untuk menyerahkan korban sampai dia mendapatkan uang tetapi negosiator menolak untuk menyerahkan uang sampai dia mendapatkan korban.

Pencarian sederhana memberi saya kode berikut:

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();
    }
}

Sumber: Deadlock

Berikut contoh di mana satu utas memegang kunci memulai utas lain yang menginginkan kunci yang sama dan kemudian starter menunggu sampai mulai selesai ... selamanya:

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();
    }
}

Berikut ini contohnya:

dua utas sedang berjalan, masing-masing menunggu untuk melepaskan kunci

kelas publik ThreadClass memperluas 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();
            }
        }

    }


}

}

Menjalankan ini akan menyebabkan kebuntuan:

kelas publik 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);


}

}