الویت با زودترین ضرب الاجل( EDF ) یا کمترین زمان برای اجرا یک الگوریتم زمانبندی الویت پویا است که در سیستم عاملهای بلادرنگ برای قراردادن فرآیندها در صف الویت مورد استفاده قرار میگیرد. زمانی که یک رویداد زمانبندی (تمام شدن یک وظیفه، آماده شدن یک وظیفه، غیره) رخ میدهد، صف برای پیدا کردن فرآیندی که نزدیکترین ضرب الاجل را دارد مورد جستجو قرار میگیرد. فرآیندی که در نتیجه جستجو پیدا شود برای اجرا زمانبندی می شود.
SHARK(شارک)، سیستم عامل های بلادرنگ نسخه های مختلف زمانبند EDF و الگوریتم های زمان بندی رزرو منابع را پیاده سازی و اجرا میکنند.
ERIKA Enterprise، نسخهٔ شرکتی اریکا حالت بهینه ایی از الگوریتم EDF را برای میکروکنترلرهای کوچک با رابط برنامه نویسی کاربردی مشابه با رابط برنامه نویسی کاربردی OSEK پیاده سازی کرده است .
کرنل Everyman این کرنل هر دو زمانبند EDF یا ضرب العجل یکنواخت را با توجه به تنظیمات کاربر اجرا می کند.
MaRTE OS این سیستم عامل به عنوان زمان اجرا برای برنامه هایی که با زبان برنامه نویسی ایدا نوشته شده اند را اجرا می کند.
پروژه AQuoSA تغییری در هسته لینوکس ایجاد کرده است و توانمندی زمانبند فرآیندها را با اضافه کردن الگوریتم EDF و با توجه به توانایی هایی که این الگوریتم دارد، افزایش داده است. تنظیم وقت یک زمان بندی نمی تواند مانند سیستم های عامل بلادرنگ سخت، دقیق باشد اما به اندازه کافی دقیق است به طوری که می تواند به میزان قابل توجهی قابل پیش بینی بودن را بالا برده و نیازمندی های برنامه های چند رسانه ای بلادرنگ را برطرف کند. AQuoSA یکی از چندین پروژه است که با استفاده از یک مدل مناسب کنترل دسترسی، قابلیت های برنامه ریزی بلادرنگی را به کاربران غیر مجاز بر روی سیستم در یک روش کنترل شده فراهم می کند.
کرنل لینوکس الگوریتم زمانبندی EDF را با نام SCHED DEADLINE پیاده سازی کرده است که از زمان انتشار نسخه 3.14 سیستم عامل در دسترس است.
زمانبند بلادرنگ این زمانبند در حین پروژه IRMOS اروپا معرفی شده است که یک زمانبند بلادرنگ چند پردازنده ایی برای کرنل لینوکس است، به ویژه برای جداسازی زمانی و ارائه گارانتی QoS برای اجزای نرم افزاری چند رشته ای پیچیده و تمامی ماشین های مجازی مناسب می باشد. برای مثال، هنگام استفاده از لینوکس به عنوان سیستم عامل میزبان و KVM به عنوان ناظر ماشین مجازی، IRMOS می تواند برای تضمین کردن زمانبندی VMهای جدا از هم و در عین حال ایزوله کردن عملکرد آنها برای اجتناب از تداخل زمانی ناخواسته، مورد استفاده قرار گیرد. IRMOS دارای یک برنامه ریز سلسله مراتبی EDF / FP می باشد . در سطح بالاتر، یک زمانبند EDF جزئی بر روی پردازنده های موجود وجود دارد. با این حال، رزروها چند پردازنده ای هستند و برای زمانبندی رشته ها(فرآیندها ی and/or)در لایه های پایین تری، FP عمومی بر روی سیستم های چندپردازنده ای به هریک از رزروهای EDF بالاتر پیوست می شود. برای یک مرور کلی و یادگیری بیشتر این مبحت می توانید مقاله ای در سایت lwn.net را مشاهده کنید.
در حال حاضر Xen یک زمانبند EDF دارد. کتابچه راهنما شامل یک توضیح کوتاه است.
سیستم عامل Plan 9 از آزمایشگاه های Bell دارای EDFI، یک پروتکل زمان بندی زمانبندی سبک وزن است که ادغام EDF را با ارجاع مهلت به منابع مشترک به اشتراک می گذارد.
RTEMS : زمانبند EDF در نسخه 4.11 در دسترس خواهد بود. RTEMS SuperCore
Litmus-RT یک توسیع بلادرنگ از کرنل لینوکس با تمرکز بر زمانبندی و هماهنگ سازی بلادرنگ چند پردازنده ها است. مجموعهٔ الگوریتم های بلادرنگ آن شامل زمانبندهای EDF-جزیی، EDF-کلی و EDF-خوشه ای می باشد .
در صورتی که کارها وقفه پذیر بوده و تنها در یک پردازنده قابل اجرا باشند آنگاه الگوریتم EDF یک الگوریتم زمانبندی بهینه خواهد بود به این معنا که اگر مجموعه ای از کارهای مستقل، که با زمان آماده شدن، زمان اجرای مورد نیاز و ضرب الاجل آن ها مشخص شده باشند را بتوان (با هر الگوریتمی) به طوری زمانبندی کرد که تمام کارها قبل از ضرب الاجل ها آن ها اجرا شوند، آنگاه الگوریتم EDF این مجموعه از کارها را نیز به گونه ای زمانبندی می کند که ضرب الاجل آن ها رعایت شود.
برای زمانبندی فرآیندهایی که ضرب الاجل آن ها برابر با دوره تناوب آن ها است، EDF کران بالای صد در صد برای بهره وری دارد. بنابراین تست زمانبندی برای EDF به صورت زیر خواهد بود:
که در این معادله { C i } {\displaystyle \left\{C_{i}\right\}} بدترین حالت از زمان اجرا برای n {\displaystyle n} فرآیند و { T i } {\displaystyle \left\{T_{i}\right\}} دوره تناوب زمان آماده شدن آن کارها(برابر با ضرب الاجل نسبی فرض می شود) می باشد.
SHARK(شارک)، سیستم عامل های بلادرنگ نسخه های مختلف زمانبند EDF و الگوریتم های زمان بندی رزرو منابع را پیاده سازی و اجرا میکنند.
ERIKA Enterprise، نسخهٔ شرکتی اریکا حالت بهینه ایی از الگوریتم EDF را برای میکروکنترلرهای کوچک با رابط برنامه نویسی کاربردی مشابه با رابط برنامه نویسی کاربردی OSEK پیاده سازی کرده است .
کرنل Everyman این کرنل هر دو زمانبند EDF یا ضرب العجل یکنواخت را با توجه به تنظیمات کاربر اجرا می کند.
MaRTE OS این سیستم عامل به عنوان زمان اجرا برای برنامه هایی که با زبان برنامه نویسی ایدا نوشته شده اند را اجرا می کند.
پروژه AQuoSA تغییری در هسته لینوکس ایجاد کرده است و توانمندی زمانبند فرآیندها را با اضافه کردن الگوریتم EDF و با توجه به توانایی هایی که این الگوریتم دارد، افزایش داده است. تنظیم وقت یک زمان بندی نمی تواند مانند سیستم های عامل بلادرنگ سخت، دقیق باشد اما به اندازه کافی دقیق است به طوری که می تواند به میزان قابل توجهی قابل پیش بینی بودن را بالا برده و نیازمندی های برنامه های چند رسانه ای بلادرنگ را برطرف کند. AQuoSA یکی از چندین پروژه است که با استفاده از یک مدل مناسب کنترل دسترسی، قابلیت های برنامه ریزی بلادرنگی را به کاربران غیر مجاز بر روی سیستم در یک روش کنترل شده فراهم می کند.
کرنل لینوکس الگوریتم زمانبندی EDF را با نام SCHED DEADLINE پیاده سازی کرده است که از زمان انتشار نسخه 3.14 سیستم عامل در دسترس است.
زمانبند بلادرنگ این زمانبند در حین پروژه IRMOS اروپا معرفی شده است که یک زمانبند بلادرنگ چند پردازنده ایی برای کرنل لینوکس است، به ویژه برای جداسازی زمانی و ارائه گارانتی QoS برای اجزای نرم افزاری چند رشته ای پیچیده و تمامی ماشین های مجازی مناسب می باشد. برای مثال، هنگام استفاده از لینوکس به عنوان سیستم عامل میزبان و KVM به عنوان ناظر ماشین مجازی، IRMOS می تواند برای تضمین کردن زمانبندی VMهای جدا از هم و در عین حال ایزوله کردن عملکرد آنها برای اجتناب از تداخل زمانی ناخواسته، مورد استفاده قرار گیرد. IRMOS دارای یک برنامه ریز سلسله مراتبی EDF / FP می باشد . در سطح بالاتر، یک زمانبند EDF جزئی بر روی پردازنده های موجود وجود دارد. با این حال، رزروها چند پردازنده ای هستند و برای زمانبندی رشته ها(فرآیندها ی and/or)در لایه های پایین تری، FP عمومی بر روی سیستم های چندپردازنده ای به هریک از رزروهای EDF بالاتر پیوست می شود. برای یک مرور کلی و یادگیری بیشتر این مبحت می توانید مقاله ای در سایت lwn.net را مشاهده کنید.
در حال حاضر Xen یک زمانبند EDF دارد. کتابچه راهنما شامل یک توضیح کوتاه است.
سیستم عامل Plan 9 از آزمایشگاه های Bell دارای EDFI، یک پروتکل زمان بندی زمانبندی سبک وزن است که ادغام EDF را با ارجاع مهلت به منابع مشترک به اشتراک می گذارد.
RTEMS : زمانبند EDF در نسخه 4.11 در دسترس خواهد بود. RTEMS SuperCore
Litmus-RT یک توسیع بلادرنگ از کرنل لینوکس با تمرکز بر زمانبندی و هماهنگ سازی بلادرنگ چند پردازنده ها است. مجموعهٔ الگوریتم های بلادرنگ آن شامل زمانبندهای EDF-جزیی، EDF-کلی و EDF-خوشه ای می باشد .
در صورتی که کارها وقفه پذیر بوده و تنها در یک پردازنده قابل اجرا باشند آنگاه الگوریتم EDF یک الگوریتم زمانبندی بهینه خواهد بود به این معنا که اگر مجموعه ای از کارهای مستقل، که با زمان آماده شدن، زمان اجرای مورد نیاز و ضرب الاجل آن ها مشخص شده باشند را بتوان (با هر الگوریتمی) به طوری زمانبندی کرد که تمام کارها قبل از ضرب الاجل ها آن ها اجرا شوند، آنگاه الگوریتم EDF این مجموعه از کارها را نیز به گونه ای زمانبندی می کند که ضرب الاجل آن ها رعایت شود.
برای زمانبندی فرآیندهایی که ضرب الاجل آن ها برابر با دوره تناوب آن ها است، EDF کران بالای صد در صد برای بهره وری دارد. بنابراین تست زمانبندی برای EDF به صورت زیر خواهد بود:
که در این معادله { C i } {\displaystyle \left\{C_{i}\right\}} بدترین حالت از زمان اجرا برای n {\displaystyle n} فرآیند و { T i } {\displaystyle \left\{T_{i}\right\}} دوره تناوب زمان آماده شدن آن کارها(برابر با ضرب الاجل نسبی فرض می شود) می باشد.
اول کمترین ضرب العجل(EDF) یا کمترین زمان برای اجرا یک الگوریتم زمانبندی الویت پویا است که در سیستم عاملهای بلادرنگ برای قراردادن فرایندها در صف الویت مورد استفاده قرار می گیرد. زمانی که یک رویداد زمانبندی (تمام شدن یک وظیفه، آماده شدن یک وظیفه، غیره) رخ می دهد، صف برای پیدا کردن فرآیندی که نزدیکترین ضرب العجل را دارد مورد جستجو قرار می گیرد. فرآیندی که در نتیجه جستجو پیدا شود برای اجرا زمانبندی می شود.
SHARK(شارک)، سیستم عاملهای بلادرنگ نسخه های مختلف زمانبند EDF و الگوریتم های زمان بندی رزرو منابع را پیاده سازی و اجرا می کنند.
ERIKA Enterprise، نسخهٔ شرکتی اریکا حالت بهینه ایی از الگوریتم EDF را برای میکروکنترلرهای کوچک با رابط برنامه نویسی کاربردی مشابه با رابط برنامه نویسی کاربردی OSEK پیاده سازی کرده است.
کرنل Everyman این کرنل هر دو زمانبند EDF یا ضرب العجل یکنواخت را با توجه به تنظیمات کاربر اجرا می کند.
MaRTE OS این سیستم عامل به عنوان زمان اجرا برای برنامه هایی که با زبان برنامه نویسی ایدا نوشته شده اند را اجرا می کند.
پروژه AQuoSA تغییری در هسته لینوکس ایجاد کرده است و توانمندی زمانبند فرایندها را با اضافه کردن الگوریتم EDF و با توجه به توانایی هایی که این الگوریتم دارد، افزایش داده است.. تنظیم وقت زمان بندی نمی تواند مانند سیستم های عامل بلادرنگ سخت، دقیق باشد اما به اندازه کافی دقیق است به طوری که به میزان قابل توجهی قابل پیش بینی بودن و به این ترتیب شرایط واقعی در برنامه های چند رسانه ای را انجام می دهد. AQuoSA یکی از چندین پروژه است که با استفاده از یک مدل کنترل دسترسی به طور مناسب طراحی شده قابلیت های برنامه ریزی زمان واقعی را به کاربران غیرمجاز بر روی سیستم در یک روش کنترل شده فراهم می کند.
کرنل لینوکس الگوریتم زمانبندی EDF را با نام SCHED DEADLINE پیاده سازی کرده است که از زمان انتشار نسخه ۳٫۱۴ سیستم عامل در دسترس است.
زمانبند بلادرنگ این زمانبند در حین پروژه IRMOS اروپا ایجاد شده است که یک زمانبند بلادرنگ چند پردازنده ایی برای کرنل لینوکس است زمان واقعی چند پردازنده برای هسته لینوکس است، مخصوصاً برای جداسازی زمانی و ارائه تضمین QoS برای اجزای نرم افزاری پیچیده چند رشته و همچنین کل ماشین های مجازی. برای مثال، هنگام استفاده از لینوکس به عنوان سیستم عامل میزبان و KVM به عنوان ناظر ماشین مجازی، IRMOS می تواند مورد استفاده قرار گیرد برای ارائه تضمین های برنامه ریزی برای VMهای indidivual و در عین حال جدا کردن عملکرد خود را به منظور جلوگیری از تداخل زمانی ناخواسته. IRMOS دارای یک برنامه ریز سلسله مراتبی EDF / FP می باشد. در سطح بیرونی یک برنامه ریزی EDF تقسیم شده بر روی پردازنده های موجود وجود دارد. با این حال، رزرو چند پردازنده است، و FP جهانی بیش از چند پردازنده در سطح درونی به منظور برنامه ریزی موضوعات (و / یا فرآیندهای) متصل به هر رزرو EDF خارجی استفاده می شود. همچنین این مقاله را در lwn.net برای یک مرور کلی و یک درس کوتاه در مورد موضوع مشاهده کنید. در حال حاضر Xen تا به حال یک برنامه ریز EDF داشته است. کتابچه راهنما شامل یک توضیح کوتاه است.
سیستم عامل Plan 9 از آزمایشگاه Bell دارای EDFI، یک پروتکل زمان بندی زمانبندی سبک وزن است که ادغام EDF را با ارجاع مهلت به منابع مشترک به اشتراک می گذارد.
RTEMS: زمانبند EDF در نسخه ۴٫۱۱ در دسترس خواهد بود. RTEMS SuperCore
Litmus-RT یک توسیع بلادرنگ از کرنل لینوکس با تمرکز بر زمانبندی و هماهنگ سازی بلادرنگ چند پردازنده ها است. مجموعهٔ الگوریتم های بلادرنگ آن شامل زمانبندهای EDF-جزیی، EDF-کلی و EDF-خوشه ای می باشد.
برای زمانبندی فرآیندهایی که ضرب العجل آنها برابر با دوره تناوب آنها است، EDF کران بالای صد در صد برای بهره وری دارد؛ بنابراین تست زمانبندی برای EDF به صورت زیر خواهد بود:
۳ فرایند تناوبی وقفه ناپذیر که روی یک پردازنده زمانبندی شده اند را در نظر بگیرید. در جدول زیر زمانهای اجرا و دوره های تناوب آنها آورده شده است:
در این مثال، واحد زمان می تواند به عنوان زمان برش زمان برنامه ریزی شده در نظر گرفته شود. منظور از ضرب العجل این است که اجرای هر فرایند باید در دورهٔ تناوب خودش به اتمام برسد.
SHARK(شارک)، سیستم عاملهای بلادرنگ نسخه های مختلف زمانبند EDF و الگوریتم های زمان بندی رزرو منابع را پیاده سازی و اجرا می کنند.
ERIKA Enterprise، نسخهٔ شرکتی اریکا حالت بهینه ایی از الگوریتم EDF را برای میکروکنترلرهای کوچک با رابط برنامه نویسی کاربردی مشابه با رابط برنامه نویسی کاربردی OSEK پیاده سازی کرده است.
کرنل Everyman این کرنل هر دو زمانبند EDF یا ضرب العجل یکنواخت را با توجه به تنظیمات کاربر اجرا می کند.
MaRTE OS این سیستم عامل به عنوان زمان اجرا برای برنامه هایی که با زبان برنامه نویسی ایدا نوشته شده اند را اجرا می کند.
پروژه AQuoSA تغییری در هسته لینوکس ایجاد کرده است و توانمندی زمانبند فرایندها را با اضافه کردن الگوریتم EDF و با توجه به توانایی هایی که این الگوریتم دارد، افزایش داده است.. تنظیم وقت زمان بندی نمی تواند مانند سیستم های عامل بلادرنگ سخت، دقیق باشد اما به اندازه کافی دقیق است به طوری که به میزان قابل توجهی قابل پیش بینی بودن و به این ترتیب شرایط واقعی در برنامه های چند رسانه ای را انجام می دهد. AQuoSA یکی از چندین پروژه است که با استفاده از یک مدل کنترل دسترسی به طور مناسب طراحی شده قابلیت های برنامه ریزی زمان واقعی را به کاربران غیرمجاز بر روی سیستم در یک روش کنترل شده فراهم می کند.
کرنل لینوکس الگوریتم زمانبندی EDF را با نام SCHED DEADLINE پیاده سازی کرده است که از زمان انتشار نسخه ۳٫۱۴ سیستم عامل در دسترس است.
زمانبند بلادرنگ این زمانبند در حین پروژه IRMOS اروپا ایجاد شده است که یک زمانبند بلادرنگ چند پردازنده ایی برای کرنل لینوکس است زمان واقعی چند پردازنده برای هسته لینوکس است، مخصوصاً برای جداسازی زمانی و ارائه تضمین QoS برای اجزای نرم افزاری پیچیده چند رشته و همچنین کل ماشین های مجازی. برای مثال، هنگام استفاده از لینوکس به عنوان سیستم عامل میزبان و KVM به عنوان ناظر ماشین مجازی، IRMOS می تواند مورد استفاده قرار گیرد برای ارائه تضمین های برنامه ریزی برای VMهای indidivual و در عین حال جدا کردن عملکرد خود را به منظور جلوگیری از تداخل زمانی ناخواسته. IRMOS دارای یک برنامه ریز سلسله مراتبی EDF / FP می باشد. در سطح بیرونی یک برنامه ریزی EDF تقسیم شده بر روی پردازنده های موجود وجود دارد. با این حال، رزرو چند پردازنده است، و FP جهانی بیش از چند پردازنده در سطح درونی به منظور برنامه ریزی موضوعات (و / یا فرآیندهای) متصل به هر رزرو EDF خارجی استفاده می شود. همچنین این مقاله را در lwn.net برای یک مرور کلی و یک درس کوتاه در مورد موضوع مشاهده کنید. در حال حاضر Xen تا به حال یک برنامه ریز EDF داشته است. کتابچه راهنما شامل یک توضیح کوتاه است.
سیستم عامل Plan 9 از آزمایشگاه Bell دارای EDFI، یک پروتکل زمان بندی زمانبندی سبک وزن است که ادغام EDF را با ارجاع مهلت به منابع مشترک به اشتراک می گذارد.
RTEMS: زمانبند EDF در نسخه ۴٫۱۱ در دسترس خواهد بود. RTEMS SuperCore
Litmus-RT یک توسیع بلادرنگ از کرنل لینوکس با تمرکز بر زمانبندی و هماهنگ سازی بلادرنگ چند پردازنده ها است. مجموعهٔ الگوریتم های بلادرنگ آن شامل زمانبندهای EDF-جزیی، EDF-کلی و EDF-خوشه ای می باشد.
برای زمانبندی فرآیندهایی که ضرب العجل آنها برابر با دوره تناوب آنها است، EDF کران بالای صد در صد برای بهره وری دارد؛ بنابراین تست زمانبندی برای EDF به صورت زیر خواهد بود:
۳ فرایند تناوبی وقفه ناپذیر که روی یک پردازنده زمانبندی شده اند را در نظر بگیرید. در جدول زیر زمانهای اجرا و دوره های تناوب آنها آورده شده است:
در این مثال، واحد زمان می تواند به عنوان زمان برش زمان برنامه ریزی شده در نظر گرفته شود. منظور از ضرب العجل این است که اجرای هر فرایند باید در دورهٔ تناوب خودش به اتمام برسد.