بخشی از مقاله
چکیده
هدف از زمانبندی وظایف لحظهای در سیستمهای چندپردازندهای بهینهسازی ترتیب اجرای وظایف و تعیین یک پردازنده برای اجرای هر وظیفه است. متاسفانه، زمانبندی وظایف لحظهای در سیستمهای چندپردازندهای یک مسئله پیچیده غیر چندجملهای است. بنابراین، الگوریتمهای بهینهسازی تکاملی بهطور موثری میتوانند برای حل این مسئله مورد استفاده قرار گیرند. در این مقاله، روشهای کلاسیک و تکاملی موجود برای زمانبندی وظایف لحظهای در سیستمهای چندپردازندهای بررسی میشوند. نتایج ارائهشده در نشریات اثبات میکند که روشهای مبتنی بر الگوریتمهای تکاملی کارایی بهتری نسبت به روشهای کلاسیک از نظر دقت و زمان اجرا دارند.
کلمات کلیدی: سیستمهای چندپردازندهای، وظایف لحظهای، زمانبندی، الگوریتمهای تکاملی.
مقدمه
زمانبندی لحظهای وظایف در سیستمهای چندپردازندهای به منظور تخصیص وظایف به پردازندهها و تعیین ترتیب اجرای آنها است . وظایف لحظهای به دو دسته سخت و نرم تقسیم میشوند. عدم رعایت قیدهای زمانی در اجرای یک وظیفه سخت غیر قابل قبول است. به بیان دیگر، تاخیر در اجرای این وظایف ممکن است فاجعه به بار آورد - مانند سیستمهای مانیتورینگ بیماران یا کنترل فرآیندهای هستهای - . با این وجود، اندکی تاخیر در اجرای وظایف نرم مشکلات جدی به دنبال ندارد.
به عبارت دیگر، تجاوز از زمان سررسید وظایف خطری برای محیط تحت کنترل ندارد - مانند سیستمهای صوتی و تصویری - . تمرکز اصلی در این مقاله بر روی زمانبندی وظایف لحظهای نرم میباشد. الگوریتمهای زمانبندی به دو دسته کلی تقسیم میشوند: زمانبندی استاتیک و زمانبندی دینامیک در زمانبندی استاتیک، شرایط سیستم شامل تعداد وظایف، قیدهای زمانی و ... مشخص است. در این حالت، زمانبندی به صورت آفلاین صورت میگیرد. درصورتیکه در زمانبندی دینامیک، الگوی رفتاری وظایف بهطور دقیق مشخص نیست، و ممکن است یک وظیفه بهصورت آنلاین به سیستم اضافه شود.
در مرجع اثبات شده است که زمانبندی در سیستمهای چند پردازندهای یک مسئله پیچیده غیر چندجمله ای است. بنابراین، دستیابی به جواب قطعی - بهینه سراسری - با استفاده از روشهای قطعی امکانپذیر نمیباشد. استفاده از الگوریتمهای بهینهسازی تکاملی در چنین شرایطی بسیار مناسب به نظر میرسد. این الگوریتمها برای زمانبندی استاتیک قادر هستند در زمانی مناسب مجموعهای از جوابهای نزدیک به بهینه حاصل کنند.در ادامه این مقاله، فرمولبندی مسئله زمانبندی وظایف لحظهای نرم استاتیک در سیستمهای چندپردازندهای در بخش دوم بیان میشود.
در بخش سوم به بررسی روشهای کلاسیک موجود برای زمانبندی پرداخته میشود. همچنین، روشهای زمانبندی موجود مبتنی بر الگوریتمهای تکاملی در بخش چهارم بحث میشوند. در نهایت، نتیجهگیری مقاله در بخش پنجم بیان میشود.
بیان مسئله زمانبندی
فرضیات مسئله زمانبندی وظایف لحظهای نرم در سیستمهای چندپردازندهای بهصورت ذیل است :پردازندههای مختلف ممکن است توان پردازش ثابت - سیستم همگن - یا مختلف - سیستم ناهمگن - داشته باشند.وظایف غیر قابل بازپسگیری هستند - هر وظیفه پس از تخصیص به یک پردازنده امکان جابجایی ندارد - .ترتیب - وابستگی - اجرایی بین وظایف وجود دارد که در قالب یک گراف بیان میشود.هر پردازنده در هر لحظه فقط میتواند یک وظیفه را اجرا کند.هر وظیفه در هر لحظه فقط بر روی یک پردازنده قابل اجرا است - امکان جابجایی وظایف در حین اجرا وجود ندارد - .زمان اجرای هر وظیفه بر روی هر پردازنده مشخص است.حداکثر زمان سررسید هر وظیفه مشخص است.
سه معیار ارزیابی مهم که بهطور وسیعی در مراجع مختلف مورد استفاده قرار گرفتهاند. هدف از یک الگوریتم زمانبندی بهینه، حداقل کردن یک، دو یا هر سه معیار مذکور است. معیار اول مجموع تاخیر ایجاد شده در اجرای تمام وظایف است . اگر زمان شروع اجرای وظیفه با ، مدت زمان اجرای آن با و زمان سررسید آن با نشان داده شود، حالت اجرای عادی - بدون تاخیر - و با تاخیر وظیفه مطابق است . معیار دوم تعداد پردازندههای فعال که برای اجرای وظایف مورد استفاده قرار گرفتهاند، است. معیار سوم حداکثر زمان اجرای آخرین وظیفه - مجموع زمان اجرای کلی سیستم - میباشد.
یک متغیر باینری است که مشخص میکند وظیفه i به پردازنده m اختصاص یافته است یا نه. هر وظیفه در هر لحظه فقط بر روی یک پردازنده اجرا میشود. مشخص میکند که زمان واقعی شروع هر وظیفه نمیتواند زودتر از حداقل زمان شروع آن وظیفه باشد. زمان خاتمه هر وظیفه مطابق از حاصل جمع زمان واقعی شروع وظیفه و زمان اجرای وظیفه محاسبه میشود. حداقل زمان شروع یک وظیفه باید بزرگتر یا مساوی زمان خاتمه تمام وظایف پیشنیاز آن وظیفه باشد. حداقل زمان شروع هر وظیفه برابر است با حداکثر زمان خاتمه تمام وظایف پیشنیاز آن وظیفه.
