دانلود ترجمه مقاله بررسی تکنیک های تحلیل زمان بندی برای وظایف وابسته به سرعت (ساینس دایرکت – الزویر 2018)

بررسی تکنیک های تحلیل زمان بندی برای وظایف وابسته به سرعت

A survey of schedulability analysis techniques for rate-dependent tasks

چکیده
1. مقدمه
2. مدل های وظیفه قبلی و اصطلاحات فنی
3. مدل‌هایی برای وظایف وابسته به سرعت
4. زمان‌بندی انحصاری اولویت ثابت
5. زمان‌بندی نخست اولین ضرب‌الاجل
6. چشم‌انداز و کار‌های آتی
منابع

چکیده
در سیستم‌های بلادرنگ تعبیه شده خودرویی، مانند واحد کنترل موتور، وظایفی وجود دارند که برای مثال هر بار زمانی فعال می‌شوند که میل لنگ به یک موقعیت زاویه‌ای خاص برسد. در نتیجه شاهد افزایش تکرار تغییرات فعال‌سازی با سرعت زاویه‌ای میل لنگ هستیم (یعنی RPM موتور). علاوه بر این، زمان اجرا و ضرب‌الاجل‌ها نیز ممکن است به سرعت و موقعیت زاویه‌ای بستگی داشته باشند. در این مقاله مطالعه اجمالی در مورد تکنیک‌های تحلیلی قابلیت زمان‌بندی برای وظایفی با این رفتار وابسته به سرعت ارائه شده است که روش‌های تجزیه و تحلیل و مدل‌های وظایف مختلفی برای هر دوی زمان‌بندی‌هایی با اولویت ثابت و نخست زودترین ضرب‌الاجل پوشش داده شده است. یک رده‌بندی‌شناسی از روش‌های تجزیه و تحلیل مختلف و طبقه‌بندی آنها با توجه به فرضیه‌های ساخته شده و دقت تجزیه و تحلیل آنها در پایان مقاله ارائه شده است.

2 . مدل های وظیفه قبلی و اصطلاحات فنی
تجزیه و تحلیل قابلیت زمان‌بندی برای انواع مختلف مدل‌های کاری توسعه یافته است. نخستین مدل وظیفه دوره‌ای توسط لیو و لیلند [22] معرفی شده بود. در این مدل، فعال‌سازی وظایف به طور مرتب دوره‌ای بوده است. هر وظیفه ti دارای دوره‌ای به شکل Ti بوده است که بدترین زمان اجرای آن به شکل Ci بوده است و دارای ضرب‌الاجل Di بوده است که ضمنی است (برای مثال برابر با دوره خود بوده است). این مدل متعاقبا گسترش یافته است تا اجازه ورودهای پراکنده با کمینه زمان بین دو ورودی از Ti و محدودیت‌های مجوزی را می‌دهد یا ضرب‌ الاجل‌های خودسرانه را می‌دهد. تست‌های قابلیت زمان‌بندی دقیقی برای مدل کاری پراکنده برای برنامه‌ریزی اولویت ثابت بر اساس تحلیل زمان پاسخ [2] و برای برنامه ریزی EDF بر اساس معیار تقاضای پردازنده [5] توسعه داده شده است. فرمت‌های دیگر این مدل عبارتند از وظایف چند منظوره عمومی [4] که یک وظیفه می‌تواند انواع مختلف از وظایف را در دنباله‌ای ثابت دنبال کند که هر کدام از کارها با زمان اجرا، حداقل زمان بین دو ورودی و پارامترهای ضرب‌العجل خاص مربوط به نوع آن مشخص می‌شود. گسترش بیشتر به مدل وظیفه GMF غیر چرخه‌ای در [24] ارائه شده است که اجازه ترتیب غیرچرخه‌ای از انواع کارها را می‌دهد. عمومی‌ترین مدل، مدل وظیفه گراف جهت‌دار بلادرنگ (DRT) است که در آن هر وظیفه توسط یک گراف جهت‌دار توصیف شده است و هر راس نشان‌دهنده نوع کار (زمان اجرا و ضرب‌الاجل) است و هر یال نشان‌دهنده کمینه زمان بین دو ورود به یک کار بعدی از نوع مشخص شده توسط راس متصل است.

مدل‌های وظیفه GMF غیرچرخه‌ای و DRT را می‌توان تماما برای نمایش و تجزیه و تحلیل وظایف وابسته به سرعت استفاده کرد با این حال نیازهای تقریبی مورد نیاز با توجه به بدبینی در تجزیه و تحلیل وجود دارد. به عنوان مثال، با استفاده از یک مدل وظیفه پراکنده، یک کار وابسته به سرعت فرض می ‌شود که نیاز به حداکثر زمان اجرای آن را در کوتاه ترین مدت داشته باشید؛ با این حال، این موضوع منجر به بدبینی شدید می‌شود همانطور که در [15] نشان داده شده است. مدل وظیفه GMF غیرچرخه‌ای را می‌توان برای بازنمایی وظیفه وابسته به سرعت با تخصیص انواع کارهای مختلف به بخش‌هایی از محدوده سرعت مورد استفاده قرار داد. با این حال که مدل وظیفه‌ GMF غیر چرخه‌ای اجازه می‌دهد تا هر گونه سفارش از انواع شغل آن بدبینانه باشد. از آنجایی که گرافیک جهت‌دار قادر به ضبط انتقالات بین حالات کلری است، نمونه‌های ساده مدل وظیفه DRT برای مدل‌سازی وظایف وابسته به سرعت مناسب هستند [19]. با این حال، هنوز هم جا برای بهبود وجود دارد، زیرا محدودیت‌های فیزیکی توالی‌های احتمالی انواع کارها را محدود می‌کند. یک مشخصه دقیق از وظایف مستقل را می‌توان با استفاده از نمونه‌های پیچیده مدل وظیفه DRT بدست آورد [9]، با این حال، این رویکرد ممکن است از لحاظ تجزیه و تحلیل زمان اجرا خود سر باشد.

ما یادآوری می‌کنیم که مسئله تجزیه و تحلیل وظایف وابسته به سرعت دارای برخی از شباهت‌ها با تجزیه تغییر وضعیت حالت کلاسیک است، با این حال، تفاوت‌های قابل توجهی نیز وجود دارد. به عنوان مثال، وظایف وابسته به سرعت متفاوت می‌توانند حالت‌های اجرای خود را با توجه به آستانه‌های مختلف تغییر دهند و می‌توان آنها را از منابع چرخشی مستقل متفاوتی اشتقاق کرد. تغییرات بیشتر در حالت اجرا ممکن است بیش از شغل های متوالی انجام شود. این موضوع از مفهوم سنتی تغییر حالت عملیاتی متفاوت است.