ऑपरेटिंग सिस्टम शेड्यूलिंग एल्गोरिदम

एक प्रक्रिया समयबद्धक विशेष अनुसूचन एल्गोरिदम के आधार पर सीपीयू को सौंपी जाने वाली विभिन्न प्रक्रियाओं को निर्धारित करता है। छह लोकप्रिय प्रक्रिया शेड्यूलिंग एल्गोरिदम हैं जिन पर हम इस अध्याय में चर्चा करने जा रहे हैं -

• फर्स्ट-कम, फर्स्ट-सेव्ड (FCFS) शेड्यूलिंग
• सबसे कम-नौकरी-अगला (SJN) निर्धारण
• प्राथमिकता निर्धारण
• सबसे कम समय शेष
• राउंड रॉबिन (RR) शेड्यूलिंग
• एकाधिक-स्तरीय कतार निर्धारण

ये एल्गोरिदम या तो हैं non-preemptive or preemptive। गैर-प्रीमेप्टिव एल्गोरिदम को डिज़ाइन किया गया है ताकि एक बार जब कोई प्रक्रिया चल रही अवस्था में प्रवेश करे, तो उसे तब तक प्रीपेप्ट नहीं किया जा सकेगा जब तक कि वह अपना आवंटित समय पूरा न कर ले, जबकि प्रीमेप्टिव शेड्यूलिंग प्राथमिकता पर आधारित होती है, जहाँ कोई शेड्यूलर उच्च प्राथमिकता होने पर कभी भी निम्न प्राथमिकता वाली रनिंग प्रक्रिया की पूर्व सूचना दे सकता है। प्रक्रिया एक तैयार अवस्था में प्रवेश करती है।

पहले आओ पहले पाओ (FCFS)

• नौकरियों को पहले आओ, पहले पाओ के आधार पर अंजाम दिया जाता है।
• यह एक गैर-प्रीमेप्टिव, प्री-इप्टिव शेड्यूलिंग एल्गोरिदम है।
• समझने और लागू करने में आसान।
• इसका कार्यान्वयन FIFO कतार पर आधारित है।
• औसत प्रतीक्षा समय के रूप में प्रदर्शन में खराब उच्च है।

Wait time प्रत्येक प्रक्रिया इस प्रकार है -

प्रोसेस	प्रतीक्षा समय: सेवा समय - आगमन समय
P0	० - ० = ०
P1	5 - 1 = 4
P2	8 - 2 = 6
पी 3	16 - 3 = 13

औसत प्रतीक्षा समय: (0 + 4 + 6 + 13) / 4 = 5.75

सबसे छोटा काम अगला (SJN)

• इस रूप में भी जाना जाता है shortest job first, या एसजेएफ

• यह एक गैर-प्रीमेप्टिव, प्री-इम्पेक्टिव शेड्यूलिंग एल्गोरिदम है।

• प्रतीक्षा समय को कम करने के लिए सबसे अच्छा तरीका।

• बैच सिस्टम में लागू करना आसान है जहां आवश्यक सीपीयू समय अग्रिम में जाना जाता है।

• इंटरैक्टिव सिस्टम में लागू करना असंभव है जहां सीपीयू समय की आवश्यकता नहीं है।

• प्रोसेसर को पहले से पता होना चाहिए कि प्रक्रिया में कितना समय लगेगा।

दिया गया: प्रक्रियाओं की तालिका, और उनके आगमन का समय, निष्पादन समय

प्रोसेस	आगमन समय	निष्पादन समय	सेवा का समय
P0	0	5	0
P1	1	3	5
P2	2	8	14
पी 3	3	6	8

Waiting time प्रत्येक प्रक्रिया इस प्रकार है -

प्रोसेस	इंतजार का समय
P0	० - ० = ०
P1	5 - 1 = 4
P2	14 - 2 = 12
पी 3	8 - 3 = 5

औसत प्रतीक्षा समय: (0 + 4 + 12 + 5) / 4 = 21/4 = 5.25

प्राथमिकता आधारित निर्धारण

• प्राथमिकता शेड्यूलिंग एक गैर-प्रीमेप्टिव एल्गोरिदम है और बैच सिस्टम में सबसे आम शेड्यूलिंग एल्गोरिदम में से एक है।

• प्रत्येक प्रक्रिया को प्राथमिकता दी जाती है। सर्वोच्च प्राथमिकता वाली प्रक्रिया को पहले और इसी तरह निष्पादित किया जाना है।

• समान प्राथमिकता वाली प्रक्रियाओं को पहले आओ पहले पाओ के आधार पर क्रियान्वित किया जाता है।

• स्मृति की आवश्यकताओं, समय की आवश्यकताओं या किसी अन्य संसाधन आवश्यकता के आधार पर प्राथमिकता तय की जा सकती है।

दिए गए: प्रक्रियाओं की तालिका, और उनके आगमन का समय, निष्पादन समय और प्राथमिकता। यहां हम विचार कर रहे हैं 1 सबसे कम प्राथमिकता है।

प्रोसेस	आगमन समय	निष्पादन समय	वरीयता	सेवा का समय
P0	0	5	1	0
P1	1	3	2	1 1
P2	2	8	1	14
पी 3	3	6	3	5

Waiting time प्रत्येक प्रक्रिया इस प्रकार है -

प्रोसेस	इंतजार का समय
P0	० - ० = ०
P1	11 - 1 = 10
P2	14 - 2 = 12
पी 3	5 - 3 = 2

औसत प्रतीक्षा समय: (0 + 10 + 12 + 2) / 4 = 24/4 = 6

सबसे कम समय शेष

• सबसे कम शेष समय (एसआरटी) एसजेएन एल्गोरिथ्म का प्रारंभिक संस्करण है।

• प्रोसेसर को पूर्णता के निकटतम कार्य के लिए आवंटित किया गया है, लेकिन इसे नए तैयार कार्य द्वारा पूरा किया जा सकता है और कम समय पूरा होने पर।

• इंटरैक्टिव सिस्टम में लागू करना असंभव है जहां सीपीयू समय की आवश्यकता नहीं है।

• इसका उपयोग अक्सर बैच के वातावरण में किया जाता है, जहां छोटी नौकरियों को वरीयता देने की आवश्यकता होती है।

राउंड रॉबिन शेड्यूलिंग

• राउंड रॉबिन प्रीमेप्टिव प्रोसेस शेड्यूलिंग एल्गोरिदम है।

• प्रत्येक प्रक्रिया को निष्पादित करने के लिए एक निश्चित समय प्रदान किया जाता है, इसे कहा जाता है quantum।

• एक बार किसी प्रक्रिया को एक निश्चित समयावधि के लिए निष्पादित किया जाता है, यह पूर्व निर्धारित है और अन्य प्रक्रिया किसी निश्चित समय अवधि के लिए निष्पादित होती है।

• पूर्वनिर्धारित प्रक्रियाओं की स्थिति को बचाने के लिए संदर्भ स्विचिंग का उपयोग किया जाता है।

Wait time प्रत्येक प्रक्रिया इस प्रकार है -

प्रोसेस	प्रतीक्षा समय: सेवा समय - आगमन समय
P0	(० - ०) + (१२ - ३) = ९
P1	(३ - १) = २
P2	(६ - २) + (१४ - ९) + (२० - १ +) = १२
पी 3	(९ - ३) + (१ 12 - १२) = ११

औसत प्रतीक्षा समय: (9 + 2 + 12 + 11) / 4 = 8.5

एकाधिक-स्तरीय कतार निर्धारण

कई-स्तरीय कतारें एक स्वतंत्र समय-निर्धारण एल्गोरिथम नहीं हैं। वे सामान्य विशेषताओं के साथ नौकरियों के समूह और अनुसूची के लिए अन्य मौजूदा एल्गोरिदम का उपयोग करते हैं।

• सामान्य विशेषताओं वाली प्रक्रियाओं के लिए कई कतारें बनी हुई हैं।
• प्रत्येक कतार का अपना शेड्यूलिंग एल्गोरिदम हो सकता है।
• प्राथमिकताएँ प्रत्येक कतार को दी जाती हैं।

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