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

قرض گرفتن صف انتظار: رزروهای منصفانه

چرا اهمیت دارد سیستم‌های رزرو که از صفر ساخته شده‌اند معمولاً به کسی پاداش می‌دهند که سریع‌تر کلیک کند، یا اجازه می‌دهند یک فرد که حاضر نمی‌شود همه را مسدود کند. مکان‌هایی که هر روز چیزهای کمیاب را بین مردم توزیع می‌کنند، مدت‌ها پیش به طراحی بهتری رسیده‌اند.

سه صف

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

لیست انتظار رستوران با زنگ خبر. شما نام خود را ثبت می‌کنید و یک زنگ خبر دریافت می‌کنید. وقتی یک میز خالی می‌شود، زنگ خبر گروه بعدی به صدا درمی‌آید و آن‌ها پنج دقیقه فرصت دارند تا به میز پذیرش برسند، وگرنه میز به گروه بعدی داده می‌شود.

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

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

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

هدف

تیم موبایل یک آزمایشگاه کوچک با تلفن‌های آزمایشی را با هم شریک می‌شوند. مهندسان یک مدل را درخواست می‌کنند؛ وقتی یک تلفن از آن مدل آزاد شود، به آن‌ها پیشنهاد می‌شود و باید ظرف دو ساعت در اپلیکیشن آزمایشگاه آن را مطالبه کنند. یک تلفن مطالبه شده برای یک بازه زمانی هشت‌ساعته رزرو می‌شود و سپس به‌طور خودکار بازگردانده می‌شود. امروز اپ به هر کسی که اول دکمه "claim" را فشار دهد، یک گوشی آزاد می‌دهد و افراد شروع به نوشتن اسکریپت‌هایی کرده‌اند تا آن را فشار دهند.

stock = [("dev1", "pixel")]
events = [("request", 0, "ana", "pixel"), ("request", 5, "ben", "pixel"),
          ("claim", 10, "ben", "pixel"), ("claim", 30, "ana", "pixel")]
loans(stock, events)   # -> [("ana", "dev1", 30)]  (ben is not first)
نوبت شما

نوشتن loans(stock, events). stock فهرست‌ها (device_id, model)، همگی در زمان ۰ رایگان هستند. events هستند ("request", t, person, model) یا ("claim", t, person, model)، مرتب‌شده بر اساس زمان t به دقیقه. قوانین:

  1. هر مدل صف درخواست‌ها را به ترتیب زمان ثبت دارد. اگر فرد قبلاً برای آن مدل در صف باشد یا پیشنهاد آن را در دست داشته باشد، درخواست نادیده گرفته می‌شود.
  2. یک تلفن رایگان به اولین نفر در صف آن مدل پیشنهاد می‌شود (او صف را ترک می‌کند). اگر هیچ‌کس در صف نباشد، منتظر می‌ماند و اگر بعداً درخواستی برای آن مدل ارائه شود، فوراً آن را دریافت می‌کند. اگر چند دستگاه روی قفسه موجود باشد، پیشنهاد را به دستگاهی با کمترین شناسه دستگاه بدهید.
  3. یک پیشنهاد در زمان o می‌توان ادعا شود در حالی که t < o + 120. درخواستی که برای آن شخص و مدل هیچ پیشنهاد فعالی وجود ندارد، نادیده گرفته می‌شود.
  4. در o + 120 یک پیشنهاد امانی منقضی می‌شود و تلفن در آن لحظه دوباره آزاد می‌شود (قانون ۲).
  5. ادعا در زمان t یک وام را آغاز می‌کند؛ تلفن در t + 480.
  6. انقضاها و بازگرداندن‌هایی که در زمان رویداد یا قبل از آن سررسید می‌شوند، قبل از رویداد و به ترتیب زمان و سپس شناسه دستگاه انجام می‌شوند.
وام‌ها را به صورت (person, device_id, claim_time) در ترتیبی که ادعا شده‌اند.

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

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

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