دانلود پاورپوینت بن بست ها Deadlocks

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

تعداد اسلایدها : 36 اسلاید          

دانلود پاورپوینت بن بست ها (Deadlocks ) در سیستم های کامپیوتری

اختصاصی از فی بوو دانلود پاورپوینت بن بست ها (Deadlocks ) در سیستم های کامپیوتری دانلود با لینک مستقیم و پر سرعت .

پاورپوینت   بن بست ها (Deadlocks )  در سیستم های کامپیوتری در 35 اسلاید شامل بخش های زیر می باشد:

مقدمه

اصول بن بست

شرایط لازم برای بوجود آمدن بن بست

مدل سازی بن بست 

Deadlock Modeling

کلا چهار استراتژی ممکن است در ارتباط با پرداختن بهDEADLOCK  استفاده شود.

The Ostrich Algorithm

Recovery from Deadlock (1)

Recovery from Deadlock (2)

Deadlock Avoidance
Resource Trajectories

Safe and Unsafe States

اجتناب از بن بست

الگوریتم بانکدار برای منابع چند گانه ( یعنی از چند نوع مختلف )

پیشگیری از بن بست     DEADLOCK  PREVENTION

Attacking the No Preemption Condition

Attacking the Circular Wait Condition (1)

Other Issues
Two-Phase Locking

Nonresource Deadlocks

Starvation

مقدمه

کامپیوتر ها دارای منابع زیادی هستند که در هر لحظه فقط توسط یک   processمی توانند استفاده شوند . مثلا  printer  ها ،tape drive   ها ، scanner ها ، slot  های  process table .

اگر دو پروسس همزمان بخواهند در یک slot درون process table  بنویسند، باعث خراب شدن سیستم میشود.اگر دو پروسس بخواهند روی printer   بنویسند حاصل آشغال خواهد بود.

بنا بر این تمام سیستمهای عامل قدرت تخصیص دسترسی انحصاری (به طور موقت) به منابع مشخصی را دارند . در بسیاری از برنامه های کاربردی ، process نیازانحصاری به چندین منبع را دارد . فرض کنیدقرار باشد نقشه یک کشور از روی یک cd ،روی یک   plotterبرده شود . فرض کنید process Aدرخواست  cd-Rom کند وcd-Rom  به او تخصیص یابد. کمی بعد  process Bدرخواست  plotterکند وبه او داده شودحالا  process A درخواست  plotterکند،و در انتظار آن منبع ،block شود . سپس  process B، تقاضای cd_Rom driverکند وblock شود . در این لحظه هر دوی process ها در حالت    blockهستند و تا ابد در این حالت باقی می مانند . این وضعیت   deadlockنام دارد.

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

دنباله اتفاقات در مورد استفاده از یک منبع به این صورت است:

.1تقاضا برای منبع

.2استفاده  از منبع    

.3آزاد کردن منبع

typedef int semaphore;                                   typedef int semaphore;

semaphore resource_1;                                   semaphore resource_1;

                                                                       semaphore resource_2;

void process_A(void) {                                      

        down(&resource _1);                              void process_A(void) {

        use_resource_1( );                                          down(&resource _1);

        up(&resource _1);                                          down(&resource _2);           

                                                                              use_both_resources( ); 

}                                                                            up(&resource _2);

                                                                              up(&resource _1);

                                                                       }   

                 (a)                                                                   (b)

اصول بن بست

تعریف رسمی بن بست این است:

     مجموعه ای از processها در حالت بن بست قرار دارد اگر هر process

    این مجموعه منتظر اتفاقی باشد که فقط  process دیگری در این مجموعه میتواند ایجادش کند.از آنجا ئیکه همه پروسس ها منتظر هستند،هرگزهیچ یک  از آنها نمی تواند اتفاقی که باعث بیدار شدن  عضو دیگری از مجموعه شود

    را ایجاد کنند  و همه process ها برای همیشه منتظر خواهند بود....

پایان نامه جامع و کامل بررسی تشخیص بن بست در سیستم‌های توزیع شده

اختصاصی از فی بوو پایان نامه جامع و کامل بررسی تشخیص بن بست در سیستم‌های توزیع شده دانلود با لینک مستقیم و پر سرعت .

فرمت فایل : word (قابل ویرایش) تعداد صفحات : 97 صفحه

فهرست مطالب

مقدمه................................................................. 1

فصل اول: تشخیص بن بست در سیستمهای توزیع شده.......................... 2

1-1- مفاهیم پایه......................................................... 3

1-2- انواع مدلهای بن‌بست بر اساس سیستم تبادل پیام.......................... 3

1-3- انواع مدلهای بن‌بست بر اساس نوع درخواست............................ 3

1-4- شرایط وجود بن‌بست.................................................. 5

1-5- طبقه‌بندی الگوریتم‌های تشخیص بن‌بست................................ 5

فصل دوم: مروری بر الگوریتم‌های تشخیص بن‌بست............................. 9

مقدمه....................................................................10

2-1- نمونه‌ای از الگوریتم متمرکز جهت تشخیص بن‌بست در سیستمهای توزیع‌شده..... 10

2-1-1- الگوریتم هو- رامامورتی........................................... 10

2-2- نمونه‌ای از الگوریتم‌های تشخیص بن‌بست سلسله‌مراتبی................... 11

2-2-1- الگوریتم منساس – مانتر............................................ 11

2-2-2- الگوایتم هو – رامامورثی....................................... 11

2-3- نمونه‌هایی از الگوریتم‌های توزیع‌شده............................... 11

2-3-1- الگوریتم تشخیص بن‌بست چندی – مسیرا – هاس...................... 11

2-3-2- الگوریتم محاسبه پخش کردن چندی – مسیرا – هاس..................... 12

2-3-3- الگوریتم براچا – توگ............................................. 13

2-3-4- الگوریتم منساس و مانتز2-3-5- الگوریتم ابرمارک..................... 13

2-3-5- الگوریتم ابرمارک................................................ 14

2-3-6- الگوریتم بدالض...................................................... 15

فصل سوم: مروری بر الگوریتم‌های تشخیص بن‌بست توزیع شده تعقیب یال.......... 20

مقدمه............................................................... 21

3-1- بررسی الگوریتم‌های تشخیص بن‌بست تعقیب یال......................... 22

3-1-1- الگوریتم میچل و مریت........................................... 22

3-1-2- الگوریتم سینها و ناتارجان......................................... 23

3-1-3- الگوریتم چودهاری – کوهلر – استنکویچ و توسلی................... 23

3-1-4- الگوریتم سینقال و شمکالیانی........................................ 24

3-1-5- تشخیص بن‌بست توزیع شده و حل آن بر اساس ساعتهای سخت‌افزاری....... 24

3-2- ارائه روشی برای حذف بن‌بست نادرست در الگوریتم‌های تشخیص بن‌بست...... 25

3-3- نتیجه‌گیری........................................................... 27

فصل چهارم: الگوریتم‌های تشخیص بن‌بست توزیع شده تحمل خطاپذیر............. 29

مقدمه........................................................ 30

4-1- مروری بر الگوریتم‌های تحمل‌پذیر خطا جهت تشخیص بن‌بست.............. 31

4-2- معرفی مدل سیستم تشخیص خرابی بر اساس شاخص زمان اتصال.............. 33

4-3- یک الگوریتم تشخیص بن‌بست توزیع شده تحمل‌پذیر خطا................... 34

4-4- اثبات درستی الگوریتم.............................................. 37

4-5- نتیجه‌گیری......................................................... 38

فصل پنجم: تشخیص و حل بن‌بست در سیستمهای نماینده موبایل................. 39

مقدمه............................................................... 40

5-1- معرفی سیستمهای نماینده موبایل(نسل آینده سیستمهای توزیع شده)............... 41

5-2- تشخیص بن‌بست توزیع‌شده در سیستمهای نماینده موبایل.................. 41

5-3- معایب الگوریتم اصلی و مشکلات کارایی الگوریتم...................... 44

5-4- الگوریتم تشخیص بن‌بست توزیع شده مبتنی بر اولویت بهبودیافته................. 47

5-4-1- آنالیز کارایی الگوریتم بهبودیافته.................................... 48

5-4-2- اثبات درستی الگوریتم............................................ 49

5-5- نتیجه‌گیری....................................................... 50

نتیجه‌گیری.............................................................. 51

فهرست منابع............................................................... 53

پیوست‌ها................................................................ 55

 

جدول 2-1- مقایسه الگوریتم های بررسی شده تشخیص بن بست.................... 17

جدول 2-2- مقایسه کارایی الگوریتم های بررسی شده........................... 19

جدول 3-1- مقایسه مدل های الگوریتم های بررسی شده کلاس تعقیب یال......... 27

جدول3-2-  بررسی صحت الگوریتم های بررسی شده.......................... 28

مقدمه

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

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

 طی دهه اخیر الگوریتم های زیادی برای تشخیص بن بست در سیستم های توزیع شده ارائه شده است که تعداد زیادی از آنها موفق به تشخیص بن بست نمی شوند و یا بن بست هایی را گزارش می کنند که در واقع وجود ندارند و یا اینکه اثبات شده است که نادرست اند.

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

دانلود مقاله بررسی آشکار سازی بن بست در سیستم عامل توزیع شده

اختصاصی از فی بوو دانلود مقاله بررسی آشکار سازی بن بست در سیستم عامل توزیع شده دانلود با لینک مستقیم و پر سرعت .

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

1- مقدمه
در طول دهه گذشته سیستمهای محاسبه گر پیشرفت سریعی داشته اند که تأثیر زیادی بر سیستم عاملهای توزیع شده دارد. در حالیکه سیستم‌های تجاری به تدریج پیشرفت می کنند، چالشهای جدید بوسیله ارتباط گسترده جهانی سیستم‌های کامپیوتری وضع شده است.
این جریان یک نیاز رشد کننده‌‌ای برای راه حلهای توزیع شده با مقیاس بالا ایجاد می‌کند. در آینده، سیستم عاملهای توزیع شده باید صدها و حتی هزاران سایت و میلیونها مراجع را حمایت کنند و بنابراین با چالشهای بزرگی در ارتباط با اجرا، در دسترس بودن و مدیریت مواجه خواهند شد. یکی از چالشهایی که ما باید حل کنیم در این حوزه مشکل بن بست است. همچنین نسبت یکی از جدی ترین مشکلات در سیستم‌ های برنامه ریزی رایج چند کاره است.
بقیه مقاله مثل زیر سازمان دهی شد. بخش 2 مختصرا بن بست و حوزه آن در سیستم عاملهای توزیع شده را توزیع می دهد.
در حالیکه بخش 3 یک شرحی از مشکل بن بست ارائه می دهد و 2 الگوی بن بست که به طور کلی در سیستم‌های بانک اطلاعاتی توزیع شده به کار می رود. یک گروه بندی از الگوریتم‌‌های توزیع شده برای این الگوها و نماینده‌های گروه های مختلف در بخش 4 شرح داده شده است. نهایتا، ما در بخش 5 خلاصه می کنیم، در حالیکه بخش 6 مرجهای ما را توصیف می کند.

2- پیش زمینه
در این بخش ما تلاش می کنیم تا نگاهی بر مقالات بررسی که بوسیله دیگران در روش آشکار سازی بن بست ارائه شده است داشته باشیم.
متون بن بست رسما یک بن بست را به عنوان یک مجموعه فرایندی که بن بست است، اگر هر فرایند در مجموعه منتظر یک رویدادی است که تنها فرایند دیگری در مجموعه می تواند موجب شود. تعریف می کند. [2 و 1]. یک تعریف غیررسمی تر این است که بن بست‌ها می تواند هر زمانی که 2 یا چند فرایند برای منابع محدودی رقابت می کنند و فرایندها برای یافتن و حفظ یک منبع فراهم شده است اتفاق بیافتد. اگر یک فرایند برای منبعی، انتظار بکشد، هر منبعی که آن حفظ برای فرایندهای دیگر در دسترس نیستند. اگر فرایندی برای منبعی که بوسیله فرایند دیگری حفظ شده است انتظار می‌کشد، که در بازکش در حال انتظار برای یکی از منابع نگهداری آن ما یک بنسبت داریم. هنگامیکه یک سیستم به این وضعیت می رسد، به طور مؤثر، بسته می شود: و باید مشکل را برای ادامه عملکرد حل کنیم.
4 شرط وجود دارد که یک بن بست نیاز دارد:
1- حذف متقابل: هر منبعی می تواند به یک منبع خاص تخصیص یافته شود.
2- حفظ و انتظار: فرایندها می توانند یک منبع و درخواست بیشتر حفظ کنند.
3- بدون پریامپشن: منابع نمی توانند بالاجبار از یک فرایند حذف شوند.
4- انتظار حلقوی: باید یک زنجیره حلقوی از فرایند وجود داشته باشد هر انتظاری برای یک منبع نه بوسیله شماری از زنجیره‌های بعدی نزدیک حفظ شده است.
به طور معمول 4 روش در ارتباط با بن بستها به کاربرده شده است
1- نادیده گرفتن مشکل
2- آشکار سازی بن بست
3- جلوگیری از بن بست
4- اجتناب از بن بست
نادیده گرفتن بن بستها آسانترین برنامه برای تکمیل است. آشکار سازی بن بست تلاش می کند تا بن بست ها را قرار دهد و حل کند. اجتناب از بن بست روشهایی را شرح می دهد که تلاش می کند تا تعیین کند آیا یک بنبست در زمانی که یک منبع درخواست می شود و نسبت به درخواستی در یک حالتی که از بن بست اجتناب می‌شود عکس عمل نشان می دهد. اتفاق خواهد افتاد. جلوگیری از بن بست ساختن یک سیستمی در یک حالتی که یکی از 4 شرط ضروری برای بن بست امکان پذیر نباشد است. هر گروه راه حل متناسب با یک نوع خاص محیط است و فواید و نقایص دارد. در این مقاله ما به آشکار سازی بن بست که شایع ترین راه حل بن بست تکمیل شده است تمرکز می کنیم.
در سیستم‌های بانک‌ها اطلاعاتی توزیع شده، آشکار سازی بن بست خیلی پیچیده می‌شود به عنوان یک نتیجه‌ای از بی ثباتی در وضعیت سیستم جهانی. اگر چه الگوریتم‌های آشکار سازی بن بست زیادی در سیستم های بانک اطلاعاتی توزیع شده مطرح شده است اکثر آنها به خاطر سربارهای سیستم بالا غیر عمل هستند.
2 روش اصلی در آشکار سازی بن بست توزیع شده شکل گرفته است. ابتدا یکی که برای ساخت وضعیت یک سیستم جهانی است و دومی برای تلاش در جهت عبور از یک پیغام خاص از طریق ترانکش‌ های بلوکه شده به منظور آشنا ساختن یک چرخه بن بست است. یک روش از روش دومی آشکار سازی بن بست توزیع شده بر پایه دلیل همان طور که توسط چندی و مسیرا و هس مطرح شده است. ترکیب اصلی این متد این است که هیچ وضعیت سیستم جهانی مورد نیاز نیست.
الگوریتم آشکار سازی بن بست کندی بر پایه احتمالی از طریق سایتهای مختلف است. تنها فرایندهایی که در مرز سایتهای یافت می شود می تواند پیغام‌های بررسی را آغاز کند. الگوریتم کندی می تواند برای آشکار سازی بن بست توزیع شده بر پایه بررسی کندی در [2] ارائه شد. به عنوان یک نتیجه از سربازهای سیستم بالا که در حفظ جدول وابستگی برای mpa ایجاد شد انتظار می رود عملکرد سیستم یک شکل اساسی داشته باشد. یک نسخه پشرقه از MPA (EPA) با جایگزینی جدول استقلال (وابستگی) با یک انتظار برای نوشتن تعریف شد.
بررسی اولیه به این کار در متن سیستم‌ های بانک اطلاعاتی توزیع شده بوسیله المگاوامیه مطرح شده است به هر صورت محققان زیادی احساس می کنند که نیازهای درجه بند و عملکرد که بوسیله سیستم‌های توزیع شده مقیاس بالا وضع شده مورد نیاز برای بروز روشهای مکمل پیشرفته است.
در یک مقاله‌ای از نپ الگوریتم‌های آشکارسازی بن بست توزیع شده در گروههای زیر تقسیم بندی شد:
1- روش مرکزی شده توسط حفظ انتظار برای نوشتن جهانی
2- الگوریتم هل دادن مسیر توسط فرستادن بخشهایی از WFG به سایتها مجاور
3- آشکار سازی جستجوی لبه با فرستادن بررسی‌ها
4- رد محاسبات با فرستادن بررسی‌‌هایی به همه فرایندهای وابسته (OMS) و انتظار برای دریافت پاسخ.
5- آشکار سازی وضعیت جهانی که بخشهای مرتبط نقشه WFG در یک هرم منسجم جهانی بدون حفظ محاسبات ساخته شده است.
DDA برنامه DDA اینجا می تواند تحت 5گروه ارائه شود.

3- مشکل بن بست عمومی
در اکثریت سیستم‌های بانک اطلاعاتی مدرن کنترل همزمان بر پایه مکانیزم‌‌های قفل کردن است. اکثر سیستم‌ها پروتکل PL2 محکمی را استفاده می کنند. پروتکل قفل کردن می تواند موجب بن بست شود. یک بن بست یک شرایط انتظار حلقوی موقت است. یک مجموعه از تراکنش‌ها بن بست. شده هستند اگر هر کدام از تراکنش‌ ها برای قفلهایی که توسط تراکنش‌های دیگر از این مجموعه انتظار می کشند. همه تراکنش‌‌ها می توانند در مجموعه در یک حالت انتظار باشند یعنی راهشان سد شده است و هیچ کدام از آنها بدون دخالت بیرون باز نمی شوند. نمونه‌های قفل کردن مختلف می تواند بوسیله الگوریتم‌های کنترل همزمان مورد استفاده باشد.
هنگامیکه از قفل کردن معنایی استفاده می شود. یک تراکنش ممکن است برای تنها یک زیرمجموعه از نگهدارنده‌های هدف انتظار بکشد. همچنین تراکنش‌‌های مختلفی که بلوکه شده اند در همان شی ممکن است. برای زیر مجموعه‌های متفاوتی از نگهدارندها شی انتظار بکشد. اداره کردن بن بست قفلها شامل 2 مسئله می شود. آشکارسازی بن بست و راه حل بن بست، در یک مفهوم راه حل بن بست DBMS که یکی از تراکنش‌های شرکت کننده، فرمانی برای ناتمام ماندن انتخاب شده است بدان وسیله بن بست حل می شود.
الگوریتم آشکارسازی یک بن بست اگر 2 شرط را رعایت کند صحیح است:
1- هر بن بست به تدریج آ‌شکار می شود (خصوصیت پیشرفت اساسی) و
2- هر بن بست آشکار شده‌ای در واقعیت وجود دارد، یعنی، تنها بن بست های عملی آشکار شده هستند (خصوصیت ایمنی).
در حالیکه اولین شرط روشن است، دومی نیاز به توضیح دارد. اگر چه یک بن بست یک خصیصه باثبات است، به واسطه اطلاعات قدیمی ممکن است که همان بن بست آشکار شود و یا دوباره حل شود. بن بست‌های آشکار شده که واقعا وجود ندارند بن بستهای فانتوم نامید می شوند. موردی که قابل بحث است این است تا یک الگوریتم آشکار کننده بن بستهای فانتوم می توانست صحیح بنظر برسد اما ناتمام های ترانکشن غیرضروری آنچنان گران گران هستند که قابل تحمل نیستند.
هر الگوریتم آشکار سازی بن بست ممکن است بن بستهای فانتوم را اگر ناتمام‌‌های همسان اجازه دهند آشکار سازد. اگر یک الگوریتم تصمیم بگیرد ناتمام بگذارد یک ترانکشن را به منظور حل یک بن بست و در همان زمان ترانکشن‌های دیگر ناتمام‌‌های بن بست را در برگیرند در نتیجه حل شدن بن بست الگوریتم بن بست فانتوم را می‌شکند. بنابراین ما فرض خواهیم کرد که هیچ ناتمام همسانی در سیستم اتفاق نمی‌افتد.
1-3- انتظار برای نمودار
شرایط بازدارنده بین تراکنش‌ها می تواند از طریق یک ترانکشن منتظر برای نمودار (WFG) ارائه شود. یک WFG یک نموادر مستقیم است که گره‌‌ها مطابق با ترانکشن‌ها و یک لبه مستقیم برای بیان آن انتظار برای یک منبع حفظ شده است.
یک بن بست می تواند بوسیله بررسی ساختار WFG آشکار شود. ساختار نمودار نشان می دهد که بن بست وابسته به نمونه بن بست است به عنوانی که در فصل بعد توضیح داده شده است به کار می رود.

2-3- نمونه‌‌‌های بن بست متفاوت
وابسته به نمونه محاسباتی در انواع درخواستهایی که توسط ترانکشن ها ایجاد می‌شود. نمونه‌های بن بست متفاوت به کار برده می شود. در DBMS توزیع شده منبع مجردی و نمونه AND در حال غالب شدن است، آنچنان که آنها در این جا مورد بحث قرار می گیرند. توضیحات نمونه‌های دیگری مثل نمونه or و نمونه کلی، که کمتر معمول هستند در فصل 5 ارائه شده است.
ساده ترین و مورد استفاده ترین نمونه در DBMS ها نمونه منبع مجرد است. در این نمونه یک ترانشکن یک درخواست برجسته در یک زمان دارد یعنی یک قفل در یک مورد درخواست می کند. اگر چه یک ترانکشن تنها یک درخواست بیرون رونده در یک زمان دارد، ممکن است برای بیش از یک ترانکشن انتظار بکشد.
یک بن بست در نمونه منبع مجرد مطابق با یک چرخه از ترانکشن‌ های منتظر است. بنابراین الگوریتم‌ها برای این نمونه یک بن بست را جدا می کنند. چرخه اگر یکی از ترانکشن‌های مرتبط ناتمام بماند و بدان وسیله قفلها را باز کند حل می‌شود.
برای این مدل الگوریتم‌های زیادی ارائه شده است. در یک مدل محاسباتی که در آن یک ترانکشن می تواند بیش از یک درخواست در یک زمان بفرستد و باید تا زمانی که همه آنها تأیید بشوند انتظار بکشد، بن بست‌ها بوسیله مدل AND توصیف شده اند. برای مثال این مدل در سیستم‌های حمایت کنند تراکنشها جای گرفتند بکار می رود، یک بن بست در این مدل دوباره از طریق یک چرخه در WFG نشان داده می شود.

4- الگوریتم‌های آشکار سازی بن بست توزیع شده
الگوریتمهای آشکار سازی بن بست توزیع شده زیادی برای DBMS های توزیع شده گسترش یافته است که بررسی ها در 10 و 5 و 4 یافت می شود. این مقاله بر الگوریتم های توزیع شده برای منبع و مدل AND تمرکز دارد. ما الگوریتمهای توزیع شده را براساس روشهایی که آنها استفاده می کنند شبیه به گروهبندی پیشنهادی در [5]، توضیح روشهای مختلف و توصیف یک نمونه از هر گروه در جزئیات بیشتر گروه بندی می کنیم. ما این الگوریتم ها را انتخاب می کنیم که برای بهترین بودن در گروهشان ظاهر می شوند، یعنی کمترین تعداد پیغامها را کاهش می دهند و ابتدا در فصل 1-4 ما یک نگاهی به استراتژی های راه حل بن بست خواهیم داشت.
1-4- راه حل بن بست
استراتژی‌های راه حل بن بست تعیین می کند که ترانکشن‌ها به منظور حل بن‌بست‌ها نا تمام می مانند. استراتژی های راه حل زیادی برای سیستم‌های مرکزی ارائه شده است. بعضی از آنها بوسیله 11 مقایسه شده است. براساس نتایج متحرکات، 2 شرط تعیین کردند که هر راه حل باید تضمین کند: 1- همیشه تضمین کند که حداقل یک ترانکشن در سیستم تمام شود و 2 هیچ ترانکشنی ناتمام نخواهد ماند.
اولین شرط در ارتباط با خصوصیت بیان شده در فصل 3 است این خصیصه ضمانت می کند که هیچ بن بستی وجود نخواهد داشت اما اطمینان نمی دهد که همه ترانکشن‌ها پایان یابند. یک آشکارسازی و الگوریتم راه حل بن بست تعیین کننده است که چه چیز انتظار می رود. صراحتا شرایط مطرح شده برای DBMS های توزیع شده حفظ می شود.

2-4- روش تایم اوت (زمان سپری شده)
در این الگوریتم یک ترانشکن یک تایم اوت هر زمانی آن یک درخواست عملکرد ایجاد کند شکل می دهد. اگر هیچ تقدیری دریافت نکند که نشان موفقیت آمیز بودن عملکرد باشد قبل از اینکه زمان به پایان برسد فرض می کنیم که درگیر یک بن بست و ناتمام شده است.
الگوریتم ساده است و بنابراین آسان تکمیل می شود. همچنین به واسطه آشکار سازی بن بست موجب ترافیک شبکه‌ای نمی شود.
فایده اصلی الگوریتم این است که آن تعداد زیادی ترانکشن را ناتمام می گذارد که ممکن است بن بست نباشند و در نتیجه موجب عکس العمل‌های غیرضروری و دوباره راه اندازی ترانکش ها می شود.
فایده دیگر این است که فاصله تایم اوت (زمان سپری شده) باید منظم باشد. اگر خیلی کوتاه است حتی بیتشر از زمانی که ترانکشهای غیرضروری ناتمام می مانند. اگر آنقدر طولانی است که بن بست‌ها در سیستم برای یک مدت طولانی باقی می مانند و در نتیجه موجب تأخیر ترانکشن در بن بست و انتظار برای قفلهایی که توسط آنها ایجاد شده است می شود.
در دوازده این طور مطرح شده است که ممکن است بعضی اوقات ناتمام ماندن تراکنشهای زیادی مطلوب نباشد، این نشان می دهد که بار قفل کردن آنچنان بالا نیست. این ممکن است صحیح باشد اما یک الگوریتم آشکار سازی بن بست نباید برای برنامه ریزی روزانه مسئول باشد.

3-4- گروه بندی الگوریتم‌های توزیع شده
الگوریتمهای آشکار سازی بن بست توزیع شده متفاوت زیادی برای DBMS ها منتشر شده است.
آنها می توانند به دو گروه زیر تقسیم شوند: 1- هل دادن مسیر 2- بر پایه بررسی
3- الگوریتمهای آشکار سازی وضعیت جهانی.
قبل از اینکه ما الگوریتمها و گروههای مختلف را توضیح می دهیم می خواهیم فرضیاتی را که فراهم کرده ایم مختصرا بیان کنیم در بخشهای قبل مطرح شد که ما در اینجا یادآوری می کنیم. ابتدا دو فرضیه در ارتباط با عملکرد ترانکشن‌ها:
آنها پروتکل PL2 را دنبال می کنند و بی اختیار تمام نمی شوند. به علاوه یک برقراری ارتباط آزاد ـ خطا نیز فرض شد. بدین معنا که هر پیغامی مقصود خودش را در یک زمانی دریافت خواهد کرد و این که هر پیغام دریافت شده صحیح است.

4-4- الگوریتم های هل دادن (فشار) مسیر (جریان کار)
الگوریتم‌ های فشار مسیر صراحتا WFG را حفظ می کنند. هر سایت به طور دوره‌ای بستگی های انتظار محلی را جمع آوری می کند و یک WFG محلی می سازد و برای چرخه‌هایی در آن جستجو می کند و چرخه‌هایی را که آن محل می کند آشکار می سازد. بخشهای دیگر WFG به بعضی سایتهای دیگر فرستاده می شود. آنها در وابستگی‌های انتظار دریافت شده در WFG محلی‌شان متحد هستند و برای چرخه‌هایی در آن جستجو می کنند. پس از آن سایت دوباره بخش‌هایی از WFG در سایت های دیگر را عبور می دهد.
جالب است ببینیم که خیلی از الگوریتم‌های فشار مسیر منتشر شده در بازگشت درست نبوده اند. اکثر آنها بن بستهای فانتوم را درحالیکه الگوریتم‌‌های دیگر حتی آشکار کردن یک بن بست وارد می کند آشکار می سازد.
اگر چه این الگوریتمها نادرست هستند الگوریتم مناسک ـ مانتز (13) و الگوریتم اوبرمارک مختصرا برای فهم مشکلات این گروه از الگوریتمها مطرح شده است.
الگوریتم مناسک ـ مانتز. الگوریتم مناسک مانتز اولین بار برای شکل مشخصی از ترانشکن منتظر برای نمودار مورد استفاده قرار گرفت. در الگوریتم‌ آنها تنها بخش‌ های TWFG جهانی کامل در سایت جهانی ترانکشن برای آشکار سازی بن بستها نگهداری شد مبدل بن بست شالوده مدل AND است، از این رو الگوریتم برای چرخه‌هایی در زیر مجموعه TWFG جستجو می کند.
یک ترانکشن می تواند یا بلوکه شود یا نشود. یک مجموعه منع شده T یک ترانشکن T مجموعه همه ترانکشن‌ها To منع نشده ای است که می تواند از T در TWFG از طریق یک مسیر مستقیم بدست آید.
الگوریتم اوبرمارسک ـ الگوریتمی که توسط اوبرمارسک درباره سیستم R تکمیل شد و استراتژی فشار مسیر را با فرستادن بخشی از یک چرخه ممکن یعنی یک مسیر به سایت دیگر تنها در مورد ترانکشن اول در مسیر یک تقدمی نسبت به آخری دارد.
این جریان شمار پیغام ها را بوسیله نیم تا نیم کاهش می دهد.
علی رغم این بهینه سازی الگوریتم سه بار عمده ای را هنگامیکه آن اجرا می شود. ارائه می کند. این جریان به صورت دوره ای انجام می شود. آنچنان که همه WFG باید برای چرخه 3 جستجو شود. به علاوه مسیرهایی که باید به سایتهای دیگر فرستاده شود باید مشخص شود. همچنین مشارکت مسیرهای بدست آمده از یک سایت اطلاعات خیلی دریافت شده از این سایت را واضح می کند. باید در WFG برای اطلاعات جدید مبادله شود.
در فصل [4] این طور مطرح شده است که الگوریتم از بن بست های فانتوم حمایت می‌کند، از آنجائی که بخشهایی از WFG بین سایتهای متعلق به اسنپ شات‌ها یعنی ممکن است ناپایدار باشد فرستاده می شود.
بدال الگوریتم: در یک تلاش برای بهینه سازی الگوریتمهای آشکار سازی بن بست توزیع شده در اصطلاحات آشکار سازی اگر بن بست ها با حداکثر کارآمدی، بدان یک الگوریتم 3 سطحی را پیشنهاد می کند. یک چرخه بن بست می تواند تپولوژی های مختلفی داشته باشد. بدال بن بست ها را به 4 نوع برطبق پتولوژی شان تقسیم بندی کرد. از کل، یک بن بست می تواند محلی باشد یا جهانی.
یک نوع محلی ساده ـ همچنین اکثر چرخه‌های بن بست تنها یک طول از 2 دارند و هرچه یک چرخه بن بست بلندتر باشد با فرکانس کمتری اتفاق می افتد. این حقیقت موجب یک عقیده‌ای از ساده کردن آشکار سا زی بن بست‌های جهانی توسط ساخت الگوریتم‌ های کار آمد تر در آشکار سازی بن بست‌های جهانی کوتاه ‌تر است. بر اساس این عقاید اجرا در الگوریتم بدال با استفاده از 3 سطح از آشکارسازی بن‌بست برای غلبه بر گروههای پیچیده مختلف بن بست‌ها بهینه می شود. فعالیت در هر سطح پیچیده تر است و نسبتا از نظر قیمت در سطح در حال پیشرفت.

5-4- الگوریتم هایی بر پایه تحقیق
الگوریتمهایی بر پایه تحقیق صراحتا WFG را حفظ نمی کند بلکه یک نوع خاص از پیغام، تطبیق را در مسئول لبه WFG می فرستد. 2 نوع الگوریتم برپایه تحقیق وجود دارد: جستجوی لبه و محاسبات پراکنده.

فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد

تعداد صفحات این مقاله    21صفحه

پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید

فیلم آموزشی طراحی فلنج برای چفت و بست کردن لوله های آب

اختصاصی از فی بوو فیلم آموزشی طراحی فلنج برای چفت و بست کردن لوله های آب دانلود با لینک مستقیم و پر سرعت .

تحلیل و آنالیز کامل طراحی فلنج برای چفت و بست کردن لوله های آب