पाठ्यक्रम 148 में से पाठ 48 · उधार की मशीनें
उधार की मशीनें

Triage उधार लें: एक job queue का क्रम

यह क्यों मायने रखता है "एक priority queue इस्तेमाल करो" प्राथमिकताओं वाली किसी भी queue का प्रतिवर्त है। यह "कौन सबसे ज़्यादा मायने रखता है?" का जवाब देता है जब असली सवाल अक्सर "कौन सबसे कम इंतज़ार कर सकता है?" होता है। दूसरे क्षेत्र उस सवाल का जवाब लंबे समय से दे रहे हैं।

तीन counters

एक अस्पताल emergency department। एक triage nurse हर आने वाले को एक श्रेणी में रखती है, और हर श्रेणी का देखे जाने का एक लक्ष्य समय है: व्यापक रूप से इस्तेमाल Manchester सिस्टम में, तुरंत, 10 मिनट के अंदर, 60, 120 या 240। जब एक डॉक्टर ख़ाली हो, तो अगला मरीज़ बस कमरे का सबसे बीमार नहीं: अपने लक्ष्य को पार करने वाला एक मानक मरीज़ एक मिनट पहले आए उस ज़रूरी मरीज़ से पहले जा सकता है जिसके पास अभी समय है।

Airport check-in। premium और economy के लिए अलग lanes हैं। एक lane के अंदर, लोग आने के क्रम में लिए जाते हैं। पर जब एक flight बंद होने वाली हो, कर्मचारी economy line में चलकर उस flight को आगे बुलाते हैं, उन premium यात्रियों से पहले जिनकी flights बाद में जाती हैं।

एक library वापसी counter। एक line, सख़्ती से क्रम में ली जाती। कोई कभी पीछे नहीं छोड़ा जाता, और किसी की ज़रूरत पर विचार नहीं होता।

code से पहले तुलना करें

  1. हर counter में, क्या तय करता है कि अगला कौन लिया जाए?
  2. कौन-से counters किसी को हमेशा के लिए इंतज़ार करवा सकते हैं? कौन-से एक ज़रूरी मामले को बहुत देर इंतज़ार करवा सकते हैं?
  3. अस्पताल और airport बिल्कुल एक जैसे नहीं दिखते। वे क्या साझा करते हैं? इसे एक वाक्य के रूप में लिखें जो न अस्पतालों का ज़िक्र करे न विमानों का।
  4. Airport में, हर lane का बस आगे का हिस्सा देखना काफ़ी क्यों है?

लक्ष्य

एक background job सिस्टम एक worker पर चलता है जो हर job में ठीक एक मिनट लेता है। Jobs interactive (priority 1), standard (2) या batch (3) हैं, और हर priority का एक service वादा है: उस priority का एक job शुरू होने से पहले ज़्यादा से ज़्यादा कितना इंतज़ार कर सकता है। मौजूदा scheduler हमेशा सबसे ऊँची priority वाला इंतज़ार करता job चलाता है, और batch jobs हर दोपहर अपना वादा चूकते हैं।

आपकी बारी

order(jobs, max_wait) लिखें। jobs arrive (पूरे मिनट) से sorted {"id", "arrive", "priority"} की एक सूची है; max_wait priority को उतने मिनटों से जोड़ता है जितना एक job इंतज़ार कर सकता है। job ids उस क्रम में लौटाएँ जिसमें worker उन्हें चलाता है। worker हर मिनट एक job चलाता है: एक job अपने आने और पिछले job के अंत में से बाद वाले पर शुरू होता है, और उसका इंतज़ार start घटा आना है। नियम: कोई job max_wait[priority] से ज़्यादा इंतज़ार नहीं कर सकता। test के सारे दिन बिना किसी job के देर हुए संभाले जा सकते हैं; {1: 3, 2: 20, 3: 60} के साथ एक दिन में लगभग 1,000 jobs हैं।

इस पाठ में कोई समस्या दिखी? बताएँ · इस पाठ के बारे में पूछें

यह अभ्यास जल्द खुलेगा

इससे पहले वाला पाठ पूरा करें और यह खुल जाएगा। पूरा कोर्स मुफ़्त है, कोई खाता नहीं चाहिए, और आप यह पाठ अभी पढ़ सकते हैं।