ในบทก่อนหน้าเราอธิบายคิวการปิดกั้นที่นำมาใช้ใน ArrayblockingQueue โดยใช้แบบฟอร์มอาร์เรย์
ต้องกำหนดความยาวของอาร์เรย์เมื่อสร้าง หากความยาวอาร์เรย์มีขนาดเล็กคิว arrayblockingqueue จะถูกบล็อกได้อย่างง่ายดาย หากความยาวของอาร์เรย์มีขนาดใหญ่มันจะเสียหน่วยความจำได้ง่าย
โครงสร้างข้อมูลคิวนั้นเหมาะสำหรับรูปแบบของรายการที่เชื่อมโยงและ LinkedBlockingQueue เป็นแบบคิวการปิดกั้นที่ใช้โดยใช้รายการที่เชื่อมโยง
1. การใช้งานรายการที่เชื่อมโยง
1.1 Node Internal Class
/ *** โหนดของรายการที่เชื่อมโยงยังใช้เพื่อใช้รายการที่เชื่อมโยงทางเดียว*/ ระดับคลาสคงที่ <e> {e รายการ; // ชี้ไปที่โหนดถัดไปของโหนดรายการที่เชื่อมโยง <E> ถัดไป; โหนด (e x) {item = x; -มีตัวแปร E ที่เก็บข้อมูลและมีตัวแปรอ้างอิงถัดไปชี้ไปที่โหนดถัดไป มันสามารถใช้รายการทางเดียวที่ง่ายที่สุด
1.2 วิธีใช้รายการลิงค์
/ *** จุดต่อไปของหัวคิวและโหนดนี้ไม่ได้จัดเก็บข้อมูล*/ โหนดชั่วคราว <e> หัว; / *** โหนดหางคิว*/ โหนดชั่วคราวส่วนตัว <E> สุดท้าย;
ในการใช้งานรายการที่เชื่อมโยงจะต้องมีตัวแปรสองตัวหนึ่งตัวแสดงถึงส่วนหัวของรายการที่เชื่อมโยงและอื่น ๆ แสดงถึงรายการสุดท้ายของรายการที่เชื่อมโยง ทั้งหัวและสุดท้ายจะเริ่มต้นเมื่อสร้างวัตถุ LinkedBlockingQueue
last = head = new node <e> (null);
โปรดทราบว่ามีการใช้เคล็ดลับเล็ก ๆ ที่นี่ โหนดหัวของรายการที่เชื่อมโยงไม่ได้จัดเก็บข้อมูล โหนดถัดไปมันชี้ไปที่การจัดเก็บข้อมูลแรกในรายการที่เชื่อมโยงอย่างแท้จริง สุดท้ายในตอนท้ายของรายการที่เชื่อมโยงจะจัดเก็บข้อมูลสุดท้ายในรายการที่เชื่อมโยง
1.3 แทรกและลบโหนด
/ *** แทรกโหนดไปที่หางของคิว*/ โมฆะส่วนตัว enqueue (โหนด <e> โหนด) {// ยืนยัน putlock.isheldbycurrentthread (); // เธรดปัจจุบันจะต้องได้รับการล็อค putlock // ชี้การอ้างอิงถัดไปของโหนดหางคิวดั้งเดิมไปยังโหนดโหนดใหม่จากนั้นตั้งค่าโหนดโหนดไปที่โหนดหางของคิวสุดท้าย // นี่จะตระหนักถึงโหนดแทรกไปที่หางของคิวสุดท้าย = last.next = node; -มันง่ายมากที่จะแทรกโหนดในตอนท้ายของรายการที่เชื่อมโยง ชี้โหนดถัดไปของคิวดั้งเดิมล่าสุดไปยังโหนดโหนดใหม่จากนั้นกำหนดโหนดโหนดใหม่ให้กับโหนดสุดท้ายที่ส่วนท้ายของคิว สิ่งนี้ช่วยให้การแทรกโหนดใหม่
// ลบโหนดหัวคิวและส่งคืนข้อมูลโหนดที่ถูกลบส่วนตัว e dequeue () {// ยืนยัน takelock.isheldbycurrentthread (); // เธรดปัจจุบันจะต้องได้รับ Takelock Lock // ยืนยัน head.item == null; โหนด <e> h = head; // ข้อมูลขององค์ประกอบแรกในคิวจะถูกเก็บไว้ในโหนดโหนดแรก <e> first = h.next; H.Next = H; // Help GC // การตั้งค่าค่าหัวใหม่เทียบเท่ากับการลบโหนดแรก เพราะโหนดหัวเองไม่ได้จัดเก็บข้อมูลหัว = ก่อน; // ข้อมูลของส่วนหัวคิว e x = first.item; // ลบข้อมูลต้นฉบับก่อน item = null; กลับ x; -โปรดทราบว่าหัวไม่ใช่ส่วนหัวซึ่งเป็นจุดต่อไปของส่วนหัวดังนั้นจึงเป็นเรื่องง่ายมากที่จะลบส่วนหัวซึ่งคือการกำหนด head.next ให้กับหัวแล้วส่งคืนข้อมูลของโหนด head.next ดั้งเดิม
เมื่อลบให้ใส่ใจกับสถานการณ์ที่รายการที่เชื่อมโยงว่างเปล่า ค่าของ head.next ถูกเพิ่มโดยใช้วิธี enqueue เมื่อ head.next == ล่าสุดหมายความว่าองค์ประกอบสุดท้ายถูกลบ เมื่อ head.next == null มันไม่สามารถลบได้เนื่องจากรายการที่เชื่อมโยงนั้นว่างเปล่าอยู่แล้ว ไม่มีการตัดสินที่นี่เนื่องจากการตัดสินได้ถูกสร้างขึ้นในสถานที่ที่เรียกวิธีการ dequeue
2. การล็อคแบบซิงโครนัส reentrantlock และเงื่อนไข
เนื่องจากคิวการปิดกั้นจะต้องถูกบล็อกและรอเมื่อคิวว่างเปล่าและคิวเต็มแล้วจึงจำเป็นต้องมีสองเงื่อนไขตามธรรมชาติ เพื่อให้แน่ใจว่าความปลอดภัยของการเกิดขึ้นพร้อมกันหลายเธรดจำเป็นต้องมีการล็อคการซิงโครไนซ์ สิ่งนี้ได้รับการกล่าวใน Arrayblockingqueue
ที่นี่เราจะพูดถึงสิ่งต่าง ๆ เกี่ยวกับ LinkedBlockingQueue
/ ** ล็อคพิเศษที่ใช้ในการจัดการกับปัญหาการเกิดขึ้นพร้อมกันของการแทรกการดำเนินการคิวนั่นคือวางและเสนอการดำเนินงาน*/ ส่วนตัวสุดท้าย reentrantlock putlock = ใหม่ reentrantlock (); / ** เงื่อนไขเงื่อนไขว่าคิวไม่พอใจมันถูกสร้างขึ้นโดย Putlock Lock*/ Private Final Condition Notfull = Putlock.newCondition (); / ** ล็อคพิเศษที่ใช้ในการจัดการกับปัญหาพร้อมกันของการลบการดำเนินงานของคิวหัวนั่นคือการดำเนินการและการสำรวจความคิดเห็น*/ ส่วนตัวสุดท้าย reentrantlock takelock = ใหม่ reentrantlock (); / ** เงื่อนไขเงื่อนไขว่าคิวไม่ว่างเปล่ามันใช้เงื่อนไขสุดท้ายส่วนตัวที่สร้างขึ้นโดย Takelock Lock*/ Private Final Condition Notempty = Takelock.newCondition ();
2.1 Putlock และ Takelock
เราพบล็อคสองตัวที่ใช้:
ตามคำสั่งข้างต้นอาจมีการดำเนินการแทรกและลบองค์ประกอบในเวลาเดียวกันดังนั้นจะไม่มีปัญหาหรือไม่?
มาวิเคราะห์อย่างละเอียด สำหรับคิวการดำเนินการแบ่งออกเป็นสามประเภท:
ดังนั้นใช้ Putlock Lock เพื่อรักษาตัวแปรสุดท้ายให้ปลอดภัยและใช้ Takelock Lock เพื่อให้ตัวแปรหัวปลอดภัย
สำหรับตัวแปรการนับทั้งหมดที่เกี่ยวข้องในจำนวนองค์ประกอบในคิวอะตอมมิกทิกเกอร์ใช้เพื่อให้แน่ใจว่าปัญหาด้านความปลอดภัยพร้อมกัน
/ ** จำนวนองค์ประกอบในคิวใช้ตัวแปร Atomicinteger ที่นี่เพื่อให้แน่ใจว่าปัญหาด้านความปลอดภัยพร้อมกัน*/ เอกชนสุดท้าย Atomicinteger Count = new Atomicinteger ();
2.2 Notfull และ Notempty
2.3 กระบวนการควบคุม
เมื่อแทรกองค์ประกอบ:
เมื่อลบองค์ประกอบ:
โปรดทราบว่าต้องเรียกสัญญาณและวิธีการรอเงื่อนไขเมื่อได้รับการล็อค ดังนั้นจึงมีวิธีการส่งสัญญาณและวิธีการส่งสัญญาณ:
/*** ปลุกเธรดที่รออยู่ภายใต้เงื่อนไขที่ไม่ได้รับการบอกกล่าวนั่นคือเมื่อถอดส่วนหัวคิวออกเธรดที่พบว่าว่างเปล่าและถูกบังคับให้รอ * โปรดทราบว่าเนื่องจากจะเรียกวิธีการสัญญาณของเงื่อนไขการล็อคที่สอดคล้องกันจะต้องได้รับวิธี takelock.lock () เรียกว่าที่นี่ * เมื่อมีการแทรกองค์ประกอบลงในคิว (เช่นใส่หรือดำเนินการเสนอ) คิวจะไม่ว่างเปล่าอย่างแน่นอนและวิธีนี้จะถูกเรียก */ โมฆะส่วนตัว signalNotEmpty () {สุดท้าย reentrantlock takelock = this.takelock; takelock.lock (); ลอง {notempty.signal (); } ในที่สุด {takelock.unlock (); }} /*** ปลุกเธรดที่รออยู่ภายใต้เงื่อนไขที่น่าจดจำนั่นคือเมื่อองค์ประกอบถูกเพิ่มในตอนท้ายของคิวเธรดที่เต็มและถูกบังคับให้รอ * โปรดทราบว่าเนื่องจากการเรียกใช้วิธีการสัญญาณของเงื่อนไขจะต้องได้รับการล็อคที่สอดคล้องกันดังนั้นวิธีการ putlock.lock () เรียกว่าที่นี่* เมื่อองค์ประกอบ (เช่นการใช้งานหรือการดำเนินการสำรวจ) จะถูกลบในคิวคิวจะไม่พอใจอย่างแน่นอนและจะเรียกวิธีนี้ */ โมฆะส่วนตัว signalNotFull () {สุดท้าย reentrantlock putlock = this.putlock; putlock.lock (); ลอง {notfull.signal (); } ในที่สุด {putlock.unlock (); -3. วิธีการแทรกองค์ประกอบ
โมฆะสาธารณะใส่ (e e) โยน interruptedexception {ถ้า (e == null) โยน nullpointerexception ใหม่ (); // บันทึกจำนวนองค์ประกอบก่อนการแทรกการทำงาน int c = -1; // สร้างโหนดโหนดใหม่ <e> node = new node <e> (e); สุดท้าย reentrantlock putlock = this.putlock; Atomicinteger สุดท้ายนับ = this.count; putlock.lockinctibly (); ลอง {// ระบุว่าคิวเต็มแล้วคุณต้องโทรหาวิธีการ notfull.await เพื่อให้เธรดปัจจุบันรอขณะที่ (count.get () == ความจุ) {notfull.await (); } // แทรกองค์ประกอบใหม่ (โหนด); // เพิ่ม 1 ในจำนวนองค์ประกอบในคิวปัจจุบันและส่งคืนจำนวนองค์ประกอบก่อนที่จะเพิ่ม 1. c = count.getandincrement (); // C + 1 <ความจุหมายความว่าคิวไม่เต็มและเธรดที่อาจรอการดำเนินการแทรกถูกปลุกถ้า (C + 1 <ความจุ) Notfull.Signal (); } ในที่สุด {putlock.unlock (); } // c == 0 หมายความว่าคิวว่างเปล่าก่อนที่จะแทรก เมื่อคิวว่างเปล่าไปยังองค์ประกอบที่ถูกวาง // ปลุกเธรดที่รอการลบ // ป้องกันการได้มาซึ่งการล็อค takelock บ่อยครั้งใช้ประสิทธิภาพถ้า (c == 0) signalNotEmpty (); -การใช้วิธีการเป็นตัวอย่างกระบวนการทั่วไปเหมือนกับที่เราแนะนำไว้ก่อนหน้านี้ นี่คือรหัสที่แปลกมาก เมื่อมีการแทรกองค์ประกอบหากคุณพบว่าคิวไม่เต็มให้โทรหา Notfull.signal () เพื่อปลุกเธรดที่รอการแทรก
ทุกคนสับสนมาก โดยทั่วไปวิธีการนี้ควรวางไว้ในองค์ประกอบการลบ (ใช้วิธีซีรีย์) เพราะเมื่อเราลบองค์ประกอบคิวจะต้องอยู่ภายใต้เต็มแล้วเรียกใช้วิธีการ Notfull.signal () เพื่อปลุกเธรดที่รอการแทรก
สิ่งนี้ส่วนใหญ่ทำที่นี่เพราะเมื่อเรียกวิธีการสัญญาณการล็อคที่สอดคล้องกันจะต้องได้รับก่อน ล็อคที่ใช้ในวิธี Take Series คือ Takelock หากคุณต้องการเรียกเมธอด notfull.signal () คุณต้องได้รับการล็อค Putlock ก่อน สิ่งนี้จะทำให้ประสิทธิภาพลดลงดังนั้นจึงใช้วิธีอื่น
4. ลบองค์ประกอบส่วนหัวคิว
สาธารณะ E TAPE () พ่น InterruptedException {E X; int c = -1; Atomicinteger สุดท้ายนับ = this.count; สุดท้าย reentrantlock takelock = this.takelock; takelock.lockintibly (); ลอง {// หมายความว่าคิวว่างเปล่าจากนั้นคุณต้องโทรหาวิธี notempty.await เพื่อให้เธรดปัจจุบันรอขณะที่ (count.get () == 0) {notempty.await (); } // ลบองค์ประกอบส่วนหัวคิวและส่งคืน x = dequeue (); // ส่งคืนจำนวนคิวปัจจุบันจากนั้นลบจำนวนคิวด้วยหนึ่ง c = count.getanddecrement (); // c> 1 หมายความว่าคิวไม่ว่างเปล่าดังนั้นมันจึงตื่นขึ้นมาเธรดที่อาจรอการดำเนินการลบถ้า (c> 1) notempty.signal (); } ในที่สุด {takelock.unlock (); } /*** C == ความจุหมายความว่าคิวเต็มก่อนการดำเนินการลบ * ปลุกเธรดที่รอการแทรกเฉพาะเมื่อองค์ประกอบถูกลบออกจากคิวเต็มรูปแบบ* ป้องกันการได้มาซึ่งการล็อค putlock บ่อยครั้งการใช้ประสิทธิภาพการใช้งาน*/ ถ้า (C == กำลังการผลิต) signalNotFull (); กลับ x; -เหตุใดจึงมีวิธีการ notempty.signal () เปรียบเทียบคำอธิบายของเราในวิธีการแทรก
5. ดูองค์ประกอบส่วนหัวของคิว
// ดูองค์ประกอบส่วนหัวของคิวสาธารณะ e peek () {// คิวว่างเปล่า, ส่งคืน null ถ้า (count.get () == 0) ส่งคืน null; สุดท้าย reentrantlock takelock = this.takelock; takelock.lock (); ลอง {// รับโหนดส่วนหัวคิวแรกโหนด <E> first = head.next; // first == null หมายความว่าคิวว่างเปล่าส่งคืน null ถ้า (แรก == null) ส่งคืน null; อื่น // ส่งคืนองค์ประกอบส่วนหัวของคิวกลับมาก่อน } ในที่สุด {takelock.unlock (); -ดูองค์ประกอบส่วนหัวของคิวซึ่งเกี่ยวข้องกับโหนดหัวดังนั้นจึงต้องใช้ Takelock Lock
VI. วิธีการสำคัญอื่น ๆ
6.1 ลบ (วัตถุ O) วิธีการ
// ลบองค์ประกอบที่ระบุออกจากคิวบูบูลีนสาธารณะลบ (วัตถุ o) {ถ้า (o == null) ส่งคืนเท็จ; // เพราะมันไม่ได้ลบองค์ประกอบส่วนหัวรายการหัวตัวแปรทั้งสองและสุดท้ายเกี่ยวข้อง // putlock และ takelock จะต้องล็อคล็อคอย่างเต็มที่ (); ลอง {// traverse ทั้งคิว, p หมายถึงโหนดปัจจุบันและเส้นทางแสดงถึงโหนดก่อนหน้าของโหนดปัจจุบัน // เพราะมันเป็นรายการที่เชื่อมโยงทางเดียวสองโหนดจะต้องบันทึกสำหรับ (โหนด <e> trail = head, p = trail.next; p! = null; (O.Equals (P.Item)) {Unlink (P, Trail); กลับมาจริง; }} return false; } ในที่สุด {forekerunLock (); -ลบองค์ประกอบที่ระบุออกจากรายการ เนื่องจากองค์ประกอบที่ถูกลบไม่จำเป็นต้องอยู่ในหัวของรายการจึงอาจมีหัวตัวแปรสองตัวและสุดท้ายดังนั้นคุณต้องใช้ทั้ง Putlock และ Takelock ในเวลาเดียวกัน เนื่องจากเป็นรายการที่เชื่อมโยงทางเดียวจึงจำเป็นต้องใช้เส้นทางตัวแปรเสริมเพื่อบันทึกโหนดก่อนหน้าเพื่อให้สามารถลบโหนดปัจจุบัน P ได้
6.2 Unlink (Node <E> P, โหนด <E> เส้นทาง) วิธีการ
// ลบโหนดปัจจุบัน p และเส้นทางแสดงถึงโหนดก่อนหน้าของ p void unlink (โหนด <e> p, โหนด <e> trail) {// ตั้งค่าข้อมูลของโหนดปัจจุบันเป็น null p.item = null; // สิ่งนี้จะลบโหนด p trail.next = p.next; // ถ้าโหนด P เป็นสุดท้ายของคิวสุดท้ายและถูกลบออกจากนั้นตั้งค่าเส้นทางเป็นสุดท้ายถ้า (สุดท้าย == p) สุดท้าย = trail; // ลบจำนวนองค์ประกอบด้วยหนึ่งถ้าคิวดั้งเดิมเต็มแล้วเรียกเมธอด notfull.signal () // ในความเป็นจริงสิ่งนี้เรียกว่าโดยตรงโดยไม่มีการตัดสินเนื่องจากการล็อค putlock จะต้องได้รับที่นี่ถ้า (count.getanddecrement () == ความสามารถ) -ในการลบโหนด P ในรายการที่เชื่อมโยงคุณจะต้องชี้ไปที่เส้นทางโหนดก่อนหน้าของ P ไปยังโหนดถัดไปถัดไปของโหนด p
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น