ارزیابی بعضی الگوریتم‌های کنترل همروندی در سیستم مدیریت پایگاه داده‌ها، از طریق مدل‌سازی با پتری رنگی

استاد راهنما:

دکتر فاطمه سعادت‌جو

استاد مشاور:

مهندس محمد علی سعادت‌جو

برای رعایت حریم خصوصی نام نگارنده درج نمی گردد

تکه هایی از متن به عنوان نمونه :

فهرست مطالب:

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

1-1- مقدمه………………………. 2

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

فصل دوم: پیشینه‌ی پژوهش

مقدمه………………………. 7
دانلود متن کامل در سایت sabzfile.com
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………………………..

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………………………..

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

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

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

مقدمه………………………. 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………………

5-1-1- مدل 2PL………………………..

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

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

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

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

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

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

5-3-1- نشانه‌گذاری اولیه در مدل 2PL……………………….. جستجو در سایت :   

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

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

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

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

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

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

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

5-5-2- تبیین توابع مدل 2PL………………………..

5-5-3- تبیین توابع مدل‌های WW و WD………………………..

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

5-7- چگونگی‌ی مدل‌سازی‌ها……………………… 73

5-7-1- چگونگی مدل‌سازی مدل 2PL………………………..

5-7-2- چگونگی مدل‌سازی مدل‌های WW و WD………………………..

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

مقدمه………………………. 79

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

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

6-2-1- مطالعه مدل 2PL………………………..

6-2-2- مطالعه مدل WW………………………..

6-2-3- مطالعه مدل WD………………………..

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

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

6-3-1- مطالعه مدل 2PL………………………..

6-3-2- مطالعه مدل WW…………………………

6-3-3- مطالعه مدل WD………………………..

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

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

6-4-1- مطالعه مدل 2PL………………………..

6-4-2- مطالعه مدل WW…………………………

6-4-3- مطالعه مدل WD………………………..

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

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

6-5-1- مطالعه مدل 2PL………………………..

6-5-2- مطالعه مدل WW…………………………

6-5-3- مطالعه مدل WD………………………

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

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

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

مراجع……………………….. 102

چکیده:

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

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

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

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

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، تصریح شده می باشد مطالعه کنیم. در این جدول، در ستون اول پارامترهایی که قرار می باشد ما در این پایان‌نامه بر اساس آن‌ها مدل‌ها را ارزیابی کنیم نظاره می گردد. سپس در ستون‌های بعدی نام الگوریتم‌هایی که قبلاً توسط این پارامترها مورد ارزیابی قرار گرفته بوده‌اند، چگونگی‌ی پیاده‌سازی یا مدل‌سازی آن‌ها و همچنین مراجعشان را نظاره می‌کنید.

در هنگام مدل‌سازی یک مطالعه موردی ساده به عنوان مثال برای درک بهتر ارائه گردیده می باشد. مثال ذکر گردیده شامل سه تراکنش و دو منبع می باشد.

مدل‌سازی‌ها با بهره گیری از پتری رنگی و نرم‌افزار CPN Tools ارائه شده‌اند. در نهایت به ارزیابی هر سه الگوریتم پرداخته شده می باشد و الگوریتم‌ها با معیارهای اظهار شده در فوق مورد مطالعه قرار داده شده‌اند. آزمایش‌ها چندین بار تکرار گردیده و از مقادیر میانگین‌گیری به اقدام آمده می باشد. نمودارهای لازم نیز جهت مقایسه‌ی آسان‌تر ترسیم و مطالعه گردیده‌اند.

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

این پایان‌نامه به فرم زیر سازماندهی شده می باشد.

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

در فصل سوم انواع الگوریتم‌های کنترل همروندی پایه‌ای موجود را مطالعه خواهیم نمود. در این بین تعدادی از الگوریتم‌های کنترل همروندی مانند پروتکل قفل 2PL که احتمال بن‌بست در آن هست و تکنیک‌های WW و WD که تکنیک‌های پیش‌گیری از بن‌بست هستند را مورد مطالعه قرار می‌دهیم. مزایا و معایب هر یک از این الگوریتم‌های کنترل همروندی پایه‌ای را نیز تا حدودی مطالعه خواهیم نمود.

در فصل چهارم نیز به مطالعه شبکه‌های پتری، مخصوصاً شبکه‌های پتری رنگی که یکی از ابزارهای بسیار مفید برای شبیه‌سازی الگوریتم‌های کنترل همروندی هستند، پرداخته می گردد.

در فصل پنجم چگونگی‌ی مدل‌سازی الگوریتم‌های مورد نظر با بهره گیری از شبکه‎های پتری اظهار شده می باشد؛ که شامل تعریف مجموعه‌های رنگ، نشانه‌گذاری‌های اولیه، متغیرهای موجود در مدل، تبیین عملکرد توابع مدل و تعیین اولویت برای فایر شدن گذار مورد نظر از بین گذارهای فعال می‌باشد.

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

[1]– Formal

[2]– Petri Nets

[3]– Colored Petri Net

[4]– Two-Phase Locking

[5]– Wait-Die

[6]– Wound-Wait

***ممکن می باشد هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود اما در فایل دانلودی همه چیز مرتب و کامل و با فرمت ورد موجود می باشد***

متن کامل را می توانید دانلود نمائید

این مطلب رو هم توصیه می کنم بخونین:   دانلود پایان نامه کارشناسی ارشد رشته کامپیوتر با موضوع بررسی حملات SQL INJECTION

زیرا فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به گونه نمونه)

اما در فایل دانلودی متن کامل پایان نامه

 با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود می باشد

تعداد صفحه : 129

قیمت : 14700 تومان

 

***

—-

پشتیبانی سایت :       

****         serderehi@gmail.com