زمان‌بندی اولویت با زودترین ضرب‌الاجل
اولویت با زودترین ضرب الاجل(EDF) یا کمترین زمان برای اجرا یک الگوریتم زمانبندی الویت پویا است که در سیستم عاملهای بی‌درنگ برای قراردادن فرایندها در صف الویت مورد استفاده قرار می‌گیرد. زمانی که یک رویداد زمانبندی (تمام شدن یک وظیفه، آماده شدن یک وظیفه، غیره) رخ می‌دهد، صف برای پیدا کردن فرآیندی که نزدیکترین ضرب الاجل را دارد مورد جستجو قرار می‌گیرد. فرآیندی که در نتیجه جستجو پیدا شود برای اجرا زمانبندی می‌شود.
در صورتی که کارها وقفه پذیر بوده و تنها در یک پردازنده قابل اجرا باشند آنگاه الگوریتم EDF یک الگوریتم زمانبندی بهینه خواهد بود به این معنا که اگر مجموعه ای از کارهای مستقل، که با زمان آماده شدن، زمان اجرای مورد نیاز و ضرب الاجل آن‌ها مشخص شده باشند را بتوان (با هر الگوریتمی) به طوری زمانبندی کرد که تمام کارها قبل از ضرب الاجل‌ها آن‌ها اجرا شوند، آنگاه الگوریتم EDF این مجموعه از کارها را نیز به گونه ای زمانبندی می‌کند که ضرب الاجل آن‌ها رعایت شود.
برای زمانبندی فرآیندهایی که ضرب الاجل آن‌ها برابر با دوره تناوب آن‌ها است، EDF کران بالای صد در صد برای بهره‌وری دارد؛ بنابراین تست زمانبندی برای EDF به صورت زیر خواهد بود:
که در این معادله formula_2 بدترین حالت از زمان اجرا برای formula_3 فرایند و formula_4 دوره تناوب زمان آماده شدن آن کارها (برابر با ضرب الاجل نسبی فرض می‌شود) می‌باشد.
به همین علت الگوریتم زمانبندی EDF تضمین می‌کند در صورتی که بهره‌وری کل CPU از ۱۰۰درصد بیشتر نباشد آنگاه تمام ضرب الاجل‌ها رعایت می‌شوند. در مقایسه با تکینک‌های زمانبندی الویت ثابت مانند زمانبندی با نرخ یکنواخت، الگوریتم EDF می‌تواند تمام ضرب الاجل‌ها در سیستم را در بارگیری بالاتری تضمین کند.
با این حال، هنگامی که سیستم بیش از حد بارگیری شود، مجموعه ای از فرایندها که قبل از ضرب الاجل خود به اتمام نمی‌رسند، به‌طور غیرقابل پیش‌بینی بزرگ می‌باشد (که این تعداد تابعی از ضرب الاجل‌های دقیق (و نه نسبی) و زمان رخ دادن بارگیری بیش از حد می‌باشد). این مسئله یک عیب قابل توجه برای یک طراح سیستم بی‌درنگ می‌باشد. همچنین این الگوریتم به سختی در سخت‌افزار پیاده‌سازی می‌شود و یک مسئله دشوار در این الگوریتم نمایش ضرب الاجل‌ها در محدوده‌های مختلف می‌باشد (ضرب الاجل‌ها نمی‌توانند دقیق تر از دقتی باشند که برای کلاک در زمانبندی در نظر گرفته شده‌است). اگر از یک محاسبات مدولار برای محاسبه ضرب الاجل‌های بعدی نسبت به زمان حال استفاده شود، بخش ذخیره‌ساز ضرب الاجل نسبی بعدی باید حداقل مقدار ("مدت زمان" *۲ + "اکنون") را اصلاح کند. منظور از "مدت زمان"، طولانی‌ترین زمان مورد انتظار برای اجرا است؛ بنابراین EDF به‌طور معمول در سیستم‌های کامپیوتری بی‌درنگ صنعتی دیده نمی‌شود.
در مقابل، اکثر سیستم‌های کامپیوتری بی‌درنگ از الگوریتم‌های (معمولا زمانبندی نرخ یکنواخت) استفاده می‌کنند. با اولویت‌های ثابت، قابل پیش‌بینی است که شرایط بارگیری منجر می‌شود تا فرآیندهای با الویت کمتر قبل از ضرب الاجل خود به پایان نرسند و در حالی که فرآیندهای با الویت بالاتر همچنان بتوانند تا قبل از ضرب الاجل خود به پایان برسند.
یک بخش مهمی از مطالعات مربوط به زمانبندی EDF در محاسبات بی‌درنگ می‌باشد. در الگوریتم EDF محاسبه بدترین حالت زمان پاسخگویی برای فرایندها امکان‌پذیر می‌باشد؛ این مسئله برای مدیریت کردن نوع‌های دیگری از فرایندها (غیر از فرآیندهای تناوبی مانند غیر تناوبی و موردی) و استفاده از سرورها برای تنظیم بارگیری مفید می‌باشد.
۳ فرایند تناوبی وقفه ناپذیر که روی یک پردازنده زمانبندی شده‌اند را در نظر بگیرید. در جدول زیر زمان‌های اجرا و دوره‌های تناوب آن‌ها آورده شده‌است:
در این مثال، واحد زمان می‌تواند به عنوان زمان برش زمان برنامه ریزی شده در نظر گرفته شود. منظور از ضرب الاجل این است که اجرای هر فرایند باید در دورهٔ تناوب خودش به اتمام برسد.
در نمودار زمانبندی، ستون‌ها برش زمانی را نشان می‌دهند که با حرکت به سمت راست افزایش می‌یابند، و تمام فرایندها دورهٔ تناوب خود را از برش زمانی صفر شروع می‌کنند. رنگ سایه‌های آبی و سفید که تناوبی به دنبال یکدیگر در نمودار زمانبندی آمده‌اند دوره تناوب فرایندها را نشان می‌دهند و ضرب‌الاجل فرایندها برابر با زمان تغییر رنگ در نمودار زمانبندی می‌باشد. با مهلت‌های تغییر رنگ.
P2 اولین فرآیندی است که توسط EDF زمانبندی شده‌است، زیرا کمترین دوره تناوب را دارد و بنابراین نزدیکترین ضرب‌الاجل را دارا می‌باشد. به همین ترتیب، زمانی که P2 تکمیل می‌شود، P1 و به دنبال آن P3 زمانبندی می‌شود.
در برش زمانی برابر با ۵، هر دو فرایند P2 و P3 ضرب‌العجل‌های برابر دارند، به همین علت لازم است ال قبل از برش زمانی برابر با ۱۰ اجرای آن‌ها تمام شود بنابراین EDF می‌تواند هر یک از آن‌ها را زمانبندی کند.
به‌کارگیری به صورت زیر خواهد بود:
formula_5
از آنجا که کوچکترین مضرب مشترک دوره تناوب ۴۰ است، الگوی زمانبندی می‌تواند در هر ۴۰ بار برش زمانی تکرار شود. اما، فقط ۳۷ از آن ۴۰ تا برش زمانی توسط P1، P2، یا P3 استفاده می‌شود. از آنجا که به‌کارگیری، ۹۲٫۵٪، بیش از ۱۰۰٪ نیست، سیستم قابلیت زمانبندی با الگوریتم EDF را دارد.
تعویض نامطلوب ضرب‌العجل‌ها ممکن است در زمانبندی EDF رخ دهد. یک فرایند ممکن است از یک منبع مشترک در یک بخش بحرانی (اجرای پردازه‌ها در بخش‌های بحرانی وقفه ناپذیر است) استفاده کند تا در صورت وجود فرآیندی با ضرب‌الاجل زودتر، مانع از ایجاد وقفه و زمانبندی مجدد در آن شود. در چنین شرایطی، برای زمانبند مهم است که به فرایند در حال اجرا زودترین ضرب‌الاجل را اختصاص داده و در نتیجه این فرایند در مقابل دیگر فرآیندهای منتظر پردازنده، الویت بیشتری پیدا می‌کند. در غیر این صورت به فرآیندهای با ضرب‌الاجل زودتر پردازنده داده نمی‌شود و ممکن است تا قبل از ضرب‌الاجل خود نتوانند کار خود را اجرا کنند.
این مسئله به خصوص اهمیت بیشتری پیدا می‌کند که فرایند در حال اجرا در بخش بحرانی، زمان بیشتری برای اجرا و خروج از بخش بحرانی داشته باشد، که در این صورت در آزاد سازی منبع مشترک تأخیر ایجاد خواهد کرد. اما فرایند همچنان می‌تواند به نفع فرآیندهای دیگر که ضرب‌الاجل زودتری داشته اما منبع حیاتی را به اشتراک نمی‌گذارند، وقفه پذیر باشد. این خطر در تعویض ضرب‌العجل‌ها مشابه است با معکوس کردن الویت‌ها وقتی از استفاده می‌کنیم.
برای سرعت بخشیدن در یافتن زودترین ضرب‌الاجل در یک صف آماده، لازم است تا عناصر در صف براساس ضرب‌الاجل آن‌ها مرتب شود. زمانی که یک فرایند یا یک فرایند تناوبی با ضرب‌الاجل جدیدی وارد شود، قبل از اولین فرایند با ضرب‌الاجل دیرتر در صف قرار می‌گیرد. با این روش، فرآیندهای با ضرب‌العجل‌های زودتر همیشه در ابتدای صف قرار می‌گیرند.
در تحلیل رفتار یک صف با ترافیک-سنگین در سروری که از الگوریتم زمانبندی EDF با سیاست رها کردن(انجام نشدن) استفاده می‌کند، فرایندها ضرب‌العجلی برای انجام کارهایشان دارند و سرور تنها تا زمانی که ضرب‌الاجل آن‌ها سپری نشده به آن‌ها سرویس می‌دهد. میزان کار رها شده (انجام نشده)، به عنوان کار باقی‌مانده تعریف می‌شود که به علت سپری شدن ضرب‌الاجل امکان سرویس دهی به آن وجود نداشته‌است. این میزان از کار رها شده (انجام نشده) معیاری مهم برای ارزیابی عملکرد می‌باشد.
عموماً پذیرفته شده‌است که پیاده‌سازی یک زمانبندی وقفه ناپذیر الویت ثابت (FPS) ساده‌تر از یک زمانبند اولویت پویا، مانند EDF است. با این حال، هنگام مقایسه حداکثر استفاده یک زمانبندی بهینه با الویت ثابت (با اولویت هر موضوعی که توسط برنامه‌ریزی نرخ مونوتونی ارائه شده‌است)، EDF می‌تواند به ۱۰۰٪ به‌کارگیری برسد، در حالی که از لحاظ تئوری حداکثر مقدار زمانبندی نرخ یکنواخت حدود ۶۹٪ می‌باشد.
توجه داشته باشید که EDF هیچگونه فرض خاصی را در مورد دوره تناوب وظایف تعریف نمی‌کند؛ بنابراین می‌توان از این الگوریتم هم برای زمانبندی وظایف تناوبی و هم برای زمانبندی وظایف غیر تناوبی استفاده کرد.
اگر چه پیاده‌سازی EDF در؛ کرنل‌های بی‌درنگ تجاری رایج نیست، در ادامه چندین مورد از کرنل‌های متن باز و بلادرنگی که EDF را پیاده‌سازی و اجرا کرده‌اند آورده شده‌است: