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

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

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

برای زمانبندی فرآیندهایی که ضرب الاجل آن‌ها برابر با دوره تناوب آن‌ها است، EDF کران بالای صد در صد برای بهره‌وری دارد؛ بنابراین تست زمانبندی برای EDF به صورت زیر خواهد بود:

${\displaystyle U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leq 1,}$

که در این معادله ${\displaystyle \left\{C_{i}\right\}}$ بدترین حالت از زمان اجرا برای ${\displaystyle n}$ فرایند و ${\displaystyle \left\{T_{i}\right\}}$ دوره تناوب زمان آماده شدن آن کارها (برابر با ضرب الاجل نسبی فرض می‌شود) می‌باشد.

به همین علت الگوریتم زمانبندی EDF تضمین می‌کند در صورتی که بهره‌وری کل CPU از ۱۰۰درصد بیشتر نباشد آنگاه تمام ضرب الاجل‌ها رعایت می‌شوند. در مقایسه با تکینک‌های زمانبندی الویت ثابت مانند زمانبندی با نرخ یکنواخت، الگوریتم EDF می‌تواند تمام ضرب الاجل‌ها در سیستم را در بارگیری بالاتری تضمین کند.

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

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

یک بخش مهمی از مطالعات مربوط به زمانبندی EDF در محاسبات بی‌درنگ می‌باشد. در الگوریتم EDF محاسبه بدترین حالت زمان پاسخگویی برای فرایندها امکان‌پذیر می‌باشد؛ این مسئله برای مدیریت کردن نوع‌های دیگری از فرایندها (غیر از فرآیندهای تناوبی مانند غیر تناوبی و موردی) و استفاده از سرورها برای تنظیم بارگیری مفید می‌باشد.

مثال

۳ فرایند تناوبی وقفه ناپذیر که روی یک پردازنده زمانبندی شده‌اند را در نظر بگیرید. در جدول زیر زمان‌های اجرا و دوره‌های تناوب آن‌ها آورده شده‌است:

داده‌های زمانبندی فرایندها

فرایند	زمان اجرا	دوره تناوب
P1	۱	۸
P2	۲	۵
P3	۴	۱۰

در این مثال، واحد زمان می‌تواند به عنوان زمان برش زمان برنامه ریزی شده در نظر گرفته شود. منظور از ضرب الاجل این است که اجرای هر فرایند باید در دورهٔ تناوب خودش به اتمام برسد.

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

نمودار زمان‌بندی برای مثال بخشی از یک زمانبندی ممکن را نشان می‌دهد.

در نمودار زمانبندی، ستون‌ها برش زمانی را نشان می‌دهند که با حرکت به سمت راست افزایش می‌یابند، و تمام فرایندها دورهٔ تناوب خود را از برش زمانی صفر شروع می‌کنند. رنگ سایه‌های آبی و سفید که تناوبی به دنبال یکدیگر در نمودار زمانبندی آمده‌اند دوره تناوب فرایندها را نشان می‌دهند و ضرب‌الاجل فرایندها برابر با زمان تغییر رنگ در نمودار زمانبندی می‌باشد. با مهلت‌های تغییر رنگ.

P2 اولین فرآیندی است که توسط EDF زمانبندی شده‌است، زیرا کمترین دوره تناوب را دارد و بنابراین نزدیکترین ضرب‌الاجل را دارا می‌باشد. به همین ترتیب، زمانی که P2 تکمیل می‌شود، P1 و به دنبال آن P3 زمانبندی می‌شود.

در برش زمانی برابر با ۵، هر دو فرایند P2 و P3 ضرب‌العجل‌های برابر دارند، به همین علت لازم است ال قبل از برش زمانی برابر با ۱۰ اجرای آن‌ها تمام شود بنابراین EDF می‌تواند هر یک از آن‌ها را زمانبندی کند.

به‌کارگیری

به‌کارگیری به صورت زیر خواهد بود:

${\displaystyle \left({\frac {1}{8}}+{\frac {2}{5}}+{\frac {4}{10}}\right)=\left({\frac {37}{40}}\right)=0.925={\mathbf {92.5\%} }}$

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

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

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

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

برای سرعت بخشیدن در یافتن زودترین ضرب‌الاجل در یک صف آماده، لازم است تا عناصر در صف براساس ضرب‌الاجل آن‌ها مرتب شود. زمانی که یک فرایند یا یک فرایند تناوبی با ضرب‌الاجل جدیدی وارد شود، قبل از اولین فرایند با ضرب‌الاجل دیرتر در صف قرار می‌گیرد. با این روش، فرآیندهای با ضرب‌العجل‌های زودتر همیشه در ابتدای صف قرار می‌گیرند.

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

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

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

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

توجه داشته باشید که EDF هیچگونه فرض خاصی را در مورد دوره تناوب وظایف تعریف نمی‌کند؛ بنابراین می‌توان از این الگوریتم هم برای زمانبندی وظایف تناوبی و هم برای زمانبندی وظایف غیر تناوبی استفاده کرد.^[۱]

کرنل‌هایی که برنامه‌ریزی EDF را پیاده‌سازی می‌کنند

اگر چه پیاده‌سازی EDF در؛ کرنل‌های بی‌درنگ تجاری رایج نیست، در ادامه چندین مورد از کرنل‌های متن باز و بلادرنگی که EDF را پیاده‌سازی و اجرا کرده‌اند آورده شده‌است:

• SHARK(شارک)، سیستم عامل‌های بی‌درنگ نسخه‌های مختلف زمانبند EDF و الگوریتم‌های زمان‌بندی رزرو منابع را پیاده‌سازی و اجرا می‌کنند.
• ERIKA Enterprise، نسخهٔ شرکتی اریکا حالت بهینه ایی از الگوریتم EDF را برای میکروکنترلرهای کوچک با رابط برنامه‌نویسی کاربردی مشابه با رابط برنامه‌نویسی کاربردی OSEK پیاده‌سازی کرده‌است.
• کرنل Everyman این کرنل هر دو زمانبند EDF یا ضرب‌الاجل یکنواخت را با توجه به تنظیمات کاربر اجرا می‌کند.
• MaRTE OS این سیستم عامل به عنوان زمان اجرا برای برنامه‌هایی که با زبان برنامه‌نویسی ایدا نوشته شده‌اند را اجرا می‌کند.
• پروژه AQuoSA تغییری در هسته لینوکس ایجاد کرده‌است و توانمندی زمانبند فرایندها را با اضافه کردن الگوریتم EDF و با توجه به توانایی‌هایی که این الگوریتم دارد، افزایش داده‌است. تنظیم وقت یک زمان‌بندی نمی‌تواند مانند سیستم‌های عامل بی‌درنگ سخت، دقیق باشد اما به اندازه کافی دقیق است به طوری که می‌تواند به میزان قابل توجهی قابل پیش‌بینی بودن را بالا برده و نیازمندی‌های برنامه‌های چند رسانه ای بی‌درنگ را برطرف کند. AQuoSA یکی از چندین پروژه است که با استفاده از یک مدل مناسب کنترل دسترسی، قابلیت‌های برنامه‌ریزی بلادرنگی را به کاربران غیرمجاز بر روی سیستم در یک روش کنترل شده فراهم می‌کند.^[۲]
• کرنل لینوکس الگوریتم زمانبندی EDF را با نام SCHED DEADLINE پیاده‌سازی کرده‌است که از زمان انتشار نسخه ۳٫۱۴ سیستم عامل در دسترس است.
• زمانبند بی‌درنگ این زمانبند در حین پروژه IRMOS بایگانی‌شده در ۲۰۱۸-۱۰-۱۰ توسط Wayback Machine اروپا معرفی شده‌است که یک زمانبند بی‌درنگ چند پردازنده ایی برای کرنل لینوکس است، به ویژه برای جداسازی زمانی و ارائه گارانتی QoS برای اجزای نرم‌افزاری چند رشته‌ای پیچیده و تمامی ماشین‌های مجازی مناسب می‌باشد. برای مثال، هنگام استفاده از لینوکس به عنوان سیستم عامل میزبان و KVM به عنوان ناظر ماشین مجازی، IRMOS می‌تواند برای تضمین کردن زمانبندی VMهای جدا از هم و در عین حال ایزوله کردن عملکرد آنها برای اجتناب از تداخل زمانی ناخواسته، مورد استفاده قرار گیرد. IRMOS دارای یک برنامه‌ریز سلسله مراتبی EDF / FP می‌باشد. در سطح بالاتر، یک زمانبند EDF جزئی بر روی پردازنده‌های موجود وجود دارد. با این حال، رزروها چند پردازنده ای هستند و برای زمانبندی رشته ها (فرایندها ی and/or)در لایه‌های پایین‌تری، FP عمومی بر روی سیستم‌های چندپردازنده ای به هریک از رزروهای EDF بالاتر پیوست می‌شود. برای یک مرور کلی و یادگیری بیشتر این مبحت می‌توانید مقاله ای در سایت lwn.net را مشاهده کنید.
• در حال حاضر Xen یک زمانبند EDF دارد. کتابچه راهنما شامل یک توضیح کوتاه است.
• سیستم عامل Plan 9 از آزمایشگاه‌های Bell دارای EDFI، یک پروتکل زمان‌بندی زمانبندی سبک‌وزن است که ادغام EDF را با ارجاع مهلت به منابع مشترک به اشتراک می‌گذارد.^[۳]
• RTEMS: زمانبند EDF در نسخه ۴٫۱۱ در دسترس خواهد بود. RTEMS SuperCore
• Litmus-RT یک توسیع بی‌درنگ از کرنل لینوکس با تمرکز بر زمانبندی و هماهنگ سازی بی‌درنگ چند پردازنده‌ها است. مجموعهٔ الگوریتم‌های بی‌درنگ آن شامل زمانبندهای EDF-جزئی، EDF-کلی و EDF-خوشه ای می‌باشد.

جستارهای وابسته

• زمانبندی اولویت پویا

منابع

1. Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (Third ed.), New York, NY: Springer, p. 100
2. Cucinotta, Tommaso (April 2008). "Access Control for Adaptive Reservations on Multi-User Systems". 14th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2008).
3. پیر جی. جانسن، صپه J. مولنر، پل جی. م.، هانس شولتن. برنامه‌ریزی EDF سبک‌وزن با وراث آخرت