فهرست مطالب
عنوان صفحه
فصل اول: مقدمه
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
آن. 45
آن. 45
آن. 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
فصل اول
مقدمه
1-1- مقدمه
اجرای همروند تراکنشها در پایگاه دادهها با مشکلات بسیاری مواجه است. مکانیزمهای کنترل همروندی، برای حفظ انزوا و عدم دخالت اجرا در میان تراکنشهای متعارض و حفظ سازگاری پایگاه دادهها استفاده میشوند (a-Pashazadeh, 2012)، (b-Pashazadeh, 2012) و (Shu, and Young, 2002). به عبارت دیگر الگوریتمهای کنترل همروندی، الگوریتمهایی هستند که باعث میشوند اجرای همروند چند تراکنش و اجرای متوالی آن معادل شود. مسئلهی كنترل همروندی در پایگاه دادهها امری ضروری و با اهمیت میباشد (Shu, and Young, 2002). در این زمینه مطالعات و تحقیقات فراوانی صورت گرفته است كه نتیجهی آن، به وجود آمدن الگوریتمهای متنوع كنترل همروندی میباشد. همچنین با توجه به گسترش روزافزون انواع پایگاه دادهها در سراسر جهان، نیاز به بررسی پروتکلهای کنترل همروندی پایگاه دادهها، بیشتر نمایان میشود.
مدلسازی رسمی[1] از الگوریتمهای کنترل همروندی در مطالعه ویژگیهای مختلف آن ها بسیار مفید است (a-Pashazadeh, 2012) و (b-Pashazadeh, 2012). بررسیها نشان میدهد که شبکههای پتری (PNs)[2] روش مناسبی برای مدلسازی رسمی مکانیزمهای کنترل همروندی میباشند. شبکههای پتری انواع مختلفی دارند که یکی از آن ها شبکه پتری رنگی (CPN)[3] است. شبکههای پتری رنگی یکی از بهترین ابزارها برای مدلسازی الگوریتمهای کنترل همروندی هستند (a-Pashazadeh, 2012) و (b-Pashazadeh, 2012). به همین دلیل در این پایاننامه نیز از این روش برای مدلسازیها استفاده خواهد شد.
یکی از اصلیترین مکانیزمهای کنترل همروندی تکنیک قفلگذاری دو مرحلهای مبنایی (2PL)[4] است. این تکنیک کنترل همروندی از طریق قفلگذاری روی دادهها انجام میشود. قفلگذاری روی دادهها به تدریج که نیاز به دستیابی به آن ها پیش میآید صورت میگیرد و قفلگشایی از آن ها پس از دریافت تمام قفلهای تراکنش رخ خواهد داد. در این تکنیک امکان رخ دادن بنبست وجود دارد، به همین دلیل دو مکانیزم پیشگیری از بنبست نیز مورد بررسی قرار خواهد گرفت.
مکانیزم منتظر گذاشتن-میراندن (WD)[5] یکی از الگوریتمهای پیشگیری از بنبست است که در آن حق تقدم زمانی تراكنشها براساس زمانمهر و لحظهی ورودشان به سیستم رعایت نمیشود. یعنی در مکانیزم WD هیچ قانونی وجود ندارد که تراکنشی که زودتر وارد سیستم شده است اولویت بیشتری برای زودتر دریافت کردن قفلهای مورد نیازش داشته باشد، به همین دلیل به آن الگوریتم نابازدارنده میگویند. در سمت مقابل، مکانیزم زخمی كردن-منتظر گذاشتن (WW)[6] وجود دارد که یکی از الگوریتمهای پیشگیری از بنبست است که در آن حق تقدم زمانی تراكنشها براساس زمانمهر و لحظه ورودشان به سیستم رعایت میشود. یعنی در مکانیزم WW تراکنشی که زودتر وارد سیستم شده است اولویت بیشتری برای زودتر دریافت کردن قفلهای مورد نیازش دارد، به همین دلیل به آن الگوریتم بازدارنده میگویند.
در این پایاننامه تلاش بر این است که با مدلسازی مکانیزمهای 2PL، WD و WW، امکان بررسی اجرای تراکنشها از دیدگاهها و جوانب مختلفی را فراهم کنیم. سپس به ارزیابی این الگوریتمها بپردازیم و آن ها را با بهره گرفتن از پارامترهای مختلفی که در جدول 1-1، اشاره شده است بررسی کنیم. در این جدول، در ستون اول پارامترهایی که قرار است ما در این پایاننامه بر اساس آن ها مدلها را ارزیابی کنیم مشاهده میشود. سپس در ستونهای بعدی نام الگوریتمهایی که قبلاً توسط این پارامترها مورد ارزیابی قرار گرفته بودهاند، نحوهی پیادهسازی یا مدلسازی آن ها و همچنین مراجعشان را مشاهده میکنید.
جدول1-1- پارامترهای مورد نظر برای ارزیابی مدلها در این پایاننامه
پارامتر |
الگوریتم(ها) |
پیادهسازی یا مدلسازی |
مرجع |
تعداد تراکنشهای وارد شونده به سیستم |
مقایسه یک الگوریتم امن و یک الگوریتم غیر امن برای پایگاه دادههای بلادرنگ |
پیادهسازی در مقیاس کوچک |
(Hedayati, Kamali, Shakerian and Rahmani, 2010) |
اندازه هر تراکنش (تعداد دستورات هر تراکنش) |
الگوریتم مرتبسازی زمانمهر پایهای |
مدلسازی توسط مدل مارکف |
(Singhal, 1991) و
(روحانی رانکوهی، 1386)
|
تعداد دادههای مشترک و غیر مشترک تراکنشها |
یک مکانیزم بر اساس قفل دو مرحلهای |
پیادهسازی در مقیاس کوچک |
(Al-Jumah, Hossam, and El-Sharkawi, 2000) |
تعداد دادههای مشترک در تراکنشهایی بدون داده غیر مشترک |
یک مکانیزم بر اساس قفل دو مرحلهای |
پیادهسازی در مقیاس کوچک |
(Al-Jumah, et al., 2000) |
در هنگام مدلسازی یک مطالعه موردی ساده به عنوان مثال برای درک بهتر ارائه گردیده است. مثال ذکر شده شامل سه تراکنش و دو منبع است.
مدلسازیها با بهره گرفتن از پتری رنگی و نرمافزار CPN Tools ارائه شدهاند. در نهایت به ارزیابی هر سه الگوریتم پرداخته شده است و الگوریتمها با معیارهای بیان شده در فوق مورد بررسی قرار داده شدهاند. آزمایشها چندین بار تکرار گردیده و از مقادیر میانگینگیری به عمل آمده است. نمودارهای لازم نیز جهت مقایسهی آسانتر ترسیم و بررسی گردیدهاند.
1-2- ساختار پایاننامه
این پایاننامه به فرم زیر سازماندهی شده است.
در فصل دوم پیشینهتحقیق و مطالب مرتبط آورده شده است. در این فصل یک مرور کلی بر کلیات مطلب، اهداف، پیشینهتحقیق و سایر کارهای انجام شده در این زمینه خواهیم داشت. در پیشینه تحقیق، میپردازیم به این که تا کنون چه الگوریتمهایی ارائه شده، ارزیابی از طریق چه روشهایی صورت گرفته است و مانند آن ها. همچنین تعدادی از پارامترها و معیارهای ارزیابی الگوریتمهای کنترل همروندی را بررسی خواهیم نمود. علاوه بر آن بعضی روشهای پیادهسازی و شبیهسازی موجود مانند پیادهسازی در مقیاس کوچک، شبیهسازی از طریق مدل مارکف، شبیهسازی از طریق شبکههای پتری و مانند آن ها را بررسی میکنیم و به مزایا و معایب آن ها اشارهای خواهیم داشت. همچنین روش تجزیه و تحلیل از طریق صف نیز بطور مختصر مورد بررسی قرار میگیرد.
در فصل سوم انواع الگوریتمهای کنترل همروندی پایهای موجود را بررسی خواهیم کرد. در این میان تعدادی از الگوریتمهای کنترل همروندی مانند پروتکل قفل 2PL که احتمال بنبست در آن وجود دارد و تکنیکهای WW و WD که تکنیکهای پیشگیری از بنبست هستند را مورد مطالعه قرار میدهیم. مزایا و معایب هر یک از این الگوریتمهای کنترل همروندی پایهای را نیز تا حدودی بررسی خواهیم نمود.
در فصل چهارم نیز به بررسی شبکههای پتری، مخصوصاً شبکههای پتری رنگی که یکی از ابزارهای بسیار مفید برای شبیهسازی الگوریتمهای کنترل همروندی هستند، پرداخته میشود.
در فصل پنجم نحوهی مدلسازی الگوریتمهای مورد نظر با بهره گرفتن از شبکههای پتری بیان شده است؛ که شامل تعریف مجموعههای رنگ، نشانهگذاریهای اولیه، متغیرهای موجود در مدل، شرح عملکرد توابع مدل و تعیین اولویت برای فایر[7] شدن گذار مورد نظر از بین گذارهای فعال میباشد.
در فصل ششم که همان بخش پایانی است مدلها بر اساس پارامترهای متفاوت بررسی و با هم مقایسه شدهاند. آزمایشهای مورد نیاز صورت گرفته و هرکدام چندین بار تکرار گردیدهاند. نتایج میانگینگیری شده و نمودارهای لازم جهت مقایسه ترسیم شدهاند. در نهایت نیز نتیجهگیری کلی از مباحث بیان شده مشاهده میشود و پیشنهاداتی برای کارهای آینده ارائه خواهد شد.
[1]- Formal
[2]- Petri Nets