قائمة انتظار متعددة المستويات للتعليقات

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
الموسوعة الحرة

في علوم الحاسوب ، تُعدّ قائمة الانتظار متعددة المستويات ذات التغذية الراجعة خوارزمية جدولة . تُصمّم خوارزميات الجدولة بحيث تعمل بعض العمليات باستمرار لإبقاء وحدة المعالجة المركزية (CPU) مشغولة. [ 1 ] تُوسّع قائمة الانتظار متعددة المستويات ذات التغذية الراجعة الخوارزميات القياسية مع متطلبات التصميم التالية:

  1. قم بفصل العمليات إلى قوائم انتظار متعددة جاهزة بناءً على حاجتها للمعالج.
  2. أعطِ الأفضلية للعمليات ذات فترات استخدام وحدة المعالجة المركزية القصيرة.
  3. أعطِ الأولوية للعمليات ذات معدلات الإدخال/الإخراج العالية . (ستتوقف العمليات التي تعتمد على الإدخال/الإخراج في قائمة الانتظار لإتاحة وقت المعالجة للعمليات الأخرى).

طُوِّر نظام طابور التغذية الراجعة متعدد المستويات لأول مرة على يد فرناندو ج. كورباتو (1962). [ 2 ] تقديرًا لهذا الإنجاز، منحت جمعية آلات الحوسبة كورباتو جائزة تورينج . [ 3 ]

جدولة العمليات

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

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

الخوارزمية

يتم استخدام عدة طوابير FIFO وتكون العملية كما يلي:

  1. يتم إدخال عملية جديدة في نهاية (ذيل) قائمة انتظار FIFO ذات المستوى الأعلى .
  2. في مرحلة ما، تصل العملية إلى رأس قائمة الانتظار ويتم تخصيص وحدة المعالجة المركزية لها .
  3. إذا اكتملت العملية خلال الفترة الزمنية المحددة للطابور، فإنها تغادر النظام.
  4. إذا تخلت العملية طواعية عن التحكم في وحدة المعالجة المركزية، فإنها تغادر شبكة الانتظار، وعندما تصبح العملية جاهزة مرة أخرى، يتم إدراجها في نهاية نفس قائمة الانتظار التي تخلت عنها سابقًا.
  5. إذا استهلكت العملية كامل الوقت الكمي، يتم إيقافها مؤقتًا وإدراجها في نهاية قائمة الانتظار التالية ذات المستوى الأدنى. وستكون مدة الوقت الكمي لهذه القائمة التالية ذات المستوى الأدنى أكبر من مدة الوقت الكمي لقائمة الانتظار السابقة ذات المستوى الأعلى.
  6. سيستمر هذا المخطط حتى تكتمل العملية أو تصل إلى قائمة الانتظار الأساسية.
  • في قائمة الانتظار الأساسية، تتناوب العمليات بالتناوب حتى تكتمل وتغادر النظام. ويمكن أيضًا جدولة العمليات في قائمة الانتظار الأساسية وفقًا لأسبقية الوصول . [ 6 ]
  • في حال توقف عملية ما بسبب عمليات الإدخال/الإخراج، يتم ترقيتها مستوىً واحداً، ووضعها في نهاية قائمة الانتظار الأعلى التالية. يتيح هذا للمجدول إعطاء الأولوية للعمليات التي تعاني من قيود الإدخال/الإخراج، كما يسمح للعمليات الأخرى بالخروج من قائمة الانتظار الأساسية.

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

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

معايير الجدولة

بشكل عام، يتم تعريف جدولة قائمة انتظار التغذية الراجعة متعددة المستويات من خلال المعلمات التالية: [ 6 ]

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

انظر أيضاً

مراجع

  1. ↑ سيلبرشاتز، أبراهام (1994). مفاهيم أنظمة التشغيل، الطبعة الرابعة . أديسون-ويسلي. ص  131. ISBN 978-0-201-50480-4.
  2. ↑ كورباتو، فرناندو جيه؛ ميروين-داجيت، مارجوري؛ دالي، روبرت سي. (1962). "نظام تجريبي لتقاسم الوقت". وقائع المؤتمر المشترك للحاسوب في ربيع 1-3 مايو 1962 - AIEE-IRE '62 (ربيع) . ص 335. doi : 10.1145/1460833.1460871 . S2CID 14363753 .  
  3. ↑ أرباتشي-دوسو، رمزي ح.؛ أرباتشي-دوسو، أندريا س. (2014). "قائمة انتظار التغذية الراجعة متعددة المستويات". أنظمة التشغيل: ثلاثة أجزاء سهلة (ملف PDF) . كتب أرباتشي-دوسو.
  4. ↑ سيلبرشاتز، أبراهام (1994). مفاهيم أنظمة التشغيل، الطبعة الرابعة . أديسون-ويسلي. ص 147. ISBN  978-0-201-50480-4.
  5. ↑ سيلبرشاتز، أبراهام (1994). مفاهيم أنظمة التشغيل، الطبعة الرابعة . أديسون-ويسلي. ص 148. ISBN  978-0-201-50480-4.
  6. 1 2 سيلبرشاتز، أبراهام؛ جالفين، بيتر باير؛ غاني، جريج (2008). مفاهيم نظام التشغيل ( الطبعة الثامنة). هوبوكين، نيوجيرسي: وايلي. ص 198. ISBN   978-0470128725.