عنوان

یک الگوریتم ترکیبی بین ‮‭ACO‬ و ‮‭EDF‬ برای زمانبندی در سیستم‌های بلادرنگ

Number

‭۱۷۸۱۳پ‬

.Language of Text, Soundtrack etc

per

Title Proper

یک الگوریتم ترکیبی بین ‮‭ACO‬ و ‮‭EDF‬ برای زمانبندی در سیستم‌های بلادرنگ

First Statement of Responsibility

/شهرزادطریقی

Name of Publisher, Distributor, etc.

: پردیس دانشگاه تبریز

Date of Publication, Distribution, etc.

، ‮‭۱۳۹۵‬

Name of Manufacturer

، راشدی

Text of Note

چاپی

Dissertation or thesis details and type of degree

کارشناسی ارشد

Discipline of degree

مهندسی کامپیوتر گرایش نرم افزار

Date of degree

‮‭۱۳۹۵/۱۱/۲۵‬

Body granting the degree

تبریز

Text of Note

سیستم‌های بلادرنگ، سیستم‌هایی هستند که علاوه بر تولید نتیجه‌ی منطقی صحیح، ضرب اجل زمانی دارند و در زمان مشخصی باید نتیجه را تحویل دهند .مهمترین محدودیت سیستم‌های بلادرنگ این است که صحت این سیستم‌ها تنها به نتایج محاسبه شده وابسته نیست، بلکه زمانی که نتایج فراهم می‌شوند هم اهمیت دارد .به عبارت دیگر این سیستم‌ها محدودیت‌های زمانی دارند که باید تضمین شود .بدین وسیله بحث ضرب اجل به میان می‌آید که خصیصه‌ی مشترک تمام سیستم‌های بلادرنگ است و این سیستم‌ها را از سیستم‌های اشتراک زمانی متمایز می‌کند .بحث زمان‌بندی در این سیستم‌ها موضوعی چالش برانگیز است چون علاوه بر شرایط زمان‌بندی معمول، در این سیستم‌ها وظایف ضرب اجل‌هایی هم دارند که باید محقق شوند .یکی از نیازهای ضروری هر سیستم یک مکانیسم زمان‌بندی است که در واقع بر مبنای آن سیستم تصمیم می‌گیرد کدام وظیفه در چه زمانی باید اجرا شود .مشکل زمان‌بندی سیستم‌های بلادرنگ متفاوت از مشکل زمان‌بندی در سیستم‌های اشتراک زمانی است، چون در سیستم‌های بلادرنگ محدودیت‌های زمانی نقش اساسی در ارزیابی کارآیی سیستم دارد .یکی از پراستفاده‌ترین الگوریتم‌های ارائه شده در این زمینه ‮‭Earliest Deadline First(EDF)‬است که الگوریتمی با تخصیص اولویت پویاست .بر اساس این الگوریتم، وظیفه‌ی آماده‌ی اجرا با نزدیکترین ضرب اجل زمانی، بالاترین اولویت را دارد و اول اجرا می‌شود .بهینه بودن این الگوریتم در شرایط مقدار بار کم پردازنده از بین تمام الگوریتم‌های زمان‌بندی تک پردازنده اثبات شده است .الگوریتم ‮‭ACO‬ علی رغم نیاز به زمان اجرای بسیار بیشتر نسبت به‮‭EDF‬ ، در شرایط مقدار بار اضافه‌ی پردازنده که الگوریتم ‮‭EDF‬ موجب از دست رفتن ضرب اجل‌های زمانی می‌شود، می‌تواند کارآیی بهتری داشته باشد و حد اکثر ضرب اجل زمانی ممکن را حفظ و محقق می‌کند .در این پایان نامه با در نظر گرفتن وظایف از نوع منظم که بر اساس مقدار دوره‌شان در هر دوره یکبار درخواست پردازش دارند و اجرای راهکارهای پیشنهادیمان بر اساس عملکرد الگوریتم ‮‭ACO‬ در قالب دو الگوریتم ‮‭Proposed‬ و ‮‭Layered‬ توانسته ایم متوسط نرخ موفقیت در اجرای وظایف تا ضرب اجلشان را در شرایط مقدار بار اضافه‌ی پردازنده، به ترتیب ‮‭۰۲۸۱/۸‬ و ‮‭۰۰۹۰/۱۸‬ نسبت به الگوریتم ‮‭EDF‬ بهبود بخشیم و در انتها با ترکیب الگوریتم ارائه شده‌ی ‮‭Layered‬ با الگوریتم ‮‭EDF‬ در قالب الگوریتم‮‭EDF- Layered‬، متوسط زمان اجرای الگوریتم ‮‭Layered‬ را که به علت اعمال متدهای ‮‭ACO‬ بالا رفته است، در ازای افت ناچیز نرخ موفقیت به مقدار‮‭۶۵۸۹/۰‬ ، با نسبت ‮‭۰۲۹۹/۲۴‬ بهبود بخشیده و کمتر کنیم

Text of Note

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

طریقی، شهرزاد

زلفی لیقوان، مینا، استاد راهنما

درخشان، فرناز، استاد مشاور

Public note

سیاه و سفید

نمایه‌سازی قبلی