زمانبندی نوبت چرخشی
 |
زمانبندی نوبت چرخشی (Round-robin Scheduling) یا (RR) یکی از الگوریتم‌هایی است که با فرایندها و زمان بندی شبکه کار می‌کند. پارامترهایی که عموماً استفاده می‌شوند، قطعات زمانی هستند که به هر فرایند بخش یکسان و به صورت ترتیب چرخشی انتساب داده می‌شود، تمام فرایندها بدون اولویت در نظر گرفته می‌شوند.(که به اجرای چرخشی معروف است) زمان بندی RR ساده، پیاده‌سازی آسان و بدون قحطی است. این زمان بندی هم چنین می‌تواند برای مسائل زمان بندی دیگر مثل زمان بندی بسته داده در شبکه‌های کامپیوتری بکار برده شود. این خط مشی سیستم عامل است.
نام الگوریتم از اصل نوبت چرخشی که در دیگر زمینه‌ها معروف است می‌آید، که هر فردی یک سهم یکسان از چیزی را در نوبت می‌گیرد.
زمان بندی فرایندها
[ویرایش]زمان بندی فرایندها به صورت منصفانه‌است، یک زمان بند RR عموماً اشتراک زمانی را در نظر می‌گیرد. به هر کار یک قطعه زمانی یا کوانتوم (توسط cpu اجازه داده می‌شود) داده می‌شود، اگر یک کار تمام نشده باشد به وسیله آن وقفه داده می‌شود و آن کار دوباره در زمان بعدی¬ یک قطعه زمانی به فرایند اختصاص می‌دهد. اگر اشتراک زمانی نباشد یا کوانتوم‌ها بزرگتر از سایز کارها باشند، یک فرایندی که کارهای بزرگ را تولید کرده‌است نسبت به فرایندهای دیگر مورد توجه قرار خواهد گرفت.
مثلاً اگر قطعه زمانی ۱۰۰ میلی ثانیه باشد و کار شماره یک، مجموعاً ۲۵۰ میلی ثانیه طول کشد تا کامل شود، زمان بند RR، کار را ۱۰۰ میلی ثانیه به تعویق می‌اندازد و به دیگر فرایندها زمانشان را روی cpu می‌دهد. اولین بار کارهای دیگر سهم یکسانشان را دارند؛ (۱۰۰ میلی ثانیه) کار شماره یک تخصیص دیگری از زمان cpu را خواهد گرفت و چرخه ادامه پیدا خواهد کرد. این فرایندها ادامه پیدا خواهند کرد تا زمانیکه کار تمام شود و احتیاجی به زمان بیشتری روی cpu نباشد.
کار۱: مجموعاً ۲۵۰ میلی ثانیه طول می‌کشد (کوانتوم ۱۰۰ میلی ثانیه)
- تخصیص اول: ۱۰۰ میلی ثانیه
- تخصیص دوم: ۱۰۰ میلی ثانیه
- تخصیص سوم: ۱۰۰ میلی ثانیه، اما کار۱ بعد از ۵۰ میلی ثانیه خاتمه می‌یابد.
- زمان کل cpu کار۱: ۲۵۰ میلی ثانیه
روش دیگر، تقسیم تمام فرایندها به یک عدد یکسان از کوانتوم زمانی مثل سایز کوانتوم که با سایز فرایند متناسب است، می‌باشد. بنابراین تمام فرایندها در یک زمان یکسان خاتمه می‌یابند.
زمان بندی بسته بندی شبکه
[ویرایش]در بهترین تلاش سوییچ کردن بسته و تسهیم آماری، زمان بندی RR می‌تواند به صورت تناوبی در صف بندی fcfs استفاده شود. یک تسهیم کننده، سوییچ یا روتر که از زمان بندی RR استفاده می‌کند یک صف جدا برای هر جریان داده دارد، که هر جریان داده ممکن است با آدرس‌های منبع و مقصد شناخته شود. الگوریتم اجازه می‌دهد هر جریان داده فعال که بسته‌های داده در صف دارد، یک نوبت در انتقال بسته روی یک کانال مشترک به صورت دوره‌ای در یک ترتیب پی در پی بگیرد. زمان بندی، نگهداری کار است ؛ یعنی اگر یک جریان خارج از بسته‌ها باشد، جریان داده بعدی در آن مکان قرار خواهد گرفت. بنابراین زمان بندی تلاش می‌کند تا از اینکه لینک منابع بلااستفاده باشند، جلوگیری می‌کند.
نتایج زمان بندی RR در max-min fairness، اگربسته‌های داده سایز یکسانی داشته باشند، بنابراین جریان داده‌ای که زمان بیشتری منتظر بوده‌است، اولویت زمان بندی به آن داده می‌شود. این ممکن است نامطلوب باشد اگر سایز بسته‌های داده از یک کار نسبت به کار دیگر خیلی متفاوت باشد. یک کاربری که بسته‌های بزرگتری تولید می‌کند نسبت به کاربران دیگر بیشتر مورد توجه قرار می‌گیرد. دراین مورد صف بندی منصفانه برتری دارد.
اگر ضمانت یا کیفیت متمایز سرویس پیشنهاد شود نه تنها ارتباطات بهترین تلاش بلکه زمانبندی کسر نوبت چرخشی (deficit round-robin(DRR))، زمان بندی نوبت چرخشی وزن دار (weighted round-robin(WRR)) یا صف بندی منصفانه وزن دار (weighted fair queuing ) مطرح می‌شود.
در شبکه‌های دسترسی چندگانه که چند پایانه به یک وسیله فیزیکی مشترک متصل هستند، زمان بندی RR ممکن است به وسیله شمای کانال دسترسی گذر نشانه مثل حلقه نشانه یا سرکشی (polling) یا ذخیره منابع از یک وضعیت کنترل مرکزی، تهیه شود.
در یک شبکه رادیویی بسته بدون سیم متمرکز، که وضعیت‌های زیادی روی یک کانال فرکانس به اشتراک گذاشته می‌شوند، یک الگوریتم زمان بند در یک وضعیت پایه مرکزی، ممکن است قطعات زمانی را برای وضعیت‌های مبایل به روش RR ذخیره و به صورت بی‌طرفانه تهیه کند. اگرچه انطباق لینک استفاده شود، آن یک زمان بیشتری برای کاربران پرهزینه نسبت به دیگران، برای انتقال مقدار معینی از داده خواهد گرفت از اینرو شرایط کانال تفاوت دارد. آن بیشتر مؤثر خواهد بود تا منتظر انتقال بمانیم تا زمانیکه شرایط کانال بهبود یابد یا زمان بندی اولویت را به کاربران با هزینه کمتری بدهد. زمان بندی RR از این استفاده نمی‌کند. ممکن است توان عملیاتی بالاتر و کارایی بینش سیستم به وسیله زمان بندی وابسته به کانال برسد. برای مثال یک الگوریتم به تناسب منصفانه یا زمان بندی توان عملیاتی بیشینه. توجه کنید که آخری توسط زمان بندی نامطلوب قحطی توصیف می‌شود. این نوع از زمان بندی یکی از الگوریتم‌های پایه برای سیستم عامل در کامپیوترهایی که از طریق ساختمان داده صف چرخشی پیاده‌سازی می‌شوند، است.
منابع
[ویرایش]- Silberschatz, Abraham; Galvin, Peter B.; Gagne, Greg (2010). "Process Scheduling". Operating System Concepts (8th ed.). John_Wiley_&_Sons (Asia). p. 194. ISBN 978-0-470-23399-3. "5.3.4 Round Robin Scheduling"