باز کردن منو اصلی

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

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

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

که در این معادله بدترین حالت از زمان اجرا برای فرآیند و دوره تناوب زمان آماده شدن آن کارها(برابر با ضرب الاجل نسبی فرض می‌شود) می‌باشد.

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

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

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

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

محتویات

مثالویرایش

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

داده‌های زمانبندی فرآيندها
فرآیند زمان اجرا دوره تناوب
P1 1 8
P2 2 5
P3 4 10

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

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

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

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

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

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

به کارگیریویرایش

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

 

از آنجا که کوچکترین مضرب مشترک دوره تناوب 40 است، الگوی زمانبندی می‌تواند در هر 40 بار برش زمانی تکرار شود. اما، فقط 37 از آن 40 تا برش زمانی توسط P1، P2، یا P3 استفاده می‌شود. از آنجا که به کارگیری، 92.5٪، بیش از 100٪ نیست، سیستم قابلیت زمانبندی با الگوریتم EDF را دارد.

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

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

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

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

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

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

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

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

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

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

اگر چه پیاده‌سازی EDF در ;کرنل‌های بلادرنگ تجاری رایج نیست، در ادامه چندین مورد از کرنل‌های متن باز و بلادرنگی که 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-خوشه ای می‌باشد .

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

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

منابعویرایش

  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 سبک وزن با وراث آخرت