الگوریتم راند رابین در سیستم عامل – آموزش کامل الگوریتم راند رابین همراه با ۲ مثال

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

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

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

الگوریتم راند رابین (Round Robin)

الگوریتم زمان‌بندی Round Robin (RR) عمدتاً برای سیستم‌های اشتراک زمانی طراحی‌شده است و ترکیبی از الگوریتم‌های زمان‌بندی FCFS و Pre_emptive است. این الگوریتم در دسته الگوریتم‌های پیشگیرانه قرار دارد و بلادرنگ است زیرا در یک محدوده زمانی خاص به رویداد پاسخ می‌دهد.

برش‌های زمانی به‌صورت دایره‌ای به فرآیندها اختصاص می‌یابد که مقداری ثابت است و کوانتوم نامیده می‌شود، طول کوانتوم زمانی معمولاً بین ۱۰ تا ۱۰۰ میلی‌ثانیه است. اگر زمان یک فرآیند مساوی یا کمتر از برش زمانی باشد، اجرای فرآیند به‌صورت کامل انجام‌شده و از صف آماده حذف می‌شود، در غیر این صورت برای تکمیل اجرای خود دوباره به‌صف برمی‌گردد. اگر کوانتوم زمانی خیلی کاهش یابد، روی راندمان CPU تأثیر می‌گذارد.

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

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

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

• الگوریتم های زمان بندی در سیستم عامل — ۱۰ الگوریتم زمان بندی پردازنده — کلیک کنید.

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

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

واژه‌های مهم

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

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

Turn Around Time= Completion Time – Arrival Time

Waiting Time (W.T): تفاوت بین زمان چرخش و زمان انفجار را نشان می‌دهد و به صورت محاسبه می‌شود:

Waiting Time= Turn Around Time – Burst Time

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

مثال۱:

اکنون به مثالی برای همین موضوع می‌پردازیم:

فرض کنید ۵ فرآیند با شناسه فرآیند و Burst Time (زمان انفجار) وجود دارد که در جدول زیر آورده شده است:

می‌توانیم اجرای فرآیندهای فوق را با استفاده از نمودار GANTT همانطور که در زیر نشان داده‌شده‌است نشان دهیم:کوانتوم زمانی برابر با ۲ واحد و فرض کنید تمامی فرآیندها به ۰ برسد.

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

Waiting time = Turn Around Time – Burst Time
P1 = 19 – ۶ = 13
P2 = 20 – ۵ = 15
P3 = 6 – ۲ = 4
P4 = 15 – ۳ = 12
P5 = 23 – ۷ = 16

Average waiting time = (13+15+4+12+16) / 5 = 12

اولین فرآیند یعنی P1 که ۶ واحد است از صف آماده انتخاب‌شده و برای ۲ واحد زمانی اجرا می‌شود، بقیه که برابر ۴ واحد است باقی می‌ماند. حالا نوبت فرآیند دو است که اجرا شود، P2 هم ۶ واحد زمانی است اما فقط ۲ واحد آن اجراشده و ۳ تا از آن باقی می‌ماند. و بعد نوبت به P3 می‌رسد، چون این فرآیند فقط ۲ واحد زمان است در همین مرحله اجراشده و به‌پایان می‌رسد. حال P4 اجرا می‌شود و ۱ واحد آن‌هم باقی می‌ماند و درنهایت با اجرای ۲ واحد از ۷ واحد فرآیند پنج، این دور تمام می‌شود و دوباره P1 اجرا می‌گردد.

بازهم ۲ واحد از P1 اجراشده و ۲ واحد دیگر باقی می‌ماند. نوبت به P2 می‌رسد و ۲ واحد هم از آن اجراشده و ۱ واحد باقی می‌ماند. P3 اجرا نمی‌شود چراکه در مرحله قبل اجرای آن به‌پایان رسیده و از صف خارج‌شده است. ۱ واحد باقیمانده‌ی P4 هم اجرا می‌شود و آن‌هم از صف خارج می‌گردد. بعد P5 اجراشده و ۳ واحد از آن باقی می‌ماند. در آخر هم ۲ واحد باقیمانده‌ی P1 و بعد ۱ واحد باقیمانده‌ی P2 و دو بار پشت سرهم P5 اجرا می‌شود که یک بار ۲ واحد و بار دیگر هم ۱ واحد اجرا می‌شوند و این الگوریتم به‌پایان می‌رسد.

در الگوریتم زمان‌بندی Round Robin، با کاهش زمان کوانتومی، سوئیچینگ زمینه افزایش می‌یابد. افزایش مقدار کوانتومی زمان منجر به گرسنگی زمانی می‌شود که ممکن است بسیاری از فرآیندها را متوقف کند. بنابراین، کوانتوم زمان نه باید بزرگ باشد و نه کوچک. اگر کوانتوم زمانی بی‌نهایت شود، الگوریتم زمان‌بندی Round Robin به‌تدریج به الگوریتم زمان‌بندی FCFS تبدیل می‌شود.

مثال ۲:

حال برای درک بهتر مثالی دیگر می‌زنیم:

اولین فرآیند یعنی P1 که ۵۳ واحد است از صف آماده انتخاب‌شده و برای ۲۰ واحد زمانی اجرا می‌شود، بقیه که برابر ۳۳ واحد است باقی می‌ماند. حالا نوبت فرآیند دو است که اجرا شود، P2 هم ۱۶ واحد زمانی است، چون این فرآیند فقط ۱۶ واحد زمان است در همین مرحله اجراشده و به‌پایان می‌رسد. بعد نوبت به P3 می‌رسد، این فرآیند ۶۸ واحد زمان است در این مرحله ۲۰ واحد آن اجراشده و بقیه به‌صف آماده برمی‌گردد و منتظر می‌ماند تا بار دیگر در کوانتوم بعدی اجرا شود.

حال P4 اجرا می‌شود، ۴ واحد آن‌هم باقی می‌ماند. دوباره P1 اجرا می‌گردد و بازهم ۲۰ واحد از آن اجراشده و ۱۳ واحد دیگر باقی می‌ماند. P2 اجرا نمی‌شود چراکه در مرحله قبل اجرای آن به‌پایان رسیده و از صف خارج‌شده است. نوبت به P3 می‌رسد و ۲۰ واحد هم از آن اجراشده و ۲۸ واحد باقی می‌ماند.  ۴ واحد باقیمانده‌ی P4 هم اجرا می‌شود و آن‌هم از صف خارج می‌گردد.

دوباره نوبت به P1 می‌رسد و ۱۳ واحد باقیمانده‌ی آن‌هم اجراشده و از صف خارج می‌شود. در آخر هم ۸ واحد باقیمانده‌ی P3 اجرا می‌شود و این الگوریتم به‌پایان می‌رسد.

الگوریتم راند رابین نوع خاصی از الگوریتم FCFS

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

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

در زمان‌بندی دوره‌ای، سیستم عامل توسط یک وقفه منظم (“تیک ساعت”) هدایت می‌شود. وظایف در یک دنباله ثابت برای اجرا انتخاب می‌شوند. در هر تیک ساعت، کار فعلی متوقف می‌شود و کار بعدی مجاز به شروع اجرا است. همه وظایف به‌عنوان اهمیت یکسانی در نظر گرفته می‌شوند و به‌نوبه خود برای زمان CPU خود منتظر می‌مانند. کارها مجاز نیستند تا تکمیل شوند، اما «Pre_empted» هستند، یعنی اجرای آنها در اواسط متوقف می‌شود. این نمونه‌ای از زمان‌بندی «پیشگیرانه» است.

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

• بررسی و مقایسه الگوریتم های زمانبندی در سیستم عامل — کلیک کنید.

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

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

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

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

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

کلیک کنید