سرفصل‌ها درس 48 از 148 · ماشین‌های قرضی
ماشین‌های قرضی

تراژیک قرضی: سفارش صف کار

چرا اهمیت دارد «استفاده از صف اولویت‌بندی‌شده» واکنش غریزی هر صف اولویت‌دار است. این پاسخ می‌دهد «چه کسی بیشترین اهمیت را دارد؟» در حالی که سؤال واقعی اغلب این است «چه کسی کمترین توانایی انتظار را دارد؟». حوزه‌های دیگر مدت‌هاست که به این سؤال پاسخ می‌دهند.

سه میز

بخش اورژانس بیمارستان. یک پرستار تریاژ هر مراجعه‌کننده را در یک دسته قرار می‌دهد و هر دسته زمان هدف مشخصی برای ویزیت شدن دارد: در سیستم رایج منچستر، فوراً، ظرف ۱۰ دقیقه، ۶۰، ۱۲۰ یا ۲۴۰ دقیقه. وقتی یک پزشک آزاد است، بیمار بعدی لزوماً بیمارترین فرد در اتاق نیست: یک بیمار عادی که در آستانه عبور از زمان هدف خود است، ممکن است قبل از یک بیمار اورژانسی که یک دقیقه پیش رسیده و هنوز زمان دارد، مورد درمان قرار گیرد.

چک‌این فرودگاه. خطوط مجزایی برای کلاس‌های فرستاده (پریمیم) و اکونومی وجود دارد. در هر خط، به افراد به ترتیب ورود خدمت‌رسانی می‌شود. اما وقتی زمان بسته شدن یک پرواز نزدیک می‌شود، کارکنان در خط اکونومی قدم می‌زنند و آن پرواز را جلوتر فرا می‌خوانند، پیش از مسافرانی که پروازشان دیرتر انجام می‌شود و در کلاس فرستاده هستند.

میز امانات کتابخانه. یک صف، و خدمات‌رسانی دقیقاً به ترتیب ورود. هیچ‌کس از صف جلو نمی‌زند و فوریت هیچ‌کس در نظر گرفته نمی‌شود.

قبل از کدنویسی مقایسه کنید

  1. در هر میز، چه چیزی تعیین می‌کند که چه کسی بعداً خدمت‌رسانی می‌شود؟
  2. کدام میزها می‌توانند کسی را برای همیشه منتظر نگه دارند؟ کدام یک می‌تواند یک مورد فوری را بیش از حد منتظر نگه دارد؟
  3. بیمارستان و فرودگاه هیچ شباهتی به هم ندارند. چه چیزی مشترک دارند؟ آن را به صورت یک جمله بنویسید که نه از بیمارستان‌ها و نه از هواپیماها نامی نبرد.
  4. در فرودگاه، چرا کافی است فقط به جلوی هر صف نگاه کنید؟

هدف

یک سیستم کارهای پس‌زمینه روی یک کارگر اجرا می‌شود که برای هر کار دقیقاً یک دقیقه زمان می‌برد. وظایف تعاملی (اولویت ۱)، استاندارد (۲) یا دسته‌ای (۳) هستند و هر اولویت یک تعهد سرویس دارد: حداکثر مدتی که یک وظیفه با آن اولویت می‌تواند قبل از شروع منتظر بماند. برنامه‌ریز فعلی همیشه وظیفه در حال انتظار با بالاترین اولویت را اجرا می‌کند و وظایف دسته‌ای هر بعدازظهر تعهد خود را از دست می‌دهند.

نوبت شما

نوشتن order(jobs, max_wait). jobs فهرستی از {"id", "arrive", "priority"} بر اساس arrive (دقیقهٔ کامل)؛ max_wait مرتب‌سازی را بر اساس بیشترین دقایقی که یک کار می‌تواند منتظر بماند انجام می‌دهد. شناسه‌های کارها را به ترتیبی که کارگر آن‌ها را اجرا می‌کند بازگردانید. کارگر هر دقیقه یک کار را اجرا می‌کند: یک کار در دیرتر از زمان رسیدن آن یا پایان کار قبلی آغاز می‌شود و مدت انتظار آن برابر با زمان شروع منهای زمان رسیدن است. قاعده: هیچ کاری نباید بیش از max_wait[priority]. روزهای آزمون همگی می‌توانند بدون تأخیر هیچ شغلی انجام شوند؛ با {1: 3, 2: 20, 3: 60} یک روز حدوداً شامل ۱۰۰۰ شغل است.

مشکلی در این درس دیدید؟ گزارشش کنید · دربارهٔ این درس بپرسید

این تمرین به‌زودی باز می‌شود

درس پیش از آن را تمام کنید تا این یکی باز شود. کل دوره رایگان است، حساب کاربری لازم نیست، و می‌توانید همین الان این درس را بخوانید.