في الفصل السابق ، شرحنا قائمة انتظار الحظر التي تم تنفيذها في ArrayBlockingQueue ، باستخدام نموذج الصفيف.
يجب تحديد طول الصفيف عند الإنشاء. إذا كان طول الصفيف صغيرًا ، فسيتم بسهولة حظر قائمة انتظار ArrayBlockingQueue. إذا كان طول الصفيف كبيرًا ، فسوف يضيع الذاكرة بسهولة.
بنية بيانات قائمة الانتظار مناسبة بشكل طبيعي لشكل القوائم المرتبطة ، و LinkedBlockingQueue هي قائمة انتظار الحظر التي يتم تنفيذها باستخدام القوائم المرتبطة.
1. تنفيذ القائمة المرتبطة
1.1 الفئة الداخلية العقدة
/ *** يتم استخدام عقدة القائمة المرتبطة أيضًا لتنفيذ قائمة مرتبطة في اتجاه واحد*/ عقدة الفئة الثابتة <e> {e item ؛ // أشر إلى العقدة التالية لعقدة القائمة المرتبطة <e> التالية ؛ العقدة (e x) {item = x ؛ }}هناك متغير E يخزن البيانات ، وهناك مرجع متغير التالي يشير إلى العقدة التالية. يمكن أن تنفذ أبسط قائمة في اتجاه واحد.
1.2 كيفية تنفيذ قائمة الارتباطات
/ *** النقطة التالية إلى رأس قائمة الانتظار ، وهذه العقدة لا تخزن البيانات*/ عقدة عابرة <e> ؛ / *** Queue Tail Node*/ Private Transient Node <e> Last ؛
لتنفيذ قائمة مرتبطة ، يجب أن يكون هناك متغيران ، ويمثل أحدهما رئيس القائمة المرتبطة والآخر يمثل آخر القائمة المرتبطة. تتم تهيئة كل من الرأس والأخير عند إنشاء كائن LinkedBlockingQueue.
last = head = new node <e> (null) ؛
لاحظ أنه يتم استخدام خدعة صغيرة هنا. عقدة الرأس للقائمة المرتبطة لا تخزن البيانات. تشير العقدة التالية إلى تخزين البيانات الأولى في القائمة المرتبطة حقًا. الأخير في نهاية القائمة المرتبطة يقوم بالفعل بتخزين البيانات الأخيرة في القائمة المرتبطة.
1.3 إدراج وحذف العقد
/ *** أدخل عقدة إلى ذيل قائمة الانتظار*/ private void enqueue (Node <e> node) {// assert putlock.isheldbyCurrentTrathread () ؛ // يجب أن يكون مؤشر الترابط الحالي قد حصل على قفل putlock // النقطة المرجع التالي لعقدة ذيل قائمة الانتظار الأصلية إلى عقدة العقدة الجديدة ، ثم قم بتعيين عقدة العقدة على عقدة الذيل في قائمة الانتظار الأخيرة // وهذا يدرك العقدة الإدراجية لذيل قائمة الانتظار الأخيرة = last.next = node ؛ }من السهل جدًا إدخال عقدة في نهاية القائمة المرتبطة. قم بتوضيح العقدة التالية من قائمة الانتظار الأصلية إلى عقدة العقدة الجديدة ، ثم قم بتعيين العقدة الجديدة إلى العقدة الأخيرة في نهاية قائمة الانتظار. هذا يتيح إدخال عقدة جديدة.
// قم بإزالة عقدة رأس قائمة الانتظار وإرجاع بيانات العقدة المحذوفة الخاصة e dequeue () {// assert takelock.isheldbyCurrentTrathread () ؛ // يجب أن يكون الخيط الحالي قد حصل على قفل takelock // assert head.item == null ؛ العقدة <e> h = الرأس ؛ // يتم تخزين بيانات العنصر الأول في قائمة الانتظار في عقدة العقدة الأولى <e> first = h.next ؛ H.Next = h ؛ // مساعدة GC // تعيين قيمة الرأس الجديدة تعادل حذف العقدة الأولى. لأن عقدة الرأس نفسها لا تخزن رأس البيانات = أولاً ؛ // بيانات رأس قائمة الانتظار e x = first.item ؛ // إزالة البيانات الأصلية first.item = null ؛ إرجاع x ؛ }لاحظ أن Head ليس هو الرأس ، النقطة التالية إلى الرأس ، لذلك من السهل جدًا حذف الرأس ، وهو تعيين رأس.
عند الحذف ، انتبه إلى الموقف الذي تكون فيه القائمة المرتبطة فارغة. تتم إضافة قيمة head.next باستخدام طريقة enqueue. عندما يكون head.next == الأخير ، فهذا يعني أنه تم حذف العنصر الأخير. عندما يكون head.next == null ، لا يمكن حذفه لأن القائمة المرتبطة فارغة بالفعل. لا يوجد حكم هنا لأن الحكم قد تم إصداره في المكان الذي تسمى طريقة Dequeue.
2
نظرًا لأن قائمة انتظار الحظر يجب أن يتم حظرها وانتظرها عندما تكون قائمة الانتظار فارغة وتكون قائمة الانتظار ممتلئة ، فهذا مطلوبان بشكل طبيعي. من أجل ضمان سلامة التزامن متعدد الخيوط ، هناك حاجة إلى قفل المزامنة. وقد قيل هذا في arrayblockingqueue.
سنتحدث هنا عن الأشياء المختلفة حول LinkedBlockingQueue.
/ ** قفل حصري ، يستخدم للتعامل مع مشاكل التزامن لإدخال عمليات قائمة الانتظار ، أي وضع وتقديم عمليات*/ private reentrantlock putlock = جديد reentrantlock () ؛ / ** شرط الشرط الذي لا يرضي فيه قائمة الانتظار ، يتم إنشاؤه بواسطة قفل putlock*/ الشرط النهائي الخاص nustfull = putlock.newcondition () ؛ / ** قفل حصري ، يستخدم للتعامل مع مشاكل التزامن لحذف عمليات رأس قائمة الانتظار ، أي عمليات الاستيلاء والاستطلاع*/ reentrantlock takelock النهائي الخاص = جديد reentrantlock () ؛ / ** حالة شرط عدم وجود قائمة الانتظار فارغة ، فإنها تستخدم الحالة النهائية الخاصة التي تم إنشاؤها بواسطة Takelock Lock*/ Private Final Condition Notempty = takelock.newcondition () ؛
2.1 Putlock و Takelock
وجدنا قفلان مستخدمان:
وفقًا للبيان أعلاه ، قد تكون هناك عمليات إدراج وحذف العناصر في نفس الوقت ، فهل ستكون هناك مشكلة؟
دعنا نحللها بالتفصيل. لقوائم الانتظار ، تنقسم العمليات إلى ثلاثة أنواع:
لذلك ، استخدم قفل Putlock للحفاظ على آخر متغير آمن ، واستخدم قفل Takelock للحفاظ على آمنة متغير الرأس.
بالنسبة لجميع متغيرات العد المشاركة في عدد العناصر في قائمة الانتظار ، يتم استخدام AtomicInteger لضمان مشكلات أمان التزامن.
/ ** عدد العناصر في قائمة الانتظار ، استخدم متغير AtomicInteger هنا لضمان مشكلات أمان التزامن*/ COUNT ATOMICINTEGER النهائي الخاص = New AtomicInteger () ؛
2.2 notfull و notfermty
2.3 عملية التحكم
عند إدخال عنصر:
عند حذف العناصر:
لاحظ أيضًا أنه يجب استدعاء طرق الشرط وانتظارها عند الحصول على قفل. لذلك ، هناك طرق إشارة و notenotfull:
/*** استيقظ الخيط الذي ينتظر تحت حالة عدم الالتزام ، أي عند إزالة رأس قائمة الانتظار ، فإن الخيط الذي وجد أنه فارغ ومجبر على الانتظار. * لاحظ أنه بسبب استدعاء طريقة الإشارة للحالة ، يجب الحصول على القفل المقابل ، يتم استدعاء طريقة takelock.lock () هنا. * عند إدراج عنصر ما في قائمة الانتظار (أي وضع أو عرض العرض) ، فإن قائمة الانتظار ليست فارغة بالتأكيد ، وسيتم استدعاء هذه الطريقة. */ private void signalNotempty () {النهائي reentrantlock takelock = this.takelock ؛ takelock.lock () ؛ حاول {notempty.signal () ؛ } أخيرًا {takelock.unlock () ؛ }} /*** استيقظ الخيط الذي ينتظر تحت الحالة المستحقة ، أي عند إضافة العنصر في نهاية قائمة الانتظار ، فإن الخيط ممتلئ ومجبر على الانتظار. * لاحظ أنه نظرًا لاستدعاء طريقة الإشارة للحالة ، يجب الحصول على القفل المقابل ، لذلك يتم استدعاء طريقة putClock.lock () هنا* عندما يتم حذف العنصر (أي أخذ أو تشغيل الاستطلاع) في قائمة الانتظار ، سيكون قائمة الانتظار بالتأكيد غير راضية وستسمي هذه الطريقة. */ private void signalNotfull () {Final reentrantlock putlock = this.putlock ؛ putlock.lock () ؛ حاول {notfull.signal () ؛ } أخيرًا {putlock.unlock () ؛ }}3. إدراج طريقة عنصر
Public void pum (e e) رميات interruptedException {if (e == null) رمي nullpointerxception () ؛ // سجل عدد العناصر قبل عملية الإدراج int c = -1 ؛ // قم بإنشاء عقدة عقدة جديدة <e> node = node node <e> (e) ؛ reentrantlock النهائي putlock = this.putlock ؛ عدد AtomicInteger النهائي = this.count ؛ putlock.lockInterruptly () ؛ حاول {// تشير إلى أن قائمة الانتظار ممتلئة ، فأنت بحاجة إلى استدعاء طريقة notfull.await لجعل مؤشر الترابط الحالي ينتظر بينما (count.get () == السعة) {notull.await () ؛ } // إدراج عنصر جديد enqueue (العقدة) ؛ // أضف 1 إلى عدد العناصر في قائمة الانتظار الحالية وإرجاع عدد العناصر قبل إضافة 1. c = count.getandincrement () ؛ // c + 1 <السعة يعني أن قائمة الانتظار ليست ممتلئة ، وأن الخيط الذي قد ينتظر عملية الإدراج يتم إيقاظه إذا (c + 1 <coutpt) notfl.signal () ؛ } أخيرًا {putlock.unlock () ؛ } // c == 0 يعني أن قائمة الانتظار فارغة قبل الإدراج. عندما تكون قائمة الانتظار فارغة لعنصر يتم وضعه ، // استيقظ الخيط في انتظار الحذف // منع الاستحواذ المتكرر لأقفال Takelock ، يستهلك الأداء إذا (C == 0) SignalNotempty () ؛ }أخذ طريقة PUT كمثال ، فإن العملية العامة هي نفسها كما قدمنا سابقًا. هنا رمز غريب جدا. عند إدراج العنصر ، إذا وجدت أن قائمة الانتظار ليست ممتلئة ، فاستدعاء notfl.signal () لإيقاظ الموضوع في انتظار الإدراج.
الجميع مرتبكون للغاية. بشكل عام ، يجب وضع هذه الطريقة في عنصر الحذف (خذ طريقة السلسلة) ، لأنه عندما نحذف عنصرًا ، يجب أن تكون قائمة الانتظار غير ممتلئة ، ثم استدعاء طريقة notfull.signal () لإيقاظ مؤشر الترابط في انتظار الإدراج.
يتم ذلك بشكل أساسي هنا لأنه عند استدعاء طريقة الإشارة ، يجب الحصول على القفل المقابل أولاً. القفل المستخدم في طريقة Take Series هو Takelock. إذا كنت ترغب في استدعاء طريقة notfull.signal () ، فيجب عليك أولاً الحصول على قفل putlock. سيؤدي ذلك إلى انخفاض الأداء ، لذلك يتم استخدام طريقة أخرى.
4. حذف عنصر رأس قائمة الانتظار
public e take () رميات interruptedException {e x ؛ int c = -1 ؛ عدد AtomicInteger النهائي = this.count ؛ النهائي reentrantlock takelock = this.takelock ؛ takelock.lockInterruptly () ؛ جرب {// يعني أن قائمة الانتظار فارغة ، فأنت بحاجة إلى استدعاء طريقة notempty.await لجعل مؤشر الترابط الحالي ينتظر (count.get () == 0) {notempty.await () ؛ } // حذف عنصر رأس قائمة الانتظار وإعادته x = dequeue () ؛ // إرجاع عدد قوائم الانتظار الحالية ، ثم قم بطرح عدد قوائم الانتظار بواسطة C = count.getAndDecrement () ؛ // c> 1 يعني أن قائمة الانتظار ليست فارغة ، لذلك يستيقظ على الخيط الذي قد ينتظر عملية الحذف إذا (c> 1) notempty.signal () ؛ } أخيرًا {takelock.unlock () ؛ } /*** c == السعة تعني أن قائمة الانتظار ممتلئة قبل عملية الحذف. * استيقظ الخيط في انتظار الإدراج فقط عندما يتم حذف عنصر من قائمة الانتظار الكاملة* يمنع الاستحواذ المتكرر لأقفال putlock ، والاستهلاك الأداء*/ if (c == السعة) SignalNotfull () ؛ إرجاع x ؛ }لماذا تسمى طريقة notempty.signal () ، قارن تفسيرنا في طريقة عنصر الإدراج.
5. عرض عناصر رأس قائمة الانتظار
// عرض عنصر Queue header public e peek () {// قائمة الانتظار فارغة ، وإرجاع null if (count.get () == 0) return null ؛ النهائي reentrantlock takelock = this.takelock ؛ takelock.lock () ؛ حاول {// الحصول على عقدة رأس قائمة الانتظار الأولى <e> first = head.next ؛ // أولاً == NULL يعني أن قائمة الانتظار فارغة ، وإرجاع فارغة إذا (أولاً == null) إرجاع NULL ؛ Else // إرجاع عنصر قائمة الانتظار للعودة أولاً. } أخيرًا {takelock.unlock () ؛ }}عرض عنصر رأس قائمة الانتظار ، والذي يتضمن عقدة الرأس ، لذلك يجب استخدام قفل Takelock.
السادس. طرق مهمة أخرى
6.1 إزالة (الكائن O) طريقة
// قم بإزالة العنصر المحدد من قائمة الانتظار O Boolean Public Remove (Object O) {if (o == null) return false ؛ // لأنه ليس حذف عنصر رأس القائمة ، يجب أن يكون المتغيران رأسًا وآخرًا ، // putlock و takelock مغلقان بشكل كامل () ؛ جرب {// Traverse قائمة الانتظار بأكملها ، تمثل p العقدة الحالية ، ويمثل المسار العقدة السابقة للعقدة الحالية // لأنها قائمة مرتبطة في اتجاه واحد ، يجب تسجيل عقدتين لـ (Node <e> trail = head ، p = trail.next ؛ p! = null ؛ {unlink (p ، trail) ؛ العودة صحيح. }} إرجاع خطأ ؛ } أخيرًا {commonunlock () ؛ }}حذف العنصر المحدد من القائمة. نظرًا لأن العنصر المحذوف ليس بالضرورة في رأس القائمة ، فقد يكون هناك اثنين من المتغيرين رأسًا وأخيراً ، لذلك يجب عليك استخدام كل من أقفال Putlock و Takelock في نفس الوقت. نظرًا لأنه قائمة مرتبطة في اتجاه واحد ، هناك حاجة إلى مسار متغير إضافي لتسجيل العقدة السابقة بحيث يمكن حذف العقدة الحالية P.
6.2 طريقة غير متوفرة (عقدة <e> p ، العقدة <e> trail)
. // هذا يحذف العقدة p trail.next = p.next ؛ // إذا كانت العقدة P هي الأخيرة الأخيرة من قائمة الانتظار وتم حذفها ، فقم بتعيين المسار إلى آخر إذا (Last == P) Last = Trail ؛ // قم بطرح عدد العناصر بواحدة ، إذا كانت قائمة الانتظار الأصلية ممتلئة ، فاستدعاء طريقة notfull.signal () // في الواقع ، وهذا ما يسمى مباشرة دون حكم ، لأنه يجب الحصول على قفل putlock هنا إذا (count.getAndDecrement () == COTER) }
لحذف عقدة P في القائمة المرتبطة ، تحتاج فقط إلى توجيه إلى التالي من مسار العقدة السابق لـ P إلى العقدة التالية من العقدة P.
ما سبق هو كل محتوى هذه المقالة. آمل أن يكون ذلك مفيدًا لتعلم الجميع وآمل أن يدعم الجميع wulin.com أكثر.