نام فایل : روشی جدید برای الگوریتم زمانبندی CPU

فرمت : .pptx

تعداد صفحه/اسلاید : 54

حجم : 726 کیلوبایت

1
روشی جدید برای الگوریتم زمانبندی CPU با گردش به نوبت ژنتیکی
2
چکیده
زمانبندی CPU باید بیطرف حفظ شود و از فرایند هایی که هرگز CPU حاصل نمیشود جلوگیری شود. سیستم عاملهای جدید دوره با عملکرد چند وظیفه ای در محیط عملیاتی کامپیوتر روبرو میشود. اگر زمانبندی CPU کارامد باشد, محاسبات زیادی میتوانست بدرستی انجام شود و سیستم میتواند پایداری را حفظ کند. یک معیار که باید بوسیله ی الگوریتم زمانبندی بدست آورده شود، بحداقل رساندن میانگین زمان انتظار برای مجموعه ای از فرایندها در بدست آوردن تخصیص CPU ست.
3
روشهای مختلفی برای زمانبندی CPU وجود دارد؛ یکی از آنها گردش بنوبت است. گردش بنوبت، کوانتوم را فراهم میکند که برای هر یک از فرایندها مشابه است. با این حال هیچ استاندارد مشخصی برای کوانتوم وجود ندارد. ناچارا اگر کوانتومی بسیار زیاد باشد، پاسخ / زمان انتظاربرای هر فرایند میتواند زیاد باشد و در غیر اینصورت افزایش رو به به بالا CPU برای تعویض بستر وجود دارد.

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

5
اصطلاحات کلی
زمانبندی CPU,الگوریتم گردش بنوبت,الگوریتم ژنتیک.
کلمات کلیدی
گردش بنوبت ژنتیک

6
Round-robin تعریف الگوریتم
7
زمان‌بندی نوبت چرخشی (Round-robin Scheduling) یا (RR) یکی از الگوریتم‌هایی است که با فرایندها و زمان بندی شبکه کار می‌کند. پارامترهایی که عموماً استفاده می‌شوند، قطعات زمانی هستند که به هر فرایند بخش یکسان و به صورت ترتیب چرخشی انتساب داده می‌شود، تمام فرایندها بدون اولویت در نظر گرفته می‌شوند.(که به اجرای چرخشی معروف است) زمان بندی RR ساده، پیاده سازی آسان و بدون قحطی است. این زمان بندی هم چنین می‌تواند برای مسائل زمان بندی دیگر مثل زمان بندی بسته داده در شبکه‌های کامپیوتری بکار برده شود. این خط مشی سیستم عامل است.
نام الگوریتم از اصل نوبت چرخشی که در دیگر زمینه‌ها معروف است می‌آید، که هر فردی یک سهم یکسان از چیزی را در نوبت می‌گیرد.

زمان بندی فرایندها در RR
8
زمان بندی فرایندها به صورت منصفانه‌است، یک زمان بند RR عموماً اشتراک زمانی را در نظر می‌گیرد. به هر کار یک قطعه زمانی یا کوانتوم (توسط cpu اجازه داده می‌شود) داده می‌شود، اگر یک کار تمام نشده باشد به وسیله آن وقفه داده می‌شود و آن کار دوباره در زمان بعدی¬ یک قطعه زمانی به فرایند اختصاص می‌دهد. اگر اشتراک زمانی نباشد یا کوانتوم‌ها بزرگتر از سایز کارها باشند، یک فرایندی که کارهای بزرگ را تولید کرده‌است نسبت به فرایندهای دیگر مورد توجه قرار خواهد گرفت.
مثلاً اگر قطعه زمانی ۱۰۰ میلی ثانیه باشد و کارشماره یک، مجموعاً ۲۵۰ میلی ثانیه طول کشد تا کامل شود، زمان بند RR، کار را ۱۰۰ میلی ثانیه به تعویق می‌اندازد و به دیگر فرایندها زمانشان را روی cpu می‌دهد. اولین بار کارهای دیگر سهم یکسانشان را دارند؛ (۱۰۰ میلی ثانیه) کار شماره یک تخصیص دیگری از زمان cpu را خواهد گرفت و چرخه ادامه پیدا خواهد کرد. این فرایندها ادامه پیدا خواهند کرد تا زمانیکه کار تمام شود و احتیاجی به زمان بیشتری روی cpu نباشد.


9
کار۱: مجموعاً ۲۵۰ میلی ثانیه طول می‌کشد (کوانتوم ۱۰۰ میلی ثانیه)
تخصیص اول: ۱۰۰ میلی ثانیه
تخصیص دوم: ۱۰۰ میلی ثانیه
تخصیص سوم: ۱۰۰ میلی ثانیه، اما کار۱ بعد از ۵۰ میلی ثانیه خاتمه می‌یابد.
زمان کل cpu کار۱: ۲۵۰ میلی ثانیه
....