چكیده:

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

در این پایان‌نامه ابتدا الگوریتم‌های کنترل همروندی قفل‌گذاری دو مرحله‌ای مبنایی و همچنین تکنیک‌های زخمی كردن-منتظر گذاشتن و منتظر گذاشتن-میراندن که جزء تکنیک‌های پیش‌گیری از بن‌بست هستند، مدل‌سازی شده‌اند. از آنجا که شبکه پتری رنگی قابلیت‌های مدل‌سازی بالایی دارد و یکی از بهترین روش‌ها برای تحلیل مکانیزم‌های کنترل همروندی است؛ مدل‌سازی‌ها با استفاده از پتری رنگی و نرم‌افزار CPN Tools ارائه شده‌اند. یک مطالعه موردی ساده به عنوان مثال برای درک بهتر ارائه گردیده که مثال ذکر شده شامل سه تراکنش و دو منبع است. سپس الگوریتم‌های ذکر شده ارزیابی گردیده‌اند. ارزیابی بر اساس پارامترها و معیارهایی مثل تعداد تراکنش‌های وارد شونده به سیستم، تعداد دستورات هر تراکنش، تعداد داده‌های مشترک و غیر مشترک بین تراکنش‌ها و تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک، صورت گرفته است.

آزمایش‌ها چندین بار تکرار و نتایج میانگین‌گیری شدند. با مقایسه و انجام بررسی‌ها، این نتیجه به دست آمد که در حالت کلی الگوریتم زخمی كردن-منتظر گذاشتن نسبت به دو الگوریتم دیگر زمان اجرای بهتری دارد. الگوریتم منتظر گذاشتن-میراندن از نظر زمان اجرا با اختلاف زیادی در سطح بدتری نسبت به دو الگوریتم دیگر قرار دارد و الگوریتم قفل‌گذاری دو مرحله‌ای مبنایی به دلیل امکان رخ دادن بن‌بست، مشکلات فراوانی دارد.

واژه‌های كلیدی: کنترل همروندی، شبکه پتری رنگی، ارزیابی، قفل‌گذاری دو مرحله‌ای مبنایی، زخمی كردن-منتظر گذاشتن، منتظر گذاشتن-میراندن، بن‌بست، پیش‌گیری از بن‌بست

فهرست مطالب

عنوان                                                                                                                                            صفحه

فصل اول: مقدمه

1-1- مقدمه 2

1-2- ساختار پایان‌نامه 4

فصل دوم: پیشینه‌ی تحقیق

مقدمه 7

2-1- اهمیت الگوریتم‌های کنترل همروندی پایگاه داده‌ها 7

2-2- برخی از انواع پایگاه داده‌ها 8

2-3- انواع روش‌های پیاده‌سازی و مدل‌سازی الگوریتم‌های کنترل همروندی 9

2-3-1- پیاده‌سازی در مقیاس کوچک 9

2-3-2- مدل‌سازی و شبیه‌سازی توسط مدل مارکف 11

2-3-3- مدل‌سازی و شبیه‌سازی توسط شبکه‌های پتری 12

2-4- پارامترهای ارزیابی 14

2-4-1- پارامترهای منابع سیستم 14

2-4-2- پارامترهای حجم کاری 15

2-5- پارامترها و آزمایش‌های انجام شده 16

2-6- برخی از مزایا و معایب روش‌های مدل‌سازی و شبیه‌سازی 18

2-7- لزوم انجام تحقیق 20

فصل سوم: تکنیک‌های کنترل همروندی

مقدمه 22

3-1- تکنیک‌های کنترل همروندی و انواع آن‌ها 22

3-2- تکنیک‌های قفل‌گذاری و انواع آن‌ها 23

3-2-1- تعریف قفل 24

3-2-2- اندازه‌های واحد قفل‌شدنی 24

3-2-3- ساختار قفل 25

3-2-4- مثالی برای لزوم قفل‌گذاری 26

3-2-5- مدیر قفل و مراحل انجام شده برای قفل‌گذاری 27

3-2-6- نحوه در اختیار قرار دادن قفل توسط مدیر قفل 28

3-2-7- قفل چند اسلوبی 28

3-2-7-1- ماتریس همایندی یا سازگاری قفل‌های چند اسلوبی 28

3-2-7-2- پروتکل قفل چند اسلوبی برای یک تراکنش 29

3-2-7-3- تغییر قفل 30

3-2-7-4- قفل چند اسلوبی و توالی‌پذیری 30

3-2-7-5- خصوصیات قفل چند اسلوبی 30

3-2-8- تکنیک قفل‌گذاری دو مرحله‌ای مبنایی 30

3-2-8-1- مشکلات تداخل کنترل نشده 31

3-2-8-2- خصوصیات و مشکلات 2PL مبنایی 32

3-2-8-3- تغییر قفل در پروتکل 2PL 33

3-2-8-4- تأثیرعملیات درج در کنترل همروندی 33

3-2-8-5- تأثیرعملیات حذف در کنترل همروندی 33

3-3- بن‌بست 34

3-3-1- راه حل‌های مشكل بن‌بست 35

3-3-2- تکنیک‌های زمان‌مهر 36

3-3-2-1- الگوریتم WD 37

3-3-2-2- الگوریتم WW 37

3-3-2-3- خصوصیات الگوریتم WD و WW 37

فصل چهارم: شبکه‌های پتری

مقدمه 39

4-1- مختصری در مورد شبکه‌های پتری 39

4-2- تفاوت UML و پتری 39

4-3- تاریخچه شبکه‌های پتری 40

4-4- ویژگی‌های شبکه‌های پتری 40

4-5- اجزای شبکه‌ی پتری 40

4-5-1- تعریف اجزای شبکه‌ی پتری 41

4-5-2- وظایف اجزای شبکه‌ی پتری 41

4-6- تعریف چهارگانه شبکه‌های پتری 42

4-7- گراف شبکه پتری 42

4-8- چند مثال از گراف شبکه پتری 43

4-9- رفتار شبکه‌های پتری 43

4-10- گذار توانا 44

4-11- مثالی از اجرای یک شبکه پتری 44

4-12- قوانین مربوط به فایر شدن گذار، در شبکه پتری 45

4-13- شبکه‌های پتری به بن‌بست رسیده، زنده و غیر زنده 46

4-14- انواع شبکه‌های پتری و نحوه‌ی نشانه‌گذاری آن‌ها 47

4-15- فلوچارت‌ها و شبکه‌های پتری 47

4-16- انواع پتری 48

4-16-1- شبکه پتری رنگی 48

4-16-2- شبکه پتری زمانی 49

4-16-3- شبکه پتری سلسله مراتبی 50

فصل پنجم: نحوه‌ی مدل‌سازی مکانیزم‌های 2PL، WW و WD با پتری رنگی

مقدمه 52

5-1- مختصری در مورد مدل‌سازی مکانیزم‌های 2PL، WW و WD 52

5-1-1- مدل 2PL 52

5-1-2- مدل‌های WW و WD 53

5-2- مجموعه‌های رنگ 53

5-2-1- مجموعه‌های رنگ در مدل 2PL 53

5-2-2- مجموعه‌های رنگ در مدل‌های WW و WD 54

5-2-3- توضیحات مجموعه‌های رنگ 55

5-3- نشانه‌گذاری اولیه 58

5-3-1- نشانه‌گذاری اولیه در مدل 2PL 58

5-3-2- نشانه‌گذاری اولیه در مدل‌های WW و WD 59

5-3-3- توضیحات نشانه‌گذاری اولیه 59

5-4- متغیرها 61

5-4-1- متغیرهای مدل 2PL 61

5-4-2- متغیرهای مدل‌های WW و WD 62

5-5- شرح توابع مدل و عملکردهای آن‌ها 62

5-5-1- شرح توابع مشترک بین مدل‌های 2PL، WW و WD 63

5-5-2- شرح توابع مدل 2PL 63

5-5-3- شرح توابع مدل‌های WW و WD 76

5-6- اولویت‌های معین شده برای تعیین فایر شدن گذار مورد نظر از بین گذارهای فعال 72

5-7- نحوه‌ی مدل‌سازی‌ها 73

5-7-1- نحوه مدل‌سازی مدل 2PL 73

5-7-2- نحوه مدل‌سازی مدل‌های WW و WD 75

فصل ششم: ارزیابی مدل‌های 2PL، WW و WD

مقدمه 79

6-1- مختصری در مورد اهمیت ارزیابی پایگاه داده‎ها 79

6-2- پارامتر تعداد تراکنش‌های وارد شونده به سیستم 80

6-2-1- بررسی مدل 2PL 80

6-2-2- بررسی مدل WW 80

6-2-3- بررسی مدل WD 81

6-2-4- مقایسه‌ی مدل‌های 2PL، WW و WD براساس پارامتر تعداد تراکنش‌ها 82

6-3- پارامتر تعداد دستورات هر تراکنش 83

6-3-1- بررسی مدل 2PL 83

6-3-2- بررسی مدل WW 84

6-3-3- بررسی مدل WD 85

6-3-4- مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد دستورات تراکنش‌ها 86

6-4- پارامتر تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها 88

6-4-1- بررسی مدل 2PL 88

6-4-2- بررسی مدل WW 89

6-4-3- بررسی مدل WD 90

6-4-4- مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها 91

6-5- پارامتر تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک 92

6-5-1- بررسی مدل 2PL 92

6-5-2- بررسی مدل WW 93

6-5-3- بررسی مدل WD 94

6-5-4- مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک 96

6-6- نتیجه‌گیری 97

6-7- پیشنهادات 100

مراجع 102

فهرست جدول‌ها

عنوان جدول                                                                                                                                 صفحه

جدول1-1- پارامترهای مورد نظر برای ارزیابی مدل‌ها در این پایان‌نامه 4

جدول2-1- آزمایش‌های مورد نظر برای ارزیابی مدل‌ها در این پایان‌نامه 18

جدول 3-1- مزایا و معایب اندازه‌ی واحد قفل‌شدنی 25

جدول 3-2- نمایش لزوم قفل‌گذاری 26

جدول 3-3- نمایش ناحیه کاری 27

جدول 3-4- ماتریس همایندی 29

جدول 3-5- سازگاری قفل‌های چند اسلوبی 29

جدول 5-1- توضیحات مربوط به مجموعه‌های رنگی 55

جدول 5-2- توضیحات مربوط به نشانه‌گذاری‌های اولیه 60

جدول 5-3- پارامترهای ورودی تابع checklock برای مدل 2PL 64

جدول 5-4- پارامترهای خروجی تابع checklock برای مدل 2PL 65

جدول 5-5- پارامترهای ورودی تابع checklock برای مدل‌های WW و WD 68

جدول 5-6- پارامترهای خروجی تابع checklock برای مدل‌های WW و WD 69

جدول6-1- تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل 2PL 80

جدول 6-2- تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل WW 81

جدول 6-3- تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل WD 82

جدول 6-4- تعداد گام‌های اجرای تراکنش‌های کوچک و بزرگ در مدل 2PL 84

جدول 6-5- تعداد گام‌های اجرای تراکنش‌های کوچک و بزرگ در مدل WW 85

جدول 6-6- تعداد گام‌های اجرای تراکنش‌های کوچک و بزرگ در مدل WD 86

جدول 6-7- تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل 2PL 88

جدول 6-8- تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل WW 89

جدول 6-9- تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل WD 90

جدول 6-10- تعداد گام‌های اجرای تراکنش‌هایی بدون داده غیر مشترک، با تعداد کم و زیاد داده‌های مشترک در مدل 2PL 92

جدول 6-11- تعداد گام‌های اجرای تراکنش‌هایی بدون داده غیر مشترک، با تعداد کم و زیاد داده‌های مشترک در مدل WW 93

جدول 6-12- تعداد گام‌های اجرای تراکنش‌هایی بدون داده غیر مشترک، با تعداد کم و زیاد داده‌های مشترک در مدل WD 95

فهرست شکل‌ها

عنوان شکل                                                                                                                                  صفحه

شکل 3-1- عملیات مدیر قفل و مدیر تراکنش 27

شکل 3-2- پروتکل 2PL و لحظه قفل 31

شکل 3-3- نمونه‌ای از نحوه رخ دادن بن‌بست 34

شکل 3-4- مثال برای بن‌بست 35

شکل 4-1- اجزای شبکه‌ی پتری 40

شکل 4-2- عملکرد اجزای شبکه پتری 41

شکل 4-3- گراف شبکه پتری 42

شکل 4-4- مثال سیستم عابر بانک با گراف شبکه پتری 43

شکل 4-5- مثال تابع y=f(x) با گراف شبکه پتری 43

شکل 4-6- مثالی از نشانه‌گذاری یک مکان 43

شکل 4-7- مثالی برای یک گذار توانا و یک گذار غیر توانا 44

شکل 4-8- مثالی از اجرای یک شبکه پتری و نشانه‌گذاری اولیه آن 44

شکل 4-9- مثالی از اجرای یک شبکه پتری و M0 آن 45

شکل 4-10- مثالی از اجرای یک شبکه پتری و M1 آن 45

شکل 4-11- مثالی از اجرای یک شبکه پتری و M2 آن 45

شکل 4-12- مثالی از گراف شبکه پتری، قبل و بعد از فایر شدن 46

شکل 4-13- مثالی از گراف شبکه پتری، قبل و بعد از فایر شدن 46

شکل 4-14- یک شبکه پتری که دچار بن‌بست شده 46

شکل 4-15- انواع شبکه‌های پتری و نحوه‌ی نشانه‌گذاری آن‌ها 47

شکل 4-16- مدل‌سازی گره‌های تصمیم‌گیریِ فلوچارت با شبکه پتری 47

شکل 4-17- مدل‌سازی فلوچارت با شبکه پتری 48

شکل 4-18- شبکه پتری سلسله مراتبی 50

شکل 4-19- مدل‌سازی مسئله ممانعت دو جانبه با شبکه پتری 50

شکل 5-1- ماژول سطح بالا از مدل 2PL به صورت سلسله مراتبی، برای سه تراکنش 73

شکل 5-2- ماژول سطح بالا از مدل 2PL به صورت سلسله مراتبی، برای دو تراکنش 74

شکل 5-3- ماژول مربوط به تراکنش T1 از مدل 2PL به صورت سلسله مراتبی 74

شکل 5-4- ماژول سطح بالا از مدل‌های WW و WD به صورت سلسله مراتبی، برای سه تراکنش 75

شکل 5-5- ماژول مربوط به تراکنش T1 از مدل‌های WW و WD به صورت سلسله مراتبی، برای سه تراکنش 76

شکل 5-6- ماژول سطح بالا از مدل‌های WW و WD به صورت سلسله مراتبی، برای دو تراکنش 77

شکل 6-1- مقایسه تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل‌های 2PL، WW و WD 82

شکل 6-2- مقایسه تعداد گام‌های اجرای تراکنش‌های کوچک در مدل‌های 2PL، WW و WD 87

شکل 6-3- مقایسه تعداد گام‌های اجرای تراکنش‌های بزرگ در مدل‌های 2PL، WW و WD 87

شکل 6-4- مقایسه تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل‌های 2PL، WW و WD 91

شکل 6-5- مقایسه تعداد گام‌های تراکنش‌ها با تعداد کم و زیاد داده‌های مشترک (بدون داده غیر مشترک) در مدل‌های 2PL، WW و WD 96