امروزه با فراگير شدن كاربردهاي سامانه‌هاي بي‌درنگ، مسئله زمان‌بندي وظايف در اين سامانه‌ها حائز اهميت فراواني است. با توجه به ضرورت استفاده از اين سامانه‌ها براي كاربردهاي گوناگون و سنگين شدن پردازش‌ها، پژوهشگران به‌منظور بهره‌وري بيشتر در سامانه‌هاي بي‌درنگ، ناگزير به استفاده از چند پردازنده به‌صورت هم‌زمان هستند. علي‎رغم كارايي بيشتر سامانه‌هاي چندپردازنده‌اي به نسبت سامانه‌هاي تك‌پردازنده‌اي، اين سامانه‌ها متحمل سربار بيشتري نيز براي زمان‌بندي وظايف هستند. دليل اصلي اين سربارها، جابجايي وظايف ميان پردازنده‌هاي مختلف و توقف وظايف در حال اجرا بر روي يك پردازنده توسط ساير وظايف است. از مهم‌ترين چالش‌هايي كه براي زمان‌بندي وظايف در سامانه‌هاي چندپردازنده‌اي بي‌درنگ وجود دارد، مي‌توان به دو سربار قبضه‌كردن و مهاجرت اشاره كرد. با توجه به اين‌كه كاهش اين دو سربار منجر به افزايش قابل توجه كارايي سامانه‌هاي بي‌درنگ خواهد شد، لذا در اين پژوهش انگيزه بالايي براي رسيدن به اين هدف وجود دارد. لازم به ذكر است با توجه به ماهيت سامانه‌هاي بي‌درنگ كه زمان پاسخ‌گويي وظايف در آن‌ها بسيار مهم است، بهينگي الگوريتم مورد نظر اصلي‌ترين هدف پژوهش بوده است. در اولويت بعد افزايش كارايي الگوريتم به‌وسيله كاهش اين دو سربار حائز اهميت است. در اين پژوهش يك الگوريتم بهينه جديد به‌نام RUMP براي زمان‌بندي وظايف در سامانه‌هاي چندپردازنده‌اي ارائه شده‌است. الگوريتم RUMP از نوع الگوريتم‌هاي پويا است كه از مزاياي الگوريتم‌هاي بخش‌بندي و الگوريتم‌هاي سراسري به‌صورت هم‌زمان استفاده مي‌كند. مبناي اصلي زمان‌بندي در الگوريتم RUMP دسته‌بندي وظايف براساس بهره‌وري سامانه و سپس تخصيص مجموعه وظايف دسته‌بندي شده به تعداد مشخصي از پردازنده‌هاست. در اين الگوريتم، تلاش شده است به‌گونه‌اي وظايف دسته‌بندي شوند كه تعداد بيشتري از مجموعه وظايف با استفاده از حداقل تعداد پردازنده زمان‌بندي شوند. اين تفكيك وظايف و زمان‌بندي آگاهانه، باعث كاهش چشمگير سربارهاي قبضه‌كردن و مهاجرت در سامانه‌هاي چندپردازنده‌اي با حفظ بهينگي الگوريتم شده است. در اين پژوهش الگوريتم RUMP در مقايسه با برترين الگوريتم‌هاي زمان‌بندي چندپردازنده‌اي همچون الگوريتم RUN و الگوريتم U-EDF در شبيه‌ساز SimSo، از نظر تعداد سربارهاي قبضه‌كردن و مهاجرت، در برخي از مجموعه وظايف تا 50% و در برخي ديگر از مجموعه وظايف تا 60% كاهش داشته است كه اين ميزان كاملاً قابل توجه است. واژه‌هاي كليدي: الگوريتم زمان‌بندي، سامانه‌هاي بي‌درنگ، سامانه‌هاي چندپردازنده‌اي، قبضه‌كردن و مهاجرت، تخصيص وظايف

1397/07/08

An Optimal High Performance Scheduling Algorithm to Reduce Preemptions and Migrations of Tasks in Multiprocessor Real-Time Systems.

9/29/2018 12:00:00 AM

Real-time embedded systems are playing important role in the industry within many commercial applications which necessitates innovative hardware design and scheduling. Embedded applications are getting more complex and raise the necessity for more computation power. As the Moore’s law is not keeping up with single processor architecture, multiprocessing is now a solution to this problem and researchers are urged to use multiple processors to gain performance in real-time systems. Task scheduling on multiprocessor systems imposes overhead due to its intrinsic computational complexity. The main reason for the overhead is the task migration between processors and preemption of running tasks while others arrive. Migration and preemption problems are two of the most important challenges in multiprocessor real-time systems. Mitigation of the aforementioned overheads results in a significant gain in the performance of real-time systems. Thus, in this research, we aim to mitigate preemption and migration by introducing a novel algorithm that minimizes the response times of the real-time tasks. We propose a new optimal task scheduling algorithm “Reconciling Uni and Multi-Processor scheduling via task utilization” (RUMP) in this dissertation. RUMP is a dynamic algorithm which is basically inspired by both partitioned and global algorithms presented in related works. Utilization-based partitioning of the incoming tasks and task-set assignment to individual processors are the most fundamental building blocks of our solution. Our design goal is to schedule the task-sets with the minimum number of processors at runtime while reducing the preemption and migration overhead in the multiprocessor system accordingly. Experiments show that RUMP improves the performance (both preemption and migration) up to 50%, compared with the available multi-processor algorithms such as RUN and U-EDF, which is a remarkable improvement. Keywords: Task Scheduling Algorithm, Real-Time Systems, Multiprocessor System, Preemption, Migration.