Pada bab sebelumnya, kami memperkenalkan blocking queue blockingqueue. Di bawah ini kami memperkenalkan arrayblockingqueue kelas implementasi yang umum digunakan.
1. Gunakan array untuk mengimplementasikan antrian
Karena persyaratan khusus dari struktur data antrian, secara alami cocok untuk diimplementasikan dalam bentuk daftar yang ditautkan. Dua variabel digunakan untuk merekam header dan ujung daftar yang ditautkan masing -masing. Saat menghapus atau memasukkan antrian, cukup ubah header atau akhir dari daftar yang ditautkan. Selain itu, daftar tertaut ditautkan dengan cara referensi, sehingga kapasitasnya hampir tidak terbatas.
Jadi cara menggunakan array untuk mengimplementasikan antrian, kita membutuhkan empat variabel: array objek [] untuk menyimpan elemen dalam antrian, headIndex dan tailindex merekam kepala dan ekor antrian, dan menghitung merekam jumlah antrian.
Cara yang sangat pintar digunakan di sini. Kita tahu bahwa ketika suatu elemen dimasukkan ke dalam antrian, ia mengambil posisi dalam array. Ketika suatu elemen dihapus, posisi array sebenarnya gratis, menunjukkan bahwa elemen baru dapat dimasukkan dalam posisi ini.
Jadi sebelum kita memasukkan elemen baru, kita harus memeriksa apakah antriannya penuh, dan sebelum kita menghapus elemen, kita harus memeriksa apakah antriannya kosong.
2. Variabel anggota penting di arrayblockingqueue
/ ** Simpan elemen dalam item antrian*/ objek akhir []; / ** Posisi kepala antrian*/ int TakeIndex; / ** posisi ekor antrian*/ int putindex; / ** Jumlah elemen dalam jumlah antrian saat ini*/ int; / ** Digunakan untuk memastikan keamanan variabel bersama multi-threaded*/ kunci reentrantlock terakhir; / ** Ketika antrian kosong, metode tunggu dari Notempty akan dipanggil untuk membuat utas saat ini menunggu*/ Kondisi akhir pribadi Notempty; / ** Ketika antrian penuh, metode tunggu titchfull akan dipanggil, menyebabkan utas saat ini menunggu*/ kondisi akhir pribadi yang terkenal;
Ada lebih banyak variabel kunci, notempty, dan mencolok untuk mengimplementasikan keselamatan multi-utas dan kondisi tunggu utas. Bagaimana mereka beroperasi?
2.1 Peran kunci
Karena ArrayBlockingQueUe beroperasi di bawah beberapa utas, ketika memodifikasi variabel anggota seperti item, TakeIndex, PutIndex dan Count, masalah keselamatan multi-threaded harus dipertimbangkan. Oleh karena itu, kunci kunci eksklusif digunakan di sini untuk memastikan keamanan operasi bersamaan.
2.2 Peran Notempty dan Mothfull
Karena pemblokiran antrian harus diimplementasikan, ketika antrian kosong atau antrian penuh, antrian yang dibaca atau dimasukkan harus menunggu. Jadi kami memikirkan objek kondisi di bawah kerangka kerja konkurensi dan menggunakannya untuk mengendalikannya.
Di AQS, kami memperkenalkan peran kelas ini:
3. Tambahkan metode elemen
3.1 Tambahkan (e e) dan tawarkan (e e) Metode:
// Panggil metode di kelas induk AbstractQueue. public boolean add (e e) {// mengimplementasikan jika (tawaran (e)) return true; lain melempar IllegalStateException baru ("Antrian penuh"); } // Tambahkan elemen baru ke akhir antrian. Return true berarti penambahan berhasil, salah berarti penambahan gagal, dan tidak ada pengecualian yang dilemparkan penawaran boolean publik (e e) {checknotnull (e); final reentrantlock lock = this.lock; // Gunakan kunci untuk memastikan bahwa modifikasi multi-threaded atribut anggota lock.lock (); Coba {// antriannya penuh, dan penambahan elemen gagal, mengembalikan false. if (count == item.length) return false; else {// panggil metode enqueue untuk memasukkan elemen ke dalam antrian enqueue (e); Kembali Benar; }} akhirnya {lock.unlock (); }}Metode Tambah diimplementasikan dengan memanggil metode penawaran. Dalam metode penawaran, perlu untuk terlebih dahulu menentukan apakah antriannya penuh. Jika penuh, itu akan langsung mengembalikan False tanpa memblokir utas saat ini. Jika Anda tidak puas, hubungi metode enqueue untuk memasukkan elemen ke dalam antrian.
Catatan: Menggunakan lock.lock () di sini memastikan bahwa hanya satu variabel anggota Modifys Thread secara bersamaan untuk mencegah masalah operasi bersamaan. Meskipun juga akan memblokir utas saat ini, ini bukan penantian bersyarat, itu hanya karena kunci dipegang oleh utas lain, dan waktu operasi metode di arrayblockingqueue tidak lama, yang setara dengan tidak menghalangi utas.
3.2 Put Metode
// Tambahkan elemen baru ke ujung antrian. Jika antrian penuh, utas saat ini akan menunggu. Respons terhadap interupsi pengecualian public void put (e e) melempar interruptedException {checknotnull (e); final reentrantlock lock = this.lock; // Gunakan kunci untuk memastikan bahwa multi-threads memodifikasi keamanan atribut anggota lock.lockinterruptly (); Coba {// Jika antrian penuh, panggil metode tiThfull.AWAIT () untuk membiarkan utas saat ini menunggu sampai antrian tidak penuh sementara (count == items.length) itfull.Await (); // Panggil metode enqueue untuk memasukkan elemen ke dalam antrian enqueue (e); } akhirnya {lock.unlock (); }}Proses umum dari metode penawaran sama dengan metode penawaran. Namun, ketika antrian penuh, metode yang mencolok. Ketika antrian tidak puas, utas menunggu akan dibangunkan.
3.3 Penawaran (E E, Timeout Long, TimeUnit Unit) Metode
/*** Tambahkan elemen baru ke akhir antrian. Jika tidak ada ruang yang tersedia dalam antrian, utas saat ini akan menunggu. * Jika waktu tunggu melebihi batas waktu, maka false dikembalikan, menunjukkan bahwa penambahan gagal*/ penawaran boolean publik (e e, waktu tunggu lama, unit timeunit) melempar interruptedException {checknotnull (e); // Hitung nilai waktu dari total nano penantian maksimum nano long nanos = unit.tonanos (timeout); final reentrantlock lock = this.lock; // Gunakan kunci untuk memastikan bahwa modifikasi multi-thread atribut anggota lock.lockinterruptible (); Coba {// antriannya penuh sementara (count == items.length) {// nanos <= 0 berarti waktu tunggu maksimum telah tiba, jadi tidak perlu menunggu lebih lama. Return False, menunjukkan bahwa penambahan gagal. if (nanos <= 0) mengembalikan false; // Panggil metode yang mencolok. // Jika terbangun di muka, maka waktu yang tersisa dikembalikan nanos = khotbah.Awaitnanos (nanos); } // Panggil metode enqueue untuk memasukkan elemen ke dalam antrian enqueue (e); Kembali Benar; } akhirnya {lock.unlock (); }}Aliran umum metode put adalah sama dengan metode put, itu hanya memanggil metode yang mencolok.
4. Hapus metode elemen
4.1 Lepaskan () dan polling () Metode:
// Panggil metode di kelas induk AbstractQueue. publik e hapus () {// implementasi dengan memanggil jajak pendapat e x = poll (); if (x! = null) mengembalikan x; lain melempar nosuchelementException baru (); } // Hapus elemen pertama dari antrian (mis. Header antrian) dan kembalikan. Jika antriannya kosong, itu tidak melempar pengecualian, tetapi kembali nol. jajak pendapat publik () {final reentrantlock lock = this.lock; // Gunakan kunci untuk memastikan bahwa modifikasi multi-threaded atribut anggota lock.lock (); Coba {// if count == 0 dan daftarnya kosong, kembalikan nol. Kalau tidak, hubungi metode Dequeue untuk mengembalikan elemen header daftar (Count == 0)? null: dequeue (); } akhirnya {lock.unlock (); }}Metode hapus diimplementasikan dengan memanggil metode jajak pendapat (). Dalam metode jajak pendapat (), jika daftarnya kosong, ia mengembalikan nol, jika tidak, metode Dequeue dipanggil untuk mengembalikan elemen header daftar.
4.2 Take () Metode
/*** Kembalikan dan hapus elemen pertama antrian. Jika antrian kosong, utas depan akan menunggu. Pengecualian Interupsi Respons*/ Public e Take () melempar InterruptedException {final reentrantlock lock = this.lock; // Gunakan kunci untuk memastikan bahwa multi-threads memodifikasi keamanan atribut anggota lock.lockinterruptly (); Coba {// Jika antriannya kosong, hubungi metode notempty.aWait () untuk membiarkan utas saat ini menunggu. // Sampai utas lain memasukkan elemen ke dalam antrian, utas akan dibangunkan. while (count == 0) notempty.aWait (); // Panggil metode Dequeue untuk mengembalikan daftar header elemen header return dequeue (); } akhirnya {lock.unlock (); }}Ketika metode ambil () kosong, utas saat ini harus menunggu sampai utas lain memasukkan elemen baru ke dalam antrian, dan utas akan dibangunkan.
4.3 Metode Poll (Timeout Long, TimeUnit
/*** Kembalikan dan hapus elemen pertama antrian. Jika antrian kosong, utas depan akan menunggu. * Jika waktu tunggu melebihi batas waktu, maka false dikembalikan untuk menunjukkan bahwa elemen gagal*/ jajak pendapat publik (waktu lama, unit waktu) melempar interruptedException {// Hitung nilai waktu tunggu maksimum dalam total nano nanos long nanos = unit.tonanos (timeout); final reentrantlock lock = this.lock; // Gunakan kunci untuk memastikan bahwa modifikasi multi-threaded dari atribut anggota lock.lockinterruptible (); Coba {// antriannya kosong sementara (hitung == 0) {// nanos <= 0 berarti bahwa waktu tunggu maksimum telah tiba, jadi tidak perlu menunggu lagi, kembalikan nol. if (nanos <= 0) return null; // Hubungi metode notempty.awaitnanos (nanos) untuk membuat utas jadwal menunggu dan mengatur waktu batas waktu. nanos = notempty.aWaitnanos (nanos); } // Panggil metode Dequeue untuk mengembalikan elemen header daftar return dequeue (); } akhirnya {lock.unlock (); }}Sama seperti proses metode take (), itu hanya disebut metode Audiitnanos (Nanos) untuk membuat utas saat ini menunggu dan mengatur waktu tunggu.
5. Metode untuk melihat elemen
Metode 5.1 Element () dan Peek ()
// Panggil metode di kelas induk AbstractQueue. elemen e public () {e x = peek (); if (x! = null) mengembalikan x; lain melempar nosuchelementException baru (); } // Lihat elemen header antrian publik e peek () {final reentrantlock lock = this.lock; // Gunakan kunci untuk memastikan bahwa modifikasi multi-threaded atribut anggota lock.lock (); coba {// kembalikan elemen dari header antrian saat ini, return itemat (TakeIndex); // null saat antrian kosong} akhirnya {lock.unlock (); }}Vi. Metode penting lainnya
6.1 metode enqueue dan dequeue
// Masukkan elemen x ke dalam ekor antrian private void enqueue (e x) {// tegaskan lock.getHoldCount () == 1; // menegaskan item [putIndex] == null; // Elemen posisi putIndex saat ini harus nol objek akhir [] item = this.items; item [putIndex] = x; // Jika putIndex sama dengan item.length, lalu atur ulang putIndex ke 0 if (++ putIndex == item.length) putIndex = 0; // tambahkan satu hitungan ++ ke jumlah antrian; // Karena elemen dimasukkan, antrian saat ini jelas tidak kosong. Kemudian bangun utas yang menunggu di bawah kondisi notempty notempty.signal (); } // hapus elemen header antrian dan kembalikan private e dequeue () {// tegaskan lock.getHoldCount () == 1; // menegaskan item [TakeIndex]! = NULL; objek akhir [] item = this.items; // Dapatkan elemen header antrian saat ini @suppresswarnings ("Uncecked") e x = (e) item [TakeIndex]; // Atur posisi header antrian saat ini ke item nol [TakeIndex] = null; if (++ takeIndex == items.length) TakeIndex = 0; // minus jumlah antrian dengan satu hitungan--; if (itrs! = null) itrs.elementdequeued (); // Karena suatu elemen dihapus, antriannya jelas tidak puas, jadi bangunkan utas yang menunggu di bawah kondisi yang mencolok yang mencolok. SIGNAL (); mengembalikan x; }Kedua metode ini mewakili, memasukkan elemen ke dalam dan menghapus elemen dari antrian, masing -masing. Dan mereka ingin membangunkan utas menunggu. Setelah memasukkan elemen, antrian tidak boleh kosong, sehingga utas yang menunggu di bawah kondisi tidak keras kepala harus dibangunkan. Setelah menghapus elemen, antrian harus tidak puas, sehingga utas yang menunggu di bawah kondisi yang mencolok harus dibangunkan.
6.2 Hapus metode (objek o)
// hapus elemen objek o dalam antrian, dan hapus paling banyak satu boolean publik hapus (objek o) {if (o == null) return false; objek akhir [] item = this.items; // Gunakan kunci untuk memastikan keamanan modifikasi multi-threaded dari atribut anggota reentrantlock lock = this.lock; lock.lock (); Coba {// hapus hanya jika ada nilai dalam antrian. if (count> 0) {// Posisi berikutnya di akhir antrian final int putIndex = this.putIndex; // Posisi header antrian int i = TakeIndex; do {// elemen posisi saat ini sama dengan elemen yang dihapus jika (o.equals (item [i])) {// hapus elemen posisi i lepas (i); // return true return true; } if (++ i == items.length) i = 0; // ketika i == putIndex berarti bahwa semua elemen telah dilalui} while (i! = PutIndex); } return false; } akhirnya {lock.unlock (); }} Hapus objek yang ditentukan O dari antrian, maka Anda harus melintasi antrian dan menghapus elemen pertama yang sama dengan objek o. Jika tidak ada objek o elemen dalam antrian, maka kembalikan false untuk menghapus gagal.
Berikut adalah dua poin yang perlu diperhatikan:
Cara melintasi antrian adalah melintasi dari kepala antrian ke ujung antrian. Itu tergantung pada dua variabel yang TakeIndex dan Putindex.
Mengapa objek [] item = this.items; Kode ini tidak ditempatkan di blok kode kunci kunci sinkron. Item adalah variabel anggota. Ketika ada begitu banyak utas, apakah tidak akan ada masalah konkurensi?
Ini karena item adalah variabel referensi, bukan tipe data dasar, dan operasi penyisipan dan penghapusan kami pada antrian semuanya untuk array item ini, dan referensi ke array tidak diubah. Oleh karena itu, dalam kode kunci, item akan mendapatkan modifikasi terbaru untuk itu oleh utas lain. Tetapi jika int putIndex = this.putIndex; Metode mengunci blok kode di luar, masalah akan terjadi.
Metode Lepas (Int RemoveIndex) Final
// hapus elemen dalam antrian lepas posisi void removeAt (final int remeempuIndex) {// asert lock.getHoldCount () == 1; // menegaskan item [remeCEnIndex]! = null; // Assert RemestIndex> = 0 && RemoveIndex <items.length; objek akhir [] item = this.items; // Ini berarti bahwa jauh lebih mudah untuk menghapus elemen sebagai header daftar, yang mirip dengan proses metode dequeue jika (lepasIndex == TakeIndex) {// Lepaskan elemen dalam item posisi RemestIndex [TakeIndex] = null; // Ketika akhir array, Anda harus pergi ke posisi header array jika (++ takeIndex == items.length) TakeIndex = 0; // minus jumlah antrian dengan satu hitungan--; if (itrs! = null) itrs.elementdequeued (); } else {// an "interior" hapus int intIndex = this.putIndex; untuk (int i = RemoveIndex ;;) {int next = i + 1; if (next == items.length) next = 0; // Ujung antrian belum mencapai ujung antrian, maka elemen di posisi berikutnya ditimpa oleh elemen pada posisi sebelumnya jika (selanjutnya! = PutIndex) {item [i] = item [selanjutnya]; i = selanjutnya; } else {// atur elemen ekor item antrian null [i] = null; // Setel ulang nilai putIndex this.putIndex = i; merusak; }} // Kurangi jumlah antrian dengan hitungan--; if (itrs! = null) itrs.removedAt (RemoveIndex); } // Karena suatu elemen dihapus, antriannya jelas tidak puas, jadi bangunkan utas yang menunggu di bawah kondisi yang mencolok yang mencolok. SIGNAL (); }Hapus elemen di lokasi yang ditentukan dalam antrian. Perlu dicatat bahwa array setelah penghapusan masih dapat mempertahankan bentuk antrian, yang dibagi menjadi dua situasi:
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.