شبکه های تورین محاسباتی (گرید) زمینه‌ای را فراهم آورده است که بتوان از منابع ناهمگن در نقاط مختلف جغرافیایی برای حل مسائل پیچیده علمی، مهندسی و تجارت استفاده کرد. عملیات زمانبندی نقش کلیدی در عملکرد گرید ایفا میکند. بدلیل پویایی منابع و تخمین نادقیق زمان اجرایی و ... عملیات زمانبندی باید مکانیسم هایی را برای پشتیبانی از تحمل خطا، افزایش بهره وری از منابع و کاهش زمان اتمام کارها استفاده کند، که به آن زمانبندی مجدد گویند. در این پایان نامه دو الگوریتم زمانبندی کارهای مستقل و یک الگوریتم زمانبندی جریان کارها با در نظر گرفتن پویایی محیط ارائه شده که اهداف آنها کاهش زمان اجرا، افزایش بهرهوری از منابع، ایجاد توازن بار و پشتیبانی از تحمل خطا می باشد. کلید واژه: گرید محاسباتی، زمانبندی، زمانبندی مجدد، جریان کار. فهرست مطالب عنوان صفحه 1- مقدمه .......................................... 11-1 مقدمه........................................ 11-2 ضرورت اجرا................................... 21-3 هدف از اجرای پایاننامه....................... 31-4 مراحل انجام پایاننامه........................ 41-5 ساختار پایاننامه.......................... 42- مفاهیم اولیه زمانبندی و مروری بر کارهای گذشته. 52-1 مقدمه..................................... 52-2 ساختار متمرکز............................. 72-3 ساختار غیر متمرکز و یا توزیعی............. 82-4 فرایند زمانبندی گرید و اجزای آن .......... 102-5 انواع زمانبند ............................ 112-6 انواع کارها .............................. 122-7 نحوهی زمانبندی ........................... 142-8 وظایف فرازمانبند ......................... 142-8-1 نگاشت کار ........................... 152-9 گذری بر تحقیقات پیشین .................... 172-9-1 مفاهیم اولیه ........................ 172-9-2 الگوریتم ETF......................... 192-9-3 الگوریتم Myopic....................... 192-9-4 الگوریتم کمترین کمترین، بیشترین کمترین، حق رای 192-9-5 الگوریتم HLEFT....................... 202-9-6 الگوریتم hybrid........................ 202-9-7 الگوریتم GRASP....................... 212-9-8 الگوریتم CPOP........................ 212-9-9 الگوریتم PETS........................ 222-9-10 الگوریتم HLEFTبا نگاه به جلو ....... 232-9-11 الگوریتم FTBAR...................... 232-9-12 الگوریتم TSB....................... 242-10 جمع بندی............................... 243- الگوریتمهای پیشنهادی ......................... 253-1 مقدمه .................................... 253-2 الگوریتم Asuffrage.......................... 273-3 الگوریتم MaxSuffrage......................... 283-4 الگوریتم DHLEFT............................ 304-نتایج حاصل از ارزیابی و مقایسه الگوریتم های پیشنهادی 344-1 مقدمه .................................... 344-2محک ارزیابی براون.......................... 344-3ارزیابی الگوریتم Asuffrage................... 364-4 ارزیابی الگوریتم MaxSuffrage................. 384-5 ارزیابی زمانبند الگوریتم پیشنهادی برای جریان کار404-6 ارزیابی الگوریتم DHLEFT.................... 434-7 نتیجه گیری و پیشنهادات برای آینده ........ 495- منابع......................................... 50 فهرست جدولها عنوان صفحه جدول 4-1 حالات ماتریسETC.......................... 36جدول 4-2 نتایج زمان اتمام آخرین کارالگوریتم Asuffrage 37جدول 4-3 نتایج درصد بهرهوری از منابع الگوریتم Asuffrage37جدول 4-4 نتایج زمان اتمام آخرین کار الگوریتم MaxSuffrage 39جدول 4-5 نتایج درصد بهرهوری از منابع الگوریتم MaxSuffrage 39جدول 4-6 مقادیر پارامتر N........................ 41جدول 4-7 مقادیر پارامتر Fat....................... 41جدول 4-8 مقادیر پارامتر Density.................... 41جدول 4-9 درصد خطا در تخمین زمان اجرایی.......... 42جدول 4-10 زمان رخداد رویداد..................... 43جدول 4-11 میانگین نتایج زمان اتمام آخرین کار الگوریتم DHLEFT48جدول 4-12 میانگین نتایج درصد بهرهوری از منابع الگوریتم DHLEFT48 فهرست شکلها عنوان صفحه شکل2-1 معماری زمانبندی متمرکز ................... . 7شکل2-2 معماری زمانبندی سلسله مراتبی ............. . 9شکل 2-3 معماری زمانبندی غیرمتمرکز ............... . 9شکل 2-4 معماری زمانبندی گرید .................... 10شکل 2-5 جریان کار ............................... 13شکل 2-6 نمونه ماتریس ETC......................... 14شکل 2-7 گراف جهت دار بدون دور(DAG) .............. 18شکل 2-8 جدول زمان اجرایی تخمینی................. 18شکل 3-1 شبه کد الگوریتم DHLEFT................... 33شکل 4-1 نتایج زمان اتمام آخرین کار الگوریتم DHLEFTبا Fat=0.1 44شکل 4-2 نتایج زمان اتمام آخرین کار الگوریتم DHLEFTبا Fat=0.3 45شکل 4-3 نتایج زمان اتمام آخرین کار الگوریتم DHLEFTبا Fat=0.5 45شکل 4-4 نتایج زمان اتمام آخرین کار الگوریتم DHLEFTبا Fat=0.7 46شکل 4-5 نتایج درصد بهرهوری از منابعالگوریتم DHLEFTبا Fat=0.1 46شکل 4-6 نتایج درصد بهرهوری از منابع الگوریتم DHLEFTبا Fat=0.3 47شکل 4-7 نتایج درصد بهرهوری از منابع الگوریتم DHLEFTبا Fat=0.5 47شکل 4-8 نتایج درصد بهرهوری از منابع الگوریتم DHLEFTبا Fat=0.7 48فصل اول 1-1 مقدمهاصطلاح "گرید" در اواسط دهه 1990 مطرح شده و زیر ساخت محاسبات گرید (محاسبات شبکه) در زمینه علم و مهندسی پیشرفته پیشنهاد شد [1]. ایده اصلی محیط گرید به اشتراک گذاری منابع محاسباتی است. امروزه، اکثر مردم بیشتر از حد نیاز، قدرت محاسباتی بر روی سیستمهای کامپیوتری خود دارند. از این رو کشف منابع محاسباتی توزیع شده در سطح جغرافیایی و استفاده از آنها برای حل برنامههای کاربردی که قدرت محاسباتی بالایی نیاز دارند و باید در مدت زمان معین با هزینه مشخص اجرا شوند، ترویج پیدا کرد. چنین زیر ساخت هایی گرید محاسباتی نامیده می شود، و منجر به محبوبیت حوزهای به نام محاسبات گرید شده است [1].از اتصال منابع محاسباتی مانند رایانههای شخصی، ایستگاههای کاری، خوشهها، سرویس دهندهها، ابررایانهها و ...، توزیع شده در مناطق مختلف جغرافیایی شبکههای تورین محاسباتی (گرید) پدید آمده است که به عنوان یک سکوی محاسبات برای حل مسائل مقیاس بزرگ در دانشگاه، پژوهش و صنعت مورد استفاده قرار میگیرد[2].یکی از عملیات اصلی تضمین کنندهی کارایی در شبکههای تورین محاسباتی، تخصیص منابع به کارها میباشد. عملیات تخصیص منابع باید مکانیسمهایی را برای پشتیبانی از تحمل خطا، اطمینان از اجرای حتمی کارها، افزایش بهرهوری از منابع و کاهش زمان اتمام کارها ارائه دهد. زمانبندی در محیط گرید، با توجه به توزیع جغرافیایی منابع و کاربران، نوسانات منابع، الزامات کیفیت سرویس از برنامههای کاربردی و محدودیتهای اعمال شده توسط صاحبان منابع، جزء مسائل NP-completeمی باشد[3].در زمانبندی وظایف مستقل، هدف افزایش عملکرد کل سیستم و در زمانبندی وظایف با وابستگی، هدف کاهش زمان اجرا کارها، بدون نقض محدودیت اولویت آنها میباشد. با کم کردن زمان اجرا کارها، باعث افزایش بهرهوری از منابع شده، در نتیجه بهبود در عملکرد کل سیستم را خواهیم داشت.در دهه گذشته زمانبندی کارها (وظایف با وابستگی و مستقل) درون محیط گرید توجه بسیاری از محققین را به خود جلب کرده است. به دلیل پویایی محیط گرید، عملیات زمانبندی باید مرتبا با بررسی کردن حالت جاری سیستم، اقدام به بروزرسانی زمانبند خود نماید. عملیات بروزرسانی با رخداد رویدادی در گرید به دلیل تخمین نادقیق زمان اجرایی، اضافه یا حذف شدن منابع، رخ می دهد. در واقع هدف اصلی از اعمال زمانبندی مجدد افزایش بهره وری از منابع، اجرای قطعی و کاهش زمان اتمام کارها می باشد به این صورت که در ابتدا براساس وضعیت جاری منابع و کارها زمانبندی صورت می پذیرد و در صورت رخداد رویدادهای فوق زمانبندی مجدد براساس منابع موجود و وضعیت کارهای باقی مانده صورت می پذیرد. 1-2 ضرورت اجراپژوهشهای زیادی بر روی رابطهی بین تخمینهایی که توسط کاربر به سیستم مدیریت منبع میدهد و زمان واقعی اجرای کارها صورت گرفته است و نشان داده شده که تخمینهایی که توسط کاربر فراهم میشوند در اغلب موارد از دقت کافی برخوردار نیستند. دلیل این موضوع را میتوان چنین دانست که در سیستمهای مدیریت منابع محلی، هنگامی که زمان اجرای تخمین زده شده کار به پایان برسد، کار خاتمه مییابد (فسخ میشود)، بنابراین کاربران اصولا زمان اجرای کار را بیش از حد واقعی تخمین می زنند تا از اتمام کامل کار مطمئن باشند. در پژوهشهای مختلفی تأثیر تخمینهای کاربر بر روی کارائی سیستم ارزیابی شده است و نتایج حاکی از آن است که تخمینهای غیرصحیح کاربر باعث کاهش کارائی سیستم میشود. علاوه بر این در مقاله [4] که در سال 2009 ارائه شد، نویسندگان نشان دادند که سیستمهای مدیریت منابع محلی توانایی کنار آمدن و کنترل حجم زیادی از واگذاریها را ندارند. در مقاله]5[ که در سال 2009 ارائه شد تاثیر تغییر پذیری مجموعه کاریها بر روی سیستم مدیریت منابع محلی مورد بررسی قرار گرفت و نتایج نشان داد که این تغییر پذیری باعث تصمیمات زمانبندی بدتر می شود. زمانبندی مجدد سه هدف اساسی را دنبال میکند: افزایش کارایی زمانبند، کاهش زمان اجرایی و ارائه تحمل خطا.زمانبندی در محیط گرید بدلیل پویایی از دو مرحله تشکیل میشود در مرحله اول زمانبند براساس حالت جاری منابع، و زمان اجرایی تخمینی یک نگاشت از کارها روی منابع را بوجود میآورد. در مرحله دوم با رخداد یک رویداد، زمانبند، زمانبندی مجددی را براساس کارها، منابع و وابستگی های موجود بین کارها، صورت میدهد و نگاشت جدیدی را تولید می کند.