ในบทก่อนหน้าเราแนะนำการปิดกั้นคิวการบล็อกคิว ด้านล่างเราแนะนำคลาสการใช้งานที่ใช้กันทั่วไป arrayblockingqueue
1. ใช้อาร์เรย์เพื่อใช้คิว
เนื่องจากข้อกำหนดพิเศษของโครงสร้างข้อมูลของคิวจึงเหมาะสมที่จะนำไปใช้ในรูปแบบของรายการที่เชื่อมโยง ตัวแปรสองตัวใช้เพื่อบันทึกส่วนหัวและส่วนท้ายของรายการที่เชื่อมโยงตามลำดับ เมื่อลบหรือแทรกคิวให้เปลี่ยนส่วนหัวหรือส่วนท้ายของรายการที่เชื่อมโยง ยิ่งไปกว่านั้นรายการที่เชื่อมโยงนั้นเชื่อมโยงกันในลักษณะอ้างอิงดังนั้นความสามารถของมันจึงไม่ จำกัด
ดังนั้นวิธีการใช้อาร์เรย์เพื่อใช้คิวเราต้องการตัวแปรสี่ตัว: อาร์เรย์วัตถุ [] เพื่อจัดเก็บองค์ประกอบในคิวหัวและ tailindex บันทึกหัวคิวและหางและนับจำนวนคิว
มีการใช้วิธีที่ฉลาดมากที่นี่ เรารู้ว่าเมื่อมีการแทรกองค์ประกอบลงในคิวมันจะใช้ตำแหน่งในอาร์เรย์ เมื่อองค์ประกอบถูกลบตำแหน่งของอาร์เรย์นั้นฟรีจริงซึ่งบ่งชี้ว่าสามารถแทรกองค์ประกอบใหม่ในตำแหน่งนี้ได้
ดังนั้นก่อนที่เราจะแทรกองค์ประกอบใหม่เราต้องตรวจสอบว่าคิวเต็มและก่อนที่เราจะลบองค์ประกอบเราต้องตรวจสอบว่าคิวว่างเปล่าหรือไม่
2. ตัวแปรสมาชิกที่สำคัญใน arrayblockingqueue
/ ** จัดเก็บองค์ประกอบในคิว*/ วัตถุสุดท้าย [] รายการ; / ** ตำแหน่งของหัวคิว*/ int TakeIndex; / ** ตำแหน่งของหางคิว*/ int putindex; / ** จำนวนองค์ประกอบในคิวปัจจุบัน*/ int จำนวน; / ** ใช้เพื่อให้แน่ใจว่าความปลอดภัยของตัวแปรที่ใช้ร่วมกันแบบมัลติเธรด*/ ล็อค Reentrantlock สุดท้าย; / ** เมื่อคิวว่างเปล่าวิธีการรอคอยของ notempty จะถูกเรียกให้ทำเธรดปัจจุบันรอ*/ เงื่อนไขสุดท้ายส่วนตัว notempty; / ** เมื่อคิวเต็มวิธีการรอคอยของ Notfull จะถูกเรียกทำให้เธรดปัจจุบันรอ*/ เงื่อนไขสุดท้ายส่วนตัว Notfull;
มีตัวแปรล็อคที่ไม่ได้รับการล็อคและเป็นสิ่งที่น่าสนใจมากขึ้นในการใช้เงื่อนไขความปลอดภัยแบบมัลติเธรดและเงื่อนไขการรอเธรด พวกเขาทำงานอย่างไร?
2.1 บทบาทของการล็อค
เนื่องจาก ArrayBlockingQueue ทำงานภายใต้หลายเธรดเมื่อปรับเปลี่ยนตัวแปรสมาชิกเช่นรายการ, TakeIndex, Putindex และ Count, ปัญหาด้านความปลอดภัยแบบหลายเธรดต้องได้รับการพิจารณา ดังนั้นล็อคล็อคแบบพิเศษจึงถูกใช้ที่นี่เพื่อให้แน่ใจว่าความปลอดภัยของการดำเนินงานพร้อมกัน
2.2 บทบาทของ notempty และ notfull
เนื่องจากการปิดกั้นคิวจะต้องดำเนินการเมื่อคิวว่างเปล่าหรือคิวเต็มรูปแบบการอ่านหรือแทรกการดำเนินการคิวจะต้องรอ ดังนั้นเราจึงนึกถึงวัตถุเงื่อนไขภายใต้กรอบการทำงานพร้อมกันและใช้มันเพื่อควบคุมมัน
ใน AQS เราแนะนำบทบาทของคลาสนี้:
3. เพิ่มวิธีการองค์ประกอบ
3.1 เพิ่ม (e e) และข้อเสนอ (e e) วิธี:
// เรียกวิธีการในคลาส Parent -Abstractqueue บูลีนสาธารณะเพิ่ม (e e) {// ใช้ถ้า (ข้อเสนอ (e)) ส่งคืนจริง; อื่น ๆ โยน unleegalstateException ใหม่ ("คิวเต็ม"); } // เพิ่มองค์ประกอบใหม่ในตอนท้ายของคิว Return True หมายถึงการเพิ่มนั้นประสบความสำเร็จเท็จหมายถึงการเพิ่มความล้มเหลวและไม่มีข้อยกเว้นใด ๆ ถูกโยนข้อเสนอบูลีนสาธารณะ (e e) {checknotNull (e); สุดท้าย reentrantlock lock = this.lock; // ใช้ล็อคเพื่อให้แน่ใจว่าการปรับเปลี่ยนมัลติเธรดของแอตทริบิวต์สมาชิก lock.lock (); ลอง {// คิวเต็มและการเพิ่มองค์ประกอบล้มเหลวส่งคืนเท็จ if (count == items.length) ส่งคืน false; else {// เรียกวิธี enqueue เพื่อแทรกองค์ประกอบลงในคิว enqueue (e); กลับมาจริง; }} ในที่สุด {lock.unlock (); -วิธีการเพิ่มถูกนำไปใช้โดยเรียกใช้วิธีการเสนอ ในวิธีการเสนอนั้นจำเป็นต้องพิจารณาก่อนว่าคิวเต็มหรือไม่ หากเต็มมันจะส่งคืนเท็จโดยตรงโดยไม่ต้องปิดกั้นเธรดปัจจุบัน หากคุณไม่พอใจให้โทรหาวิธี enqueue เพื่อแทรกองค์ประกอบลงในคิว
หมายเหตุ: การใช้ lock.lock () ที่นี่ทำให้มั่นใจได้ว่ามีเพียงหนึ่งเธรดที่ดัดแปลงตัวแปรสมาชิกในเวลาเดียวกันเพื่อป้องกันปัญหาการทำงานพร้อมกัน แม้ว่ามันจะปิดกั้นเธรดปัจจุบัน แต่ก็ไม่ใช่การรอคอยตามเงื่อนไข แต่ก็เป็นเพราะการล็อคนั้นถูกจัดขึ้นโดยเธรดอื่น ๆ และเวลาในการดำเนินการใน ArrayblockingQueue ไม่ยาวซึ่งเทียบเท่ากับการไม่ปิดกั้นเธรด
3.2 ใส่วิธีการ
// เพิ่มองค์ประกอบใหม่ในตอนท้ายของคิว หากคิวเต็มเธรดปัจจุบันจะรอ การตอบสนองต่อข้อยกเว้นขัดจังหวะโมฆะสาธารณะใส่ (e e) พ่น InterruptedException {checknotNull (e); สุดท้าย reentrantlock lock = this.lock; // ใช้ล็อคเพื่อให้แน่ใจว่ามัลติเธรดแก้ไขความปลอดภัยของแอตทริบิวต์สมาชิกล็อคล็อคอย่างต่อเนื่อง (); ลอง {// ถ้าคิวเต็มให้โทรหาวิธี notfull.await () เพื่อให้เธรดปัจจุบันรอจนกว่าคิวจะไม่เต็มในขณะที่ (count == items.length) notfull.await (); // เรียกวิธี enqueue เพื่อแทรกองค์ประกอบลงในคิว enqueue (e); } ในที่สุด {lock.unlock (); -กระบวนการทั่วไปของวิธีการเสนอนั้นเหมือนกับวิธีการเสนอ อย่างไรก็ตามเมื่อคิวเต็มวิธีการ notfull.await () จะถูกเรียกให้ทำบล็อกเธรดปัจจุบันและรอจนกว่าคิวจะถูกลบออกโดยเธรดอื่น เมื่อคิวไม่พอใจกระทู้ที่รอคอยจะถูกปลุก
3.3 ข้อเสนอ (E, Long Timeout, TimeUnit Unit) วิธีการ
/*** เพิ่มองค์ประกอบใหม่ในตอนท้ายของคิว หากไม่มีพื้นที่ว่างในคิวเธรดปัจจุบันจะรอ * หากเวลารอเกินกว่าการหมดเวลาจะถูกส่งกลับเท็จแสดงให้เห็นว่าการเพิ่มข้อเสนอ*/ บูลีนสาธารณะ (E E, Long Timeout, TimeUnit Unit) โยน InterruptedException {ChecknotNull (E); // คำนวณค่าเวลาของ Nanos Long Long Nanos ทั้งหมดที่รอคอยสูงสุด = unit.tonanos (หมดเวลา); สุดท้าย reentrantlock lock = this.lock; // ใช้ล็อคเพื่อให้แน่ใจว่าการปรับเปลี่ยนมัลติเธรดของแอตทริบิวต์สมาชิกล็อคล็อคอย่างต่อเนื่อง (); ลอง {// คิวเต็มในขณะที่ (count == items.length) {// nanos <= 0 หมายความว่าเวลารอคอยสูงสุดมาถึงดังนั้นจึงไม่จำเป็นต้องรออีกต่อไป ส่งคืนเท็จแสดงว่าการเพิ่มล้มเหลว if (nanos <= 0) ส่งคืน false; // โทรหาวิธี Notfull.awaitnanos (nanos) เวลา Nanos หมดเวลาจะถูกปลุกโดยอัตโนมัติ // ถ้ามันตื่นขึ้นมาล่วงหน้าเวลาที่เหลือจะถูกส่งคืน nanos = notfull.awaitnanos (นาโน); } // เรียกวิธี enqueue เพื่อแทรกองค์ประกอบลงในคิว enqueue (e); กลับมาจริง; } ในที่สุด {lock.unlock (); -วิธีการไหลทั่วไปของวิธีการพัตต์เหมือนกับวิธีการพัตต์มันเป็นเพียงการเรียกวิธีการ notfull.awaitnanos (nanos) เพื่อให้เธรดปัจจุบันรอและตั้งเวลารอ
4. วิธีการลบองค์ประกอบ
4.1 ลบ () และวิธีการสำรวจ ():
// เรียกวิธีการในคลาส Parent -Abstractqueue สาธารณะ e ลบ () {// การใช้งานโดยการโทรแบบสำรวจความคิดเห็น e x = poll (); if (x! = null) return x; อื่นโยน nosuchelementexception ใหม่ (); } // ลบองค์ประกอบแรกของคิว (เช่นส่วนหัวคิว) และส่งคืน หากคิวว่างเปล่ามันจะไม่โยนข้อยกเว้น แต่ส่งคืนค่า NULL Public E Poll () {สุดท้าย reentrantlock lock = this.lock; // ใช้ล็อคเพื่อให้แน่ใจว่าการปรับเปลี่ยนมัลติเธรดของแอตทริบิวต์สมาชิก lock.lock (); ลอง {// ถ้า count == 0 และรายการว่างเปล่าส่งคืนค่า null มิฉะนั้นโทรหาวิธี dequeue เพื่อส่งคืนองค์ประกอบส่วนหัวของรายการ (count == 0)? null: dequeue (); } ในที่สุด {lock.unlock (); -วิธีการลบจะถูกนำไปใช้โดยการเรียกวิธีการสำรวจความคิดเห็น () ในวิธีการสำรวจความคิดเห็น () หากรายการว่างเปล่ามันจะส่งคืนโมฆะมิฉะนั้นวิธีการ dequeue จะถูกเรียกให้ส่งคืนองค์ประกอบส่วนหัวของรายการ
4.2 ใช้ () วิธีการ
/*** ส่งคืนและลบองค์ประกอบแรกของคิว หากคิวว่างเปล่าเธรดด้านหน้าจะรอ การตอบสนองขัดจังหวะข้อยกเว้น*/ สาธารณะ e รับ () พ่น InterruptedException {สุดท้าย reentrantlock lock = this.lock; // ใช้ล็อคเพื่อให้แน่ใจว่ามัลติเธรดแก้ไขความปลอดภัยของแอตทริบิวต์สมาชิกล็อคล็อคอย่างต่อเนื่อง (); ลอง {// ถ้าคิวว่างเปล่าให้เรียกเมธอด notempty.await () เพื่อให้เธรดปัจจุบันรอ // จนกระทั่งเธรดอื่นแทรกองค์ประกอบลงในคิวเธรดจะถูกปลุก ในขณะที่ (count == 0) notempty.await (); // เรียกเมธอด dequeue เพื่อส่งคืนองค์ประกอบส่วนหัวของรายการส่งคืน dequeue (); } ในที่สุด {lock.unlock (); -เมื่อวิธีการใช้ () ว่างเปล่าเธรดปัจจุบันจะต้องรอจนกว่าเธรดอื่นจะแทรกองค์ประกอบใหม่ลงในคิวและเธรดจะถูกปลุก
4.3 โพล (การหมดเวลายาว, หน่วย TimeUnit) วิธีการ
/*** ส่งคืนและลบองค์ประกอบแรกของคิว หากคิวว่างเปล่าเธรดด้านหน้าจะรอ * หากเวลารอเกินกว่าการหมดเวลาจะถูกส่งกลับเท็จเพื่อระบุว่าองค์ประกอบนั้นล้มเหลว*/ การสำรวจความคิดเห็นสาธารณะ (การหมดเวลานาน, หน่วย TimeUnit) พ่น InterruptedException {// คำนวณค่าเวลาการรอคอยสูงสุดในนาโนทั้งหมด Long Nanos = UNIT.tonanos (หมดเวลา); สุดท้าย reentrantlock lock = this.lock; // ใช้ล็อคเพื่อให้แน่ใจว่าการปรับเปลี่ยนมัลติเธรดของแอตทริบิวต์สมาชิกล็อคล็อคอย่างต่อเนื่อง (); ลอง {// คิวว่างเปล่าในขณะที่ (count == 0) {// nanos <= 0 หมายความว่าเวลารอคอยสูงสุดมาถึงแล้วดังนั้นจึงไม่จำเป็นต้องรออีกต่อไป if (nanos <= 0) ส่งคืน null; // เรียกเมธอด notempty.awaitnanos (nanos) เพื่อให้เธรดกำหนดการรอและตั้งเวลาหมดเวลา nanos = notempty.awaitnanos (นาโน); } // เรียกเมธอด dequeue เพื่อส่งคืนองค์ประกอบส่วนหัวรายการส่งคืน dequeue (); } ในที่สุด {lock.unlock (); -เช่นเดียวกับกระบวนการวิธีการ TAPE () มันเรียกว่าวิธี Awaitnanos (nanos) เพื่อให้เธรดปัจจุบันรอและตั้งเวลารอ
5. วิธีการดูองค์ประกอบ
5.1 Element () และ Peek () วิธีการ
// เรียกวิธีการในคลาส Parent -Abstractqueue element e สาธารณะ () {e x = peek (); if (x! = null) return x; อื่นโยน nosuchelementexception ใหม่ (); } // ดูองค์ประกอบส่วนหัวของคิวสาธารณะ e peek () {สุดท้าย reentrantlock lock = this.lock; // ใช้ล็อคเพื่อให้แน่ใจว่าการปรับเปลี่ยนมัลติเธรดของแอตทริบิวต์สมาชิก lock.lock (); ลอง {// ส่งคืนองค์ประกอบของรายการส่งคืนส่วนหัวคิวปัจจุบัน (TakeIndex); // null เมื่อคิวว่างเปล่า} ในที่สุด {lock.unlock (); -VI. วิธีการสำคัญอื่น ๆ
6.1 วิธีการ enqueue และ dequeue
// แทรกองค์ประกอบ x เข้าไปในหางของคิวโมฆะส่วนตัว enqueue (e x) {// assert lock.getholdCount () == 1; // ยืนยันรายการ [putindex] == null; // องค์ประกอบตำแหน่ง putindex ปัจจุบันจะต้องเป็นวัตถุสุดท้ายที่เป็นโมฆะ [] รายการ = this.items; รายการ [putindex] = x; // ถ้า putindex เท่ากับ items.length จากนั้นรีเซ็ต putindex เป็น 0 ถ้า (++ putindex == items.length) putindex = 0; // เพิ่มหนึ่ง count ++ ในจำนวนคิว; // เนื่องจากองค์ประกอบถูกแทรกคิวปัจจุบันจึงไม่ว่างเปล่าอย่างแน่นอน จากนั้นปลุกเธรดที่รออยู่ภายใต้เงื่อนไข notempty notempty.signal (); } // ลบองค์ประกอบของส่วนหัวคิวและส่งคืนส่วนตัว e dequeue () {// assert lock.getholdCount () == 1; // ยืนยันรายการ [TakeIndex]! = null; วัตถุสุดท้าย [] รายการ = this.items; // รับองค์ประกอบของส่วนหัวคิวปัจจุบัน @suppresswarnings ("ไม่ได้ตรวจสอบ") e x = (e) รายการ [TakeIndex]; // ตั้งค่าตำแหน่งส่วนหัวคิวปัจจุบันเป็นรายการว่าง [TakeIndex] = null; if (++ takeIndex == items.length) TakeIndex = 0; // ลบจำนวนคิวด้วยการนับหนึ่งครั้ง-; ถ้า (itrs! = null) itrs.elementDequeued (); // เนื่องจากองค์ประกอบถูกลบคิวจึงไม่พอใจอย่างแน่นอนดังนั้นตื่นขึ้นมาด้วยเธรดที่รออยู่ภายใต้เงื่อนไขที่น่าสนใจ Notfull.signal (); กลับ x; -วิธีการทั้งสองนี้แสดงถึงการแทรกองค์ประกอบลงในและลบองค์ประกอบออกจากคิวตามลำดับ และพวกเขาต้องการที่จะตื่นขึ้นมาด้ายรอ หลังจากแทรกองค์ประกอบคิวจะต้องไม่ว่างเปล่าดังนั้นเธรดที่รออยู่ภายใต้เงื่อนไข notempty จะต้องตื่นขึ้นมา หลังจากลบองค์ประกอบคิวจะต้องไม่พอใจดังนั้นเธรดที่รออยู่ภายใต้เงื่อนไขที่น่าสนใจจะต้องตื่นขึ้นมา
6.2 ลบเมธอด (วัตถุ o)
// ลบองค์ประกอบ Object O ในคิวและลบที่บูลีนสาธารณะส่วนใหญ่หนึ่งลบ (Object O) {ถ้า (o == null) ส่งคืนเท็จ; วัตถุสุดท้าย [] รายการ = this.items; // ใช้ล็อคเพื่อให้แน่ใจว่าความปลอดภัยของการดัดแปลงมัลติเธรดของแอตทริบิวต์สมาชิกสุดท้าย reentrantlock ล็อค = this.lock; lock.lock (); ลอง {// ลบเฉพาะเมื่อมีค่าในคิว if (count> 0) {// ตำแหน่งถัดไปที่ส่วนท้ายของคิวสุดท้าย int putindex = this.putIndex; // ตำแหน่งของส่วนหัวคิว int i = takeIndex; ทำ {// องค์ประกอบตำแหน่งปัจจุบันเหมือนกับองค์ประกอบที่ถูกลบถ้า (o.equals (รายการ [i])) {// ลบองค์ประกอบตำแหน่ง I ลบ (I); // return true return true; } if (++ i == items.length) i = 0; // เมื่อฉัน == Putindex หมายความว่าองค์ประกอบทั้งหมดได้ถูกสำรวจ} ในขณะที่ (i! = putindex); } return false; } ในที่สุด {lock.unlock (); - ลบวัตถุที่ระบุ O ออกจากคิวจากนั้นคุณต้องสำรวจคิวและลบองค์ประกอบแรกที่เหมือนกับวัตถุ o หากไม่มีองค์ประกอบ o วัตถุในคิวให้ส่งคืนเท็จเพื่อลบล้มเหลว
นี่คือสองจุดที่ควรทราบ:
วิธีการสำรวจคิวคือการสำรวจจากหัวของคิวไปจนถึงส่วนท้ายของคิว มันขึ้นอยู่กับตัวแปรสองตัวที่ TakeIndex และ Putindex
เหตุใด Object [] items = this.items; รหัสนี้ไม่ได้อยู่ในบล็อกรหัสล็อคล็อคแบบซิงโครนัส รายการเป็นตัวแปรสมาชิก เมื่อมีเธรดมากมายจะไม่มีปัญหาพร้อมกันหรือไม่?
นี่เป็นเพราะรายการเป็นตัวแปรอ้างอิงไม่ใช่ชนิดข้อมูลพื้นฐานและการแทรกและการลบของเราในคิวทั้งหมดสำหรับอาร์เรย์รายการนี้และการอ้างอิงถึงอาร์เรย์จะไม่เปลี่ยนแปลง ดังนั้นในรหัสล็อครายการจะได้รับการแก้ไขล่าสุดโดยเธรดอื่น ๆ แต่ถ้า int putindex = this.putIndex; วิธีล็อคบล็อกรหัสด้านนอกปัญหาจะเกิดขึ้น
วิธีการลบ (ขั้นสุดท้าย int remverIndex)
// ลบองค์ประกอบในคิวลบตำแหน่งโมฆะลบออก (ขั้นสุดท้าย int removeIndex) {// assert lock.getholdCount () == 1; // ยืนยันรายการ [removeIndex]! = null; // ยืนยัน removeIndex> = 0 && removeIndex <items.length; วัตถุสุดท้าย [] รายการ = this.items; // หมายความว่ามันง่ายกว่ามากในการลบองค์ประกอบเป็นส่วนหัวรายการซึ่งคล้ายกับกระบวนการ dequeue method ถ้า (removeIndex == TakeIndex) {// ลบองค์ประกอบในรายการตำแหน่ง removeIndex [TakeIndex] = null; // เมื่อสิ้นสุดอาร์เรย์คุณต้องไปที่ตำแหน่งส่วนหัวอาร์เรย์ถ้า (++ takeIndex == items.length) TakeIndex = 0; // ลบจำนวนคิวด้วยการนับหนึ่งครั้ง-; ถ้า (itrs! = null) itrs.elementDequeued (); } else {// "การตกแต่งภายใน" ลบ int final int putindex = this.putIndex; สำหรับ (int i = removeIndex ;;) {int next = i + 1; if (next == items.length) next = 0; // จุดสิ้นสุดของคิวยังไม่ถึงจุดสิ้นสุดของคิวจากนั้นองค์ประกอบในตำแหน่งถัดไปจะถูกเขียนทับโดยองค์ประกอบในตำแหน่งก่อนหน้าถ้า (ถัดไป! = putindex) {รายการ [i] = รายการ [ถัดไป]; i = ถัดไป; } else {// ตั้งค่าองค์ประกอบหางของรายการ null queue [i] = null; // รีเซ็ตค่าของ PutIndex this.putIndex = i; หยุดพัก; }} // ลดจำนวนคิวด้วยการนับ-; ถ้า (itrs! = null) itrs.removedat (removeIndex); } // เนื่องจากองค์ประกอบถูกลบคิวไม่พอใจแน่นอนดังนั้นตื่นขึ้นมาพร้อมกับด้ายที่รออยู่ภายใต้เงื่อนไขที่น่าสนใจ Notfull.signal (); -ลบองค์ประกอบในตำแหน่งที่ระบุในคิว ควรสังเกตว่าอาร์เรย์หลังการลบยังสามารถรักษาแบบฟอร์มคิวซึ่งแบ่งออกเป็นสองสถานการณ์:
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น