الگوریتم های زمان بندی (Scheduling Algorithms) در سیستم عامل – راهنمای جامع

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

• زمان‌بندی «اجرا به ترتیب ورود» (First-Come, First-Served) یا به اختصار (FCFS)
• زمان‌بندی «کوتاه‌ترین کار بعدی» (Shortest-Job-Next) یا به اختصار (SJN)
• زمان‌بندی اولویت (Priority)
• زمان‌بندی کوتاه‌ترین زمان باقیمانده (Shortest Remaining Time)
• زمان‌بندی نوبت گردشی یا راند رابین (Round Robin) یا به اختصار (RR)
• زمان‌بندی صف‌های چند سطحی (Multiple-Level Queues)

الگوریتم‌های فوی کی از دو حالت «پیش‌دستانه» (preemptive) یا «غیر پیش‌دستانه» (non-preemptive) را دارند. الگوریتم‌های غیر پیش‌دستانه چنان طراحی شده‌اند که وقتی پراسسی وارد حالت اجرایی شد، تا زمانی که زمان تخصیص‌یافته‌اش پایان نیافته است، تخلیه نشود، اما در زمان‌بندی پیش‌دستانه همه چیزبه اولویت‌بندی بستگی دارد و زمانی که یک پراسس با اولویت  بالا وارد حالت آماده‌به‌کار می‌شود، ممکن است پراسس دارای اولویت پایین‌تر خالی شود.

اجرا به ترتیب ورود (FCFS)

این روش زمان‌بندی کارها، خصوصیات زیر را دارد:

• وظایف به ترتیب ورود اجرا می‌شوند.
• یک الگوریتم زمان‌بندی غیر preemptive و pre-emptive است.
• درک و پیاده‌سازی آسانی دارد.
• پیاده‌سازی آن مبتنی بر صف FIFO است.
• عملکرد آن پایین است، زیرا میانگین زمان انتظار بالا است.

زمان انتظار هر پردازش به صورت زیر است:

زمان انتظار میانگین:

(0+4+6+13) / 4 = 5.75

کوتاه‌ترین کار بعدی (SJN)

الگوریتم SJF در سیستم عامل خصوصیات زیر را دارد:

• این روش به نام «ابتدا، کوتاه‌ترین کار» یا SJF نیز نامیده می‌شود.
• یک الگوریتم زمان‌بندی غیر preemptive و pre-emptive است.
• رویکرد ساده‌ای برای کاهش زمان انتظار محسوب می‌شود.
• در سیستم‌های دسته‌ای که زمان مورد نیاز CPU از پیش مشخص نیست به سادگی پیاده‌سازی می‌شود.
• پیاده‌سازی آن در سیستم‌های تعاملی که زمان مورد نیاز CPU مشخص نیست ناممکن است.
• پردازنده باید از قبل بداند که پردازش چه مدت طول خواهد کشید.

زمان انتظار هر پردازش به صورت زیر است:

میانگین زمان انتظار:

(0+4+12+5) / 4 = 21 / 4 = 5.25

زمان‌بندی مبتنی بر اولویت

این روش خصوصیات زیر را دارد:

فیلم آموزش مدیریت دیسک در سیستم عامل (مرور اجمالی و تست کنکور) (رایگان) در فرادرس

کلیک کنید

• زمان‌بندی اولویت یک الگویتم غیر preemptive است و یکی از رایج‌ترین الگوریتم‌های زمان‌بندی در سیستم‌های دسته‌ای محسوب می‌شود.
• هر پردازش یک اولویت دارد. پردازش دارای بالاترین اولویت ابتدا اجرا می‌شود و همین طور تا آخرین پردازش.
• پردازش‌های دارای اولویت یکسان به روش «اجرا به ترتیب ورود» اجرا می‌شوند.
• اولویت می‌تواند بر مبنای الزامات حافظه، الزامات زمانی یا هر الزام دیگر برای منابع تعیین شود.

در جدول زیر پردازش‌ها، زمان رسیدن، زمان اجرا و اولویت آن‌ها داده شده است. در این جدول عدد 1 دارای کمترین اولویت است.

زمان انتظار هر پردازش به صورت زیر است:

میانگین زمان انتظار به صورت زیر است:

(0 + 10 + 12 + 2)/4 = 24 / 4 = 6

کوتاه‌ترین زمان باقی‌مانده

این روش خصوصیات زیر را دارد:

• کوتاه‌ترین زمان باقی‌مانده (SRT) نسخه preemptive از الگوریتم SNJ محسوب می‌شود.
• زمان پردازنده به وظیفه‌ای که خاتمه یافتن آن به کمترین زمان نیاز دارد تخصیص می‌یابد؛ اما می‌تواند به وظیفه جدیدتری که زمان اجرای کوتاه‌تری دارد نیز اختصاص یابد.
• پیاده‌سازی سیستم‌های تعاملی که در آن زمان مورد نیاز CPU مشخص نباشد در این روش ممکن نیست.
• این روش غالباً در محیط‌های دسته‌ای که کوتاه‌ترین کار باید بالاترین اولویت را داشته باشد مورد استفاده قرار می‌گیرد.

زمان‌بندی راند رابین یا نوبت گردشی

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

زمان انتظار هر پردازش به صورت زیر است:

میانگین زمان انتظار:

(9+2+12+11) / 4 = 8.5

زمان‌بندی صف چند سطحی

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

• صف‌های چندگانه‌ای برای پردازش‌های دارای خصوصیات مشترک نگهداری می‌شوند.
• هر صف می‌تواند الگوریتم زمان‌بندی خاص خود را داشته باشد.
• اولویت‌هایی برای هر صف تعیین می‌شود.

برای مثال کارهای مرتبط با CPU را می‌توان در یک صف زمان‌بندی کرد و همه کارهای مرتبط با I/O را نیز می‌توان در صف دیگری جمع‌بندی نمود. سپس زمان‌بندی پردازش به نوبت وظایف کارها را از هر صف انتخاب می‌کند و آن‌ها را بر اساس الگویتم تعیین شده برای هر صف به CPU تخصیص می‌دهد.

اگر این مطلب برایتان مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های علوم کامپیوتر
• آموزش سیستم های عامل - فرادرس
• مجموعه آموزش‌های مهندسی نرم‌افزار
• مفاهیم سیستم عامل — راهنمای جامع
• مجموعه آموزش‌های پایگاه داده و سیستم های مدیریت اطلاعات
• پردازش‌ها در سیستم عامل — راهنمای جامع

==