بررسی الگوریتم های زمان بندی وظیفه در محیط محاسبات ابری
چکیده :
محاسبات ابری به دلیل مزایا که دارد در سال های اخیر بسیار مورد استقبال قرار گرفته است،بدیهی است هر فن آوری در کنار مزایای خود، معایبی دارد، یکی از موارد چالش برانگیز این فن آوری قابلیت اطمینان آن است از این رو مسئله قابلیت اطمینان در الگوریتم های زمان بندی وظیفه که برای نگاشت منابع به وظایف می باشند را مرود مطالعه قرار داده.
با مرور چند الگوریتم زمان بندی معروف به این نتیجه رسیدیم که اکثر آن ها فاکتور قابلیت اطمینان غافلند نادیده گرفته اند، پس روی الگوریتم هایی که این پارامتر را رعایت کرده اند تمرکز کرده، با مقایسه چند الگوریتم زمان بندی که سعی در رعایت قابلیت اطمینان داشته اند متوجه شدیم که این الگوریتم ها همراه با قابلیت اطمینان به دنبال پارامترهای دیگری نیز می باشند، ازجمله بهره برداری از منبع،مدت زمان اجرا و غیره و این در حالی است که پارامترهای دیگر مثل دسترس پذیری و یا کاهش احتمال شکست پیش بینی شکست و غیره را ندارند.
الگوریتم PPDD مسئله تعادل بار و زمان بندی چندین بار روی چندین پردازنده را روی یک شبکه درختی تک سطحی بررسی می کند، این الگوریتم قابلیت اطمینان را در نظر نمی گیرد با استفاده از توزیع پوآسون با اضافه کردن پارامترƛ به عنوان نرخ متوسط رخ دادن شکست در توزیع مجدد بار علاوه بر میزان اختلاف بار فعلی با بار ایده آل توان پردازشی را که متاثر از قابلیت اطمینان آن پردازنده می باشد دخیل می کنیم، با این روش بارها منصفانه تر بین پردازنده ها توزیع می شود، همانطور که می دانید قابلیت اطمینان با مدت زمان اجرا رابطه عکس دارد، طبیعی است با در نظر گرفتن رخ دادن شکست و ریکاوری شکست، زمان پردازشی این الگوریتم نسبت به حالتی که قابلیت اطمینان را در نظر گرفته نمی شود افزایش یابد، در کارهای بعدی می توان مدت زمان پردازش سراسری را کاهش داد و الگوریتم PPDD با قابلیت اطمینان را بهبود بخشیم به طوری که الگوریتم دو هدفه ای باشد که یک تابع توافقی جهت موازنه بین دو داشته باشد.
از آنجایی که در این گزارش بیش از بیست الگوریتم مورد مقایسه قرار گرفته است می تواند به عنوان یک مرجع برای علاقه مندانی باشد که می خواهند در حوزه الگوریتمی های زمان بندی کار کنند.
واژه های کلیدی:
محاسبات ابری،الگوریتم های زمان بندی،قابلیت اطمینان ، الگوریتم PPDD
فهرست مطالب
فصل 1 مقدمه 1
1-1 مقدمه 2
1-2 تعریف مساله و بیان سوال های اصلی تحقیق 3
1-3 سابقه و ضرورت انجام تحقیق 3
1-4 فرضیه ها 5
1-5 هدف ها 5
1-6 کاربردها 5
1-7 جنبه نوآوری تحقیق 6
1-8 روش تحقیق 6
1-9 مراحل انجام تحقیق 7
1-10 ساختار پایان نامه 7
فصل 2 محاسبات ابری 8
2-1 مقدمه 9
2-2 ویژگی های احساسی محاسبات ابری 10
2-3 مزایا و معایب محاسبات ابری 11
2-3-1 مزایای محاسبات ابری 11
2-3-2 معایب محاسبات ابری 12
2-4 مولفه های محاسبات ابری 14
2-5 ابر 14
2-6 روش های پیاده سازی محاسبات ابری 15
2-7 مدل های محاسبات ابری 18
2-7-1 نرم افزار به عنوان سرویس (SaaS) 20
2-7-2 بستر به عنوان سرویس(PaaS) 21
2-7-3 زیر ساخت به عنوان سرویس (IaaS) 21
2-7-4 سخت افزار به عناوان یک سرویس (HaaS) 22
2-8 چالش های موجود در محاسبات ابری 22
2-9 جمع بندی 25
فصل3 الگوریتم‌های زمان‌بندی 26
3-1 مقدمه 27
3-2 گردش کاری 27
3-3 زمان بندی گردش کاری 28
3-4 پارامترهای الگوریتم های زمان بندی 29
3-5 چند نمونه الگوریتم زمان بندی معروف 30
3-5-1 الگوریتم Min-Min با بار متعادل شده (LBMM) 31
3-5-2 الگوریتم توزیع زمان- هزینه (DCT) 32
3-5-4 الگوریتم زمان بندی منبع مجتمع و پویا (DARIS) 34
3-5-5 الگوریتم توافق زمان هزینه CTC 36
3-5-6 بزرگ ترین تکه ابر،سریع ترین عنصر پردازشی (LCFP ) 39
3-5-7 الگوریتم قیمت گذاری بر اساس فعالیت بهبود یافته (ABC) 39
3-5-8 الگوریتم زندگی زنبورها (BLA ) 41
3-5-9 چندین گردش کاری با چندین محدودیت QOS (MQMW ) 42
3-5-10 الگوریتم کاهش تعادل (BAR ) 43
3-5-11 الگوریتم زود ترین زمان پایان ناهمگن(HEFT ) 44
3-5-12 الگوریتم زمان بندی آگاه از منبع (RASA ) 45
3-6 مقایسه اول 46
3-7 قابلیت اطمینان 48
3-8 قابلیت اعتماد 50
3-9 استراتژی مدیریت درست زمان بندی(STM ) 51
3-10 الگوریتم هایی در مورد قابلیت اطمینان 54
3-10-1 بالاترین قابلیت اطمینان(Maxre) 54
3-10-2 آگاهی از قابلیت اطمینان-منبع-مهلت زمانی (DRR ) 56
3-10-3 یادگیری تقویتی (RL) 57
3-10-4 الگوریتم زمان بندی مبتنی بر ارتباط با ماکزیمم تحمل خطا (FMCED ) 59
3-10-5 زمان بندی سطح پویا با قابلیت اطمینان (RDLS ) 61
3-10-6 الگوریتم ژنتیک جلورونده (LAGA ) 64
3-10-7 PRMS و MCMS 67
4-5-7-1 زمان بند تطابقی با حداقل هزینه (MCMS) 67
4-5-7-2 زمان بند با حداکثر قابلیت اطمینان به طور تصاعدی (PRMS ) 68
3-11 جمع بندی 70
فصل 4 قابلیت اطمینان در الگوریتم PPDD 71
4-1 مقدمه 72
4-2 الگوریتم PPDD 73
4-2-1 فلوچارت الگوریتم PPDD 74
4-3 فاکتور قابلیت اطمینان در PPDD 77
4-4 مثال الگوریتم PPDD با پرارمتر قابلیت اطمینان 79
4-5 مقایسه و نتیجه گیری 81
4-6 جمع بندی 82
فصل 5 نتیجه گیری و پیشنهادها 83
5-1 مقدمه 84
5-2 نتایج حاصل از تحقیق 84
5-3 پیشنهادها 86
مراجع 87
واژه نامه 91
واژهنامه فارسی به انگلیسی 92
واژهنامه انگلیسی به فارسی 93
فهرست شکل‌ها
شکل 2-1. ساختار ابری سه لایه 15
شکل 2-1 لایه های محاسبات ابری 18
شکل 2-3. مدل سرویس 22
شکل 3-1 مروری بر زمان بندی گردش کاری 29
شکل 3-2 مقایسه دو الگوریتم LBMM و Min-Min 32
شکل 3-3 فلوچارت الگوریتم DARIS 35
شکل 3-4- مروری بر گردش کاری زمان‌بند 42
شکل 3-5. طبقه‌بندی قابلیت اعتماد 50
شکل 3-6. فرآیند فیلتر کردن منبع 52
شکل 3-7. نتایج شبیه‌سازی سیاست مدیریت درست زمان‌بندی 53
شکل 4-1. شبکه درختی تک سطحی با چندین بار 73
شکل 4-2 فلوجارت الگوریتم PPDD 75
شکل 4-3. الگوریتم ppdd با پردازنده Front-end 76
شکل 4-4. الگوریتم ppdd بدون پردازنده Front-end 76
شکل 4-5 نمودار زمان برای مثال بالا بدون داشتن پارامتر قابلیت اطمینان 80
شکل 4-6. نمودار مدت زمان برای مثال بالا با داشتن پارامتر قابلیت اطمینان 81
فهرست جدول‌ها
جدول 3-1 پارامترهای چند الگوریتم زمان‌بندی 46
جدول 3-2 الگوریتم زمان بندی موجود 47
جدول 3-3. مقایسه الگوریتم‌های زمان‌بندی با فاکتور قابلیت اطمینان 70
جدول 4-1. مثالی از بار و توان پردازشی الگوریتم PPDD بدون قابلیت اطمینان 79
جدول 4-2 مدت زمان پردازش و اختلاف بار فعلی با بار ایده آل 79
جدول 4-3. یافته‌های اجرای مثال آلگوریتم PPDD با قابلیت اطمینان 81
فهرست علائم اختصاری
توافقنامه سطح سرویس Service Level Agreement SLA
ماشین‌های مجازی Virtual Machine VM
تعداد تراکنش‌های ماشین در هر ثانیه Million Instruction Per Second MIPS
گراف مدور جهت‌دار Directed Acyclic Graph DAG
کیفیت سرویس Quality of Service Qos
الگوریتم Min-Min با بار متعادل شده Load Balanced Min-Min Algorithm LBMM
توزیع زمان—هزینه Dispensation Time-Cost DTC
بهینه‌سازی ازدحام ذرات Particle Swarm Optimization PSO
الگوریتم زمان‌بندی منبع مجتمع پویا Dynamic And Integrated Resource Scheduling DAIRS
بودجه طراحی شده کاربر User-designated Budget UB
انتخاب بهترین مبنع Resource Best Select BRS
توزیع زمان هزینه Distribution Cost-Time DCT
اولین- رسیدن- اولین- سرویس first-come-first-service FCFS
توافق زمان- هزینه Compromised-Time-Cost CTC
توافق زمان- هزینه که هزینه اجرا را در مهلت زمانی تعیین شده مینیمم می‌کند Compromised-Time-Cost algorithmMinimising execution Cost CTC-MC
توافق زمان- هزینه که زمان اجرا مینیمم می‌کند Compromised-Time-Cost algorithmMinimising execution Time CTC-MT
بزرگ‌ترین تکه ابر، سریع‌ترین عنصر پردازشی Longest Cloudlet Fastest Processing Element LCFP
کوچک‌ترین تکه ابر، سریع‌ترین عنصر پردازشی Shortest Cloudlet Fastest Processing Element SCFP
عناصر پردازشی Processing Element PE
قیمت‌گذاری بر اساس فعالیت بهبود یافته Activity Based Costing ABC
تعداد تراکنش‌های ماشین Machine Instruction MI
الگوریتم زندگی زنبورها Bees Live Algorithm BLA
چندین گردش کاری با چندین محدودیت QQS Multiple QoS of Multi-Workflows MQMW
الگوریتم کاهش- تعادل BAlance-Reduce BAR
الگوریتم زودترین زمان پایان ناهمگن Heterogeneous Earliest Finish Time HEFT
الگوریتم زمان‌بندی آگاه از منبع Resource Aware Scheduling Algorithm RASA
مدیریت درست زمان‌بندی Scheduling Trust Management STM
نقاط آبروی Reputation Points RP
بهره‌وری ماکزیمم Utility Maximun UM
بالاترین قابلیت اطمینان Maximum Reliability Maxre
آگاهی از قابلیت اطمینان- منبع- مهلت زمانی Deadline-Reliability-Resources DRR
یادگیری تقویتی Reinforcement Learning RL
الگوریتم زمان‌بندی مبتنی بر ارتباط ماکزیمم تحمل خطا Failure-Tolerant Maximom Commonication Efficiency Driven FMCED
الگوریتم قابلیت اطمینان‌گرای تحمل خطای کارا Efficience Fail Tolerant Reliability Driven EFRD
زما‌بندی سطح پویا با قابلیت اطمینان Reliable Dynamic Level Service RDLS
زما‌بندی سطح پویا Dynamic Level Service DLS
سیستم محاسبات توزیع‌شده غیر همگن Heterogeneous Distributed Computing System HDCS
الگوریتم ژنتیک جلورونده Look-Ahead Genetic Algorithm LAGA
قابلیت اطمینانگرا Reliability Driven RD
الگوریتم ژنتیک Genetic Algorithm GA
الگوریتم ژنتیک دو هدفه Biobjective Genetic Algorithm BGA
زمان‌بند تطابقی با حداقل هزینه Minimum Cost Match Schedule MCMS
زمان‌بند با حداکثر کردن قابلیت اطمینان به طور تصاعدی Progressive Reliability Maximization Schedule PRMS
پایان نامه بررسی الگوریتم های زمان بندی وظیفه در محیط محاسبات ابری
