Pada bab sebelumnya, kami menjelaskan antrian pemblokiran yang diimplementasikan di ArrayBlockingQueue, menggunakan Formulir Array.
Panjang array harus ditentukan saat membuat. Jika panjang array kecil, antrian arrayblockingqueue akan dengan mudah diblokir. Jika panjang array besar, itu akan dengan mudah menyia -nyiakan memori.
Struktur data antrian secara alami cocok untuk bentuk daftar tertaut, dan LinkedBlockingQueue adalah antrian pemblokiran yang diimplementasikan menggunakan daftar tertaut.
1. Implementasi Daftar Tertaut
1.1 Node Internal Class
/ *** Node daftar tertaut juga digunakan untuk mengimplementasikan daftar satu arah yang ditautkan*/ simpul kelas statis <E> {e item; // Arahkan ke simpul berikutnya dari node daftar tertaut <e> berikutnya; Node (e x) {item = x; }}Ada variabel E yang menyimpan data, dan ada variabel referensi berikutnya yang menunjuk ke simpul berikutnya. Ini dapat mengimplementasikan daftar satu arah paling sederhana.
1.2 Cara Menerapkan Daftar Tautan
/ *** Poin berikutnya ke kepala antrian, dan simpul ini tidak menyimpan data*/ node transien <e> kepala; / *** Node ekor antrian*/ node transien pribadi <e> Terakhir;
Untuk mengimplementasikan daftar yang ditautkan, harus ada dua variabel, satu mewakili kepala daftar yang ditautkan dan yang lainnya mewakili yang terakhir dari daftar tertaut. Kedua kepala dan terakhir diinisialisasi ketika objek LinkedBlockingQueue dibuat.
terakhir = head = node baru <E> (null);
Perhatikan bahwa trik kecil digunakan di sini. Node kepala daftar tertaut tidak menyimpan data. Node berikutnya menunjuk untuk benar -benar menyimpan data pertama dalam daftar tertaut. Yang terakhir di akhir daftar tertaut memang menyimpan data terakhir dalam daftar tertaut.
1.3 Sisipkan dan Hapus Node
/ *** Masukkan simpul ke ekor antrian*/ private void enqueue (node <E> node) {// tegaskan putlock.isheldbyCurrentThread (); // Utas saat ini harus telah memperoleh kunci putlock // point referensi berikutnya dari simpul ekor antrian asli ke simpul simpul baru, dan kemudian atur simpul simpul ke simpul ekor dari antrian terakhir // Ini mewujudkan memasukkan simpul ke ekor antrian terakhir = last.next = node; }Sangat mudah untuk memasukkan node di akhir daftar yang ditautkan. Arahkan simpul berikutnya dari antrian asli terakhir ke simpul node baru, dan kemudian tetapkan simpul node baru ke simpul terakhir di ujung antrian. Ini memungkinkan memasukkan node baru.
// Lepaskan simpul kepala antrian dan kembalikan data node yang dihapus pribadi e dequeue () {// menegaskan takelock.isheldbyCurrentThread (); // Utas saat ini pasti telah memperoleh kunci Takelock // Assert head.item == null; Node <e> h = head; // Data elemen pertama dalam antrian disimpan di simpul node pertama <E> pertama = h.next; h.next = h; // BANTUAN GC // Mengatur Nilai Kepala Baru setara dengan menghapus node pertama. Karena simpul kepala itu sendiri tidak menyimpan head data = pertama; // Data header antrian e x = first.item; // Hapus data asli terlebih dahulu.item = null; mengembalikan x; }Perhatikan bahwa kepala bukan header, titik berikutnya ke header, jadi sangat mudah untuk menghapus header, yaitu menetapkan head.next untuk kepala dan kemudian mengembalikan data dari node head.next asli.
Saat menghapus, perhatikan situasi di mana daftar yang ditautkan kosong. Nilai head.next ditambahkan menggunakan metode enqueue. Ketika head.next == terakhir, itu berarti bahwa elemen terakhir telah dihapus. Ketika head.next == null, itu tidak dapat dihapus karena daftar yang ditautkan sudah kosong. Tidak ada penilaian di sini karena penghakiman telah dibuat di tempat di mana metode dequeue dipanggil.
2. Kunci Sinkron Reentrantlock dan Kondisi
Karena antrian pemblokiran harus diblokir dan ditunggu ketika antrian kosong dan antrian penuh, maka dua kondisi secara alami diperlukan. Untuk memastikan keamanan konkurensi multi-threaded, diperlukan kunci sinkronisasi. Ini telah dikatakan di ArrayBlockingQueue.
Di sini kita akan berbicara tentang berbagai hal tentang LinkedBlockingQueue.
/ ** Kunci eksklusif, digunakan untuk menangani masalah konkurensi memasukkan operasi antrian, yaitu, menempatkan dan menawarkan operasi*/ final swasta reentrantlock putlock = baru reentrantlock (); / ** Kondisi kondisi bahwa antrian tidak puas dengan, itu dihasilkan oleh putlock lock*/ kondisi akhir pribadi itfull = putlock.newcondition (); / ** Kunci eksklusif, digunakan untuk menangani masalah konkurensi menghapus operasi kepala antrian, yaitu operasi dan jajak pendapat*/ reentrantlock final swasta Takelock = baru reentrantlock (); / ** Kondisi kondisi bahwa antrian tidak kosong, menggunakan kondisi akhir pribadi yang dihasilkan oleh Takelock Lock*/ Private Final Condition notempty = Takelock.NewCondition ();
2.1 Putlock dan Takelock
Kami menemukan dua kunci yang digunakan:
Menurut pernyataan di atas, mungkin ada operasi untuk memasukkan dan menghapus elemen pada saat yang sama, jadi apakah tidak akan ada masalah?
Mari kita analisis secara rinci. Untuk antrian, operasi dibagi menjadi tiga jenis:
Oleh karena itu, gunakan kunci putlock untuk menjaga variabel terakhir aman, dan gunakan kunci takelock untuk menjaga variabel kepala tetap aman.
Untuk semua variabel penghitungan yang terlibat dalam jumlah elemen dalam antrian, Atomicinteger digunakan untuk memastikan masalah keamanan konkurensi.
/ ** Jumlah elemen dalam antrian, gunakan variabel AtomicInteger di sini untuk memastikan masalah keamanan konkurensi*/ final atomicinteger count = atomicinteger baru ();
2.2 Kotak dan tidak ada
2.3 Proses Kontrol
Saat memasukkan elemen:
Saat menghapus elemen:
Perhatikan juga bahwa sinyal dan metode kondisi kondisi harus dipanggil ketika kunci diperoleh. Oleh karena itu, ada sinyal tidak ada metode dan tidak ada metode:
/*** Bangunkan utas menunggu di bawah kondisi tidak keras kepala, yaitu, ketika menghapus header antrian, utas yang ditemukan kosong dan dipaksa untuk menunggu. * Perhatikan bahwa karena untuk memanggil metode sinyal kondisi, kunci yang sesuai harus diperoleh, metode takelock.lock () disebut di sini. * Ketika suatu elemen dimasukkan ke dalam antrian (mis. Masukkan atau tawarkan operasi), antrian jelas tidak kosong, dan metode ini akan dipanggil. */ private void SignalNotEmpty () {final reentrantlock takelock = this.takelock; takelock.lock (); coba {notempty.signal (); } akhirnya {takelock.unlock (); }} /*** Bangun utas menunggu di bawah kondisi yang mencolok, yaitu, ketika elemen ditambahkan di akhir antrian, utas yang penuh dan dipaksa untuk menunggu. * Perhatikan bahwa karena untuk memanggil metode sinyal kondisi, kunci yang sesuai harus diperoleh, sehingga metode putlock.lock () disebut di sini* ketika elemen (mis. Operasi atau operasi jajak pendapat) dihapus dalam antrian, antrian pasti tidak akan puas dan akan memanggil metode ini. */ private void sinyalNotFull () {final reentrantlock putlock = this.putlock; putlock.lock (); coba {notfull.signal (); } akhirnya {putlock.unlock (); }}3. Metode Sisipkan Elemen
public void put (e e) melempar interruptedException {if (e == null) melempar nullpointerException baru (); // Catat jumlah elemen sebelum operasi penyisipan int c = -1; // Buat simpul node baru <E> node = node baru <E> (e); final reentrantlock putlock = this.putlock; final atomicinteger count = this.count; putlock.lockinterricture (); Coba {// Tunjukkan bahwa antrian penuh, maka Anda perlu memanggil metode yang mencolok untuk membuat utas saat ini menunggu sementara (count.get () == kapasitas) {notfull.aWait (); } // Masukkan elemen baru enqueue (node); // Tambahkan 1 ke jumlah elemen dalam antrian saat ini dan kembalikan jumlah elemen sebelum menambahkan 1. C = count.getAndincrement (); // c + 1 <kapasitas berarti bahwa antrian tidak penuh, dan utas yang mungkin menunggu operasi penyisipan dibangunkan jika (c + 1 <kapasitas) tigifull.signal (); } akhirnya {putlock.unlock (); } // c == 0 berarti antrian kosong sebelum dimasukkan. Ketika antrian kosong ke elemen yang ditempatkan, // Bangun utas menunggu penghapusan // Cegah akuisisi kunci Takelock yang sering, konsumsi kinerja jika (c == 0) SignalNotEmpty (); }Mengambil metode put sebagai contoh, proses umum sama dengan yang kami perkenalkan sebelumnya. Ini kode yang sangat aneh. Ketika elemen dimasukkan, jika Anda menemukan bahwa antriannya tidak penuh, maka hubungi itull.signal () untuk membangunkan utas menunggu penyisipan.
Semua orang sangat bingung. Secara umum, metode ini harus ditempatkan di elemen hapus (mengambil metode seri), karena ketika kita menghapus elemen, antrian harus di bawah penuh, kemudian panggil metode tigifull.signal () untuk membangunkan utas yang menunggu untuk dimasukkan.
Ini terutama dilakukan di sini karena ketika memanggil metode sinyal, kunci yang sesuai harus diperoleh terlebih dahulu. Kunci yang digunakan dalam metode Take Series adalah Takelock. Jika Anda ingin memanggil metode itull.signal (), Anda harus terlebih dahulu mendapatkan kunci putlock. Ini akan menyebabkan kinerja berkurang, sehingga metode lain digunakan.
4. Hapus elemen header antrian
publik e take () melempar interruptedException {e x; int c = -1; final atomicinteger count = this.count; final reentrantlock takelock = this.takelock; takelock.lockinterricture (); Coba {// berarti antriannya kosong, maka Anda perlu memanggil metode notempty.aWait untuk membuat utas saat ini menunggu sementara (count.get () == 0) {notempty.aWait (); } // hapus elemen header antrian dan kembalikan x = dequeue (); // Kembalikan jumlah antrian saat ini, dan kemudian kurangi jumlah antrian dengan satu c = count.getAndDecrement (); // C> 1 berarti antrian tidak kosong, sehingga membangunkan utas yang mungkin menunggu operasi hapus jika (c> 1) notempty.signal (); } akhirnya {takelock.unlock (); } /*** C == Kapasitas berarti bahwa antriannya penuh sebelum operasi penghapusan. * Bangunkan utas yang menunggu untuk dimasukkan hanya ketika suatu elemen dihapus dari antrian penuh* mencegah akuisisi kunci putlock yang sering, mengkonsumsi kinerja*/ if (c == kapasitas) sinyalNotFull (); mengembalikan x; }Mengapa metode notempty.signal () disebut, bandingkan penjelasan kami dalam metode insert elemen.
5. Lihat elemen header antrian
// Lihat elemen header antrian publik e peek () {// antriannya kosong, return null if (count.get () == 0) return null; final reentrantlock takelock = this.takelock; takelock.lock (); Coba {// Dapatkan simpul header antrian pertama simpul <e> pertama = head.next; // pertama == null berarti bahwa antrian kosong, kembalikan null if (first == null) return null; else // kembalikan elemen header antrian kembali terlebih dahulu.item; } akhirnya {takelock.unlock (); }}Lihat elemen header antrian, yang melibatkan simpul kepala, jadi Takelock Lock harus digunakan.
Vi. Metode penting lainnya
6.1 Hapus metode (objek o)
// Hapus elemen yang ditentukan dari antrian o public boolean hapus (objek o) {if (o == null) return false; // Karena tidak menghapus elemen header daftar, dua variabel kepala dan terakhir terlibat, // putlock dan takelock harus dikunci sepenuhnya (); Coba {// lintasi seluruh antrian, P mewakili simpul saat ini, dan jejak mewakili simpul sebelumnya dari simpul saat ini // karena ini adalah daftar tertaut satu arah, dua node perlu direkam untuk (node <e> trail = head, p = trail.next; p! = null; trail = p, p, p.next) {// p. (o.equals (p.item)) {unlink (p, trail); Kembali Benar; }} return false; } akhirnya {fullunlock (); }}Hapus elemen yang ditentukan dari daftar. Karena elemen yang dihapus tidak harus ada di kepala daftar, mungkin ada dua variabel kepala dan terakhir, jadi Anda harus menggunakan kunci putlock dan takelock secara bersamaan. Karena ini adalah daftar tertaut satu arah, jejak variabel tambahan diperlukan untuk merekam node sebelumnya sehingga simpul P saat ini dapat dihapus.
6.2 Metode BUPA (NODE <E> P, Node <E> Trail)
// hapus simpul saat ini p, dan jejak mewakili simpul P void unlink sebelumnya (node <E> p, node <E> jejak) {// Atur data node saat ini ke null p.item = null; // ini menghapus node p trail.next = p.next; // Jika simpul p adalah yang terakhir dari antrian dan dihapus, lalu atur jejak ke yang terakhir jika (terakhir == p) terakhir = jejak; // Kurangi jumlah elemen dengan satu, jika antrian asli penuh, maka panggil metode tigifull.signal () // pada kenyataannya, ini dipanggil langsung tanpa penilaian, karena kunci putlock harus diperoleh di sini jika (count.getAndEcrement () == kapasitas) tokoh.signal (); }Untuk menghapus simpul P dalam daftar tertaut, Anda hanya perlu mengarahkan jejak simpul P sebelumnya ke simpul berikutnya di sebelah simpul p.
Di atas adalah semua konten artikel ini. Saya berharap ini akan membantu untuk pembelajaran semua orang dan saya harap semua orang akan lebih mendukung wulin.com.