نظام انتظار عادل

📅 آخر تحديث: ١ أغسطس ٢٠٢٦
✍️ نُشر في: ١ أغسطس ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة

تُعدّ خوارزمية جدولة المهام العادلة مجموعة من خوارزميات الجدولة المستخدمة في بعض برامج جدولة العمليات والشبكات . صُممت هذه الخوارزمية لتحقيق العدالة عند مشاركة مورد محدود، على سبيل المثال لمنع تدفقات البيانات ذات الحزم الكبيرة أو العمليات التي تُنتج مهامًا صغيرة من استهلاك إنتاجية أو وقت وحدة المعالجة المركزية أكثر من تدفقات البيانات أو العمليات الأخرى.

يتم تطبيق نظام الانتظار العادل في بعض محولات وموجهات الشبكة المتقدمة .

تاريخ

صاغ جون ناجل مصطلح " الانتظار العادل" عام 1985 عندما اقترح جدولة التناوب الدوري في البوابة بين الشبكة المحلية والإنترنت للحد من انقطاع الشبكة الناتج عن الأجهزة المضيفة سيئة السلوك. [ 1 ] [ 2 ] [ 3 ]

اقترح آلان ديمرز وسرينيفاسان كيشاف وسكوت شينكر نسخةً مُرجّحةً بالبايت في عام 1989، واستندت هذه النسخة إلى خوارزمية ناغل السابقة للترتيب العادل للحزم. [ 4 ] [ 5 ] تهدف خوارزمية الترتيب العادل المُرجّحة بالبايت إلى محاكاة تعدد الإرسال بت-بت عن طريق حساب تاريخ المغادرة النظري لكل حزمة.

وقد تم تطوير المفهوم بشكل أكبر إلى نظام الانتظار العادل الموزون ، والمفهوم الأكثر عمومية لتشكيل حركة المرور ، حيث يتم التحكم في أولويات الانتظار بشكل ديناميكي لتحقيق أهداف جودة الخدمة المطلوبة أو تسريع بعض التدفقات.

مبدأ

تستخدم آلية التوزيع العادل للصفوف طابورًا واحدًا لكل تدفق حزم ، وتخدمها بالتناوب، بحيث يمكن لكل تدفق "الحصول على جزء متساوٍ من الموارد". [ 1 ] [ 2 ]

تتمثل الميزة على نظام "الأول في الأول خارج " التقليدي أو نظام قائمة الانتظار ذات الأولوية في أن تدفق البيانات عالي السرعة، الذي يتكون من حزم كبيرة أو العديد من حزم البيانات، لا يمكنه أن يأخذ أكثر من حصته العادلة من سعة الرابط.

تُستخدم آلية التوزيع العادل للبيانات في أجهزة التوجيه والمحولات ومضاعفات الإرسال الإحصائية التي تُعيد توجيه الحزم من مخزن مؤقت . يعمل المخزن المؤقت كنظام توزيع، حيث تُخزن حزم البيانات مؤقتًا حتى يتم إرسالها.

بمعدل نقل بيانات للرابط يبلغ R ، يتم في أي لحظة معينة خدمة N تدفق بيانات نشط (التي تحتوي على قوائم انتظار غير فارغة) بمعدل بيانات متوسط ​​قدره R/N . قد يتذبذب معدل نقل البيانات حول هذه القيمة خلال فترة زمنية قصيرة نظرًا لتسليم الحزم بالتتابع.

الإنصاف

في سياق جدولة الشبكات، تتعدد تعريفات العدالة . تستخدم مقالة ناجل جدولة التناوب الدوري للحزم، [ 2 ] وهي عادلة من حيث عدد الحزم، ولكنها غير عادلة من حيث استخدام النطاق الترددي عندما تختلف أحجام الحزم. وقد تم تعريف العديد من المفاهيم الرسمية لقياس العدالة، بما في ذلك عدالة الحد الأقصى والأدنى ، وعدالة أسوأ الحالات ، [ 6 ] ومؤشر العدالة . [ 7 ]

تعميم على المشاركة المرجحة

تُعطي الفكرة الأساسية نفس المعدل لكل تدفق. ويتمثل التوسع الطبيعي في السماح للمستخدم بتحديد جزء النطاق الترددي المخصص لكل تدفق، مما يؤدي إلى ترتيب عادل مُرجّح في قائمة الانتظار ومشاركة مُعمّمة للمعالج .

خوارزمية طابور عادلة موزونة بالبايت

تحاول هذه الخوارزمية محاكاة عدالة مشاركة موارد الروابط بالتناوب بين التدفقات المتنافسة. مع ذلك، يجب إرسال التدفقات القائمة على الحزم بشكل متسلسل. تختار خوارزمية الترتيب العادل الموزون بالبايت ترتيب إرسال الحزم من خلال نمذجة وقت انتهاء كل حزمة كما لو كان من الممكن إرسالها بالتناوب. الحزمة ذات وقت الانتهاء الأقرب وفقًا لهذه النمذجة هي التي يتم اختيارها للإرسال التالي.

تعقيد الخوارزمية هو O(log(n)) ، حيث n هو عدد الطوابير / التدفقات.

تفاصيل الخوارزمية

على الرغم من إمكانية نمذجة وقت الانتهاء الفعلي، إلا أنها تتطلب موارد حاسوبية كبيرة. إذ يجب إعادة حساب النموذج بشكل كبير في كل مرة يتم فيها اختيار حزمة بيانات للإرسال، وفي كل مرة تصل فيها حزمة بيانات جديدة إلى أي قائمة انتظار.

لتقليل الحمل الحسابي، تم تقديم مفهوم الزمن الافتراضي . يُحسب وقت انتهاء كل حزمة بيانات على هذا المقياس الزمني الافتراضي البديل المتزايد بشكل رتيب. مع أن الزمن الافتراضي لا يُحاكي بدقة وقت إتمام الحزم لعمليات الإرسال، إلا أنه يُحاكي بدقة ترتيب عمليات الإرسال اللازمة لتحقيق أهداف النموذج الكامل. باستخدام الزمن الافتراضي، لا حاجة لإعادة حساب وقت انتهاء الحزم الموجودة مسبقًا في قائمة الانتظار. على الرغم من أن وقت انتهاء الحزم الموجودة، من حيث القيمة المطلقة، قد يتأثر بالحزم الجديدة، إلا أن وقت الانتهاء على خط الزمن الافتراضي يبقى ثابتًا - إذ يتغير خط الزمن الافتراضي بالنسبة للوقت الحقيقي لاستيعاب أي عملية إرسال جديدة.

يُحسب وقت الانتهاء الافتراضي لحزمة بيانات جديدة في قائمة الانتظار بجمع وقت البدء الافتراضي مع حجم الحزمة. ووقت البدء الافتراضي هو القيمة القصوى بين وقت الانتهاء الافتراضي السابق لنفس قائمة الانتظار واللحظة الحالية.

بعد حساب وقت الانتهاء الافتراضي لجميع الحزم المرشحة (أي الحزم الموجودة في بداية جميع قوائم انتظار التدفق غير الفارغة)، تقارن آلية التوزيع العادل وقت الانتهاء الافتراضي وتختار الأقل. ثم يتم إرسال الحزمة ذات أقل وقت انتهاء افتراضي.

الشفرة الزائفة

المتغيرات المشتركة const N // عدد الطوابير queues[1..N] // queues lastVirFinish[1..N] // آخر لحظة انتهاء افتراضية
استلام (حزمة) queueNum := chooseQueue(packet) queues[queueNum].enqueue(packet) تحديث الوقت (الحزمة، رقم قائمة الانتظار)
تحديث الوقت (الحزمة، رقم قائمة الانتظار) // virStart هو بدء التشغيل الافتراضي للخدمة virStart := max(now(), lastVirFinish[queueNum]) packet.virFinish := packet.size + virStart lastVirFinish[queueNum] := packet.virFinish
يرسل() queueNum := selectQueue() packet := queues[queueNum].dequeue() حزمة الإرجاع
SelectQueue() هو := 1 minVirFinish =∞{\displaystyle \infty }طالما أن قيمته ≤ N، افعل queue := queues[it] إذا لم تكن قائمة الانتظار فارغة وكان رأس قائمة الانتظار أقل من الحد الأدنى لقيمة virFinish ، minVirFinish = queue.head.virFinish رقم قائمة الانتظار := it هو := هو + 1 إرجاع رقم قائمة الانتظار

تُنفَّذ الدالة receive () في كل مرة يتم فيها استقبال حزمة بيانات، وتُنفَّذ الدالة send () في كل مرة يجب فيها اختيار حزمة بيانات لإرسالها، أي عندما يكون الرابط غير نشط وقوائم الانتظار غير فارغة. يفترض هذا الكود الزائف وجود دالة now () تُعيد الوقت الافتراضي الحالي، ودالة chooseQueue () التي تختار قائمة الانتظار التي ستُضاف إليها حزمة البيانات.

تختار الدالة selectQueue () قائمة الانتظار ذات أقل وقت انتهاء افتراضي. ولتبسيط الكود، يستخدم الكود الزائف المعروض هنا بحثًا خطيًا. مع ذلك، يمكن تنفيذ الحفاظ على قائمة مرتبة في وقت لوغاريتمي، مما يؤدي إلى تعقيد زمني قدره O(log(n)) ، ولكن باستخدام كود أكثر تعقيدًا.

انظر أيضاً

مراجع

  1. 1 2 جون ناجل: "حول محولات الحزم ذات التخزين اللانهائي"، RFC 970، IETF ، ديسمبر 1985.
  2. 1 2 3 ناجل، جيه بي (1987). "حول محولات الحزم ذات التخزين غير المحدود". معاملات IEEE في الاتصالات . 35 (4): 435-438 . CiteSeerX 10.1.1.649.5380 . doi : 10.1109/TCOM.1987.1096782 . 
  3. ↑ فيليب غروس (يناير 1986)، وقائع اجتماع فرقة عمل خوارزميات وهياكل بيانات بوابات داربا المنعقد في 16-17 يناير 1986 (ملف PDF) ، IETF ، الصفحات 5 و98 ، تاريخ الاطلاع 4 مارس 2015. قدّم ناغل مخطط "الترتيب العادل للصفوف"، حيث تحتفظ البوابات بصفوف منفصلة لكل مضيف مُرسِل. وبهذه الطريقة، لا تستطيع المضيفات ذات التطبيقات غير المنطقية الاستيلاء على أكثر من حصتها العادلة من موارد البوابة. وقد أثار هذا نقاشًا حادًا ومثيرًا للاهتمام. 
  4. ↑ ديمرز، آلان؛ كيشاف، سرينيفاسان؛ شينكر، سكوت (1989). "تحليل ومحاكاة خوارزمية طابور عادلة" . مجلة ACM SIGCOMM لمراجعة اتصالات الحاسوب . 19 (4): 1-12 . doi : 10.1145/75247.75248 .
  5. ↑ ديمرز، آلان؛ كيشاف، سرينيفاسان؛ شينكر، سكوت (1990). "تحليل ومحاكاة خوارزمية طابور عادل" (ملف PDF) . الشبكات: البحث والتجربة . 1 : 3-26 .
  6. ↑ بينيت، جيه سي آر؛ هوي تشانغ (1996). "WF/sup 2/Q: أسوأ حالة عادلة في نظام طابور الانتظار الموزون العادل". وقائع مؤتمر IEEE INFOCOM '96. مؤتمر اتصالات الحاسوب . المجلد 1. ص 120. doi : 10.1109/INFCOM.1996.497885 . ISBN   978-0-8186-7293-4. S2CID 17558577 . 
  7. ↑ إيتو، ي.؛ تاساكا، س.؛ إيشيباشي، ي. (2002). "طوابير التناوب الدوري ذات الأوزان المتغيرة لأجهزة توجيه بروتوكول الإنترنت الأساسية". وقائع مؤتمر IEEE الدولي للأداء والحوسبة والاتصالات (رقم التصنيف 02CH37326) . ص 159. doi : 10.1109/IPCCC.2002.995147 . ISBN  978-0-7803-7371-6. S2CID 60787008 .