Apa perbedaan antara jalan buntu dan livelock?

Bisakah seseorang tolong jelaskan dengan contoh (kode) apa perbedaan antara kebuntuan dan livelock ?

Diambil dari http://en.wikipedia.org/wiki/Deadlock :

Dalam komputasi bersamaan, kebuntuan adalah keadaan di mana setiap anggota grup tindakan, sedang menunggu beberapa anggota lainnya untuk melepaskan kunci

Sebuah livelock mirip dengan kebuntuan, kecuali bahwa negara-negara dari proses yang terlibat dalam livelock terus-menerus berubah sehubungan dengan satu sama lain, tidak ada kemajuan. Livelock adalah kasus khusus kelaparan sumber daya; definisi umum hanya menyatakan bahwa proses tertentu tidak mengalami kemajuan.

Contoh livelock di dunia nyata terjadi ketika dua orang bertemu di koridor sempit, dan masing-masing mencoba bersikap sopan dengan menyingkir untuk membiarkan yang lain lewat, tetapi mereka akhirnya bergoyang dari sisi ke sisi tanpa membuat kemajuan karena mereka berdua berulang kali bergerak dengan cara yang sama pada saat yang bersamaan.

Livelock adalah risiko dengan beberapa algoritma yang mendeteksi dan memulihkan dari kebuntuan. Jika lebih dari satu proses mengambil tindakan, algoritma deteksi kebuntuan dapat dipicu berulang kali. Ini dapat dihindari dengan memastikan bahwa hanya satu proses (dipilih secara acak atau berdasarkan prioritas) yang mengambil tindakan.

Livelock

Sebuah utas sering bertindak sebagai respons terhadap tindakan utas lain. Jika tindakan utas lainnya juga merupakan respons terhadap tindakan utas lain, maka livelock dapat terjadi.

Seperti halnya jalan buntu, utas yang tidak dapat membuat kemajuan lebih lanjut . Namun, utas tidak diblokir - mereka terlalu sibuk merespons satu sama lain untuk melanjutkan pekerjaan . Ini sebanding dengan dua orang yang berusaha saling melewati di koridor: Alphonse bergerak ke kiri untuk membiarkan Gaston lewat, sementara Gaston bergerak ke kanannya untuk membiarkan Alphonse lewat. Melihat mereka masih saling menghalangi, Alphonse bergerak ke kanan, sementara Gaston bergerak ke kiri. Mereka masih saling menghalangi, dan seterusnya ...

Perbedaan utama antara livelock dan jalan buntu adalah bahwa utas tidak akan diblokir, sebaliknya mereka akan mencoba saling merespons secara terus menerus.

Pada gambar ini, kedua lingkaran (utas atau proses) akan mencoba memberi ruang kepada yang lain dengan bergerak ke kiri dan ke kanan. Tetapi mereka tidak bisa bergerak lebih jauh.

Semua konten dan contoh di sini berasal

Sistem Operasi: Internal dan Prinsip Desain
William Stallings
Edisi 8º

Jalan buntu : Situasi di mana dua atau lebih proses tidak dapat dilanjutkan karena masing-masing menunggu satu sama lain untuk melakukan sesuatu.

Sebagai contoh, pertimbangkan dua proses, P1 dan P2, dan dua sumber daya, R1 dan R2. Misalkan setiap proses memerlukan akses ke kedua sumber daya untuk melakukan bagian dari fungsinya. Maka dimungkinkan untuk memiliki situasi berikut: OS menetapkan R1 ke P2, dan R2 ke P1. Setiap proses menunggu salah satu dari dua sumber. Tidak satu pun akan melepaskan sumber daya yang sudah dimiliki sampai memiliki sumber daya lain dan melakukan fungsi yang membutuhkan kedua sumber daya. Kedua proses menemui jalan buntu

Livelock : Situasi di mana dua atau lebih proses secara terus-menerus mengubah keadaan mereka sebagai respons terhadap perubahan dalam proses lain tanpa melakukan pekerjaan yang bermanfaat:

Kelaparan : Suatu situasi di mana proses runnable diabaikan tanpa batas oleh penjadwal; meskipun ia dapat melanjutkan, itu tidak pernah dipilih.

Misalkan tiga proses (P1, P2, P3) masing-masing memerlukan akses berkala ke sumber daya R. Pertimbangkan situasi di mana P1 memiliki sumber daya, dan kedua P2 dan P3 tertunda, menunggu sumber daya itu. Ketika P1 keluar dari bagian kritisnya, P2 atau P3 harus diizinkan mengakses R. Asumsikan bahwa OS memberikan akses ke P3 dan bahwa P1 lagi membutuhkan akses sebelum P3 menyelesaikan bagian kritisnya. Jika OS memberikan akses ke P1 setelah P3 selesai, dan kemudian secara bergantian memberikan akses ke P1 dan P3, maka P2 tanpa batas waktu dapat ditolak akses ke sumber daya, meskipun tidak ada situasi jalan buntu.

LAMPIRAN A - TOPIK DALAM KONSURENSI

Contoh kebuntuan

Jika kedua proses mengatur flag mereka menjadi true sebelum salah satu telah menjalankan pernyataan while, maka masing-masing akan berpikir bahwa yang lain telah memasuki bagian kritisnya, menyebabkan kebuntuan.

/* PROCESS 0 */
flag[0] = true;            // <- get lock 0
while (flag[1])            // <- is lock 1 free?
    /* do nothing */;      // <- no? so I wait 1 second, for example
                           // and test again.
                           // on more sophisticated setups we can ask
                           // to be woken when lock 1 is freed
/* critical section*/;     // <- do what we need (this will never happen)
flag[0] = false;           // <- releasing our lock

 /* PROCESS 1 */
flag[1] = true;
while (flag[0])
    /* do nothing */;
/* critical section*/;
flag[1] = false;

Contoh Livelock

/* PROCESS 0 */
flag[0] = true;          // <- get lock 0
while (flag[1]){         
    flag[0] = false;     // <- instead of sleeping, we do useless work
                         //    needed by the lock mechanism
    /*delay */;          // <- wait for a second
    flag[0] = true;      // <- and restart useless work again.
}
/*critical section*/;    // <- do what we need (this will never happen)
flag[0] = false; 

/* PROCESS 1 */
flag[1] = true;
while (flag[0]) {
    flag[1] = false;
    /*delay */;
    flag[1] = true;
}
/* critical section*/;
flag[1] = false;

[...] pertimbangkan urutan kejadian berikut:

• P0 menetapkan flag [0] menjadi true.
• P1 menetapkan flag [1] menjadi true.
• P0 memeriksa flag [1].
• P1 memeriksa flag [0].
• P0 menetapkan flag [0] menjadi false.
• P1 menetapkan flag [1] menjadi false.
• P0 menetapkan flag [0] menjadi true.
• P1 menetapkan flag [1] menjadi true.

Urutan ini dapat diperpanjang tanpa batas waktu, dan tidak ada proses yang bisa masuk ke bagian kritisnya. Sebenarnya, ini bukan jalan buntu , karena setiap perubahan dalam kecepatan relatif dari dua proses akan memutus siklus ini dan memungkinkan seseorang untuk memasuki bagian kritis. Kondisi ini disebut livelock . Ingat bahwa kebuntuan terjadi ketika serangkaian proses ingin memasuki bagian kritis mereka tetapi tidak ada proses yang bisa berhasil. Dengan livelock , ada kemungkinan urutan eksekusi yang berhasil, tetapi juga dimungkinkan untuk menggambarkan satu atau lebih urutan eksekusi di mana tidak ada proses yang pernah memasuki bagian kritisnya.

Tidak puas dari buku lagi.

Dan bagaimana dengan spinlocks?

Spinlock adalah teknik untuk menghindari biaya mekanisme kunci OS. Biasanya yang akan Anda lakukan:

try
{
   lock = beginLock();
   doSomething();
}
finally
{
   endLock();
}

Masalah mulai muncul ketika beginLock()harganya jauh lebih mahal doSomething(). Dalam istilah yang sangat luas, bayangkan apa yang terjadi ketika beginLockbiaya 1 detik, tetapi doSomethingbiaya hanya 1 milidetik.

Dalam hal ini jika Anda menunggu 1 milidetik, Anda akan terhindar selama 1 detik.

Mengapa beginLockharganya sangat mahal? Jika kunci gratis tidak memerlukan biaya banyak (lihat https://stackoverflow.com/a/49712993/5397116 ), tetapi jika kunci tidak gratis OS akan "membekukan" utas Anda, siapkan mekanisme untuk membangunkan Anda ketika kunci dibebaskan, dan kemudian membangunkan Anda lagi di masa depan.

Semua ini jauh lebih mahal daripada beberapa loop yang memeriksa kunci. Itulah sebabnya terkadang lebih baik melakukan "spinlock".

Sebagai contoh:

void beginSpinLock(lock)
{
   if(lock) loopFor(1 milliseconds);
   else 
   {
     lock = true;
     return;
   }

   if(lock) loopFor(2 milliseconds);
   else 
   {
     lock = true;
     return;
   }

   // important is that the part above never 
   // cause the thread to sleep.
   // It is "burning" the time slice of this thread.
   // Hopefully for good.

   // some implementations fallback to OS lock mechanism
   // after a few tries
   if(lock) return beginLock(lock);
   else 
   {
     lock = true;
     return;
   }
}

Jika implementasi Anda tidak hati-hati, Anda dapat jatuh cinta, menghabiskan semua CPU pada mekanisme kunci.

Lihat juga:

https://preshing.com/20120226/roll-your-own-lightweight-mutex/
Apakah implementasi penguncian spin saya benar dan optimal?

Ringkasan :

Deadlock : situasi di mana tidak ada yang maju, tidak melakukan apa-apa (tidur, menunggu dll.). Penggunaan CPU akan rendah;

Livelock : situasi di mana tidak ada kemajuan, tetapi CPU dihabiskan untuk mekanisme kunci dan bukan pada perhitungan Anda;

Kelaparan: situasi di mana satu penuntut tidak pernah mendapat kesempatan untuk lari; karena nasib buruk atau oleh beberapa propertinya (prioritas rendah, misalnya);

Spinlock : teknik menghindari biaya menunggu kunci dibebaskan.

DEADLOCK Deadlock adalah suatu kondisi di mana tugas menunggu tanpa batas untuk kondisi yang tidak pernah dapat dipenuhi - tugas mengklaim kontrol eksklusif atas sumber daya bersama - tugas memegang sumber daya sambil menunggu sumber daya lainnya akan dirilis - tugas tidak dapat dipaksa untuk melemahkan sumber daya - menunggu melingkar kondisi ada

LIVELOCK Kondisi Livelock dapat muncul ketika dua atau lebih tugas bergantung pada dan menggunakan beberapa sumber daya yang menyebabkan kondisi dependensi melingkar di mana tugas-tugas terus berjalan selamanya, sehingga memblokir semua tugas tingkat prioritas yang lebih rendah dari berjalan (tugas-tugas prioritas yang lebih rendah ini mengalami kondisi yang disebut kelaparan)

Mungkin dua contoh ini menggambarkan Anda perbedaan antara jalan buntu dan livelock:

Java-Contoh untuk kebuntuan:

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class DeadlockSample {

    private static final Lock lock1 = new ReentrantLock(true);
    private static final Lock lock2 = new ReentrantLock(true);

    public static void main(String[] args) {
        Thread threadA = new Thread(DeadlockSample::doA,"Thread A");
        Thread threadB = new Thread(DeadlockSample::doB,"Thread B");
        threadA.start();
        threadB.start();
    }

    public static void doA() {
        System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
        lock1.lock();
        System.out.println(Thread.currentThread().getName() + " : holds lock 1");

        try {
            System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
            lock2.lock();
            System.out.println(Thread.currentThread().getName() + " : holds lock 2");

            try {
                System.out.println(Thread.currentThread().getName() + " : critical section of doA()");
            } finally {
                lock2.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
            }
        } finally {
            lock1.unlock();
            System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
        }
    }

    public static void doB() {
        System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
        lock2.lock();
        System.out.println(Thread.currentThread().getName() + " : holds lock 2");

        try {
            System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
            lock1.lock();
            System.out.println(Thread.currentThread().getName() + " : holds lock 1");

            try {
                System.out.println(Thread.currentThread().getName() + " : critical section of doB()");
            } finally {
                lock1.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
            }
        } finally {
            lock2.unlock();
            System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
        }
    }
}

Output sampel:

Thread A : waits for lock 1
Thread B : waits for lock 2
Thread A : holds lock 1
Thread B : holds lock 2
Thread B : waits for lock 1
Thread A : waits for lock 2

Java-Contoh untuk livelock:

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class LivelockSample {

    private static final Lock lock1 = new ReentrantLock(true);
    private static final Lock lock2 = new ReentrantLock(true);

    public static void main(String[] args) {
        Thread threadA = new Thread(LivelockSample::doA, "Thread A");
        Thread threadB = new Thread(LivelockSample::doB, "Thread B");
        threadA.start();
        threadB.start();
    }

    public static void doA() {
        try {
            while (!lock1.tryLock()) {
                System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
                Thread.sleep(100);
            }
            System.out.println(Thread.currentThread().getName() + " : holds lock 1");

            try {
                while (!lock2.tryLock()) {
                    System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
                    Thread.sleep(100);
                }
                System.out.println(Thread.currentThread().getName() + " : holds lock 2");

                try {
                    System.out.println(Thread.currentThread().getName() + " : critical section of doA()");
                } finally {
                    lock2.unlock();
                    System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
                }
            } finally {
                lock1.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
            }
        } catch (InterruptedException e) {
            // can be ignored here for this sample
        }
    }

    public static void doB() {
        try {
            while (!lock2.tryLock()) {
                System.out.println(Thread.currentThread().getName() + " : waits for lock 2");
                Thread.sleep(100);
            }
            System.out.println(Thread.currentThread().getName() + " : holds lock 2");

            try {
                while (!lock1.tryLock()) {
                    System.out.println(Thread.currentThread().getName() + " : waits for lock 1");
                    Thread.sleep(100);
                }
                System.out.println(Thread.currentThread().getName() + " : holds lock 1");

                try {
                    System.out.println(Thread.currentThread().getName() + " : critical section of doB()");
                } finally {
                    lock1.unlock();
                    System.out.println(Thread.currentThread().getName() + " : does not hold lock 1 any longer");
                }
            } finally {
                lock2.unlock();
                System.out.println(Thread.currentThread().getName() + " : does not hold lock 2 any longer");
            }
        } catch (InterruptedException e) {
            // can be ignored here for this sample
        }
    }
}

Output sampel:

Thread B : holds lock 2
Thread A : holds lock 1
Thread A : waits for lock 2
Thread B : waits for lock 1
Thread B : waits for lock 1
Thread A : waits for lock 2
Thread A : waits for lock 2
Thread B : waits for lock 1
Thread B : waits for lock 1
Thread A : waits for lock 2
Thread A : waits for lock 2
Thread B : waits for lock 1
...

Kedua contoh memaksa utas untuk mendapatkan kunci dalam pesanan yang berbeda. Sementara kebuntuan menunggu kunci lainnya, livelock tidak benar-benar menunggu - itu mati-matian mencoba untuk mendapatkan kunci tanpa kesempatan mendapatkannya. Setiap percobaan mengkonsumsi siklus CPU.

Bayangkan Anda memiliki utas A dan utas B. Keduanya berada synchroniseddi objek yang sama dan di dalam blok ini ada variabel global yang keduanya diperbarui;

static boolean commonVar = false;
Object lock = new Object;

...

void threadAMethod(){
    ...
    while(commonVar == false){
         synchornized(lock){
              ...
              commonVar = true
         }
    }
}

void threadBMethod(){
    ...
    while(commonVar == true){
         synchornized(lock){
              ...
              commonVar = false
         }
    }
}

Jadi, ketika benang A masuk dalam whilelingkaran dan memegang kunci, itu tidak apa yang harus dilakukan dan mengatur commonVaruntuk true. Kemudian benang B masuk, masuk dalam whilelingkaran dan karena commonVarini truesekarang, itu dapat memegang kunci. Itu melakukannya, mengeksekusi synchronisedblok, dan mengatur commonVarkembali ke false. Sekarang, benang A lagi mendapat itu jendela CPU baru, itu adalah tentang untuk keluar dari whilelingkaran tapi thread B baru saja mengatur kembali ke false, sehingga siklus berulang lagi. Utas melakukan sesuatu (jadi mereka tidak diblokir dalam arti tradisional) tetapi untuk hampir tidak ada.

Mungkin juga menyenangkan untuk menyebutkan bahwa livelock tidak harus muncul di sini. Saya berasumsi bahwa scheduler lebih menyukai utas lainnya setelah synchronisedblok selesai dieksekusi. Sebagian besar waktu, saya pikir itu adalah ekspektasi yang sulit dicapai dan tergantung pada banyak hal yang terjadi di bawah tenda.