پایان نامه کشف بن بست عمومی و الگوریتم حل بن بست در سیستم های توزیع شده
موضوع پروژه:پایان نامه کشف بن بست عمومی و الگوریتم حل بن بست در سیستم های توزیع شده
فرمت فایل: WORD (قابل ویرایش)
تعداد صفحات فایل: ۳۷
فهرست
چکیده —————————————————————————————————۳
فصل اول «۱- مقدمه » ————————————————————————- ———–۴
فصل دوم «۲- کارهای انجام شده قبلی » ———————————————————————۷
۱-۲ کار پیشنهادی —————————————————————————————-۸
۲-۲ تفاوت بین الگوریتم پیشنهادی و الگوریتم های قبلی ————————- ————————–۸
۳-۲ کارهای مربوط ——————————————————————– ——————–۹
۴-۲ مدل سیستم و تعریف مسئله —————————————————————————۱۰
فصل سوم«۳- الگوریتم پیشنهادی جدید» ——————————————————————–۱۳
۱-۳ الگوریتم پیشنهادی ———————————————————————————–۱۴
۲-۳ مروری بر الگوریتم ———————————————————————————۱۴
۳-۳ توضیح الگوریتم ————————————————————————————۱۵
۴-۳ مثال————————————————————————————————- ۱۶
۵-۳ رفع بن بست ——————————————————————————————۲۰
۶-۳ توضیح الگوریتم ——————————————————————- —————–۲۰
۷-۳ مثال ————————————————————————————————-۲۴
۸-۳ اثبات درستی ——————————————————————————————۲۶
۹-۳ تحلیل بن بست —————————————————————————————–۲۷
۱۰-۳ تجزیه و تحلیل عملکرد ——————————————————————————-۲۷
۱۱-۳ تجزیه و تحلیل عملکرد ——————————————————————————-۲۹
فصل چهارم«۴- نتیجه گیری» ——————————————————————————- ۳۱
منابع ————————————————————————————————— ۳۳
چکیده انگلیسی —————————————————————————————— ۳۵
فهرست اشکال
شکل۱-۳ انتظار برای گراف ——————————————————————————-۱۹
شکل۲-۳ درخت پوشای توزیع شده—————————————————————————–۱۹
شکل۳-۳ انتظار برای گراف ——————————————————————————-۲۴
شکل۴-۳ گردش پیام—————————————————————————————–۲۵
شکل۵-۳ مدت زمان بن بست ———————————————————————————-۲۹
شکل۶-۳ ترافیک پیام ————————————————————————————۲۹
شکل۷-۳ طول پیام —————————————————————————————–۳۰
چکیده
ما یک الگوریتم توزیع شده جدید برای پیدا کردن بن بستهای عمومی درسیستم توزیع شده قصدداریم ارائه دهیم.
در این مقاله روی دو مقاله ی اصلی کار شده و الگوریتمهای موجود در هر دو مقاله مورد بررسی و مقایسه قرار گرفته:
۱-A decentralized deadlock detection and resolution
algorithm for generalized model in distributed systems
۲-An Efficient Detection and Resolution of Generalized
Deadlocks in Distributed Systems
در این مقاله،ما یک الگوریتم جدید برای شناسایی و حل و فصل بن بست های توزیع شده در مدل های تعمیم یافته پیشنهاد می کنیم.آغازگر الگوریتم پیشنهادی بررسیهایی در امتداد خروجی نمودار (WFG) پخش میکند و پاسخهایی که حامل اطلاعات وابسته بین فرایندها بطور مستقیم هستند جمع آوری میکند.با این حال،آغازگر شرایط باز گره های مسدود در پاسخ به یک پاسخ از یک گره مسدود را ساده سازی میکند و تقریباً دو پاسخ از هر گره را برخلاف الگوریتم قبلی دریافت میکند.در نهایت آن همه ی گره هایی را که به بن بست رسیده اند اعلام میکند.ما همچنین صحت الگوریتم را اثبات میکنیم. بدترین حالت پیچیدگی زمان( در مقاله۱ d+1 و پیچیدگی پیام کمتر از e+2n را دارد)و( در مقاله۲ پیچیدگی زمانی از واحدهای زمانی ۲d و پیچیدگی پیام ۲e است) که در آن d قطر، e تعداد لبه ها و n تعداد گره ها در WFG می باشد. از آنجا که کشف پایانی الگوریتم از کشف بن بست جدا شده است،طول پیام را با به حداقل رساندن بدون استفاده از هیچ روش صریح و روش به یک مقدار ثابت میرساند.این بهبود قابل توجهی روی الگوریتم های موجود دارد.و نیز دور اضافی ارسال پیام به بن بست های حل شده را به حداقل میرساند.
بهبود معنی دار الگوریتم برنامه ریزی شده برروی الگوریتمهای دیگر است که پیچیدگی ترافیک داده ها را با استفاده از ثابت نگه داشتن اندازه پیام ها ساده میکند. علاوه بر این ، پیام های اضافی را در حل دوباره بن بست به حداقل می رساند.
کلمات کلیدی سیستمهای توزیع شده،بن بست عمومی،انتظار برای گراف،کشف بن بست،حل بن بست
دیدگاه ها