सीपीयू शेड्यूलिंग

सीपीयू शेड्यूलिंग ऑपरेटिंग-सिस्टम का वह कार्य है जो यह तय करता है कि कौन सी तैयार प्रक्रिया या थ्रेड अगले प्रोसेसर पर चलेगा, जिसमें प्रतिक्रियाशीलता, थ्रूपुट, निष्पक्षता और समय-सीमा को पूरा करने जैसे लक्ष्यों को संतुलित किया जाता है।

Definition

सीपीयू शेड्यूलिंग वह नीति और तंत्र है जिसके द्वारा एक ऑपरेटिंग सिस्टम, चलने योग्य प्रक्रियाओं या थ्रेड्स में से, यह चुनता है कि प्रोसेसर किसे और कितने समय के लिए आवंटित किया जाए, ताकि चुने हुए प्रदर्शन और निष्पक्षता के उद्देश्यों को अनुकूलित किया जा सके।

Scope

यह विषय शेड्यूलिंग नीतियों और उनके मूल्यांकन को शामिल करता है: फर्स्ट-कम-फर्स्ट-सर्व्ड, शॉर्टेस्ट-जॉब-फर्स्ट, राउंड-रॉबिन, प्रायोरिटी, और मल्टीलेवल फीडबैक क्यू; प्रीएम्प्टिव बनाम नॉन-प्रीएम्प्टिव शेड्यूलिंग; सीपीयू यूटिलाइजेशन, थ्रूपुट, टर्नअराउंड, वेटिंग और रिस्पांस टाइम के मानदंड; और मल्टीप्रोसेसर और रियल-टाइम सिस्टम के लिए शेड्यूलिंग। इसमें शेड्यूल किए जा रहे कार्यों का प्रतिनिधित्व (प्रक्रिया और थ्रेड प्रबंधन) और सिंक्रोनाइज़ेशन (समवर्तीता) शामिल नहीं है।

Core questions

• शेड्यूलिंग गुणवत्ता को किन मानदंडों से मापा जाता है?
• सामान्य शेड्यूलिंग एल्गोरिदम निष्पक्षता और दक्षता में कैसे भिन्न होते हैं?
• शेड्यूलर को चल रहे कार्य को कब प्रीएम्प्ट करना चाहिए?
• मल्टीप्रोसेसर और रियल-टाइम समय-सीमा के लिए शेड्यूलिंग को कैसे अनुकूलित किया जाता है?

Key concepts

• फर्स्ट-कम-फर्स्ट-सर्व्ड
• शॉर्टेस्ट-जॉब-फर्स्ट
• राउंड-रॉबिन और टाइम क्वांटम
• प्रायोरिटी शेड्यूलिंग
• मल्टीलेवल फीडबैक क्यू
• प्रीएम्प्टिव बनाम नॉन-प्रीएम्प्टिव
• टर्नअराउंड, वेटिंग और रिस्पांस टाइम
• स्टार्वेशन और एजिंग
• रियल-टाइम शेड्यूलिंग

Key theories

शेड्यूलिंग के उद्देश्य और ट्रेड-ऑफ

कोई भी एक नीति सभी लक्ष्यों को अनुकूलित नहीं करती है: शॉर्टेेस्ट-जॉब-फर्स्ट औसत प्रतीक्षा समय को कम करता है लेकिन लंबे कार्यों को भुखमरी का शिकार बना सकता है, राउंड-रॉबिन कुछ थ्रूपुट लागत पर प्रतिक्रिया समय को सीमित करता है, और प्रायोरिटी योजनाएं भुखमरी का जोखिम उठाती हैं, इसलिए शेड्यूलर अपने वर्कलोड के लिए थ्रूपुट, निष्पक्षता और प्रतिक्रियाशीलता को संतुलित करते हैं।

Mechanisms

शेड्यूलर तब चलता है जब कोई प्रक्रिया ब्लॉक हो जाती है, रुक जाती है, या उसका समय क्वांटम समाप्त हो जाता है, और अपनी नीति के अनुसार तैयार कतार से अगला कार्य चुनता है। राउंड-रॉबिन प्रत्येक कार्य को बारी-बारी से एक समय-स्लाइस देता है; प्रायोरिटी और मल्टीलेवल फीडबैक क्यू कार्यों को महत्व और देखे गए व्यवहार के अनुसार क्रमबद्ध करते हैं, भुखमरी (starvation) को रोकने के लिए एजिंग (aging) का उपयोग करते हैं। प्रीएम्प्टिव शेड्यूलर एक चल रहे कार्य को बाधित कर सकते हैं ताकि एक उच्च-प्राथमिकता वाले कार्य पर स्विच किया जा सके, जो इंटरैक्टिविटी और रियल-टाइम समय-सीमा के लिए आवश्यक है।

Clinical relevance

शेड्यूलिंग सीधे उपयोगकर्ता अनुभव और सिस्टम दक्षता को आकार देती है: यह निर्धारित करती है कि इंटरैक्टिव एप्लिकेशन प्रतिक्रियाशील महसूस करते हैं या नहीं, बैच वर्कलोड जल्दी पूरे होते हैं या नहीं, और रियल-टाइम कार्य समय-सीमा को पूरा करते हैं या नहीं। लिनक्स जैसे उत्पादन प्रणालियों में शेड्यूलर कई कोर और विविध वर्कलोड में इन प्रतिस्पर्धी लक्ष्यों को संतुलित करते हैं।

History

शेड्यूलिंग की समस्याएं 1960 के दशक में मल्टीप्रोग्रामिंग और टाइम-शेयरिंग के साथ उत्पन्न हुईं, जब प्रोसेसर को साझा करने के लिए राउंड-रॉबिन और प्रायोरिटी योजनाएं विकसित की गईं। रेट-मोनोटोनिक और अर्लिएस्ट-डेडलाइन-फर्स्ट विश्लेषण सहित रियल-टाइम शेड्यूलिंग सिद्धांत को 1970 के दशक में औपचारिक रूप दिया गया था, और आधुनिक मल्टीकोर शेड्यूलर ने इन विचारों को कई प्रोसेसर तक बढ़ाया।

Debates

निष्पक्षता बनाम थ्रूपुट और प्राथमिकता

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

Key figures

• Edsger W. Dijkstra
• Abraham Silberschatz
• Andrew S. Tanenbaum
• C. L. Liu
• James W. Layland

Seminal works

• silberschatz2018
• tanenbaum2014os

Frequently asked questions

प्रीएम्प्टिव और नॉन-प्रीएम्प्टिव शेड्यूलिंग में क्या अंतर है?

नॉन-प्रीएम्प्टिव शेड्यूलिंग एक चल रहे कार्य को प्रोसेसर को तब तक रखने देती है जब तक वह ब्लॉक न हो जाए या समाप्त न हो जाए। प्रीएम्प्टिव शेड्यूलिंग जबरन प्रोसेसर को हटा सकती है — उदाहरण के लिए जब उसका समय-स्लाइस समाप्त हो जाता है या एक उच्च-प्राथमिकता वाला कार्य तैयार हो जाता है — जो प्रतिक्रियाशीलता में सुधार करता है और रियल-टाइम गारंटियों के लिए आवश्यक है।

भुखमरी (starvation) क्या है, और इसे कैसे रोका जाता है?

भुखमरी तब होती है जब कोई कार्य कभी शेड्यूल नहीं होता क्योंकि उच्च-प्राथमिकता वाले कार्य लगातार प्राथमिकता लेते रहते हैं। इसे आमतौर पर एजिंग (aging) द्वारा रोका जाता है, जो लंबे समय से प्रतीक्षा कर रहे कार्यों की प्राथमिकता को धीरे-धीरे बढ़ाता है ताकि वे अंततः चल सकें।