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

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

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

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

یک فرآیند (Process) اساساً یک برنامه‌ی در حال اجراست. منظور از برنامه در حال اجرا، کاری است که توسط زمان‌بندِ کار، انتخاب و وارد گردونه‌ی اجرا شده است ولی هنوز پایان نیافته و از سیستم خارج نشده است. این فرآیند الزاماً در حال حاضر CPU را در اختیار ندارد.

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

معیارهای زمان‌بندی پردازنده

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

به طور کلی این معیارها به دو دسته تقسیم‌بندی می‌شوند.

1. معیارهای از دید کاربر (مانند زمان پاسخ)
2. معیارهای از دید سیستم (مانند توان عملیاتی و بهره‌وری پردازنده)

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

1- اولین معیار، زمان انتظار هر فرآیند است.

زمان انتظار فرآیند به میزان زمانی گفته می‌شود که فرآیند باید منتظر بماند تا پردازنده (CPU) به آن تعلق بگیرد.

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

 

2- دومین معیار، توان عملیاتی (Throughput) پردازنده است. منظور از توان عملیاتی پردازنده، تعداد کار انجام شده در واحد زمان توسط پردازنده است.

 

3- زمان بازگشت (Turn Around Time): فاصله زمانی بین لحظه تحویل تا تکمیل فرآیند؛ به عبارت دیگر مدت زمانی که Job در سیستم قرار دارد.

RT = F.T – A.T
#RT: Response Time , F.T: Finish Time , A.T: Arrival Time

 

4- زمان پاسخگویی (Response Time): فاصله زمانی ورود پردازش به سیستم تا شروع دریافت اولین پاسخ آن

 

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

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

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

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

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

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

چند الگوریتم انحصاری زمانبندی پردازنده عبارت‌اند از:

• الگوریتم FCFS
• الگوریتم SJF
• الگوریتم HRRN

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

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

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

چند الگوریتم غیرانحصاری زمانبندی پردازنده عبارت‌اند از:

• الگوریتم RR
• الگوریتم SRTF
• الگوریتم MLFQ

 

 

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

الگوریتم FCFS (سرویس به ترتیب ورود)

ساده‌ترین الگوریتم زمان‌بندی پردازنده، الگوریتم FCFS (مخفف First Come First Serve) است. زمان‌بندی فرآیندها در این الگوریتم بر اساس زمان ورود آن‌ها به سیستم تعیین می‌شود. یعنی آن فرآیندی که زودتر وارد سیستم شده، زودتر هم بر روی پردازنده اجرا خواهد شد.

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

مزایای الگوریتم FCFS در سیستم عامل

• سادگی اجرا
• نوعی انصاف و عدالت در اجرا
• عدم وجود قحطی (گرسنگی)
• حداقل بودن سربار اجرایی (زیرا نیازی به اطلاعات قبلی یا اضافه در مورد فرآیندها ندارد)

معایب الگوریتم FCFS (ترتیب ورود)

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

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

 

الگوریتم SJF (کوتاه‌ترین فرآیند)

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

وقتی که چند کار با اهمیت یکسان برای اجرا شدن در صف ورودی قرار می‌گیرند، زمان‌بند باید ابتدا کوتاه‌ترین کار (Shortest Jib First یا به اختصار SJF) را انتخاب کند.

به این الگوریتم گاهی الگوریتم SPN (مخفف Shortest Process Next) نیز گفته می‌شود.

 

مزایای الگوریتم SJF

اگر کارها به طور همزمان وارد سیستم شوند، میانگین زمان برگشت و زمان انتظار، حداقل خواهد بود.

معایب الگوریتم SJF در سیستم عامل

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

سایر مشکلات این الگوریتم عبارت‌اند از:

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

 

الگوریتم تخمین زمان فرآیند

جهت تخمین زمان فرآیند در الگوریتم SJF از فرمول زیر استفاده می‌کنیم.

S_n+1 = (1-α)S_n + αt_n

که در آن T_n مقدار زمان واقعی اجرای فرآیند در مرحله n بوده و S_n مقدار تخمینی برای مرحله nاُم است.

مقدار اولیه تخمین (یعنی S₁) را برابر صفر فرض کرده و مقدار ضریب α همواره بین 0 و 1 است.

 

 

الگوریتم HRRN در سیستم عامل

در الگوریتم انحصاری بالاترین نسبت پاسخ (الگوریتم Highest Response Ratio Next) هر گاه فرآیند جاری تکمیل یا بلوکه گردد، کاری که در بین کلیه کارهای آماده دارای بیشترین مقدار «نسبت پاسخ» باشد برای اجرا انتخاب خواهد شد.

نسبت پاسخ هر کار با فرمول زیر مشخص می‌شود:

(w+s)/s = w/s + 1

 

در این الگوریتم زمان‌بندی پردازنده نیز مانند الگوریتم SJF کارهای کوتاه‌تر در شرایط مساوی (زمان انتظار یکسان)، نسبت به کارهای طولانی اولویت دارند. زیرا مخرج کسر w/s برای آن‌ها کوچک‌تر است. با این رفتار، الگوریتم HRRN میانگین زمان انتظار خود را کاهش می‌دهد.

البته برای این‌که این مزیت به قیمت ایجاد قحطی (گرسنگی) تمام نشود، مشابه الگوریتم FCFS به کارهایی که برای اجرا بیشتر منتظر مانده‌اند نیز اهمیت می‌دهد. در حقیقت آن‌هایی که صورت کسر w/s برایشان بزرگ‌تر است اهمیت بیشتری پیدا می‌کنند.

 

الگوریتم rr

الگوریتم نوبت چرخشی یا همان الگوریتم Round Robin به هر فرایند یک بازه زمانی به نام کوانتوم (ذره یا تکه‌ی کوچک) اختصاص داده تا بتواند در آن کوانتوم اجرا شود.

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

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

 

مزایای الگوریتم RR

• تضمین زمان پاسخ مطلوب برای کارهای معمولی کوچک
• نداشتن قحطی و گرسنگی در سیستم
• سادگی اجرا
• عملکرد عادلانه

معایب الگوریتم rr در سیستم عامل

انتخاب برهه زمانی (مدت زمان کوانتوم) یکی از معیارهای مشخص‌کننده عملکرد الگوریتم rr است. اگر کوانتوم زمانی خیلی کوچک باشد، توان عملیاتی (throughput سیستم عامل) کم خواهد شد.

دو مورد از معایب دیگر الگوریتم round robin عبارت‌اند از:

• سربار تعداد زیاد تعویض میان اجرای فرآیندها
• میانگین زمان اجرای نسبتاً بالا در پردازش‌های طولانی

 

 

الگوریتم SRTF برای زمانبندی پردازنده

الگوریتم کوتاه‌ترین زمان باقی‌مانده یا Shortest Remaining Time First یک الگوریتم غیرانحصاری بوده که ملاک انتخاب فرآیند را زمان باقی‌مانده‌ی اجرا در نظر گرفته است.

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

• در این الگوریتم زمان‌های برگشت و انتظار حداقل است.
• الگوریتم SRTF مشکلاتی نظیر پیاده‌سازی (نیاز به زمان اجرای کارها) و گرسنگی کارهای طولانی دارد.

 

الگوریتم MLFQ

الگوریتم زمان‌بندی صف بازخوردی چند سطحی (Multi Level feedback Queue & Multi Level Queue) یک الگوریتم غیرانحصاری برای مدیریت فرآیندها در پردازنده است.

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

زمان اجرای پردازنده مشابه الگوریتم rr به برش‌های زمانی (کوانتوم) تقسیم شده و هر فرآیند متناسب با کلاس خود، از این کوانتوم‌ها استفاده می‌کند.

فرآیندهای موجود در بالاترین کلاس، به مدت یک کوانتوم اجرا می‌شوند. فرآیندهای کلاس بعدی، 2 کوانتوم، کلاس بعدی 4 کوانتوم و به همین روال تا آخرین صف.

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

در الگوریتم MLFQ هنگامی به سراغ فرآیندهای یک کلاس می‌رویم که صف تمامی کلاس‌های بالاتر از آن خالی باشد.

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

مشتقات الگوریتم MLFQ زمانبندی پردازنده

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

اگر الگوریتم پایه را به صورت . بشناسیم (در صف شماره n به هر فرآیند 2ⁿ کوانتوم تخصیص داده می‌شود) الگوریتم‌هایی مانند دو مورد زیر را نیز داریم:

• nQ – MLFQ که در آن به فرآیندهای موجود در صف n تعداد n کوانتوم زمانی اختصاص داده می‌شود.
• 1Q – MLFQ که در آن به فرآیندهای صف nاُم، یک کوانتوم اختصاص می‌یابد.

برای محدود کردن تعداد صف‌ها، روش‌های مختلفی در عمل به کار گرفته شده است.

برای مثال، می‌توانیم سه صف داشته باشیم که در صف Q₀ یک کوانتوم و در صف Q₁ دو کوانتوم به فرآیندها تخصیص دهیم؛ اما فرآیندهای صف سوم را با الگوریتم انحصاری FCFS زمانبندی کرده و اجرا کنیم. در این‌صورت فرآیندهای صف سوم، آن‌قدر ادامه می‌یابند تا خاتمه یافته یا مسدود شوند و پس از بیداری به انتهای صف اول خواهد رفت.

 

مزایای الگوریتم MLFQ

• تضمین زمان پاسخ مطلوب برای کارهای کوچک
• کاهش لگاریتمی نرخ تعویض متن
• اهمیت دادن به کارهای محدود به I/O
• اهمیت دادن به کارهای کوچک، بدون نیاز به دانستن زمان سرویس فرآیند از قبل یا نیاز به تخمین آن

معایب الگوریتم MLFQ در سیستم عامل

• گرسنگی کارهای طولانی
• پیچیدگی نسبتاً بالا در پیاده‌سازی
• میانگین زمان پاسخ و انتظار بالا برای برخی فرآیندها

 

توضیحات تکمیلی در مورد الگوریتم‌های زمانبندی پردازنده

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

• فرآیندها، فضای مشترک آدرس‌دهی ندارند ولی نخ‌های داخل یک فرآیند، فضای مشترک آدرس‌دهی دارند. (نخ چیست ؟)
• چنانچه 80 درصد از CBTهای مجموعه‌ای از فرآیند‌ها، کوتاه‌تر از کوانتم باشند، آنگاه میانگین زمان پاسخ‌دهی در این مجموعه از فرآیندها می‌تواند مطلوب باشد. (در الگوریتم RR)
• در سیستم اشتراک زمانی، وقت پردازنده به طور مساوی بین فرآیند‌ها تقسیم می‌شود؛ هنگامی که فرآیندی به اتمام رسید وقت پردازنده بین مابقی آن‌ها به طور مساوی تقسیم می‌گردد.
• در سیستم اشتراک زمانی، زمان به کار‌گیری پردازنده از فرمول زیر به دست می‌آید:

TS / TS+CST
#TS: Time Sliue , CST: Context Switch Time

عملیات تعویض اجرای فرآیندها، تعویض متن (Context Switch) نام دارد. که این کار توسط بخشی از سیستم عامل به نام Dispatcher انجام می‌شود.

 

در زمان‌بندی سیستم‌های بلادرنگ (Real Time)، پردازنده مرکزی در صورتی می‌تواند به وقایع پاسخ دهد که داشته باشیم:

C₁/P₁ + C₂/P₂ + C₃/P₃ + … + C_m/P_m <= 1

در فرمول بالا C_i (یعنی CBT مورد نیاز) و P_i (دوره تناوب) بر حسب برش زمانی هستند یعنی چند TB. (علامت <= به معنی کوچکتر یا مساوی است.)

در حالت کلی، انواع زمانبند‌های سیستم عامل به سه دسته تقسیم‌بندی می‌شوند:

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

 

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

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

الگوریتم‌های زمانبندی به طور کلی به دو دسته انحصاری و غیرانحصاری تقسیم می‌شوند. روش‌ها و الگوریتم‌های مختلفی وجود دارند که در این مقاله با مهم‌ترین و پرکاربردترین آن‌ها آشنا شدیم. الگوریتم SJF، الگوریتم rr و الگوریتم MLFQ جزء بهترین الگوریتم‌های زمانبندی پردازنده هستند.

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