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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم زمان بندی نوبت گردشی (به انگلیسی: 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»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد.