مقدمه:

کنترل روال اجرای چند برنامه که به صورت همزمان در حال اجرا می باشند از مسائلی است که در بسیاری از شاخه های سیستم های کامپیوتری مطرح می شود و تا کنون راهکار های مختلفی جهت تامین صحت نتیجه نهایی حاصل از اجرای اینگونه برنامه ها ارائه شده است .هرچند که ماهیت مسئله کنترل همزما نی در تمام این نوع سیستم ها یکسان است ، منتها برای هر سیستم با توجه به شرایط و ویژیگی های ان راهکار خاصی مناسب ، وقابل ارائه می باشد . به عنوان مثال مسئله کنترل دسترسی همزمان تراکنش ها به یک منبع در دیتابیس در اصل یک نوع مسئله می باشند. منتها با توجه به محدودیتی که در تعداد دستگاه های فیزیکی سیستم عامل وجود دارد راهکار های مورد استفاده جهت حل این مسئله در سیستم عامل در دنیای دیتابیس کاربردی نخواهد داشت و بالعکس . فلذا حل مسئله همزمانی در اجرای تراکنش ها در دیتا بیس نیازمند توجه خاص و ارائه راهکار های مناسب ، و مخصوص محیط دیتا بیس می باشد .اساس الگوریتم ها و راهکار های ارائه شده جهت کنترل همزمانی در اجرای تراکنش ها به سه صورت مختلف است : serialization graph testing. Timestamping .lockingو الگوریتم های بیشماری که تاکنون ارائه شده اند همگی ( مگر در موارد خاص ) بر مبنای یکی و یا ترکیبی از این سه تکنیک می باشد . هر چند که اساس کارکرد الگوریتم ها یکسان می باشد با این وجود با توجه به تفاوت هایی که در نحوه تصمیم گیری در خصوص برخورد های پیش امده بین تراکنش ها وجود دارد لذا نسخه های مختلف هر کدام از الگوریتم ها به صورت مجزا می بایستی مورد بررسی قرار گیرد . در ادامه ابتدا به صورت کلی هر کدام از تکنیک های پایه را به همراه نسخه های مختلف هر تکنیک توضیح داده و برای هر کدام از تکنیک ها یک یا دو الگوریتم نمونه ارائه می شود . بدیهی است که روش های موجود ابتدا در محیط متمرکز ارائه شده و مورد استفاده قرار گرفته و سپس با اعمال تغییراتی در ساختار و رفتار الگوریتم ، در محیط توزیع شده نیز از الگوریتم استفاده شده است .

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

فهرست مطالب

2: مقدمه                                                                                                                     3

3: مدل محیط توزیع شده وپردازش در ان                                                                        5

4: serializability           ا                                                                                          13

5: locking              ا                                                                                                  16

کنترل همزمانی در پایگاه داده توزیع شده1

1-5: روشی جهت جلوگیری از بن بست در محیط توزیع شده                                          19

2-5: basict 2pl                         ا                                                                            23

3-5: strict 2pl                   ا                                                                                   25

4-5: distributed basic 2pl (strict 2pl)       ا                                                   26

5-5: primary copy 2pl                                     ا                                               27

6-5: voting 2pl                     ا                                                                            28

7-5: centralized 2pl           ا                                                                              29

8-5: conservative 2pl        ا                                                                              29

9-5: dummy lock             ا                                                                                   32

10-5: promoting priority concurrency control            ا                             42

11-5: PRABHA(concurrency control algorithm)         ا                              54

6: timestamp ordering(to)                  ا                                                              71

1-6: basict to                       ا                                                                                  73

2-6: strict to        on to                         ا                                                                   80

4-6: Thomas write rule         ا                                                                            83

5-6: conservative to               ا                                                                             83

6-6: a timestamp based concurrency control algorithm for ddbms    ا  87

کنترل همزمانی در پایگاه داده توزیع شده2

7: serialization graph testing                                                                   ا          96

1-7: badic sgt    ا                                                                                                    97

2-7: conservative sgt      ا                                                                                     100

3-7: distributed SGT scheduler ا                                                                    103

کنترل همزمانی در پایگاه داده توزیع شده3

8: optimistic scheduler یا certifiers         ا                                                    105

1-8: 2pl certification     ا                                                                                112

2-8: sgt certification   ا                                                                                 116

3-8: to certification    ا                                                                                 117

4-8: distributed certifiers ا                                                                        118

5-8: distributed time optimistic concurrency control    ا                 125

کنترل همزمانی در پایگاه داده توزیع شده4

9: integrated scheduler           ا                                             139

1-9: pure 2pl method           ا                                              144

2-9: pure to method           ا                                                 149

3-9: mixed 2pl and to method    ا                                       157

10: نتیجه گیری انی                                                                        162

11: مطالعات اتی                                                                            165

12: مراجع                                                                                     166

13: چکیده لاتین                                                                           170

یک روش جهت تضمین تولید اجرا های seralizable استفاده از فقل است بدین صورت که وقتی تراکنش به یک شی دسترسی پیدا میکند . قفلی انحصاری روی ان قرار داده و از دسترسی سایر تراکنش ها جلوگیری می کند . در واقع با استفاده   از تکنیک های قفل گذاری دستورات برخوردی به صورت صریح شناسایی شده و ترتیب خاصی بین انها اعمال می شود .اگر به صورت کلی به زمانبندی هایی که از locking استفاده می کنند نگاه شود در واقع این زمانبند ها بر اساس تعریفی که از دستورات برخوردی وجود دارد انواع مختلفی قفل برای خود تعریف می کنند و به نوعی تعریف دستورات برخوردی وجود را به صورت دیگری بر روی قفل های خود تعریف می کنند . و به مفهوم قفل های برخوردی می رسند .به عنوان مثال وقتی گفته می شودتراکنش t1 قفلی انحصاری روی شی x گرفته است و لذا t2 نمی تواند قفلی از نوع اشتراکی روی x داشته باشد به واقع نوعی از برخورد میان قفل ها تعریف می شود، به این صورت که قفل انحصاری با قفل اشتراکی برخورد دارد . این زمانبند ها بر اساس مفهومی که برای قفل ها ی برخوردی تعریف می کنند در خصوص تخصیص یا عدم تخصیص قفل تصمیم گیری می کنند . هر چند که این نوع زمانبند ها مسئله کنترل اجرای همزمان را حل میکنند و همواره اجرا های serializable  تولید می کنند منتها در مقابل این لطف دو مسئله خاص ایجاد می کنند که میبایستی جهت استفاده از انها حل شود : ( شاید به نوعی بتوان گفت جهت حل مسئله، مسئله دیگری را مطرح میکنند که رد هر حال ساده تر از مسئله اول(کنترل همزمانی) می باشد)

1:starvation:

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

Deadlock:2

بن بست یک مسئله عمومی است که بسیاری دیگر از سیستم های اطلاعاتی همرخ میدهد ودر مورد تراکنش ها به این صورت است که هر تراکنشدر انتظار آزاد کردن قفلی است که در اختیار دیگری است، البته نوع دیگری از   بن بست هم در اثرارتقاء قفل اتفاق می افتد که خاص دنیای پایگاه داده ها می باشد ودر آن دو تراکنش درخواست ارتقاءقفل مربوط به شی را که در اختیار دارند به صورت همزمان می دهند. در خصوص مسائل مربوط به جلو گیری از بن بست،رفع بن بست، و تشخیص بن بست، تا کنون تحقیقات بسیاری صورت گرفته است و البته در خصوص این مسئله در دنیای DDBMS نیز تحقیقات زیادی صورت گرفته {5} {6} در کلان راهکار های موجود جهت جلوگیری از بن بست در دنیای پایگاه داده ها نیز همچون سایر روش ها از بروز یکی از دو شرط hold & wait یا circular wait جلوگیری می کنند. البته با توجه به اینکه جهت جلوگیری از شرط hold & wait ضروری است read set و write set تراکنش موقع شروع به اجرا مشخص شود(که در دنیای واقع مگر در موارد خاص امکان پذیر نیست)،لذا غالبا از بروز شرط دوم جلو گیری می شود . بدیهی است هر الگوریتم کنترل همزمانی که از قفل استفاده می کند میبایستی تدبیر خاصی جهت موتجه شدت با بن بست داشته باشد و لذا مسئله بن بست را به صورت مجزا بررسی خواهیم کرد ضمن اینکه در حال حاضر استاندارد خاصی نیز در محیط پایگاه داده جهت مواجه شدن با بن بست وجود ندارد . در اینجا صرفا به روشی ساده که جهت جلوگیری از بن بست توسط محققین داانشگاه ازاد اسلامی واحد قزوین {7} ارائه شده است اشاره می شود . این روش از بروز شرط دوم در محیط پایگاه داده جلوگیری می کند .


 مقطع کارشناسی ارشد

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


فایل pdf غیر قابل ویرایش

قیمت25000تومان

قیمت45000تومان