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

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

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

زمان بندی پردازش

به منظور ایجاد برنامه‌های پردازشی عادلانه، الگوریتم Round-robin به‌طور کلی بخش‌بندی زمان را در نظر می‌گیرد. این کار به صورت دادن هر وظیفه به مرتبه زمانی یا کوانتوم (بهرهٔ آن در CPU) انجام می‌گیرد و چنانچه وظیفه کامل نشده باشد جلوگیری از اجرای آن می‌کند. وظیفه‌ای که زمان بعدی مرتبه زمانی را دوباره به دست می‌آورد مدیریت آن پردازش را به عهده می‌گیرد. در غیاب شراکت زمانی اگر کوانتوم‌ها نسبتاً بزرگ تر از اندازه‌های وظیفه باشند پردازشی که وظیفه‌های بزرگی تولید می‌کند بیش از پردازش‌های دیگر مورد علاقه هستند. مثال: اگر مرتبه زمانی را ۱۰۰ میلی ثانیه در نظر بگیریم و وظیفه ۱ زمان کلی ۲۵۰ میلی‌ثانیه را تا کامل شدن اختیار کند، الگوریتم تعیین زمان Round-robin وظیفه را بعد از ۱۰۰ میلی‌ثانیه به تعویق می‌اندازد و وظیفه‌های دیگر زمان خودشان را به CPU می‌دهند. زمانی که وظیفه‌های دیگر سهم مساوی دارند (۱۰۰ میلی‌ثانیه برای هر کدام) وظیفه ۱ سهمیه دیگری از زمان CPU را می‌گیرد و چرخه تکرار خواهد شد. این پردازش تا زمانی که وظیفه تمام شود ادامه می‌یابد و احتیاج به زمان بیشتری روی CPU ندارد. روش دیگر بدین صورت است که تقسیم بندی تمام پردازش‌ها به تعداد مساوی کوانتوم‌ها به‌طوری‌که اندازه کوانتوم متناسب با اندازه پردازش است. از این رو تمام پرداش‌ها در یک زمان ،پایان می‌یابد.

زمان بندی بسته اطلاعات

در تغییر دادن داده‌ها و دیگر تسهیم کنندگان آماری الگوریتم Round-robin می‌تواند به عنوان یک چاره به منظور مرتب کردن داده‌ها استفاده شود. یک تسهیم‌کننده، یک مبادله یا یک مسیر یاب را که الگوریتم زمان بندی Round-robin را حمایت می‌کنند، برای هر جریان داده‌ها و اطلاعات صف داده جدا داردکه جریان داده‌ها توسط آدرس منبع و مقصد آن شناخته می‌شود. الگوریتم اجازه می‌دهد که هر جریان داده‌های فعال که دارد بسته اطلاعات در صف داده‌ها گرفتن در انتقال بسته‌ها روی کانال‌های تقسیم شده در یک نظم و ترتیب تکراری تناوبی. الگوریتم زمان بندی نگه دارنده کار است بدین معنی که اگر یک جریان بیرون بسته‌ها باشد جریان داده‌های بعدی جای آن را خواهد گرفت از این رو الگوریتم سعی دارد که منابع پیوندی را از رفتن به مبانی بیهوده و غیرقابل استفاده جلوگیری کند. الگوریتم Round-robin منجر به انصاف بیشینه – کمینه می‌شود اگر بسته داده‌ها به صورت مساوی اندازه بندی شده باشند، زمانی که جریان داده‌ها در انتظار قرار گرفته‌است طولانی‌ترین زمان برتری زمان بندی را نوید می‌دهد. این امر ممکن است که مطلوب نباشد که اندازه بسته داده‌ها از یک وظیفه تا وظیفه دیگر به صورت گسترده تغییر کند. یک کاربر که بسته‌های بزرگ تر تولید کند از دیگر کاربران بیشتر مورد علاقه واقع خواهد شد. در این مورد ایجاد صف داده‌های منصفانه ترجیح داده می‌شود. اگر ضمانت قرار دادن یا بی‌تفاوت بودن کیفیت سرویس دهی پیشنهاد شود و نه تنها بهترین تلاش برای ارتباط برقرار کردن الگوریتم زمان بندی کسری Round-robin (DRR)، الگوریتم Round-robin وزین (WRR) یا الگوریتم صف داده‌های منصفانه وزین (WFQ) ممکن است در نظر گرفته شود. در شبکه‌هایی که نیاز به دسترسی زیاد است، جایی که چندین ترمینال به یک محیط فیزیکی تقسیم شد وصل شده باشند، الگوریتم زمان بندی Round-robin ممکن است توسط شماتیک دسترسی کانال‌های گذری حمایت شود نظیر رینگ نشان، یا توسط شمارش یا نگاهداری منابع از یک ایستگاه کنترل مرکزی باشد. در یک بسته بی سیم متمرکز شده شبکه رادیویی جایی که ایستگاه‌های زیادی از یک فرکانس کانال سهم دارند، الگوریتم زمان بندی در یک ایستگاه پایه مرکزی ممکن است برش‌های زمانی را برای ایستگاه‌های سیار نگاه داری کنند در مد Round-robin و انصاف را تأمین کنند. اما اگر سازگاری پیوندی استفاده شود موجب خواهد شد که زمانی طولانی تر برای انتقال یک مقدار معینی داده برای کاربران غنی به کار گرفته شود نسبت به دیگران زمانی که شرایط کانال فرق کند. شاید پر بازده این باشد که انتظار کشیدن برای انتقال تا زمانی که شرایط کانال تحت بهبود قرار بگیرد یا حداقل برتری زمان بندی به کاربران غنی داده شود. الگوریتم Round-robin از این استفاده نمی‌کند. ظرفیت پذیرش بالاتر و بازده طیف سیستم می‌تواند با زمان بندی وابسته به کانال به دست آید. برای مثال یک الگوریتم تناسبی منصفانه یا زمان بندی ظرفیت پذیرش بیشینه. توجه داشته باشید که این موضوع آخر با کمبود زمان بندی نامطلوب شناخته می‌شود.

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Round-robin scheduling». در دانشنامهٔ ویکی‌پدیای انگلیسی.