شکل ۴-۱- اجزای شبکه‌ی پتری ۴۰
شکل ۴-۲- عملکرد اجزای شبکه پتری ۴۱
شکل ۴-۳- گراف شبکه پتری ۴۲
شکل ۴-۴- مثال سیستم عابر بانک با گراف شبکه پتری ۴۳
شکل ۴-۵- مثال تابع y=f(x) با گراف شبکه پتری ۴۳
شکل ۴-۶- مثالی از نشانه‌گذاری یک مکان ۴۳
شکل ۴-۷- مثالی برای یک گذار توانا و یک گذار غیر توانا ۴۴

شکل ۴-۸- مثالی از اجرای یک شبکه پتری و نشانه‌گذاری اولیه آن ۴۴
آن ۴۵
آن ۴۵
آن ۴۵
شکل ۴-۱۲- مثالی از گراف شبکه پتری، قبل و بعد از فایر شدن ۴۶
شکل ۴-۱۳- مثالی از گراف شبکه پتری، قبل و بعد از فایر شدن ۴۶
شکل ۴-۱۴- یک شبکه پتری که دچار بن‌بست شده ۴۶
شکل ۴-۱۵- انواع شبکه‌های پتری و نحوه‌ی نشانه‌گذاری آن‌ها ۴۷
شکل ۴-۱۶- مدل‌سازی گره‌های تصمیم‌گیریِ فلوچارت با شبکه پتری ۴۷
شکل ۴-۱۷- مدل‌سازی فلوچارت با شبکه پتری ۴۸
شکل ۴-۱۸- شبکه پتری سلسله مراتبی ۵۰
شکل ۴-۱۹- مدل‌سازی مسئله ممانعت دو جانبه با شبکه پتری ۵۰
شکل ۵-۱- ماژول سطح بالا از مدل ۲PL به صورت سلسله مراتبی، برای سه تراکنش ۷۳
شکل ۵-۲- ماژول سطح بالا از مدل ۲PL به صورت سلسله مراتبی، برای دو تراکنش ۷۴
شکل ۵-۳- ماژول مربوط به تراکنش T1 از مدل ۲PL به صورت سلسله مراتبی ۷۴
شکل ۵-۴- ماژول سطح بالا از مدل‌های WW و WD به صورت سلسله مراتبی، برای سه تراکنش ۷۵
شکل ۵-۵- ماژول مربوط به تراکنش T1 از مدل‌های WW و WD به صورت سلسله مراتبی، برای سه تراکنش ۷۶
شکل ۵-۶- ماژول سطح بالا از مدل‌های WW و WD به صورت سلسله مراتبی، برای دو تراکنش ۷۷
شکل ۶-۱- مقایسه تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل‌های ۲PL، WW و WD 82
شکل ۶-۲- مقایسه تعداد گام‌های اجرای تراکنش‌های کوچک در مدل‌های ۲PL، WW و WD 87
شکل ۶-۳- مقایسه تعداد گام‌های اجرای تراکنش‌های بزرگ در مدل‌های ۲PL، WW و WD 87
شکل ۶-۴- مقایسه تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل‌های ۲PL، WW و WD 91
شکل ۶-۵- مقایسه تعداد گام‌های تراکنش‌ها با تعداد کم و زیاد داده‌های مشترک (بدون داده غیر مشترک) در مدل‌های ۲PL، WW و WD 96
فصل اول
مقدمه
مقدمه
اجرای همروند تراکنش‌ها در پایگاه داده‌ها با مشکلات بسیاری مواجه است. مکانیزم‌های کنترل همروندی، برای حفظ انزوا و عدم دخالت اجرا در میان تراکنش‌های متعارض و حفظ سازگاری پایگاه داده‌ها استفاده می‌شوند (a-Pashazadeh, 2012)، (b-Pashazadeh, 2012) و (Shu, and Young, 2002). به عبارت دیگر الگوریتم‌های کنترل همروندی، الگوریتم‌هایی هستند که باعث می‌شوند اجرای همروند چند تراکنش و اجرای متوالی آن معادل شود. مسئله‌ی کنترل همروندی در پایگاه داده‎ها امری ضروری و با اهمیت می‎باشد (Shu, and Young, 2002). در این زمینه مطالعات و تحقیقات فراوانی صورت گرفته است که نتیجه‌ی آن، به وجود آمدن الگوریتم‌های متنوع کنترل همروندی می‎باشد. همچنین با توجه به گسترش روزافزون انواع پایگاه داده‌ها در سراسر جهان، نیاز به بررسی پروتکل‌های کنترل همروندی پایگاه داده‌ها، بیشتر نمایان می‌شود.
مدل‌سازی رسمی^[۱] از الگوریتم‌های کنترل همروندی در مطالعه ویژگی‌های مختلف آن‌ها بسیار مفید است (a-Pashazadeh, 2012) و (b-Pashazadeh, 2012). بررسی‌ها نشان می‌دهد که شبکه‌های پتری (PNs)^[2] روش مناسبی برای مدل‌سازی رسمی مکانیزم‌های کنترل همروندی می‌باشند. شبکه‌های پتری انواع مختلفی دارند که یکی از آن‌ها شبکه‌ پتری رنگی (CPN)^[3] است. شبکه‌های پتری رنگی یکی از بهترین ابزارها برای مدل‌سازی الگوریتم‌های کنترل همروندی هستند (a-Pashazadeh, 2012) و (b-Pashazadeh, 2012). به همین دلیل در این پایان‌نامه نیز از این روش برای مدل‌سازی‌ها استفاده خواهد شد.
یکی از اصلی‌ترین مکانیزم‌های کنترل همروندی تکنیک قفل‌گذاری دو مرحله‌ای مبنایی (۲PL)^[4] است. این تکنیک کنترل همروندی از طریق قفل‌گذاری روی داده‌ها انجام می‌شود. قفل‌گذاری روی داده‌ها به تدریج که نیاز به دستیابی به آن‌ها پیش می‌آید صورت می‌گیرد و قفل‌گشایی از آن‌ها پس از دریافت تمام قفل‌های تراکنش رخ خواهد داد. در این تکنیک امکان رخ دادن بن‌بست وجود دارد، به همین دلیل دو مکانیزم پیش‌گیری از بن‌بست نیز مورد بررسی قرار خواهد گرفت.
مکانیزم منتظر گذاشتن-میراندن (WD)^[5] یکی از الگوریتم‌های پیش‌گیری از بن‌بست است که در آن حق تقدم زمانی تراکنش‌ها براساس زمان‌مهر و لحظه‌ی ورودشان به سیستم رعایت نمی‌شود. یعنی در مکانیزم WD هیچ قانونی وجود ندارد که تراکنشی که زودتر وارد سیستم شده است اولویت بیشتری برای زودتر دریافت کردن قفل‌های مورد نیازش داشته باشد، به همین دلیل به آن الگوریتم نابازدارنده می‌گویند. در سمت مقابل، مکانیزم زخمی کردن-منتظر گذاشتن (WW)^[6] وجود دارد که یکی از الگوریتم‌های پیش‌گیری از بن‌بست است که در آن حق تقدم زمانی تراکنش‌ها براساس زمان‌مهر و لحظه ورودشان به سیستم رعایت می‌شود. یعنی در مکانیزم WW تراکنشی که زودتر وارد سیستم شده است اولویت بیشتری برای زودتر دریافت کردن قفل‌های مورد نیازش دارد، به همین دلیل به آن الگوریتم بازدارنده می‌گویند.
در این پایان‌نامه تلاش بر این است که با مدل‌سازی مکانیزم‌های ۲PL، WD و WW، امکان بررسی اجرای تراکنش‌ها از دیدگاه‌ها و جوانب مختلفی را فراهم کنیم. سپس به ارزیابی این الگوریتم‌ها بپردازیم و آن‌ها را با بهره گرفتن از پارامترهای مختلفی که در جدول ۱-۱، اشاره شده است بررسی کنیم. در این جدول، در ستون اول پارامترهایی که قرار است ما در این پایان‌نامه بر اساس آن‌ها مدل‌ها را ارزیابی کنیم مشاهده می‌شود. سپس در ستون‌های بعدی نام الگوریتم‌هایی که قبلاً توسط این پارامترها مورد ارزیابی قرار گرفته بوده‌اند، نحوه‌ی پیاده‌سازی یا مدل‌سازی آن‌ها و همچنین مراجعشان را مشاهده می‌کنید.
جدول۱-۱- پارامترهای مورد نظر برای ارزیابی مدل‌ها در این پایان‌نامه

پارامتر
الگوریتم(ها)
پیاده‌سازی یا مدل‌سازی
مرجع