مرکز دانلود خلاصه کتاب و جزوات دانشگاهی

فهرست مطالب

عنوان صفحه

فصل اول : مقدمه

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-min...............................................33

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- الگوریتم Sarkar................................................54

3-6-2- الگوریتمHLFET................................................55

3-6-3- الگوریتم ETF................................................55

3-6-4- الگوریتم ISH ..............................................55

3-6-5- الگوریتم FLB................................................56

3-6-6- الگوریتم DSC................................................56

3-6-7- الگوریتم CASS-II..............................................58

3-6-8- الگوریتم DCP................................................59

3-6-9- الگوریتم MCP................................................60

3-6-10- الگوریتم MD...............................................61

3-6-11- الگوریتم TDS...............................................61

3-7- الگوریتم­های زمان­بندی گراف برنامه در محیطهای ناهمگن...............63

3-7-1- الگوریتم HEFT................................................63

3-7-2- الگوریتم CPOP..................................................63

3-7-3- الگوریتمLMT.................................................64

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- optosim..................................................79

5-1-2SimGrid ..................................................80

5-1-3- Gridsim ..................................................80

کارهای انجام شده...............................................83 پیشنهادات............................................................83

مراجع.............................................................85

  

فهرست اشکال

عنوان صفحه

شکل 1-2 ساختار کلاستر ......................................11

شکل 2-2 ساختار زمانبند گرید ...............................14

شکل 2-3-2 رده بندی الگوریتم های ایستا.......................19

شکل 2-4 رده بندی برنامه های کاربردی.........................26

شکل 2-5-6کلاس بندی برنامه های کاربردی .......................37

شکل 3-2-3 گراف نمونه با هزینه محاسباتی و ارتباطی .............43

شکل 3-3 دسته بندی الگوریتم های گراف برنامه..................45

شکل 3-4 گراف کارها .........................................50

شکل 3-5-3 گراف بازه ای مرتب شده با هزینه محاسباتی یکسان .....53

شکل 3-5-3 مقایسه الگوریتم های زمانبندی گراف برنامه در محیطهای

همگن ........................................................54

شکل 4-1 گراف کار...........................................76

شکل 5-2 ساختار Gridsim .....................................81

 

 

فصلاول : مقدمه

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

Mainfram معایب

• هزينه سيستم های Mainfarme . يکی از اولين دلايل مهم ، هزينه های بالای سيستم های Mainframe است . اين مسئله از دو زاويه متفاوت قابل بررسی است : هزينه بالای سرمايه گذاری اوليه که بسياری از سازمان ها و موسسات توان مالی آن را ندارند و دوم اينکه در اين مدل ، دارای صرفا" يک نقطه آسيب پذير با ريسک بالا می باشيم .
• مالکيت اختصاصی داده ها. يکی از فاکتورهای مهم ديگر، سياست های مربوط به مالکيت داده ها است . سازمان ها و موسسات که دارای داده های اختصاصی خود می باشند، علاقه مند به واگذاری مسئوليت مديريت داده های مربوطه ، به ساير مکان های فيزيکی نمی باشند .
• امنيت . يکی ديگر از فاکتورهای مهم در اين زمينه موضوع امنيت است . برای يک سازمان ، اولا" دستيابی به اغلب داده های آن می بايست بسادگی محقق گردد و ثانيا" داده ها ی حساس موجود در سازمان می بايست از بعد امنيتی، ايمن نگهداری گردند . تامين دو خواسته فوق ( رويکردهایرقابتی و رويکردهای امنيتی ) با جدا سازی فيزيکی داده از يکديگر محقق خواهد شد ( انباشت داده ها، با نگرش های متفاوت در رابطه با سرعت در دستيابی و ايمن در ذخيره سازی ، ضرورت وجود برنامه های توزيع شده را بخوبی نمايان می سازد )

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

يک برنامه توزيع شده، برنامه ای است که پتانسيل های پردازشی آن ممکن است توسط چندين کامپيوتر فيزيکی تامين و داده های آن در چندين محل فيزيکی، مستقر شده باشد .

یک سیستم توزیع شده مجموعه ای از کامپیوتر هاست که دارای منابع اجرایی مختلف و زیادی هستند.

مفهوم گرید1-1

در گريد هر شخصي مي تواند به راحتي وارد يك شبكه شود و از توان محاسباتي موجود در شبكه استفاده كند.در شیوه های نوین به جای استفاده از رایانه های اختصاصی برای حل مسائل بزرگ، با استفاده از رایانه های موجود پراکنده که از همه توان محاسباتی خود استفاده نمی کنند، سعی می شود با جمع آوری این توانهای پراکنده که اغلب بی استفاده می مانند، کارهای خود را انجام دهند. این منابع محاسباتی اگرچه اغلب قدرت و هماهنگی رایانه های اختصاصی را ندارند، اما تعداد زیادی از آنها به وفور در مراکز عمومی از قبیل دانشگاه ها، اداره ها، کتابخانه ها و غیره و حتی در منازلی که اتصال قوی به اینترنت دارند یافت می شوند و این موجب می شود که توان محاسباتی آن در مجموع بسیار بالا باشد و در عین حال هزینه آن به مراتب پایین تر می باشد.

 

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

یکی ازمزایای مهم سیستمهای توزیع شده سرعت بالای اجرای برنامه‌هاستچرا که یک برنامههمزمان می‌تواند از چندین کامپیوتر برای اجراء شدنش استفاده کند.[22]

همچنینبه علت توزیع شدن اطلاعات, بانکهای اطلاعاتی حجیم می‌توانند روی یکسریکامپیوترهای شبکه شده قرار بگیرند. و لازم نیست که همه اطلاعات به یک کامپیوترمرکزی فرستاده شود(که در نتیجه این نقل و انتقالات حجیم زمان زیادی به هدرمی‌رود.(

به علتتأخیر‌های انتقال در شبکه ونویزهای احتمالی در خطوط انتقالی قابلیتاعتماد اجرای یک برنامه دریک سیستم تنها,بیشتراز قابلیت اجرای آن دریک سیستم توزیعشده است .

همچنیندرسیستم توزیع شده اگر یکی از کامپیوترهایی که وظیفه اصلی برنامه جاری را برعهدهدارد خراب شود کل عمل سیستم مختل خواهد شد . از طرف دیگر اگر اطلاعاتی همزمان درچند کامپیوتر به صورت یکسان ذخیره گردد ویکی از کامپیوترها خراب شود, داده هارا می‌توان از کامپیوترهای دیگر بازیابی کرد از این نظر امنیت افزایشمی‌یابد.

اشتراک به منابع محاسباتی محدود نمی­شود. انواع منابع اعم از انباره­ها،نرم­افزار و بانک­های اطلاعاتی را در بر می­گیرد. در عین حال، امنیت و سیاست محلی نیز تضمین می­شود.[21]

بعد از اتصال به گرید، کاربر استخر بزرگی از منابع را در اختیار دارد. هنگامی که بار کاری سیستم محلی سنگین باشد، می­توان بخشی از بارکاری را به سایر منابع گرید منتقل کرد.

 

 

 

 

2-1طبقه بندی گرید

 

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

هرچند مرز مشخصی بین این سه دسته وجود ندارد، اما بحث ما معطوف به گریدهای محاسباتی است.

انگيزه گريد محاسباتي، مجتمع كردن منابع توزيع شده ناهمگون جهت حل مسائل پيچيده علمي، صنعتي و تجاري است . جهت رسيدن به اين هدف يك سيستم زمانبندي كارآمد به عنوان يك بخش حياتي براي گريد لازم است . متاسفانه پويايي و ناهمگوني منابع گريد باعث پيچيدگي زمانبندي وظايف مي شوند. بعلاوه با معرفي مدل اقتصادي گريد، علاوه بر زمان اتمام كار،

هزينه اجراي كار نيز به نگراني هاي كاربران اضافه شد .

 

1 – 3 ارزیابی گرید

سه مرحله برای ارزیابی گرید وجود دارد اول:تولید سیستم هایی که در اوایل 1990 متولد شد. دوم:تولید سیستم با تمرکز روی ابزار برای حمایت از معیار های بزرگ داده و محاسبه جریان الکتریکی . سوم: تولید سیستم هایی که برای همکاری جهانی بر تغییرات تاکیید دارد .

اولین تولید فوریتی فرا محاسبه یا محیط های گرید نام گذاری شدهاست. عموما واقعیت این پروژه بهبود بخشیدن به منابع محاسباتی در یک دامنه کاربردوسیع بود. پروژه ارائه شده پیشگام این تکنولوژی [3]فافنر بود.

نسل دوم گرید در نتیجه یک فوریت از یک زیر ساخت که قادر به بهم پیوند دادن بیشتر مرکزهای سوپر محاسباتی مشخص شده است. اکنون با ارتقا تکنولوژیهای شبکه وسازگاری آن با استانداردهای گرید می تواند به عنوان یک زیر ساخت توزیع کننده ممکن و قابل قبول در مقیاس های بزرگ که محاسبات را می خواهند حمایت کنند. در این نوع گرید به طور معمول طبیعت نا همگون منبع ها و بهبود بخشیدن کاربرد ها با محیط همگون ویکنواخت را با مجموعه ای از واسط های استاندارد پنهان می کند.گلو باس [20]یکی از پروژه های توزیع شده است که برای اینکه گرید را استوار کند.

نسل سوم:سازگاری و انطباق زیادی از مدل های خدمات هدفمند وجود دارد . یک حالت قوی از اتوماسیون در سیستم های این نسل وجود دارد . برای مثال زمانی که انسانها نمی توانند برای مدت طولانی مقیاس و ناهمگونی منابع را ارتباط دهند اما ارسال برای پردازش انجام می شود که باعث خود گردانی درون سیستم ها می شود.

 

4-1 کاربردهای گرید

 

اخیرا تلاش زیادی برای انتقال دادن برنامههای کاربردی به گرید صورت گرفته است.یک مثال پروژه EGEE است. هدف های آن بهبود بخشیدن کار محققان در دانشگاه و صنعت با دسترسی به منبع های محاسباتی اصلی و مستقل از محل جغرافیایی آنها است.تمرکز روی تعداد زیادی از کاربران گرید است.دو کاربرد برای پیدا کردن تایید اجرا و کارایی زیر ساختها انتخاب شده است یکی محاسبه برخوردها با پشتیبانی از انرژی فیزیکی بالا در آزمایشات فیزیک ودیگری گرید های پزشکی که چندین گروه به طور یکسان با مشکلات سیل عظیم اطلاعات و داده های مراقبت از سلامت روبه رو هستند.[14]

نمونه : تلسکوپ جادوگر(majic)

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

آن بزرگترین تلسکوپ اشعه گاما در جهان است و چندین تلسکوپ دیگر در کشورهای اروپایی به آن در جمع آوری اطلاعات کمک می کنند.توزیع جغرافیایی منابع مدیریت آنها را مشکل می کند و این یک نمونه برای گرید محاسباتی است که می تواند کمک بزرگی بکند زیرا محققان می تواند به طور یکسان به تمام منابع دسترسی داشته باشند. تلسکوپ در شبهای اول ماه کار می کند و حدود 600 گیگا بایت اطلاعات در شب ثبت می کند داده های اضافی تلسکوپ و اطلاعات هوا شناسی نیز ذخیره می شوند.تمام این داده ها باید دریافت و آنالیز شوند.[11]

نمونه رایج استفاده از گرید در هواشناسی است.که در آن ایستگاه تلوزیون و شرکت ماهواره ای و مر کز تجسم و یک کامپیوتر مرکزی وجود دارد که ایجاد امنیت و ارتباطات آنها در محیط گرید فراهم می شود.

قدرت گرید بخصوص در پردازش های فشرده مثل تحقیقات علمی و نمونه های مالی و طراحی های صنعتی و نمودار پرداخت تصویر مفید تر است.

 

 

 

1-5 تعریف زمان بندی گرید

 

زمان­بند، مدیر منبعی میانی است و واسطی است بین مصرف کننده­ها و منابع.

در محیطهای توزیع شده، گروهی از کاربران برنامه­های خود را برای اجرا به مجموعه ای از منابع می­فرستند. سیستم زمان­بند چنین محیط توزیع شده­ای، مسئول مدیریت منابع و برنامه­­هاست. سیستم زمان­بند بایستی بتواند منابع مناسبی به برنامه­ها اختصاص داده و اهداف کارایی را نیز برآورده سازد.سیستم زمان­بند محیطهای محاسباتی موازی سنتی به دلیل خصوصیات یکسان برنامه­ها وخصوصیات یکسان منابع، ساده تر است. در فرهنگ لغت GGF [1]، مراحل زمان­بندی گرید به شرح زیر بیان شده است: کشف منبع در دسترس برای برنامه، انتخاب سیستم یا سیستم­های مناسب آن و پذیرشبرنامه. به طور خلاصه می­توان گفت زمان­بندی گرید، قالبی است نرم­افزاری که اطلاعات وضعیت منابع را جمع نموده، منابع مناسب را نامزد نموده، کارایی هر نامزد را پیش بینی نموده و بهترین منبع را تعیین می­کند.

 

1-6 مروری بر تحقیقات گذشته

طیف وسیع کاربران گرید دارای برنامه­هایی با نیازمندی­های متفاوت هستند. ممکن است برنامه­های آنان دسته­ای و یا به خط[2] باشد، شامل کارهای وابسته به هم و یا مستقل باشد. به همین دلیل، ارائه الگوریتم زمان­بندی همه منظوره که بتواند برای تمامی سناریوها مناسب باشد، امکان­پذیر نیست. از این رو ما بحث خود را به زمان­بندی کارهای وابسته، معطوف نموده ایم. هنگامی که کارهای تشکیل دهنده برنامه دارای ترتیب تقدمی باشند، برنامه، به شکل گراف جهتدار بدون سیکل (DAG[3]) مدل می­شود که در آن گره­ها نشان دهنده کارها و لبه­ها نشان دهنده ترتیب گره­هاست. گاهی اوقات وزنی نیز به گره­ها و لبه­ها اضافه می­شود که به ترتیب نشان دهنده هزینه­های محاسباتی و هزینه­های ارتباطی است. ایجاد تعادل بین به حداکثر رساندن موازی سازی و به حداقل رساندن تاخیر ارتباطی به عنوان مسئله مهمی در زمان­بندی کارها مطرح است. برای زمان­بندی گراف برنامه، الگوریتم­های ابتکاری[4] متعددی مطرح شده است. برای زمان­بندی گراف برنامه، الگوریتم­های ابتکاری[5] متعددی مطرح شده است. این الگوریتم­ها را می­توان به سه دسته کلی تقسیم کرد. الگوریتم­های بر پایه لیست[6]، الگوریتم­های بر پایه تکرار[7] و الگوریتمهای کلاسترینگ[8]. ­

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

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

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

1- 7 مفهوم اصطلاحات بکاربرده شده در این پایان نامه

ü application:مجموعه­ای از کارهای وابسته و یا مستقل است که به حل مسئله معینی منتهی می­شود. در این تحقیق از واژه فارسی "برنامه" به جای واژه " application " استفاده شده است. در این تحقیق واژه job نیز معادل واژه application تلقی شده است.

ü task: واحد کار application گرید به شمار می­آید که می­توان آن را برای اجرا فقط به یک منبع محاسباتی فرستاد . در این تحقیق از واژه فارسی "کار" به جای واژه " task " استفاده شده است.

 

ü scheduling: به فرایند کشف منبع، انتخاب منبع و ارسال کار به منبع گفته می­شود . در این تحقیق "زمان­بندی" ترجمه شده است.

 

DAG: برنامه حاوی چندین کار موازی، به شکل گراف جهتدار بدون سیکل "DAG" مدل می­شود. از این واژه با عنوان گراف برنامه و یا به اختصار گراف یاد شده است.

1- 8 نمای کلی پایان نامه

در فصل اول (فصل جاری)، مفاهیم و تعاریف پایه بیان شده است. مفهوم گرید و مسئله زمان­بندی تبیین شده، روش­های موجود زمان­بندی گراف برنامه به طوراجمال بیان شده است.

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

در فصل سوم، موضوع زمان­بندی گراف برنامه در سیستم­های توزیع شده، مورد بحث و بررسی قرار گرفته، پارامترها و عناصر تاثیرگذار بر الگوریتم­ها بیان شده است.

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

 

 

 

 

 

فصل دوم: زمان­بندی کارها در سیستمهای توزیع شده

2-1- زمان­بندی کلاسترها و ویژگی­های آن

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

نهادی مرکزی کنترل همه گره­های محاسباتی را بر عهده دارد. نمونه ای از پیاده سازی کلاستر می­تواند بدین صورت باشد: گره­هایی که سیستم عامل لینوکس دارند و نرم افزار Beowulf که امکان موازی­سازی را فراهم می­کند . شکل زیر ساختار کلاستر را نشان می دهد.

 

 

 

 

 

 

 

 

 

شکل 2-1 ساختار کلاستر

کلاسترها به صورت رئیس/مرئوس[9] سازماندهی می­شوند.[6] گره رئیس، مسئولیت قبول کارها،
زمان­بندی آنها، ارسال آنها به گره مرئوس را برای اجرا بر عهده دارد. گره مرئوس، کامپیوتر مستقلی است که پردازنده، حافظه و سیستم عامل خودش را دارد و مسئول اجرای کار و برگشت دادن نتیجه به کاربران است. گره­های مرئوس معمولا با شبکه ای با سرعت بالا، تاخیرکم و عرض باند زیاد که امکان ارتباط بین پردازنده ای را فراهم می­کند، به هم متصل هستند. ارتباط بین پردازنده ای با مکانیسم ارسال پیام[10] مانند PVM یا MPI انجام می­شود.

کلاستر، هم برای اجرای کارهای ترتیبی و هم کارهای موازی، وسیله مناسبی است. برنامه نویس بر اساس مکانیسمهای ارسال پیام، نحوه توازی برنامه­ها را مشخص می­کند. اجرای موازی نیازمند کتابخانه زمان اجرایی[11] است که از PVM و MPI حمایت کند. سیستم زمان­بند کلاستر ساختار رئیس/مرئوس دارد. گره رئیس،کارها را از سرویس گیرنده­ها[12] دریافت نموده و در صف قرار می­دهد. گره رئیس اطلاعات مربوط به کارهای پذیرفته شده را در اختیار دارد. گره رئیس کارهای منتظر در صف را برای اجرا به گره­های مرئوس می­فرستد. یعنی نقش زمان­بند را نیز بازی می­کند. همه گره­های کلاستر همسان هستند، یعنی پردازنده، اندازه حافظه و عرض باند شبکه یکسانی دارند. تعداد گره­های مرئوس نیز معمولا ثابت است. همه گره­ها نیز به محاسبه کلاستر اختصاص دارند. شبکه ارتباطی، خصوصی و سرعت بالاست یعنی امکان ارتباط بین هر زوج از گره­ها در اغلب مواقع تضمین شده است. گره رئیس که نقش زمان­بند را نیز بازی می­کند، با مجموعه ثابتی از گره­های مرئوس در ارتباط است.

زمان­بند در هنگام تصمیم گیری فقط به در دسترس بودن گره­ها توجه دارد. گره مرئوسی که اجرای کاری را به پایان می­رساند، در دسترس بودن خود را به زمان­بند گزارش می­دهد. یعنی در هر زمان، زمان­بند اطلاعات وضعیت همه گره­ها را در اختیار دارد. روش کار بدین صورت است که هر برنامه، درخواست­های منبع خود را در یک فایل اسکریپت ثبت می­نماید و زمان­بند این فایل را تفسیر می­کند. ممکن است برنامه ای شامل چندین کار کوچکتر شود که انتظار می رود هرکدام در گره مرئوس مجزایی اجرا شوند. برنامه هنگام تقاضای منبع، تعداد گره­های درخواستی و زمان اجرای انتظاری را مشخص می­کند. ممکن است زمان­بند ابتدا صف کارها را مرتب نماید.متداول­ترین الگوریتم­های مرتب سازی در کلاسترها عبارت است از: ابتدا اولین کار[13] ، ابتدا کار با کوچکترین تقاضا[14]، ابتدا کوتاهترین کار[15] و backfill .

بعد از مرتب سازی صف کارها، اولین کاری که زمان­بندی می­شود، کار ابتدای صف است. بر اساس تقاضای برنامه، زمان­بند به تعداد گره­های درخواستی برنامه، گره انتخاب کرده و گره­های مرئوس منتخب را به برنامه مربوطه تخصیص می­دهد. هنگامی که اجرای همه کارهای کوچک به اتمام رسید، نتیجه کار در فایلی در گره رئیس نوشته شده و نهایتا به سرویس گیرنده پذیرنده برنامه ارسال می­شود. اهداف کارایی سیستم زمان­بند کلاستر معمولا اهدافی سیستم­گرا مانند به حداکثر رساندن توان عملیاتی[16] می­باشد.

خصوصیات زمان­بند کلاستر از خصوصیات محیطهای محاسباتی کلاستر ناشی می­شود. این خصوصیات عبارتند از:

• همسانی منابع و برنامه­ها

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

 

• منابع تخصیص داده شده[17]

اغلب کلاسترها در یک دامنه مدیریتی قرار دارند و گره­های محاسباتی و شبکه ارتباطی هردو به محاسبات کلاستر اختصاص دارند. به همین دلیل رفتار گره­های محاسباتی و ظرفیت ارتباط قابل پیش بینی است.

• ساختار زمان­بندی مرکزی

در کلاستر، نهادی مرکزی وظیفه زمان­بندی را بر عهده دارد. زمان­بند بر روی همه گره­های محاسباتی و اطلاعات کارها، کنترل کامل دارد.

• شبکه ارتباط داخلی سریع

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

 

• هدف کارایی یکنواخت

کل کلاستر یک هدف کارایی را دنبال می­کند و زمان­بند برای رسیدن به این هدف تلاش
می­کند. به همین دلیل طراحی زمان­بند برای چنین سیستمی، ساده است.

2-2- زمان­بندی گرید و ویژگی­های آن

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

• ناهمگونی منابع:

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

• خودمختاربودن دامنه ها:

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

• منابع تخصیص نیافته:

به دلیل وجود منابع تخصیص نیافته، رقابت زیادی بر سر استفاده از منابع وجود دارد. یعنی ممکن است که منبعی به طور همزمان به چند گرید متصل باشد و کاربران محلی و سایر گریدها بطور همزمان در آن منبع شریک باشند. یکی از نتایج رقابت این است که رفتار و کارایی در خلال زمان تغییر می­کند. به عنوان مثال در شبکه­های گسترده که از مجموعه پروتکل اینترنت[19] استفاده می­کنند، خصوصیات شبکه مانند تاخیر و عرض باند در خلال زمان تغییر می­کند. در چنین محیطی، طراحی مدل کارایی دقیق کار بسیار مشکلی است. با سنجش کسری از منابع در دسترس به شکل پویا می­توان رقابت را تشخیص داد. سیستم مدیریت منبع با ضمانت کیفیت سرویس و رزرو منبع، پیش بینی کارایی منبع را ساده­تر می­کند.[9]

• تنوع برنامه ها:

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

• رفتار پویا:

در محیطهای محاسباتی موازی سنتی مانند کلاستر، استخر منبعی با منابع ثابت وجود دارد. اما در گرید هم در شبکه و هم در منابع محاسباتی پویایی وجود دارد. اولا شبکه­ای که کاربران زیادی به آن متصل اند، نمی­تواند عرض باند تضمین شده را فراهم کند در ثانی در دسترس بودن منابع و توانایی آنها نیز حالتی پویا دارد یعنی ممکن است منابع جدیدی به شبکه افزوده شود و یا به دلیل مشکلات شبکه منابعی از دسترس خارج شوند. به دلیل وجود رقابت بین اعضای شریک در یک منبع، توانایی منابع در حین زمان نیز تغییر می­کند. زمان­بند باید بتواند با چنین رفتار پویایی سازگار شده، بعد از اتصال منبع جدیدی به طور خودکار آن را تشخیص داده و در تصمیم گیری­های آتی آن را به شمار آورد و هنگامی که به دلایل نامعلومی، منبعی از دسترس خارج می­شود با اعمال مکانیزم­هایی مانند نقطه وارسی[20] و یا زمان­بندی مجدد[21] قابلیت اطمینان سیستم گرید را تضمین کند.شکل زیر ساختار زمانبند گرید را نشان می دهد.

شکل 2-2 ساختار زمانبند گرید [28]

 

2-3- رده بندی الگوریتم­های زمان­بندی گرید

2-3-1- زمان­بندی محلی/ سراسری

زمان­بندی محلی، نحوه تخصیص و اجرای کارها در یک پردازنده را تعیین می­کند ولی سیاست زمان­بندی سراسری از اطلاعات سیستم بهره می­برد تا کارها را بین چندین پردازنده به گونه­ای تقسیم کند که کارایی سیستم بهینه شود. مشخص است که زمان­بندی گرید در دسته زمان­بندی سراسری قرار دارد.[8]

2-3-2- زمان­بندی ایستا/ پویا

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

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

 

 

 

 

 

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

 

 

شکل 2-3-2 رده بندی الگوریتم های ایستا

 

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

اگر به منبعی تعداد زیادیکار واگذار شود، سیاست متوازن­سازی مشخص می­کند که آیا لازم است که تعدادی ازکارها به منابع دیگر فرستاده شود یا نه و در صورت لزوم ، کدام کارها باید منتقل شوند. توازن بار پویا به چهار روش مختلف انجام می­شود. روش FIFO­ی غیر مقید[23]، روش مقید به توازن، روش مقید به هزینه و روش ترکیبی[24] که در ذیل به توضیح آنها خواهیم پرداخت.

 

- روش FIFOی غیر مقید

در این روش ، کار وارده، به منبعی که در حال حاضر کوتاهترین طول صف و یا کمترین زمان انتظار در صف را دارد، واگذار می­شود. به این روش، توازن بار مصلحت­بین[25] نیز گفته می­شود.

 

- روش مقید به توازن

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

این شیوه مزایای زیادی دارد. بارهای اولیه سریعا بین منابع توزیع شده و اجرای آنها آغاز می­شود، پروسه متوازن­سازی مجدد، توزیع شده و قابل توسعه[26] است. تاخیر ارتباطی آن کم است چون انتقال کارها فقط بین منابع نزدیک به هم انجام می­گیرد. چن و همکارانش با بهره­گیری از این روش، الگوریتم زمان­بندی برای گرید ارائه داده اند.

 

- روش مقید به هزینه

این روش بهبود یافته روش مقید به توازن است. یعنی هنگام متوازن­سازی مجدد به هزینه ارتباط کارها نیز توجه دارد. یعنی به جای تعویض کارها به شکل دوره­ای،کارها را قبل از انتقال بررسی می­کند. اگر هزینه ارتباطی مربوط به انتقال کار از کاهش زمان اجرای آن بزرگتر باشد، کار منتقل نخواهد شد. این روش هنگامی که هزینه ارتباط بین منابع نا­همگون باشد و هزینه ارتباط در اجرای برنامه کاربردی، دغدغه اصلی باشد، از روش قبلی کارآمدتر است. کوروسکی و همکارانش سیاست زمان­بندی خود را بر این اساس پایه نهادند[25].

-روش ترکیبی

روش بعدی، زمان­بندی ترکیبی ایستا/ پویا ست. ایده اصلی این تکنیک، استفاده همزمان از مزایای زمان­بندی ایستا و کنترل رفتارهای غیرمطمئن برنامه­های کاربردی و منابع است. برای سناریوی برنامه­ای با رفتار نامطمئن، زمان­بندی ایستا برای آن بخش­هایی که همیشه اجرا می­شوند، بکار گرفته می­شود. در زمان اجرا، زمان­بندی با استفاده از تخمین­های محاسبه شده به شکل ایستا انجام می­شود تا سربار زمان اجرا کاهش یابد. یعنی کارهای همیشه در حال اجرا به شکل ایستا زمان­بندی می­شوند و سایر کارها به شکل پویا. به عنوان مثال، هنگامی که کیفیت سرویس خاصی مورد نیاز بعضی کارهاست، می­توان از فاز ایستا برای نگاشت کارهای نیازمند کیفیت سرویس استفاده کرد و سایر کارها را به شکل پویا زمان­بندی کرد. یا زمانی که امکان پیش­بینی رفتار منابع کم است، در شروع کار برای تخصیص اولیه کارها ، از زمان­بندی ایستا استفاده می­شود و هنگامی که تخمین کارایی که زمان­بندی ایستا بر اساس آن کار می­کند، با شکست مواجه شود، زمان­بند پویا فعال می­شود.

در بعضی از الگوریتم­های زمان­بندی پویا مانند ، منابع رزرو می­شوند. به ویژه در گرید برای رسیدن به درجه­ای از قطعیت کارایی منابع، این تکنیک عمومیت دارد.

2-3-3-بهینه / نزدیک به بهینه

در حالتی که همه اطلاعات مربوط به منابع و کارها شناخته شده باشند، تخصیص بهینه بر اساس معیارهایی مانند "به حداقل رساندن زمان گسترش[27]" یا "حداکثر نمودن بهره­وری منابع[28] " صورت می­گیرد. اما به علت طبیعت NP-complete الگوریتم­های زمان­بندی، داشتن فرضیات معقول مشکل بوده و معمولا اثبات بهینگی چنین الگوریتم­هایی سخت است. به همین دلیل تحقیقات فعلی به دنبال راه حل­های نزدیک به بهینه است. الگوریتم­های نزدیک به بهینه به دو دسته تقریبی و ابتکاری تقسیم می­شوند. الگوریتم­های تقریبی مدل­های محاسباتی رسمی[29] را بکار می­برند اما کل فضای جواب را جستجو نمی­کنند بلکه هنگامی که راه حلی به اندازه­ی کافی خوب پیدا شود، جستجو متوقف می­شود. زمانی که متریک مناسبی برای ارزیابی جواب وجود داشته باشد، این روش زمان صرف شده برای یافتن زمان­بندی [30] را کاهش می­دهد.

فاکتورهایی که به کمک آن می­توان تعیین کرد که آیا ادامه روش مناسب است یا نه عبارتند از:

• در دسترس بودن تابعی برای ارزیابی جواب
• زمان مورد نیاز برای ارزیابی جواب
• توانایی قضاوت در مورد مقدار جواب بهینه بر اساس بعضی متریکها
• در دسترس بودن مکانیسمی برای محدود کردن فضای جواب

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

2-3-4- توزیع شده/ مرکزی

در زمان­بندی­های پویا، مسئولیت تصمیم­گیری در خصوص زمان­بندی سراسری بر عهده یک زمان­بند مرکزی قرار داده می­شود و یا بین چندین زمان­بند توزیع شده به اشتراک گذاشته می­شود. پیاده­سازی زمان­بند مرکزی ساده است اما قابل توسعه نیست، تحمل خطا ندارد و احتمال زیادی وجود دارد که تبدیل به گلوگاه کارایی شود. سابین و همکارانش زمان­بندی مرکزی ارائه کردند که کارهای موازی سایتهای ناهمگون را به روش backfilling زمان­بندی می­کرد. آرورا و همکارانش زمان­بندی غیرمرکزی ، پویا، با متد "فرستنده آغازگر[31]" با توازن بار ارائه نمودند که در آن برای یافتن گره­های پدری که باید کار به آن جا مهاجرت کند، از تکنیک جستجوی هوشمندانه­ای بهره گرفته شده است. در این الگوریتم پروسه تصمیم­گیری با روند اجرای واقعی کارها، روی­هم­اندازی شده است تا در سیکل­های گرانبهای پردازنده صرفه­جویی شود.

2-3-5- همکار/مستقل

نکته قابل توجه دیگر در الگوریتم­های زمان­بندی توزیع شده این است که آیا گره­های درگیر زمان­بندی به شکل همکار، کار می­کنند یا به شکل مستقل؟ درحالت مستقل، هر زمان­بند[6] به صورت خودمختار و بر اساس اهداف بهینه خود و بدون توجه به تاثیر تصمیمش بر روی بقیه سیستم، تصمیم­گیری می­کند. مثال این نوع زمان­بندها، زمان­بند سطح برنامه کاربردی است. در حالت همکار، هر زمان­بند کارهای بخش مربوط به خود را زمان­بندی می­کند اما همه زمان­بندها به سمت یک هدف مشترک سیستمی پیش می­روند و هدف مشترک، بالا بردن کارایی کل سیستم است نه کارایی محلی و نه کارایی برنامه خاصی.

2-3-6- زمانبندی زمان کامپایل /اجرا

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

2-4-1 دسته­بندی الگوریتم­های زمان­بندی از دیدگاهی دیگر

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

2-4-2- اهداف زمان­بندی

مصرف­کنندگان منابع (کاربران گرید) و فراهم­کنندگان منابع، اهداف متفاوتی را دنبال می­کنند. کاربران به دنبال کارایی بیشتر برنامه کاربردی خود هستند و هزینه کمتر در حالی که فراهم­کنندگان منبع به دنبال بهره­وری بیشتر از منابع خود هستند و منفعت بیشتر.

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

الگوریتم­های زمان­بندی با هدف منبع گرا، تلاش دارند که کارایی منابع را بهبود بخشند یعنی توان عملیاتی[32](تعداد برنامه­های پردازش شده یک منبع در یک پریود خاص) را بالا برند و بهره­وری(درصد مشغول بودن یک منبع) را بهبود بخشند. بهره­وری پایین به معنای بیکار بودن منبع و تلف شدن توان آن است. در یک منبع دارای چند پردازنده، بهره­وری پردازنده ها، متفاوت است و برای بهبود توان عملیاتی بایستی بار پردازنده­ها را متوازن ساخت. کندر سیستمی است که هدف زمان­بندی آن افزایش توان عملیاتی است.

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

 

[1] Global Grid Forum

[2] On Line

[3] Directed Acyclic Graph

[4] Heuristic

[5] Heuristic

[6] List scheduling

[7] Duplication based

[8] Clustering

[9] Master/Slave

[10] Message Passing

[11] Run Time

[12] Client

[13] First Come First Serve

[14] Minimal Request Job First

[15] Shortest Job First

[16] Throughput

[17] Dedicated

[18] Domain

[19] IP

[20] Check Pointing

[21] Rescheduling

[22] Real Time

[23] Unconstrained FIFO

[24] Hybrid

[25]Opportunistic Load Balancing

[26]Scalable

[27] Make Span

[28] Utilization

[29]Formal

[30]Schedule

[31] Sender-initiated

[32]Throughput