یک فرآیند (Process) اساساً یک برنامه در حال اجراست.

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

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

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

 

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

1- بهره وری پردازنده: در صفر زمانی که پردازنده مشغول است.

2- توان عملیاتی (Through put): مقدار کار انجام شده در واحد زمان

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

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

 

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

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

1- الگوریتم FCFS یا FIFO

در این الگوریتم فرآیندها CPU را به ترتیبی که درخواست میکنند، در اختیار میگیرند.

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

 

اهداف و مزایای الگوریتم FCFS عبارتند از:

– سادگی

– قابلیت پیاده سازی

– انصاف و عدالت

– عدم وجود قحطی (گرسنگی)

 

میانگین زمان های برگشت و انتظار نسبتاً بالا از نقاط ضعف و معایب الگوریتم FCFS است.

 

2- الگوریتم Shortest Job First

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

این الگوریتم انحصاری است و به کارهای کوچک اولویت میدهد.

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

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

 

تخمین زمان فرآیند

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

Sn+1 = (1-α)Sn + αtn

که در آن Tn مقدار واقعی ای است که در مرحله n اجرا کردیم، Sn مقدار تخمینی برای مرحله n  و S1 را برابر صفر فرض میکنیم.

همچنین باید در نظر داشت که α همواره بین 0 و 1 است.

 

3- الگوریتم Highest Response Ratio Next

در الگوریتم انحصاری بالاترین نسبت پاسخ (یا به اختصار HRRN) هر گاه فرآیند جاری تکمیل یا بلوکه گردد، کاری که در بین کلیه کارهای اماده دارای بیشتری مقدار “نسبت پاسخ” باشد، برای اجرا انتخاب میشود.

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

که در آن w معرف زمان انتظار کار از لحظه ورود تا کنون و s نشان دهنده زمان سرویس (اجرای) آن کار است.

 

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

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

 

 

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

1- نوبت چرخشی یا Round Robin

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

به کوانتم برش زمانی نیز میگویند.

واضح است که فرآیند میتواند در طول کوانتم اختصاص داده شده به آن اجرا شود؛ در صورتی که مدت زمان پردازش فرآیند برابر با زمان اختصاص داده شده (کوانتم) نباشد، دو حالت زیر به وجود می آید:

– اگر فرآیند در پایان کوانتم هنوز در حال اجرا باشد، CPU از آن گرفته شده و به فرآیند دیگری واگذار میشود. (زمان بندی غیر انحصاری)

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

 

اهداف و مزایای الگوریتم Round Robin عبارتند از:

– تضمین زمان پاسخ مطلوب برای کارهای معمولی کوچک

– نداشتن قحطی

– انصاف و عدالت

– سادگی

 

از نقاط ضعف و معایب الگوریتم RR نیز میتوان به سه مورد زیر اشاره کرد:

– سربار تعداد زیاد تعویض متن و کاهش بهره وری پردازنده

– میانگین زمان پاسخ و انتظار بالا

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

 

 

2- الگوریتم Shortest Remaining Time First (یا به اختصار SRTF)

نسخه غیر انحصاری “از ابتدا کوتاه ترین کار”، الگوریتم “کوتاه ترین زمان باقی مانده” (SRT) می باشد.

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

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

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

 

3- الگوریتم Multi Level feedback Queue & Multi Level Queue

این روش با ایجاد صف های چندگانه (Multi Queue) کلاس های اولویت ایجاد میکند.

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

فرآیندها در بالاترین کلاس، به مدت یک کوانتم اجرا میشوند. فرآیندهای کلاس بعدی، 2 کوانتم، فرآیند های کلاس بعد، 4 کوانتم و به همین ترتیب، فرآیند درون صف Qn ، تعداد 2 به قوه n کوانتم میگیرد.

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

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

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

این الگوریتم با نام الگوریتم صف های چند سطحی بازخورد (Multiple feedback Queues یا به اختصاری MLFQ) نیز شناخته میشود.

 

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

اگر الگوریتم پایه را بهصورت 2nQ – MLFQ بشناسیم که در صف شماره n (منظور Qn است.) به هر فرایند 2 به قوه n کوانتم تخصیص داده میشود، الگوریتم هایی مانند nQ – MLFQ و 1Q – MLFQ نیز وجود دارند که در صف شماره n آنها به هر فرآیند به ترتیب n و 1 کوانتم اختصاص داده میشود.

 

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

مثلاً میتوانیم سه صف داشته باشیم که در صف Qn یک کوانتم و در صف Q1 دو کوانتم به فرآیندها تخصیص دهیم؛ اما فرآیندهای صف سوم را به الگوریتم انحصاری FCFS زمان بندی و آنها را اجرا کنیم تا خاتمه یابند و یا مسدود شده و پس از بیداری به انتهای صف اول بروند.

 

مزایای الگوریتم MLFQ عبارتند از:

– تضمین زمان پاسخ مطلوب برای کارهای کوچک

– کاهش لگاریتمی نرخ تعویض متن

– اهمیت دادن به کارهای محدود به I/O

– قابلیت پیاده سازی

– اهمیت دادن به کارهای کوچک، بدون نیاز به دانستن زمان سرویس فرآیند از قبل یا نیاز به تخمین آن

 

نقاط ضعف و معایب الگوریتم MLFQ عبارتند از:

– قحطی (گرسنگی) کارهای طولانی

– پیچیدگی

– میانگین زمان پاسخ و انتظار بالا

 

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

 

 

زمان بندی بلادرنگ (Real Time)

CPU در صورتی میتواند به این وقایع پاسخ دهد که داشته باشیم:

C1/P1 + C2/P2 + C3/P3 + … + Cm/Pm <= 1

در فرمول بالا Ci (یعنی CBT مورد نیاز) و Pi (دوره تناوب) بر حسب برش زمانی هستند یعنی چند TB.

(علامت <= به معنی کوچکتر یا مساوی است.)

ذکر چند نکته زیر در مورد زمان بندی حائز اهمیت است:

– فرآیندها فضای مشترک آدرس دهی ندارند ولی ریسمان های داخل یک فرآیند فضای مشترک آدرس دهی دارند.

– چنانچه 80% از CBT های مجموعه ای از فرآیند ها، کوتاه تر از کوانتم باشند، آنگاه میانگین زمان پاسخ دهی این مجموعه فرآیندها میتواند مطلوب باشد. (در الگوریتم RR)

– در سیستم اشتراک زمانی وقت پردازنده به طور مساوری بین فرآیندها تقسیم میشود؛ هنگامی که فرآیندی به اتمام رسید وقت پردازنده بین مابقی آنها به طور مساوی تقسیم میگردد.

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

 

– تعویض اجرای فرآیندها، تعویض متن (Context Switch) نام دارد.

– تعویض متن توسط بخشی از سیستم عامل به نام Dispatcher انجام میشود.

 

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

– زمان بند سطح پایین: همگام کردن منطقی برنامه ها

– زمان بند سطح وسط: تنظیم اولویت و عملیات برش زمانی

– زمان بندی سطح بالا: ورود کارها به داخل سیستم