ورود به حساب کاربری

نام کاربری *
رمز عبور *
مرا به خاطر بسپار.

بنیاد توسعه رایانش سریع و ابری

HPC and Cloud Computing Development Foundation

زمان بندی و تخصیص منابع در ابر

نویسنده : امین نظارات

عضو هیئت علمی دانشگاه پیام نور

محاسبات ابري مدلي است براي توانمندسازي دسترسي فراگير، راحت و تقاضا محور شبكه اي به مجموعه اي از منابع محاسباتي اشتراكي و قابل پيكربندي از قبيل شبكه ها ، سرويس دهنده ها ، فضاي ذخيره سازي ، سرويس هاي كاربردي و ساير سرويس ها، كه مي توان به سرعت انها را تامين كرد و با كمترين تلاش و تماس با مدير سرويس دهنده، آن ها را نهايي و قابل استفاده نمود

 

رويكردي كه در سرويسهايي محاسبات ابري دنبال مي شود عبارت است از پرداخت مبلغ مشخصي براي منابع مور تقاضا و در اختيار گرفتن منبع براي مدت زمان توافق شده. از اين روش در حال حاضر سرويس دهنده هاي معروف ابري از جملهAmazon EC2  به صورت محاسبه منبع به ازاء استفاده ساعتي از CPU بهره می برند . اگر چه اين روش از ابتدايي ترين روشهاي فروش كالا يا خدمات مي باشد، اما از تعامل پيچيده [1] بين خريدار و سرويس دهنده ابري جلوگيري مي كند.

 

يكي از ايرادات اين روش اين است كه در زمان بالابودن  باركاري سيستم، يك كار[2] كه توسط يك مشتري تقاضا داده مي شود مي بايستي مدت زمان زيادي را در انتظار بماند تا بار كاري كمتر شده و به كار مورد نظر منابع مورد نياز اختصاص داده شود اين استراتژي فارغ از اولويت اجرايي كارها مي باشد حال آنكه مشتري صاحب اين كار مي تواند با پيشنهاد مبلغ بيشتري براي آن، اولويت خود را بالا برده و منابع مورد نياز را در اختيار بگيرد . روشهاي فعلي اختصاصي منابع[3] از قبيل FIFO, Round-Robin,… كه در ابرها استفاده مي شوند، بدون در نظر گرفتن اولويت كاري بين کارها نوعي تخصیص غير عادلانه [4] را انجام دهند.

 

در عمده سرويس هاي ابري، انجام زمان بندي [5] كارها با لحاظ كردن اين شرايط و همچنين در نظر گرفتن الزامات ذكر شده در توافقنامه سطح سرويس[6] كاري پيچيده است. به طور معمول سرويس دهنده هاي ابري در زمان واگذاري منابع به مشتريان مواردي را به عنوان تعهدات خود در ارائه سرويس با كيفيت توافق مي كنند بنابراين هرگونه اختصاص منابع به كارها و يا جابجايي كارها از يك منبع به منبع ديگر مي بايستي با در نظر گرفتن سطح كيفيت سرویس[7] توافق شده صورت می پذيرد. به عنوان مثال اگر منبعي در اختياريك کار قرار گيرد، هيچ کار ديگري با پيشنهاد قيمت بالاتر نمي تواند آن منبع را تا زمان اجراي كار اختصاص داده شده در اختيار بگيرد و همچنين در زمان بررسي پيشنهادات کارهای متقاضي براي اختصاص به منابع ، لحاظ كردن اين پارامترها براي تضمين كيفيت مورد نظر الزامي به نظر مي رسد. مواردي همچون زمان پايان کار[8] و حداكثر بودجه [9]مشتري از اين جمله اند موارد ديگري را نيز مي توان در اين بحث گنجاند كه پهناي باند شبكه[10] براي كارهايي كه نياز به فايل ورودي دارند و يا كارهاي كه از تعدادي زير كار تشكيل شده اند (Workflow).

 

به عنوان مثال كاربري قصد مسافرت به يك شهر را داشته و از يك سرويس يكپارچه ساز كه همزمان عمليات خريد بليط هواپيما، رزرو هتل و... را انجام مي دهد، استفاده مي كند. سرويس دهنده ابري كه وظيفه اجراي اين سرويس را بر عهده دارد با استفاده از زمان بند، به صورت همزمان چندين زير كار [11]را كه با يكديگر ارتباط همكارانه [12]دارند زمان بندي مي نمايد. اين زمان بند بايستي زير كارهاي مذكور را به نحوي زمان بندي كند كه زمان پايان اجراي آنها و منابعي كه به هر يك اختصاص داده مي شود يكسان و همزمان باشد (deadline) و علاوه بر اين پهناي باند مورد نياز جهت ارتباط زير كارها با يكديگر به صورت مناسب تامين شود (Bandwidth) . يا به عنوان يك مثال ديگر، گردش كارهاي علمي[13] كه به صورت همزمان و يا حتي در زمان اجرا تعدادي زير كار به صورت موازي بر روي منابع مورد نياز به اجرا در مي آورند را مي توان نام برد. در اين نوع گردش كار علاوه بر اينكه بايستي زمان اجرای كار اصلي را در نظر گرفت ، ارتباطات زير كارها با يكديگر و پهناي باند مورد نياز آنها نيز مي بايست لحاظ گردد.

 

مشتريان علاقه مند هستند كه كارهايشان در كمترين زمان ممكن و با كمترين هزينه [14]كه سرويس دهنده ابري بايستي دريافت كند به اتمام برسند. از طرف ديگر، سرويس دهنده ابر نيز تمايل دارد ميزان استفاده[15] از منابع خود را به حداكثر برساند و همچنين ميزان سود خود را افزايش دهد كه اين دو در تضاد با يكديگر هستند و معمولاً با روشهاي سنتي اختصاص منابع و مكانيزهاي زمان بندي موجود هم خواني ندارد.

 

از آنجا كه ارائه سرويس در ابرها نوعي محصول در چرخه زنجيره تامين مي باشد، زمان بندي سرويس را مي توان به دو دسته كلي تقسيم كرد:

 

1-    سطح كاربر[16]

 

2-    سطح سيستم[17]

 

در زمان بندي سطح كاربر به حل مسئله تامين سرويس بين سرويس دهنده[18]  و مشتريان پرداخته مي شود به طور عمده اين موضوع به مسائل اقتصادي از قبيل تعادل در عرضه و تقاضا، رقابت ميان مشتريان و حداقل كردن نسبي هزينه مشتري بر مي گردد.

 

در زمان بندي سطح سيستم، حل مسئله مديريت منابع درون مراكز داده[19] مد نظر مي باشد. از ديد مشتنري يك مركز داده يك سيستم يكپارچه است كه سرويسهايي را به كاربران ارائه مي كند اما در واقع مراكز داده تركيبي از تعداد زيادي ماشينهاي فيزيكي مي باشند كه به صورت يكپارچه سرويس دهي مي كنند. بعد از دريافت تعداد زيادي كار از كاربران مختلف و اختصاص آنها به ماشينهاي فيزيكي، كارايي[20] يك مركز داده تحت تاثير قرار مي گيرد. به منظور كنترل و ارتقاء میزان بهره وری[21] از سيستم موارد متعددي از قبيل اجراي همزمان فرايندها، اشنراك منابع ، خطايابي و ... بايستي لحاظ گردند.

 

در يك دسته بندي ريز تر، زمان بندي منابع و اختصاص آنها به كارها در سرويس دهنده ابري را مي توان به دو گروه تقسيم بندي كرد.

 

1)      زمان بندي تامين منابع مبتني بر مدل هاي اقتصادي[22] ( از ديد كاربر)

 

2)      زمان بندي اجراي كار مبتني بر مدل هاي ابتكاري[23] (از ديد سيستم)

 

روش زمان بندي تامين منابع مبتني بر مدلهاي اقتصادي در قالب چندين استراتژي قابل اجرا است كه از جمله آنها مي توان به موارد زير اشاره كرد:

 

1)      استراتژي هاي مبتني بر بازار[24]شامل

 

-         مدل كالايي[25]: قيمت گذاري منابع برابر

 

-         مدل قيمت ارسال شده[26]: قيمت گذاري متنوع براي روشها و ساعتهاي مختلف استفاده

 

-         مدل چانه زني[27]: قيمت گذاري اوليه توسط سرويس دهنده و چانه زني تا رسيدن به قيمت توافقي

 

2)      استراتژي مبتني بر مزايده[28] شامل:

 

-         تعداد شركت كنندگان[29]: انتخاب نوع مزايده (فروش، خريد، دو طرفه و ...) بر اساس تعداد شركت كنندگان (پيشنهاد دهدگان)

 

-         مبتني بر شفافيت اطلاعات[30]: انتخاب روش ارائه اطلاعات به ساير شركت كنندگان از قبيل روش كاملاً شفاف ، روش مهر و موم شده و ...

 

-         روش مزايده تركيبي[31]: ارائه پيشنهادات به صورت تركيبي از چند پيشنهاد براي انواع منابع. به عنوان مثال مشتري يك پيشنهاد براي تركيبي از Network,Storage,Ram,Cpu ارائه مي كند.

 

زمان بندي اجراي كارها مبتني بر مدل هاي ابتكاري نيز به طور عمده شامل روشهاي ايستا[32] و پويا[33] مي باشند. از روشهاي ايستا براي زماني كه مجموعه كارهايي كه بايستي زمان بندي شوند از قبل مشخص باشند استفاده مي شود و از روشهاي پويا نيز براي زماني كه كارها به صورت  بر خط[34] وارد مي شوند استفاده شود[26].

 

استراتژي هاي ايستا:

 

از معروف ترين الگوريتم های ارائه شده در اين گروه مي توان به   OLB,MET,MCT,MIN-MIN,MAX-MIN, GA, SA, Tabu,A* , …. اشاره كرد بر اساس ارزيابي صورت گرفته در در زماني كه ماشين ها سازگار باشند الگوريتم  GA بهترين جواب MET و  بدترين جواب  را مي دهد.

 

و براي ماشينهاي ناسازگار ، A*,GAبهترين راه حل و OLB بدترين است . به طور كلي الگوريتم هاي  Min-Min, A*, GA را مي توان به عنوان مورد اعتماد ترين روشها در ارائه كمترين  Makespan معرفي كرد.

 

استرتژي هاي پويا :

 

 اينگونه الگوريتم ها را مي توان در دو گروه Online و Batch گنجاد، درحالت  Onlineكليه كارها به صورت برخط  زمان بندي مي شوند و هر كار پس از دريافت توسط زمان بند به يكي از منابع سپرده مي شد در حالت Batch كارها به صورت گروهي زمان بندي مي شوند و گروهها با يك وقفه كوتاه به منابع مربوطه سپرده مي شوند.

 

Online-Mode: الگوريتم هاي KPB ,SA, MCT, MET, OLB  در اين گروه قرار مي گيرند.

 

:Batch - Mode الگوریتم های Suffrage, Max-min, Min-Min از اين دسته مي باشند.

با توجه به مواردي كه ذكر شد، در اين مقاله موضوع اختصاص منابع با استفاده از تئوري بازي ها و مذاكره عاملها در يك محيط چند عاملي[35] پيشنهاد مي شود. در مدل پيشنهادي ما هر عامل به دنبال حداكثر كردن ميزان سودمندي مورد انتظار[36] خود است و سرويس دهنده ابري نيز به عنوان محیط[37]  قصد دارد علاوه بر حفظ حالت سيستم در تعادل نش[38] ميزان استفاده[39]  از ابر را به حداكثر برساند.



[1] Complex Interaction

[2] Job

[3] Resource allocation

[4] Unfair

[5] Scheduling

[6] Service Level agreement

[7] QoS

[8] DeadLine

[9] Budjet

[10] Bandwidth

[11] Subtask

[12] Correlated

[13] Scientific workflow

[14] Cost

[15] Utilization

[16] User-Level

[17] System-Level

[18] Provider

[19] Data center

[20] Performance

[21] Utilization

[22] Economic models for Resource-Provisioning

[23] Heuristic Models for task-execution scheduling

[24] Market based

[25] commodity

[26] posted price

[27] Bargaining model

[28] Auction Based

[29] Number of participants

[30] Information transparency

[31] Combinatorial auction

[32] Static

[33] Dynamic

[34] Real time

[35] Multi-Agent

[36] Expected utility

[37] Nature

[38] Nash equilibrium

[39] utilization