تعاونی نیرومندسازی تحقیقات جامع ترین مرجع دانلود تحقیق، مقاله، سمینار و پایان نامه
تا کنون الگوریتمهای بسیاری برای زمانبندی وظیفههای بیدرنگ در بسترهای سختافزاری مختلف ارایه شده است. در ادامه مروری بر اقسام الگوریتمهای زمانبندی داشته و ویژگیهای آنها را بیان میکنیم. سپس به ذکر متداولترین روشهای ارایه شده پرداخته، نقاط ضعف و قوت هر کدام را بررسی کرده و مورد کاربردشان را تشریح خواهیم کرد. همچنین سیاستهای زمانبندی برای بسترهای چندپردازنده را مرور خواهیم کرد. الگوریتمهای ابتکاری نیز به علت فایق آمدن بر معایب الگوریتمهای سنتی به ویژه محدودیتهای زمانی در مسایل زمانبندی جایگاه خاصی یافتهاند. بنابراین در پایان نیز گذری بر این دسته از الگوریتمها خواهیم داشت.
2-1: الگوریتم های زمانبندی
به منظور تضمین این که سیستم بیدرنگ اجرای وظیفهها را در ضربالاجل خود به پایان میرساند از الگوریتمهای زمانبندی استفاده میشود. یک الگوریتم زمانبندی مجموعهای از قوانین است که مشخص میکند در هر لحظه از زمان چه وظیفههایی باید اجرا شوند. به عبارت دیگر یک مسالهی زمانبندی ترتیبی را مشخص میکند که وظیفهها بر اساس آن اجرا شده تا محدودیتها یا شرایط خاصی برآورده گردد. به دلیل بحرانی بودن وظیفهها الگوریتمهای زمانبندی باید به موقع و قابل پیشبینی باشند.
در زمانبندی بیدرنگ باید اهداف زیر را مد نظر قرار داد [Mar 2006]، [Cot 2005]:
- تامین محدودیتها و شرایط زمانی سیستم
- جلوگیری از دسترسی همزمان به منابع و دستگاههای اشتراکی
- به دست آوردن بهرهوری بیشینه از منابع
- کاهش هزینههای تعویض متن[1] وظیفهها
- کاهش هزینهی ارتباط در سیستمهای بیدرنگ توزیع شده
- پوشش دادن قابلیت اعتماد و امنیت
الگوریتمهای زمانبندی باید بر مبنای ویژگیهای سیستم و وظیفههایی که در آن اجرا میشوند طراحی شوند. این ویژگیها عبارتند از:
- نرم یا سخت بودن وظیفههای بیدرنگ
- دورهای[2] یا غیردورهای بودن وظیفهها
- وجود یا عدم وجود انقطاعپذیری
- تکپردازنده یا چندپردازنده بودن سیستم
- ایستا یا پویا بودن اولویت وظیفهها
- مستقل یا وابسته بودن وظیفهها
الگوریتمهای زمانبندی سیستمهای بیدرنگ به سه دستهی ایستا[3]، پویا[4] و ترکیبی[5] تقسیم میشوند.
2-1-1: الگوریتم های ایستا
اگر بتوان کاربردهای بیدرنگ را به وظیفههایی با زمان اجرای معلوم تقسیم کرد زمانبندی را میتوان به صورت ایستا و در زمان کامپایل[6] انجام داد. زمانبندی ایستا دارای مزیت است که ترتیب اجرای وظیفهها به صورت غیربرخط[7] قابل تعیین شدن است. بنابراین سربار[8] زمانبندی میتواند خیلی کم و ناچیز باشد. پیادهسازی چنین الگوریتمهایی ساده است ولی مشکل آنها عدم انعطافپذیری است. آنها با وظیفههای دورهای به خوبی کار میکنند ولی وظیفههای غیردورهای را به خوبی مدیریت نمیکنند. عیب مهم دیگر زمانبندی ایستا بهرهوری پایین پردازنده است [Moh 2005].
الگوریتم RM[9] [Liu 1973] یک مثال مناسب از این دسته است. بیشترین اولویت را به وظیفههایی با بیشترین بسامد تخصیص میدهد. در هر لحظه زمانبند[10] وظیفهای را که دارای بالاترین اولویت است، برای اجرا انتخاب میکند.
2-1-2: الگوریتم های پویا
الگوریتمهای پویا به مقدار زیادی از منابع برخط[11] نیاز دارند. افزونگی منابع به آنها اجازه میدهد که خیلی انعطافپذیر باشند. چنین الگوریتمهایی برای شرایطی قابل استفاده هستند که اطلاع قبلی از مشخصات وظیفهها در دسترس نباشد. این الگوریتمها بر اساس وظیفههای موجود و اطلاعات جاری سیستم به هر وظیفه یک اولویت اختصاص داده و وظیفهای با بالاترین اولویت را انتخاب میکنند. ولی در هر لحظه امکان رسیدن وظیفههای جدید و تغییر شرایط وجود دارد و در نتیجه نیاز به زمانبندی مجدد وجود دارد [Sae 1996]. از آنجا که این الگوریتمها برخط اجرا میشوند باید کارآمد باشند زیرا پیچیدگی آنها بر کارایی کلی سیستم تاثیر میگذارد. مزیت آنها انعطافپذیری بالا و بهرهوری پردازنده[12] و عیب آنها سربار بیشتر نسبت به نوع ایستا است. دو دستهی عمده از الگوریتمهای پویا عبارتند از: مبتنی بر برنامهریزی[13] و بهترین تلاش[14].
در الگوریتمهای مبتنی بر برنامهریزی محدودیتهای زمانی همهی وظیفههایی که برای اجرا شدن انتخاب میشوند برآورده میشود. این الگوریتمها تلاش میکنند که زمان پاسخ و کارایی وظیفههای بیدرنگ نرم را بهبود بخشند در حالی که رساندن وظیفههای بیدرنگ سخت به ضربالاجلشان را تضمین میکنند. در این روش وظیفههای نرم فقط زمانی شانس اجرا شدن پیدا میکنند که پردازندهها کار دیگری نداشته باشند. EDF[15] و LLF[16] ([Che 2002]، [Cot 2002]) دو مثال مناسب از این دسته هستند.
الگوریتمهای بهترین تلاش در شرایط اضافه بار[17] سعی بر این دارند که حداکثر مزایا را برای وظیفهها فراهم کنند الگوریتمهای بهترین تلاش بسیاری وجود دارند که مهمترین آنها عبارتند از DASA[18] [Cla 1990] و LBESA[19] [Loc 1986] که معادل با EDF و LLF در شرایط کم بار هستند.
2-1-3: الگوریتم های ترکیبی
الگوریتمهای ترکیبی در واقع تلفیقی از دو نوع ایستا و پویا هستند. این نوع از الگوریتم از یک اولویت ترکیبی برای زمانبندی وظیفهها استفاده میکند. این اولویت دارای دو قسمت ایستا و پویا است. دلیل استفاده از این نوع الگوریتمها استفاده از مزایای هر دو نوع ایستا و پویا است. بنابراین این الگوریتمها از هر دو ویژگی سربار نسبتا کم و انعطافپذیری نسبتا بالا برخوردار هستند.
الگوریتمهای MFU[20] [Ste 1991] و MMUF[21] [Sal 2005] دو مثال از نوع ترکیبی هستند. در این الگوریتمها اولویت ایستا قبل از شروع سیستم و برای افزودن ویژگی قابل پیشبینی بودن اختصاص یافته و اولویت پویا نیز برای تعیین رفتار زمانبند در زمان اجرا به کار میرود.
فهرست مطالب
مروری بر الگوریتم های زمانبندی سنتی و الگوریتم های تکاملی 1
2-1: الگوریتم های زمانبندی 3
2-1-1: الگوریتم های ایستا 4
2-1-2: الگوریتم های پویا 4
2-1-3: الگوریتم های ترکیبی 6
2-2: زمانبندی در چندپردازنده ها 6
2-3: الگوریتم های ابتکاری 9
مراجع 14
فایل Word
18 صفحه
