دانلود پایان نامه کارشناسی ارشد رشته آی تی
ارائه الگوریتمی تطبیقی مبتنی بر پیش بینی اشکال با استفاده از مدلهای هزینه احتمالی برای زمانبندی در سیستم های رایانش ابری
چکیده
با افزایش بازار استفاده از تکنولوژی محاسبات ابری، مراکز داده عظیمی به وجود آمده اند تا محاسبات را سریع تر انجام دهند. یکی از دغدغه های اصلی در محاسبات ابری، مواجه شدن با اشکال ها در حین اجرا کردن یک برنامه موازی زمان بر است. برای غلبه بر این قبیل مشکلات، عموما از روش های آزمون نقطه مقابله گیری یا آرشیوکردن استفاده می شود. اما این روش ها غالبا سربار بالایی دارند و به صورت واکنشی عمل می کنند.
در این پایان نامه روشی را معرفی می کنیم که علاوه بر بازیافت و بازگشت به عقب برای تحمل پذیری اشکال، بتواند گره های محاسباتی که احتمال وقوع خرابی در آن ها بیشتر است را شناسایی نماید و به صورت پیش کنشی عمل کرده و ماشین های مجازی را که بر روی آن ها قرار دارد به گره های محاسباتی امن تر مهاجرت دهد تا در صورت وقوع اشکال در گره مشکوک برنامه موازی بدون وقفه به کار خود ادامه دهد. علاوه بر آن، در این الگوریتم با بهره گیری از قانون بیز و مدل هزینه پیشنهادی، آزمون نقطه مقابله گیری زائد تا حد امکان حذف شده و زمان اجرای برنامه بهبود خواهد یافت. با استفاده ازشبیه سازی نشان می دهیم که روش پیشنهادی بسته به شرایط مختلف تا 78% زمان اجرا را بهبود می بخشد و از منابع کمتری استفاده می کند.
واژه های کلیدی:
قانون بیز
پیش کنشی
پیش بینی اشکال
مدل مبتنی بر هزینه
سیستم های محاسبات ابر
آزمون نقطه مقابله گیری هماهنگ
مقدمه
جهان محاسباتی که امروزه با آن روبرو هستیم روز بهروز در حال بزرگ تر و پیچیدهتر شدن است. محاسبات ابری نیز در ادامه سبکهای دیگر مانند محاسبات توری با هدف پردازش حجم عظیمی از داده با استفاده از خوشههایی از کامپیوترهاست. طبق گراش ارائه شده ای از گوکل، در حال حاضر به لطف محاسبات توزیع شده روزانه بیش از 20 ترابایت داده خام اینترنتی مورد پردازش قرار میگیرد. تکامل و شکلگیری محاسبات ابری خواهد توانست این چنین مسائلی را به راحتی و به شکلی مناسبتر از طریق سرویسهای مبتنی بر تقاضا حل و فصل نماید. از زاویه دیگر، جهان محاسباتی اطراف ما در حال حرکت به سمت الگوهای "پرداخت برای استفاده" حرکت میکند و همین الگو یکی دیگر از پایههای اصلی محاسبات ابری محسوب میشود.
محاسبات ابری که در اواخر سال 2007 پا به عرضه ظهور گذاشت هم اکنون به دلیل تواناییاش در ارائه زیر ساخت فناوری پویا و بسیار منعطف، محیطهای محاسباتی تصمین شده از نظر کیفیت و همچنین سرویسهای نرمافزاری قابل پیکر بندی به موضوع داغ بدل شده است .
فهرست مطالب
1کلیات:
2قابلیت دسترسی بالا9
2-1مفاهیم پایه قابلیت دسترسی بالا9
2-1-1تعریف قابلیت دسترسی بالا9
2-1-2مفاهیم و مباحث مرتبط با قابلیت دسترسی بالا10
2-1-3معیارهای سنجش قابلیت دسترسی12
2-1-4سطوح قابلیت دسترسی بالا13
2-1-5توقف برنامهریزی شده و توقف برنامهریزی نشده14
2-1-6عوامل مؤثر بر میزان دسترسی سیستم16
2-2دستیابی به قابلیت دسترسی بالا در سیستمهای كلاستر16
2-2-1تعریف نقاط منفرد بروز خرابی17
2-2-2از بین بردن نقاط منفرد بروز خرابی در اجزای سختافزاری17
2-2-3از بین بردن نقاط منفرد بروز اشكال در اجزای نرمافزاری23
2-2-4تشخیص دهندۀ خرابی در كلاسترهای با قابلیت دسترسی بالا25
2-2-5معماری کلاسترهای با قابلیت دسترسیبالا26
2-2-6اتصالات و شبکه کلاستر28
2-2-7مدیریت و نظارت بر کلاستر28
2-2-8تصویر یکپارچه سیستم (SSI)33
3روالهای تحملپذیر اشکال برای رسیدن به قابلیت دسترسی بالا در سیستمهای مبادله پیام36
3-1پیشزمینه و تعاریف38
3-1-1مدل سیستم38
3-1-2حالتهای سیستم یكپارچه39
3-1-3تعامل با دنیای خارج40
3-1-4پیام در حال گذر41
3-1-5قراردادهای ثبت وقایع42
3-1-6ذخیرهساز پایدار43
3-1-7جمعآوری دادههای زائد44
3-2بازیافت براساس نقطه مقابله44
3-2-1نقطه مقابله گرفتن به صورت غیرهماهنگ45
3-2-2نقطه مقابله گرفتن به صورت هماهنگ48
3-2-3نقطه مقابله گرفتن بر اساس ارتباطات51
3-3بازیافت بر اساس ثبت وقایع54
3-3-1شرط یكپارچگی بدون پروسههای یتیم55
3-3-2ثبت بدبینانه وقایع56
3-3-3ثبت خوشبینانه وقایع59
3-3-4ثبت علّی وقایع61
3-3-5مقایسه قراردادهای بازیافت63
3-4مباحث مطرح در پیادهسازی63
3-4-1بررسی63
3-4-2پیادهسازی تکنیکهای نقطه مقابله گرفتن64
3-4-3مقایسة قراردادهای نقطه مقابله گرفتن66
3-4-4قراردادهای ارتباطی66
3-4-5بازیافت بر اساس روش ثبت وقایع67
3-4-6ذخیرهساز پایدار67
3-4-7دنبال كردن وابستگی68
3-4-8بازیافت69
4کارهای انجام شده اخیر71
4-1مروری بر روشهای پیشبینی اشکال72
4-1-1کلاسه بندی و اشکالهای ریشه آماری72
4-1-2مدل آماری زمان میان خرابیها73
4-1-3جمعآوری و پیشپردازش دادههای مرتبط با خرابی73
4-2تکنیکهای پیشبینی اشکال74
4-2-1حدآستانه مبتنی بر آمار74
4-2-2آنالیز سریهای زمانی75
4-2-3کلاسهبندی مبتنی بر قانون75
4-2-4مدلهای شبکه بیزی76
4-2-5مدلهای پردازش شبه مارکوف76
4-3مطالعات انجام گرفته77
5روش پیشنهادی86
5-1مدل اشکال86
5-1-1متوسط زمانی تا خرابی89
5-2مبانی احتمال و پیشبینی91
5-2-1مفاهیم اولیه91
5-2-2رابطه قانون بیز و احتمال درستی پیشبینی92
5-3رابطه الگوریتم پیشبینی و مدل اشکال94
5-3-1تحلیل روابط احتمالی94
5-4مدل پیشنهادی97
5-4-1ارائه الگوریتم100
5-4-2مدل مبتنی بر هزینه101
5-4-3اثر پیشبینیکننده بر روی مدلهای هزینه105
5-4-4تصمیمگیری سیستم در کارگزار ابر106
6نتایج آزمایشها109
6-1معرفی شبیهساز CloudSim109
6-1-1اجزای ابر109
6-1-2اجزای اصلی هسته111
6-1-3سرویسهای موجود و الگوریتمهای آنها114
6-1-4روند کار شبیهساز115
6-2نحوه پیادهسازی سیستم تحملپذیر اشکال در شبیهساز116
6-2-1FaultInjector117
6-2-2FaultPredictor120
6-2-3FTHost121
6-2-4FTDatacenter121
6-2-5FTDatacenterBroker122
6-3نتایج آزمایشات124
6-3-1بررسی اثر سربار نقطه مقابلهگیری126
6-3-2بررسی عملهای انتخابی127
6-3-3خرابیهای متوقف سازنده و غیر متوقف سازنده129
7نتیجه گیری و پیشنهادات132
منابع133
فهرست شکل ها
شکل 1 1رویکرد یه تکنولوژیهای مختلف محاسبات توزیع شده [1]3
شکل 2 1 سهم عوامل مختلف در از کارافتادگی سیستم HA [11]16
شکل 2 2 برخی SPOFها در سیستم سرویسدهنده/سرویسگیرنده18
شکل 2 3 SPOFها در یک شبکه اترنت نوعی22
شکل 2 4 حذف SPOFهای شبکه به روش افزونگی کامل23
شکل 2 5 نمونهای از تشخیص خرابی با سیگنال ضربان قلب26
شکل 2 6 نمای ساده از نظارت31
شکل 2 7 ارتباط اجزا مختلف EMS31
شکل 3 1 مثالی از یك سیستم مبادله پیام با سه واحد موازی38
شکل 3 2 مثالی از حالت یكپارچه و غیریكپارچه سیستم40
شکل 3 3 پیادهسازی مكانیسمهای بازیافت42
شکل 3 4 ثبت كردن پیام برای اجرای مجدد قطعی43
شکل 3 5 اندیس نقطه مقابله و بازه نقطه مقابله46
شکل 3 6 (a) یك اجرای مثال (b) گراف وابستگی بازگشت به عقب (c) گراف نقطه مقابله47
شکل 3 7 انتشار بازگشت به عقب، خط بازیافت و اثر دومینو48
شکل 3 8 نقطه مقابله گرفتن به صورت هماهنگ و غیربلوكه شونده (a) غیریكپارچگی نقطه مقابله (b) با كانال FIFO (c) با كانال غیرFIFO49
شکل 3 9 مسیر Z سیكل Z52
شکل 3 10 روش ثبت بدبینانه وقایع57
شکل 3 11 روش ثبت خوشبینانه وقایع60
شکل 3 12 روش ثبت علّی وقایع (الف) حالتهای قابل بازیافت حداكثر (ب)گراف مقدم را برای پروسه P0 در حالت X62
شکل 5 1 منحنی وان88
شکل 5 2 نمودار مثبت واقعی، منفی واقعی و دقت پیشبینی95
شکل 5 3 اثر تغییرات MTTF بر روی دقت پیشبینی96
شکل 5 4 اثر حساسیت و ویژگی بر روی دقت پیشبینی97
شکل 5 5 شماتیک خط زمانی نقطه مقابلهگیری هماهنگ دورهای98
شکل 5 6 شماتیک خط زمانی نقطه مقابلهگیری هماهنگ دورهای در برخورد با اشکال99
شکل 5 7 شماتیک خط زمانی الگوریتم تطبیقی پیشنهادی101
شکل 6 1دیاگرام کلی شبیهساز[92]116
شکل 6 2 جریان کار اجزای برنامههای موازی در شبیهساز [92]116
شکل 6 3 نمونهای از محتویات یک فایل سناریوی خرابی گرها در یک مرکز داده118
شکل 6 4 ماشین حالت خرابی یک گره محاسباتی در ابر119
شکل 6 5 تکه کد تغییر وضعیت حالت میزبانهای یک مرکزداده به صورت بهینه120
شکل 6 6 تکه کد پیشبینی وضعیت یک گره محاسباتی در زمان آینده time121
شکل 6 7 در صد بهبود زمان اجرای الگوریتمهای پیشنهادی نسبت به الگوریتم آزمون نقطه مقابلهگیری دورهای کلاسیک126
شکل 6 8 در صد بهبود زمان اجرای الگوریتمهای پیشنهادی نسبت به الگوریتم آزمون نقطه مقابلهگیری دورهای کلاسیک با افزایش زمان نقطه مقابلهگیری به 5 دقیقه127
شکل 6 9 تعداد عملهای انتخابی در طول زمان اجرا با الگوریتم نقطه مقابلهگیری دورهای128
شکل 6 10 تعداد عملهای انتخابی در طول زمان اجرا با الگوریتم تطبیقی اولیه128
شکل 6 11 تعداد عملهای انتخابی در طول زمان اجرا با الگوریتم تطبیقی تصحیح شده129
شکل 6 12 تعداد اشکالهایی که در طول اجرای برنامه سبب توقف یا عدم توقف ابر میشوند130
فهرست جداول
جدول 1 1 قابلیت اطمینان در مراکز داده مختلف[4]5
جدول 2 1 مقایسه کلاسترهای HA و FT [13]11
جدول 2 2 زمانهای توقف و کارکرد یک سیستم 52×7×1214
جدول 2 3 زمانهای توقف و كاركرد یك سیستم 52×5×1214
جدول 3 1 مقایسه بین قراردادهای مختلف بازیابی [47]64
جدول 5 1 رابطه وضعیت محیط و الگوریتم پیشبینی91
جدول 5 2 تعاریف پارامترهای استفاده شده در مدلها102
جدول 5 3 مدل هزینه عمل مهاجرت103
جدول 5 4 مدل هزینه عمل نقطه مقابلهگیری104
جدول 5 5 مدل هزینه عمل اجرای بلافاصل105
جدول 6 1 مقداردهی اولیه متغیرهای شبیهساز125