نجمه کج کلاه

abstract It is over 40 years since the first seminal work on priority assignment for real-time systems using fixed priority scheduling. Since then, huge progress has been made in the field of real-time scheduling with more complex models and schedulability analysis techniques developed to better represent and analyse real systems .This tutorial style review provides an in-depth assessment of priority assignment techniques for hard real-time systems scheduled using fixed priorities.It examines the role and importance of priority in fixed priority scheduling in all of its guises,including: pre-emptive and non-pre-emptive scheduling;covering single-and multi-processor systems,and networks .A categorisation of optimal priority assignment techniques is given,along with the conditions on their applicability .We examine the extension of these techniques via sensitivity analysis to form robust priority assignment policies that can be used even when there is only partial information available about the system .The review covers priority assignment in a wide variety of settings including: mixed-criticality systems , systems with deferred pre-emption , and probabilistic real-time systems with worst-case execution times described by random variables.It concludes with a discussion of open problems in the area of priority assignment.

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

10. Summary and conclusions This tutorial-style survey and review examined the importance of priority assignment in systems scheduled using fixed priorities.We started with a graphic example based on Controller Area Network(CAN)showing how ignoring appropriate priority assignment techniques can reduce achievable bus utilisation from around 80% down to below 35%.This is one of the reasons for the current myth in some parts of the Automotive industry that CAN is only able to operate at around 35% utilisation without missing deadlines.

10. خلاصه و نتیجه گیری این سبک آموزش خصوصی بررسی و باز بینی امتحان شده اهمیت واگذاری اولویت در سیستم های زمانبندی شده با استفاده اولویت های ثابت است . ما شروع می کنیم با یک مثال ترسیمی پایه ای در شبکه فضا کنترل کننده (CAN) نشان دادن چگونه اختصاص تکنیک های واگذاری اولویت می تواند قابلیت دست یافتن کارایی bus از محدوده 80%پایین به زیر 35% کاهش دهد . این یک دلیل برای صحت در بعضی بخش ها از صنعت خودرو که CAN فقط قادر به اجرا در حدود کارایی 35% بدون اینکه مهلت زمانی را از دست دهد .

We also described how Audsley’s algorithm can be modified to minimise the number of priority levels required or to minimise the reverse lexicographical distance from any desired priority ordering . Further , we introduced a new variant of Audsley’s algorithm , OPA-MLD which can be used to minimise the lexicographical distance from any desired priority ordering , enabling important tasks to be placed at high priority levels.

ما همچنین توصیف کردیم چگونه الگوریتم Audsley می تواند به حداقل کردن سطوح اولویت مورد نیاز یا حداقل کردن فاصله lexicographical معکوس از هر مرتب سازی اولویت خواسته شده اصلاح شود . بعلاوه ، ما یک تنوع جدید از الگوریتم Audsley معرفی کردیم ، OPA-MLD که می تواند به حداقل کردن فاصله lexicographical از هر مرتب سازی اولویت خواسته شده استفاده شود ، task های مهم به جایگذاری در سطوح اولویت بالا را قادر می سازد .