دوستان عزیز برای پیدا کردن سریع مطالب مورد نظر خود، می توانید از قسمت جستجوی سریع در سایت، یک یا چند کلمه کلیدی مورد نظر خود را جستجو نمایید.
یا اینکه بر روی دو آیکون سبز رنگ "طبقه بندی موضوعات" یا "جستجوی کلمات کلیدی" در سمت راست و چپ موجود در بالای سایت کلیک نمایید...
در صورت بروز مشکل در پرداخت الکترونیکی؛ میتونید ایمیلی ، پیامکی، تلفنی یا تلگرامی بگید تا فایلتون براتون ارسال بشه.
مروری بر الگوریتم های زمانبندی سنتی و الگوریتم های تکاملی | تعاونی نیرومندسازی تحقیقات
طبقه بندی موضوعات
جستجوی کلمات کلیدی
شنبه , ۱۳ آذر ۱۳۹۵
آخرین مطالب
خانه -> کامپایلر -> مروری بر الگوریتم های زمانبندی سنتی و الگوریتم های تکاملی

مروری بر الگوریتم های زمانبندی سنتی و الگوریتم های تکاملی

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

۲-۱: الگوریتم های زمانبندی

به منظور تضمین این که سیستم بی­درنگ اجرای وظیفه­ها را در ضرب­الاجل خود به پایان می­رساند از الگوریتم­های زمانبندی استفاده می­شود. یک الگوریتم زمانبندی مجموعه­ای از قوانین است که مشخص می­کند در هر لحظه از زمان چه وظیفه­هایی باید اجرا شوند. به عبارت دیگر یک مساله­ی زمانبندی ترتیبی را مشخص می­کند که وظیفه­ها بر اساس آن اجرا شده تا محدودیت­ها یا شرایط خاصی برآورده گردد. به دلیل بحرانی بودن وظیفه­ها الگوریتم­های زمانبندی باید به موقع و قابل پیش­بینی باشند.

در زمانبندی بی­درنگ باید اهداف زیر را مد نظر قرار داد [Mar 2006]، [Cot 2005]:

  • تامین محدودیت­ها و شرایط زمانی سیستم
  • جلوگیری از دسترسی همزمان به منابع و دستگاه­های اشتراکی
  • به دست آوردن بهره­وری بیشینه از منابع
  • کاهش هزینه­های تعویض متن[۱] وظیفه­ها
  • کاهش هزینه­ی ارتباط در سیستم­های بی­درنگ توزیع شده
  • پوشش دادن قابلیت اعتماد و امنیت

الگوریتم­های زمانبندی باید بر مبنای ویژگی­های سیستم و وظیفه­هایی که در آن اجرا می­شوند طراحی شوند. این ویژگی­ها عبارتند از:

  • نرم یا سخت بودن وظیفه­های بی­درنگ
  • دوره­ای[۲] یا غیردوره­ای بودن وظیفه­ها
  • وجود یا عدم وجود انقطاع­پذیری
  • تک­پردازنده یا چندپردازنده بودن سیستم
  • ایستا یا پویا بودن اولویت وظیفه­ها
  • مستقل یا وابسته بودن وظیفه­ها

الگوریتم­های زمانبندی سیستم­های بی­درنگ به سه دسته­ی ایستا[۳]، پویا[۴] و ترکیبی[۵] تقسیم می­شوند.

۲-۱-۱: الگوریتم های ایستا

اگر بتوان کاربردهای بی­درنگ را به وظیفه­هایی با زمان اجرای معلوم تقسیم کرد زمانبندی را می­توان به صورت ایستا و در زمان کامپایل[۶] انجام داد. زمانبندی ایستا دارای مزیت است که ترتیب اجرای وظیفه­ها به صورت غیربرخط[۷] قابل تعیین شدن است. بنابراین سربار[۸] زمانبندی می­تواند خیلی کم و ناچیز باشد. پیاده­سازی چنین الگوریتم­هایی ساده است ولی مشکل آنها عدم انعطاف­پذیری است. آنها با وظیفه­های دوره­ای به خوبی کار می­کنند ولی وظیفه­های غیردوره­ای را به خوبی مدیریت نمی­کنند. عیب مهم دیگر زمانبندی ایستا بهره­وری پایین پردازنده است [Moh 2005].

الگوریتم RM[9] [Liu 1973] یک مثال مناسب از این دسته است. بیشترین اولویت را به وظیفه­هایی با بیشترین بسامد تخصیص می­دهد. در هر لحظه زمانبند[۱۰] وظیفه­ای را که دارای بالاترین اولویت است، برای اجرا انتخاب می­کند.

۲-۱-۲: الگوریتم های پویا

الگوریتم­های پویا به مقدار زیادی از منابع برخط[۱۱] نیاز دارند. افزونگی منابع به آنها اجازه می­دهد که خیلی انعطاف­پذیر باشند. چنین الگوریتم­هایی برای شرایطی قابل استفاده هستند که اطلاع قبلی از مشخصات وظیفه­ها در دسترس نباشد. این الگوریتم­ها بر اساس وظیفه­های موجود و اطلاعات جاری سیستم به هر وظیفه­ یک اولویت اختصاص داده و وظیفه­ای با بالاترین اولویت را انتخاب می­کنند. ولی در هر لحظه امکان رسیدن وظیفه­های جدید و تغییر شرایط وجود دارد و در نتیجه نیاز به زمانبندی مجدد وجود دارد [Sae 1996]. از آن­جا که این الگوریتم­ها برخط اجرا می­شوند باید کارآمد باشند زیرا پیچیدگی آنها بر کارایی کلی سیستم تاثیر می­گذارد. مزیت آنها انعطاف­پذیری بالا و بهره­وری پردازنده[۱۲] و عیب آنها سربار بیشتر نسبت به نوع ایستا است. دو دسته­ی عمده از الگوریتم­های پویا عبارتند از: مبتنی بر برنامه­ریزی[۱۳] و بهترین تلاش[۱۴].

در الگوریتم­های مبتنی بر برنامه­ریزی محدودیت­های زمانی همه­ی وظیفه­هایی که برای اجرا شدن انتخاب می­شوند برآورده می­شود. این الگوریتم­ها تلاش می­کنند که زمان پاسخ و کارایی وظیفه­های بی­درنگ نرم را بهبود بخشند در حالی که رساندن وظیفه­های بی­درنگ سخت به ضرب­الاجل­شان را تضمین می­کنند. در این روش وظیفه­های نرم فقط زمانی شانس اجرا شدن پیدا می­کنند که پردازنده­ها کار دیگری نداشته باشند. EDF[15] و LLF[16] ([Che 2002]، [Cot 2002]) دو مثال مناسب از این دسته هستند.

الگوریتم­های بهترین تلاش در شرایط اضافه بار[۱۷] سعی بر این دارند که حداکثر مزایا را برای وظیفه­ها فراهم کنند الگوریتم­های بهترین تلاش بسیاری وجود دارند که مهم­ترین آنها عبارتند از DASA[18] [Cla 1990] و LBESA[19] [Loc 1986] که معادل با EDF و LLF در شرایط کم بار هستند.

۲-۱-۳: الگوریتم های ترکیبی

الگوریتم­های ترکیبی در واقع تلفیقی از دو نوع ایستا و پویا هستند. این نوع از الگوریتم­ از یک اولویت ترکیبی برای زمانبندی وظیفه­ها استفاده می­کند. این اولویت دارای دو قسمت ایستا و پویا است. دلیل استفاده از این نوع الگوریتم­ها استفاده از مزایای هر دو نوع ایستا و پویا است. بنابراین این الگوریتم­ها از هر دو ویژگی سربار نسبتا کم و انعطاف­پذیری نسبتا بالا برخوردار هستند.

الگوریتم­های MFU[20] [Ste 1991] و MMUF[21] [Sal 2005] دو مثال از نوع ترکیبی هستند. در این الگوریتم­ها اولویت ایستا قبل از شروع سیستم و برای افزودن ویژگی قابل پیش­بینی بودن اختصاص یافته و اولویت پویا نیز برای تعیین رفتار زمانبند در زمان اجرا به کار می­رود.

 

فهرست مطالب
مروری بر الگوریتم های زمانبندی سنتی و الگوریتم های تکاملی ۱
۲-۱: الگوریتم های زمانبندی ۳
۲-۱-۱: الگوریتم های ایستا ۴
۲-۱-۲: الگوریتم های پویا ۴
۲-۱-۳: الگوریتم های ترکیبی ۶
۲-۲: زمانبندی در چندپردازنده ها ۶
۲-۳: الگوریتم های ابتکاری ۹
مراجع ۱۴

فایل Word

18 صفحه

کاربر گرامی

برای دانلود فایل های مورد نظرتان بایستی بر روی دکمه "افزودن به سبد خرید" کلیک نمایید .

پس از چند ثانیه ، فایل مورد نظر شما به سبد خریدتان اضافه گردیده و این دکمه تبدیل به دکمه "پرداخت" خواهد شد.

با کلیلک بر روی دکمه "پرداخت" ، وارد صفحه پرداخت خواهید شد .

با وارد کردن اطلاعات و ایمیل خود ، فایل مورد نظر به ایمیل شما ارسال گردیده و همچنین لینک دانلود فایل بلافاصله برایتان به نمایش درخواهد آمد.

– قابل پرداخت با تمام کارتهای بانکی + رمز دوم

– پشتیبانی سایت ۰۹۳۵۹۵۲۹۰۵۸ – Info@tnt3.ir – universitydatainfo@yahoo.com




سفارش ترجمه متون عمومی و تخصصیفروشگاه اینترنتی کتاب - خرید آنلاین کتاب - دانلود کتاب الکترونیکی

جوابی بنویسید

ایمیل شما نشر نخواهد شد

18 − شانزده =

شما می‌توانید از این دستورات HTML استفاده کنید: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


This site is using the Seo Wizard plugin by http://seo.uk.net/