LinkedBlockingQueue vs ConcurrentLinkedQueue

112

Pertanyaan saya berkaitan dengan pertanyaan yang diajukan sebelumnya. Dalam situasi di mana saya menggunakan antrean untuk komunikasi antara utas produsen dan konsumen, apakah orang biasanya merekomendasikan penggunaan LinkedBlockingQueueatau ConcurrentLinkedQueue?

Apa keuntungan / kerugian menggunakan salah satu dari yang lain?

Perbedaan utama yang dapat saya lihat dari perspektif API adalah bahwa a LinkedBlockingQueuedapat dibatasi secara opsional.

java multithreading data-structures concurrency queue Adamski
sumber

Jawaban:

110

Untuk utas produsen / konsumen, saya tidak yakin itu ConcurrentLinkedQueueadalah pilihan yang masuk akal - itu tidak diterapkan BlockingQueue, yang merupakan antarmuka dasar untuk antrian produsen / konsumen IMO. Anda harus menelepon poll(), menunggu sebentar jika Anda tidak menemukan apa pun, lalu melakukan polling lagi, dll. Menyebabkan penundaan saat item baru masuk, dan inefisiensi saat item kosong (karena tidak perlu bangun dari tidur) .

Dari dokumen untuk BlockingQueue:

BlockingQueue implementasi dirancang untuk digunakan terutama untuk antrian produsen-konsumen

Saya tahu itu tidak secara tegas mengatakan bahwa hanya antrian pemblokiran yang harus digunakan untuk antrian produsen-konsumen, tetapi meskipun demikian ...

Jon Skeet
sumber
4
Terima kasih Jon - saya tidak menyadarinya. Jadi di mana / mengapa Anda menggunakan ConcurrentLinkedQueue?
Adamski
27
Ketika Anda perlu mengakses antrian dari banyak utas, tetapi Anda tidak perlu "menunggu" di atasnya.
Jon Skeet
2
A ConcurrentLinkedQueuejuga berguna jika utas Anda memeriksa beberapa antrian. Misalnya, dalam server multi-tenant. Dengan asumsi untuk alasan isolasi Anda tidak menggunakan satu antrian pemblokiran dan diskriminator penyewa sebagai gantinya.
LateralFractal
kasus Anda hanya berlaku jika kita menggunakan antrian terbatas , dalam antrian tak terbatastake() dan put()hanya mengkonsumsi sumber daya tambahan (dalam sinkronisasi) daripada ConcurrentLinkedQueue . meskipun merupakan kasus untuk menggunakan antrean terbatas untuk skenario Produsen-konsumen
amarnath harish
@Adamski IMO, ConcurrentLinkedQueue hanyalah daftar tertaut untuk digunakan dalam lingkungan multi-utas. Analogi terbaik untuk ini adalah ConcurrentHashMap dan HashMap.
Nishit
69

Pertanyaan ini membutuhkan jawaban yang lebih baik.

Java ConcurrentLinkedQueuedidasarkan pada algoritme terkenal oleh Maged M. Michael dan Michael L. Scott untuk antrean bebas kunci yang tidak memblokir .

"Non-pemblokiran" sebagai istilah di sini untuk sumber daya yang diperebutkan (antrean kami) berarti bahwa apa pun yang dilakukan penjadwal platform, seperti menyela untaian, atau jika untaian yang dipermasalahkan terlalu lambat, untaian lain bersaing untuk sumber daya yang sama akan tetap bisa maju. Jika ada kunci yang terlibat, misalnya, utas yang menahan kunci bisa terputus dan semua utas yang menunggu kunci itu akan diblokir. Kunci intrinsik ( synchronizedkata kunci) di Java juga dapat mengakibatkan hukuman yang berat untuk kinerja - seperti saat penguncian yang biasterlibat dan Anda memang memiliki perselisihan, atau setelah VM memutuskan untuk "memekarkan" kunci setelah masa tenggang putaran dan memblokir utas yang bersaing ... itulah sebabnya dalam banyak konteks (skenario pertengkaran rendah / menengah), melakukan bandingkan-dan -set pada referensi atom bisa jauh lebih efisien dan inilah yang dilakukan oleh banyak struktur data non-pemblokiran.

Java ConcurrentLinkedQueuebukan hanya non-pemblokiran, tetapi juga memiliki properti luar biasa yang tidak bersaing dengan konsumen oleh produsen. Dalam skenario produsen / konsumen tunggal (SPSC), ini benar-benar berarti bahwa tidak akan ada perselisihan untuk dibicarakan. Dalam skenario banyak produsen / konsumen tunggal, konsumen tidak akan bersaing dengan produsen. Antrean ini memang memiliki perselisihan ketika beberapa produsen mencoba offer(), tetapi menurut definisi itu konkurensi. Ini pada dasarnya adalah tujuan umum dan antrian non-pemblokiran yang efisien.

Adapun itu bukan BlockingQueue, yah, memblokir utas untuk menunggu di antrian adalah cara yang sangat mengerikan untuk merancang sistem bersamaan. Jangan. Jika Anda tidak dapat menemukan cara menggunakan a ConcurrentLinkedQueuedalam skenario konsumen / produsen, beralih saja ke abstraksi tingkat yang lebih tinggi, seperti kerangka aktor yang baik.

Alexandru Nedelcu
sumber
8
Menurut paragraf terakhir Anda, mengapa Anda mengatakan bahwa menunggu dalam antrian adalah cara yang buruk untuk merancang sistem bersamaan? Jika kita memiliki grup utas dengan 10 utas yang memakan tugas dari antrean tugas, apa yang salah dengan pemblokiran saat antrean tugas memiliki kurang dari 10 tugas?
Pacerier
11
@AlexandruNedelcu Anda tidak dapat membuat pernyataan seperti "sangat mengerikan" di mana sangat sering kerangka aktor yang Anda katakan menggunakan threadpool yang dengan sendirinya Anda BlockingQueue . Jika Anda membutuhkan sistem yang sangat reaktif dan Anda tahu bagaimana menangani tekanan balik (sesuatu yang mengurangi antrian pemblokiran) daripada nonblocking jelas lebih unggul. Tapi .. sering kali memblokir IO dan memblokir antrian dapat melakukan nonblocking terutama jika Anda memiliki tugas yang berjalan lama yang terikat IO dan tidak dapat dibagi n 'ditaklukkan.
Adam Gent
1
@AdamGent - Framework aktor memang menerapkan kotak surat berdasarkan antrean pemblokiran, tetapi menurut saya itu bug, karena pemblokiran tidak bekerja di atas batas asinkron dan hanya berfungsi di demo. Bagi saya ini telah menjadi sumber frustrasi, karena misalnya gagasan Akka tentang menangani overflow adalah memblokir, bukannya menjatuhkan pesan, hingga versi 2.4, yang belum keluar. Yang mengatakan saya tidak percaya bahwa ada kasus penggunaan yang memblokir antrian bisa lebih baik. Anda juga menggabungkan dua hal yang tidak boleh digabungkan. Saya belum berbicara tentang pemblokiran I / O.
Alexandru Nedelcu
1
@AlexandruNedelcu sementara saya biasanya setuju dengan Anda tentang tekanan balik, saya belum melihat sistem "bebas kunci" dari atas ke bawah. Di suatu tempat dalam tumpukan teknologi apakah itu Node.js, Erlang, Golang, yang menggunakan semacam strategi menunggu apakah itu antrian pemblokiran (kunci) atau CAS yang memutar pemblokirannya dan beberapa kasus strategi kunci tradisional lebih cepat. Sangat sulit untuk tidak memiliki kunci karena konsistensi dan ini terutama penting dengan pemblokiran io dan penjadwal yang ~ Produser / Konsumen. ForkJoinPool bekerja dengan tugas-tugas yang berjalan singkat dan masih memiliki kunci pemintalan CAS.
Adam Gent
1
@AlexandruNedelcu Saya kira jika Anda dapat menunjukkan kepada saya bagaimana Anda dapat menggunakan ConcurrentLinkedQueue (yang tidak dibatasi btw maka argumen tekanan balik saya yang lemah) untuk pola Produsen / Konsumen yang merupakan pola yang diperlukan untuk penjadwal dan threadpooling, saya rasa saya akan menyerah dan mengakuinya BlockingQueue tidak boleh digunakan (dan Anda tidak dapat menipu dan mendelegasikan sesuatu yang lain melakukan penjadwalan yaitu akka karena itu pada gilirannya akan melakukan pemblokiran / menunggu karena itu adalah produsen / konsumen).
Adam Gent
33

LinkedBlockingQueuememblokir konsumen atau produsen ketika antrian kosong atau penuh dan benang konsumen / produsen masing-masing tertidur. Tetapi fitur pemblokiran ini memiliki biaya: setiap operasi put atau take dikunci antara produsen atau konsumen (jika banyak), jadi dalam skenario dengan banyak produsen / konsumen, operasinya mungkin lebih lambat.

ConcurrentLinkedQueuetidak menggunakan kunci, tetapi CAS , pada operasi put / take-nya berpotensi mengurangi perselisihan dengan banyak utas produsen dan konsumen. Tetapi menjadi struktur data "menunggu bebas", ConcurrentLinkedQueuetidak akan memblokir ketika kosong, yang berarti bahwa konsumen perlu berurusan dengan nilai-nilai yang take()kembali nulldengan "menunggu sibuk", misalnya, dengan benang konsumen memakan CPU.

Jadi mana yang "lebih baik" tergantung pada jumlah benang konsumen, pada tingkat yang mereka konsumsi / produksi, dll. Diperlukan tolok ukur untuk setiap skenario.

Salah satu kasus penggunaan di mana ConcurrentLinkedQueuejelas lebih baik adalah ketika produsen pertama kali memproduksi sesuatu dan menyelesaikan pekerjaan mereka dengan menempatkan pekerjaan dalam antrian dan hanya setelah konsumen mulai mengkonsumsi, mengetahui bahwa mereka akan selesai ketika antrian kosong. (di sini tidak ada konkurensi antara produsen-konsumen tetapi hanya antara produsen-produsen dan konsumen-konsumen)

dcernahoschi.dll
sumber
satu keraguan di sini. Seperti yang Anda sebutkan, konsumen menunggu ketika antrian kosong..berapa lama menunggu. Siapa yang akan memberi tahu untuk tidak menunggu?
Brinal
@brindal Satu-satunya cara untuk menunggu, yang saya tahu, adalah dalam satu lingkaran. Yang merupakan masalah signifikan yang belum mendapat banyak perhatian dalam jawaban di sini. Hanya menjalankan satu putaran menunggu data menggunakan banyak waktu prosesor. Anda akan mengetahuinya saat penggemar Anda mulai bersemangat. Satu-satunya solusi adalah dengan membuat tidur dalam lingkaran. Jadi ini masalah dalam sistem dengan aliran data yang tidak konsisten. Mungkin saya salah paham dengan jawaban AlexandruNedelcu, tetapi sistem operasi itu sendiri adalah sistem konkuren, yang akan sangat tidak efisien jika penuh dengan loop acara non-pemblokiran.
orodbhen
oke, tetapi jika unbounded blockingqueuedigunakan apakah akan lebih baik daripada berbasis CAS secara bersamaanConcurrentLinkedQueue
amarnath harish
@orodbhen Menidurkan juga tidak akan menghilangkan pemborosan. OS harus melakukan banyak pekerjaan untuk mengeluarkan thread dari mode sleep dan menjadwalkan dan menjalankannya. Jika pesan belum tersedia, pekerjaan yang dilakukan oleh OS Anda akan sia-sia. Saya akan merekomendasikan lebih baik menggunakan BlockingQueue, karena ini dirancang khusus untuk masalah produsen-konsumen.
Nishit
sebenarnya saya sangat tertarik dengan bagian "tingkat konsumsi / produksi", jadi mana yang lebih baik jika tarif naik?
workplaylifecycle
0

Solusi lain (yang tidak berskala baik) adalah saluran pertemuan: java.util.concurrent SynchronousQueue

Ovidiu Lupas
sumber
0

Jika antrian Anda tidak dapat diperluas dan hanya berisi satu thread produsen / konsumen. Anda dapat menggunakan antrian tanpa kunci (Anda tidak perlu mengunci akses data).

Rahul
sumber