Apa itu jalan buntu?

159

Saat menulis aplikasi multi-utas, salah satu masalah paling umum yang dialami adalah kebuntuan.

Pertanyaan saya kepada komunitas adalah:

  1. Apa itu jalan buntu?

  2. Bagaimana Anda mendeteksi mereka?

  3. Apakah Anda menanganinya?

  4. Dan akhirnya, bagaimana Anda mencegahnya terjadi?

bmurphy1976
sumber

Jawaban:

207

Sebuah kunci terjadi ketika beberapa proses mencoba untuk mengakses sumber daya yang sama pada waktu yang sama.

Satu proses hilang dan harus menunggu yang lain selesai.

Sebuah kebuntuan terjadi ketika proses tunggu masih berpegang pada sumber daya lain yang kebutuhan pertama sebelum dapat menyelesaikan.

Jadi, sebuah contoh:

Sumber daya A dan sumber daya B digunakan oleh proses X dan proses Y

  • X mulai menggunakan A.
  • X dan Y mencoba untuk mulai menggunakan B
  • Y 'menang' dan mendapat B pertama
  • sekarang Y perlu menggunakan A
  • A dikunci oleh X, yang sedang menunggu Y

Cara terbaik untuk menghindari kebuntuan adalah dengan menghindari proses melintas dengan cara ini. Kurangi kebutuhan untuk mengunci apa pun sebanyak yang Anda bisa.

Dalam basis data, hindari membuat banyak perubahan pada tabel yang berbeda dalam satu transaksi, hindari pemicu dan beralih ke optimis / kotor / nolock membaca sebanyak mungkin.

Keith
sumber
9
Saya menggunakan proses di sini sebagai generalisasi, bukan secara khusus Proses OS. Ini bisa berupa utas, tetapi bisa juga aplikasi yang sama sekali berbeda, atau koneksi basis data. Polanya sama.
Keith
1
Hai, mengingat skenario ini: Thread A mengunci sumber daya A dan memiliki proses yang panjang. Thread B menunggu untuk mengunci sumber daya A. Penggunaan waktu CPU: 20%, dapatkah Anda menganggap bahwa situasi jalan buntu?
rickyProgrammer
2
@rickyProgrammer tidak, itu hanya menunggu kunci biasa, meskipun perbedaannya sedikit akademis. B menunggu lambat A adalah kunci, B menunggu A menunggu B adalah jalan buntu.
Keith
Jadi kebuntuan lebih dari dua proses dengan sumber daya terkunci menunggu sumber daya tersebut dirilis ..
rickyProgrammer
2
@rickyProgrammer adalah kunci yang tidak akan menjadi bebas, tidak peduli berapa lama Anda menunggu, karena antrian bundar.
Keith
126

Biarkan saya menjelaskan contoh dunia nyata (tidak benar-benar nyata) untuk situasi jalan buntu dari film-film kejahatan. Bayangkan seorang penjahat menyandera dan melawan itu, seorang polisi juga menyandera seorang teman penjahat. Dalam kasus ini, penjahat tidak akan membiarkan sandera pergi jika polisi tidak akan membiarkan temannya melepaskannya. Juga polisi tidak akan membiarkan teman penjahat melepaskan, kecuali penjahat melepaskan sandera. Ini adalah situasi yang tak dapat dipercaya yang tak ada habisnya, karena kedua belah pihak bersikeras langkah pertama dari satu sama lain.

Criminal & Cop Scene

masukkan deskripsi gambar di sini

Jadi sederhananya, ketika dua utas membutuhkan dua sumber daya yang berbeda dan masing-masing dari mereka memiliki kunci sumber daya yang dibutuhkan oleh yang lain, itu adalah jalan buntu.

Penjelasan Tingkat Tinggi Kebuntuan Lain: Patah Hati

Anda berkencan dengan seorang gadis dan satu hari setelah pertengkaran, kedua belah pihak hancur hati satu sama lain dan menunggu panggilan saya-maaf-dan-saya-tidak terjawab . Dalam situasi ini, kedua belah pihak ingin berkomunikasi satu sama lain jika dan hanya jika salah satu dari mereka menerima panggilan maaf dari yang lain. Karena masing-masing tidak akan memulai komunikasi dan menunggu dalam keadaan pasif, keduanya akan menunggu yang lain untuk memulai komunikasi yang berakhir dalam situasi jalan buntu.

Levent Divilioglu
sumber
Tidakkah utas milik proses berbeda ?, bisakah utas milik proses yang sama juga menyebabkan jalan buntu?
lordvcs
1
@diabolicfreak Tidak masalah apakah utasnya memiliki proses yang sama atau tidak.
Sam Malayek
2
Contoh lain dari kehidupan nyata adalah empat mobil datang ke persimpangan dua jalan yang sama dalam empat arah secara bersamaan. Setiap orang perlu memberi jalan ke mobil dari sisi kanan, sehingga tidak ada yang bisa melanjutkan.
LoBo
35

Kebuntuan hanya akan terjadi ketika Anda memiliki dua kunci atau lebih yang dapat diperoleh pada saat yang sama dan mereka diambil dalam urutan yang berbeda.

Cara untuk menghindari kebuntuan adalah:

  • hindari memiliki kunci (jika mungkin),
  • hindari memiliki lebih dari satu kunci
  • selalu ambil kunci dalam urutan yang sama.
Mats Fredriksson
sumber
Poin ke-3 untuk mencegah kebuntuan (selalu mengambil kunci dalam urutan yang sama) sangat penting, yang agak mudah dilupakan dalam praktik pengkodean.
Qiang Xu
20

Untuk mendefinisikan kebuntuan, pertama saya akan mendefinisikan proses.

Proses : Seperti yang kita tahu proses tidak lain adalah programeksekusi.

Sumberdaya : Untuk menjalankan suatu proses program dibutuhkan beberapa sumber daya. Kategori sumber daya dapat meliputi memori, printer, CPU, file terbuka, tape drive, CD-ROM, dll.

Jalan buntu : Deadlock adalah situasi atau kondisi ketika dua proses atau lebih memegang beberapa sumber daya dan mencoba untuk memperoleh beberapa sumber daya lebih banyak, dan mereka tidak dapat melepaskan sumber daya sampai mereka menyelesaikan eksekusi di sana.

Kondisi atau situasi jalan buntu

masukkan deskripsi gambar di sini

Dalam diagram di atas ada dua proses P1 dan p2 dan ada dua sumber daya R1 dan R2 .

Sumber daya R1 dialokasikan untuk memproses P1 dan sumber daya R2 dialokasikan untuk memproses p2 . Untuk menyelesaikan eksekusi proses P1 perlu resource R2 , jadi P1 meminta R2 , tetapi R2 sudah dialokasikan untuk P2 .

Dengan cara yang sama, Proses P2 untuk menyelesaikan eksekusi membutuhkan R1 , tetapi R1 sudah dialokasikan untuk P1 .

kedua proses tidak dapat melepaskan sumber daya mereka sampai dan kecuali mereka menyelesaikan eksekusi mereka. Jadi keduanya menunggu sumber daya lain dan mereka akan menunggu selamanya. Jadi ini DEADLOCK Kondisi .

Agar kebuntuan terjadi, empat kondisi harus benar.

  1. Pengecualian bersama - Setiap sumber daya saat ini dialokasikan tepat untuk satu proses atau tersedia. (Dua proses tidak dapat secara bersamaan mengontrol sumber daya yang sama atau berada di bagian kritis mereka).
  2. Tahan dan Tunggu - proses yang memegang sumber daya saat ini dapat meminta sumber daya baru.
  3. Tanpa preemption - Setelah suatu proses memiliki sumber daya, itu tidak dapat diambil oleh proses lain atau kernel.
  4. Circular wait - Setiap proses menunggu untuk mendapatkan sumber daya yang dimiliki oleh proses lain.

dan semua kondisi ini terpenuhi dalam diagram di atas.

Varun
sumber
8

Kebuntuan terjadi ketika utas sedang menunggu sesuatu yang tidak pernah terjadi.

Biasanya, ini terjadi ketika utas menunggu pada mutex atau semaphore yang tidak pernah dirilis oleh pemilik sebelumnya.

Ini juga sering terjadi ketika Anda memiliki situasi yang melibatkan dua utas dan dua kunci seperti ini:

Thread 1               Thread 2

Lock1->Lock();         Lock2->Lock();
WaitForLock2();        WaitForLock1();   <-- Oops!

Anda biasanya mendeteksi mereka karena hal-hal yang Anda harapkan terjadi tidak pernah dilakukan, atau aplikasi hang sepenuhnya.

17 dari 26
sumber
Kebuntuan terjadi ketika utas sedang menunggu sesuatu yang tidak dapat terjadi.
Marquis of Lorne
4

Anda dapat melihat artikel yang luar biasa ini , di bawah bagian Deadlock . Itu ada di C # tetapi idenya masih sama untuk platform lain. Saya kutip di sini agar mudah dibaca

Kebuntuan terjadi ketika dua utas masing-masing menunggu sumber daya dipegang oleh yang lain, sehingga tidak ada yang bisa melanjutkan. Cara termudah untuk menggambarkan ini adalah dengan dua kunci:

object locker1 = new object();
object locker2 = new object();

new Thread (() => {
                    lock (locker1)
                    {
                      Thread.Sleep (1000);
                      lock (locker2);      // Deadlock
                    }
                  }).Start();
lock (locker2)
{
  Thread.Sleep (1000);
  lock (locker1);                          // Deadlock
}
onmyway133
sumber
4

Deadlock adalah masalah umum dalam masalah multiprocessing / multiprogramming di OS. Katakanlah ada dua proses P1, P2 dan dua sumber daya yang dapat dibagikan secara global R1, R2 dan di bagian kritis kedua sumber daya perlu diakses

Awalnya, OS menetapkan R1 untuk memproses P1 dan R2 untuk memproses P2. Karena kedua proses berjalan secara bersamaan, mereka mungkin mulai mengeksekusi kode mereka tetapi MASALAH muncul ketika suatu proses menyentuh bagian kritis. Jadi proses R1 akan menunggu proses P2 untuk merilis R2 dan sebaliknya ... Jadi mereka akan menunggu selamanya (DEADLOCK CONDITION).

ANALOGI kecil ...

Ibumu (OS),
Kamu (P1),
Saudaramu (P2),
Apple (R1),
Knife (R2),
bagian kritis (memotong apel dengan pisau).

Ibumu memberimu apel dan pisau untuk kakakmu di awal.
Keduanya senang dan bermain (Menjalankan kode mereka).
Siapa pun dari Anda ingin memotong apel (bagian kritis) di beberapa titik.
Anda tidak ingin memberikan apel kepada saudaramu.
Kakakmu tidak mau memberikan pisau kepadamu.
Jadi kalian berdua akan menunggu untuk waktu yang sangat lama :)

Rohit Singh
sumber
2

Kebuntuan terjadi ketika dua utas meminta kunci yang mencegah salah satu dari mereka berkembang. Cara terbaik untuk menghindarinya adalah dengan pengembangan yang cermat. Banyak sistem tertanam melindungi dari mereka dengan menggunakan pengawas waktu (pengatur waktu yang me-reset sistem setiap kali jika hang untuk jangka waktu tertentu).

Joseph Sturtevant
sumber
2

Kebuntuan terjadi ketika ada rantai melingkar benang atau proses yang masing-masing memegang sumber daya yang terkunci dan mencoba untuk mengunci sumber daya yang dimiliki oleh elemen berikutnya dalam rantai. Misalnya, dua utas yang masing-masing menahan kunci A dan kunci B, dan keduanya berusaha mendapatkan kunci lainnya.

Marquis dari Lorne
sumber
Saya memilih Anda. Jawaban Anda lebih ringkas daripada di atas karena membuat kebuntuan yang membingungkan terjadi karena proses atau utas. Ada yang bilang proses, ada yang bilang utas :)
hainguyen
1

Program klasik dan sangat sederhana untuk memahami situasi Deadlock : -

public class Lazy {

    private static boolean initialized = false;

    static {
        Thread t = new Thread(new Runnable() {
            public void run() {
                initialized = true;
            }
        });

        t.start();

        try {
            t.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        System.out.println(initialized);
    }
}

Ketika utas utama memanggil Lazy.main, ia memeriksa apakah kelas Lazy telah diinisialisasi dan mulai menginisialisasi kelas. Utas utama sekarang menyetel inisialisasi ke false, membuat dan memulai utas latar belakang yang metodenya set diinisialisasi menjadi true, dan menunggu utas latar belakang selesai.

Kali ini, kelas saat ini sedang diinisialisasi oleh utas lainnya. Dalam keadaan ini, utas saat ini, yang merupakan utas latar belakang, menunggu objek Class hingga inisialisasi selesai. Sayangnya, utas yang sedang melakukan inisialisasi, utas utama, sedang menunggu utas latar belakang selesai. Karena dua utas sekarang menunggu satu sama lain, program ini DIHADAPI.

Vivek Pratap Singh
sumber
0

Kebuntuan adalah keadaan sistem di mana tidak ada proses / utas tunggal yang mampu melakukan suatu tindakan. Seperti disebutkan oleh orang lain, kebuntuan biasanya merupakan hasil dari situasi di mana setiap proses / utas ingin mendapatkan kunci ke sumber daya yang sudah dikunci oleh proses / utas lain (atau bahkan sama).

Ada berbagai metode untuk menemukannya dan menghindarinya. Seseorang berpikir sangat keras dan / atau mencoba banyak hal. Namun, berurusan dengan paralelisme sangat sulit dan sebagian besar (jika tidak semua) orang tidak akan dapat sepenuhnya menghindari masalah.

Beberapa metode yang lebih formal dapat bermanfaat jika Anda serius berurusan dengan masalah seperti ini. Metode paling praktis yang saya sadari adalah menggunakan pendekatan teori proses. Di sini Anda membuat model sistem Anda dalam beberapa bahasa proses (mis. CCS, CSP, ACP, mCRL2, LOTOS) dan menggunakan alat yang tersedia untuk (model-) memeriksa kebuntuan (dan mungkin beberapa properti lainnya juga). Contoh toolset untuk digunakan adalah FDR, mCRL2, CADP dan Uppaal. Beberapa jiwa pemberani bahkan mungkin membuktikan sistem mereka bebas dari kebuntuan dengan menggunakan metode simbolik murni (pembuktian teorema; cari Owicki-Gries).

Namun, metode formal ini biasanya memang memerlukan beberapa upaya (misalnya mempelajari dasar-dasar teori proses). Tapi saya kira itu hanyalah konsekuensi dari kenyataan bahwa masalah ini sulit.

mweerden
sumber
0

Kebuntuan adalah situasi yang terjadi ketika jumlah sumber daya yang tersedia lebih sedikit karena diminta oleh proses yang berbeda. Ini berarti bahwa ketika jumlah sumber daya yang tersedia menjadi kurang dari yang diminta oleh pengguna maka pada saat itu proses berjalan dalam kondisi menunggu. Beberapa kali menunggu meningkat lebih banyak dan tidak ada kesempatan untuk memeriksa masalah kekurangan sumber daya kemudian situasi ini dikenal sebagai jalan buntu. Sebenarnya, kebuntuan adalah masalah utama bagi kami dan itu terjadi hanya dalam sistem operasi multitasking .deadlock tidak dapat terjadi dalam sistem operasi penugasan tunggal karena semua sumber daya hadir hanya untuk tugas yang sedang berjalan ......

puja bharti
sumber
0

Di atas beberapa penjelasan bagus. Semoga ini juga berguna: https://ora-data.blogspot.in/2017/04/deadlock-in-oracle.html

Dalam database, ketika suatu sesi (misalnya ora) menginginkan sumber daya dipegang oleh sesi lain (misalnya data), tetapi sesi (data) itu juga menginginkan sumber daya yang dipegang oleh sesi pertama (ora). Mungkin ada lebih dari 2 sesi yang terlibat, tetapi idenya akan sama. Sebenarnya, kebuntuan mencegah beberapa transaksi terus bekerja. Sebagai contoh: Misalkan, ORA-DATA memegang kunci A dan meminta kunci B Dan SKU memegang kunci B dan meminta kunci A.

Terima kasih,

Sapna
sumber
0

Kebuntuan terjadi ketika utas sedang menunggu utas lainnya selesai dan sebaliknya.

Bagaimana cara menghindarinya?
- Hindari Kunci Bertumpuk
- Hindari Kunci Tidak Perlu
- Gunakan utas gabung ()

Bagaimana Anda mendeteksinya?
jalankan perintah ini di cmd:

jcmd $PID Thread.print

referensi : geeksforgeeks

Arun Raaj
sumber
0

Kebuntuan tidak terjadi begitu saja dengan kunci, meskipun itulah penyebab paling sering. Di C ++, Anda bisa membuat kebuntuan dengan dua utas dan tanpa kunci dengan hanya meminta setiap utas bergabung () pada objek std :: utas untuk yang lainnya.

Raghav Navada
sumber
0

Kontrol concurrency berbasis kunci

Menggunakan penguncian untuk mengontrol akses ke sumber daya bersama rentan terhadap kebuntuan, dan penjadwal transaksi sendiri tidak dapat mencegah kejadiannya.

Misalnya, sistem basis data relasional menggunakan berbagai kunci untuk menjamin properti ACID transaksi .

Apa pun sistem basis data relasional yang Anda gunakan, kunci akan selalu diperoleh saat memodifikasi (misalnya, UPDATEatau DELETE) catatan tabel tertentu. Tanpa mengunci baris yang dimodifikasi oleh transaksi yang sedang berjalan, Atomicity akan dikompromikan .

Apa itu jalan buntu

Seperti yang saya jelaskan dalam artikel ini , kebuntuan terjadi ketika dua transaksi bersamaan tidak dapat membuat kemajuan karena masing-masing menunggu yang lain untuk melepaskan kunci, seperti yang diilustrasikan dalam diagram berikut.

masukkan deskripsi gambar di sini

Karena kedua transaksi berada dalam fase akuisisi kunci, tidak ada yang melepaskan kunci sebelum memperoleh yang berikutnya.

Sembuh dari situasi jalan buntu

Jika Anda menggunakan algoritma Kontrol Konkurensi yang bergantung pada kunci, maka selalu ada risiko berjalan dalam situasi jalan buntu. Kebuntuan dapat terjadi di lingkungan konkurensi apa pun, tidak hanya dalam sistem basis data.

Misalnya, program multithreading dapat menemui jalan buntu jika dua atau lebih utas menunggu pada kunci yang sebelumnya diperoleh sehingga tidak ada utas yang dapat membuat kemajuan. Jika ini terjadi pada aplikasi Java, JVM tidak bisa memaksa Thread untuk menghentikan eksekusi dan melepaskan kunci-kuncinya.

Bahkan jika Threadkelas mengekspos suatu stopmetode, metode itu sudah tidak digunakan lagi sejak Java 1.1 karena dapat menyebabkan objek dibiarkan dalam keadaan tidak konsisten setelah thread dihentikan. Sebaliknya, Java mendefinisikan interruptmetode, yang bertindak sebagai petunjuk sebagai utas yang terputus dapat dengan mudah mengabaikan gangguan dan melanjutkan eksekusi.

Untuk alasan ini, aplikasi Java tidak dapat pulih dari situasi deadlock, dan merupakan tanggung jawab pengembang aplikasi untuk memesan permintaan akuisisi kunci sedemikian rupa sehingga deadlock tidak pernah terjadi.

Namun, sistem basis data tidak dapat memberlakukan perintah akuisisi kunci yang diberikan karena tidak mungkin untuk meramalkan kunci lain yang ingin diperoleh transaksi tertentu. Mempertahankan urutan kunci menjadi tanggung jawab lapisan akses data, dan database hanya dapat membantu memulihkan dari situasi deadlock.

Mesin basis data menjalankan proses terpisah yang memindai grafik konflik saat ini untuk siklus kunci-tunggu (yang disebabkan oleh deadlock). Ketika sebuah siklus terdeteksi, mesin basis data mengambil satu transaksi dan membatalkannya, menyebabkan kunci-nya dilepaskan, sehingga transaksi lainnya dapat membuat kemajuan.

Berbeda dengan JVM, transaksi basis data dirancang sebagai unit kerja atom. Oleh karena itu, rollback membuat database dalam keadaan konsisten.

Untuk detail lebih lanjut tentang topik ini, lihat artikel ini juga.

Vlad Mihalcea
sumber
-2

Mutex pada dasarnya adalah kunci, menyediakan akses yang dilindungi ke sumber daya bersama. Di Linux, tipe data thread mutex adalah pthread_mutex_t. Sebelum digunakan, inisialisasi.

Untuk mengakses sumber daya bersama, Anda harus mengunci mutex. Jika mutex sudah di kunci, panggilan akan memblokir utas sampai mutex dibuka. Setelah menyelesaikan kunjungan ke sumber daya bersama, Anda harus membuka kuncinya.

Secara keseluruhan, ada beberapa prinsip dasar yang tidak tertulis:

  • Dapatkan kunci sebelum menggunakan sumber daya bersama.

  • Memegang kunci sesingkat mungkin.

  • Lepaskan kunci jika utas mengembalikan kesalahan.

Marcus Thornton
sumber
3
Ini menjelaskan kunci, bukan jalan buntu.
Marquis of Lorne