ارائه الگوریتمی تطبیقی مبتنی بر پیش بینی اشکال با استفاده از مدلهای هزینه احتمالی برای زمانبندی در سیستم های رایانش ابری

رشته فناوری اطلاعات (IT)
دانلود پایان نامه کارشناسی ارشد رشته آی تی ارائه الگوریتمی تطبیقی مبتنی بر پیش بینی اشکال با استفاده از مدلهای هزینه احتمالی برای زمانبندی در سیستم های رایانش ابری چکیده با افزایش بازار استفاده از تکنولوژی محاسبات ابری، مراکز داده عظیمی به وجود آمده اند تا محاسبات را سریع تر انجام دهند. یکی از دغدغه های اصلی در محاسبات ابری، مواجه شدن با اشکال ها در حین اجرا کردن یک برنامه موازی زمان بر است. برای غلبه بر این قبیل مشکلات، عموما از روش های آزمون نقطه مقابله گیری یا آرشیوکردن استفاده می شود. اما این روش ها غالبا سربار بالایی دارند و به صورت واکنشی عمل می کنند. در این پایان نامه روشی را معرفی می کنیم که علاوه بر بازیافت و بازگشت به عقب برای تحمل پذیری اشکال، بتواند گره های محاسباتی که احتمال وقوع خرابی در آن ها بیشتر است را شناسایی نماید و به صورت پیش کنشی عمل کرده و ماشین های مجازی را که بر روی آن ها قرار دارد به گره های محاسباتی امن تر مهاجرت دهد تا در صورت وقوع اشکال در گره مشکوک برنامه موازی بدون وقفه به کار خود ادامه دهد. علاوه بر آن، در این الگوریتم با بهره گیری از قانون بیز و مدل هزینه پیشنهادی، آزمون نقطه مقابله گیری زائد تا حد امکان حذف شده و زمان اجرای برنامه بهبود خواهد یافت. با استفاده ازشبیه سازی نشان می دهیم که روش پیشنهادی بسته به شرایط مختلف تا 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 معرفی شبیه‌ساز CloudSim 109 6-1-1 اجزای ابر 109 6-1-2 اجزای اصلی هسته 111 6-1-3 سرویس‌های موجود و الگوریتم‌های آن‌ها 114 6-1-4 روند کار شبیهساز 115 6-2 نحوه پیادهسازی سیستم تحمل‌پذیر اشکال در شبیهساز 116 6-2-1 FaultInjector 117 6-2-2 FaultPredictor 120 6-2-3 FTHost 121 6-2-4 FTDatacenter 121 6-2-5 FTDatacenterBroker 122 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 ارتباط اجزا مختلف EMS 31 شکل ‏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) با كانال غیرFIFO 49 شکل ‏3 9 مسیر Z سیكل Z 52 شکل ‏3 10 روش ثبت بدبینانه وقایع 57 شکل ‏3 11 روش ثبت خوشبینانه وقایع 60 شکل ‏3 12 روش ثبت علّی وقایع (الف) حالتهای قابل بازیافت حداكثر (ب)گراف مقدم را برای پروسه P0 در حالت X 62 شکل ‏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 تکه کد پیش‌بینی وضعیت یک گره محاسباتی در زمان آینده time 121 شکل ‏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×12 14 جدول ‏2 3 زمان‌های توقف و كاركرد یك سیستم 52×5×12 14 جدول ‏3 1 مقایسه بین قراردادهای مختلف بازیابی [47] 64 جدول ‏5 1 رابطه وضعیت محیط و الگوریتم پیشبینی 91 جدول ‏5 2 تعاریف پارامترهای استفاده شده در مدلها 102 جدول ‏5 3 مدل هزینه عمل مهاجرت 103 جدول ‏5 4 مدل هزینه عمل نقطه مقابلهگیری 104 جدول ‏5 5 مدل هزینه عمل اجرای بلافاصل 105 جدول ‏6 1 مقداردهی اولیه متغیرهای شبیهساز 125