موضوع مقاله: زمان‌بندی اولویت با زودترین ضرب‌الاجل | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # زمان‌بندی اولویت با زودترین ضرب‌الاجل | مقدمه: اولویت با زودترین ضرب الاجل(EDF) یا کمترین زمان برای اجرا یک الگوریتم زمانبندی الویت پویا است که در سیستم عاملهای بی‌درنگ برای قراردادن فرایندها در صف الویت مورد استفاده قرار می‌گیرد. | ## بخش 1: زمان‌بندی اولویت با زودترین ضرب‌الاجل | زمانی که یک رویداد زمانبندی (تمام شدن یک وظیفه، آماده شدن یک وظیفه، غیره) رخ می‌دهد، صف برای پیدا کردن فرآیندی که نزدیکترین ضرب الاجل را دارد مورد جستجو قرار می‌گیرد. در صورتی که کارها وقفه پذیر بوده و تنها در یک پردازنده قابل اجرا باشند آنگاه الگوریتم EDF یک الگوریتم زمانبندی بهینه خواهد بود به این معنا که اگر مجموعه ای از کارهای مستقل، که با زمان آماده شدن، زمان اجرای مورد نیاز و ضرب الاجل آن‌ها مشخص شده باشند را بتوان (با هر الگوریتمی) به طوری زمانبندی کرد که تمام کارها قبل از ضرب الاجل‌ها آن‌ها اجرا شوند، آنگاه الگوریتم EDF این مجموعه از کارها را نیز به گونه ای زمانبندی می‌کند که ضرب الاجل آن‌ها رعایت شود. برای زمانبندی فرآیندهایی که ضرب الاجل آن‌ها برابر با دوره تناوب آن‌ها است، EDF کران بالای صد در صد برای بهره‌وری دارد؛ بنابراین تست زمانبندی برای EDF به صورت زیر خواهد بود: که در این معادله بدترین حالت از زمان اجرا برای فرایند و دوره تناوب زمان آماده شدن آن کارها (برابر با ضرب الاجل نسبی فرض می‌شود) می‌باشد. به همین علت الگوریتم زمانبندی EDF تضمین می‌کند در صورتی که بهره‌وری کل CPU از ۱۰۰درصد بیشتر نباشد آنگاه تمام ضرب الاجل‌ها رعایت می‌شوند. در مقایسه با تکینک‌های زمانبندی الویت ثابت مانند زمانبندی با نرخ یکنواخت، الگوریتم EDF می‌تواند تمام ضرب الاجل‌ها در سیستم را در بارگیری بالاتری تضمین کند. با این حال، هنگامی که سیستم بیش از حد بارگیری شود، مجموعه ای از فرایندها که قبل از ضرب الاجل خود به اتمام نمی‌رسند، به‌طور غیرقابل پیش‌بینی بزرگ می‌باشد (که این تعداد تابعی از ضرب الاجل‌های دقیق (و نه نسبی) و زمان رخ دادن بارگیری بیش از حد می‌باشد). همچنین این الگوریتم به سختی در سخت‌افزار پیاده‌سازی می‌شود و یک مسئله دشوار در این الگوریتم نمایش ضرب الاجل‌ها در محدوده‌های مختلف می‌باشد (ضرب الاجل‌ها نمی‌توانند دقیق تر از دقتی باشند که برای کلاک در زمانبندی در نظر گرفته شده‌است). اگر از یک محاسبات مدولار برای محاسبه ضرب الاجل‌های بعدی نسبت به زمان حال استفاده شود، بخش ذخیره‌ساز ضرب الاجل نسبی بعدی باید حداقل مقدار ("مدت زمان" *۲ + "اکنون") را اصلاح کند. منظور از "مدت زمان"، طولانی‌ترین زمان مورد انتظار برای اجرا است؛ بنابراین EDF به‌طور معمول در سیستم‌های کامپیوتری بی‌درنگ صنعتی دیده نمی‌شود. در مقابل، اکثر سیستم‌های کامپیوتری بی‌درنگ از الگوریتم‌های زمانبندی الویت ثابت (معمولا زمانبندی نرخ یکنواخت) استفاده می‌کنند. با اولویت‌های ثابت، قابل پیش‌بینی است که شرایط بارگیری منجر می‌شود تا فرآیندهای با الویت کمتر قبل از ضرب الاجل خود به پایان نرسند و در حالی که فرآیندهای با الویت بالاتر همچنان بتوانند تا قبل از ضرب الاجل خود به پایان برسند. در الگوریتم EDF محاسبه بدترین حالت زمان پاسخگویی برای فرایندها امکان‌پذیر می‌باشد؛ این مسئله برای مدیریت کردن نوع‌های دیگری از فرایندها (غیر از فرآیندهای تناوبی مانند غیر تناوبی و موردی) و استفاده از سرورها برای تنظیم بارگیری مفید می‌باشد. مثال ۳ فرایند تناوبی وقفه ناپذیر که روی یک پردازنده زمانبندی شده‌اند را در نظر بگیرید. در جدول زیر زمان‌های اجرا و دوره‌های تناوب آن‌ها آورده شده‌است: + داده‌های زمانبندی فرایندها فرایند زمان اجرا دوره تناوب P1 ۱ ۸ P2 ۲ ۵ P3 ۴ ۱۰ در این مثال، واحد زمان می‌تواند به عنوان زمان برش زمان برنامه ریزی شده در نظر گرفته شود. | ## بخش 2: زمان‌بندی اولویت با زودترین ضرب‌الاجل | منظور از ضرب الاجل این است که اجرای هر فرایند باید در دورهٔ تناوب خودش به اتمام برسد. در نمودار زمانبندی، ستون‌ها برش زمانی را نشان می‌دهند که با حرکت به سمت راست افزایش می‌یابند، و تمام فرایندها دورهٔ تناوب خود را از برش زمانی صفر شروع می‌کنند. رنگ سایه‌های آبی و سفید که تناوبی به دنبال یکدیگر در نمودار زمانبندی آمده‌اند دوره تناوب فرایندها را نشان می‌دهند و ضرب‌الاجل فرایندها برابر با زمان تغییر رنگ در نمودار زمانبندی می‌باشد. P2 اولین فرآیندی است که توسط EDF زمانبندی شده‌است، زیرا کمترین دوره تناوب را دارد و بنابراین نزدیکترین ضرب‌الاجل را دارا می‌باشد. در برش زمانی برابر با ۵، هر دو فرایند P2 و P3 ضرب‌العجل‌های برابر دارند، به همین علت لازم است ال قبل از برش زمانی برابر با ۱۰ اجرای آن‌ها تمام شود بنابراین EDF می‌تواند هر یک از آن‌ها را زمانبندی کند. به‌کارگیری به‌کارگیری به صورت زیر خواهد بود: از آنجا که کوچکترین مضرب مشترک دوره تناوب ۴۰ است، الگوی زمانبندی می‌تواند در هر ۴۰ بار برش زمانی تکرار شود. از آنجا که به‌کارگیری، ۹۲٫۵٪، بیش از ۱۰۰٪ نیست، سیستم قابلیت زمانبندی با الگوریتم EDF را دارد. یک فرایند ممکن است از یک منبع مشترک در یک بخش بحرانی (اجرای پردازه‌ها در بخش‌های بحرانی وقفه ناپذیر است) استفاده کند تا در صورت وجود فرآیندی با ضرب‌الاجل زودتر، مانع از ایجاد وقفه و زمانبندی مجدد در آن شود. در چنین شرایطی، برای زمانبند مهم است که به فرایند در حال اجرا زودترین ضرب‌الاجل را اختصاص داده و در نتیجه این فرایند در مقابل دیگر فرآیندهای منتظر پردازنده، الویت بیشتری پیدا می‌کند. در غیر این صورت به فرآیندهای با ضرب‌الاجل زودتر پردازنده داده نمی‌شود و ممکن است تا قبل از ضرب‌الاجل خود نتوانند کار خود را اجرا کنند. این مسئله به خصوص اهمیت بیشتری پیدا می‌کند که فرایند در حال اجرا در بخش بحرانی، زمان بیشتری برای اجرا و خروج از بخش بحرانی داشته باشد، که در این صورت در آزاد سازی منبع مشترک تأخیر ایجاد خواهد کرد. اما فرایند همچنان می‌تواند به نفع فرآیندهای دیگر که ضرب‌الاجل زودتری داشته اما منبع حیاتی را به اشتراک نمی‌گذارند، وقفه پذیر باشد. این خطر در تعویض ضرب‌العجل‌ها مشابه است با معکوس کردن الویت‌ها وقتی از زمانبندی وقفه پذیر الویت ثابت استفاده می‌کنیم. برای سرعت بخشیدن در یافتن زودترین ضرب‌الاجل در یک صف آماده، لازم است تا عناصر در صف براساس ضرب‌الاجل آن‌ها مرتب شود. | ## بخش 3: زمان‌بندی اولویت با زودترین ضرب‌الاجل | زمانی که یک فرایند یا یک فرایند تناوبی با ضرب‌الاجل جدیدی وارد شود، قبل از اولین فرایند با ضرب‌الاجل دیرتر در صف قرار می‌گیرد. تحلیل ترافیک سنگین برای صف EDF با رفع در تحلیل رفتار یک صف با ترافیک-سنگین در سروری که از الگوریتم زمانبندی EDF با سیاست رها کردن(انجام نشدن) استفاده می‌کند، فرایندها ضرب‌العجلی برای انجام کارهایشان دارند و سرور تنها تا زمانی که ضرب‌الاجل آن‌ها سپری نشده به آن‌ها سرویس می‌دهد. میزان کار رها شده (انجام نشده)، به عنوان کار باقی‌مانده تعریف می‌شود که به علت سپری شدن ضرب‌الاجل امکان سرویس دهی به آن وجود نداشته‌است. مقایسه با زمانبندهای اولویت ثابت عموماً پذیرفته شده‌است که پیاده‌سازی یک زمانبندی وقفه ناپذیر الویت ثابت (FPS) ساده‌تر از یک زمانبند اولویت پویا، مانند EDF است. با این حال، هنگام مقایسه حداکثر استفاده یک زمانبندی بهینه با الویت ثابت (با اولویت هر موضوعی که توسط برنامه‌ریزی نرخ مونوتونی ارائه شده‌است)، EDF می‌تواند به ۱۰۰٪ به‌کارگیری برسد، در حالی که از لحاظ تئوری حداکثر مقدار زمانبندی نرخ یکنواخت حدود ۶۹٪ می‌باشد. توجه داشته باشید که EDF هیچگونه فرض خاصی را در مورد دوره تناوب وظایف تعریف نمی‌کند؛ بنابراین می‌توان از این الگوریتم هم برای زمانبندی وظایف تناوبی و هم برای زمانبندی وظایف غیر تناوبی استفاده کرد. MaRTE OS این سیستم عامل به عنوان زمان اجرا برای برنامه‌هایی که با زبان برنامه‌نویسی ایدا نوشته شده‌اند را اجرا می‌کند. پروژه AQuoSA تغییری در هسته لینوکس ایجاد کرده‌است و توانمندی زمانبند فرایندها را با اضافه کردن الگوریتم EDF و با توجه به توانایی‌هایی که این الگوریتم دارد، افزایش داده‌است. تنظیم وقت یک زمان‌بندی نمی‌تواند مانند سیستم‌های عامل بی‌درنگ سخت، دقیق باشد اما به اندازه کافی دقیق است به طوری که می‌تواند به میزان قابل توجهی قابل پیش‌بینی بودن را بالا برده و نیازمندی‌های برنامه‌های چند رسانه ای بی‌درنگ را برطرف کند. AQuoSA یکی از چندین پروژه است که با استفاده از یک مدل مناسب کنترل دسترسی، قابلیت‌های برنامه‌ریزی بلادرنگی را به کاربران غیرمجاز بر روی سیستم در یک روش کنترل شده فراهم می‌کند. زمانبند بی‌درنگ این زمانبند در حین پروژه IRMOS اروپا معرفی شده‌است که یک زمانبند بی‌درنگ چند پردازنده ایی برای کرنل لینوکس است، به ویژه برای جداسازی زمانی و ارائه گارانتی QoS برای اجزای نرم‌افزاری چند رشته‌ای پیچیده و تمامی ماشین‌های مجازی مناسب می‌باشد. برای مثال، هنگام استفاده از لینوکس به عنوان سیستم عامل میزبان و KVM به عنوان ناظر ماشین مجازی، IRMOS می‌تواند برای تضمین کردن زمانبندی VMهای جدا از هم و در عین حال ایزوله کردن عملکرد آنها برای اجتناب از تداخل زمانی ناخواسته، مورد استفاده قرار گیرد. با این حال، رزروها چند پردازنده ای هستند و برای زمانبندی رشته ها (فرایندها ی and/or)در لایه‌های پایین‌تری، FP عمومی بر روی سیستم‌های چندپردازنده ای به هریک از رزروهای EDF بالاتر پیوست می‌شود. | ## جمع‌بندی | برای یک مرور کلی و یادگیری بیشتر این مبحت می‌توانید مقاله ای در سایت lwn.net را مشاهده کنید.