زمان‌بندی اولویت با زودترین ضرب‌الاجل

نمودار زمان‌بندی

در نمودار زمانبندی، ستون‌ها برش زمانی را نشان می‌دهند که با حرکت به سمت راست افزایش می‌یابند، و تمام فرایندها دورهٔ تناوب خود را از برش زمانی صفر شروع می‌کنند. رنگ سایه‌های آبی و سفید که تناوبی به دنبال یکدیگر در نمودار زمانبندی آمده‌اند دوره تناوب فرایندها را نشان می‌دهند و ضرب‌العجل فرایندها برابر با زمان تغییر رنگ در نمودار زمانبندی می‌باشد. با مهلت‌های تغییر رنگ.
P2 اولین فرآیندی است که توسط EDF زمانبندی شده‌است، زیرا کمترین دوره تناوب را دارد و بنابراین نزدیکترین ضرب‌العجل را دارا می‌باشد. به همین ترتیب، زمانی که P2 تکمیل می‌شود، P1 و به دنبال آن P3 زمانبندی می‌شود.
در برش زمانی برابر با ۵، هر دو فرایند P2 و P3 ضرب‌العجل‌های برابر دارند، به همین علت لازم است ال قبل از برش زمانی برابر با ۱۰ اجرای آن‌ها تمام شود بنابراین EDF می‌تواند هر یک از آن‌ها را زمانبندی کند.

به‌کارگیری

به‌کارگیری به صورت زیر خواهد بود:
از آنجا که کوچکترین مضرب مشترک دوره تناوب ۴۰ است، الگوی زمانبندی می‌تواند در هر ۴۰ بار برش زمانی تکرار شود. اما، فقط ۳۷ از آن ۴۰ تا برش زمانی توسط P1، P2، یا P3 استفاده می‌شود. از آنجا که به‌کارگیری، ۹۲٫۵٪، بیش از ۱۰۰٪ نیست، سیستم قابلیت زمانبندی با الگوریتم EDF را دارد.

تعویض ضرب‌العجل

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

تحلیل ترافیک سنگین برای صف EDF با رفع

در تحلیل رفتار یک صف با ترافیک-سنگین در سروری که از الگوریتم زمانبندی EDF با سیاست رها کردن(انجام نشدن) استفاده می‌کند، فرایندها ضرب‌العجلی برای انجام کارهایشان دارند و سرور تنها تا زمانی که ضرب‌العجل آن‌ها سپری نشده به آن‌ها سرویس می‌دهد. میزان کار رها شده (انجام نشده)، به عنوان کار باقی‌مانده تعریف می‌شود که به علت سپری شدن ضرب‌العجل امکان سرویس دهی به آن وجود نداشته‌است. این میزان از کار رها شده (انجام نشده) معیاری مهم برای ارزیابی عملکرد می‌باشد.

مقایسه با زمانبندهای اولویت ثابت

عموماً پذیرفته شده‌است که پیاده‌سازی یک زمانبندی وقفه ناپذیر الویت ثابت (FPS) ساده‌تر از یک زمانبند اولویت پویا، مانند EDF است. با این حال، هنگام مقایسه حداکثر استفاده یک زمانبندی بهینه با الویت ثابت (با اولویت هر موضوعی که توسط برنامه‌ریزی نرخ مونوتونی ارائه شده‌است)، EDF می‌تواند به ۱۰۰٪ به‌کارگیری برسد، در حالی که از لحاظ تئوری حداکثر مقدار زمانبندی نرخ یکنواخت حدود ۶۹٪ می‌باشد.
توجه داشته باشید که EDF هیچگونه فرض خاصی را در مورد دوره تناوب وظایف تعریف نمی‌کند؛ بنابراین می‌توان از این الگوریتم هم برای زمانبندی وظایف تناوبی و هم برای زمانبندی وظایف غیر تناوبی استفاده کرد.