چکیده
پیاده سازی الگوریتم FLB
گرید محاسباتی مجموعه ای از منابع نا همگن و پویا که بوسیله یک شبکه به یکدیگر متصل می شوندو کاربران زیادی در مکان های مختلف آنها را به اشتراک می گذارند.اغلب برنامه های کاربردی بوسیله گراف جهت دار بدون سیکل خلاصه می شوندکه رئوس آن کارها و یالهای آن ارتباطات بین کارها را نشان می دهد. که در آن کارها وابسته هستند و بر اساس اولویت باید اجرا شوند به این معنی که در گراف تا والد یک کار انجام نشود فرزند یا فرزندان نباید انجام شوند.
برای اینکه تمام این اصول رعایت شود و از منابع به صورت بهینه استفاده گردد از الگوریتم های زمانبندی استفاده می کنیم.
در اینجا ما ابتدا به بررسی مفهوم گرید وفواید آن وسپس انواع زمانبندی در سیستم های توزیع شده و بررسی برخی از الگوریتم های زمانبندی در کارهای مستقل و وابسته می پردازیم و روشهای زمانبندی گراف برنامه وبعضی از الگوریتم های آنها در محیطهای ناهمگن وهمگن را معرفی می کنیم.سپس الگوریتمFLB راتشریح کردوشبیه ازهای گرید را بررسی می کنیم.
قبل از ابداع کامپیوترهای شخصی، عملا سیستم های توزیع شده ای وجود نداشته است . در آن دوران ، استفاده از کامپیوتر، شامل نشستن پشت یک ترمینال و برقراری ارتباط با یک سیستم بزرگ بود. با اینکه ترمینال ها در چندین ساختمان و یا حتی محل فیزیکی قرار می گرفتند ، ولی عملا یک کامپیوتر مرکزی وجود داشت که مسئولیت انجام تمامی پردازش ها و ذخیره سازی داده ها را برعهده می گرفت .
Mainfram معایب
•هزینه سیستم های Mainfarme . یکی از اولین دلایل مهم ، هزینه های بالای سیستم های Mainframe است . این مسئله از دو زاویه متفاوت قابل بررسی است : هزینه بالای سرمایه گذاری اولیه که بسیاری از سازمان ها و موسسات توان مالی آن را ندارند و دوم اینکه در این مدل ، دارای صرفا" یک نقطه آسیب پذیر با ریسک بالا می باشیم .
•مالکیت اختصاصی داده ها. یکی از فاکتورهای مهم دیگر، سیاست های مربوط به مالکیت داده ها است . سازمان ها و موسسات که دارای داده های اختصاصی خود می باشند، علاقه مند به واگذاری مسئولیت مدیریت داده های مربوطه ، به سایر مکان های فیزیکی نمی باشند .
•امنیت . یکی دیگر از فاکتورهای مهم در این زمینه موضوع امنیت است . برای یک سازمان ، اولا" دستیابی به اغلب داده های آن می بایست بسادگی محقق گردد و ثانیا" داده ها ی حساس موجود در سازمان می بایست از بعد امنیتی، ایمن نگهداری گردند . تامین دو خواسته فوق ( رویکردهای رقابتی و رویکردهای امنیتی ) با جدا سازی فیزیکی داده از یکدیگر محقق خواهد شد ( انباشت داده ها، با نگرش های متفاوت در رابطه با سرعت در دستیابی و ایمن در ذخیره سازی ، ضرورت وجود برنامه های توزیع شده را بخوبی نمایان می سازد )
مسائل فوق، ضرورت حرکت بسمت ایجاد یک الگوی جدید بمنظور طراحی برنامه های کامپیوتری را مطرح و بر همین اساس نسل جدیدی از برنامه های کامپیوتری با عنوان " برنامه های توزیع شده" در عرصه نرم افزار بوجود آمد.که این برنامه ها به سیستم های توزیع شده نیاز دارد.
یک برنامه توزیع شده، برنامه ای است که پتانسیل های پردازشی آن ممکن است توسط چندین کامپیوتر فیزیکی تامین و داده های آن در چندین محل فیزیکی، مستقر شده باشد .
یک سیستم توزیع شده مجموعه ای از کامپیوتر هاست که دارای منابع اجرایی مختلف و زیادی هستند.
مفهوم گرید 1-1
در گرید هر شخصی می تواند به راحتی وارد یک شبکه شود و از توان محاسباتی موجود در شبکه استفاده کند.در شیوه های نوین به جای استفاده از رایانه های اختصاصی برای حل مسائل بزرگ ، با استفاده از رایانه های موجود پراکنده که از همه توان محاسباتی خود استفاده نمی کنند، سعی می شود با جمع آوری این توانهای پراکنده که اغلب بی استفاده می مانند، کارهای خود را انجام دهند. این منابع محاسباتی اگرچه اغلب قدرت و هماهنگی رایانه های اختصاصی را ندارند، اما تعداد زیادی از آنها به وفور در مراکز عمومی از قبیل دانشگاه ها، اداره ها، کتابخانه ها و غیره و حتی در منازلی که اتصال قوی به اینترنت دارند یافت می شوند و این موجب می شود که توان محاسباتی آن در مجموع بسیار بالا باشد و در عین حال هزینه آن به مراتب پایین تر می باشد.
فهرست
1-1مفهوم گرید2
1-2طبقه بندی گرید 4
3-1 ارزیابی گرید 4
1-4کاربردگرید5
1-5 تعریف زمانبندی گرید6
1-6 مروری بر تحقیقات گذشته7
1-7 مفهوم اصطلاحات به کار برده شده8
1-8 نمای کلی تحقیق9
فصل دوم:زمانبندی کارها در سیستم های توزیع شده
2-1 زمانبندی کلاستر و ویژگیهای آن 10
2-2 زمانبندی گرید و ویژگیهای آن13
3-2 رده بندی الگوریتم های زمانبندی گرید 16
2-3-1 زمانبندی محلی/سراسری 16
2-3-2 زمانبندی ایستا/پویا16
2-3-3 زمانبندی بهینه/نزدیک به بهینه21
2-3-4 زمانبندی توزیع شده/مرکزی22
2-3-5 زمانبندی همکار و مستقل22
2-3-6 زمانبندی زمان کامپایل /اجرا 23
2-4-1 رده بندی الگوریتم های زمانبندی از دیدگاهی دیگری 23
2-4-2 اهداف زمانبندی23
2-4-3 زمانبندی وفقی24
2-4-4 رده بندی برنامه های کاربردی25
2-4-4-1 کارهای وابسته25
2-4-4-2 گراف کار26
2-4-5 وابستگی کارهای تشکیل دهنده برنامه کاربردی 26
2-4-6 زمانبندی تحت قیود کیفیت سرویس26
2-4-7 راهکارهای مقابله با پویایی گرید28
2-5 الگوریتم های زمانبندی کارهای مستقل32
2 -5-1 الگوریتم MET 32
2-5-2 الگوریتم MCT 32
2-5-3 الگوریتم Min-min33
2-5-4 الگوریتم Max-Min 33
2 -5-5 الگوریتم Xsuffrage 34
2 -5-6- الگوریتم GA 35
2-5-7- الگوریتم SA 37
فصل سوم:الگوریتم های زمانبندی گراف برنامه
3-1 مشکلات زمانبندی گراف برنامه39
3-2 تکنیک¬های مهم زمان¬بندی گراف برنامه در سیستم¬های توزیع شده40
3-2-1- روش ابتکاری بر پایه لیست 40
3-2-2- روش ابتکاری بر پایه تکثیر40
3-2-3- روش ابتکاری کلاسترینگ41
3-3- دسته بندی الگوریتم¬های زمان¬بندی گراف برنامه در سیستم¬های توزیع شده44
3-4- پارامترها و مفاهیم مورد استفاده در الگوریتم¬های زمان¬بندی گراف برنامه46
3-5- الگوریتم¬های زمان¬بندی گراف برنامه با فرضیات محدودکننده50
3-5-1- الگوریتمی با زمان چند جمله¬ای برای گراف های درختی - الگوریتم HU 50
3-5-2- الگوریتمی برای زمان¬بندی گراف برنامه با ساختار دلخواه در سیستمی با دو پردازنده51
3-5-3- الگوریتمی برای زمان¬بندی گراف بازه¬ای مرتب شده52
3-6- الگوریتم¬های زمان¬بندی گراف برنامه در محیطهای همگن 54
3-6-1- الگوریتم Sarkar54
3-6-2- الگوریتمHLFET55
3-6-3- الگوریتم ETF55
3-6-4- الگوریتم ISH 55
3-6-5- الگوریتم FLB56
3-6-6- الگوریتم DSC56
3-6-7- الگوریتم CASS-II58
3-6-8- الگوریتم DCP59
3-6-9- الگوریتم MCP60
3-6-10- الگوریتم MD61
3-6-11- الگوریتم TDS61
3-7- الگوریتم¬های زمان¬بندی گراف برنامه در محیطهای ناهمگن63
3-7-1- الگوریتم HEFT63
3-7-2- الگوریتم CPOP63
3-7-3- الگوریتم LMT64
3-7-4- الگوریتمTANH 65
فصل چهارم :الگوریتم FLB
1-4 ویژگیهای الگوریتم66
4-2 اصطلاحات به کار برده شده66
4-3 الگوریتم67
4-4 پیچیدگی الگوریتم75
4-5 کارایی الگوریتم77
فصل پنجم: شبیه سازی گرید
5-1 ابزار شبیه سازی79
5-1-1- optosim79
5-1-2 SimGrid 80
5-1-3- Gridsim 80
کارهای انجام شده83
پیشنهادات83
شامل 92 صفحه word
دانلود تحقیق پیاده سازی الگوریتم FLB
