فهرست مطالب
عنوان صفحه
1-1- مقدمه ای بر سیستم های توزیع شده: 5
1-3- تفاوت سیستم های توزیع شده و شبکه های کامپیوتری در چیست ؟ 5
1-4- سیستم های محاسبات خوشه ای 7
1-5- سیستم های محاسبات شبکه ای 7
1-7- Cloud computing and virtualization: 7
1-8- Parallel and distributed operating systems : 8
1-10- Wireless and ad-hoc networks: 8
1-11- Distributed Algorithms : 9
فصل 2- الگوریتمهای تشخیص بن‌بست 10
2-1-1- الگوریتم هو- رامامورتی 11
2-2- نمونه هایی از الگوریتم های تشخیص بن بست سلسله مراتبی 12
2-2-1- الگوریتم منساس- مانتز 12
2-2-2- الگوریتم هو-رامامورتی 13
2-3- نمونه هایی از الگوریتم های توزیع شده 14
2-3-1- الگوریتم تشخیص بن بست چندی – مسیرا– هاس 14
2-3-2- الگوریتم محاسبه پخش کردن چندی- مسیرا-هاس 15
فصل 3- تشخیص و رفع بن بست در پایگاه داده (سیستم) توزیع شده 29
3-2- روشهای صوری در تشخیص بن‌بست 30
3-3- بن‌بست از نقطهنظر گراف 32
3-4-1- 4.1 مدل تک منبع (one-resource) 34
3-4-2- 4.2 مدل عطفی (AND model) 36
3-4-3- مدل عمومی (Genral model) 37
3-5- مدیر داده آغازگر کاوشگر 41
3-6- تراکنش کاوشگرها را دریافت نموده میفرستد 42
3-7- دریافت کردن کاوشگر توسط مدیر داده 43
فصل 4- تشخیص و حل بن بست در سیستم های نماینده موبایل (نسل آینده سیستم های توزیع شده) 49
4-2- معرفی سیستم های نماینده موبایل (نسل آینده سیستم های توزیع شده) 50
4-3- تشخیص بن بست توزیع شده در سیستم های نماینده موبایل 52
4-4- معایب الگوریتم اصلی و مشکلات کارایی الگوریتم 57
4-5- الگوریتم تشخیص بن بست توزیع شده مبتنی بر اولویت بهبود یافته 64
4-6- آنالیز کارایی الگوریتم بهبود یافته 66
فصل 5- آشکار سازی بن بست در سیستم عامل توزیع شده 70
5-3-2- نمونه‌‌‌های بن بست متفاوت 76
5-4- الگوریتمهای آشکار سازی بن بست توزیع شده 77
5-6- روش تایم اوت (زمان سپری شده) 78
5-7- گروه بندی الگوریتمهای توزیع شده 79
5-8- الگوریتم های هل دادن (فشار) مسیر (جریان کار) 80
5-9- الگوریتم هایی بر پایه تحقیق 82
5-10- الگوریتمهای جستجوی لبه 82
5-12- خلاصه ای از الگوریتمهای آشکار سازی بن بست توزیع شده 85
- نمونه هایی از الگوریتم های تشخیص بن بست سلسله مراتبی
- الگوریتم منساس- مانتز
این الگوریتم یک الگوریتم سلسله مراتبی تشخیص بن بست است که برای بانک های اطلاعاتی توزیع شده ارائه شد. در آن بانک اطلاعاتی به مجموعه از زیر مجموعه های بانک اطلاعاتی تقسیم می شود . قفل کردو و کنترل های بن بست در ساختار درخت سازماندهی می شوند. هر کنترلر برگ یک زیرمجموعه را اداره می نماید، در حالیکه کنترلرهایغیربرگ مسئول تشخیص بن بست هستند. یک کنترلر برگ بخشی از گراف کاهش یافته را نگهداری می کند که کنترلر آن را اداره می نماید.
یک کنترلر غیر-برگ اطلاعاتی را شامل کنترلرهای بچه هایش را نگهداری می کند و مسئول تشخیص بن بست هایی که تنها شامل کنترلرهای بچه هایشاند، می باشد. یک کنترلر غیر-برگ، مراقب تغییرات مانند تخصیص، انتظار و رها کردن منبع کنترلرهای بچه هایش است. این کار می تواند بطور پریودیک انجام شود. بعد از هر بهنگام سازی گراف عمومی ، تشخیص بن بست توطی یک گره غیر برگ انجام می شود. این الگوریتم برای مدل AND طراحی شده است و بدنبال چرخه می گردد.
- الگوریتم هو-رامامورتی
در الگوریتم سلسله مراتب که توسط آنها ارائه شد ، سایت هایی که به یکدیگر نزدیک اند در یک خوشه[1] گروه بندی می شوند. یک سایت در یک خوشه بطور پریودیک بعنوان سایت کنترلی انتخاب می شود. این سایت کنترلی اطلاعات جدول وضعیت را از همه سایت های در یک خوشه جمع آوری می کند و یک پروتکل تشخیص بن بست یک مرحله ای برای تشخیص بن بست های درون-خوشه ای اجرا می نماید. همچنین سایت کنترل مرکزی بطور داینامیک انتخاب می شود و اطلاعات درون – خوشه ای را جمع آوری می کند و یک گراف وضعیت کل سیستم جهت تشخیص بن بست می سازد.
- نمونه هایی از الگوریتم های توزیع شده
- الگوریتم تشخیص بن بست چندی – مسیرا– هاس
الگوریتم کاملاً توزیع شده تشخیص بن بست به وسیله چندی-مسیرا-هاس در سال 1993 ارائه شده است. این الگوریتم یک الگوریتم مبتنی بر تعقیب یال است. الگوریتم آنها یکی از بهترین الگوریتم های تشخیص بن بست در سیستم های توزیع شده است.
روش کار بدین صورت است که اگر یک فرآیند درخواست منبعی نموده که درخواست آن با شکست مواجه شود یا زمان انقضا[2]شود ، فرآیند پیام کاوشگر تولید نموده و آن را به همه فرآیندهایی که یک یا بیش از یک منبع مورد نیاز آن را در اختیار دارند می فرستند. هر پیام کاوشگر شامل اطلاعات زیر می باشد :
- شناسه فرآیندی که مسدود شده است (فرآیندی که پیام کاوشگر را آغاز نموده است)،
- شناسه فرآیندی که در حال ارسال نتیجه ای از پیام کاوشگر است،
- شناسه فرآیندی که باید این پیام کاوشگر را دریافت نماید.
زمانی که فرآیندی یک پیام کاوشگر دریافت می نماید، کنترل می کند تا ببیند آیا آن هم منتظر فرآیند دیگری است یا نه اگر نباشد ، او در حال استفاده از منبع است و سرانجام کارش تمام می شود و منبع را رها می نماید. اگر او هم منتظر منبعی باشد ، او پیام کاوشگر را به همه فرآیندهایی که منبع را نگه داشته اند و او منتظر آنها است می فرستند. فرآیند ابتدا پیام کاوشگر را به هنگام نموده و شناسه فرستنده و گیرنده آن را تغییر می دهد.
اگر فرآیندی پیام کاوشگری را که خودش آغاز کرده بود ، دریافت نمایید ، تشخیص می دهد که یک چرخه در سیستم وجود دارد و بنابراین بن بست رخ داده است.
این الگوریتم دارای ویژگی های زیر می باشد:
- پیاده سازی آسانی دارد.
- هر پیام کاوشگر دارای طول ثابتی است.
- محاسبات کمی وجود دارد.
- سربار کمی دارد.
- نیاز به ساختن گراف عمومی نیست.
- نیاز به ارسال اطلاعات گراف به سایت های دیگر نیست.
- این الگوریتم بن بست نادرست تشخیص نمی دهد (البته تحت شرایط خاص)
- نیاز به ساختار داده خواصی نمی باشد.
- الگوریتم محاسبه پخش کردن چندی- مسیرا-هاس
چندی-مسیرا-هاسالگوریتم تشخیص بن بست توزیع شده ای را برای مدل OR ارتباطی ارائه نمودند. در این الگوریتم به پیام ها "پرس جو " و به سیگنال ها " پاسخ " گفته می شود . یک وظیفه ای که مسدود شده است ، بن بست را با ارسال یک پرس و جو به مجموعه وابسته اش آغاز می کند. یک وظیفه در حال اجرا تمامی پرس و جوها و پاسخ ها را نادیده می گیرد. بعبارت دیگر ، اگر محاسبات پخش شدن به یک وظیفه مسدود شده برسد ، آن وظیفه مسدود شده بکارگرفته می شود و در محاسبات شرکت می کند. به یک پرس و جو زمانی که به وظیفه بکار گرفته شده می رسد ، پاسخ داده می شود. به یک پرس و جو در صورتیکه در یال های یک چرخه در حال سفر کردن باشد ، پاسخ داده می شود و همه یال های بکار گرفته شده لغو می شوند. از این فرض که یال های بکار گرفته شد نمی توانند تشکیل چرخه دهند ، استفاده شده است. همه پرس و جوهایی که آغاز شده اند در صورتی چرخه پیدا می کنند که محاسبه پخش شدن تمام شود و آغاز کننده به وضعیت طبیعی اش بازگردد.
متعاقباً آغاز کننده در صورتیکه به وضعیت طبیعی خودش بازگردد ، دچار بن بست شده است. بعنوان مثال ،یک وظیفه مسدود شده Ta تشخیش بن بست را با محاسبات پخش شدن آغاز می کند و نیاز به منابع Bیا Cدارد که بوسیله وظایف Tbو Tcنگه داشته شده اند. وضعیتی را در نظر بگیرید که وظیفه Tbدر حال اجراست و وظیفه TcمنتظرTa است. پرس و جویی که وظیفه Tbمی رسد ،نادیده گرفته می شود زیرا این وظیفه مسدود شده نیست.بمحض رسیدن پرس و جوی از Ta،وظیفه Tcبکار گرفته می شود و پرس و جو را به همه مجموعه وابستگی اش (Ta) ارسال می نماید. زمانیکه Taدر وضعیت بکار گرفتن است ، فوراً به Tcپاسخ می دهد. زمانیکه Tcپاسخ را از Taدریافت می کند ، یک پیام پاسخ بکار گرفتن به Ta می فرستد و به وضعیت عادی برمی گردد. پرس و جو و پاسخ گیری در این لحظه از وظیفه Ta ارسال نمی شود. وضعیت دیگری را در نظر بگیرید که هر دو وظیفه TbوTcمنتظر وظیفه Taهستند . هر دو یال (TbوTa) و (TcوTa) سرانجام لغو خواهند شد. در نهایت وظیفه Ta محاسبه را تمامی می کند و بعد از دریافت پاسخ از همه وظیفه هایی که در مجموعه وابستگی اش یعنی (TbوTa)هستند پاسخ دریافت نماید، اعلان بن بست می کند و به وضعیت طبیعی خودش باز می گردد.
- الگوریتم براچا- توگ
آنها الگوریتمی برای پردازش تصاویر لحظه ای GRGسیستم بمنظور پیدا کردن بن بست در مدل (k،n)Cارائه نمودند. از آنجایی که ساختار ساده ای در تعوری گراف برای چیدا کردن بن بسست در مدل (k،n)C وجود ندارد،تکنیک کاهش گراف بمنظور تعیین وجود بن بست استفاده شده است. خر وظیفه فعالی در تصویر لحظه ای GRGمی تواند بمنظور خاتمه و رها نمودن منابعی که در دست دارد ، زمانبندی شود. سپس GRGمی تواند به یک وضعیت جدید کاهش داده شود. به یک GRG کاملاً کاهش پیدا کرده می گویند اگر دنباله ای از کاهش های گراف که هر کدام GRG را به یک مجموعه ایزوله از گره ها کاهش می دهند ، وجود داشته باشد.وظیفه مانند Ti در وضعیت Sدچار بن بست نشده است اگر و تنها اگر مجموع های از کاهش های GRG مربوطه اش وجود داشته باشد که اجازه می دهند که Ti از حالت مسدود خارج شود. اگر یک GRG بطور کامل کاهش داده شود ، وضعیتی که در آن نشان داده می شود ، وضعیت بن بست رده نیست.
90 - پروژه آماده: بررسی سیستم های تشخیص و رفع بن بست در سیستم های توزیع شده - 93 صفحه فایل ورد (word)
