Saya mengerti apa itu livelock, tapi saya bertanya-tanya apakah ada yang punya contoh berbasis kode yang bagus? Dan berdasarkan kode, saya tidak bermaksud "dua orang mencoba untuk melewati satu sama lain di koridor". Jika saya membacanya lagi, saya akan kehilangan makan siang.
concurrency
livelock
Alex Miller
sumber
sumber
Jawaban:
Berikut adalah contoh livelock Jawa yang sangat sederhana di mana suami dan istri mencoba makan sup, tetapi hanya memiliki satu sendok di antara mereka. Setiap pasangan terlalu sopan, dan akan melewati sendok jika yang lain belum makan.
sumber
getOwner
metode harus disinkronkan juga? Dari Java Efektif " sinkronisasi tidak berpengaruh kecuali baca dan tulis ".Thread.join()
daripadaThread.sleep()
, karena dia ingin menunggu pasangannya makan?getOwner
Metode harus disinkronkan karena bahkan jikasetOwner
disinkronkan, ini tidak menjamin benang menggunakangetOwner
(atau mengakses lapanganowner
langsung) akan melihat perubahan yang dilakukan oleh thread lain melakukansetOwner
. Vid ini menjelaskan hal ini dengan sangat hati-hati: youtube.com/watch?v=WTVooKLLVT8synchronized
kata kunci untuksetOwner
metode, karena membaca dan menulis adalah tindakan atom untuk variabel referensi.Selain komentar Flippant, salah satu contoh yang diketahui muncul adalah dalam kode yang mencoba mendeteksi dan menangani situasi deadlock. Jika dua utas mendeteksi kebuntuan, dan mencoba untuk "melangkah ke samping" untuk satu sama lain, tanpa peduli mereka akan terjebak dalam lingkaran selalu "melangkah ke samping" dan tidak pernah berhasil bergerak maju.
"Minggir" Maksudku, mereka akan melepaskan kunci dan mencoba membiarkan yang lain mendapatkannya. Kita mungkin membayangkan situasi dengan dua utas melakukan ini (kodesemu):
Di samping kondisi balapan, yang kita miliki di sini adalah situasi di mana kedua utas, jika mereka masuk pada saat yang sama, akan berakhir berjalan di loop dalam tanpa melanjutkan. Jelas ini adalah contoh yang disederhanakan. Sebuah perbaikan naif adalah dengan menempatkan semacam keacakan dalam jumlah waktu thread akan menunggu.
Perbaikan yang tepat adalah untuk selalu menghormati hirarki kunci . Pilih pesanan di mana Anda memperoleh kunci dan menaatinya. Misalnya jika kedua utas selalu mendapatkan kunci1 sebelum kunci2, maka tidak ada kemungkinan kebuntuan.
sumber
Karena tidak ada jawaban yang ditandai sebagai jawaban yang diterima, saya telah berupaya membuat contoh kunci langsung;
Program asli ditulis oleh saya pada bulan April 2012 untuk mempelajari berbagai konsep multithreading. Kali ini saya telah memodifikasinya untuk membuat jalan buntu, kondisi balapan, livelock dll.
Jadi mari kita memahami pernyataan masalah terlebih dahulu;
Masalah Pembuat Cookie
Ada beberapa wadah bahan: ChocoPowederContainer , WheatPowderContainer .CookieMaker mengambil sejumlah bubuk dari wadah bahan untuk membuat kue . Jika pembuat kue menemukan wadah kosong, ia memeriksa wadah lain untuk menghemat waktu. Dan menunggu sampai Filler mengisi wadah yang diperlukan. Ada Pengisi yang memeriksa wadah pada interval reguler dan mengisi jumlah tertentu jika wadah membutuhkannya.
Silakan periksa kode lengkap di github ;
Biarkan saya menjelaskan implementasi Anda secara singkat.
Mari kita lihat kodenya:
CookieMaker.java
IngredientContainer.java
Semuanya berjalan dengan baik sampai Filler mengisi wadah. Tetapi jika saya lupa untuk memulai pengisi, atau pengisi pergi cuti yang tak terduga, sub-utas terus mengubah negara mereka untuk memungkinkan pembuat lain untuk pergi dan memeriksa wadah.
Saya juga telah membuat daemon ThreadTracer yang terus memantau status utas dan kebuntuan. Ini keluaran dari konsol;
Anda akan melihat bahwa sub-utas dan mengubah negara mereka dan menunggu.
sumber
Contoh nyata (walaupun tanpa kode persis) adalah dua proses yang saling bersaing mengunci secara langsung dalam upaya untuk memperbaiki kebuntuan SQL server, dengan setiap proses menggunakan algoritma menunggu-coba yang sama untuk mencoba kembali. Meskipun ini adalah keberuntungan dari pengaturan waktu, saya telah melihat ini terjadi pada mesin yang terpisah dengan karakteristik kinerja yang serupa dalam menanggapi pesan yang ditambahkan ke topik EMS (misalnya menyimpan pembaruan grafik objek tunggal lebih dari sekali), dan tidak dapat mengontrol urutan kunci.
Solusi yang baik dalam hal ini adalah memiliki konsumen yang bersaing (mencegah pemrosesan duplikat setinggi mungkin dalam rantai dengan mempartisi pekerjaan pada objek yang tidak terkait).
Solusi yang kurang diinginkan (ok, hack-kotor) adalah untuk memecah waktu nasib buruk (jenis perbedaan kekuatan dalam pemrosesan) di muka atau memecahnya setelah kebuntuan dengan menggunakan algoritma yang berbeda atau beberapa elemen keacakan. Ini masih bisa memiliki masalah karena kemungkinan urutan pengambilannya "lengket" untuk setiap proses, dan ini membutuhkan waktu minimum tertentu yang tidak diperhitungkan dalam menunggu-coba lagi.
Namun solusi lain (setidaknya untuk SQL Server) adalah mencoba tingkat isolasi yang berbeda (misalnya snapshot).
sumber
Saya membuat kode contoh 2 orang yang lewat di koridor. Kedua utas akan saling menghindari segera setelah mereka menyadari arah mereka sama.
sumber
C # versi kode jelbourn:
sumber
Salah satu contoh di sini mungkin menggunakan tryLock berjangka waktu untuk mendapatkan lebih dari satu kunci dan jika Anda tidak dapat memperoleh semuanya, mundur dan coba lagi.
Saya bisa membayangkan kode seperti itu akan bermasalah karena Anda memiliki banyak utas bertabrakan dan menunggu untuk mendapatkan satu set kunci. Tapi saya tidak yakin ini sangat menarik bagi saya sebagai contoh sederhana.
sumber
tryLockAll()
dengan kunci dalamlocks
urutan yang sama, tidak ada livelock.Versi python dari kode jelbourn:
sumber
Saya memodifikasi jawaban @jelbourn. Ketika salah satu dari mereka memperhatikan bahwa yang lain lapar, dia harus melepaskan sendok dan menunggu pemberitahuan lainnya, sehingga livelock terjadi.
sumber
sumber