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

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

عنوان : ارزیابی برخی الگوریتم‌های کنترل همروندی در سیستم مدیریت پایگاه داده‌ها، از طریق مدل‌سازی با پتری رنگیتعداد صفحه : 123ساختار پروژه به فرم زیر سازماندهی شده است.درفصل دوم پیشینه‌ی تحقیق و مطالب مرتبط آورده شده است. در این فصل یک مرورکلی بر کلیات مطلب، اهداف، پیشینه‌ی تحقیق و سایر کارهای انجام شده در اینزمینه خواهیم داشت. در پیشینه تحقیق، می‌پردازیم به این که تا کنون چهالگوریتم‌هایی ارائه شده، ارزیابی از طریق چه روش‌هایی صورت گرفته است ومانند آن‌ها. همچنین تعدادی از پارامترها و معیارهای ارزیابی الگوریتم‌هایکنترل همروندی را بررسی خواهیم نمود. علاوه بر آن بعضی روش‌های پیاده‌سازی وشبیه‌سازی‌ موجود مانند پیاده‌سازی در مقیاس کوچک، شبیه‌سازی از طریق مدلمارکف، شبیه‌سازی از طریق شبکه‌های پتری و مانند آن‌ها را بررسی می‌کنیم وبه مزایا و معایب آن‌ها اشاره‌ای خواهیم داشت. همچنین روش تجزیه و تحلیل ازطریق صف نیز بطور مختصر مورد بررسی قرار می‌گیرد.در فصل سوم انواعالگوریتم‌های کنترل همروندی پایه‌ای موجود را بررسی خواهیم کرد. در اینمیان تعدادی از الگوریتم‌های کنترل همروندی مانند پروتکل قفل 2PL که احتمالبن‌بست در آن وجود دارد و تکنیک‌های WW و WD که تکنیک‌های پیش‌گیری ازبن‌بست هستند را مورد مطالعه قرار می‌دهیم. مزایا و معایب هر یک از اینالگوریتم‌های کنترل همروندی پایه‌ای را نیز تا حدودی بررسی خواهیم نمود.درفصل چهارم نیز به بررسی شبکه‌های پتری، مخصوصاً شبکه‌های پتری رنگی که یکیاز ابزارهای بسیار مفید برای شبیه‌سازی الگوریتم‌های کنترل همروندی هستند،پرداخته می‌شود.در فصل پنجم نحوه‌ی مدل‌سازی الگوریتم‌های مورد نظربا استفاده از شبکه‎های پتری بیان شده است؛ که شامل تعریف مجموعه‌های رنگ،نشانه‌گذاری‌های اولیه، متغیرهای موجود در مدل، شرح عملکرد توابع مدل وتعیین اولویت برای فایر شدن گذار مورد نظر از بین گذارهای فعال می‌باشد.درفصل ششم که همان بخش پایانی است مدل‌ها بر اساس پارامترهای متفاوت بررسی وبا هم مقایسه شده‌اند. آزمایش‌های مورد نیاز صورت گرفته و هرکدام چندینبار تکرار گردیده‌اند. نتایج میانگین‌گیری شده و نمودارهای لازم جهت مقایسهترسیم شده‌اند. در نهایت نیز نتیجه‌گیری کلی از مباحث بیان شده مشاهدهمی‌شود و پیشنهاداتی برای کارهای آینده ارائه خواهد شد.فهرست مطالبفصل اول: مقدمه1-1- مقدمه1-2- ساختار پروژهفصل دوم: پیشینه‌ی تحقیقمقدمه.2-1- اهمیت الگوریتم‌های کنترل همروندی پایگاه داده‌ها2-2- برخی از انواع پایگاه داده‌ها2-3- انواع روش‌های پیاده‌سازی و مدل‌سازی الگوریتم‌های کنترل همروندی2-3-1- پیاده‌سازی در مقیاس کوچک2-3-2- مدل‌سازی و شبیه‌سازی توسط مدل مارکف2-3-3- مدل‌سازی و شبیه‌سازی توسط شبکه‌های پتری2-4- پارامترهای ارزیابی2-4-1- پارامترهای منابع سیستم2-4-2- پارامترهای حجم کاری2-5- پارامترها و آزمایش‌های انجام شده2-6- برخی از مزایا و معایب روش‌های مدل‌سازی و شبیه‌سازی2-7- لزوم انجام تحقیقفصل سوم: تکنیک‌های کنترل همروندیمقدمه3-1- تکنیک‌های کنترل همروندی و انواع آن‌ها3-2- تکنیک‌های قفل‌گذاری و انواع آن‌ها3-2-1- تعریف قفل3-2-2- اندازه‌های واحد قفل‌شدنی3-2-3- ساختار قفل3-2-4- مثالی برای لزوم قفل‌گذاری3-2-5- مدیر قفل و مراحل انجام شده برای قفل‌گذاری3-2-6- نحوه در اختیار قرار دادن قفل توسط مدیر قفل3-2-7- قفل چند اسلوبی3-2-7-1- ماتریس همایندی یا سازگاری قفل‌های چند اسلوبی3-2-7-2- پروتکل قفل چند اسلوبی برای یک تراکنش3-2-7-3- تغییر قفل3-2-7-4- قفل چند اسلوبی و توالی‌پذیری3-2-7-5- خصوصیات قفل چند اسلوبی3-2-8- تکنیک قفل‌گذاری دو مرحله‌ای مبنایی3-2-8-1- مشکلات تداخل کنترل نشده3-2-8-2- خصوصیات و مشکلات 2PL مبنایی3-2-8-3- تغییر قفل در پروتکل 2PL3-2-8-4- تأثیرعملیات درج در کنترل همروندی3-2-8-5- تأثیرعملیات حذف در کنترل همروندی3-3- بن‌بست3-3-1- راه حل‌های مشکل بن‌بست3-3-2- تکنیک‌های زمان‌مهر3-3-2-1- الگوریتم WD3-3-2-2- الگوریتم WW3-3-2-3- خصوصیات الگوریتم WD و WWفصل چهارم: شبکه‌های پتریمقدمه.4-1- مختصری در مورد شبکه‌های پتری4-2- تفاوت UML و پتری4-3- تاریخچه شبکه‌های پتری4-4- ویژگی‌های شبکه‌های پتری4-5- اجزای شبکه‌ی پتری4-5-1- تعریف اجزای شبکه‌ی پتری4-5-2- وظایف اجزای شبکه‌ی پتری4-6- تعریف چهارگانه شبکه‌های پتری4-7- گراف شبکه پتری4-8- چند مثال از گراف شبکه پتری4-9- رفتار شبکه‌های پتری4-10- گذار توانا 444-11- مثالی از اجرای یک شبکه پتری4-12- قوانین مربوط به فایر شدن گذار، در شبکه پتری4-13- شبکه‌های پتری به بن‌بست رسیده، زنده و غیر زنده4-14- انواع شبکه‌های پتری و نحوه‌ی نشانه‌گذاری آن‌ها4-15- فلوچارت‌ها و شبکه‌های پتری4-16- انواع پتری4-16-1- شبکه پتری رنگی4-16-2- شبکه پتری زمانی4-16-3- شبکه پتری سلسله مراتبیفصل پنجم: نحوه‌ی مدل‌سازی مکانیزم‌های 2PL، WW و WD با پتری رنگیمقدمه5-1- مختصری در مورد مدل‌سازی مکانیزم‌های 2PL، WW و WD5-1-1- مدل 2PL5-1-2- مدل‌های WW و WD5-2- مجموعه‌های رنگی5-2-1- مجموعه‌های رنگ در مدل 2PL5-2-2- مجموعه‌های رنگ در مدل‌های WW و WD5-2-3- توضیحات مجموعه‌های رنگ5-3- نشانه‌گذاری اولیه5-3-1- نشانه‌گذاری اولیه در مدل 2PL5-3-2- نشانه‌گذاری اولیه در مدل‌های WW و WD5-3-3- توضیحات نشانه‌گذاری اولیه5-4- متغیرها5-4-1- متغیرهای مدل 2PL5-4-2- متغیرهای مدل‌های WW و WD5-5- شرح توابع مدل و عملکردهای آن‌ها5-5-1- شرح توابع مشترک بین مدل‌های 2PL، WW و WD5-5-2- شرح توابع مدل 2PL5-5-3- شرح توابع مدل‌های WW و WD5-6- اولویت‌های معین شده برای تعیین فایر شدن گذار مورد نظر از بین گذارهای فعال5-7- نحوه‌ی مدل‌سازی‌ها5-7-1- نحوه مدل‌سازی مدل 2PL5-7-2- نحوه مدل‌سازی مدل‌های WW و WDفصل ششم: ارزیابی مدل‌های 2PL، WW و WDمقدمه6-1- مختصری در مورد اهمیت ارزیابی پایگاه داده‎ها6-2- پارامتر تعداد تراکنش‌های وارد شونده به سیستم6-2-1- بررسی مدل 2PL6-2-2- بررسی مدل WW6-2-3- بررسی مدل WD6-2-4- مقایسه‌ی مدل‌های 2PL، WW و WD براساس پارامتر تعداد تراکنش‌ها6-3- پارامتر تعداد دستورات هر تراکنش6-3-1- بررسی مدل 2PL6-3-2- بررسی مدل WW6-3-3- بررسی مدل WD6-3-4- مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد دستورات تراکنش‌ها6-4- پارامتر تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها6-4-1- بررسی مدل 2PL6-4-2- بررسی مدل WW6-4-3- بررسی مدل WD6-4-4- مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها6-5- پارامتر تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک6-5-1- بررسی مدل 2PL6-5-2- بررسی مدل WW6-5-3- بررسی مدل WD6-5-4- مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک6-6- نتیجه‌گیری6-7- پیشنهاداتمراجعدارای فهرست جداول و اشکال می باشدنمونه جدولجدول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 ارائه شده‌اند. در نهایتبه ارزیابی هر سه الگوریتم پرداخته شده است و الگوریتم‌ها با معیارهای بیانشده در فوق مورد بررسی قرار داده شده‌اند. آزمایش‌ها چندین بار تکرارگردیده و از مقادیر میانگین‌گیری به عمل آمده است. نمودارهای لازم نیز جهتمقایسه‌ی آسان‌تر ترسیم و بررسی گردیده‌اند.عنوان : ارزیابی برخی الگوریتم‌های کنترل همروندی در سیستم مدیریت پایگاه داده‌ها، از طریق مدل‌سازی با پتری رنگیتعداد صفحه : 123