پروپوزال cloud computing (docx) 1 صفحه
دسته بندی : تحقیق
نوع فایل : Word (.docx) ( قابل ویرایش و آماده پرینت )
تعداد صفحات: 1 صفحه
قسمتی از متن Word (.docx) :
دانشکده آموزشهای الکترونیکیپايان‌نامه كارشناسی ارشد در رشته ی مهندسی فناوری اطلاعات(طراحی و تولید نرم افزار)طراحي و پياده سازي يک زمانبندِکار اشکالآگاه در سيستمهاي محاسبات ابريبه کوششروشنک لکی شیرازاستاد راهنماآقای دکتر فرشاد خون جوشاستادان مشاورآقای دکتر غلامحسین دستغیبی فردخانم دکتر منیژه کشتگریاسفند ماه 1391ﺑـﻪ ﻧﺎم ﺧـﺪاﺍﻇﻬﺎﺭﻧﺎﻣــﻪﺍﯾﻨﺠﺎﻧﺐ روشنک لکی شیراز( 897159 )ﺩﺍﻧﺸﺠــﻮی ﺭﺷﺘـــﻪی مهندسی فناوری اطلاعات ﮔﺮﺍﯾش طراحی و تولید نرم افزار، دانشکدﻩی آموزشهای الکترونیکی ﺍﻇﻬﺎﺭﻣﯽﮐﻨﻢ ﮐﻪ ﺍﯾﻦ ﭘﺎﯾﺎﻥ ﻧﺎﻣﻪ ﺣﺎﺻﻞ ﭘﮋوﻫﺶ ﺧﻮﺩﻡ ﺑﻮﺩﻩ و ﺩﺭ ﺟﺎﻫﺎﯾﯽ ﮐﻪ ﺍﺯ ﻣﻨﺎﺑﻊ ﺩﯾﮕﺮﺍﻥ ﺍﺳﺘﻔﺎﺩﻩ ﮐﺮﺩﻩﺍﻡ، ﻧﺸﺎﻧﯽ ﺩﻗﯿﻖ و ﻣﺸﺨﺼﺎﺕ ﮐﺎﻣﻞ ﺁﻥ ﺭﺍ ﻧﻮﺷﺘﻪﺍﻡ. ﻫﻤﭽﻨﯿﻦ ﺍﻇﻬﺎﺭﻣﯽﮐﻨﻢ ﮐﻪ ﺗﺤﻘﯿﻖ و ﻣﻮﺿﻮﻉ ﭘﺎﯾﺎﻥ ﻧﺎﻣﻪﺍﻡ ﺗﮑﺮﺍﺭیﻧﯿﺴﺖ و ﺗﻌﻬﺪ ﻣﯽﻧﻤﺎﯾﻢ ﮐﻪ ﺑﺪوﻥ ﻣﺠﻮﺯ ﺩﺍﻧﺸﮕﺎﻩ ﺩﺳﺘﺎوﺭﺩﻫﺎی ﺁﻥ ﺭﺍ ﻣﻨﺘﺸر ﻧﻨﻤﻮﺩﻩ و ﯾﺎ ﺩﺭ ﺍﺧﺘﯿﺎﺭ ﻏﯿﺮ ﻗﺮﺍﺭ ﻧﺪﻫﻢ. ﮐﻠﯿﻪ ﺣﻘﻮﻕ ﺍﯾﻦ ﺍﺛﺮ ﻣﻄﺎﺑﻖ ﺑﺎ ﺁﯾﯿﻦﻧﺎﻣﻪ ﻣﺎﻟﮑﯿﺖ ﻓﮑﺮی و ﻣﻌﻨﻮی ﻣﺘﻌﻠﻖ ﺑﻪ ﺩﺍﻧﺸﮕﺎﻩ ﺷﯿﺮﺍﺯ ﺍﺳﺖ.ﻧﺎﻡ وﻧﺎﻡ ﺧﺎﻧﻮﺍﺩﮔﯽ :ﺗﺎﺭﯾﺦ و ﺍﻣﻀﺎ:به نام خداطراحي و پياده سازي يک زمانبندِ کار اشکالآگاه در سيستمهاي محاسبات ابريبه کوششروشنک لکی شیرازپایان نامهاﺭﺍﺋﻪ ﺷﺪﻩ ﺑﻪ ﺗﺤﺼﯿﻼﺕ ﺗﮑﻤﯿﻠﯽ ﺩﺍﻧﺸﮕﺎﻩ ﺷﯿﺮﺍﺯ ﺑﻪ ﻋﻨﻮﺍﻥ ﺑﺨﺸﯽ ﺍﺯ ﻓﻌﺎﻟﯿﺖﻫﺎی ﺗﺤﺼﯿﻠﯽ ﻻﺯﻡ ﺑﺮﺍی ﺍﺧﺬ ﺩﺭﺟﻪ ﮐﺎﺭﺷﻨﺎﺳﯽ ﺍﺭﺷﺪﺩﺭ ﺭﺷﺘﻪی: فناوری اطلاعاتاز دانشگاه شیرازشیرازجمهوری اسلامی ایرانارزﻳﺎﺑﻲ ﻛﻤﻴﺘﻪي ﭘﺎﻳﺎنﻧﺎﻣﻪ، ﺑﺎ درﺟﻪي: ------------ دکتر فرشاد خون جوش استادیار بخش مهندسی و علوم کامپیوتر دانشگاه شیراز(رئیس کمیته)-----------------دکتر غلامحسین دسنغیبی فرد استادیار بخش مهندسی و علوم کامپیوتر دانشگاه شیراز-----------------------دکتر منیژه کشتگری استادیار بخش مهندسی کامپیوتر و فناوری اطلاعات دانشگاه صنعتی شیراز----------------ماحصل آموخته هایم را تقدیم می کنم به آنان که مهر آسمانی شان آرام بخش آلام زمینی ام است به استوارترین تکیه گاهم، دستان پرمهر پدرم به پراميدترين نگاه زندگیم، چشمان اميدبخش مادرم که هرچه آموختم در مکتب عشق شما آموختم و هرچه بکوشم قطره ای از دریای بی کران مهربانیتان را سپاس نتوانم بگویم. بوسه بر دستان پرمهرتانكه تمام تجربه های یکتا و زیبای زندگیم، مدیون حضور سبز شماستسپاسگزاریاکنون که این رساله به پایان رسیده است، بر خود لازم می دانم که پس از سپاسگزاری از خدای منان، از استاد راهنمای ارجمندم، جناب آقای دکتر فرشاد خون جوش، استادیار بخش مهندسی و علوم کامپیوتر دانشگاه شیراز، که در مسير انجام اين پروژه از مساعدت‌ها و راهنمايي‌های بي‌شائبه ايشان بهره‌های فراوان بردم، تشکر نمایم. بي‌شک بدون کمک‌های ايشان پيمودن اين راه بسيار سخت مي‌نمود.همچنین از اساتید گرانقدرم، جناب آقای دکتر غلامحسین دسنغیبی فرد استادیار بخش مهندسی و علوم کامپیوتر دانشگاه شیراز و سرکار خانم دکتر منیژه کشتگری استادیار بخش مهندسی کامپیوتر و فناوری اطلاعات دانشگاه صنعتی شیراز که بر من منت نهاده و اساتید مشاور من در این رساله بوده اند سپاسگزارم.روشنک لکی شیرازاسفند ماه 91
چکيدهطراحي و پياده سازي يک زمانبندِکار اشکالآگاه در سيستمهاي محاسبات ابريبه کوششروشنک لکی شیراز
با افزایش بازار استفاده از تکنولوژی محاسبات ابری، مراکز داده عظیمی به وجود آمدهاند تا محاسبات را سریعتر انجام دهند. يکي از دغدغههاي اصلي در محاسبات ابری، مواجهشدن با اشکالها در حين اجرا کردن يک برنامه موازي زمانبر است. براي غلبه بر اين قبيل مشکلات، عموما از روشهاي آزمون نقطهمقابلهگيري يا آرشيوکردن استفاده ميشود. اما اين روشها غالبا سربار بالايي دارند و به صورت واکنشي عمل ميکنند.
در اين پایاننامه روشي را معرفي ميکنيم که علاوه بر بازيافت و بازگشت به عقب برای تحمل پذیری اشکال، بتواند گرههای محاسباتی که احتمال وقوع خرابی در آنها بیشتر است را شناسایی نماید و به صورت پیشکنشی عمل کرده و ماشینهای مجازی را که بر روی آنها قرار دارد به گرههای محاسباتی امنتر مهاجرت دهد تا در صورت وقوع اشکال در گره مشکوک برنامه موازی بدون وقفه به کار خود ادامه دهد. علاوه بر آن، در این الگوریتم با بهرهگیری از قانون بیز و مدل هزینه پیشنهادی، آزمون نقطهمقابلهگيري زائد تا حد امکان حذف شده و زمان اجرای برنامه بهبود خواهد یافت. با استفاده ازشبیهسازی نشان میدهیم که روش پیشنهادی بسته به شرایط مختلف تا 78% زمان اجرا را بهبود میبخشد و از منابع کمتری استفاده میکند.
واژههای کلیدی: سیستمهای محاسبات ابر، پیشبینی اشکال، مدل مبتنی بر هزینه، قانون بیز، پیشکنشی، آزمون نقطهمقابلهگيري هماهنگ ، مهاجرت.
فهرست مطالب
عنوان صفحه
TOC \o "1-3" \h \z \u 1مقدمه PAGEREF _Toc347985971 \h 22قابليت دسترسي بالا PAGEREF _Toc347985972 \h 92-1مفاهيم پايه قابليت دسترسي بالا PAGEREF _Toc347985973 \h 102-1-1تعريف قابليت دسترسي بالا PAGEREF _Toc347985974 \h 102-1-2مفاهيم و مباحث مرتبط با قابليت دسترسي بالا PAGEREF _Toc347985975 \h 112-1-3معيارهاي سنجش قابليت دسترسي PAGEREF _Toc347985976 \h 132-1-4سطوح قابليت دسترسي بالا PAGEREF _Toc347985977 \h 152-1-5توقف برنامه‌ريزي شده و توقف برنامه‌ريزي نشده PAGEREF _Toc347985978 \h 162-1-6عوامل مؤثر بر ميزان دسترسي سيستم PAGEREF _Toc347985979 \h 182-2دستيابي به قابليت دسترسي بالا در سيستمهاي كلاستر PAGEREF _Toc347985980 \h 192-2-1تعريف نقاط منفرد بروز خرابی PAGEREF _Toc347985981 \h 192-2-2از بين بردن نقاط منفرد بروز خرابی در اجزاي سخت‌افزاري PAGEREF _Toc347985982 \h 192-2-3از بين بردن نقاط منفرد بروز اشكال در اجزاي نرم‌افزاري PAGEREF _Toc347985983 \h 282-2-4تشخيص دهندۀ خرابي در كلاسترهاي با قابليت دسترسي بالا PAGEREF _Toc347985984 \h 302-2-5معماري کلاسترهاي با قابليت دسترسيبالا PAGEREF _Toc347985985 \h 322-2-6اتصالات و شبکه کلاستر PAGEREF _Toc347985986 \h 342-2-7مديريت و نظارت بر کلاستر PAGEREF _Toc347985987 \h 342-2-8تصوير يکپارچه سيستم (SSI) PAGEREF _Toc347985988 \h 413روالهای تحمل‌پذیر اشکال برای رسیدن به قابلیت دسترسی بالا در سیستمهای مبادله پیام PAGEREF _Toc347985989 \h 363-1پيشزمينه و تعاريف PAGEREF _Toc347985990 \h 393-1-1مدل سيستم PAGEREF _Toc347985991 \h 393-1-2حالتهاي سيستم يكپارچه PAGEREF _Toc347985992 \h 403-1-3تعامل با دنياي خارج PAGEREF _Toc347985993 \h 423-1-4پيام در حال گذر PAGEREF _Toc347985994 \h 433-1-5قراردادهاي ثبت وقايع PAGEREF _Toc347985995 \h 443-1-6ذخيره‌ساز پايدار PAGEREF _Toc347985996 \h 463-1-7جمع‌آوري داده‌هاي زائد PAGEREF _Toc347985997 \h 473-2بازيافت براساس نقطه مقابله PAGEREF _Toc347985998 \h 483-2-1نقطه مقابله گرفتن به صورت غيرهماهنگ PAGEREF _Toc347985999 \h 483-2-2نقطه مقابله گرفتن به صورت هماهنگ PAGEREF _Toc347986000 \h 533-2-3نقطه مقابله گرفتن بر اساس ارتباطات PAGEREF _Toc347986001 \h 573-3بازيافت بر اساس ثبت وقايع PAGEREF _Toc347986002 \h 623-3-1شرط يكپارچگي بدون پروسه‌هاي يتيم PAGEREF _Toc347986003 \h 633-3-2ثبت بدبينانه وقايع PAGEREF _Toc347986004 \h 643-3-3ثبت خوشبينانه وقايع PAGEREF _Toc347986005 \h 683-3-4ثبت علّي وقايع PAGEREF _Toc347986006 \h 713-3-5مقايسه قراردادهاي بازيافت PAGEREF _Toc347986007 \h 743-4مباحث مطرح در پياده‌سازي PAGEREF _Toc347986008 \h 743-4-1بررسي PAGEREF _Toc347986009 \h 743-4-2پياده‌سازي تکنيکهاي نقطه مقابله گرفتن PAGEREF _Toc347986010 \h 753-4-3مقايسة قراردادهاي نقطه مقابله گرفتن PAGEREF _Toc347986011 \h 773-4-4قراردادهاي ارتباطي PAGEREF _Toc347986012 \h 783-4-5بازيافت بر اساس روش ثبت وقايع PAGEREF _Toc347986013 \h 793-4-6ذخيره‌ساز پايدار PAGEREF _Toc347986014 \h 803-4-7دنبال كردن وابستگي PAGEREF _Toc347986015 \h 813-4-8بازيافت PAGEREF _Toc347986016 \h 824کارهاي انجام شده اخیر PAGEREF _Toc347986017 \h 714-1مروري بر روشهاي پيشبيني اشکال PAGEREF _Toc347986018 \h 724-1-1کلاسه بندي و اشکالهاي ريشه آماری PAGEREF _Toc347986019 \h 734-1-2مدل آماري زمان ميان خرابي‌ها PAGEREF _Toc347986020 \h 744-1-3جمع‌آوري و پيش‌پردازش داده‌هاي مرتبط با خرابي PAGEREF _Toc347986021 \h 744-2تکنيکهاي پيشبيني اشکال PAGEREF _Toc347986022 \h 764-2-1حدآستانه مبتني بر آمار PAGEREF _Toc347986023 \h 764-2-2آناليز سري‌هاي زماني PAGEREF _Toc347986024 \h 764-2-3کلاسه‌بندي مبتني بر قانون PAGEREF _Toc347986025 \h 774-2-4مدل‌هاي شبکه بيزي PAGEREF _Toc347986026 \h 784-2-5مدل‌هاي پردازش شبه مارکوف PAGEREF _Toc347986027 \h 794-3مطالعات انجام گرفته PAGEREF _Toc347986028 \h 805روش پيشنهادي PAGEREF _Toc347986029 \h 865-1مدل اشکال PAGEREF _Toc347986030 \h 865-1-1متوسط زماني تا خرابي PAGEREF _Toc347986031 \h 905-2مبانی احتمال و پیشبینی PAGEREF _Toc347986032 \h 925-2-1مفاهیم اولیه PAGEREF _Toc347986033 \h 925-2-2رابطه قانون بيز و احتمال درستي پيشبيني PAGEREF _Toc347986034 \h 945-3رابطه الگوريتم پيشبيني و مدل اشکال PAGEREF _Toc347986035 \h 965-3-1تحليل روابط احتمالي PAGEREF _Toc347986036 \h 965-4مدل پيشنهادي PAGEREF _Toc347986037 \h 1005-4-1ارائه الگوريتم PAGEREF _Toc347986038 \h 1035-4-2مدل مبتني بر هزينه PAGEREF _Toc347986039 \h 1055-4-3اثر پيش‌بيني‌کننده بر روي مدل‌هاي هزينه PAGEREF _Toc347986040 \h 1105-4-4تصميمگيري سيستم در کارگزار ابر PAGEREF _Toc347986041 \h 1126نتایج آزمایشها PAGEREF _Toc347986042 \h 1096-1معرفی شبیهساز CloudSim PAGEREF _Toc347986043 \h 1096-1-1اجزای ابر PAGEREF _Toc347986044 \h 1106-1-2اجزای اصلی هسته PAGEREF _Toc347986045 \h 1126-1-3سرویس‌های موجود و الگوریتمهای آنها PAGEREF _Toc347986046 \h 1166-1-4روند کار شبیهساز PAGEREF _Toc347986047 \h 1186-2نحوه پیادهسازی سیستم تحمل‌پذیر اشکال در شبیهساز PAGEREF _Toc347986048 \h 1196-2-1FaultInjector PAGEREF _Toc347986049 \h 1216-2-2FaultPredictor PAGEREF _Toc347986050 \h 1246-2-3FTHost PAGEREF _Toc347986051 \h 1266-2-4FTDatacenter PAGEREF _Toc347986052 \h 1266-2-5FTDatacenterBroker PAGEREF _Toc347986053 \h 1276-3نتایج آزمایشات PAGEREF _Toc347986054 \h 1306-3-1بررسی اثر سربار نقطه مقابلهگیری PAGEREF _Toc347986055 \h 1336-3-2بررسی عمل‌های انتخابی PAGEREF _Toc347986056 \h 1346-3-3خرابیهای متوقف سازنده و غیر متوقف سازنده PAGEREF _Toc347986057 \h 1377نتیجه گیری و پیشنهادات PAGEREF _Toc347986058 \h 140منابع PAGEREF _Toc347986059 \h 142
فهرست شکلها
TOC \h \z \c "شکل" شکل 11رویکرد یه تکنولوژی‌های مختلف محاسبات توزیع شده [1] PAGEREF _Toc347719165 \h 3
شکل 21 سهم عوامل مختلف در از کارافتادگی سیستم HA [11] PAGEREF _Toc347719166 \h 16
شکل 22 برخی SPOFها در سیستم سرویسدهنده/سرویسگیرنده PAGEREF _Toc347719167 \h 18
شکل 23 SPOFها در یک شبکه اترنت نوعی PAGEREF _Toc347719168 \h 22
شکل 24 حذف SPOFهای شبکه به روش افزونگی کامل PAGEREF _Toc347719169 \h 23
شکل 25 نمونهای از تشخیص خرابی با سیگنال ضربان قلب PAGEREF _Toc347719170 \h 26
شکل 26 نمای ساده از نظارت PAGEREF _Toc347719171 \h 31
شکل 27 ارتباط اجزا مختلف EMS PAGEREF _Toc347719172 \h 31
شکل 31 مثالی از يك سيستم مبادله پيام با سه واحد موازی PAGEREF _Toc347719173 \h 38
شکل 32 مثالی از حالت يكپارچه و غيريكپارچه سيستم PAGEREF _Toc347719174 \h 40
شکل 33 پياده‌سازي مكانيسمهاي بازيافت PAGEREF _Toc347719175 \h 42
شکل 34 ثبت كردن پيام براي اجراي مجدد قطعي PAGEREF _Toc347719176 \h 43
شکل 35 انديس نقطه مقابله و بازه نقطه مقابله PAGEREF _Toc347719177 \h 46
شکل 36 (a) يك اجراي مثال (b) گراف وابستگي بازگشت به عقب (c) گراف نقطه مقابله PAGEREF _Toc347719178 \h 47
شکل 37 انتشار بازگشت به عقب، خط بازيافت و اثر دومينو PAGEREF _Toc347719179 \h 48
شکل 38 نقطه مقابله گرفتن به صورت هماهنگ و غيربلوكه شونده (a) غيريكپارچگي نقطه مقابله (b) با كانال FIFO (c) با كانال غيرFIFO PAGEREF _Toc347719180 \h 49
شکل 39 مسير Z سيكل Z PAGEREF _Toc347719181 \h 52
شکل 310 روش ثبت بدبينانه وقايع PAGEREF _Toc347719182 \h 57
شکل 311 روش ثبت خوشبينانه وقايع PAGEREF _Toc347719183 \h 60
شکل 312 روش ثبت علّي وقايع (الف) حالتهاي قابل بازيافت حداكثر (ب)گراف مقدم را براي پروسه P0 در حالت X PAGEREF _Toc347719184 \h 62
شکل 51 منحنی وان PAGEREF _Toc347719185 \h 88
شکل 52 نمودار مثبت واقعی، منفی واقعی و دقت پیشبینی PAGEREF _Toc347719186 \h 95
شکل 53 اثر تغییرات MTTF بر روی دقت پیشبینی PAGEREF _Toc347719187 \h 96
شکل 54 اثر حساسیت و ویژگی بر روی دقت پیشبینی PAGEREF _Toc347719188 \h 97
شکل 55 شماتیک خط زمانی نقطه مقابلهگیری هماهنگ دورهای PAGEREF _Toc347719189 \h 98
شکل 56 شماتیک خط زمانی نقطه مقابلهگیری هماهنگ دورهای در برخورد با اشکال PAGEREF _Toc347719190 \h 99
شکل 57 شماتیک خط زمانی الگوریتم تطبیقی پیشنهادی PAGEREF _Toc347719191 \h 101
شکل 61دیاگرام کلی شبیهساز[92] PAGEREF _Toc347719192 \h 116
شکل 62 جریان کار اجزای برنامههای موازی در شبیهساز [92] PAGEREF _Toc347719193 \h 116
شکل 63 نمونهای از محتویات یک فایل سناریوی خرابی گرها در یک مرکز داده PAGEREF _Toc347719194 \h 118
شکل 64 ماشین حالت خرابی یک گره محاسباتی در ابر PAGEREF _Toc347719195 \h 119
شکل 65 تکه کد تغییر وضعیت حالت میزبان‌های یک مرکزداده به صورت بهینه PAGEREF _Toc347719196 \h 120
شکل 66 تکه کد پیشبینی وضعیت یک گره محاسباتی در زمان آینده time PAGEREF _Toc347719197 \h 121
شکل 67 در صد بهبود زمان اجرای الگوریتمهای پیشنهادی نسبت به الگوریتم آزمون نقطه مقابلهگیری دورهای کلاسیک PAGEREF _Toc347719198 \h 126
شکل 68 در صد بهبود زمان اجرای الگوریتمهای پیشنهادی نسبت به الگوریتم آزمون نقطه مقابلهگیری دورهای کلاسیک با افزایش زمان نقطه مقابلهگیری به 5 دقیقه PAGEREF _Toc347719199 \h 127
شکل 69 تعداد عمل‌های انتخابی در طول زمان اجرا با الگوریتم نقطه مقابلهگیری دورهای PAGEREF _Toc347719200 \h 128
شکل 610 تعداد عمل‌های انتخابی در طول زمان اجرا با الگوریتم تطبیقی اولیه PAGEREF _Toc347719201 \h 128
شکل 611 تعداد عمل‌های انتخابی در طول زمان اجرا با الگوریتم تطبیقی تصحیح شده PAGEREF _Toc347719202 \h 129
شکل 612 تعداد اشکال‌هایی که در طول اجرای برنامه سبب توقف یا عدم توقف ابر می‌شوند PAGEREF _Toc347719203 \h 130
فهرست جداول
TOC \h \z \c "جدول" جدول 11 قابلیت اطمینان در مراکز داده مختلف[4] PAGEREF _Toc347719204 \h 5
جدول 21 مقایسه کلاسترهای HA و FT [13] PAGEREF _Toc347719205 \h 11
جدول 22 زمانهای توقف و کارکرد یک سیستم 52×7×12 PAGEREF _Toc347719206 \h 14
جدول 23 زمان‌هاي توقف و كاركرد يك سيستم 52×5×12 PAGEREF _Toc347719207 \h 14
جدول 31 مقايسه بين قراردادهاي مختلف بازيابي [47] PAGEREF _Toc347719208 \h 64
جدول 51 رابطه وضعیت محیط و الگوریتم پیشبینی PAGEREF _Toc347719209 \h 91
جدول 52 تعاریف پارامترهای استفاده شده در مدلها PAGEREF _Toc347719210 \h 102
جدول 53 مدل هزینه عمل مهاجرت PAGEREF _Toc347719211 \h 103
جدول 54 مدل هزینه عمل نقطه مقابلهگیری PAGEREF _Toc347719212 \h 104
جدول 55 مدل هزینه عمل اجرای بلافاصل PAGEREF _Toc347719213 \h 105
جدول 61 مقداردهی اولیه متغیرهای شبیهساز PAGEREF _Toc347719214 \h 125
فصل اول
مقدمه
مقدمه
جهان محاسباتی که امروزه با آن روبرو هستیم روز بهروز در حال بزرگتر و پیچیده‌تر شدن است. محاسبات ابری نیز در ادامه سبک‌های دیگر مانند محاسبات توری با هدف پردازش حجم عظیمی از داده با استفاده از خوشه‌هایی از کامپیوتر‌هاست. طبق گراش ارائه شده ای از گوکل، در حال حاضر به لطف محاسبات توزیع شده روزانه بیش از 20 ترابایت داده خام اینترنتی مورد پردازش قرار میگیرد. تکامل و شکل‌گیری محاسبات ابری خواهد توانست این چنین مسائلی را به راحتی و به شکلی مناسب‌تر از طریق سرویس‌های مبتنی بر تقاضا حل و فصل نماید. از زاویه دیگر، جهان محاسباتی اطراف ما در حال حرکت به سمت الگوهای "پرداخت برای استفاده" حرکت میکند و همین الگو یکی دیگر از پایه‌های اصلی محاسبات ابری محسوب میشود.
محاسبات ابری که در اواخر سال 2007 پا به عرضه ظهور گذاشت هماکنون به دلیل توانایی‌اش در ارائه زیر ساخت فناوری پویا و بسیار منعطف، محیط‌های محاسباتی تصمین شده از نظر کیفیت و همچنین سرویس‌های نرم‌افزاری قابل پیکربندی به موضوع داغ بدل شده است . در گزارش رویکردی گوگل همانطور که در REF _Ref347364413 \h \* MERGEFORMAT شکل 11 مشاهده می‌نمایید، محاسبات ابری، محاسبات توری را پشت سر گذاشته است [1]. محاسبات ابری از رویکرد مجازیسازی بهرهگیری مینماید که این امر سبب انعطافپذیری بیشتر سیستم ابر میشود. در حقیقت با استفاده از این تکنولوژی، برنامهها میتوانند سرویس‌های مختلف را به صورت مجزا و انتزاعی از گرههای سرویسدهنده دریافت نمایند.
شکل STYLEREF 1 \s 1 SEQ شکل \* ARABIC \s 1 1رویکرد یه تکنولوژی‌های مختلف محاسبات توزیع شده [1]
تعاریف زیادی در مورد محاسبات ابری ارائه شده است که سعی می‌نمایند مشخصه‌های اصلی محاسبات ابری را مد نظر بگیرند که سیستم ابری را " یک مدل برای دسترسی بنابر تقاضا و راحت تحت شبکه به یک مجموعه اشتراکی از منابع محاسباتی قابل پیکربندی" تعریف می‌نمایند درحالیکه "این منابع با کمترین تلاش و هزینه به صورت آزاد" فراهم گردند [2].
محاسبات ابری از خصوصیات منحصر به فردی بهره میبرد که این سبک محاسباتی را از سایر سبک‌ها متمایز میکند. البته برخی از این خصوصیات کما بیش در سبک‌های پیشین نیز وجود داشتهاند. بعضی از این خصوصیات عبارتند از:
ارائه سرویس مبتنی بر تقاضا: در اینجا لازم نیست تا برای آن چه استفاده نمی‌کنید هزینه پرداخت کنید. این بدان معناست که مشتریان تنها بر اساس مقدار و کیفیت سرویسی که مصرف می‌نمایند، هزینه استفاده پرداخت می‌نمایند. در حقیقت رویکرد این تکنولوژی همانند سرویس‌های عمومی قابل استفاده دیگر امروزی است. برای مثال همانطور که برای تولید برق نیاز نیست که هر خانوار دارای ژنراتور و سایر وسایل تولید الکتریسیته باشد، دریافت سرویسی مانند محاسبات یا محل ذخیره داده نیز دیگر نیازی به خصوصی بودن ندارد و می‌توان آن را از فراهم آوردنگان ابر اجاره کرد.
دسترسی شبکه گسترده (اینترنت): این سیستم برای تحویل و ارئه سرویس‌ها از بستر موجود برای اینترنت استفاده مینماید. بنابراین مشتریان سرویس‌ها به هیچگونه نرم‌افزار یا سخت‌افزار خاصی نیاز ندارند و با همان مرورگری که هر روزه به گشت و گذار در وب می‌پردازند میتوانند از سرویس‌های ابر بهره ببرند.
استخر منابع: در این سیستم با حجم وسیعی از منابع روبرو هستیم. این منابع از طریق مجازیسازی از محل فیزیکی خود مستقل شدهاند. بنابراین به راحتی میتوانند در بستر شبکه جابهجا شوند. در واقع نرم‌افزارها، پایگاه‌های داد، وب سرورها و سیستمهای عامل همگی به عنوان سرورهای مجازی در سیستم ابر حضور دارند.
قابلیت اطمینان بالا: فراهم آورندگان ابر به مشتریان خود تضمین می‌دهند که سیستم ابر همیشه قابلیت ارائه سرویس را داشته باشد. حال آنکه در سیستمهای خانگی یک اشکال در نرم‌افزار یا سخت‌افزار می‌تواند موجب عدم دسترسی به اطلاعات و سرویس شود.
هزینه پایین: به صورت سنتی برای اجرای برنامههای سنگین محاسباتی یا داده ای عظیم نیاز به یک سیستم با توان بالای محاسباتی و دادهای احساس می‌شده است. این سیستم هزینه سنگینی را برای شرکت و یا افراد سرویسگیرنده فراهم می‌آورده است. حال با استفاده از سرویس‌های موجود بر روی ابر، کاربران میتوانند بر روی پروژه خود تمرکز بیشتری داشته باشد و هزینه گزافی را بابت تهیه زیرساخت‌ها نپردازد.
بهروز بودن: هزینههای گزافی که برای برپا بودن و بهروز بودن زیرساخت‌های سختافزاری و نرم‌افزاری باید پرداخت شوند با استفاده از ابر از بین میرود. در حقیقت بهروز در آوردن زیرساخت‌ها از وظایف فراهمآورندگان ابر میشود که بدون آنکه کاربر نهایی از این موضوع مطلع شود انجام می‌پذیرد.
در سیستمهای محاسبات توزیعی به دلیل کم کردن هزینه و توان مصرفی، از اجزاء تجاری عاممنظوره موجود در بازار استفاده میشود[3]. این اجزا به مرور زمان مستهلک شده و دچار خرابی می‌شوند تا جایی‌که برای همیشه غیرقابلاستفاده میگردند. همچنین با توجه به آمار ذکر شده، تعداد پردازندهها به منظور بهبود کارآیی سیستم محاسباتی توزیعی رو به افزایش است. با این حال احتمال وقوع خرابی در کل سیستم توزیعی با یک رابطه نمایی بالا میرود. برای مثال سیستم کلاستری که برای یکی از قسمت‌های سایت گوگل استفاده میشود، بیش از 15000 پردازنده دارد که بر اساس آمار ذکر شده در [4]، نرخ خرابی هر گره محاسباتی تقریبا 2-3% در سال است. این سیستم به طور میانگین 20 بار در هر روز به علت خرابی ناگزیر به راهاندازی مجدد است. بزرگترین مرکز داده جهان بیش از 560000 هسته پردازشی دارد و در کمتر از هر 10 دقیقه با یک اشکال در سیستم مواجه میشود. درجدول 1-1 چند نمونه از تعداد اشکال‌های گزارش شده در مراکز داده آمده است.
جدول STYLEREF 1 \s 1 SEQ جدول \* ARABIC \s 1 1 قابلیت اطمینان در مراکز داده مختلف[4]
سیستمتعداد پردازندهمیانگین زمان تا خرابی بعدیASCI Q81926.5 ساعتASCI White81925 ساعت و 40 دقیقهPSC Lemieux30169.7 ساعتGoogle1500020 راهاندازی مجدد در روز
برای برنامههای علمی-کاربردی موازی امروزی که بسیار پیچیده‌تر شدهاند و معمولا برای روزها، هفتهها و یا بیشتر طراحی شدهاند تا به اتمام برسند، برخورد با اشکال در حین اجرا برنامه موازی امری اجتنابناپذیر به نظر میرسد. امروزه رویکردهای تحمل‌پذیر اشکال در مراکز به یکی از چالش‌های اصلی در محاسبات توزیعی تبدیل شده است.
آزمون نقطه مقابلهگیری(cp) و بازیافت یک تکنیک معمول برای مدیریت اشکال در محاسبات توزیع شده میباشد و مقالات ارزشمندی در مورد بازیابی بر اساس الگوریتمهای آزمون نقطه مقابلهگیری مختلف موجود میباشد[5 و6 و7]. مطالعه بر روی هزینه نقطه مقابله گرفتن به صورت گسترده کماکان در حال انجام است. بیشتر کارها بر روی انتخاب بازه بهینه نقطه مقابله و کم کردن سربار برای عمل نقطه مقابله انجام شده است. در واقع مهمترین مساله در بازیافت، برخورد با اشکالها بعد از وقوع آن و رویکرد بازگشت به عقب است. در روش نقطه مقابله بهصورت هماهنگ دورهای، در ابتدای بازه‌های زمانی از پیش تعریف شده حالت کنونی تکتک واحدهای محاسباتی موجود (این واحد در ابر ماشینهای مجازی است) ذخیره میشود. پس از اتمام ذخیرهسازی تمام ماشینهای مجازی، سیستم تا ابتدای بازه زمانی بعدی به کار خود ادامه میدهد.
زمانیکه در یکی از گرههای محاسباتی خرابی رخ داد، این خرابی کشف میشود و تمام کارهای موازی متوقف شده تا اشکال در سیستم بر طرف گردد. پس از رفع اشکال سیستم به آخرین حالت ذخیره شده ماشینهای مجازی باز میگردد و عملیات را از آن نقطه دوباره آغاز میکند و به کار خود ادامه میدهد. در اغلب پیادهسازیها، پروتکل کشف و بازیافت اشکال از دید برنامهنویس پنهان میباشد. این قبیل پروتکلها به صورت واکنشی پس از وقوع اشکال در سیستم عمل مینماید. بنابراین در این حالت ممکن است زمان زیادی به لحاظ تعمیر سیستم و بازیابی مجدد ماشینهای مجازی از دست برود که روی کارآیی ابر بهصورت مستقیم تاثیر منفی میگذارد.
در مقابل این روشها، اخیرا روشهای دیگری پیشنهاد شده که مبتنی بر پیشبینی اشکال در هر گره محاسباتی هستند. در این سیستمها، یک مکانیسم مدیریت اشکال تطبیقی وجود دارد که سعی دارد تا بهصورت بهینه، بهترین عمل را در ابتدای هر بازه تصمیمگیری نماید.
در دهههای گذشته پیشرفتهایی در زمینه پیشبینی اشکال حاصل شده است. برای نمونه، وسایل سختافزاری مدرنی با خصیصههای مختلفی همچون سنسورهای سختافزاری طراحی شدهاند که میتوانند افت یک ویژگی در طول زمان را (برای شناسایی خرابیهای نزدیک) نشان دهند[8 و 9] و تعدادی روشهای یادگیری ماشینی و آماری مبتنی بر تکنیکهای احتمال برای بالابردن دقت آنها ارائه شده است[3 و 10]. تکنیکهای مقاومت در برابر اشکال پیشکنشی مبتنی بر پیشبینی به منظور دستیابی به دسترسی‌بالا، برای کاربردهای بحرانی- امن اتخاذ گردیده است. اما تاکنون مطالعات خوبی بر روی ابر صورت نگرفته است.
در این پایاننامه سیستمهای محاسبات ابری را به عنوان یکی از سیستمهای پردازش موازی مبتنی بر مبادله پیام مورد بررسی قرار میدهیم. این محیطها به علت ویژگی خاص خود که ارتباط کارهای موازی فقط از پیام‌های رد و بدل شده انجام می‌پذیرد، دارای توانمندی‌های بالقوه برای انجام عملیات بازیافت می‌باشند. از این رو، آنچه ما به طور خلاصه مورد مطالعه قرار خواهیم داد، قراردادهای بازیافت مختلف برای محیط مبادله پیام خواهد بود. این قراردادها برای توانمند کردن محیط پردازش موازی به منظور تحمل‌پذیر کردن در برابر اشکال، اطلاعاتی نظیر حالت ماشینهای مجازی یا محتوی پیام‌ها را در طول اجرای عادی نگهداری می‌کنند تا در زمان وقوع اشکال با استفاده از آنها، عملیات بازیافت انجام پذیرد.
در این پایاننامه در فصل دوم با قابلیت دسترسی‌بالا آشنا خواهیم شد و سپس در فصل سوم قراردادهای بازیافت در یک محیط پردازش موازی مبتنی بر مبادله پیام را مورد بررسی و مقایسه قرار میدهیم. در فصل چهارم به مطالعه کارهای اخیر انجام شده در زمینه برخورد پیشکنشی با اشکال‌های محتمل می‌پردازیم. فصل پنجم را به معرفی الگوریتم پیشنهادی اختصاص داده و در آخر به پیادهسازی و ارزیابی الگوریتمهای پیشنهادی و مقایسه آن با روش کلاسیک پرداخته و نتیجهگیری می‌نماییم.
فصل دوم
قابليت دسترسيبالا
روش پيشنهادي
يکي از مواردي که بايد به آن پرداخت احتمال وقوع يک رويداد است. براي اين منظور بايد ابتدا اشکال را مدل کرد تا بتوان بر اساس مدل اشکال و قوانين احتمال، احتمال درست پيشبيني کردن وضيعت سيستم را در هر لحظه محاسبه نمود. از پيشبيني براي ارزشگذاري کردن و محاسبه جريمه مدل‌هاي پيشنهادي که در قسمتهاي بعدي در مورد آن صحبت خواهيم کرد استفاده مي‌نماييم. در اين قسمت ابتدا مدل اشکال را معرفي و بعد از آن مفاهيم اوليه احتمال را بررسي مي‌نماييم. احتمال‌هاي مختلف و تاثير پارامترهاي مختلف بر درستي پيشبيني و حالت بهينه تصميمگيري مباحث بعدي اين فصل مي‌باشند.
مدل اشکال
به‌طور شهودي، نرخ خرابي تعداد خرابي‌هاي مورد انتظار يک وسيله يا سيستم در يک بازه زماني مشخص است [88]. براي مثال، اگر يک کامپيوتر به‌طور ميانگين هر 2000 ساعت يک بار خراب شود، نرخ خرابي آن خرابي در ساعت است که آن را با λ نشان مي‌دهند. نرخ خرابي يکي از معيارهاي مقايسه سيستم‌ها و يا اجزا مي‌باشد. براي فهم بهتر ايده نرخ خرابي از نظر رياضي تابع قابليت اعتماد را تعريف مي‌نماييم و آن را با نشان مي‌دهيم. قابليت اعتماد يک جزء يا سيستم، احتمال درست کار کردن يک جزء در بازه زماني QUOTE مي‌باشد با شرط اينکه جزء مفروض در زمان QUOTE t0 درست کار مي‌کند. QUOTE Nf(t) را تعداد اجزايي که در مدت زمان t QUOTE خراب شده است و را تعداد اجزايي را که در زمان به درستي کار کردهاند را در نظر بگيريد. اگر فرض کنيم که جزء خراب شده به‌طور دائم در اين وضيعت مي‌ماند قابليت اعتماد اجزا در زمان به صورت
است که N تعداد کل اجزاء مشابه مي‌باشد. به همين طريق قابليت عدم اعتماد را به صورت
تعريف مي‌نماييم. با توجه به تعاريف فوق مي‌توان به رابطه دست يافت. پس
و مي‌توان نتيجه گرفت که
مشتق ، ، نرخ لحظه‌اي اجزاء خراب مي‌باشد. در زمان t، اجزاء هنوز درست کار ميکنند. با تقسيم کردن بر به رابطه
دست مي‌يابيم. را تابع نرخ خرابي مي‌ناميم. به طريق ديگر نيز مي‌توان نرخ خرابي را نشان داد. براي مثال را مي‌توان از طريق رابطهبه صورت
و يا از طريق Q(t) به صورت
استخراج کرد.
را تابع تراکم خرابي مي‌ناميم. تابع نرخ خرابي مشخصا به دليل توجه مولفه‌هاي و مقدار به زمان وابسته است. با اين حال تجربه نشان داده است که تابع نرخ خرابي براي اجزا الکترونيکي داراي يک بازه زماني است که در طول اين بازه تقريبا ثابت است.
ارتباط پذيرفته شده معمول مابين تابع نرخ خرابي و زمان براي اجزاء الکترونيکي را منحني وانمي‌نامند که در شکل 5-1 نشان داده شده است.
شکل STYLEREF 1 \s 5 SEQ شکل \* ARABIC \s 1 1 منحنی وان
در منحني وان فرض شده است که در زمان اوليه شروع به کار سيستم‌ها، اشکالها متناوبا اتفاق مي‌افتند که به دليل استاندار نبودن يا مشکل داشتن اوليه اجزاست. قسمت اوليه منحني وان، که داراي شيب پايين رونده است ناحيه early life يا Infant mortality مي‌نامند.
در قسمت انتهاي منحني ناحيه ازکارافتادگي قرار دارد که به دليل فرسودگي فيزيکي قطعات مکانيکي و الکترونيکي خرابي زياد اتفاق مي‌افتد. در ناحيه مياني منحني تابع نرخ اشکال يک مقدار ثابت در نظر گرفته ميشود که به اين قسمت از منحني، ناحيه زندگي مفيد سيستم گفته ميشود و رابطه نرخ خرابي با مقدار λ در طول اين بازه معرفي ميشود.
در طول ناحيه زندگي مفيد سيستم سرويس‌هاي قابل پيشبيني را براي کاربرانش فراهم مي‌نمايد. با توجه به توضيحات، تابع نرخ خرابي مي‌تواند با تابع قابليت در ارتباط باشد؛ بدين صورت که
با اين حال، مقدار معکوس تابع قابليت اعتماد،، است. پس مي‌توان نوشت
که نتايج معادله ديفرانسيلي به فرم
تبديل مي‌گردد. اگر تصور کنيم که سيستم در ناحيه مفيد زندگي است، پس تابع نرخ خرابي برابر با مقدار ثابت λ QUOTE است که با حل معادله ديفرانسيلي به رابطه
دست مي‌يابيم. رابطه نمايي قابليت اعتماد و زمان به قانون خرابي نمايي معروف است. قانون خرابي نمايي براي تحليل اجزاء الکترونيکي بسيار کارآمد است. با اين حال، خيلي از نمونه‌ها نمي‌تواند تابع نرخ خرابي را ثابت فرض نمايند و بنابراين اين قانون در مورد تمام مدل‌هاي خرابي قابل تعميم نمي‌باشد. يک مثال از تابع نرخ خرابي متغير با زمان، آناليز نرم‌افزاري مي‌باشد. خرابي نرم‌افزاري نتيجه اشکالهاي طراحي است که زماني که به عنوان يک بسته نرم‌افزاري ارائه مي‌گردند اشکالهاي طراحي پيدا و تصحيح مي‌شوند و نتيجتا قابليت اعتماد نرم‌افزاري تابعي از زمان است.
يک تکنيک مدل‌سازي معمول، توزيع weibull است [89] که تابع نرخ خرابي متغير با زمان را معرفي مي‌کند. تابع نرخ خرابي به صورت
با استفاده از توزيع weibull قابل تعريف است که و ثابت‌هاي کنترلي متغيرهاي تابع نرخ خرابي است. تابع قابليت اعتماد با استفاده از توزيع weibull به صورت
تبديل ميشود که يقينا به صورت
در مي‌آيد.
متوسط زماني تا خرابي
MTTF ميانگين زمان مورد انتظار است که يک سيستم تا قبل از اولين خرابي بهدرستی کار کند. MTTF را مي‌توان با پيدا کردن مقدار زمان مورد انتظار خرابي محاسبه گردد که همان اميد رياضي است. از نظر تئوري احتمال اميد رياضي متغير x به صورت
است که تابع چگالي احتمال است. در تحليل قابليت احتمال، اميد رياضي زمان خرابي مورد نظر است. پس
است. لازم به ذکر است که به دليل اينکه تابع چگالي خرابي براي زمان‌هاي منفي بيمعني است، کران پايين اين انتگرال به صفر تبديل مي‌گردد. تابع نرخ خرابي به صورت
است. بنابراين MTTF به صورت
قابل نوشتن است. با توجه به اين که داريم
مولفه زماني که و يا زماني که است به صفر تبديل شده و در نظر گرفته نمي‌شود. نتيجتا MTTF به صورت
در مي‌آيد که با توجه به قانون توزيع زماني خرابي MTTF را مي‌توان به صورت
نوشت. بنابراين قابليت اعتماد در زمانيکه برابر با میانگین زمانی تا خرابی بعدی که با قانون توزيع نمايي خرابي به دست آمده است برابر
مي‌باشد. به عبارت ديگر يک سيستم که از قانون خرابي نمايي تبعيت مي‌نمايد، به احتمال 0.3678 يک خرابي را با فرض سالم بودن در زمان آغاز به کار تا قبل MTTF تجربه نمي‌نمايد.
مبانی احتمال و پیشبینی
در ابتدا يک سري مفاهيم اوليه را تعريف مي‌نماييم و بعد از آن ارتباط اين قسمت با مدل خرابي را مورد مطالعه قرار مي‌دهيم.
مفاهیم اولیه
مثبت واقعي (tp) به تعداد رويدادهايي که در يک بازه زماني رخ مي‌دهد و به درستي پيشبيني ميشود گويند.
مثبت کاذب (fp) به تعداد رويدادهايي که در يک بازه زماني رخ نمي‌دهد ولي به اشتباه وقوع آن پيشبيني ميشود گويند.
منفي واقعي (tn) به تعداد رويدادهايي که در يک بازه زماني رخ ندهد و عدم وقوع آن نیز پيشبيني شده است گويند.
منفي کاذب (fn) به تعداد رويدادهايي که رخ مي‌دهد ولي وقوع آن پيشبيني شده است گويند.
براي فهم بهتر مي‌توان از جدول 5-1 کمک گرفت تا اين 4 حالت ممکن و رابطه بين آنها به صورت شهودي ملموستر شود.
جدول STYLEREF 1 \s 5 SEQ جدول \* ARABIC \s 1 1 رابطه وضعیت محیط و الگوریتم پیشبینی
وضيعت محيطعدم وقوعوقوعfptpوقوعنتيجه پيشبينيtnfnعدم وقوع
هر تخمينزن را مي‌توان با دو پارامتر مدل کرد که اين دو پارامتر مي‌تواند ويژگي و حساسيت پيشبيني باشد. ويژگي يک تخمينزن برابر با تعداد رويدادهايي که اتفاق نمي‌افتد و تخمينزن به درستي عدم وقوع آن را پيشبيني مي‌کند بر تعداد کل رويدادهای اتفاق نیافتاده در يک بازه زمانی است. بنابراين ويژگي يک تخمينزن برابر است:
ويژگي
حساسيت يک تخمينزن به تعداد رويدادهايي که در يک بازه زماني اتفاق مي‌افتد و احتمال وقوع آن نيز پيشبيني شده است به تعداد کل رويدادهاي رخ داده در طول يک بازه زماني گویند. بنابراين
حساسيت
با توجه به تعاريف فوق، به‌راحتي قابل اثبات است که هر چه حساسيت و ويژگي يک الگوريتم پيشبيني بالاتر باشد اين الگوريتم پيش‌بيني‌هاي درست‌تري را براي وقوع يا عدم وقوع يمک رويداد دارد.
تنش يک رابطه تعادلي مابين دقت و حساسيت يک سيستم پيش‌بيني‌کننده است. به صورت شهودي سيستمي که حساسيت آن بهتر باشد معمولا منفي کاذب آن کمتر است ولي احتمالا مثبت واقعي آن نيز بيش‌تر ميشود. به عبارت ديگر اين سيستم بيش‌تر تمايل به رخ ندادن يک رويداد تا رخ دادن آن دارد و اين الگوريتم به صورت بدبينانه پيشبيني مي‌نمايد. برعکس اين موضوع نيز قابل تفسير است و ممکن است الگوريتم بيش‌تر به صورت خوشبينانه پيشبيني نمايد. تنش به ما کمک مي‌کند که بتوانيم الگوريتم‌هاي پيشبيني را بهتر با هم مقايسه نماييم. تنش يک سيستم به صورت
تنش=2 × حساسیت × ویژگیحساسیت+ویژگی
تعريف مي‌گردد.
رابطه قانون بيز و احتمال درستي پيشبيني
در اين قسمت سعي داريم تا احتمال درست پيشبيني کردن يک رويداد را با استفاده از يک الگوريتم پيشبيني محاسبه نماييم. براي اين منظور فرض کنید که احتمال وقوع يک رويداد به صورت يک تابع متغير با زمان مانند باشد. با توجه به تعاريف قسمت قبل، احتمال آنکه اين رويداد رخ دهد و الگوريتم پيشبيني مفروض بتواند آن را پيشبيني نمايد همان مثبت واقعی است.
حال به صورت برعکس به قضيه نگاه ميکنيم. فرض کنيد که الگوريتم پيشبيني، احتمال وقوع يک رويداد را پيشبيني کرده است. مساله اين است که با توجه به خاصيت‌هاي ويژگي و حساسيت اين پيش‌بيني‌کننده چقدر احتمال دارد که اين رويداد واقعا رخ دهد.
برعکس سناريو قبل نيز قابل تعريف است؛ بدين ترتيب که الگوريتم پيش‌بيني‌کننده مفروض در زمان t احتمال عدم وقوع يک رويداد را پیشبيني مي‌کند. چقدر احتمال دارد که اين پيشبيني درست باشد و رويداد رخ ندهد و يا چقدر احتمال دارد که رويداد اتفاق افتد.
با استفاده از قانون بيز به اين سوالات پاسخ مي‌دهيم. براي اين منظور ابتدا حالتي را فرض مي‌نماييم که پيشبيني شده که يک رويداد اتفاق بيافتد. با توجه به اين که تابع توزيع وقوع رويداد را در نظر گرفتيم، با استفاده از قانون بيز مثبت واقعی و مثبت کاذب را محاسبه مي‌نماييم؛ بدين صورت که
که در اينجا sens همان مقدار حساسيت و spec همان مقدار ويژگي الگوريتم پيش‌بيني‌کننده است.
حال فرض کنيد که الگوريتم پيشبيني مفروض، عدم وقوع يک رويداد را پيشبيني کند. مي‌خواهيم بررسي نماييم که تا چه حد اين پيشبيني درست است که اين همان منفی واقعی مي‌باشد. با استفاده از قانون بيز و تعاريف ذکر شده به رابطه‌هاي
مي‌رسيم. لازم به ذکر است که چون است پس tp، fp، fn و tn نيز داراي بردي مشابه تابع مي‌باشند و به صورت احتمال در نظر گرفته می شوند.
رابطه الگوريتم پيشبيني و مدل اشکال
حال به بررسي دقيقتر مساله مي‌پردازيم. با توجه به توضيحات قسمتهاي قبل، مدل خرابي قطعات الکترونيکي را به صورت يک توزيع نمايي در ناحيه زندگي مفيد با نرخ خرابي ثابتي مانند QUOTE در نظر مي‌گيريم با توجه به توضيحات بيان شده قابليت اعتماد به صورت در مي‌آيد که يک تابع اکيدا نزولي است. قابليت اعتماد در حقيقت اميد رياضي درست کار کردن يک سيستم يا جزء در زمان t مي‌باشد. بنابراين رويداد مورد بحث را مي‌توان با احتمال درست کار کردن سيستم مفروض در نظر گرفت. پس روابط به صورت
(1)
در مي‌آيد.
تحليل روابط احتمالي
حال به تحليل روابط (1) مي‌پردازيم. فرض کنيد که يک سيستم در زمان قرار دارد. بنابرابن
چون احتمال وقوع اشکال در لحظه با توجه به تعريف صفر است، tp نيز در لحظه صفر براي هر الگوريتم پيش‌بيني‌کننده‌اي با هر دقتي برابر يک ميشود و با همين استدلال fp نيز بايد يک گردد.حال به بررسي پيش‌بيني‌کننده در مدت زمان بسيار زياد مي‌پردازيم پس داريم
به عبارت ديگر هر الگوريتم پيش‌بيني‌کننده‌اي در دراز مدت به احتمال 50% يک اشکال را پيشبيني مي‌کند يا نمي‌کند. شکل 5-2 نمودار tp، tn و ميانگين اين دو که همان دقت پيشبيني است را نشان مي‌دهد.
شکل STYLEREF 1 \s 5 SEQ شکل \* ARABIC \s 1 2 نمودار مثبت واقعی، منفی واقعی و دقت پیشبینی
همانطور که مشاهده ميشود منحني دقت پيشبيني در دراز مدت به سمت 0.5 ميل مي‌کند. حال به تحليل دقيقتر اين منحني مي‌پردازيم. براي اين منظور مقدار MTTF را تغيير مي‌دهيم و تغييرات آن را بر روي دقت پيشبيني بررسي مي‌نماييم. شکل 5-3 اثر تغييرات MTTF را بر روي دقت پيشبيني نشان مي‌دهد. همانطور که پيداست هرچه MTTF بيش‌تر ميشود و يا به عبارتي نرخ اشکال کمتر ميشود دقت پيشبيني در بازه زماني بيش‌تري مطلوب نسبي خواهد بود و با شيب کم‌تري به سمت 0.5 ميل مي‌کند.
شکل STYLEREF 1 \s 5 SEQ شکل \* ARABIC \s 1 3 اثر تغییرات MTTF بر روی دقت پیشبینی
با توجه به تعريف تابع دقت که با acc نمايش مي‌دهيم داريم
که نتيجتا
با مشتقگيري از اين تابع و پيدا کردن نقطه اکسترمم مطلق آن درمییابیم که تابع در نقطه
داراي اکسترمم مطلق است و اگر حساسیت و ویژگی به یک اندازه باشند، این رابطه به تبدیل میشود و مقدار تابع در این حالت sens است که این بدین معنی است که دقت پیشبینیکننده در بهترین حالت (به شرط0.5 sens ≥)، sens میباشد. دراين مرحله اثر پارامترهاي ويژگي و حساسيت تخمينزن را مورد بررسي قرار مي‌دهيم. شکل 5-4، نمودار منحني دقت پيشبيني براساس تغييرات حساسيت و ويژگي الگوريتم پيشبيني نشان مي‌دهد. همانطور که پيداست اگر دو پارامتر ويژگي و حساسيت هردو بزرگتر از 0.5 باشند، منحني دقت به صورت صعودي در مي‌آيد و با يک ماکسيمم مطلق است و هرچه اين مقادير بهتر باشند، منحني دقت پيشبيني داراي مقادير اکسترمم بهتري خواهد بود و ديرتر به سمت 0.5 ميل مي‌کند. اکسترمم اين تابع برابر sens است که ارتباط مستقيم حساسيت و ويژگي پيشبيني با ماکسيمم تابع قابل مشاهده است.
شکل STYLEREF 1 \s 5 SEQ شکل \* ARABIC \s 1 4 اثر حساسیت و ویژگی بر روی دقت پیشبینی
با توجه به بحث‌هاي مطرح شده، مي‌توان نتيجه گرفت که دقت پيشبيني را در دراز مدت نمي‌توان تغييرداد و الگوريتم‌هاي پيشبيني بسيار قدرتمندتر نيز تنها در مدت زمان‌هاي محدود مفيد مي‌باشند و در دراز مدت کارآيي چنداني ندارند. به همين منظور در قسمتهاي آينده مدل‌هاي مبتني بر هزينه را معرفي مي‌نماييم تا با استفاده آنها اين ضعف پوشش داده شود و به صورت هوشمندانه از اين توابع احتمالي استفاده گردد.
مدل پيشنهادي
در يک سيستم پردازش موازي مانند ابر، ماشینهای مجازی برروي گره‌هاي محاسباتي قرار دارند که ارتباط آنها با يکديگر از طريق کارگزار سیستم مي‌باشد که به شبکه ارتباطي متصل هستند. اين ارتباط و همچنين ارتباط با جهان خارج از طريق ارسال پيام صورت مي‌پذيرد. در حقيقت ارسال و دريافت پيام تنها راه ارتباطي ما بين ماشینهای مجازیست. در سيستم مدل شده يک سرويس کارگزار وجود دارد که اعزام کارها به ماشینهای مجازی از وظائف آن مي‌باشد. زمان اجراي ماشینهای مجازی بر روي گرههای محاسباتي با خط زماني مشخص مي‌گردد. يادآوري ميشود که در الگوريتم آزمون نقطه مقابلهگیری کلاسيک که به صورت هماهنگ دورهاي عمل مي‌نمايد، بعد از سپري شدن اجراي برنامه در ابتداي يک بازه زماني مشخص همه ماشینهای مجازی اقدام به نقطه مقابلهگیری مي‌نمايند و پس از آن که عمل نقطه مقابلهگیری به انجام رسيد به کار خود ادامه مي‌دهند. شکل 5-5 شماتيک کلي اين روش را نشان مي‌دهد.
شکل STYLEREF 1 \s 5 SEQ شکل \* ARABIC \s 1 5 شماتیک خط زمانی نقطه مقابلهگیری هماهنگ دورهای
در اين روش در صورتي که يک اشکال بر روي يکي از گره‌هاي محاسباتي صورت پذيرد، دیتاسنتر پس از کشف اشکال، کارگزار را از وقوع اشکال آگاه میسازد. چنانچه کار در حال اجرایی بر روی آن گره محاسباتی وجود داشته باشد، به تمام ماشینهاي مجازی ديگر فرمان توقف اجراي برنامه مي‌دهد. پس از بر طرف شدن اشکال در گره مفروض، ماشینهای مجازی از آخرين نقطه مقابله گرفته شده شروع به کار مي‌نمايند و سيستم اين الگوريتم را دوباره در دستور کار خود قرار مي‌دهند. در این حالت چنانچه کاری بر روی یک ماشین مجازی قبل از وقوع اشکال به اتمام رسیده شده باشد، بازیافت نمی شود و نیازی به شروع مجدد آن نیست. شکل 5-6 نمودار زماني حالتی که سیستم با خرابی یک گره محاسباتی مواجه می شود را نشان مي‌دهد.
شکل STYLEREF 1 \s 5 SEQ شکل \* ARABIC \s 1 6 شماتیک خط زمانی نقطه مقابلهگیری هماهنگ دورهای در برخورد با اشکال
يکي از مسائل مهم در نقطه مقابلهگیری دورهاي هماهنگ تعيين بازه نقطه مقابلهگیری است. هرچه اين بازه زماني بزرگتر باشد، احتمال وقوع اشکال در اين بازه بيش‌تر مي‌باشد و هرچه اين بازه کوچک‌تر باشد، سيستم زمان بيش‌تري بايد براي آزمون نقطه مقابلهگیری هزينه کند و در حقيقت از کارآيي سيستم به مقدار قابل توجهي در صورت عدم برخورد با اشکال کاسته ميشود و سر بار قابل ملاحظه‌اي به سيستم تحميل مي‌گردد. در [90] نشان داده شده است که بازه بهينه است که cpOverhead مدت زماني که طول مي‌کشد تا سيستم عمل نقطه مقابلهگیری را انجام دهد. از طرفي با بزرگتر شدن کلاسترها که در حقيقت افزايش تعداد گره‌هاي محاسباتي در سيستم است، احتمال بر خورد با اشکالها با يک رابطه نمايي بسيار زياد‌تر ميشود. به عبارت ديگر MTTF کلي سيستم کاهش مي‌يابد و بنابراين طول اين بازه بسيار کوچک‌تر ميشود و عملا سيستم مدت زمان زيادي را بايد صرف کند تا نقطه مقابله بگيرد.
نکته قابل توجه اين است که روشهاي کلاسيک روش‌هايي واکنشي مي‌باشد يعني بايد يک اشکال در سيستم مشاهده گردد تا پس از کشف آن عمل، بازيابي و بازگشت به عقب صورت پذيرد که مدت اين زمان عمدتا قابل مقايسه است و تاثير مستقيم بر روي کارآيي سيستم دارد و در مواردي نيز ممکن است که جزء خراب شده به حالت سالم خود باز نگردد و موجب توقف کامل سيستم شده تا عمليات تعمير به صورت دستي انجام پذیرد که اين خود يک هزينه پرسنلي اضافي به سيستم ابر تحميل مي‌نمايد.
در روش پيشنهادي سعي گرديده تا به مشکلات فوقالذکر به نحوي پاسخ داده شود که براي همين، از نقطه مقابله گرفتن‌هاي اضافه که در زمان‌هايي که احتمال زيادي وجود دارد که به سيستم به درستي کار کند اجتناب گرديده شده است. همچنين اين الگوريتم اشکالهاي احتمالي هر گره محاسباتي را پيشبيني مي‌نمايد. در صورتي که احتمال وجود اين اشکال به گونه‌اي باشد که هزينه خراب شدن گره مشکوک زياد ارزيابي شود، ماشینهای مجازی که بر روي اين گره (يا گرهها) وجود دارد به گره‌اي که احتمال اشکال در آن کمتر است انتقال داده ميشود. در صورتي که احتمال سالم کار کردن سيستم (مثلا در زمان شروع به کار سيستم) بسيار زياد بوده، اين روش از نقطه مقابله گرفتن اضافي اجتناب مي‌نمايد.
ارائه الگوريتم
در اين الگوريتم نقطه مقابلهگیری به صورت هماهنگ دورهاي در نظر گرفته شده است. يعني هر گاه سيستم تصميم به نقطه مقابلهگیری نمايد، از تمام کارها نقطه مقابله گرفته ميشود. به عبارتي از اين منظر فرق کلي اين الگوريتم با روش کلاسيک آن اين است که طول بازه نقطه مقابلهگیری متغير بوده و اين تغيير رابطه‌اي هوشمندانه با احتمال اشکال در گره‌هاي مختلف سيستم کلاستر دارد. هر ماشین مجازی به صورت جدا اقدام به بررسي احتمال اشکال گره محاسباتي که بر روي آن قرار دارد مي‌نمايد و سپس يک عمل مناسب را در اين بازه تصميمگيري مي‌نمايد. اين عمل مي‌تواند يکي از سه عمل
ادامه بلافصل برنامه؛
نقطه مقابله گرفتن از حالت ماشین مجازی؛
مهاجرت ماشین مجازی از گره مفروض
باشد. اين عمل‌ها بر اساس مدل ارزيابي مبتني بر هزينه که در ادامه توضيح داده خواهد شد صورت مي‌پذيرد. اين عمل‌ها از هر ماشین مجازی به واحد کارگزار که وظيفه هماهنگي ماشینهای مجازی را دارد فرستاده ميشود. در حقيقت هر ماشین مجازی وضيعت محيطي خود را به يک مرکز تصميمگيري کلي سيستم ارسال مي‌نمايد. عمل هر ماشین مجازی تنها يک پيشنهاد از طرف هر ماشین مجازی به سيستم است. در ادامه توضيح داده خواهد شد که چگونه سيستم تصميم کلي را اتخاذ مي‌نمايد.
شماتيک کلي الگوريتم در شکل 5-7 نشان داده شده است.
شکل STYLEREF 1 \s 5 SEQ شکل \* ARABIC \s 1 7 شماتیک خط زمانی الگوریتم تطبیقی پیشنهادی
لازم به ذکر است که اين الگوريتم چون به صورت تقريبا توزيعي عمل مي‌نمايد، بنابراين زمان محاسباتي آن با افزايش تعداد پردازندهها تفاوت چنداني نمي‌کند. همچنين اين الگوريتم امکان آن را فراهم مي‌کند تا بتوان از الگوريتم‌هاي پيچيده‌تر پيشبيني حالت گره محاسباتي و همين‌طور استفاده از مدل‌هاي پيچيده‌تر هزينه هر عمل استفاده کرد. در اين مدلها فرض شده است که اشکال در انتهاي بازه تصميمگيري و درست قبل از انتهاي بازه تصميمگيري بعدي رخ مي‌دهد.
مدل مبتني بر هزينه
براي هر عمل يک مدل پيشنهادي در نظر مي‌گيريم. هدف اين مدلها محاسبه جريمه و يا سود ناشي از انتخاب هر عمل مي‌باشد. هزينه هر عمل را به‌طور ساده مقدار زماني که يک سيستم به دست مي‌آورد يا از دست مي‌دهد تا بتواند برنامه را در طول يک بازه تصميمگيري اجرا کند در نظر مي‌گيريم. پر واضح است که هزينه‌ها بايد نسبت به يک عمل ثابت در نظر گرفته شود که ما در مدل‌هاي خود هزينه‌ها را نسبت به نقطه مقابله گرفتن کلاسيک دورهای هماهنگ در نظر مي‌گيريم تا هزينه همه عمل‌ها با يک معيار واحد سنجيده شود.
قبل از پرداختن به هزينه هر عمل به‌طور مشخص، يک سري پارامترهايي را تعريف مي‌نماييم که در ادامه بحث به آنها نياز ميشود. جدول 5-2 اين پارامترها را بيان مي‌نمايد.
جدول STYLEREF 1 \s 5 SEQ جدول \* ARABIC \s 1 2 تعاریف پارامترهای استفاده شده در مدلهاperiodطول بازه تصميمگيريlastCp[t]زمان آخرين نقطه مقابله گرفته شده سيستم تا قبل از زمان tcpOverheadزمان لازم براي نقطه مقابله گرفتن هماهنگ سيستمmigOverheadزمان لازم براي مهاجرت دادن ماشینهاي يک گرهMTTRميانگين زمان تعمير سيستم
عمل مهاجرت
در صورتي که در ابتداي بازه تصميمگيري فعلي (که همان نقطه تصميمگيري است) بخواهيم از اين عمل استفاده نماييم، بايد ببينيم که انتخاب اين عمل در چه صورتي به نفع و در چه حالتي به ضرر گره‌اي است که اين ماشین مجازی بر روي آن در حال اجراست. در مدل پيشنهادي فرض شده است که عمل مهاجرت به صورت زنده صورت مي‌پذيرد. بنابراين عمل مهاجرت به اين صورت است که ماشینهاي مجازی واقع بر روي گره مشکوک به اشکال گره امنتر مهاجرت می کنند. برای انجام مهاجرت زنده گره مبدا درصدی از توان محاسباتی خودش را در طول زمان این مهاجرت صرف می نماید. طول این زمان به سرعت شبکه ارتباطی، سایز فایل ماشین مجازی وابسته است. بنابراین، migOverhead طول این زمان در درصد اضافه از ماشین مبدا است.
ذکر اين نکته لازم به نظر مي‌رسد که يافتن گره مقصد براي عمل مهاجرت هر ما از وظائف کارگزار مي‌باشد و در ادامه در مورد آن توضيح داده خواهد شد.
در صورتي که وضيعت گره مذکور تا نقطه تصميمگيري بعدي که در حقيقت ابتداي بازه بعدي است سالم باشد و اين عمل انتخاب گردد، يک هزينه اضافي به سيستم متحمل شده است که در واقع همان جريمهي انتخاب اين عمل است. برعکس، اگر گره‌اي که اين ماشین مجازی بر روي آن قرار دارد تا بازه بعدي دچار اشکال گردد وعمل مهاجرت انتخاب گردد، کل سيستم از اين پيشنهاد بهره مي‌برد زیرا در اين صورت سيستم نیازی ندارد تا به حالت تعمير در بيايد و متوقف شود مادامی که گره خراب شده به سيستم باز گردد. در حقيقت يکي از سودهايي که الگوريتم پيشنهادي دارد، انتخاب درست اين عمل مي‌باشد زيرا در صورت اشکال در آزمون نقطه مقابله کلاسيک کل سيستم بايستي به حالت توقف در بيايد تا زمانیکه سيستم از حالت تعمير خارج شود. پس نتيجه مي‌گيريم که در حالت کلاسيک، کل سيستم حتي به علت اشکال در يک گره بايد منتظر بماند. يادآوري ميشود که دیتاسنترها امروزه در حال بزرگ شدن مي‌باشند و اين امر باعث مي‌گردد تا احتمال برخورد سيستم با حداقل يک اشکال در يک بازه زماني مشخص (که رابطه نمايي با تعداد گره‌هاي محاسباتي در کلاستر دارد) افزايش يابد. هنگامی که در اين الگوريتم خرابي يک گره تشخيص داده شود و اين عمل انتخاب گردد، تنها اين گره به حالت تعمير مي‌رود و برنامه موازي متوقف نمي‌شود.
در جدول 5-3 سود و يا جريمه‌هايي که با توجه به وضيعت سيستم در طول بازه مشخص بايد بپردازيم، مشخص شده است. البته این مدل هزینه تنها سود یا ضرری است که یک ماشین مجازی متحمل میشود. برای روشن شدن بهتر مساله، حالتی را در نظر بگیرید که ماشینهای مجازی یک گره مشکوک به خرابی را به گرههای دیگر انتقال دادیم ولی بر خلاف پیشبینی، خرابی این گره اشتباها گزارش شده بود. بدیهی است که سیستم یک گره سالم را به نادرستی از کار خارج کرده است. انتخاب نادرست این عمل نه تنها سبب کاهش توان محاسباتی سیستم ابر میشود، بلکه ترافیک شبکه را نیز بالا میبرد. بنابراین باید
جدول STYLEREF 1 \s 5 SEQ جدول \* ARABIC \s 1 3 مدل هزینه عمل مهاجرت
هزينهسود/ضرروضعيت سيستمperiod+lastCp[time]×cpOverhead-migOverhead+MTTRسودخرابmigOverhead-cpOverheadضررسالم
عمل نقطه مقابله گرفتن
اين عمل براي اين در نظر گرفته شده است تا سيستم در مقابل اشکالهاي غير قابل پيشبيني هزينه زيادي متحمل نشود. اگر اين عمل در هر نقطه تصميمگيري انتخاب گردد، (صرف نظر از سرباری ناچيز) اين الگوريتم شبيه آزمون نقطه مقابله گرفتن معمولي عمل مي‌نمايد. به عبارتي هدف از اجراي اين عمل عدم اطمينان صِرف به مکانيسم پيشبيني است.
براي روشن شدن بهتر، حالتي را در نظر بگيريد که سيستم براي مدت زمان طولاني اقدام به نقطه مقابله گرفتن نکرده است و مکانيسم پيشبيني هيچگونه اشکال متحملي را در سيستم پیشبینی نکرده است. اگر در این حالت یک اشکال رخ دهد، سیستم بايد هزينه زماني بسيار گزافي را بپردازد تا به حالت فعلي برگردد که علاوه بر مدت زمان تعميري که بايد سپري شود که گره خراب به حالت سالم بازگردد کل سيستم از آخرين نقطه مقابله گرفته شده، بايد شروع به کار کند و به عبارتي تمام زمان کارهايی که تا قبل از اشکال صرف شده، به هدر رفته است.
جدول 5-4 هزينه استفاده از اين عمل را در وضيعتي که سيستم تا انتهاي اين بازه سالم بماند و يا در سيستم اشکالی اتفاق افتد را نشان مي‌دهد. بديهي است که اگر در اين نقطه از تمام ماشینهای مجازی اقدام به نقطه مقابله گرفتن نماييم، ضرر نمي‌کنيم. به عبارت دقيقتر، با انتخاب اين عمل باعث شده‌ايم که نقطه مقابله گرفتن ما به صورت دورهاي ولي با بازه زماني ناهمگون انجام شود. در صورتي که آخرين زمان نقطه مقابله گرفتن قبلي مربوط به دوره غيرنقطه تصميمگيري قبلي باشد اين الگوريتم سود کرده و اگر احتمالا در نقطه قبلي نيز سيستم به نقطه مقابله گرفتن مبادرت ورزيده باشد هيچ سودي نبرده، در عين حالي که ضرري هم نکرده است.
جدول STYLEREF 1 \s 5 SEQ جدول \* ARABIC \s 1 4 مدل هزینه عمل نقطه مقابلهگیری
هزينهسود/ضرروضعيت سيستم(lastCp[time]-1) (cpOverhead)×سودخراب(lastCp[time]-1) (cpOverhead)×سودسالم
پس نتيجه مي‌گيريم که هرچه مکانيسم پيشبيني دقيقتر عمل نمايد بايد عمل نقطه مقابله گرفتن کمتر در تصميمگيري انتخاب شود تا آن جا که در حالت ايده‌ال پيشبيني، قاعدتا نبايد از نقطه مقابله گرفتن استفاده شود و هر زمان سيستم اشکالی را به درستي پيشبيني کرد بايد عمل مهاجرت اتخاذ گردد.
عمل اجراي بلافاصل برنامه
يکي ديگر از مزيت‌هاي الگوريتم پيشنهادي استفاده درست از اين عمل مي‌باشد. اين عمل سبب مي‌گردد تا نقطه مقابله گرفتن‌هاي اضافي که سربار زيادي را به کل سيستم متحمل ميکنند کاهش يابد. در حقيقت اگر فرض کنيم که برنامه کاربردي موازي هيچ اشکالی را در طول اجرايش تجربه نمي‌کند استفاده هميشگي از اين عمل منجر به دستيابي به کارآيي بهينه سيستم موازي مي‌گردد (البته به شرطي که از سربار ناشي از الگوريتم پيشنهادي چشم پوشي نماييم) و مزيت اين الگوريتم بيش از پيش عيان ميشود. با اينحال، استفاده نابهجا از اين عمل سبب مي‌گردد تا در صورت برخورد با يک رويداد اشکال، سيستم جريمه سنگين‌تري را نسبت به نقطه مقابله گرفتن دورهاي بپردازد. بنابراين استفاده از اين عمل به دقت الگوريتم پيشبيني در دراز مدت بستگي دارد. به عبارت ديگر بايد الگوريتم پيشنهادي به صورتي تصميمگيري نمايد که اگر به مکانيسم پيشبيني اشکال بيش‌تر اعتماد داشت، عمل اجراي بلافاصل برنامه يا مهاجرت (در صورت پيشبيني اشکال در سيستم) و اگر کمتر اعتماد داشت عمل نقطه مقابله گرفتن بيش‌تر انتخاب شود. در قسمت کارگزار نقش دقت پيشبيني و تعداد گره‌هاي محاسباتي در تصميمگيري نهايي سيستم را به تفصيل توضيح خواهيم داد. جدول 6-5 مدل هزينه اين عمل را در حالت وضيعت سالم سيستم يا برخورد با اشکال را نشان مي‌دهد.
جدول STYLEREF 1 \s 5 SEQ جدول \* ARABIC \s 1 5 مدل هزینه عمل اجرای بلافاصلهزينهسود/ضرروضعيت سيستم(lastCp[time]-1)× (period-cpOverhead)ضررخرابcpOverhead × lastCp[time]سودسالم
اثر پيش‌بيني‌کننده بر روي مدل‌هاي هزينه
الگوريتم پيش‌بيني‌کننده که هر ماشین مجازی از آن استفاده مي‌نمايد، وضعيت گره محاسباتي که روي آن قرار دارد را يا درست حدس مي‌زند يا به اشتباه پيشبيني مي‌نمايد و بنا به توضيحات ذکر شده در قسمتهاي قبل، چهار حالت مثبت واقعي، مثبت کاذب، منفي واقعي و منفي کاذب ممکن است پيش بيايد که از ميان اين چهار حالت، مثبت واقعي و منفي واقعي حالات دلخواه ما مي‌باشند وهر چه دقت الگوريتم پيشبيني بيش‌تر باشد، بايد انتظار داشته باشيم که اين حالات بيش‌تر اتفاق بيافتند. بنابراين براي بررسي مدلها در نقطه تصميمگيري از برآيند وزندار وضعيت سيستم (سالم يا خراب) استفاده مي‌نماييم که احتمال اين چهار حالت نقش وزن‌ها را ايفا ميکنند. به عبارت ديگر، هر ماشین مجازی مدل ارزيابي مبتني بر هزينه هر سه عمل را با استفاده از برآيند اين چهار حالت محاسبه مي‌نمايد و سپس عملي را انتخاب مي‌نمايد که بيش‌ترين سود و يا کم‌ترين ضرر محتمل را داشته باشد و آن را به کارگزار ابر ارسال مي‌نمايد تا کارگزار از طريق اين پيشنهاد تصميم کلي سيستم را اتخاذ نمايد.
با توجه به توضيحات بيان شده، برآيند هر عمل در دو حالت بر اساس نتيجه پيشبيني قابل بحث است. روابط (2) برآيند هزينه عمل‌هاي مهاجرت، نقطه مقابله گرفتن و اجراي بلافاصل برنامه کاربردي موازي در صورتي که الگوريتم پيشبيني اشکالی در گره مفروض پيشبيني نکند را نشان مي‌دهد.
(2)
همچنين روابط (3) برآيند هزينه‌هاي اين سه عمل در حالتي که الگوريتم پيشبيني، گره مفروض را در وضعيت سالم برآورد کند نشان مي‌دهد.
(3)
پس مي‌توان نتيجه گرفت که الگوريتم پيشنهادي، مکانيسم پيشبيني را به صورت صرف قبول ندارد و کاملا به آن اعتماد نمي‌کند.
تصميمگيري سيستم در کارگزار ابر
الگوریتم اولیه
هر ماشین مجازی بر اساس روند توضيح داده شده در قسمت قبل، يک عمل را انتخاب و به کارگزار ارسال مي‌کند. در حقيقت اين عمل يک پيشنهاد از طرف هر ماشین مجازی به کارگزار ابر است و بر اساس شرايط محیطی گره محاسباتی است که بر روی واقع شده است. حال کارگزار ابر از مجموعه پيشنهادهاي ارسال شده بايد يک عمل را انتخاب نمايد؛ بدين صورت که اگر لااقل يک پيشنهاد نقطه مقابله گرفتن، سيستم به حالت توقف برود و به تمام ماشینهای مجازی فرمان نقطه مقابله گرفتن بدهد. اگر تصميم یک ماشین مجازی، مهاجرت بود ماشینهاي مجازی که در خواست مهاجرت داده‌اند را به گره‌هاي امنتر مهاجرت دهد و حین انجام اين کار، سيستم به اجراي برنامه موازي به صورت عادي ادامه دهد. در صورتي که هيچ ماشین مجازی پيشنهاد نقطه مقابله گرفتن يا مهاجرت نداد و به عبارتي همه ماشینهای مجازی عمل اجراي بلافاصل را پيشنهاد داده باشند کارگزار نيز تصميم اجراي بلافاصل را به عنوان تصميم کلي سيستم به تمام ماشینهای مجازی اعلام مي‌نمايد. لازم به ذکر است تنها پیشنهاد ماشینهای مجازی در نظر گرفته می شوند که کاری برای انجام در حال اجرا داشته باشند.
یکی از مسائل مطرح در این قسمت، تصمیم گیری در مورد مکان مقصد عمل مهاجرت یک ماشین مجازی است. براي اين منظور مي‌توان چند راهکار در نظر گرفت. يکي از آنها اين است که ماشینهای مجازی را به گره‌هايي مهاجرت دهيم که ماشینهاي مجازی که بر روي آنها قرار دارند عمل اجراي بلافاصل را انتخاب کرده باشند چرا که احتمالا اين گرهها در حالت امن‌تري نسبت به گره‌هاي ديگر قرار دارند. اگر چنين گره‌اي پيدا نشد، آنها را بر روي گره‌هايي انتقال دهيم که عمل انتخابي ماشینهاي مجازی روي آن نقطه مقابله گرفتن است. کارگزار پیشنهادی لیستی از گرههای سالم تهیه مینماید و آن را بر اساس آخرین زمان خراب شده به صورت صعودی مرتب می نماید. سپس از ابتدای لیست گرهای را انتخاب می نماید که ضمن آنکه مدت زمان کمتری از تعمیر آن گذشته، تعداد خرابی آن نیز در طول مدت حیاتش کمتر باشد. این الگوریتم هم اکنون در سیستمهای واقعی به صورت عرف کاملا پذیرفته شده و مورد استفاده قرار میگیرد.
بديهي است که در اين نوع تصميمگيري سيستم به مرور زمان از عمل اجراي بلافاصل کمتر استفاده مي‌کند چرا که ماشینهای مجازی بيش‌تري با گذشت زمان، بروز اشکال را در گره محل اجرايشان احتمال مي‌دهند و بنابراين بيش‌تر يکي از اعمال نقطه مقابله گرفتن و يا مهاجرت را پيشنهاد مي‌دهند و اين عمل کمتر به عنوان تصميم سيستم اتخاذ مي‌گردد.
با همين استدلال مي‌توان نتيجه گرفت که هرچه تعداد گره‌هاي محاسباتي افزايش يابد احتمال آن که اين عمل به تصميم سيستم استفاده شود کاهش مي‌يابد وعملا اين تصميم در ابتداي کار برنامه موازي بيش‌تر استفاده ميشود و با گذشت زمان اثر آن کاهش مي‌يابد و نمي‌توان از مزيت آن بهره برد.
براي مثال، سيستم کلاستري را در نظر بگيريد که داراي 100000 گره محاسباتي است که اين مقياس با توجه به سيستمهاي کلاستري امروزي بسيار معمول است. با استفاده از الگوريتم تصميمگيري توصيف شده اگر تنها يک ماشین مجازی پيشنهاد نقطه مقابله گرفتن نمايد و تمام ماشینهاي مجازی ديگر بر روي گره‌هاي محاسباتي پيشنهاد اجراي بلافاصل برنامه را بدهند، عمل نقطه مقابله گرفتن به عنوان تصميم سيستم اتخاذ مي‌گردد. به عبارت ديگر تمام ماشینهای مجازی فداي تصميم يک ماشین مجازی مي‌شوند. پس استفاده از اين روش يک مزيت کلي سيستم را احتمالا در دراز مدت از بين مي‌برد و تنها مزيت پيشبيني اشکالها، فرار از حالت تعمير و توقف کل سيستم مي‌باشد. لازم به ذکر است که گره‌هايي که داراي تعداد ماشینهاي مجازی بيش‌تري مي‌باشند با اين روش بسيار حياتي‌تر مي‌شوند چرا که در تصميمگيري (به تعداد ماشینهای مجازی روي گره) بيش‌تر نقش ايفا ميکنند.
الگوریتم تصحیح شده
در مقابل اين روش مي‌توان اثر نقطه مقابله گرفتن را تا حدي تعديل کرد. بدين صورت که سيستم تصميمگيري زماني مبادرت به نقطه مقابله گرفتن مي‌نمايد که تعداد درخواست‌ها از سوي ماشینهای مجازی از يک حد آستانه بيش‌تر شود. براي مثال اگر بيش‌تر از 10% از درخواست‌ها عمل نقطه مقابله گرفتن بود، اين عمل به عنوان تصميم کلي سيستم در نظر گرفته شود و در غير‌اينصورت عمل اجراي بلافاصل برنامه در دستور کار ماشینهای مجازی قرار گيرد.
یکی دیگر از مسائلی که به طور مستقیم بر روی کارآیی این الگوریتم تاثیر می گذارد، مهاجرت ماشین های مجازی یک گره سالم و در نتیجه بیکار شدن آن است. همچنین یکی دیگر ازعلل افزایش گرههای بیکار بازگشت گره خراب شده به سیستم پس از تعمیراست. برای حل این مساله، چنانچه بعد از مهاجرت، سیستم به اشتباه خود در انتخاب عمل مهاجرت پی برد و تعداد ماشین های بیکار بیشتر از یک حد آستانه باشند، کارگزار پیشنهادی عمل بهینهسازی نگاشت ماشینهای مجازی به گرههای محاسباتی بیکار را انجام میدهد. برای این منظور از گرههایی که بیشترین مجموع حجم محاسباتی در ماشینهای مجازیشان وجود دارد به عنوان مبدا مهاجرت انتخاب، و به گرههای بیکار تعدادی از ماشینهای مجازیشان مهاجرت داده میشود. انجام این عمل سبب بالانس شدن توان محاسباتی گره های موجود در ابر می گردد.
يکي ديگر از مواردي که بايد متذکر شد اين است که تصميم يک ماشین مجازی براي انتخاب عمل پيشنهادياش بيرابطه با عمل انتخابي ماشینهای مجازی ديگر نمي‌باشد. همانطور که در مدل‌هاي هزينه هر سه عمل مشاهده شد، زمان آخرين نقطه مقابله گرفته شده نقش بهسزايي در مقدار کمي هزينه هر عمل ايفا مي‌کند. فرض کنيد که به دليل عمل انتخابي ماشین مجازیVMi بر روي ماشين، سيستم در نقطه تصميمگيري t تصميم به نقطه مقابله گرفتن نمايد. بنابراين به دليل انتخاب VMi در نقطه تصميمگيري t، مقدار آخرين زمان نقطه مقابله گرفته شده بهروز ميشود و در نقطه تصميمگيري اين مقدار بر روي مدل هزينه ساير ماشینهای مجازی نيز تاثير مي‌گذارد.
نتیجه گیری و پیشنهادات
نتیجهگیری و پیشنهادات
در این پایاننامه پس از مطالعه دقیق روشهای کلاسیک در تحملپذیری اشکال، الگوریتمی تطبیقی مبتنی بر پیشبینی اشکال با استفاده از مدلهای هزینه احتمالی را ارائه دادیم. در نتایج به دست آمده شاهد بهبود بسیار خوبی در زمان اجرای برنامههای موازی بودیم و اثر پارامترهای مختلف الگوریتم و محیطی را روی آن بررسی نمودیم. این الگوریتم کاملا به نتیجه پیشبینیکننده اعتماد نمیکند و در انتخاب عمل پیشنهادی هزینههای پیشبینی اشتباهات محتمل را نیز در نظر میگیرد. یکی از مزایای این الگوریتم توزیعی بودن آن است که موجب میشود تا سربار زیادی به کارگزار ابر تحمیل نشود.
کارهایی که در آینده در راستای این مطالعه مفید به نظر میرسد عبارتند از
ارائه مدلهای هزینه بهتر؛
بررسی دقیق ارتباط تحملپذیری اشکال و نحوه تخصیص ماشینهای مجازی به گرهها در بهبود زمان اجرای برنامه؛
ارائه الگوریتم پیشبینی متغیر با زمان؛
تخمین لحظهای پارامترهای پیشبینی و متوسط زمان تا خرابی بعدی؛
پیادهسازی الگوریتمهای تطبیقی مشابه بر روی متدهای دیگر تحمل‌پذیر اشکال و بررسی بهبود زمان اجرا در آنها؛
استفاده از رویدادهای محیطی در کشف اشکال‌های محتمل سیستم؛
پیدا کردن حد آستانه بهینه برای نقطه مقابله گرفتن.
منابع
Google Trends, http://www.google.com/trends?q=Grid+Computing%2C+vitualization%2C+Cloud+computing.
Sriram, Ilango, Ali Khajeh-Hosseini, "Research agenda in cloud technologies." CoRR, 1001.3259 (2010).
R. K. Sahoo, A. Oliner, I. Rish, M. Gupta, J. E. Moreira, S. Ma, R. Vilalta, A. Sivasubramaniam, "Critical Event Prediction for Proactive Management in Large-Scale Computer Clusters", KDD’03, PP 426-435, August 2003.
A. B. Nagarajan, F. Mueller, C. Engelmann, S. L. Scott, "Proactive Fault tolerance for HPC with Xen virtualization", ICS’07, PP 23-32, Seattle, WA, USA, June 2007.
Duda, "The Effects of Checkpointing on Program Execution Time", Information Processing Letters, Vol. 16, No. 5, PP 221-229, June 1983.
A. Oliner, R. K. Sahoo, J. E. Moreira, M. Gupta, "Performance Implications of periodic Checkpointing on Large-Scale Cluster Systems", IPDPS’05, April 2005.
P. Lemarinier, A. Bouteiller, G. Krawezik, F. Cappello, "Coordinated Checkpoint versus Message Logging for Fault Tolerance MPI", International Journal of High Performance Computing and Networking, Vol. 2, No. 2/3/4, PP. 146-155, 2004.
Health Application Programming Interface (HAPI), http://www.renci.org/software/hapi/.
Hardware Monitoring by Lm-Sensors, http://secure.netroedge.com/lm78/info.html.
R. Vilalta, S. Ma, "Predicting Rare Events in Temporal Domains Using Associative Classification Rules", Technical Report, IBM Research, T. J. Watson Research Center, Yorktown Heights, Vol. 41, No 3, 2002.
P.S. Weygant, "Clusters for High Availability: A Primer of HP Solutions", Hewlett-Parker Company, Packard Company, Prentice Hall, Inc., 2nd ed., 2001.
B. Johnson, "Design & Analysis of Fault-Tolerant Digital Systems", Addison-Wesley Longman Publishing Co. Inc, 1989.
L. Sherman, "Choosing the Right Availability Solution: High Avaialbility Clusters & Fault Tolerant Systems", White Paper, Stratus Computer Inc., 1998.
"Stategies for Fault-Tolerant Computing", Microsoft Corporation, White Paper, 2003.
H. Shah, "Fault Tolerance in Cluster Computing Enviroment", CSCI 555 Research Paper Assignment, University of South California, 2002.
B. Randell, "System Structure for Software Fault Tolerance", IEEE Trans. Softw. Engin. 1, 2, PP 220–232, 1975.
M. Chandy, L. Lamport, "Distributed Snapshots: Determining Global States of Distributed Systems", ACM Trans Comput. Syst. 31, 1, PP 63–75, 1985.
D.L. Russell, "State Restoration in Systems of Communicating Processes", IEEE Trans. Softw. Eng., 6, 2, PP 183–194, 1980.
R. Strom, S. Yemini, "Optimistic Recovery in Distributed Systems", ACM Trans. Comp. Sys., 3, 3, PP 204–226, 1985.
L. Alvisi, "Understanding the Message Logging Paradigm for Masking Process Crashes", Ph.D. Thesis, Cornell university, Department of Computer Science, 1996.
E. N. Elnozahy, W. Zwaenepoel, "on the Use and Implementing of Message Passing", In Digest of Papers, FTCS-24, the Twenty Fourth International Symposium on Fault Tolerance Computing, PP 298-307, 1994.
R. Pausch, "Adding Input and Output to the Transactional Model", Ph.D. Thesis, Carnegie Mellon University, Department of Computer Science, 1988.
D.B. Johnson, W. Zwaenpoe, W. "Recovery in Distributed Systems Using Optimistic Message Logging and Checkpointing", J. Algorithms, 11, 3, PP 462–491, 1990.
A. Borg, W.Blau, W. Graetsch, F. Hermann, W. Oberle, "Fault Tolerance under UNIX ", ACM Trans. Comput. Syst., 34, 3, PP 1–24, 1989.
B.W. Lampson, H.E. Sturgis, "Crash Recovery in a Distributed Data Storage System", Technical Report, Xerox Palo Alto Research Center, 1979.
Y.M. Wang, "Space Reclamation for Uncoordinated Checkpointing in Message-Passing Systems", Ph.D. Thesis, University of Illinois, Department of Computer Science, 1993.
B. Bhargava, S.R. Lian, "Independent Checkpointing and Concurrent Rollback for Recovery—an Optimistic Approach", In Proceedings of Seventh Symposium on Reliable Distributed Systems, 3–12, 1988.
Y.M. Wang, "Consistent Global Checkpoints that Contain a Set of Local Checkpoints", IEEE Trans. Comp. 46, 4, PP 456–468, 1997.
Y. Tamir, C. H. Sequin, "Error Recovery in Multicomputers Using Global Checkpoints", In Proceedings of the International Conference on Parallel Processing, PP 32–41, 1984.
E.N. Elnozahy, D.B.Johnson, W.Zwaenepoel, "The Performance of Consistent Checkpointing", In Proceedings of Eleventh Symposium on Reliable Distributed Systems, PP 39–47, 1992.
Z. Tong R.Y. Kain, W.T. Tsai, "Rollback Recovery in Distributed Systems Using Loosely Synchronized Clocks", IEEE Trans. Parallel and Distributed Syst., 3, 2, PP 246–251, 1992.
R. Koo, S. Toueg, "Checkpointing and Rollback Recovery for Distributed Systems", IEEE Trans. Softw. Eng., 13, 1, PP 23–31, 1987.
R.H. Netzer, J. Xu, "Necessary and Sufficient Conditions for Consistent Global Snapshots", IEEE Trans. Parallel and Distributed Syst., 6, 2, PP 165–169, 1995.
L. Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System", Com. ACM, 21, 7, PP 588–565, 1978.
J.M. Helary, A. Mostefaoui, R.H. Netzer, M. Raynal, "Preventing Useless Checkpoints in Distributed Computations", In Proceedings of Sixteenth Symposium on Reliable Distributed Systems, PP 183–190, 1997.
L. Alvisi, E.N. Elnozahy, S. Rao, S.A. Husain, A.D. Mel "An Analysis of Communication-Induced Checkpointing", In Digest of Papers, FTCS-29, The Twenty Nineth Annual International Symposium on Fault-Tolerant Computing (Madison,Wisconsin), PP 242–249, 1999.
J.F. Bartlett, "A Non Stop Kernel", In Proceedings of the Eighth ACM Symposium on Operating Systems Principles, PP 22–29, 1981.
R. Baldoni, F. Quaglia, B. Ciciani, "AVP-Accordant Checkpointing Protocol Preventing Useless Checkpoints", In Proceedings of Seventeenth Symposium on Reliable Distributed Systems, PP 61–67, 1998.
D. Briatico, A. Ciuffoletti, L. Simoncini "A Distributed Domino-Effect Free Recovery Algorithm", In IEEE International Symposium on Reliability, Distributed Software, and Databases, PP 207–215, 1984.
J.S. Plank, M. Beck, G. Kingsley, K. Li, "Libckpt: Transparent Checkpointing under UNIX," In Proceedings of the USENIX, PP 213–223, 1995.
Y. Huang, Y.M. Wang, "Why Optimistic Message Logging Has not Been Used in Telecommunication Systems", In Digest of Papers, FTCS-25, the Twenty Fifth Annual International Symposium on Fault-Tolerant Computing, PP 459– 463, 1995.
J.P. Banatre, M. Banatre, G. Muller, "Ensuring Data Security and Integrity with a Fast Stable Storage", In Proceedings of the Fourth Conference on Data Engineering, PP 285–293. 1988.
D.B. Johnson, W. Zwaenpoe, "Sender-Based Message Logging", In Digest of Papers, FTCS-17, the Seventeenth Annual International Symposium on Fault-Tolerant Computing, PP 14–19, 1987.
T.Y. Juang, S. Venkatesan, "Crash Recovery with Little Overhead", In Proceedings of the 11th International Conference on Distributed Computing Systems, PP 454–461, 1991.
E.N. Elnozahy, "Manetho: Fault Tolerance in Distributed Systems Using Rollback-Recovery and Process Replication", Ph.D. Thesis, Rice University, Department of Computer Science, 1993.
A. Sistla, J. Welch, "Efficient Distributed Recovery Using Message Logging", In Proceedings of the 8th Annual ACM Symposium on Principles of Distributed Computing (PODC), PP 223–238, 1989.
M. Elnozahy, L. Alvisi, Y. M. Wang, D. B. Johnson, "A Survey of Rollback-Recovery Protocols in Message Passing Systems,” Technical Report CMU-CS-96- 181, School of Comp. Scie., Carnegie Mellon University, Pittsburgh, PA, USA, October 1996.
J.S. Plank, "Efficient Checkpointing on MIMD Architectures", Ph.D. Thesis, Princeton University, Department of Computer Science, 1993.
C.C. Li, W.K. Fuchs, "CATCH: Compiler Assisted Techniques for Checkpointing", In Digest of Papers, FTCS-20, the Twentieth Annual, International Symposium on Fault-Tolerant Computing, PP 74–81, 1990.
M. Chandy, C.V. Ramamoorthy, "Rollback and Recovery Strategies for Computer programs", IEEE Trans. Comp., 21, 6, PP 546–556, 1972.
M. Ruffin, "KITLOG: A Generic Logging Service", In Proceedings of Eleventh Symposium on Reliable Distributed Systems, PP 139–148, 1992.
L.M. Silva, "Checkpointing Mechanisms for Scientific Parallel Applications", Ph.D. Thesis, University of Coimbra, Department of Computer Science, 1997.
S. Rao, L. Alvisi, H.M. Vin, "The Cost of Recovery in Message Logging Protocols", In Proceedings of Seventeenth Symposium on Reliable Distributed Systems, PP 10–18, 1998.
G. M. Weiss, H. Hirsh, "Learning to Predict Rare Events in Categorical Time-Series Data", AAAI Workshop, PP 359-363, 1998.
G. M. Weiss, H. Hirsh, "Learning to Predict Rare Events in Event Sequences", KDD, 1998.
B. Rasndell, "On Failures and Faults", In Formal Methods (FME), vol. 2805, LCNS, PP 18-39, 2003.
B. Schroeder, G. Gibson, "A Large Study of Failures in HPC Systems", In Proceedings of International Conf. on Dependable Systems and Networks, June 2006
T. Heath, R. P. Martin, T. D. Nguyen, "Improving Cluster Availability Using Workstation Validation", In Proceedings of ACM SIGMETRICS, 2002.
D. Nurmi, J. Brevik, R Wolski, "Modeling Machine Availability in Enterprise and Wide-Area Distributed Computing Environments", In Proceedings of EuroPar’05, August 2005.
F. Salfner, S. Tschirpke, M. Malek, "Comprehensive LogFiles for Autonomic Systems", In Proceedings of 9th IEEE Workshop on Fault-Tolerant Parallel Distributed and Network-Centric Systems ,2004.
Y. Liang, Y. Zhang, A. Sivasubramaniam, M. Jette, R. Sahoo, "BlueGene/L Failure Analysis and Prediction Models", In Proceedings of IEEE International Conference on Dependable System and Network (DSN '06), PP 425-434, 2006.
Y. Liang, Y. Zhang, A. Sivasubramaniam, R. Sahoo, J. Moreira, M. Gupta, "Filtering Failure Logs for a BlueGene/L Prototype", In Proceedings of the International Conference on Dependable Systems and Networks (DSN), 2005.
F. A. Nassar, D. M. Andrews, "A Methodology for Analysis of failure Prediction Data", CRC Technical Report No. 85-20, Stanford University, Polo Alto, CA, 1985.
B. Zou, Q. Liu, "ARMA-Based Traffic Forecasting and Overload Detection of Network", J. of Comp. Eng., 32, 12, PP 1645-1652, 2004.
X. Ren, S. Lee, R. Eigenmann, S. Bagchi, "Resource Failure Prediction in Fine-Grained CycleSharing Systems", In proceedings of the 15th IEEE International Syposium on High Performance Distributed Computing, June 2006
P. Gujrati, Y. Li, Z. Lan, R. Thakur, J. White, "Exploring Meta-Learning to Improve Failure Prediction in Supercomputing Clusters", In Proceedings of ICPP'07, 2007.
Z. Lan, Y. Li, "Adaptive Fault Management of Parallel Applications for High Performance Computing", IEEE Trans. on Comp., 57, 12, PP 1647-1660, December 2008.
Y. Li, P. Gujrati, Z. Lan, X. Sun, "Fault-Driven Re-Scheduling for Improving System-Level Fault Resilience", ICPP’07, 2007.
Y. Li, Z. Lan, P. Gujrati, X. Sun, "Fault-Aware Runtime Strategies for High Performance Computing", IEEE Trans. on Parallel and Distributed Systems, 99, 2, 2008.
Y. Li, Z. Lan, "Exploit Failure Prediction for Adaptive Fault-Tolerance in Cluster Computing", CCGrid06, 1, PP 531-538, Singapore, May 2006.
A. J. Oliner, L. Rudolph, R. K. Sahoo, "Cooperative Checkpointing Theory", In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS), Rhodes Island, Greece, April 2006.
A. J. Oliner, R. K. Sahoo, J. E. Moreira, M. Gupta, A. Sivasubramaniam, "Fault-Aware Job Scheduling for BlueGene/L Systems", In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS), Santa Fe, NM, April 2004.
Y. Li, Z. Lan, P. Gujrati, X. Sun, "Fault-Aware Runtime Strategies for High Performance Computing", IEEE Trans. on Parallel and Distributed Systems , 20, 4, PP 460-473, 2009.
Ganglia, http://ganglia.sourceforge.net/.
X. Gu, S. Papadimitriou, P. S. Yu, S. Chang, "Toward Predictive Failure Management for Distributed Stream Processing Systems", IEEE International Conf. on Distributed Computing Systems (ICDCS), Beijing, China, June 2008.
X. Gu, S. Papadimitriou, P. S. Yu, S. Chang, "Online Failure Forecast for Fault-Tolerant Data Stream Processing", IEEE International Conf. on Data Eng. (ICDE), Cancun, Mexico, April 2008.
H. Jitsumoto, T. Endo, S. Matsuoka, "ABARIS: An Adaptable Fault Detection/Recovery Component Framework for MPIs", 12th IEEE Workshop on Dependable Parallel, Distributed and Network-Centric Systems DPDNS '07, CA, March 2007.
MPICH-P4MPD, http://mpich-v.lri.fr/.
Egwutuoha, Ifeanyi P., Shiping Chen, David Levy, and Bran Selic. "A Fault Tolerance Framework for High Performance Computing in Cloud." In Cluster, Cloud and Grid Computing (CCGrid), 2012 12th IEEE/ACM International Symposium on, pp. 709-710. IEEE, 2012.
Litvinova, Antonina, Christian Engelmann, and Stephen L. Scott. "A proactive fault tolerance framework for high-performance computing." In Proceedings of the 9th IASTED International Conference on Parallel and Distributed Computing and Networks (PDCN), pp. 16-18. 2010.
Malik, Sheheryar, and Fabrice Huet. "Adaptive Fault Tolerance in Real Time Cloud Computing." In Services (SERVICES), 2011 IEEE World Congress on, pp. 280-287. IEEE, 2011.
Bala, Anju, and Inderveer Chana. "Fault Tolerance-Challenges, Techniques and Implementation in Cloud Computing." IJCSI International Journal of Computer Science Issues 9, no. 1 (2012).
Yang, Chao-Tung, Wei-Li Chou, Ching-Hsien Hsu, and Alfredo Cuzzocrea. "On improvement of cloud virtual machine availability with virtualization fault tolerance mechanism." In Cloud Computing Technology and Science (CloudCom), 2011 IEEE Third International Conference on, pp. 122-129. IEEE, 2011.
Padhy, Smruti, Diego Kreutz, António Casimiro, and Marcelo Pasin. "Trustworthy and resilient monitoring system for cloud infrastructures." InProceedings of the Workshop on Posters and Demos Track, p. 3. ACM, 2011.
Sun, Dawei, Guiran Chang, Changsheng Miao, and Xingwei Wang. "Building a High Serviceability Model by Checkpointing and Replication Strategy in Cloud Computing Environments." In Distributed Computing Systems Workshops (ICDCSW), 2012 32nd International Conference on, pp. 578-587. IEEE, 2012.
Zhu, Jun, Zhefu Jiang, Zhen Xiao, and Xiaoming Li. "Optimizing the performance of virtual machine synchronization for fault tolerance." Computers, IEEE Transactions on 60, no. 12 (2011): 1718-1729.
Garraghan, Peter, Paul Townend, and Jie Xu. "Real-Time Fault-Tolerance in Federated Cloud Environments." In Object/Component/Service-Oriented Real-Time Distributed Computing Workshops (ISORCW), 2012 15th IEEE International Symposium on, pp. 118-123. IEEE, 2012.
M. L. Shooman, "Probabilistic Reliability: An Enineering Approach", McGraw-Hill, NY 1968.
D. P. Siewiorek, R. S. Swarz, "The Theory and Practice of Reliable System Design", Digital Press, Bedford, Mass., 1982.
J. W. Young, "A First Order Approximation to the Optimal Checkpoint Interval", Comm. ACM, 17, 9, PP 530-531, 1974.
Buyya, Rajkumar, Rajiv Ranjan, and Rodrigo N. Calheiros. "Modeling and simulation of scalable Cloud computing environments and the CloudSim toolkit: Challenges and opportunities." In High Performance Computing & Simulation, 2009. HPCS'09. International Conference on, pp. 1-11. IEEE, 2009.
Calheiros, Rodrigo N., Rajiv Ranjan, Anton Beloglazov, César AF De Rose, and Rajkumar Buyya. "CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms."Software: Practice and Experience 41, no. 1 (2011): 23-50.
Buyya, Rajkumar, and Manzur Murshed. "Gridsim: A toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing." Concurrency and Computation: Practice and Experience 14, no. 13‐15 (2003): 1175-1220.
ABSTRACT
Design & Implementation of a Fault-aware Job Scheduler in Cloud Computing Systems
BY
ROSHANAK LAKISHIRAZ
With increasing market to use Cloud computing technology, huge data-centers are existed to execute calculations fast. One of the main challenges in cloud computing is facing to faults when a time-consuming parallel program runs. To overcome this problem, checkpointing or logging techniques are proposed. However, these techniques typically have considerable overheads. Besides, they operate reactively.
In this thesis, we propose an approach which more than recovery and rolling back for fault tolerance, can detect the computing nodes that are more likely to experience faults, and migrates their allocated virtual machines into safe computing nodes. Furthermore, using Bayes’ rule and proposed cost models, the algorithm avoid excess checkpointing with purpose of improve time executions of running programs. By simulation, we show that proposed method ameliorate the execution time up to 78% in cases and take advantage of less resource.
Keywords: Cloud Computing Systems, Fault Prediction, Cost-Based Model, Bayes’ Rules, Proactive, Coordinated Checkpoint, Migration.
Shiraz UniversityFaculty of Engineering Computer Engineering and IT DepartmentMaster of Science ThesisDesign & Implementation of a Fault-aware Job Scheduler in Cloud Computing SystemsBy:Roshanak LakishirazSupervisor:Dr. Farshad KhunjushMarch 2013
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
قیمت: 49٬000 تومان
