چكیده:مسئله‌ی كنترل همروندی در پایگاه داده‌ها امری ضروری و با اهمیت است. اجرای همروند تراكنش‌ها در یك سیستم مدیریت پایگاه داده، ممكن است منجر به ناسازگاری شود. ناسازگاری بر اثر مقادیر نادرستی است كه برای داده‌های موجود، بر اثر تعارض و تداخل اجرای تراكنش‌ها به وجود می‌آید. الگوریتم‌های كنترل همروندی، جهت تضمین اجرای همروند چندین تراكنش كه به صورت همروند با داده‌های مشترك كار میكنند طراحی شده‌اند. در زمینه‌ی كنترل همروندی پایگاه داده‌ها، تحقیقات فراوانی صورت گرفته است كه نتیجه آن، الگوریتم‌های متنوع كنترل همروندی میباشد. با توجه به الگوریتم‌های متنوع در این زمینه و این واقعیت كه روز به روز بر اهمیت آنها افزوده می‌شود، در حوزه ارزیابی الگوریتم‌های کنترل همروندی جای کارِ بسیاری وجود دارد.در این پایان‌نامه ابتدا الگوریتم‌های کنترل همروندی قفل‌گذاری دو مرحله‌ای مبنایی و همچنین تکنیک‌های زخمی كردن-منتظر گذاشتن و منتظر گذاشتن-میراندن که جزء تکنیک‌های پیش‌گیری از بن‌بست هستند، مدل‌سازی شده‌اند. از آنجا که شبکه پتری رنگی قابلیت‌های مدل‌سازی بالایی دارد و یکی از بهترین روش‌ها برای تحلیل مکانیزم‌های کنترل همروندی است؛ مدل‌سازی‌ها با استفاده از پتری رنگی و نرم‌افزار CPN Tools ارائه شده‌اند. یک مطالعه موردی ساده به عنوان مثال برای درک بهتر ارائه گردیده که مثال ذکر شده شامل سه تراکنش و دو منبع است. سپس الگوریتم‌های ذکر شده ارزیابی گردیده‌اند. ارزیابی بر اساس پارامترها و معیارهایی مثل تعداد تراکنش‌های وارد شونده به سیستم، تعداد دستورات هر تراکنش، تعداد داده‌های مشترک و غیر مشترک بین تراکنش‌ها و تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک، صورت گرفته است.آزمایش‌ها چندین بار تکرار و نتایج میانگین‌گیری شدند. با مقایسه و انجام بررسی‌ها، این نتیجه به دست آمد که در حالت کلی الگوریتم زخمی كردن-منتظر گذاشتن نسبت به دو الگوریتم دیگر زمان اجرای بهتری دارد. الگوریتم منتظر گذاشتن-میراندن از نظر زمان اجرا با اختلاف زیادی در سطح بدتری نسبت به دو الگوریتم دیگر قرار دارد و الگوریتم قفل‌گذاری دو مرحله‌ای مبنایی به دلیل امکان رخ دادن بن‌بست، مشکلات فراوانی دارد. واژه‌های كلیدی: کنترل همروندی، شبکه پتری رنگی، ارزیابی، قفل‌گذاری دو مرحله‌ای مبنایی، زخمی كردن-منتظر گذاشتن، منتظر گذاشتن-میراندن، بن‌بست، پیش‌گیری از بن‌بست فهرست مطالبعنوان صفحهفصل اول: مقدمه1-1- مقدمه21-2- ساختار پایان‌نامه4فصل دوم: پیشینه‌ی تحقیقمقدمه72-1- اهمیت الگوریتم‌های کنترل همروندی پایگاه داده‌ها72-2- برخی از انواع پایگاه داده‌ها82-3- انواع روش‌های پیاده‌سازی و مدل‌سازی الگوریتم‌های کنترل همروندی92-3-1-پیاده‌سازی در مقیاس کوچک92-3-2- مدل‌سازی و شبیه‌سازی توسط مدل مارکف112-3-3- مدل‌سازی و شبیه‌سازی توسط شبکه‌های پتری122-4- پارامترهای ارزیابی142-4-1- پارامترهای منابع سیستم142-4-2- پارامترهای حجم کاری152-5- پارامترها و آزمایش‌های انجام شده162-6- برخی از مزایا و معایب روش‌های مدل‌سازی و شبیه‌سازی182-7- لزوم انجام تحقیق20فصل سوم: تکنیک‌های کنترل همروندیمقدمه223-1- تکنیک‌های کنترل همروندی و انواع آنها223-2- تکنیک‌های قفل‌گذاری و انواع آنها233-2-1- تعریف قفل243-2-2- اندازه‌های واحد قفل‌شدنی243-2-3- ساختار قفل253-2-4- مثالی برای لزوم قفل‌گذاری263-2-5- مدیر قفل و مراحل انجام شده برای قفل‌گذاری273-2-6- نحوه در اختیار قرار دادن قفل توسط مدیر قفل283-2-7- قفل چند اسلوبی283-2-7-1- ماتریس همایندی یا سازگاری قفل‌های چند اسلوبی283-2-7-2- پروتکل قفل چند اسلوبی برای یک تراکنش293-2-7-3- تغییر قفل303-2-7-4- قفل چند اسلوبی و توالی‌پذیری303-2-7-5- خصوصیات قفل چند اسلوبی303-2-8- تکنیک قفل‌گذاری دو مرحله‌ای مبنایی303-2-8-1- مشکلات تداخل کنترل نشده313-2-8-2- خصوصیات و مشکلات 2PL مبنایی323-2-8-3- تغییر قفل در پروتکل 2PL333-2-8-4- تأثیرعملیات درج در کنترل همروندی333-2-8-5- تأثیرعملیات حذف در کنترل همروندی333-3- بن‌بست343-3-1- راه حل‌های مشكل بن‌بست353-3-2- تکنیک‌های زمان‌مهر363-3-2-1- الگوریتم WD373-3-2-2- الگوریتم WW373-3-2-3- خصوصیات الگوریتم WD و WW37فصل چهارم: شبکه‌های پتریمقدمه394-1- مختصری در مورد شبکه‌های پتری394-2- تفاوت UML و پتری394-3- تاریخچه شبکه‌های پتری404-4- ویژگی‌های شبکه‌های پتری404-5- اجزای شبکه‌ی پتری404-5-1- تعریف اجزای شبکه‌ی پتری414-5-2- وظایف اجزای شبکه‌ی پتری414-6- تعریف چهارگانه شبکه‌های پتری424-7- گراف شبکه پتری424-8- چند مثال از گراف شبکه پتری434-9- رفتار شبکه‌های پتری434-10- گذار توانا444-11- مثالی از اجرای یک شبکه پتری444-12- قوانین مربوط به فایر شدن گذار، در شبکه پتری454-13- شبکه‌های پتری به بن‌بست رسیده، زنده و غیر زنده464-14- انواع شبکه‌های پتری و نحوه‌ی نشانه‌گذاری آنها474-15- فلوچارت‌ها و شبکه‌های پتری474-16- انواع پتری484-16-1- شبکه پتری رنگی484-16-2- شبکه پتری زمانی494-16-3- شبکه پتری سلسله مراتبی50فصل پنجم: نحوه‌ی مدل‌سازی مکانیزم‌های 2PL، WW و WD با پتری رنگیمقدمه525-1- مختصری در مورد مدل‌سازی مکانیزم‌های 2PL، WW و WD525-1-1- مدل 2PL525-1-2- مدل‌های WW و WD535-2- مجموعه‌های رنگ535-2-1- مجموعه‌های رنگ در مدل 2PL535-2-2- مجموعه‌های رنگ در مدل‌های WW و WD545-2-3- توضیحات مجموعه‌های رنگ555-3- نشانه‌گذاری اولیه585-3-1- نشانه‌گذاری اولیه در مدل 2PL585-3-2- نشانه‌گذاری اولیه در مدل‌های WW و WD595-3-3- توضیحات نشانه‌گذاری اولیه595-4- متغیرها615-4-1- متغیرهای مدل 2PL615-4-2- متغیرهای مدل‌های WW و WD625-5- شرح توابع مدل و عملکردهای آنها625-5-1- شرح توابع مشترک بین مدل‌های 2PL، WW و WD635-5-2- شرح توابع مدل 2PL635-5-3- شرح توابع مدل‌های WW و WD765-6- اولویت‌های معین شده برای تعیین فایر شدن گذار مورد نظر از بین گذارهای فعال725-7- نحوه‌ی مدل‌سازی‌ها735-7-1- نحوه مدل‌سازی مدل 2PL735-7-2- نحوه مدل‌سازی مدل‌های WW و WD75فصل ششم: ارزیابی مدل‌های 2PL، WW و WDمقدمه796-1- مختصری در مورد اهمیت ارزیابی پایگاه داده‌ها796-2- پارامتر تعداد تراکنش‌های وارد شونده به سیستم806-2-1- بررسی مدل 2PL806-2-2- بررسی مدلWW806-2-3- بررسی مدل WD816-2-4- مقایسه‌ی مدل‌های 2PL، WW و WD براساس پارامتر تعداد تراکنش‌ها826-3- پارامتر تعداد دستورات هر تراکنش836-3-1- بررسی مدل 2PL836-3-2- بررسی مدل WW846-3-3- بررسی مدل WD856-3-4- مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد دستورات تراکنش‌ها866-4- پارامتر تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها886-4-1- بررسی مدل 2PL886-4-2- بررسی مدل WW896-4-3- بررسی مدل WD906-4-4-مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها916-5- پارامتر تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک926-5-1- بررسی مدل 2PL926-5-2- بررسی مدل WW936-5-3- بررسی مدل WD946-5-4- مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک966-6- نتیجه‌گیری976-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 برای مدل 2PL64جدول 5-4- پارامترهای خروجی تابع checklock برای مدل 2PL65جدول 5-5- پارامترهای ورودی تابع checklock برای مدل‌های WW و WD68جدول 5-6- پارامترهای خروجی تابع checklock برای مدل‌های WW و WD69جدول6-1- تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل 2PL80جدول 6-2- تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل WW81جدول 6-3- تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل WD82جدول 6-4- تعداد گام‌های اجرای تراکنش‌های کوچک و بزرگ در مدل 2PL84جدول 6-5- تعداد گام‌های اجرای تراکنش‌های کوچک و بزرگ در مدل WW85جدول 6-6- تعداد گام‌های اجرای تراکنش‌های کوچک و بزرگ در مدل WD86جدول 6-7- تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل 2PL88جدول 6-8- تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل WW89جدول 6-9- تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل WD90جدول 6-10- تعداد گام‌های اجرای تراکنش‌هایی بدون داده غیر مشترک، با تعداد کم و زیاد داده‌های مشترک در مدل 2PL92جدول 6-11- تعداد گام‌های اجرای تراکنش‌هایی بدون داده غیر مشترک، با تعداد کم و زیاد داده‌های مشترک در مدل WW93جدول 6-12- تعداد گام‌های اجرای تراکنش‌هایی بدون داده غیر مشترک، با تعداد کم و زیاد داده‌های مشترک در مدل WD95 فهرست شکلهاعنوان شکل صفحهشکل 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 و WD82شکل 6-2- مقایسه تعداد گام‌های اجرای تراکنش‌های کوچک در مدل‌های 2PL، WW و WD87شکل 6-3- مقایسه تعداد گام‌های اجرای تراکنش‌های بزرگ در مدل‌های 2PL، WW و WD87شکل 6-4- مقایسه تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل‌های 2PL، WW و WD91شکل 6-5- مقایسه تعداد گام‌های تراکنش‌ها با تعداد کم و زیاد داده‌های مشترک (بدون داده غیر مشترک) در مدل‌های 2PL، WW و WD96 فصل اول مقدمهاجرای همروند تراکنش‌ها در پایگاه داده‌ها با مشکلات بسیاری مواجه است. مکانیزم‌های کنترل همروندی، برای حفظ انزوا و عدم دخالت اجرا در میان تراکنش‌های متعارض و حفظ سازگاری پایگاه داده‌ها استفاده می‌شوند (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، اشاره شده است بررسی کنیم. در این جدول، در ستون اول پارامترهایی که قرار است ما در این پایان‌نامه بر اساس آنها مدل‌ها را ارزیابی کنیم مشاهده می‌شود. سپس در ستون‌های بعدی نام الگوریتم‌هایی که قبلاً توسط این پارامترها مورد ارزیابی قرار گرفته بوده‌اند، نحوه‌ی پیاده‌سازی یا مدل‌سازی آنها و همچنین مراجعشان را مشاهده می‌کنید.