زمانبندی در شبکه های گرید محاسباتی (سیستم رایانش مشبک)

چکیده

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

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

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

طبقه بندی زمانبندها­ی پیشین

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

• پارتیشن بندی کار
• جمع آوری اطلاعات
• انتساب وظایف به نودها
• آغاز اجرای وظایف

پارتیشن بندی کار عبارت است از تقسیم یک کار به وظایف آن . به طور کلی کارهای موازی را می توان به دو گروه تقسیم کرد :1. انعطاف ناپذیر. 2. قالب پذیر.

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