10 الگوریتم زمان بندی پردازنده ( CPU ) در سیستم عامل

مقدمه

در حالت کلی، فرآیند یک برنامه در حال اجرا است که وارد سیستم شده، روی آن پردازش انجام می‌شود و درنهایت از سیستم خارج می‌گردد اما یک فرآیند بلافاصله بعد از ورود نمی‌تواند CPU را در اختیار گرفته و عملیات پردازش روی آن صورت گیرد. الگوریتم‌های زمان‌بندی فرآیندها را بر روی پردازنده به شیوه‌ای کارآمد برنامه‌ریزی می‌کنند. این زمان‌بندی توسط یک زمان‌بند فرآیند Process Scheduler انجام می‌شود که با افزایش توان عملیاتی، استفاده از CPU را به حداکثر می‌رساند.

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

اهداف الگوریتم‌های زمان‌بندی در سیستم‌عامل

1. حداکثر استفاده از CPU:CPU را تا حد امکان مشغول نگه می‌دارند.
2. تخصیص منصفانه CPU: اختصاص عادلانه CPU به فرآیندها را انجام می‌دهد.
3. حداکثر توان عملیاتی: تعداد فرآیندهایی که اجرای خود را در واحد زمان کامل می‌کنند.
4. حداقل زمان بازگشت: زمان صرف شده توسط یک فرآیند برای پایان اجرا می‌باشد.
5. حداقل زمان انتظار: زمان انتظار یک فرآیند در صف آماده است.
6. حداقل زمان پاسخ: زمانی که یک فرآیند اولین پاسخ را تولید می‌کند.

انواع الگوریتم‌های زمان‌بندی در سیستم‌عامل

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

1. الگوریتم‌های انحصاری
2. الگوریتم‌های غیر انحصاری

الگوریتم‌های انحصاری (Non Preemptive)

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

الگوریتم‌های غیر انحصاری (Preemptive)

در این الگوریتم‌ها یک فرآیند که در حال اجراست ممکن است توسط سیستم‌عامل متوقف‌شده و به حالت آماده منتقل شود. این کار برای اختصاص پردازنده به یک فرآیند دیگر و یا انجام عملیات I/O و وقفه انجام می‌شود. به‌عبارت‌دیگر در این نوع از الگوریتم‌ها، فرآیندها ممکن است به چند بخش تقسیم‌شده و در چند مرحله عملیات تخصیص پردازنده انجام‌گرفته و اجرا شود. الگوریتم‌های RR, SRTF, MLFQ از این نوع هستند.

الگوریتم‌های زمان‌بندی مختلف

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

1. الگوریتم First-Come, First-Served (FCFS)

این الگوریتم ساده‌ترین و آسان‌ترین نوع  الگوریتم‌های زمان‌بندی در سیستم‌عامل است. در این الگوریتم، فرآیندی که ابتدا CPU را درخواست می‌کند،متقابلاً زودتر CPU را برای اجرا در اختیار می‌گیرد. این الگوریتم را می‌توان آن را با استفاده از روش FIFO (First-In, First-Out) Queue پیاده‌سازی کرد. ویژگی‌های این الگوریتم عبارتند از:

1. اجرای آن آسان است.
2. CPU همیشه بر اساس First-come و First-serve تخصیص داده می‌شود.
3. اما، این الگوریتم عملکرد ضعیفی دارد زیرا میانگین زمان انتظار آن بسیار بالاست.

2. الگوریتم Shortest-Job-Next (SJN)

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

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

3. الگوریتم Priority Scheduling

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

4. الگوریتم Shortest Remaining Time

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

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

5. الگوریتم Round Robin(RR)

زمان‌بند یک واحد زمان ثابت را به هر فرآیند اختصاص می‌دهد و آن‌ها را طی می‌کند. اگر فرآیند در آن بازه زمانی کامل شود، خاتمه می‌یابد، در غیر این صورت، پس از دادن فرصت به سایر فرآیندها، مجدداً زمان‌بندی می‌شود. برنامه‌ریزی RR شامل سربار گسترده‌ای است، به‌خصوص اگر یک واحد زمانی کوچک در نظر گرفته شود. به دلیل زمان انتظار بالا، ضرب‌الاجل‌ها به‌ندرت در یک سیستم RR خالص رعایت می‌شود.
گرسنگی هرگز نمی‌تواند رخ دهد، زیرا هیچ اولویتی داده نمی‌شود. ترتیب تخصیص واحد زمان‌بر اساس زمان رسیدن فرآیند، مشابه FIFO است. اگر Time-Slice بزرگ باشد به FCFS /FIFO یا اگر کوتاه باشد تبدیل به SJF/SRTF می‌شود.

6. الگوریتم Multiple-Level Queues (MLQ)

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

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

هر سه نوع مختلف فرآیند دارای صف خاص خود هستند. هر صف الگوریتم زمان‌بندی خاص خود را دارد. به‌عنوان‌مثال، صف 1 و صف 2 از Round Robin استفاده می‌کنند درحالی‌که صف 3 می‌تواند از FCFS برای برنامه‌ریزی فرآیندهای خود استفاده کند.

7. الگوریتم Multi level Feedback Queues (MLFQ)

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

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

8. الگوریتم Highest Response Ratio Next (HRRN)

الگوریتم زمان‌بندی HRRN وظیفه یافتن میانگین زمان انتظار و میانگین زمان چرخش با توجه به n فرآیند بازمان رسیدن و زمان انفجار را دارد. ما باید نسبت پاسخ تمام فرآیندهای موجود را پیداکرده و آن را که بالاترین نسبت پاسخ را دارد انتخاب کنیم. یک فرآیند پس از مرحله انتخاب، تا تکمیل فرآیند اجرا خواهد شد. در t = 0 ما فقط یک فرآیند در دسترس داریم، بنابراین A زمان‌بندی می‌شود. به طور مشابه در t = 3 ما فقط یک فرآیند در دسترس داریم، بنابراین B زمانبندی می‌شود.

اکنون در t = 9 ما 3 فرآیند C، D و E در دسترس داریم. زیرا C، D و E به ترتیب پس از 4، 6 و 8 واحد در دسترس بودند. بنابراین، زمان انتظار برای C، D و E به ترتیب 5 = (4 – 9)،  3 = (6 – 9) 3، و 1 = (8 – 9) واحد است.

با استفاده از فرمول داده‌شده در زیر، نسبت‌های پاسخ C، D و E را به ترتیب 2.25، 1.6 و 1.5 محاسبه می‌کنیم. واضح است که C بالاترین نسبت پاسخ را  دارد و بنابراین زمان‌بندی می‌شود. بعد در t = 13 ما 2 فرآیند در دسترس D و E داریم. نسبت پاسخ D و E به ترتیب 2.4 و 3.5 است. بنابراین فرآیند E در مرحله بعدی و فرآیند D در آخر انتخاب می‌شود.

9.  الگوریتم (Fixed priority pre-emptive (FPPS

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

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

10. الگوریتم Work-conserving

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

یک زمان‌بندی حفظ کار تنها زمانی بیکار است که هیچ سرویس در انتظار بسته‌ای وجود نداشته باشد. در مقابل، یک زمان‌بندی غیرفعال ممکن است حتی اگر بسته‌هایی برای ارائه داشته باشد، بیکار باشد.

سخن پایانی در مورد الگوریتم‌های زمان‌بندی در سیستم‌عامل

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

منتظر نظرات و پیشنهاد‌های شما در این زمینه هستیم. ممد دانلود