زمان‌بندی نوبت گردشی
 | برای تأییدپذیری کامل این مقاله به منابع بیشتری نیاز است. (سپتامبر ۲۰۲۶) |
زمان‌بندی نوبت گردشی (به انگلیسی: Round-robin scheduling) یا (RR) یکی از الگوریتم‌های ساده و پرکاربرد زمان‌بندی است که در درجهٔ نخست برای زمان‌بندی فرایندها در سیستم‌عامل و همچنین در برخی مسائل زمان‌بندی در شبکه‌های رایانه‌ای به کار می‌رود. در این روش، به هر فرایند یا کار، یک بازهٔ زمانی ثابت و معمولاً برابر با سایر فرایندها اختصاص داده می‌شود و فرایندها به صورت چرخشی و بدون اولویت‌بندی میان آن‌ها اجرا می‌شوند. این بازهٔ زمانی «کوانتوم» یا «قطعهٔ زمانی» نام دارد.
زمان‌بندی نوبت گردشی ساده، پیاده‌سازی آسانی دارد و در شرایط معمول از قحطی فرایندها جلوگیری می‌کند. نام این الگوریتم از مفهوم «نوبت گردشی» گرفته شده است که در آن هر فرد یا عضو یک مجموعه، سهم خود را به صورت نوبتی دریافت می‌کند.
زمان‌بندی فرایندها
[ویرایش | اشتراک‌گذاری]زمان‌بندی نوبت گردشی برای ایجاد اشتراک منصفانهٔ زمان پردازنده میان فرایندهای آماده طراحی شده است. یک زمان‌بند نوبت گردشی، معمولاً از اشتراک زمانی استفاده می‌کند. به هر فرایند یک کوانتوم یا قطعهٔ زمانی مشخص اختصاص داده می‌شود. اگر فرایند در پایان این بازه هنوز به اجرای خود ادامه دهد، اجرای آن متوقف یا به انتهای صف آماده منتقل می‌شود و فرایند بعدی فرصت استفاده از CPU را پیدا می‌کند. هنگامی که نوبت به آن فرایند دوباره برسد، اجرای آن برای یک کوانتوم دیگر ادامه پیدا می‌کند. این چرخه تا پایان یافتن همهٔ فرایندها ادامه می‌یابد.
در این روش، اگر کوانتوم زمانی بیش از اندازه بزرگ باشد، الگوریتم از نظر رفتاری به زمان‌بندی اول ورود، اول خروج (FCFS) نزدیک می‌شود؛ زیرا یک فرایند می‌تواند برای مدت نسبتاً طولانی پردازنده را در اختیار داشته باشد. از سوی دیگر، اگر کوانتوم بیش از حد کوچک انتخاب شود، تعداد تعویض‌های زمینه افزایش می‌یابد و بخشی از زمان پردازنده صرف سربار زمان‌بندی می‌شود؛ بنابراین، اندازهٔ کوانتوم یکی از پارامترهای مهم در عملکرد زمان‌بندی نوبت گردشی است.
مثال
[ویرایش | اشتراک‌گذاری]فرض کنید اندازهٔ کوانتوم ۱۰۰ میلی‌ثانیه باشد و اجرای کار شمارهٔ ۱ در مجموع به ۲۵۰ میلی‌ثانیه زمان پردازنده نیاز داشته باشد. زمان‌بند نوبت گردشی این کار را حداکثر برای ۱۰۰ میلی‌ثانیه اجرا می‌کند و سپس، در صورت باقی‌ماندن کار، نوبت را به فرایندهای دیگر می‌دهد. هنگامی که دوباره نوبت کار شمارهٔ ۱ برسد، اجرای آن ادامه پیدا می‌کند.
برای کار شمارهٔ ۱:
تخصیص نخست: ۱۰۰ میلی‌ثانیه تخصیص دوم: ۱۰۰ میلی‌ثانیه تخصیص سوم: حداکثر ۱۰۰ میلی‌ثانیه؛ اما کار پس از ۵۰ میلی‌ثانیه به پایان می‌رسد. مجموع زمان استفادهٔ کار از CPU: ۲۵۰ میلی‌ثانیه
در نتیجه، آخرین کوانتوم این فرایند به اندازهٔ کامل مصرف نمی‌شود و فرایند پس از پایان کار از صف آماده خارج می‌شود.
در یک روش دیگر، می‌توان تعداد کوانتوم‌های اختصاص‌یافته به فرایندها را با توجه به اندازهٔ آن‌ها تعیین کرد، به گونه‌ای که کوانتوم‌ها متناسب با اندازهٔ فرایندها باشند. با این حال، چنین روشی دیگر بیانگر شکل استاندارد زمان‌بندی نوبت گردشی با کوانتوم ثابت نیست و ممکن است ویژگی‌های عدالت و زمان پاسخ آن با روش معمول تفاوت داشته باشد.
زمان‌بندی بسته‌های داده در شبکه
[ویرایش | اشتراک‌گذاری]زمان‌بندی نوبت گردشی تنها به زمان‌بندی فرایندهای سیستم‌عامل محدود نمی‌شود و می‌تواند در شبکه‌های رایانه‌ای نیز برای زمان‌بندی انتقال بسته‌های داده مورد استفاده قرار گیرد. برای نمونه، در تسهیم آماری و سامانه‌هایی که چند جریان داده از یک کانال مشترک استفاده می‌کنند، می‌توان برای هر جریان یک صف جداگانه در نظر گرفت و با استفاده از نوبت گردشی، به جریان‌های فعال فرصت انتقال داد.
در یک مسیریاب، سوئیچ یا تسهیم‌کننده‌ای که از این روش استفاده می‌کند، هر جریان داده می‌تواند با استفاده از اطلاعاتی مانند نشانی مبدأ و مقصد از سایر جریان‌ها متمایز شود. زمان‌بند، صف‌های دارای بسته را به صورت چرخشی بررسی می‌کند و به هر جریان فعال اجازه می‌دهد بستهٔ خود را از کانال مشترک عبور دهد.
زمان‌بندی نوبت گردشی در این حالت معمولاً «کار-حفظ» (work-conserving) است؛ به این معنا که اگر یک جریان داده در نوبت خود بسته‌ای برای ارسال نداشته باشد، زمان یا فرصت انتقال آن به جریان بعدی داده می‌شود. در نتیجه، الگوریتم تلاش می‌کند ظرفیت لینک تا حد امکان بدون استفاده باقی نماند.
اگر اندازهٔ بسته‌های داده یکسان باشد، زمان‌بندی نوبت گردشی می‌تواند ویژگی عدالت بیشینه-کمینه (max-min fairness) را ایجاد کند؛ به این معنا که جریان‌هایی که مدت بیشتری منتظر مانده‌اند، به نوبت فرصت دریافت می‌کنند. با این حال، اگر اندازهٔ بسته‌ها میان جریان‌های مختلف تفاوت زیادی داشته باشد، جریان‌هایی که بسته‌های بزرگ‌تری دارند ممکن است نسبت به جریان‌هایی که بسته‌های کوچک‌تری دارند، زمان بیشتری از کانال را مصرف کنند. در چنین شرایطی، روش‌هایی مانند صف‌بندی منصفانه می‌توانند مناسب‌تر باشند.
در شبکه‌هایی که علاوه بر اشتراک منصفانه، نیاز به کیفیت خدمات (QoS) یا تضمین‌های متفاوت برای جریان‌های مختلف وجود دارد، می‌توان از گونه‌های دیگری از این الگوریتم استفاده کرد؛ از جمله:
زمان‌بندی نوبت گردشی وزنی (Weighted Round Robin یا WRR)
زمان‌بندی نوبت گردشی کسری (Deficit Round Robin یا DRR)
صف‌بندی منصفانهٔ وزنی (Weighted Fair Queuing یا WFQ)
این روش‌ها با درنظرگرفتن وزن، اندازهٔ بسته یا سهم اختصاص‌یافته به هر جریان، امکان ایجاد تفاوت در میزان دسترسی جریان‌ها به منابع شبکه را فراهم می‌کنند.
کاربرد در شبکه‌های دسترسی چندگانه
[ویرایش | اشتراک‌گذاری]در شبکه‌های دسترسی چندگانه، که چندین پایانه یا دستگاه از یک محیط فیزیکی مشترک استفاده می‌کنند، می‌توان زمان‌بندی نوبت گردشی را با سازوکارهای مختلف دسترسی به کانال ترکیب کرد. از جملهٔ این سازوکارها می‌توان به توکن رینگ، سرکشی (polling) و تخصیص منابع توسط یک ایستگاه کنترل مرکزی اشاره کرد.
در این ساختارها، نوبت میان پایانه‌ها یا جریان‌های داده توزیع می‌شود و هر پایانه در نوبت خود فرصت استفاده از محیط مشترک را به دست می‌آورد. در صورت نبود داده برای ارسال، نوبت می‌تواند به پایانهٔ بعدی منتقل شود.
کاربرد در شبکه‌های بی‌سیم
[ویرایش | اشتراک‌گذاری]در یک شبکهٔ رادیویی بستهٔ بی‌سیم متمرکز، که چندین ایستگاه از یک کانال فرکانسی مشترک استفاده می‌کنند، یک زمان‌بند در ایستگاه پایهٔ مرکزی می‌تواند قطعه‌های زمانی را به ایستگاه‌های سیار به صورت نوبت گردشی اختصاص دهد. این روش باعث می‌شود هر ایستگاه در طول چرخه، فرصت مشخصی برای انتقال داده داشته باشد و دسترسی به کانال به صورت نسبتاً منظم میان کاربران توزیع شود.
با این حال، در شبکه‌های بی‌سیم شرایط کانال برای کاربران مختلف یکسان نیست و می‌تواند در طول زمان تغییر کند. اگر از سازگاری لینک یا روش‌های تطبیق انتقال با شرایط کانال استفاده شود، انتقال مقدار مشخصی از داده برای کاربری که در شرایط نامناسب کانال قرار دارد ممکن است زمان بیشتری نسبت به کاربری با شرایط مناسب نیاز داشته باشد. زمان‌بندی نوبت گردشی این تفاوت در شرایط کانال را مستقیماً در تصمیم‌گیری خود لحاظ نمی‌کند و همچنان تلاش می‌کند فرصت‌ها را به صورت چرخشی توزیع کند.
در برخی سامانه‌های بی‌سیم، می‌توان با استفاده از زمان‌بندی وابسته به شرایط کانال، توان عملیاتی یا بهره‌وری طیفی را افزایش داد. نمونه‌هایی از این رویکردها شامل زمان‌بندی تناسبی منصفانه (Proportional Fair Scheduling) و روش‌های بیشینه‌سازی توان عملیاتی هستند. در مقابل، برخی روش‌های بیشینه‌سازی توان عملیاتی ممکن است به قیمت کاهش فرصت دسترسی برخی کاربران تمام شوند و در شرایط خاص، مسئلهٔ قحطی را ایجاد کنند.
مزایا و محدودیت‌ها
[ویرایش | اشتراک‌گذاری]از مهم‌ترین ویژگی‌های زمان‌بندی نوبت گردشی می‌توان به سادگی، سهولت پیاده‌سازی و جلوگیری از قحطی در شکل استاندارد آن اشاره کرد. همچنین، اختصاص زمان به صورت چرخشی باعث می‌شود فرایندهای مختلف فرصت استفاده از CPU یا یک منبع مشترک را به دست آورند.
با این حال، عملکرد الگوریتم به انتخاب اندازهٔ کوانتوم وابسته است. کوانتوم بسیار بزرگ می‌تواند زمان پاسخ فرایندهای کوتاه را افزایش دهد و رفتار الگوریتم را به FCFS نزدیک کند؛ در حالی که کوانتوم بسیار کوچک می‌تواند تعداد تعویض‌های زمینه و در نتیجه سربار سیستم را افزایش دهد.
در کاربردهای شبکه‌ای نیز، نوبت گردشی در صورتی که بسته‌ها اندازه‌های متفاوتی داشته باشند الزاماً عدالت یکسانی را از نظر مقدار دادهٔ منتقل‌شده ایجاد نمی‌کند. به همین دلیل، در شبکه‌هایی با نیازهای پیچیده‌تر ممکن است از الگوریتم‌های وزنی یا الگوریتم‌هایی استفاده شود که اندازهٔ بسته و شرایط کانال را نیز در نظر می‌گیرند.
جستارهای وابسته
[ویرایش | اشتراک‌گذاری]منابع
[ویرایش | اشتراک‌گذاری]Silberschatz, Abraham; Galvin, Peter B. ; Gagne, Greg (2010). Operating System Concepts (8th ed.). John Wiley & Sons (Asia). p. 194. شابک ۹۷۸−۰−۴۷۰−۲۳۳۹۹−۳. "5.3.4 Round Robin Scheduling"