۱۷۸۱۳پ
per
یک الگوریتم ترکیبی بین ACO و EDF برای زمانبندی در سیستم‌های بلادرنگ
/شهرزادطریقی
: پردیس دانشگاه تبریز
، ۱۳۹۵
، راشدی
چاپی
کارشناسی ارشد
مهندسی کامپیوتر گرایش نرم افزار
۱۳۹۵/۱۱/۲۵
تبریز
سیستم‌های بلادرنگ، سیستم‌هایی هستند که علاوه بر تولید نتیجه‌ی منطقی صحیح، ضرب اجل زمانی دارند و در زمان مشخصی باید نتیجه را تحویل دهند .مهمترین محدودیت سیستم‌های بلادرنگ این است که صحت این سیستم‌ها تنها به نتایج محاسبه شده وابسته نیست، بلکه زمانی که نتایج فراهم می‌شوند هم اهمیت دارد .به عبارت دیگر این سیستم‌ها محدودیت‌های زمانی دارند که باید تضمین شود .بدین وسیله بحث ضرب اجل به میان می‌آید که خصیصه‌ی مشترک تمام سیستم‌های بلادرنگ است و این سیستم‌ها را از سیستم‌های اشتراک زمانی متمایز می‌کند .بحث زمانبندی در این سیستم‌ها موضوعی چالش برانگیز است چون علاوه بر شرایط زمانبندی معمول، در این سیستم‌ها وظایف ضرب اجل‌هایی هم دارند که باید محقق شوند .یکی از نیازهای ضروری هر سیستم یک مکانیسم زمانبندی است که در واقع بر مبنای آن سیستم تصمیم می‌گیرد کدام وظیفه در چه زمانی باید اجرا شود .مشکل زمانبندی سیستم‌های بلادرنگ متفاوت از مشکل زمانبندی در سیستم‌های اشتراک زمانی است، چون در سیستم‌های بلادرنگ محدودیت‌های زمانی نقش اساسی در ارزیابی کارآیی سیستم دارد .یکی از پراستفاده‌ترین الگوریتم‌های ارائه شده در این زمینه Earliest Deadline First(EDF)است که الگوریتمی با تخصیص اولویت پویاست .بر اساس این الگوریتم، وظیفه‌ی آماده‌ی اجرا با نزدیکترین ضرب اجل زمانی، بالاترین اولویت را دارد و اول اجرا می‌شود .بهینه بودن این الگوریتم در شرایط مقدار بار کم پردازنده از بین تمام الگوریتم‌های زمانبندی تک پردازنده اثبات شده است .الگوریتم ACO علی رغم نیاز به زمان اجرای بسیار بیشتر نسبت بهEDF ، در شرایط مقدار بار اضافه‌ی پردازنده که الگوریتم EDF موجب از دست رفتن ضرب اجل‌های زمانی می‌شود، می‌تواند کارآیی بهتری داشته باشد و حد اکثر ضرب اجل زمانی ممکن را حفظ و محقق می‌کند .در این پایان نامه با در نظر گرفتن وظایف از نوع منظم که بر اساس مقدار دوره‌شان در هر دوره یکبار درخواست پردازش دارند و اجرای راهکارهای پیشنهادیمان بر اساس عملکرد الگوریتم ACO در قالب دو الگوریتم Proposed و Layered توانسته ایم متوسط نرخ موفقیت در اجرای وظایف تا ضرب اجلشان را در شرایط مقدار بار اضافه‌ی پردازنده، به ترتیب ۰۲۸۱/۸ و ۰۰۹۰/۱۸ نسبت به الگوریتم EDF بهبود بخشیم و در انتها با ترکیب الگوریتم ارائه شده‌ی Layered با الگوریتم EDF در قالب الگوریتمEDF- Layered، متوسط زمان اجرای الگوریتم Layered را که به علت اعمال متدهای ACO بالا رفته است، در ازای افت ناچیز نرخ موفقیت به مقدار۶۵۸۹/۰ ، با نسبت ۰۲۹۹/۲۴ بهبود بخشیده و کمتر کنیم
Real-time systems are defined as those systems in which the correctness of the system depends not only on the logical result of computation, but also on the task deadlines and the time at which the results are produced. In other words, real-time systems have timing requirements that must be guaranteed. This leads to the notion of deadline which is a common thread among all Real-time system models and the core of the difference between real-time systems and time-sharing systems. An essential component of a computer system is the scheduling mechanism that is the strategy by which the system decides which task should be executed at any given time. The problem of Real-time scheduling is different from that of multiprogramming time-sharing scheduling because of the role of timing constraints in the evaluation of the system performance. One of the most used algorithms in this field is The Earliest Deadline First (EDF), which is a dynamic priority based algorithm. Based on this algorithm, The priority of each task is decided related to the value of its deadline. The task with nearest deadline is given highest priority and it is selected for execution. This algorithm is simple and proved to be optimal when the system is underloaded, among all uniprocessor algorithms. The Ant Colony Optimization (ACO), in spite of requiring more execution time compared to EDF algorithm, can perform better than EDF algorithm and improve the number of tasks met their deadlines in overloaded conditions in which, EDF algorithm causes tasks to miss their deadlines. In this Thesis, considering Periodic tasks which need service once in their period and simulating our proposed methods as Proposed and Layered algorithms, we succeeded in improving the average success ratio of tasks with 8.0281 and 18.0090 in overloaded conditions compared to EDF algorithm and in the end, we succeeded in improving the average execution time of the Layered algorithm with 24.0299 for 0.6958 decreasing in average success ratio, by mixing the Layered and EDF algorithm presented as the Layered-EDF algorithm
طریقی، شهرزاد
زلفی لیقوان، مینا، استاد راهنما
درخشان، فرناز، استاد مشاور
سیاه و سفید
نمایه‌سازی قبلی
