اجرای همروند تراکنش‌ها در پایگاه داده‌ها با مشکلات بسیاری مواجه است. مکانیزم‌های کنترل همروندی، برای حفظ انزوا و عدم دخالت اجرا در میان تراکنش‌های متعارض و حفظ سازگاری پایگاه داده‌ها استفاده می‌شوند (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- پارامترهای مورد نظر برای ارزیابی مدل‌ها در این پایان‌نامه

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

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

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

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

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

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

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

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

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

[1]- Formal

[2]- Petri Nets

[3]- Colored Petri Net

[4]- Two-Phase Locking

[5]- Wait-Die

[6]- Wound-Wait

[7]- Fire