پایان نامه زمان بندی کار در محاسبات ابری

پایان‌نامه برای دریافت درجه کارشناسی ارشد در رشته مهندسی کامپیوتر

 گرایش  نرم‌افزار

چکیده :

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

فصل یک

کلیات تحقیق

مقدمه

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

۱-۲ بیان مسله

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

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

۱-۳ اهمیت و ضرورت تحقیق

۱-۳-۱ سیستم عامل

سیستم‌عامل یا سامانه عامل : نرم‌افزاری است که مدیریت منابع رایانه را به عهده گرفته و بستری را فراهم می‌سازد که نرم‌افزار کاربردی اجرا شده و از خدمات آن استفاده کنند. سیستم‌عامل جزء ضروری‌ترین نرم‌افزارهای یک سیستم کامپیوتری است. سیستم‌عامل خدماتی به برنامه‌های کاربردی و کاربر ارائه می‌دهد. برنامه‌های کاربردی یا از طریق واسط‌ های برنامه نویسی کاربردی[1] و یا از طرق فراخوانی‌های سیستم به این خدمات دسترسی دارند. با فراخوانی این واسط‌ها، برنامه‌های کاربردی می‌توانند سرویسی را از سیستم‌عامل درخواست کنند، پارامترها را انتقال دهند، و پاسخ عملیات را دریافت کنند. ممکن است کاربران با بعضی انواع واسط کاربری نرم‌افزار مثل واسط خط فرمان یا یک واسط گرافیکی کاربر با سیستم‌عامل تعامل کنند. برای کامپیوترهای دستی و رومیزی، عموماً واسط کاربری به عنوان بخشی از سیستم‌عامل در نظر گرفته می‌شود. در سیستم‌های بزرگ و چند کاربره مثل یونیکس و سیستم‌ های شبیه یونیکس، واسط کاربری معمولاً به عنوان یک برنامه کاربردی که خارج از سیستم‌عامل اجرا می‌شود پیاده‌سازی می‌شود. نمونه‌هایی از محبوب‌ترین سیستم‌ عامل‌های نوین شامل اندروید ، بی‌اس‌دی، آی‌اواس، لینوکس، اواس ده، کیوان‌اکس، مایکروسافت ویندوز، ویندوز فون و زدواس می‌باشند.

نظریه‌ ها و الگوریتم‌ های موجود سعی خود را کردند تا بتوانند یک تعادلی ما بین منابع مورد استفاده و مصرف انرژی و کارایی بالاتر ایجاد نمایند ولی هیچ یک از الگوریتم‌ها و روش‌ها نتوانستند کارایی خیلی بالا با مصرف انرژی خیلی پایین دست یابند  . هر دیتاسنتر معمولی به صورت میانگین در خدود ۲۵۰۰۰  سیستم خانگی انرژی مصرف می‌کند و از سمتی دیگر نمی‌توان درخواست‌های کاربران را با تأخیر و یا اینکه به صورت ناقص اجرا نمود . تعادل بین موارد بالا به احتصاب قابلیت اطمینان پذیری سیستم و امنیت آن‌ها موضوعی شده تا همه دنبال راه حلی باشند که بتوان راهی برای اینکه همه موارد را تغریبا کنارهم داشت تلاش کنند  و راه حلی مناسب ارائه دهند تا بتوان از کمترین منابع بیشترین بازدهی را داشت .

۱-۳-۲ انواع سیستم عامل‌ها[2]

       سیستم‌عامل بی‌درنگ[3]

سیستم‌ های بی درنگ یا زمان واقعی یک سیستم عامل چند وظیفه‌ای است که معمولاً بعنوان یک کنترل کننده در یک کاربرد خاص استفاده می‌شوند. سیستم در این حالت می‌بایست در زمانی مشخص و معین حتماً جواب مورد نظر را بدهد. سیستم‌های کنترل آزمایش‌های علمی، تصویربرداری پزشکی، کنترل صنعتی و برخی از سیستم‌های نمایش از این دسته‌اند. هدف اصلی استفاده از سیستم‌ های بی‌درنگ واکنش سریع و تضمین شده در برابر یک رویداد خارجی می‌باشد. در سیستم‌ های بی‌درنگ معمولاً وسایل ذخیره‌سازی ثانویه وجود ندارد و به جای آن از حافظه‌های ROM استفاده می‌شود. سیستم‌عامل‌ های پیشرفته نیز در این سیستم‌ها وجود ندارند چرا که سیستم‌عامل کاربر را از سخت‌افزار جدا می‌کند و این جداسازی باعث عدم قطعیت در زمان پاسخ‌گویی می‌شود. سیستم‌هایی که در آن مهلت زمانی[4] باید پاسخ داده شود را بی‌درنگ سخت و سیستم‌هایی که مهلت زمانی را پشتیبانی نمی‌کنند بی‌درنگ نرم می‌نامند. از کاربرد سیستم‌های بی‌درنگ سخت می‌توان به کنترل موتور یک خودرو(پاسخ با تأخیر می‌تواند نتایج فاجعه‌باری را به همراه داشته باشد) و در سیستم‌های بی‌درنگ نرم می‌توان به اسکن بارکد در پایانه فروشگاه(با اینکه سرعت پاسخ‌دهی باید سریع باشد اما به حادّی سیستم‌های سخت نمی‌باشد) اشاره کرد

در سال ۲۰۱۲ دو نفر به نام‌های Shamsollah Ghanbari  Mohamed Othman ,  الگوریتمی را پیشنهاد دادند به نام PJSC  به نام  A Priority based Job Scheduling Algorithm in Cloud Computing که بر اساس اولویت کارها را دسته بندی می‌کند و این الگوریتم به گفته خودشان چندیدن معیار مختلف را برای تصمیم گیری لحاظ می‌کند.

 سیستم‌ عامل چند کاربره

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

 سیستم‌عامل تک پردازنده

این نوع سیستم‌عامل‌ها، سیستم‌عامل‌های نسل چهار (نسل فعلی) هستند که بر روی یک پردازنده اجرا می‌شوند.از قبیل XP,Vista,۹۸,Me که بیشتر محصول شرکت مایکرو سافت می‌باشند.

سیستم‌عامل شبکه‌ای

سیستم عامل‌هایی مثل ناول نت که بیشترین استفاده و امکانات این سیستم عامل برای شبکه می‌باشد

         سیستم‌های عامل توزیع شده

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

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

۱-۳-۳ زمان‌بندی کار در سیستم عامل

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

الف- دراز مدت[5]

ب– کوتاه مدت[6]

ج – میان مدت

زمان‌بندی دراز مدت

در یک سیستم دسته‌ای پردازش‌های بیشتری نسبت به آنچه فوراً می‌توانند اجرا شوند تحویل داده می‌شوند . این پردازش‌ها در دیسک نگهداری می‌شوند .زمان‌بندی دراز مدت یازمانبندی کار [7]پروسسهایی را انتخاب کرده و آن‌ها را برای اجرا از دیسک به حافظه اصلی می‌آورد.

زمان‌بندی کوتاه مدت

زمانبند کوتاه مدت (یا زمانبند CPU) از بین پروسس های موجود در حافظه اصلی که آماده اجرا هستند یک را انتخاب کرده و CPU را به آن اختصاص می‌دهد. غالباً زمانبند کوتاه مدت هر صد میلی ثانیه یک بار اجراء می‌شود ولی زمانبند دراز مدت ممکن است هر چند دقیقه یک بار اجرا شود. در واقع زمانبند دراز مدت در جه چند برنامگی  [8]یعنی تعداد پردازش‌های موجود در حافظه را کنترل می‌کند .

زمانبند دراز مدت وقت زایدی برای تصمیم گیری دارد ولی زمانبند کوتاه مدت می‌بایست خیلی سریع تصمیمی گیری کند. زمانبند دراز مدت می‌بایست مخلوط مناسبی از پردازش‌های CPU-limiter و I/O limited را جهت قرار گیری در حافظه انتخاب کند تا کارایی CPU و وسایل I/O بهینه شود. در بعضی سیستم‌ها مثل اغلب سیستم‌های اشتراک زمانی زمانبند دراز مدت وجود ندارد, چرا که هر پردازش در سیستم عامل جدید جهت زمانبند CPU در حافظه گذاشته می‌شود تا زمان پاسخ دهی به برنامه مناسب باشد.

        زمان‌بندی میان مدت :

بعضی سیستم عامل‌ها از زمانبند میان مدت نیز استفاده می‌کنند. بدین ترتیب که گاهی پروسس هایی از حافظه و در واقع از رقابت جهت دریافت CPU حذف شده و به دیسک برده می‌شوند[9] . بدین ترتیب درجه چند برنامگی کاهش می‌یابد . سپس در زمانی دیگر پردازش در سیستم عامل مذکور مجدداً به حافظه آورده شده  و اجرایش از همان نقطه قبلی ادامه می‌یابد, این عملیات به نام مبادله[10] معروف است .

زمان‌بندی CPU به طوری کلی می‌تواند انحصاری غیر قابل پس گرفتن[11] قابل پس گرفتن [12]باشد.