عنوان پایان‌نامه
تحلیل و بهبود قابلیت اطمینان در سیستمهای توزیع شده
- رشته تحصیلی
- مهندسی کامپیوتر -نرم افزار
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی پردیس 2 فنی شماره ثبت: E 2190;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 56877
- تاریخ دفاع
- ۰۵ مهر ۱۳۹۱
- دانشجو
- حمیدرضا فراگردی
- استاد راهنما
- ناصر یزدانی, مهدی کارگهی
- چکیده
- قابلیت اطمینان یکی از چالش های مهم در طراحی سیستم های کامپیوتری می باشد. به خصوص در کاربردهایی که قابلیت اطمینان در آن ها حیاتی می باشد (مانند کاربردهای نظامی، هسته ای و کنترل هوایی). در سیستم های توزیع شده معمولاً نرخ خرابی پیوندها و گره ها با هم متفاوت است و لذا توزیع مناسب وظیفه ها روی گره های سیستم می تواند بدون هزینه ی سخت افزاری یا نرم افزاری اضافی قابلیت اطمینان را تا حد زیادی بهبود بخشد. با این حال، تخصیص بهینه وظیفه ها در سیستم های توزیع شده مساله NP سخت بوده و برای سیستم هایی با اندازه های بزرگ حل آن در زمان قابل قبول، امکان پذیر نیست. در گذشته یک مدل ریاضی برای تحلیل قابلیت اطمینان با توجه به نحوه ی تخصیص وظیفه ها در سیستم های توزیع شده ارائه شده است. در این جا این مدل توسعه پیدا کرده تا این که بتواند محدودیت های سیستم های واقعی را مدل کرده و بیش از پیش تحلیل کارایی از سیستم ارائه کند. از جمله این محدودیت ها می توان به روابط پیش نیازی بین وظیفه ها و ضرب الاجل وظیفه ها اشاره کرد که در مدل قبلی لحاظ نشده بودند. همچنین با تغییری در مدل مذکور ازآن برای مدل کردن سیستم های بلادرنگ توزیع شده با وظیفه های متناوب استفاده شده است. پس از مدل کردن سیستم، برای یافتن تخصیص بهینه ی وظیفه ها به صورت برون خط در زمان قابل قبول، دو الگوریتم فراابتکاری پیشنهاد شده است. الگوریتم اول تبرید شبیه سازی شده حافظه دار سیستماتیک (SMSA) است که نسخه توسعه یافته ای از الگوریتم تبرید شبیه سازی شده (SA) می باشد. الگوریتم دوم بهینه سازی جفت گیری مورچه (AMO) است که الهام گرفته ازجفت گیری مورچه ها بوده و قابلیت الگوریتم های بهینه سازی کولونی مورچه (ACO)، SA و الگوریتم ژنتیک را به صورت هوشمندانه ی با هم ترکیب کرده است. پیچیدگی زمانی هر دو الگوریتم تحلیل شده اند. به علاوه برای ارزیابی کارایی این دو الگوریتم، چندین سیستم توزیع شده با توپولوژی شبکه متفاوت در نظر گرفته شده و نتایج بدست آمده با الگوریتم های SA و جفت گیری زنبور عسل (HBMO) مقایسه شده است. نتایج مقایسات نشان می دهد الگوریتم SMSA می تواند در زمان اجرای چندین برابر کم تر از SA و HBMO نتایجی بهتر از SA تولیدکند ولی کیفیت جواب های آن بهتر از HBMO نیست. AMO هم از نظر کیفیت جواب و هم از نظر زمان اجرا بهتر از HBMO و طبیعتاً بهتر از SA است. در پایان یک مساله بهینه سازی با دو هدف در سیستم های توزیع شده با توجه به نحوه ی توزیع وظیفه ها مطرح شده است. هدف حداکثر کردن قابلیت اطمینان در کنار حداقل کردن جریمه ی از دست دادن ضرب الاجل های نرم در یک سیستم توزیع شده بلادرنگ می باشد. مدلی برای این مساله نیز ارائه شده و سپس با استفاده از الگوریتم بهینه سازی جفت گیری مورچه حل شده است. نتایج بدست آمده برای وزن دهی های مختلف این دو تابع هدف نسبت به یکدیگر فراهم شده است.
- Abstract
- Distributed system has been developed as a platform for huge computations. Reliability is one of the prominent issues in such systems. The nodes and links of a DS typically have different hazard rates; therefore, proper task allocation can significantly improve system reliability. On the other hand, optimal task allocation in DSs is an NP-hard problem, thus finding exact solutions are limited to small-scale problems. Many studies have been done to improve reliability by proper task allocation in distributed systems, but they have only considered some system constraints such as processing load, memory capacity and communication rate. In this thesis, we consider task precedence constraint and also time constraint in form of task deadline to above-mentioned constraints in order to model and analyze reliability in real-time distributed systems. In addition, two new meth-heuristic algorithms to find near optimal solution are suggested. The first one is Systematic Memory-based Simulated Annealing (SMSA) which uses a monotonic cooling schedule and limited memory to store recently visited solutions to prevent cycling. The second one is based on a swarm intelligence technique and inspired by ants mating. Ant Mating Optimization (AMO) combines the power of simulated annealing, genetic algorithm with a specific heuristic local search to find the best possible solution within a reasonable computation time. We study the performance of the algorithms over a wide range of parameters such as the number of tasks, the number of processors, network topology, and task interaction density of applications. For evaluating the algorithm, SMSA and Ant Colony Optimization (ACO) are compared with Simulated Annealing (SA) and Honey Bee Mating Optimization (HBMO). Simulation results indicate that SMSA can produce better solution in contrast to SA in shorter execution time. Moreover, ACO produces better solutions than SA and HBMO. Meanwhile, it leads to shorter execution time. The results also reveal the flexibility and scalability of the proposed algorithms.
