پایان نامه بررسی الگوریتم های زمان بندی وظیفه در محیط محاسبات ابری

اختصاصی از رزفایل پایان نامه بررسی الگوریتم های زمان بندی وظیفه در محیط محاسبات ابری دانلود با لینک مستقیم و پر سرعت .

بررسی الگوریتم های زمان بندی وظیفه در محیط محاسبات ابری

چکیده :

محاسبات ابری به دلیل مزایا که دارد در سال های اخیر بسیار مورد استقبال قرار گرفته است،بدیهی است هر فن آوری در کنار مزایای خود، معایبی دارد، یکی از موارد چالش برانگیز این فن آوری قابلیت اطمینان آن است از این رو مسئله قابلیت اطمینان در الگوریتم های زمان بندی وظیفه که برای نگاشت منابع به وظایف می باشند را مرود مطالعه قرار داده.

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

الگوریتم 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