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

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

مسئله زمان بندی کارها به معنای نگاشت و تعیین ترتیب اجرای کارها بر روی منابع موجود است، به گونه ای که یک یا چند معیار کارآیی بهینه شوند. این مسئله جزو مسائل شناخته شده NP-کامل محسوب می گردد.
بنابراین هیچ الگوریتم شناخته شده با مرتبه زمانی چندجمله ای وجود ندارد، که بتواند جواب بهینه ای برای این مسئله پیدا کند. علاوه براین، مسئله زمان بندی در سیستم ابرهای محاسباتی به دلیل برخی از خصوصیات خاص آن همچون ناهمگونی، استقلال، و پویایی منابع، به مراتب پیچیده تر از سیستم های سنتی است. تحقیقات زیادی بر روی مسئله زمان بندی کارها در سیستم ابرهای محاسباتی انجام گرفته که در فصل بعدی برخی از آنها را مورد بررسی قرار خواهیم داد. الگوریتم های زمان بندی ارائه شده به دو دسته اصلی تقسیم می گردند:
الگوریتم های ایستا که عمل زمان بندی را پیش از شروع اجرای برنامه انجام می دهند؛ و الگوریتم های پویا که عمل زمان بندی را در حین اجرای برنامه انجام می دهند. مزیت الگوریتم های ایستا در آن است که می توانند با بهره گرفتن از امکان رزرو پیشاپیش منابع، مانع از ایجاد تاخیر در اجرای کارها گردند. معمولا هدف الگوریتم های ارائه شده حداقل کردن زمان اجرای برنامه است، بدون اینکه هیچ تضمین خاصی در مورد سقف زمان اجرا به کاربر داده شود (زمان بندی حداکثر تلاش). اما مسئله هنگامی پیچیده تر می شود که بحث کیفیت خدمت نیز مطرح گردد. در این مسئله، محیط ابرهای محاسباتی از چندین عرضه کننده تشکیل می گردد که هریک منابعی را در اختیار کاربران قرار می دهند. هریک از این منابع قادرند یک یا چند کار را با کیفیت خدمت متفاوت (همانند زمان اجرا، امنیت و قیمت متفاوت) اجرا نمایند. در زمان بندی مبتنی بر کیفیت خدمت، زمان بند باید به گونه ای عمل کند که حداقل کیفیت خدمت موردنیاز کاربر برآورده شود. اما نکته مهم در این است
که کاربر معمولا کیفیت خدمت موردنیاز برای هر کار به تنهایی را مشخص نمی نماید، بلکه کیفیت خدمت کل کارها را تعیین می نماید. به عنوان مثال، کاربر مایل است که کارهای وی قبل از مهلت معین و با حداقل قیمت اجرا شود. اکنون زمان بند باید با توجه به زمان اجرا و قیمت پیشنهادی هر منبع برای هریک از کارها، منابع را به گونه ای انتخاب کند که کل کار در مهلت تعیین شده پایان یابد و قیمت نیز حداقل گردد. نکته ای که به پیچیدگی مسئله می افزاید این است که نحوه محاسبه کیفیت خدمت کل برنامه از روی کیفیت خدمت هر کار برای معیارهای مختلف، متفاوت است. به عنوان مثال برای قیمت برابر با حاصل جمع قیمت کارها، برای زمان اجرا برابر با زمان طولانی ترین مسیر بین کار ابتدایی و پایانی (مسیر بحرانی) برنامه، و برای قابلیت اطمینان برابرحاصل ضرب قابلیت اطمینان هر کار است. همان طور که قبلا نیز اشاره شد، این مسئله جزو مسائل چند هدفه یا چند معیاری می باشد و به دلیل پیچیدگی مسئله، الگوریتم های چندانی برای آن پیشنهاد نشده است. علاوه براین، اکثر محققین از روش های فوق ابتکاری همانند الگوریتم های ژنتیک برای حل آن استفاده کرده اند که زمان اجرای آنها معمولا طولانی است. اما به دو دلیل برای حل این مسئله نیاز به الگوریتم هایی داریم که زمان اجرای کوتاهی داشته باشند. دلیل اول آن است که در محیط های پویا همانند سیستم های ابرهای محاسباتی، وضعیت منابع به سرعت تغییر می کند. بنابراین چنانچه زمان اجرای الگوریتم زمان بندی بالا باشد، ممکن است در این مدت وضعیت بسیاری از منابع تغییر کرده و از دسترس خارج شده باشند. دلیل دیگر آن است که معمولا زمان اجرای کارها یکی از پارامترهای مهم کیفیت خدمت برای کاربران است، و در بسیاری از موارد مهلت زمانی مشخصی برای اجرای برنامه وجود دارد. لذا بالا بودن زمان اجرای الگوریتم زمان بندی، باعث بالا رفتن زمان کل اجرای برنامه می شود که ممکن است باعث اجرا نشدن برنامه در مهلت مقرر شود. بنابراین به نظر می رسد برای حل این مسئله باید به دنبال الگوریتم های ابتکاری با مرتبه زمانی مناسب، و زمان اجرای کوتاه باشیم. از طرف دیگر، بسیاری از محققین از مدل زمان بندی ایستا برای زمان بندی مبتنی بر کیفیت خدمت استفاده کرده اند. با توجه به اینکه رزرو پیشاپیش منابع روش مناسبی برای تضمین کیفیت خدمت موردنیاز کاربران می باشد، به نظر می رسد زمان بندی ایستا کارآیی بهتری برای زمان بندی مبتنی بر کیفیت خدمت داشته باشد.
۱-۲ اهمیت موضوع تحقیق
الگوریتم های زیادی برای زمان بندی کارها در بسیاری از زمینه های مختلف پژوهشی مطرح شده است، در حالی که فقط چند مورد از آنها زمینه مطرح شده را پوشش می دهد.
اغلب روش‌های بهینه‌سازی عام مطرح شده، شبیه‌سازی کامپیوتری فرایند‌های طبیعی هستند. شاید یک دلیل برای این کار، ملموس بودن و سادگی فرموله کردن و درک تکامل این فرایند‌ها است. در نقطه مقابل، در ارائه‌ الگوریتم‌های بهینه‌سازی، علی‌رغم توجه به تکامل زیستی انسان و سایر موجودات (الگوریتم‌های ژنتیک)، به تکامل اجتماعی وتاریخی او به عنوان پیچیده‌ترین و موفق‌ترین حالت تکامل، توجه چندانی نشده‌ است. در این تحقیق، نو بودن ایده‌ی پایه‌ای و هوشمندانه تر بودن الگوریتم رقابت استعماری نسبت به رفتار بیولوژیکی (الگوریتم ژنتیک) و توانایی بهینه‌سازی هم‌تراز و حتی بالاتر در مقایسه با الگوریتم‌های مختلف بهینه‌سازی، سرعت مناسب یافتن جواب بهینه، سرعت همگرایی بالا و توانایی بهینه سازی با تعداد متغیرهای بسیار زیاد این الگوریتم، باعث می شود تا در این تحقیق از آن، برای بهینه سازی زمان بندی کارهای بلادرنگ در محیط ابرهای محاسباتی استفاده شود.]۳۰[
۱-۳ تعریف مسئله
محیط ابرهای محاسباتی از چندین عرضه کننده تشکیل می گردد که هریک منابعی را در اختیار کاربران قرار می دهند. در این تحقیق با بهره گرفتن از الگوریتم رقابت استعماری جهت نگاشت کارها به منابع، الگوریتمی برای زمان بندی کارهای بلادرنگ^[۸] از نوع نرم^[۹] در محیط ابرهای محاسباتی طراحی می گردد که بتواند برنامه را در کمترین زمان ممکن، پیش از مهلت تعیین شده و با بهره گرفتن از کمترین تعداد منابع اجرا نماید.
۱-۴ اهداف تحقیق
هدف از این تحقیق، استفاده از توانایی های الگوریتم رقابت استعماری با توجه به سرعت مناسب آن در یافتن پاسخ بهینه، برای زمان بندی کارهای بلادرنگ نرم در محیط ابرهای محاسباتی می باشد که بتواند برنامه را در کمترین زمان ممکن، پیش از مهلت تعیین شده و با بهره گرفتن از کمترین تعداد منابع اجرا نماید.
۱-۵ محدوده تحقیق
این تحقیق در زمینه زمان بندی کارهایی از نوع بلادرنگ نرم در محیط ابرهای محاسباتی صورت خواهد گرفت.
۱-۶ ساختار کلی پایان نامه
در این پایان نامه ابتدا ادبیات موضوع و مفاهیم مرتبط از جمله ابرهای محاسباتی، زمان بندی کارها، الگوریتم های زمان بندی ارائه شده در ابرهای محاسباتی و الگوریتم رقابت استعماری بیان می شود، سپس زمان بندی کارهای مستقل بلادرنگ بر اساس الگوریتم رقابت استعماری را در محیط ابرهای محاسباتی پیاده سازی کرده و در نهایت، مقایسه ای در شرایط یکسان، با راهکارهایی که بر اساس الگوریتم ژنتیک بوده]۱[ انجام می گردد .
فصل دوم
ادبیات و پیشینه ی تحقیق
۲-۱ مقدمه
سیستم های توزیع شده^[۱۰] و تکنیک های پردازش موازی، از جمله راه حل های استفاده ی بهتر و سریع تر از دنیای حجیم و پیچیده اطلاعات عصر حاضر می باشد. امروزه صد ها رایانه و ابر رایانه با ظرفیت ها و معماری های گوناگون در سراسر دنیا وجود دارند که در کاربردهای گوناگون علمی، نظامی، تجاری و غیره از آنها استفاده می شود، و اکثرا لزوم به اشتراک گذاری اطلاعات در میان آنها امری مقتضی است. یک سیستم توزیع شده مجموعه ای است از کامپیوتر های مستقل که در نظر کاربران به صورت یک سیستم منسجم واحد به نظر می آید و می بایست دارای دو ویژگی اصلی باشد: خودمختاری و شفافیت توزیع. خودمختاری به معنی مدیریت جداگانه هر گره^[۱۱] در عین تعامل آن با سایر گره ها می باشد، به نحوی که سیاست های مدیریت یا اختلال در هر گره برروی سایر گره ها تاثیر نگذارد. شفافیت توزیع، تصور تک واحد بودن سیستم را برای کاربران بوجود می آورد که خود شامل شفافیت در مباحثی نظیر دسترسی، مکان، مهاجرت، تغییر مکان منبع، تکرار، همروندی و خطا می باشد]۸[.
ابرهای محاسباتی از مجموعه رایانه های عظیم متصل به اینترنت تشکیل شده است و راهکاری انعطاف پذیر برای رفع نیاز بسیاری از برنامه های کاربردی است]۲۳[.
یکی از چالش برانگیزترین مسائل در ابرها استراتژی زمان بندی^[۱۲] یا اختصاص منابع به درخواست های سیستم می باشد. دلایل متعددی از جمله ناهمگون بودن و پویایی خصوصیات منابع و درخواست ها در محیط ابرهای محاسباتی موجب شده که این موضوع به عنوان یک مسئله ی NP-کامل^[۱۳] نمود پیدا کند.
۲-۲ ابرهای محاسباتی
ابرهای محاسباتی الگویی از محاسبات توزیع شده، مرکب از تعداد زیادی منابع و درخواست ها با هدف به اشتراک گذاری منابع به صورت سرویس، بروی بستر اینترنت می باشد]۳۱[.
ساختار اصلی ابرهای محاسباتی سیستم هایی با توان محاسباتی بالا، مراکز داده ها، رسانه های ذخیره سازی، بستر های نرم افزاری^[۱۴] و خدمات نرم افزاری است که روی اینترنت به کاربر ارائه می شود]۲۴ .[سطوح خدمات رسانی ابرهای محاسباتی به سه سطح تقسیم می شود. خدمات به صورت نرم افزاری(Saas)^[15]، خدمات به صورت بستر های نرم افزاری(Paas)^[16]، خدمات به صورت زیر ساختی(Iaas)^[17].
۲-۲-۱ تعریف
با پیشرفت فناوری اطلاعات نیاز به انجام کارهای محاسباتی در همه جا و همه زمان به وجود آمده است. همچنین نیاز به این هست که افراد بتوانند کارهای محاسباتی سنگین خود را بدون داشتن سخت افزارها و نرم افزارهای گران، از طریق خدماتی انجام دهند. ابرهای محاسباتی آخرین پاسخ فناوری به این نیازها بوده است.
ابر محاسباتی مدلی است برای فراهم کردن دسترسی آسان بر اساس تقاضای کاربر از طریق شبکه به مجموعه ای از منابع محاسباتی قابل تغییر و پیکربندی )مثل: شبکه ها، خادم ها^[۱۸]، فضای ذخیره سازی، برنامه های کاربردی و سرویس ها( که این دسترسی بتواند با کمترین نیاز به مدیریت منابع و یا نیاز به دخالت مستقیم فراهم کننده سرویس به سرعت فراهم شده یا آزاد گردد]۳۱[.
۲-۲-۲ تاریخچه
پیدایش مفاهیم اساسی ابر محاسباتی به دهه ۱۹۶۰ بازمی گردد. زمانی که جان مک کارتی^[۱۹] اظهار داشت که محاسبات ممکن است روزی به عنوان یکی از صنایع همگانی، سازماندهی شود. تقریبا تمام ویژگی های امروز ابرهای محاسباتی (منابع انعطاف پذیر^[۲۰]، ارائه به صورت یک صنعت همگانی، برخط بودن و توهم دسترسی به عرضه نامحدود) به همراه مقایسه با صنعت برق و شکلهای مصرف عمومی و خصوصی و دولتی و انجمنی را پارک هیل داگلاس^[۲۱] در کتابی که با عنوان مشکل صنعت همگانی رایانه در سال ۱۹۶۶ مورد بررسی قرار داد. واژه ابر در واقع بر گرفته از صنعت تلفن است به این گونه که کمپانی های ارتباطات راه دور که تا دهه ۱۹۹۰ تنها خطوط نقطه به نقطه اختصاصی ارائه می کردند، شروع به ارائه شبکه های خصوصی مجازی با کیفیتی مشابه و قیمت های کمتر نمودند. نماد ابر برای نمایش نقطه مرزی بین بخش هایی که در حیطه مسئولیت کاربرند و آن هایی که در حیطه مسئولیت عرضه کننده بکار گرفته می شد. ابر محاسباتی مفهوم ابر را به گونه ای گسترش می دهد که خادم ها را نیز علاوه بر زیرساخت های شبکه در بر گیرد]۹.[
۲-۲-۳ معماری ابرهای محاسباتی
معماری سامانه های نرم افزاری دست اندر کار در ارائه ابرهای محاسباتی عموما شامل اجزایی است که با یکدیگر از طریق رابط برنامه نویسی نرم افزار و معمولاَ وب سرویس ارتباط برقرار می کنند.
این طراحی شباهتی با فلسفه یونیکس دارد که در آن چند برنامه مختلف که هر یک کاری را به خوبی انجام می دهند، با یکدیگر از طریق واسط های جهانی کار می کنند. پیچیدگی کنترل می شود و سامانه های حاصل، مدیریت پذیرتر از همتاهای یکپارچه خود هستند.
شکل۲-۱ دید کلی از معماری ابرهای محاسباتی را نمایش می دهد.
شکل۲-۱ معماری ابر محاسباتی]۸[
لایه منابع فیزیکی^[۲۲]: مدیران ارائه دهنده ی سرویس های ابرهای محاسباتی نیاز به ارتباط با حجم عظیمی از خوشه ها و رسانه های ذخیره سازی دارند، از این رو از تجهیزات شبکه ای براساس ساختار توپولوژی مناسب جهت ایجاد مرکز داده های این محیط بهره می برند.
لایه منابع مجازی^[۲۳]: توسط تکنولوژی مجازی سازی، استخری از منابع مجازی را توسط منابع سخت افزاری لایه فیزیکی، ایجاد می کنند که بر اساس نیاز درخواست های کاربران با حفظ درجه بالایی از اشتراک به آنها اختصاص می یابد.
لایه مدیریت سکو^[۲۴]: مدیریت سکو شامل، مدیریت منابع، مدیریت درخواست ها، مدیریت کاربران و مدیریت امنیت می باشد.
لایه سرویس های کاربردی^[۲۵]: در کنار استفاده از سرویس های محاسباتی و ذخیره سازی، از سرویس های بستر های نرم افزاری و برنامه ها و نرم افزارها نیز به صورت برخط می توان بهره مند گردید.
سرویس ها در محیط ابرهای محاسباتی در سه سطح ارائه می شوند و این تقسیم بندی، امکان پشتیبانی از مدیریت متفاوت برای هر سطح، و همچنین تکنولوژی مجازی سازی را موجب می شود. در محیط ابر، محاسبات بروی استخری از منابع پویا و مجازی به صورت بر خط^[۲۶] و بر اساس نیاز کاربران اختصاص می یابند.]۱۰[
معماری IaaS ( Insfractructure as a Service )، زیر ساخت رایانه ای که به طور بستر مجازی است به صورت سرویس ارائه می شود .
معماری PaaS ( Platform as a Service )، یک لایه از نرم افزار را ارائه می دهند .
معماری SaaS ( Software as a Service )، نرم افزار را به صورت سرویس روی اینترنت قرار می دهند .
۲-۲-۴ مدل های پیاده سازی ابرهای محاسباتی
روش های پیاده سازی ابرهای محاسباتی را می توان به سه مدل ابر عمومی^[۲۷]، ابر خصوصی(داخلی)^[۲۸]، ابر ترکیبی(آمیخته)^[۲۹] تقسیم کرد]۱۰[.
ابر عمومی یا ابر خارجی: توصیف کننده ابرهای محاسباتی در معنای اصلی و سنتی آن است. سرویس ها به صورت پویا^[۳۰] و از طریق اینترنت و در واحدهای کوچک از یک عرضه کننده شخص ثالث تدارک داده می شوند و عرضه کننده، منابع را به صورت اشتراکی به کاربران اجاره می دهد.
ابر خصوصی: یک زیر ساخت از ابرهای محاسباتی است که توسط یک سازمان برای استفاده داخلی آن سازمان به وجود آمده است.
ابر آمیخته: متشکل از چندین ارائه دهنده داخلی و یا خارجی، گزینه مناسبی برای بیشتر مؤسسات تجاری می باشد.