فرز الاستعارة: ترتيب طابور المهام
لماذا هذا مهم "استخدم priority queue" هو رد الفعل التلقائي لأي queue يحتوي على priorities. إنه يجيب على سؤال "من هو الأكثر أهمية؟" بينما السؤال الحقيقي غالباً ما يكون "من يمكنه الانتظار أقل؟". مجالات أخرى تجيب على ذلك السؤال منذ وقت طويل.
ثلاثة مكاتب
A قسم الطوارئ في مستشفى. تضع ممرضة الفرز كل حالة واصلة في فئة، ولكل فئة وقت مستهدف للفحص: في نظام مانشستر واسع الانتشار، فوراً، خلال 10 دقائق، 60، 120 أو 240. عندما يصبح الطبيب متفرغاً، لا يكون المريض التالي هو الأكثر مرضاً في الغرفة ببساطة: يمكن لمريض قياسي أوشك على تجاوز وقته المستهدف أن يسبق مريضاً عاجلاً وصل قبل دقيقة واحدة ولا يزال لديه وقت.
تسجيل الوصول في المطار. توجد مسارات منفصلة للدرجة الممتازة والاقتصادية. داخل المسار، يتم خدمة الأشخاص حسب ترتيب وصولهم. ولكن عندما يوشك الرحلة على الإغلاق، يسير الموظفون في خط الاقتصاد وينادون على تلك الرحلة للمضي قدما، قبل ركاب الدرجة الممتازة الذين تغادر رحلاتهم لاحقا.
A library returns desk. سطر واحد، يتم تنفيذه بالترتيب بدقة. لا يتم تجاوز أي شخص، ولا يتم النظر في استعجال أي شخص.
قارن قبل أن تبرمج
- في كل مكتب، ما الذي يحدد من سيتم خدمته بعد ذلك؟
- أي المكاتب يمكن أن تجعل شخصا ينتظر للأبد؟ أي منها يمكن أن يجعل حالة عاجلة تنتظر لفترة طويلة جدا؟
- لا يشبه المستشفى والمطار بعضهما البعض أبدا. ما الذي يشتركان فيه؟ اكتب ذلك في جملة واحدة لا تذكر المستشفيات ولا الطائرات.
- في المطار، لماذا يكفي النظر إلى مقدمة كل مسار؟
الهدف
يعمل نظامA background job على عامل واحد يستغرق دقيقة واحدة بالضبط لكل job. تكون الـ Jobs تفاعلية (priority 1) أو قياسية (2) أو batch (3)، ولكل priority وعد خدمة: أقصى وقت يمكن أن ينتظره job من تلك الـ priority قبل أن يبدأ. يقوم الـ scheduler الحالي دائماً بتشغيل job الانتظار ذو الـ priority الأعلى، وتفشل الـ batch jobs في الوفاء بوعدها كل بعد ظهر.
اكتب order(jobs, max_wait). jobs هي قائمة من {"id", "arrive", "priority"} مرتبة حسب arrive (دقائق كاملة)؛ max_wait يربط الأولوية بأقصى عدد من الدقائق التي يمكن أن ينتظرها العمل. أعد معرفات العمل بالترتيب الذي يقوم به العامل بتشغيلها. يقوم العامل بتشغيل عمل واحد في الدقيقة الواحدة: يبدأ العمل في الوقت المتأخر بين وصوله ونهاية العمل السابق، وانتظاره هو وقت البدء ناقص وقت الوصول. قاعدة : لا يمكن لأي عمل أن ينتظر لفترة أطول من max_wait[priority]. يمكن خدمة جميع أيام الاختبار دون تأخير أي عمل؛ مع {1: 3, 2: 20, 3: 60} يحتوي اليوم الواحد على حوالي 1,000 عمل.
سيفتح هذا التمرين قريبا
أنهِ الدرس السابق ليفتح هذا الدرس. الدورة كاملة مجانية، ولا تحتاج إلى حساب، ويمكنك قراءة هذا الدرس الآن.
يقوم هذا المتصفح بحظر ملفات تعريف الارتباط لـ learn.floati.life، لذا لا يمكن فتح الدروس التي أنهيتها هنا بالترتيب. اسمح بملفات تعريف الارتباط لهذا الموقع وأعد التحميل.