ارائه يك الگوريتم زمان‌بندي بهينه با كارايي بالا به‌منظور كاهش توقف و مهاجرت وظايف ميان پردازنده‌ها در سامانه‌هاي بي‌درنگ چند پردازنده‌اي

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

191830

دانشگاه علم و صنعت ايران

دكتر حاكم بيت اللهي

معماري سيستم هاي كامپيوتري

دكتر محسن سرياني