في الفصل السابق ، قدمنا لطفاء قائمة انتظار الحظر. أدناه نقدم ArrayBlockingqueue فئة التنفيذ المستخدمة بشكل شائع.
1. استخدم المصفوفات لتنفيذ قوائم الانتظار
نظرًا للمتطلبات الخاصة لهيكل بيانات قائمة الانتظار ، فمن المناسب بشكل طبيعي تنفيذها في شكل قائمة مرتبطة. يتم استخدام متغيرين لتسجيل الرأس ونهاية القائمة المرتبطة على التوالي. عند حذف أو إدخال قائمة الانتظار ، ما عليك سوى تغيير رأس أو نهاية القائمة المرتبطة. علاوة على ذلك ، ترتبط القائمة المرتبطة بطريقة مرجعية ، وبالتالي فإن قدرتها غير محدودة تقريبًا.
لذا ، كيفية استخدام المصفوفات لتنفيذ قوائم الانتظار ، نحتاج إلى أربعة متغيرات: كائن [] صفيف لتخزين العناصر في قائمة الانتظار ، و HeadIndex و Tailindex يسجلون رأس قائمة الانتظار وذيل ، وتسجيل عدد قوائم الانتظار.
يتم استخدام طريقة ذكية جدا هنا. نعلم أنه عندما يتم إدراج عنصر في قائمة الانتظار ، فإنه يشغل موقفًا في الصفيف. عند حذف عنصر ما ، يكون موضع الصفيف مجانيًا بالفعل ، مما يشير إلى أنه يمكن إدراج عنصر جديد في هذا الموضع.
لذلك قبل أن نقوم بإدراج عنصر جديد ، يجب علينا التحقق مما إذا كانت قائمة الانتظار ممتلئة ، وقبل حذف العنصر ، يجب علينا التحقق مما إذا كانت قائمة الانتظار فارغة.
2. متغيرات الأعضاء المهمة في arrayblockingqueue
/ ** قم بتخزين العناصر الموجودة في قائمة الانتظار*/ الكائن النهائي [] ؛ / ** موضع رأس قائمة الانتظار*/ int takeindex ؛ / ** موضع ذيل قائمة الانتظار*/ int putIndex ؛ / ** عدد العناصر في قائمة الانتظار الحالية*/ int ؛ / ** يستخدم لضمان أمان المتغيرات المشتركة متعددة الخيوط*/ قفل إعادة إيندرانتلوك النهائي ؛ / ** عندما تكون قائمة الانتظار فارغة ، سيتم استدعاء طريقة الانتظار لـ NONFEMPTY لجعل الخيط الحالي WAIT*/ Private Final Condition Notempty ؛ / ** عندما تكون قائمة الانتظار ممتلئة ، سيتم استدعاء طريقة الانتظار لـ Nustfull ، مما يتسبب في انتظار الخيط الحالي*/ الحالة النهائية الخاصة
هناك المزيد من المتغيرات القفل والإلغاء والمتغيرات البارزة لتنفيذ ظروف السلامة متعددة الخيوط وانتظار الخيوط. كيف تعمل؟
2.1 دور القفل
نظرًا لأن ArrayBlockingseue تعمل ضمن مؤشرات ترابط متعددة ، عند تعديل متغيرات الأعضاء مثل العناصر ، و takeindex ، و putIndex و count ، يجب النظر في مشكلات السلامة متعددة الخيوط. لذلك ، يتم استخدام القفل الحصري هنا لضمان سلامة العمليات المتزامنة.
2.2 دور الإلغاء واللاحظ
نظرًا لأنه يجب تنفيذ قوائم الانتظار ، عندما تكون قائمة الانتظار فارغة أو أن تكون قائمة الانتظار ممتلئة ، يجب أن تنتظر قائمة الانتظار أو إدراج عملية الإدراج. لذلك فكرنا في كائن الحالة تحت إطار التزامن واستخدامه للسيطرة عليه.
في AQS ، نقدم دور هذه الفئة:
3. إضافة طريقة العنصر
3.1 إضافة (e e) وعرض الأساليب (e e):
// استدعاء الطريقة في فئة الوالدين الملخص. إضافة منطقية عامة (e e) {// تنفيذ if (عرض (e)) إرجاع true ؛ آخر رمي جديد غير قانوني stateException ("قائمة الانتظار كاملة") ؛ } // إضافة عنصر جديد إلى نهاية قائمة الانتظار. الإرجاع الحقيقي يعني أن الإضافة ناجحة ، والكاذبة تعني فشل الإضافة ، ولم يتم إلقاء أي استثناء عرض منطقي عام (e e) {checkNotnull (e) ؛ القفل النهائي لإعادة الدخول = this.lock ؛ // استخدم القفل للتأكد من تعديل سمات الأعضاء متعددة الخيوط. جرب {// قائمة الانتظار ممتلئة ، وإضافة العناصر تفشل ، وإرجاع خطأ. if (count == items.length) return false ؛ آخر {// استدعاء طريقة enqueue لإدراج العنصر في قائمة الانتظار enqueue (e) ؛ العودة صحيح. }} أخيرًا {lock.unlock () ؛ }}يتم تنفيذ طريقة إضافة عن طريق استدعاء طريقة العرض. في طريقة العرض ، من الضروري تحديد ما إذا كانت قائمة الانتظار ممتلئة. إذا كان ممتلئًا ، فسيعود مباشرة إلى خطأ دون حظر الخيط الحالي. إذا لم تكن راضيًا ، فاتصل بالطريقة enqueue لإدراج العنصر في قائمة الانتظار.
ملاحظة: يضمن استخدام Lock.lock () هنا أن متغيرات عضو واحد فقط في مؤشر ترابط واحد في نفس الوقت لمنع مشاكل التشغيل المتزامنة. على الرغم من أنه سيمنع الخيط الحالي أيضًا ، إلا أنه ليس انتظارًا مشروطًا ، إلا أنه فقط لأن القفل يحتفظ به مؤشرات الترابط الأخرى ، ووقت تشغيل الطريقة في ArrayBlockingeue ليس طويلًا ، وهو ما يعادل عدم حظر الخيط.
3.2 وضع الطريقة
// إضافة عنصر جديد إلى نهاية قائمة الانتظار. إذا كانت قائمة الانتظار ممتلئة ، فسوف ينتظر الخيط الحالي. استجابة لمقاطعة استثناء الفراغ العام وضع (e e) رميات interruptedException {checkNotnull (e) ؛ القفل النهائي لإعادة الدخول = this.lock ؛ // استخدم القفل للتأكد من تعديل الأطراف المتعددة أمان سمات الأعضاء lock.lockinterruptilely () ؛ جرب {// إذا كانت قائمة الانتظار ممتلئة ، اتصل بالطريقة notfull.await () للسماح لخيط الخيط الحالي بالانتظار حتى لا يكون قائمة الانتظار ممتلئة (count == items.length) notull.await () ؛ // استدعاء طريقة enqueue لإدخال العنصر في قائمة الانتظار enqueue (e) ؛ } أخيرًا {lock.unlock () ؛ }}العملية العامة لطريقة العرض هي نفس طريقة العرض. ومع ذلك ، عندما تكون قائمة الانتظار ممتلئة ، سيتم استدعاء طريقة notfull.await () لعمل كتلة الخيط الحالية والانتظار حتى تتم إزالة قائمة الانتظار بواسطة مؤشرات ترابط أخرى. عندما يكون قائمة الانتظار غير راضية ، سيتم إيقاظ موضوع الانتظار.
3.3 عرض (E E ، Timeout ، وحدة TimeUnit) طريقة
/*** إضافة عنصر جديد إلى نهاية قائمة الانتظار. إذا لم يكن هناك مساحة متوفرة في قائمة الانتظار ، فسينتظر الخيط الحالي. * إذا تجاوز وقت الانتظار المهلة ، فسيتم إرجاع خطأ ، مما يشير إلى أن الإضافة فشلت*/ عرض منطقي عام (E e ، ant timeout ، وحدة التوقيت الزمني) رمي interruptedException {checknotnull (e) ؛ . القفل النهائي لإعادة الدخول = this.lock ؛ // استخدم القفل للتأكد من تعديل سمات الأعضاء متعددة الخيوط. جرب {// قائمة الانتظار ممتلئة بينما (count == items.length) {// nanos <= 0 يعني أن الحد الأقصى لوقت الانتظار قد وصل ، لذلك ليست هناك حاجة للانتظار لفترة أطول. إرجاع خطأ ، مما يشير إلى أن الإضافة فشلت. إذا (nanos <= 0) العودة خطأ ؛ // استدعاء طريقة notfull.awaitnanos (nanos) ، سيتم إيقاظ وقت timeout nanos تلقائيًا. // إذا تم استبعاده مسبقًا ، فسيتم إرجاع الوقت المتبقي nanos = notfl.awaitnanos (nanos) ؛ } // استدعاء طريقة enqueue لإدراج العنصر في قائمة الانتظار enqueue (e) ؛ العودة صحيح. } أخيرًا {lock.unlock () ؛ }}إن التدفق العام لطريقة PUT هو نفس طريقة PUT ، فهو يطلق على طريقة notfull.awaitnanos (nanos) لجعل الخيط الحالي ينتظر وضبط وقت الانتظار.
4. حذف طريقة العناصر
4.1 إزالة () وطلاب الاستطلاع () الأساليب:
// استدعاء الطريقة في فئة الوالدين الملخص. public e remove () {// التنفيذ عن طريق استدعاء الاستطلاع e x = poll () ؛ if (x! = null) return x ؛ آخر رمي nosuchelementException () ؛ } // حذف العنصر الأول من قائمة الانتظار (أي رأس قائمة الانتظار) وإعادته. إذا كانت قائمة الانتظار فارغة ، فإنها لا ترمي استثناء ، ولكنها تعيد NULL. Public E Poll () {Final Reentrantlock Lock = this.lock ؛ // استخدم القفل للتأكد من تعديل سمات الأعضاء متعددة الخيوط. جرب {// if count == 0 والقائمة فارغة ، إرجاع فارغة. خلاف ذلك ، اتصل بالطريقة dequeue لإرجاع عنصر رأس القائمة (العد == 0)؟ null: dequeue () ؛ } أخيرًا {lock.unlock () ؛ }}يتم تنفيذ طريقة إزالة عن طريق استدعاء طريقة الاستطلاع (). في طريقة الاستطلاع () ، إذا كانت القائمة فارغة ، فإنها تُرجع فارغة ، وإلا يتم استدعاء طريقة dequeue لإرجاع عنصر رأس القائمة.
4.2 خذ () طريقة
/*** إرجاع وإزالة العنصر الأول من قائمة الانتظار. إذا كانت قائمة الانتظار فارغة ، فسوف ينتظر الخيط الأمامي. استثناء مقاطعة الاستجابة*/ public e take () رميات interruptedException {Final reentrantlock lock = this.lock ؛ // استخدم القفل للتأكد من تعديل الأطراف المتعددة أمان سمات الأعضاء lock.lockinterruptilely () ؛ جرب {// إذا كانت قائمة الانتظار فارغة ، فاتصل بالطريقة notempty.await () للسماح للموضوع الحالي بالانتظار. // حتى يقوم مؤشر ترابط آخر بإدراج عناصر في قائمة الانتظار ، سيتم إيقاظ الخيط. بينما (count == 0) notempty.await () ؛ // استدعاء طريقة dequeue لإرجاع عنصر رأس القائمة إرجاع dequeue () ؛ } أخيرًا {lock.unlock () ؛ }}عندما تكون طريقة take () فارغة ، يجب أن ينتظر مؤشر الترابط الحالي حتى يقوم مؤشر ترابط آخر بإدراج عنصر جديد في قائمة الانتظار ، وسيتم إيقاظ مؤشر الترابط.
4.3 استطلاع (فترة طويلة ، وحدة الوقت)
/*** إرجاع وإزالة العنصر الأول من قائمة الانتظار. إذا كانت قائمة الانتظار فارغة ، فسوف ينتظر الخيط الأمامي. * إذا تجاوز وقت الانتظار المهلة ، فسيتم إرجاع خطأ في الإشارة إلى أن العنصر قد فشل*/ استطلاع عام عام (مهلة طويلة ، وحدة TimeUnit) يلقي interruptedException {// احسب القيمة القصوى لوقت الانتظار في إجمالي nanos nanos الطويل = unit.tonanos (timeout) ؛ القفل النهائي لإعادة الدخول = this.lock ؛ // استخدم القفل للتأكد من تعديل سمات الأعضاء متعددة الخيوط. جرب {// قائمة الانتظار فارغة بينما (count == 0) {// nanos <= 0 يعني أن الحد الأقصى لوقت الانتظار قد وصل ، لذلك لم يعد هناك حاجة للانتظار بعد الآن. إذا (nanos <= 0) إرجاع فارغ ؛ // استدعاء طريقة notempty.awaitnanos (nanos) لجعل موضوع الجدول الانتظار وتعيين وقت المهلة. nanos = notempty.awaitnanos (nanos) ؛ } // استدعاء طريقة dequeue لإرجاع عنصر رأس القائمة Dequeue () ؛ } أخيرًا {lock.unlock () ؛ }}تمامًا مثل عملية Take () ، يطلق عليها فقط طريقة Awaitnanos (nanos) لجعل الخيط الحالي ينتظر وضبط وقت الانتظار.
5. طرق عرض العناصر
5.1 element () و PEEK () طرق
// استدعاء الطريقة في فئة الوالدين الملخص. e element e public () {e x = peek () ؛ if (x! = null) return x ؛ آخر رمي nosuchelementException () ؛ }. // استخدم القفل للتأكد من تعديل سمات الأعضاء متعددة الخيوط. حاول {// إرجاع عنصر إرجاع رأس قائمة الانتظار الحالي (TakeIndex) ؛ // null عندما تكون قائمة الانتظار فارغة} أخيرًا {lock.unlock () ؛ }}السادس. طرق مهمة أخرى
6.1 طرق enqueue و dequeue
// إدراج العنصر x في ذيل قائمة الانتظار الخاصة enqueue enqueue (e x) {// assert lock.getholdcount () == 1 ؛ // تأكيد العناصر [putIndex] == null ؛ // يجب أن يكون عنصر موضع putIndex الحالي هو الكائن النهائي الفارغ [] عناصر = this.items ؛ العناصر [putIndex] = x ؛ // إذا كان putIndex يساوي العناصر. // إضافة عدد واحد ++ إلى عدد قوائم الانتظار ؛ // لأنه يتم إدخال عنصر ، فإن قائمة الانتظار الحالية ليست فارغة بالتأكيد. ثم استيقظ على موضوع ينتظر تحت حالة غير مألوفة 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 ؛ // ناقص عدد قوائم الانتظار من قبل واحد-؛ if (itrs! = null) itrs.elementDequeued () ؛ // لأنه يتم حذف عنصر ما ، فإن قائمة الانتظار غير راضية بالتأكيد ، لذا استيقظ على موضوع ينتظر تحت حالة notfull.signal () ؛ إرجاع x ؛ }تمثل هاتان الطريقتان ، إدخال العناصر في العناصر وإزالتها من قائمة الانتظار ، على التوالي. وهم يريدون أن يستيقظوا خيط الانتظار. بعد إدخال عنصر ما ، يجب ألا تكون قائمة الانتظار فارغة ، لذلك يجب إيقاظ الخيط الذي ينتظر في حالة شرط غير مألوف. بعد حذف العنصر ، يجب أن تكون قائمة الانتظار غير راضية ، لذلك يجب إيقاظ الخيط الذي ينتظر في ظل الحالة المستحقة.
6.2 إزالة (كائن O) طريقة
// حذف عنصر الكائن O في قائمة الانتظار ، وحذفه في معظم المنطقي العام واحد (كائن O) {if (o == null) إرجاع false ؛ الكائن النهائي [] عناصر = this.items ؛ // استخدم القفل لضمان أمان التعديل متعدد الخيوط لسمات الأعضاء النهائية لإعادة إدخال القفل = this.lock ؛ lock.lock () ؛ حاول {// حذف فقط عندما تكون هناك قيمة في قائمة الانتظار. if (count> 0) {// الموضع التالي في نهاية قائمة الانتظار النهائية int putIndex = this.putIndex ؛ // موضع رأس قائمة الانتظار int i = takeindex ؛ do {// عنصر الموضع الحالي هو نفسه العنصر المحذوف إذا (O.equals (العناصر [i])) {// حذف عنصر الموضع i releveat (i) ؛ // إرجاع حقيقية حقيقية ؛ } if (++ i == items.length) i = 0 ؛ // عندما i == putIndex يعني أن جميع العناصر قد تم اجتيازها} بينما (i! = putIndex) ؛ } إرجاع خطأ ؛ } أخيرًا {lock.unlock () ؛ }} احذف الكائن المحدد O من قائمة الانتظار ، ثم عليك اجتياز قائمة الانتظار وحذف العنصر الأول الذي هو نفس الكائن O. إذا لم يكن هناك عنصر كائن O في قائمة الانتظار ، فأرد FALSE إلى DELETE فشل.
فيما يلي نقطتان يجب ملاحظة:
كيفية اجتياز قائمة الانتظار هي اجتياز رأس قائمة الانتظار حتى نهاية قائمة الانتظار. يعتمد ذلك على المتغيرين اللذين يتناولان و putIndex.
لماذا الكائن [] العناصر = this.items ؛ لا يتم وضع هذا الرمز في كتلة رمز قفل القفل المتزامن. العناصر هي متغيرات الأعضاء. عندما يكون هناك الكثير من المواضيع ، ألا توجد مشاكل في التزامن؟
وذلك لأن العناصر هي متغيرات مرجعية ، وليس أنواع البيانات الأساسية ، ولا يتم تغيير عمليات الإدراج والحذف الخاصة بنا في قوائم الانتظار ، ولا يتم تغيير الإشارة إلى الصفيف. لذلك ، في رمز القفل ، ستحصل العناصر على أحدث التعديلات عليها بواسطة مؤشرات الترابط الأخرى. ولكن إذا putIndex int = this.putIndex ؛ الطريقة تغلق كتلة الكود في الخارج ، ستحدث مشكلة.
طريقة lexoveeat (int removeIndex النهائي)
// حذف العنصر في قائمة الانتظار removeIndex posital void removeeat (int removeIndex) {// assert lock.getholdcount () == 1 ؛ // تأكيد العناصر [removeIndex]! = null ؛ // تأكيد removeIndex> = 0 && removeIndex <items.length ؛ الكائن النهائي [] عناصر = this.items ؛ // هذا يعني أنه من الأسهل بكثير حذف العنصر كرأس القائمة ، وهو ما يشبه عملية dequeue if (removeIndex == takeIndex) {// قم بإزالة العنصر في عناصر موضع removeIndex [takeIndex] = null ؛ // عندما تكون نهاية الصفيف ، تحتاج إلى الانتقال إلى موضع رأس الصفيف إذا (++ takeindex == items.length) takeIndex = 0 ؛ // ناقص عدد قوائم الانتظار من قبل واحد-؛ if (itrs! = null) itrs.elementDequeued () ؛ } آخر {// "الداخلية" إزالة int final putIndex = this.putIndex ؛ لـ (int i = removeIndex ؛؛) {int next = i + 1 ؛ إذا (التالي == items.length) التالي = 0 ؛ // لم تصل نهاية قائمة الانتظار بعد إلى نهاية قائمة الانتظار ، ثم يتم كتابة العنصر في الموضع التالي بواسطة العنصر في الموضع السابق إذا (التالي! = putIndex) {عناصر [i] = العناصر [التالي] ؛ أنا = التالي ؛ } آخر {// قم بتعيين عنصر الذيل لعناصر قائمة الانتظار الخالية [i] = null ؛ // إعادة تعيين قيمة putIndex this.putIndex = i ؛ استراحة؛ }} // انخفض عدد قوائم الانتظار عن طريق العد-؛ if (itrs! = null) itrs.removeDat (removeIndex) ؛ } // لأنه يتم حذف عنصر ، فإن قائمة الانتظار غير راضية بالتأكيد ، لذا استيقظ مؤشر ترابط ينتظر تحت حالة notull.signal () ؛ }حذف العناصر في الموقع المحدد في قائمة الانتظار. تجدر الإشارة إلى أن الصفيف بعد الحذف لا يزال بإمكانه الحفاظ على نموذج قائمة الانتظار ، والذي ينقسم إلى حالتين:
ما سبق هو كل محتوى هذه المقالة. آمل أن يكون ذلك مفيدًا لتعلم الجميع وآمل أن يدعم الجميع wulin.com أكثر.