राउंड रॉबिन शेड्यूलिंग में औसत प्रतीक्षा समय

Question

प्रतीक्षा समय परिभाषित किया गया है कि प्रत्येक प्रक्रिया को समय के टुकड़े होने से पहले कितनी देर प्रतीक्षा करनी है। शॉर्ट जॉब फर्स्ट और फर्स्ट आओ फर्स्ट सर्विस जैसे शेड्यूलिंग एल्गोरिदम में, हम केवल उस समय प्रतीक्षा कर सकते हैं जब हम नौकरियों को कतारबद्ध करते हैं और देखते हैं कि सेवा प्राप्त करने से पहले प्रत्येक को कितना इंतजार करना पड़ा।

जब राउंड रॉबिन या किसी अन्य प्रीपेप्टिव एल्गोरिदम की बात आती है, तो हम पाते हैं कि लंबे समय तक चलने वाली नौकरियां सीपीयू में थोड़ी देर बिताती हैं, जब उन्हें छूट दी जाती है और फिर इसे निष्पादित करने के लिए कुछ समय के लिए प्रतीक्षा करें और किसी बिंदु पर इसकी बारी , यह पूरा होने तक निष्पादित करता है। मैं इस तरह के शेड्यूलिंग एल्गोरिदम में नौकरियों के 'प्रतीक्षा समय' को समझने का सबसे अच्छा तरीका खोजना चाहता था।

मैं एक formula जो के रूप में समय का इंतजार कर देता है पाया:

Waiting Time = (Final Start Time - Previous Time in CPU - Arrival Time) 

लेकिन मैं इस सूत्र के लिए तर्क को समझने में विफल। उदाहरण के लिए एक नौकरी पर विचार करें जिसमें हर 5 इकाइयों में 30 इकाइयों और गोल-रॉबिन का विस्फोट होता है। दो और नौकरियां बी (10) और सी (15) हैं।

जिस क्रम में इन किया जाएगा सेवा प्रदान की जाएगी:

0 A 5 B 10 C 15 A 20 B 25 C 30 A 35 C 40 A 45 A 50 A 55 

एक के लिए प्रतीक्षा समय = 40 - 5 - 0

• मैं 40 चुनते हैं, क्योंकि के बाद 40 एक कभी नहीं इंतजार कर रहा है। यह सिर्फ अपना समय स्लाइस हो जाता है और आगे बढ़ता है।
• 5 चुनें क्योंकि ए 30 से 35 के बीच पूर्व में प्रक्रिया में बिताया गया है।
• 0 प्रारंभ समय है।

ठीक है, मुझे इस सूत्र में संदेह है कि 15 A 20 क्यों नहीं माना गया था? सहजता से, मैं यह समझने में असमर्थ हूं कि यह हमें ए के लिए प्रतीक्षा समय कैसे प्राप्त कर रहा है, जब हम केवल अंतिम निष्पादन के लिए लेखांकन कर रहे हैं और फिर आगमन का समय घटा रहे हैं।

मेरे अनुसार, एक के लिए प्रतीक्षा समय होना चाहिए:

• अंतिम प्रारंभ समय - (सभी समय का योग यह प्रसंस्करण में खर्च करते हैं)।

यदि यह सूत्र गलत है, तो यह क्यों है?

कृपया इस अवधारणा की मेरी समझ को स्पष्ट करने में मदद करें।

Answer 1

आपने गलत समझा है कि "सीपीयू में पिछली बार" सूत्र का क्या अर्थ है। इसका वास्तव में वही बात है जिसका आप "प्रोसेसिंग में खर्च होने वाले हर समय योग" कहते हैं। (मुझे लगता है कि "सीपीयू में पिछली बार" को "सीपीयू पर पहले चलने वाले कुल समय" के लिए छोटा माना जाना चाहिए, जहां "पहले" का मतलब "अंतिम शुरुआत से पहले" है।)

आपको अभी भी आगमन घटाना होगा समय क्योंकि प्रक्रिया स्पष्ट रूप से आने से पहले इंतजार नहीं कर रही थी। (अगर यह अस्पष्ट है: "आगमन का समय" वह समय है जब नौकरी शेड्यूलर को जमा की गई थी।) आपके उदाहरण में, सभी प्रक्रियाओं के लिए आगमन का समय 0 है, इसलिए इससे कोई फर्क नहीं पड़ता है, लेकिन सामान्य मामले में, आगमन का समय ध्यान में रखा जाना चाहिए।

संपादित करें: यदि आप लिंक किए गए वेबपृष्ठ पर उदाहरण देखते हैं, तो पी 1 को अंतिम बार शुरू होने से पहले चार बार इकाइयों के दो बार स्लाइस लेते हैं, और इसकी "सीपीयू में पिछली बार" की गणना 8 के बराबर होती है उपरोक्त व्याख्या।

Answer 2

अंतिम इंतजार कर

value- (समय क्वांटम × (एन-1))

यहाँ n समय की कोई एक प्रक्रिया गैंट चार्ट में आता है को दर्शाता है।