اولویت با زودترین ضرب الاجل ( EDF ) یا کمترین زمان برای اجرا یک الگوریتم زمانبندی الویت پویا است که در سیستم عاملهای بی درنگ برای قراردادن فرایندها در صف الویت مورد استفاده قرار می گیرد. زمانی که یک رویداد زمانبندی ( تمام شدن یک وظیفه، آماده شدن یک وظیفه، غیره ) رخ می دهد، صف برای پیدا کردن فرآیندی که نزدیکترین ضرب الاجل را دارد مورد جستجو قرار می گیرد. فرآیندی که در نتیجه جستجو پیدا شود برای اجرا زمانبندی می شود.
در صورتی که کارها وقفه پذیر بوده و تنها در یک پردازنده قابل اجرا باشند آنگاه الگوریتم EDF یک الگوریتم زمانبندی بهینه خواهد بود به این معنا که اگر مجموعه ای از کارهای مستقل، که با زمان آماده شدن، زمان اجرای مورد نیاز و ضرب الاجل آن ها مشخص شده باشند را بتوان ( با هر الگوریتمی ) به طوری زمانبندی کرد که تمام کارها قبل از ضرب الاجل ها آن ها اجرا شوند، آنگاه الگوریتم EDF این مجموعه از کارها را نیز به گونه ای زمانبندی می کند که ضرب الاجل آن ها رعایت شود.
برای زمانبندی فرآیندهایی که ضرب الاجل آن ها برابر با دوره تناوب آن ها است، EDF کران بالای صد در صد برای بهره وری دارد؛ بنابراین تست زمانبندی برای EDF به صورت زیر خواهد بود:
که در این معادله { C i } بدترین حالت از زمان اجرا برای n فرایند و { T i } دوره تناوب زمان آماده شدن آن کارها ( برابر با ضرب الاجل نسبی فرض می شود ) می باشد.
به همین علت الگوریتم زمانبندی EDF تضمین می کند در صورتی که بهره وری کل CPU از ۱۰۰درصد بیشتر نباشد آنگاه تمام ضرب الاجل ها رعایت می شوند. در مقایسه با تکینک های زمانبندی الویت ثابت مانند زمانبندی با نرخ یکنواخت، الگوریتم EDF می تواند تمام ضرب الاجل ها در سیستم را در بارگیری بالاتری تضمین کند.
با این حال، هنگامی که سیستم بیش از حد بارگیری شود، مجموعه ای از فرایندها که قبل از ضرب الاجل خود به اتمام نمی رسند، به طور غیرقابل پیش بینی بزرگ می باشد ( که این تعداد تابعی از ضرب الاجل های دقیق ( و نه نسبی ) و زمان رخ دادن بارگیری بیش از حد می باشد ) . این مسئله یک عیب قابل توجه برای یک طراح سیستم بی درنگ می باشد. همچنین این الگوریتم به سختی در سخت افزار پیاده سازی می شود و یک مسئله دشوار در این الگوریتم نمایش ضرب الاجل ها در محدوده های مختلف می باشد ( ضرب الاجل ها نمی توانند دقیق تر از دقتی باشند که برای کلاک در زمانبندی در نظر گرفته شده است ) . اگر از یک محاسبات مدولار برای محاسبه ضرب الاجل های بعدی نسبت به زمان حال استفاده شود، بخش ذخیره ساز ضرب الاجل نسبی بعدی باید حداقل مقدار ( "مدت زمان" *۲ + "اکنون" ) را اصلاح کند. منظور از "مدت زمان"، طولانی ترین زمان مورد انتظار برای اجرا است؛ بنابراین EDF به طور معمول در سیستم های کامپیوتری بی درنگ صنعتی دیده نمی شود.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفدر صورتی که کارها وقفه پذیر بوده و تنها در یک پردازنده قابل اجرا باشند آنگاه الگوریتم EDF یک الگوریتم زمانبندی بهینه خواهد بود به این معنا که اگر مجموعه ای از کارهای مستقل، که با زمان آماده شدن، زمان اجرای مورد نیاز و ضرب الاجل آن ها مشخص شده باشند را بتوان ( با هر الگوریتمی ) به طوری زمانبندی کرد که تمام کارها قبل از ضرب الاجل ها آن ها اجرا شوند، آنگاه الگوریتم EDF این مجموعه از کارها را نیز به گونه ای زمانبندی می کند که ضرب الاجل آن ها رعایت شود.
برای زمانبندی فرآیندهایی که ضرب الاجل آن ها برابر با دوره تناوب آن ها است، EDF کران بالای صد در صد برای بهره وری دارد؛ بنابراین تست زمانبندی برای EDF به صورت زیر خواهد بود:
که در این معادله { C i } بدترین حالت از زمان اجرا برای n فرایند و { T i } دوره تناوب زمان آماده شدن آن کارها ( برابر با ضرب الاجل نسبی فرض می شود ) می باشد.
به همین علت الگوریتم زمانبندی EDF تضمین می کند در صورتی که بهره وری کل CPU از ۱۰۰درصد بیشتر نباشد آنگاه تمام ضرب الاجل ها رعایت می شوند. در مقایسه با تکینک های زمانبندی الویت ثابت مانند زمانبندی با نرخ یکنواخت، الگوریتم EDF می تواند تمام ضرب الاجل ها در سیستم را در بارگیری بالاتری تضمین کند.
با این حال، هنگامی که سیستم بیش از حد بارگیری شود، مجموعه ای از فرایندها که قبل از ضرب الاجل خود به اتمام نمی رسند، به طور غیرقابل پیش بینی بزرگ می باشد ( که این تعداد تابعی از ضرب الاجل های دقیق ( و نه نسبی ) و زمان رخ دادن بارگیری بیش از حد می باشد ) . این مسئله یک عیب قابل توجه برای یک طراح سیستم بی درنگ می باشد. همچنین این الگوریتم به سختی در سخت افزار پیاده سازی می شود و یک مسئله دشوار در این الگوریتم نمایش ضرب الاجل ها در محدوده های مختلف می باشد ( ضرب الاجل ها نمی توانند دقیق تر از دقتی باشند که برای کلاک در زمانبندی در نظر گرفته شده است ) . اگر از یک محاسبات مدولار برای محاسبه ضرب الاجل های بعدی نسبت به زمان حال استفاده شود، بخش ذخیره ساز ضرب الاجل نسبی بعدی باید حداقل مقدار ( "مدت زمان" *۲ + "اکنون" ) را اصلاح کند. منظور از "مدت زمان"، طولانی ترین زمان مورد انتظار برای اجرا است؛ بنابراین EDF به طور معمول در سیستم های کامپیوتری بی درنگ صنعتی دیده نمی شود.
