---

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

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

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

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

---

فرآیند پردازنده چیست ؟

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

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

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

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

---

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

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

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

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

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

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

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

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

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

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

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

---

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

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

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

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

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

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

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

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

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

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

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

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

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

---

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

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

الگوریتم زمانبندی FCFS (FIFO) ؛ first come first self

نوبتی مانند صف نونوایی . این الگوریتم ساده ترین الگوریتم زمانبندی است . در این روش کار ها با همان ترتیب ورود به سیستم در صف قرار گرفته و از ابتدا صف به ترتیب پردازنده را در اختیار میگیرد .
نکته ؛ FCFS یک الگوریتم انحصاری است . این الگوریتم مشکل قحطی زدگی ندارند ( ۴ فرایند P1 , P2 , P3 , P4 که ب ترتیب وارد شدند . #میانگین_زمان_انتظار میشه ۵ . فرایندP1 به محض ورود پردازنده را در اختیار گرفته بنابراین زمان انتظار صفر می باشد . فرایند p2 چهار میلی ثانیه و p3 هفت و p4 نه میلی ثانیه منتظر می مامند . بنابراین میانگین زمان انتظار فرایند ها ۵ میلی ثانیه می باشد . در واقا زمان انتظار هی فرایند برابر است با جمع « زمان انتظار همون فرایند و جمع فرایند های قبلی »)

---

الگوریتم SJF ؛ short job first

کوتاه ترین کار اول وارد میشه ! در این روش ابتدا کاری برای اجرا انتخاب می شود که از همه #زمان_اجرا کمتری مصرف میکند
نکته : این الگوریتم را SPN یا SPT هم میگویند .یک الگوریتم انحصاری است . یک نقص عمده این الگوریتم این است که ممکن است باعث قحطی زدگی فرایند طولانی طولانی شود . ب این ترتیب ک اگر همواره تعدادی فرایند کوچک وارد سیستم شود . اجرا فرایند های بزرگ ب طور متناوب به تعویق می افتد .این روال حتی ممکن است تا بی نهایت ادامه یابد و هیچگاه نوبت به اجرا فرایند های بزرگ نرسد .در این روش اگر ۲ فرایند مدت زمان اجرا برابری داشته باشند بر اساس FCFS زمانبندی می شوند . مثل ۴ فرایند با زمان اجرا ( CBT ) ۲ میلی ثانیه )
در محاسبه زمان اجرا ، آخری از سمت راست حساب میشه و صفر اول حساب نمیشه ( مانند زمان انتظار )
نکته : هدف الگوریتم SJF به حداقل رساندن میانگین زمان انتظار و زمان اجرا و در نتیجه میانگین زمان گردش کار ها است . در عمل نمی توان الگوریتم SJF را پیاده سازی کرد زیرا ؛ سیستم عامل زمان اجرا فرایند ها را از قبل نمی داند و تنها کاری که میتواند انجام دهد ، این است که زمان اجرا فرایند ها را فقط حدس زده و به طور تقریبی بدست آورد .

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

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

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

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

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

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

---

الگوریتم RR ؛ round robin

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

و به انتها یک صف وارد می شوند . سپس پردازنده از ابتدا صف شروع کرده و ب هر فرایند حداکثر ب اندازع ۱ برش زمانی سرویس می دهد . در واقع پس از اینکه برش زمانب یک فرایند ب پایان رسید ، پردازنده ان فرایند را رها کرده به سراغ فرایند بعد موجود در صف می رود .این عمل انقدر تکرار می شود تا پردازنده به انتها صف فرآیند های اماده برسد. ب عبارتی دیگر فرآیند ها در یک صف دایره ای ، سازماندهی می شوند و پردازنده بصورت #دوار در این صف حرکت کرده و ب هر فرایند فقط یک اسلایس سرویس می دهد .
نکته ؛ ب برش زمانی, کوانتوم زمانی می گویند.
مثال ؛ ( ۳ فرایند P1 , P2 ,P3 را در نظر بگیرید .با استفاده از الگوریتم RR و با برش زمانی ۱ میلی ثانیه میانگین زمان انتظار و میانگین زمان پاسخ فرایند ها را بدست اورید . فرآیند ها در لحظه صفر و به ترتیب نام وارد شدند)
نکته: یکی از اهداف مهم الگوریتم RR رعایت عدالت و مساوات است . الگوریتم RR در سیستم های اشتراک زمانی به خوبی استفاده می شود .

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

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

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

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

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

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

---

الگوریتم SRT

در این الگوریتم اگر حین اجرای یک فرایند ، فرایندی وارد شود که زمان اجرای کوتاه تری داشته باشد، در این زمان ، پردازنده را در اختیار میگیرد. این الگوریتم را به نام های srpt , srtf و srtn می شناسند.
نکته : اگر لحضه ورود همه فرایند ها یکی باشد، الگوریتم srt مشابه sjf می‌باشد.
نکته : در این الگوریتم نیز همانند الگوریتم sjf احتمال قحطی برای کار های بزرگ وجود دارد.

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

---

الگوریتم زمانبندی HRN – HRRN

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

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

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

---

الگوریتم Prority

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

1. این الگوریتم هم انحصاری و هم غیر انحصاری می‌باشد.
2. در این نوع الگوریتم فرایند های با الویت کمتر ، دچار قحطی زدگی می‌شوند.
3. یک الویت می‌تواند هم استاتیک باشد هم داینامیک.

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

---

الگوریتم MLQ

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

1. فرایند های سیستمی
2. فرایند های محاوره ای ( غیر انحصاری)
3. فرایند عای دسته ای ( انحصاری)

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

---

الگوریتم MLFQ

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

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

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

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

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

---

الگوریتم LPT

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

---

الگوریتم Lottery

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

1. در این روش فرآیند های با اولویت بالاتر هستند که بلیط های بیشتری داشته باشند .
2. الگوریتم لاتاری ، مشکل قحطی زدگی ندارد ( زیرا تقسیم شده و محدود نشده )
3. فرایند ها می توانند بلیط های خود را با هم مبادله کنند .
4. دلیل غیر انحصاری بودن الگوریتم لاتاری ، ان است که که هنگامی یک فرایند پردازنده را در اختیار دارد . پس از پایان برش زمانی پردازنده ، از وی گرفته شده و به فرایند دیگری ک بلیط را دارد ، داده می شود .

---

الگوریتم graneted

زمان بندی تضمین شده . یکی از روش های متفاوت در زمانبندی گارانتی اسکژولینگ می باشد . در این روش ابتدا با کاربران درباره سهمشان از پردازنده توافق شده . سپس سهم هر یک دادع می شود . به این معنا که دقیقا بداند هر فرایند از ابتدا تاکنون چه مدت از پردازنده را استفاده کرده و همچنین چ مقدار از سهم توافق شده باقی مانده است .غیر انحصاری و قحطی زدگی ندارد .

---

الگوریتم FSS

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

---

آیا این مقاله برای شما مفید بود ؟ چنانچه سوالی دارید ، از سید علی ابراهیمی بپرسید !