پژوهش - تحقیق علمی دانشگاه

متن کامل پایان نامه را در سایت منبع fuka.ir می توانید ببینید

لبخندهای پر مهر زندگیم
پدر و مادر عزیزم

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

چکیده:مسئله‌ی کنترل همروندی در پایگاه داده‎ها امری ضروری و با اهمیت است. اجرای همروند تراکنش‎ها در یک سیستم مدیریت پایگاه داده، ممکن است منجر به ناسازگاری شود. ناسازگاری بر اثر مقادیر نادرستی است که برای داده‎های موجود، بر اثر تعارض و تداخل اجرای تراکنش‌ها به وجود می‎آید. الگوریتم‌های کنترل همروندی، جهت تضمین اجرای همروند چندین تراکنش که به صورت همروند با داده‎های مشترک کار می‎کنند طراحی شده‎اند. در زمینه‌ی کنترل همروندی پایگاه داده‎ها، تحقیقات فراوانی صورت گرفته است که نتیجه آن، الگوریتم‌های متنوع کنترل همروندی می‎باشد. با توجه به الگوریتم‌های متنوع در این زمینه و این واقعیت که روز به روز بر اهمیت آن‌ها افزوده می‎شود، در حوزه ارزیابی الگوریتم‌های کنترل همروندی جای کارِ بسیاری وجود دارد.
در این پایان‌نامه ابتدا الگوریتم‌های کنترل همروندی قفل‌گذاری دو مرحله‌ای مبنایی و همچنین تکنیک‌های زخمی کردن-منتظر گذاشتن و منتظر گذاشتن-میراندن که جزء تکنیک‌های پیش‌گیری از بن‌بست هستند، مدل‌سازی شده‌اند. از آنجا که شبکه پتری رنگی قابلیت‌های مدل‌سازی بالایی دارد و یکی از بهترین روش‌ها برای تحلیل مکانیزم‌های کنترل همروندی است؛ مدل‌سازی‌ها با استفاده از پتری رنگی و نرم‌افزار CPN Tools ارائه شده‌اند. یک مطالعه موردی ساده به عنوان مثال برای درک بهتر ارائه گردیده که مثال ذکر شده شامل سه تراکنش و دو منبع است. سپس الگوریتم‌های ذکر شده ارزیابی گردیده‌اند. ارزیابی بر اساس پارامترها و معیارهایی مثل تعداد تراکنش‌های وارد شونده به سیستم، تعداد دستورات هر تراکنش، تعداد داده‌های مشترک و غیر مشترک بین تراکنش‌ها و تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک، صورت گرفته است.
آزمایش‌ها چندین بار تکرار و نتایج میانگین‌گیری شدند. با مقایسه و انجام بررسی‌ها، این نتیجه به دست آمد که در حالت کلی الگوریتم زخمی کردن-منتظر گذاشتن نسبت به دو الگوریتم دیگر زمان اجرای بهتری دارد. الگوریتم منتظر گذاشتن-میراندن از نظر زمان اجرا با اختلاف زیادی در سطح بدتری نسبت به دو الگوریتم دیگر قرار دارد و الگوریتم قفل‌گذاری دو مرحله‌ای مبنایی به دلیل امکان رخ دادن بن‌بست، مشکلات فراوانی دارد.
واژه‌های کلیدی: کنترل همروندی، شبکه پتری رنگی، ارزیابی، قفل‌گذاری دو مرحله‌ای مبنایی، زخمی کردن-منتظر گذاشتن، منتظر گذاشتن-میراندن، بن‌بست، پیش‌گیری از بن‌بست
فهرست مطالبعنوان صفحه
TOC o "1-4" h z u فصل اول: مقدمه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
فهرست جدول‌هاعنوان جدول صفحه
TOC h z c "جدول (2-" جدول1-1- پارامترهای مورد نظر برای ارزیابی مدل‌ها در این پایان‌نامه4 TOC h z c "جدول (2-" جدول2-1- آزمایش‌های مورد نظر برای ارزیابی مدل‌ها در این پایان‌نامه18 TOC h z c "جدول (2-" جدول 3-1- مزایا و معایب اندازه‌ی واحد قفل‌شدنی25 TOC h z c "جدول (2-" جدول 3-2- نمایش لزوم قفل‌گذاری26 TOC h z c "جدول (2-" جدول 3-3- نمایش ناحیه کاری27 TOC h z c "جدول (2-" جدول 3-4- ماتریس همایندی29 TOC h z c "جدول (2-" جدول 3-5- سازگاری قفل‌های چند اسلوبی29 TOC h z c "جدول (2-" جدول 5-1- توضیحات مربوط به مجموعه‌های رنگی55 TOC h z c "جدول (2-" جدول 5-2- توضیحات مربوط به نشانه‌گذاری‌های اولیه60 TOC h z c "جدول (2-" جدول 5-3- پارامترهای ورودی تابع checklock برای مدل 2PL64 TOC h z c "جدول (2-" جدول 5-4- پارامترهای خروجی تابع checklock برای مدل 2PL65 TOC h z c "جدول (2-" جدول 5-5- پارامترهای ورودی تابع checklock برای مدل‌های WW و WD68 TOC h z c "جدول (2-" جدول 5-6- پارامترهای خروجی تابع checklock برای مدل‌های WW و WD69 TOC h z c "جدول (2-" جدول6-1- تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل 2PL80 TOC h z c "جدول (2-" جدول 6-2- تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل WW81 TOC h z c "جدول (2-" جدول 6-3- تعداد گام‌های اجرای دو، سه، پنج، ده و پنجاه تراکنش در مدل WD82 TOC h z c "جدول (2-" جدول 6-4- تعداد گام‌های اجرای تراکنش‌های کوچک و بزرگ در مدل 2PL84 TOC h z c "جدول (2-" جدول 6-5- تعداد گام‌های اجرای تراکنش‌های کوچک و بزرگ در مدل WW85 TOC h z c "جدول (2-" جدول 6-6- تعداد گام‌های اجرای تراکنش‌های کوچک و بزرگ در مدل WD86 TOC h z c "جدول (2-" جدول 6-7- تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل 2PL88 TOC h z c "جدول (2-" جدول 6-8- تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل WW89 TOC h z c "جدول (2-" جدول 6-9- تعداد گام‌های اجرای تراکنش‌ها با تعداد کم و زیاد داده‌های غیر مشترک در مدل WD90 TOC h z c "جدول (2-" جدول 6-10- تعداد گام‌های اجرای تراکنش‌هایی بدون داده غیر مشترک، با تعداد کم و زیاد داده‌های مشترک در مدل 2PL92 TOC h z c "جدول (2-" جدول 6-11- تعداد گام‌های اجرای تراکنش‌هایی بدون داده غیر مشترک، با تعداد کم و زیاد داده‌های مشترک در مدل WW93 TOC h z c "جدول (2-" جدول 6-12- تعداد گام‌های اجرای تراکنش‌هایی بدون داده غیر مشترک، با تعداد کم و زیاد داده‌های مشترک در مدل WD95
فهرست شکل‌هاعنوان شکل صفحه
TOC h z c "شکل (2-" شکل 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). در این زمینه مطالعات و تحقیقات فراوانی صورت گرفته است که نتیجه‌ی آن، به وجود آمدن الگوریتم‌های متنوع کنترل همروندی می‎باشد. همچنین با توجه به گسترش روزافزون انواع پایگاه داده‌ها در سراسر جهان، نیاز به بررسی پروتکل‌های کنترل همروندی پایگاه داده‌ها، بیشتر نمایان می‌شود.
مدل‌سازی رسمی از الگوریتم‌های کنترل همروندی در مطالعه ویژگی‌های مختلف آن‌ها بسیار مفید است (a-Pashazadeh, 2012) و (b-Pashazadeh, 2012). بررسی‌ها نشان می‌دهد که شبکه‌های پتری (PNs) روش مناسبی برای مدل‌سازی رسمی مکانیزم‌های کنترل همروندی می‌باشند. شبکه‌های پتری انواع مختلفی دارند که یکی از آن‌ها شبکه‌ پتری رنگی (CPN) است. شبکه‌های پتری رنگی یکی از بهترین ابزارها برای مدل‌سازی الگوریتم‌های کنترل همروندی هستند (a-Pashazadeh, 2012) و (b-Pashazadeh, 2012). به همین دلیل در این پایان‌نامه نیز از این روش برای مدل‌سازی‌ها استفاده خواهد شد.
یکی از اصلی‌ترین مکانیزم‌های کنترل همروندی تکنیک قفل‌گذاری دو مرحله‌ای مبنایی (2PL) است. این تکنیک کنترل همروندی از طریق قفل‌گذاری روی داده‌ها انجام می‌شود. قفل‌گذاری روی داده‌ها به تدریج که نیاز به دستیابی به آن‌ها پیش می‌آید صورت می‌گیرد و قفل‌گشایی از آن‌ها پس از دریافت تمام قفل‌های تراکنش رخ خواهد داد. در این تکنیک امکان رخ دادن بن‌بست وجود دارد، به همین دلیل دو مکانیزم پیش‌گیری از بن‌بست نیز مورد بررسی قرار خواهد گرفت.
مکانیزم منتظر گذاشتن-میراندن (WD) یکی از الگوریتم‌های پیش‌گیری از بن‌بست است که در آن حق تقدم زمانی تراکنش‌ها براساس زمان‌مهر و لحظه‌ی ورودشان به سیستم رعایت نمی‌شود. یعنی در مکانیزم WD هیچ قانونی وجود ندارد که تراکنشی که زودتر وارد سیستم شده است اولویت بیشتری برای زودتر دریافت کردن قفل‌های مورد نیازش داشته باشد، به همین دلیل به آن الگوریتم نابازدارنده می‌گویند. در سمت مقابل، مکانیزم زخمی کردن-منتظر گذاشتن (WW) وجود دارد که یکی از الگوریتم‌های پیش‌گیری از بن‌بست است که در آن حق تقدم زمانی تراکنش‌ها براساس زمان‌مهر و لحظه ورودشان به سیستم رعایت می‌شود. یعنی در مکانیزم WW تراکنشی که زودتر وارد سیستم شده است اولویت بیشتری برای زودتر دریافت کردن قفل‌های مورد نیازش دارد، به همین دلیل به آن الگوریتم بازدارنده می‌گویند.
در این پایان‌نامه تلاش بر این است که با مدل‌سازی مکانیزم‌های 2PL، WD و WW، امکان بررسی اجرای تراکنش‌ها از دیدگاه‌ها و جوانب مختلفی را فراهم کنیم. سپس به ارزیابی این الگوریتم‌ها بپردازیم و آن‌ها را با استفاده از پارامترهای مختلفی که در جدول 1-1، اشاره شده است بررسی کنیم. در این جدول، در ستون اول پارامترهایی که قرار است ما در این پایان‌نامه بر اساس آن‌ها مدل‌ها را ارزیابی کنیم مشاهده می‌شود. سپس در ستون‌های بعدی نام الگوریتم‌هایی که قبلاً توسط این پارامترها مورد ارزیابی قرار گرفته بوده‌اند، نحوه‌ی پیاده‌سازی یا مدل‌سازی آن‌ها و همچنین مراجعشان را مشاهده می‌کنید.
جدول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 ارائه شده‌اند. در نهایت به ارزیابی هر سه الگوریتم پرداخته شده است و الگوریتم‌ها با معیارهای بیان شده در فوق مورد بررسی قرار داده شده‌اند. آزمایش‌ها چندین بار تکرار گردیده و از مقادیر میانگین‌گیری به عمل آمده است. نمودارهای لازم نیز جهت مقایسه‌ی آسان‌تر ترسیم و بررسی گردیده‌اند.
ساختار پایان‌نامه
این پایان‌نامه به فرم زیر سازماندهی شده است.
در فصل دوم پیشینه‌ی تحقیق و مطالب مرتبط آورده شده است. در این فصل یک مرور کلی بر کلیات مطلب، اهداف، پیشینه‌ی تحقیق و سایر کارهای انجام شده در این زمینه خواهیم داشت. در پیشینه تحقیق، می‌پردازیم به این که تا کنون چه الگوریتم‌هایی ارائه شده، ارزیابی از طریق چه روش‌هایی صورت گرفته است و مانند آن‌ها. همچنین تعدادی از پارامترها و معیارهای ارزیابی الگوریتم‌های کنترل همروندی را بررسی خواهیم نمود. علاوه بر آن بعضی روش‌های پیاده‌سازی و شبیه‌سازی‌ موجود مانند پیاده‌سازی در مقیاس کوچک، شبیه‌سازی از طریق مدل مارکف، شبیه‌سازی از طریق شبکه‌های پتری و مانند آن‌ها را بررسی می‌کنیم و به مزایا و معایب آن‌ها اشاره‌ای خواهیم داشت. همچنین روش تجزیه و تحلیل از طریق صف نیز بطور مختصر مورد بررسی قرار می‌گیرد.
در فصل سوم انواع الگوریتم‌های کنترل همروندی پایه‌ای موجود را بررسی خواهیم کرد. در این میان تعدادی از الگوریتم‌های کنترل همروندی مانند پروتکل قفل 2PL که احتمال بن‌بست در آن وجود دارد و تکنیک‌های WW و WD که تکنیک‌های پیش‌گیری از بن‌بست هستند را مورد مطالعه قرار می‌دهیم. مزایا و معایب هر یک از این الگوریتم‌های کنترل همروندی پایه‌ای را نیز تا حدودی بررسی خواهیم نمود.
در فصل چهارم نیز به بررسی شبکه‌های پتری، مخصوصاً شبکه‌های پتری رنگی که یکی از ابزارهای بسیار مفید برای شبیه‌سازی الگوریتم‌های کنترل همروندی هستند، پرداخته می‌شود.
در فصل پنجم نحوه‌ی مدل‌سازی الگوریتم‌های مورد نظر با استفاده از شبکه‎های پتری بیان شده است؛ که شامل تعریف مجموعه‌های رنگ، نشانه‌گذاری‌های اولیه، متغیرهای موجود در مدل، شرح عملکرد توابع مدل و تعیین اولویت برای فایر شدن گذار مورد نظر از بین گذارهای فعال می‌باشد.
در فصل ششم که همان بخش پایانی است مدل‌ها بر اساس پارامترهای متفاوت بررسی و با هم مقایسه شده‌اند. آزمایش‌های مورد نیاز صورت گرفته و هرکدام چندین بار تکرار گردیده‌اند. نتایج میانگین‌گیری شده و نمودارهای لازم جهت مقایسه ترسیم شده‌اند. در نهایت نیز نتیجه‌گیری کلی از مباحث بیان شده مشاهده می‌شود و پیشنهاداتی برای کارهای آینده ارائه خواهد شد.
فصل دوم
پیشینه‌ی تحقیق

مقدمه
در این فصل پیشینه‌ی تحقیق و مطالب مرتبط آورده شده است. یک مرور کلی بر کلیات مطلب، اهداف، پیشینه‌ی تحقیق و سایر کارهای انجام شده در این زمینه خواهیم داشت. ابتدا اهمیت الگوریتم‌های کنترل همروندی پایگاه داده‌ها، از دید سایر تحقیقات انجام شده تا کنون بررسی می‌شود. سپس بعضی از انواع پایگاه داده‌هایی که در تحقیقات گذشته بیشتر مورد بررسی قرار گرفته بوده‌اند و نام آن‌ها در این فصل ذکر شده، تعریف و بررسی گردیده‌اند. علاوه بر آن بعضی روش‌های پیاده‌سازی و شبیه‌سازی‌ موجود مانند پیاده‌سازی در مقیاس کوچک، شبیه‌سازی از طریق مدل مارکف، شبیه‌سازی از طریق شبکه‌های پتری و مانند آن‌ها نیز بررسی شده و به مزایا و معایب آن‌ها اشاره‌ای شده است. همچنین روش تجزیه و تحلیل از طریق صف نیز بطور مختصر مورد بررسی قرار می‌گیرد. علاوه بر آن تعدادی از پارامترها و معیارهای ارزیابی الگوریتم‌های کنترل همروندی و آزمایش‌هایی که تا کنون صورت گرفته‌اند مورد مطالعه قرار گرفته است. در نهایت نیز برخی از مزایا و معایب روش‌های مدل‌سازی توضیح داده می‌شوند.
اهمیت الگوریتم‌های کنترل همروندی پایگاه داده‌ها
مدت زمان زیادی است که حفظ ثبات و سازگاری داده‌های به اشتراک گذاشته شده در سیستم پایگاه داده‌ها‌، مورد مطالعه قرار گرفته است (Shu, and Young, 2002). مطالعاتی که در زمینه‌ی ارزیابی الگوریتم‌های کنترل همروندی پایگاه داده‌ها صورت می‌گیرند، نه تنها در پایگاه داده‌های معمولی و پایگاه داده‌های بلادرنگ، بلکه در سیستم پایگاه داده‌ی توزیع شده‌، پایگاه داده مبتنی بر وب، سیستم‌های بلادرنگ سخت و مانند آن‌ها نیز کاربردهای اساسی دارند. نشان داده شده است که الگوریتم‌های قفل متمرکز و توزیع شده در اغلب مواقع، رفتارهایی مشابه در مواجه شدن با سیستم، مدل و مفروضات مشخص شده‌ انجام می‌دهند (Sarkar, and Nabendu, 2009). همچنین در (Shu, and Young, 2002) پروتکل کنترل همروندی چند نسخه‌ای به گونه‌ای بیان شده است که برای سیستم پایگاه داده متمرکز و توزیع شده مشابه است. تنها برخی موارد جزیی باید در یک محیط توزیع شده، به صورت اضافه‌تر از حالت متمرکز در نظر گرفته شوند. این موارد شامل افزودن تعدادی فیلد محدود است. این فیلدها شامل تخصیص ورژن داده، اطمینان از تثبیت شدن و تجزیه‌ناپذیری است.
برخی از انواع پایگاه داده‌ها
در اینجا لازم است به تعریف جزیی برخی از پایگاه داده‌های نام برده شده در این بخش بپردازیم.
الف) پایگاه داده‌ی بلادرنگ: همان پایگاه داده‌ی معمولی است که رخدادها و دستورات در همان لحظه پردازش می‌شوند.
ب) پایگاه داده‌ی توزیع شده‌: در طول سال‌های اخیر، توزیع شدگی به عنوان یک مسئله‌ی مهم برای پایگاه داده‌ها مورد بررسی قرار گرفته است (Ozsu, 1985). این مسئله دلایل منطقی بسیاری مانند توزیع طبیعی سازمان‌ها دارد. پایگاه داده توزیع شده مجموعه‌ای از قطعات مختلف است. به بیان دیگر بیش از یک شبکه از کامپیوترهای متصل، با یکدیگر ارتباط منطقی دارند. در یک پایگاه داده توزیع شده، مجموعه‌ای از داده‌ها می‌توانند در سراسر چندین مکان فیزیکی توزیع شوند. از آنجا که این پایگاه داده به صورت توزیع شده است، کاربران مختلف می‌توانند بدون تداخل با یکدیگر، به آن دسترسی داشته باشند. اهمیت ارزیابی الگوریتم‌های پایه‌ای کنترل همروندی پایگاه داده‌ها در جایی مشخص می‌شود که سیستم مدیریت پایگاه داده‌ها (DBMS) باید همروندی را در پایگاه داده‌ها برقرار کند و به صورت دوره‌ای پایگاه داده‌های پراکنده را همگام‌سازی کند تا مطمئن شود که همه آن‌ها دارای داده‌های سازگار هستند (Mousavi, Naji, and Ebrahimi, 2013). سیستم‌های پایگاه داده توزیع شده (DDBS) در سال‌های اخیر مورد توجه بیشتری قرار گرفته اند. به نظر می‌رسد که این زمینه برای برخی از کارهای تجزیه و تحلیل و مقایسه‌ای آماده است (Sarkar, and Nabendu, 2009) و (Ozsu, 1985).
ج) پایگاه داده مبتنی بر وب: سیستم پایگاه داده‌ی مبتنی بر وب سیستمی است که هم ویژگی‌های پایگاه داده‌ی توزیع شده و هم ویژگی‌های پایگاه داده‌ی بلادرنگ را دارد. البته، مشکلات کنترل همروندی در پایگاه داده‌ی مبتنی بر وب، پیچیده‌تر و دشوارتر از پایگاه داده‌های توزیع شده معمولی می‌باشد (Han, Jiang, and Luo, 2004).
انواع روش‌های پیاده‌سازی و مدل‌سازی الگوریتم‌های کنترل همروندی
برای ارزیابی الگوریتم‌های کنترل همروندی اولین نکته‌ای که باید مد نظر گرفته شود، شیوه‌ی نمایش الگوریتم است. شیوه‌ی نمایش الگوریتم می‌تواند از راه‌های زیر باشد.
پیاده‌سازی در مقیاس کوچک
مدل‌سازی و شبیه‌سازی: مدل‌سازی را می‌توان با ابزارهای متفاوتی انجام داد. ابزارهایی از جمله:
مدل مارکف
شبکه‌های پتری
پیاده‌سازی در مقیاس کوچک
در زیر بعضی از نمونه‌های پیاده‌سازی الگوریتم در مقیاس کوچک آورده شده است.
1- یک مکانیزم بر اساس قفل دو مرحله‌ای از طریق پیاده‌سازی در مقیاس کوچکی بررسی شده است (Al-Jumah, et al., 2000). قفل دو مرحله‌ای، یک مکانیزم کنترل همروندی است که در بیشتر سیستم‌های پایگاه داده‌های تجاری مورد استفاده قرار می‌گیرد. در مکانیزم قفل دو مرحله‌ای، یک تراکنش برای دسترسی به یک آیتم داده، باید قفل مناسب (خواندن و یا نوشتن) را بر روی آیتم داده قرار دهد. قرار دادن قفل با صدور یک درخواست قفل صورت می‌پذیرد. لازم به ذکر است که روشی که درخواست قفل تراکنش‌ها را تنظیم می‌کند و بررسی می‌کند که قفل به کدام درخواست داده شود، قطعاً بر عملکرد و بازدهی سیستم تأثیر می‌گذارد. در (Al-Jumah, et al., 2000)، یک مدل کلی برای پردازش تراکنش ارائه شده است. در این مدل، یک تراکنش از چند مرحله تشکیل شده است و در هر مرحله تراکنش می‌تواند درخواست قفل کردنِ یک یا تعداد بیشتری از آیتم‌های داده را داشته باشد.
2- چند مورد از تکنیک‌های کنترل همروندی سیستم مدیریت پایگاه داده‌ها که به طور معمول استفاده می‌شوند کمی بهبود داده شده‌اند و از طریق پیاده‌سازی در مقیاس کوچک، بررسی شده‌اند (Zhen, and Li, 2009). در سیستم پایگاه داده‌ی بلادرنگ، داده‌ها از طریق خوانده شدن، نوشته شدن و اجرای همروند تراکنش‌های بلادرنگ می‌توانند سازگاری پایگاه داده را تضعیف کنند. الگوریتم کنترل همروندی باید برای اطمینان از توالی‌پذیریِ زمان‌بندی تراکنش‌ها و سیستم پایگاه داده‌ی بلادرنگ و همچنین برای حفظ سازگاری داده‌ها مورد استفاده قرار گیرد. در واقع در (Zhen, and Li, 2009) برخی پروتکل‌های کنترل همروندیِ پایگاه داده‌ی بلادرنگ سنتی، بهبود داده شده‌اند.
3- (Shu, and Young, 2002) نیز یکی دیگر از مواردی است که از طریق پیاده‌سازی در یک مقیاس کوچک‌، سیستم‌های بلادرنگ سخت را بررسی کرده است.
4- یک الگوریتم امن جدید و پیاده‌سازی یک الگوریتم غیر امن به همراه عملکرد آن در (Hedayati, et al., 2010) مورد بررسی قرار گرفته است. به عبارت دیگر یک الگوریتم همروندی خوش‌بینانه امن جدید برای پایگاه داده‌های بلادرنگ امن پیشنهاد شده است. این الگوریتم و یک الگوریتم غیر امن پیاده‌سازی شده‌اند و عملکرد و بازدهی‌شان ارزیابی گردیده است. همچنین معیارهایی برای اندازه‌گیری امنیت در سیستم‌های پایگاه داده‌ی بلادرنگ معرفی شده است. نتایج نشان می‌دهد که الگوریتم پیشنهادی در آنجا، از لحاظ امنیتی بودن و به موقع بودن به طور نسبتاً خوبی در مقایسه با الگوریتم غیر امن کارش را انجام می‌دهد. اما پیاده‌سازی الگوریتم‌ها برای ارزیابی با دشواری زیادی انجام شده است.
5- (Lee, 1999) به بررسی توالی‌پذیری روش کنترل همروندی خوش‌بینانه می‌پردازد؛ این کار را از طریق پیاده‌سازی آن انجام می‌دهد. با وجود این واقعیت که پیاده‌سازی تراکنش‌ها در اکثر سیستم‌های مدیریت پایگاه داده‌های تجاری، با استفاده از قفل برای کنترل همروندی صورت می‌گیرد، کنترل همروندی خوش‌بینانه نیز توجه بسیاری به دست آورده است. کنترل همروندی خوش‌بینانه در انواع جدیدی از برنامه‌های کاربردی داده‌های فشرده، مانند طراحی به کمک کامپیوتر و مهندسی نرم‌افزار به کمک کامپیوتر استفاده شده است. در آن مقاله به توصیف و تجزیه و تحلیل یک الگوریتم کنترل همروندی جدید اشاره می‌شود که به عنوان یک نوع جدید از یک الگوریتم کنترل همروندی خوش‌بینانه، توالی‌پذیری را ایجاد می‌کند. این الگوریتم، از بسیاری الگوریتم‌های خوش‌بینانه بهتر عمل می‌کند. ارزیابی مدل و مقایسه آن با برخی مدل‌های دیگری با کمی دشواری انجام شده است و به اجبار، ارزیابی برای حجم کاری خاصی انجام شده است (Lee, 1999).
6- یک الگوریتم جدید برای کنترل همروندی در سیستم‌های پایگاه داده توزیع شده از طریق پیاده‌سازی در مقیاس کوچک ارائه شده است (Mousavi, et al., 2013). بررسی‌ها روی موارد و پارامترهای خاصی صورت گرفته است. تعداد پیام‌های رد و بدل شده بین گره‌ها در الگوریتم‌ها، به دلیل دشواری‌هایی که در پیاده‌سازی در مقیاس کوچک وجود دارد به طور جداگانه مشخص شده و ثابت مانده است. سپس زمان اجرای الگوریتم‌ها در 20 تکرار با تعداد گره‌های متفاوت ( در ابتدا 5 گره، سپس 15 و 20 گره) بررسی شده است.
مدل‌سازی و شبیه‌سازی توسط مدل مارکف
در اینجا نمونه‌ای از مدل‌سازی توسط مدل مارکف بیان شده است. قفل کردن و زمان‌مهر دو روش برای کنترل همروندی در سیستم‌های پایگاه داده هستند. اگرچه مطالعاتی در زمینه‌ی عملکرد، بازدهی و تحلیل تکنیک قفل در پیشینه‌ی تحقیق آن وجود دارد، اما به نظر می‌رسد که تا حد زیادی، مطالعه عملکرد، بازدهی و تحلیل الگوریتم‌های کنترل همروندی بر پایه زمان‌مهر، ناشناخته باقی مانده است. از آنجا که کلاس بزرگی از الگوریتم‌های کنترل همروندی با استفاده از زمان‌مهر وجود دارد، یک نیاز قوی به مطالعه عملکرد، بازده و تحلیل کردن این الگوریتم حس می‌شود. (Singhal, 1991) نیز به تجزیه و تحلیل عملکرد و بازده الگوریتم مرتب‌سازی زمان‌مهر پایه‌ای، برای کنترل همروندی در سیستم‌های پایگاه داده پرداخته است. در آن مقاله فرض شده است که یک تراکنش، وضعیت متوسطِ سیستم و تمام تراکنش‌ها را نشان می‌دهند و با عملکرد متوسط در حالت پایدار، اجازه می‌دهد که به جای توزیع‌های احتمال‌ها با میانگین کار کنیم. بنابراین، روش مورد استفاده در تجزیه و تحلیل تقریبی است و روش با مثال عددی نشان داده شده است. مجموعه‌ای از معیارهای اندازه گیری عملکرد و بازده برای مقادیر مختلفی از پارامترهای مدل مطرح شده است. در آنجا بیان شده است که نتایج حاصل از تجزیه و تحلیل تا حدودی مانند یک مطالعه شبیه‌سازی معتبر، مورد تأیید است. با اینکه این روش تقریبی است اما تکنیک‌های مشابه به آنچه در فوق بیان شد نیز توسط محققان دیگر استفاده شده و به مطالعه عملکرد و بازده الگوریتم قفل پرداخته است.
مدل‌سازی و شبیه‌سازی توسط شبکه‌های پتری
یکی از ابزارهای شبیه‌سازی الگوریتم‌های کنترل همروندی شبکه‌های پتری هستند. به طور کلی شبکه‌های پتری ابزار امیدوار کننده و بسیار مفیدی برای مدل‌سازی و تحلیل کردن اطلاعات سیستم‌هایی هستند که عملیات همروند، همزمان، ناهمزمان، موازی و یا توزیع شده دارند (Han, et al., 2004). شبکه‌های پتری در اصل برای مدل‌سازی ناهمزمان و جریان کنترل همروندی طراحی شده‌اند و (Mikkilineni, Chow, and Su, 1988) این موضوع را به بهترین وجه نشان می‌دهد. در زیر نمونه‌های مختلفی از کاربرد انواع شبکه‌های پتری، در زمینه‌ی شبیه‌سازی الگوریتم‌های کنترل همروندی را مشاهده می‌نمایید.
1- یک مدل شبکه پتری زمانی، برای انجام تراکنش‌های همروندِ سیستم پایگاه داده‌ی مبتنی بر وب ارائه شده است (Han, et al., 2004). این مدل بدون بن‌بست است، توالی‌پذیر است، از راه‌اندازی‌های مجدد بی‌فایده و انتظارهای بیهوده جلوگیری می‌کند. در آن مقاله مدل‌های شبکه پتریِ مربوط به تمام سایت‌ها، به یک مدل کاهش داده شده است. یعنی از طریق ترکیب و هماهنگ‌سازیِ مدل‌های مختلف، فقط یک مدل شبکه پتری برای انجام تراکنش‌های همروند جهانی ایجاد شده است. همچنین مقیاس مدل شبکه پتری برای هر سایت با استفاده از تکنیک‌های خاصی، قبل از ترکیب کردن، تا حد زیادی کاهش داده شده است. این روش مشکل زیاد بودنِ تعداد وضعیت‌ها و تجزیه و تحلیل‌های شبکه‌های پتری را حل می‌کند. در آخر نیز، شرط کافی و لازم برای بررسی اینکه آیا در نهایت، در کلِ سیستم بن‌بست وجود دارد یا نه، ارائه شده است.
2- تئوری بیان شده در (Chen, Wang and Wang, 2011) از طریق شبکه پتری اثبات شده است و به کمک شبکه پتری نشان داده شده است که پروتکل پیشنهادی امکان‌پذیر و مؤثر است و می‌تواند نیازهای تراکنش بلادرنگ را برطرف کند. در نهایت، از طریق نظریه شبکه پتری درستی این موضوع ثابت شده است. در واقع در (Chen, et al., 2011) بر اساس ویژگی‌های سیستم پایگاه داده‌ی بلادرنگ، یک پروتکل کنترل همروندی برای پایگاه داده‌های بلادرنگ ارائه شده است. براساس آزمایش انجام شده در آن مقاله نشان داده می‌شود که پروتکل کنترل همروندی پایگاه داده‌ی بلادرنگ می‌تواند کارایی پردازش تراکنش‌های سیستم پایگاه داده‌ی بلادرنگ را افزایش دهد. بررسی کارایی و عملکرد مدل از طریق شبکه پتری اثبات شده است.
3- نتایج حاصل از مطالعه و ارزیابی عملکرد و بازدهی الگوریتم‌های کنترل همروندی در پایگاه داده توزیع شده در (Sarkar, and Nabendu, 2009) گزارش شده است. در واقع یک مدل‌سازی جایگزین و روش ارزیابی عملکرد و بازدهی برای الگوریتم‌های کنترل همروندی پایگاه داده توزیع شده ارائه شده است که در بررسی بیشتر تنظیمات توزیع شده به طور کلی مفید است. پتری ویژگی‌هایی دارد که می‌تواند به عنوان یک ابزار ارزیابی عملکرد و بازدهی مورد استفاده قرار گیرد. اعتبارسنجی برخی از نمونه‌های نتایج به دست آمده از شبیه‌سازی پتری، با تجزیه و تحلیل صف مورد مقایسه قرار گرفته است. ارزیابی عملکرد و بازدهی در پتری، تحت سناریوهای واقع بینانه‌تر است. زیرا مفروضات گزارش شده در روش تجزیه و تحلیل از طریق صف به شدت محدود شده هستند، با این حال، لازم به ذکر است که این فرضیات معمولاً توسط بسیاری از مطالعات عملکرد و بازدهی در این حوزه ایجاد شده‌اند و مورد استفاده قرار می‌گیرند.
4- ویژگی‌های همزمان و ناهمزمانِ شبکه‌های پتری به خوبی با همان ویژگی‌های ذاتی در معماری پردازش همروند در پایگاه داده‌ها مطابق است (Mikkilineni, et al., 1988). نتایج عملکرد و بازدهی حاصل از شبیه‌سازی انجام شده با پتری، در واقع عملکرد دقیق سیستم واقعی را ارائه می‌دهد. با این حال مدل‌سازی عملکرد و بازده عملیات پایگاه داده‌ای که در آن مقاله ارائه شده است نتوانسته به طور کامل از تمام قابلیت‌های مدل‌های شبکه پتری استفاده کند.
5- مدل‌سازی پروتکل تثبیت دو مرحله‌ای برای مدیریت تراکنش در محیط توزیع شده با استفاده از شبکه پتری زمانی، مورد مطالعه قرار گرفته است (Sarkar, and Nabendu, 2009).
6- کنترل همروندی تراکنش‌های پایگاه داده با استفاده از شبکه پتری معمولی بر اساس پروتکل قفل دو مرحله‌ای، صورت گرفته است (Jie, Fengying, and Huijiao, 2010). به عبارت دیگر خصوصیات رسمی و مشخصات صوری برای کنترل همروندی تراکنش‌های پایگاه داده با استفاده از شبکه پتری معمولی بر اساس پروتکل قفل دو مرحله‌ای مورد مطالعه قرار گرفته است و این اطمینان را حاصل می‌کند که توالی‌پذیری همروندی زمان‌بندها بررسی شده است.
7- یک پروتکل براساس پروتکل قفل دو مرحله‌ای برای پایگاه داده توزیع شده با استفاده از شبکه پتری رنگی مدل شده است (Voss, 1997).
8- روش‌های کپی اصلی و اولیه با استفاده از پتری سطح بالا که همان شبکه پتری رنگی است مدل شده‌اند (Seatzu, et al., 2013).
9- یک مدل جدید از کنترل همروندی برای پایگاه داده توزیع شده، بر اساس پروتکل قفل دو مرحله‌ای با استفاده از شبکه پتری رنگی مدل شده است (a-Pashazadeh, 2012) و (b-Pashazadeh, 2012).
پارامترهای ارزیابی
پارامترهای ارزیابی الگوریتم‌ها یکی از مهمترین موارد در ارزیابی الگوریتم‌ها هستند. پارامترهای کلیِ پایگاه داده‌ها برای ارزیابیِ پیاده‌سازی، مدل‌سازی و شبیه‌سازی‌های صورت گرفته، به طور کلی به دو دسته تقسیم می‌شوند (Hedayati, et al., 2010).
پارامترهای منابع سیستم
پارامترهای حجم کاری
پارامترهای منابع سیستم
تعدادی از پارامترهای منابع سیستم عبارتند از:
تعداد صفحات داده‌ها در پایگاه داده (Hedayati, et al., 2010)
اندازه پایگاه داده (Sarkar, and Nabendu, 2009) و (Hedayati, et al., 2010)
زمان پردازنده برای پردازش کردن یک صفحه پایگاه داده (Hedayati, et al., 2010)
زمان پردازنده برای پردازش کردن یک آیتم داده (Sarkar, and Nabendu, 2009)
زمان پردازنده برای همگام‌سازی و همزمان‌سازی (Sarkar, and Nabendu, 2009)
زمان ورودی/خروجی برای پردازش یک آیتم داده (Sarkar, and Nabendu, 2009)
زمان ورودی/خروجی برای همگام‌سازی و همزمان‌سازی (Sarkar, and Nabendu, 2009)
احتمال اینکه یک عملیات نوشتن انجام شود (در صورتی که از الگوریتمی استفاده شود که نیاز به قفل‌گذاری دارد می‌توانیم آن را احتمالِ قفل نوشتن نیز در نظر بگیریم) (Shu, and Young, 2002). و (Mikkilineni, et al., 1988).
تعداد ترمینال‌های تراکنش‌ها (تعداد پایانه‌هایی که تراکنش‌ها از آن‌ها وارد می‌شوند) (Shu, and Young, 2002) و (Hedayati, et al., 2010).
تعداد سایت‌های موجود در سیستم (این پارامتر مخصوص پایگاه داده‌های توزیع شده است) (Sarkar, and Nabendu, 2009).
زمان پردازش کردن برای انتقال یا دریافت پیام (این پارامتر مخصوص پایگاه داده‌های توزیع شده است) (Sarkar, and Nabendu, 2009).
زمان انتقال پیام (این پارامتر مخصوص پایگاه داده‌های توزیع شده است) (Sarkar, and Nabendu, 2009).
پهنای باند شبکه (این پارامتر مخصوص پایگاه داده‌های توزیع شده است) (Sarkar, and Nabendu, 2009).
تعدادِ منابع فیزیکی (پردازنده و دیسک) سیستم (Al-Jumah, et al., 2000) (البته این مورد پارامتری است که تأثیرگذار است اما اصولاً ثابت در نظر گرفته می‌شود سپس بررسی صورت می‌گیرد. مثلاً در (Al-Jumah, et al., 2000) واحد منابع این گونه بود: یک پردازنده و دو دیسک.)
مدل سیستم کامپیوتری (روحانی رانکوهی، 1386)
از آنجا که پارامترهای منابع سیستم پارامترهای سخت افزاری هستند، به عنوان پارامترهای مورد نظر این پایان‌نامه استفاده نشده‌اند.
پارامترهای حجم کاری
تعدادی از پارامترهای حجم کاری عبارتند از:
نرخ ورود تراکنش‌ها (Hedayati, et al., 2010)
تعداد تراکنش‌های وارد شونده به سیستم (Hedayati, et al., 2010)
میانگین اندازه تراکنش (Sarkar, and Nabendu, 2009) و (Mikkilineni, et al., 1988)
اندازه هر تراکنش (تعداد دستورات هر تراکنش) (Singhal, 1991) و (روحانی رانکوهی، 1386)
سربار برای شروع مجدد (Hedayati, et al., 2010)
تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها (Al-Jumah, et al., 2000)
تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک (Al-Jumah, et al., 2000)
تعداد داده‌های درخواست شونده توسط هر تراکنش (Al-Jumah, et al., 2000)
میانگین نمایی زمان بین ورود تراکنش‌ها (Shu, and Young, 2002) و (Hedayati, et al., 2010)
متوسط.زمان بین ورود تراکنش‌ها (Sarkar, and Nabendu, 2009)
سطح چند برنامه‌ای (حداکثر تعداد تراکنش‌های فعال در سیستم) (Al-Jumah, et al., 2000) و (Singhal, 1991)
در این پایان‌نامه بر روی برخی از پارامترهای حجم کاری متمرکز شده‌ایم. در جدول 1-1، به پارامترهای انتخاب شده برای بررسی و ارزیابی مدل‌ها به طور کامل اشاره گردید. این پارامترها شامل: تعداد تراکنش‌های وارد شونده به سیستم، اندازه هر تراکنش (تعداد دستورات هر تراکنش)، تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها و تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک می‌باشند.
پارامترها و آزمایش‌های انجام شده
بعضی از موارد و پارامترهایی که در پیاده‌سازی و یا شبیه‌سازی، در آزمایش‌های گوناگون، با توجه به نیاز مسئله نسبت به هم سنجیده شده‌اند و تغییراتشان بررسی شده است عبارتند از:
تأثیر زمان بین ورود تراکنش‌ها بر زمان پاسخ (Sarkar, and Nabendu, 2009) و (Lee, 1999)
تأثیر زمان بین ورود تراکنش‌ها بر استفاده از پردازنده (Sarkar, and Nabendu, 2009)
تأثیر میانگین اندازه تراکنش بر زمان پاسخ (Sarkar, and Nabendu, 2009)
تأثیر میانگین اندازه تراکنش بر استفاده از پردازنده (Sarkar, and Nabendu, 2009)
تأثیر میانگین اندازه تراکنش بر استفاده از ورودی/خروجی (Sarkar, and Nabendu, 2009)
تأثیر تعداد سایت‌ها بر زمان پاسخ (این آزمایش مخصوص ارزیابی پایگاه داده‌های توزیع شده است) (Sarkar, and Nabendu, 2009).
تأثیر تعداد سایت‌ها بر متوسطِ تعدادِ پیام‌ها (این آزمایش مخصوص ارزیابی پایگاه داده‌های توزیع شده است) (Sarkar, and Nabendu, 2009).
تأثیر تعداد سایت‌ها بر استفاده از پردازنده (این آزمایش مخصوص ارزیابی پایگاه داده‌های توزیع شده است) (Sarkar, and Nabendu, 2009).
تأثیر اندازه پایگاه داده در زمان پاسخ (Sarkar, and Nabendu, 2009)
تأثیر تعداد داده‌های غیر مشترک هر تراکنش بر زمان اجرا (Al-Jumah, et al., 2000)
تأثیر تعداد داده‌های مشترک بین تراکنش‌ها بر زمان اجرا (Al-Jumah, et al., 2000)
بررسی زمان پاسخ در مقابل درجه‌ی چند برنامه‌ای (Singhal, 1991) و (Al-Jumah, et al., 2000)
احتمال راه‌اندازی مجدد تراکنش در مقابل درجه‌ی چند برنامه‌ای (Singhal, 1991)
تأثیر اندازه هر تراکنش (تعداد دستورات هر تراکنش) بر زمان اجرا (Singhal, 1991)
نرخ ورود تراکنش (بر حسب تراکنش/ثانیه) در مقایسه با راه‌اندازی‌های مجدد هر تراکنش (Lee, 1999)
تأثیر تعداد تراکنش‌های ورودی به سیستم بر زمان اجرای تراکنش‌ها (Hedayati, et al., 2010)
در این پایان‌نامه ما زمان اجرای تراکنش‌ها برای معیارهای بیان شده در جدول 1-1، را محاسبه خواهیم کرد و سپس مدل‌ها را با هم مقایسه و ارزیابی می‌نماییم. در واقع از بین آزمایش‌های فوق آزمایش‌هایی که در جدول 2-1، مشاهده می‌نمایید برای این پایان‌نامه انتخاب شده‌اند.
جدول2-1- آزمایش‌های مورد نظر برای ارزیابی مدل‌ها در این پایان‌نامه
آزمایش مرجع
تأثیر تعداد تراکنش‌های ورودی به سیستم بر زمان اجرای تراکنش‌ها (Hedayati, et al., 2010)
تأثیر اندازه هر تراکنش (تعداد دستورات هر تراکنش) بر زمان اجرا (Singhal, 1991)
تأثیر تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها بر زمان اجرا (Al-Jumah, et al., 2000)
تأثیر تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک بر زمان اجرا (Al-Jumah, et al., 2000)
برخی از مزایا و معایب روش‌های مدل‌سازی و شبیه‌سازی
در اینجا قصد داریم مزایا و معایب بعضی از روش‌های بیان شده را بگوییم.
مزایای شبکه‌های پتری
بدیهی است که ادعایی نیست که شبکه‌ی پتری از همه روش‌های دیگر مدل‌سازی بهتر است. اما در بسیاری از جهات استفاده از این روش مدل‌سازی بسیار مناسب‌تر است.
برای مدل‌سازی تمام سیستم‌ها مناسب است و مختص به نوع خاصی از سیستم‌ها نیست (Jensen, Christensen, Kristensen, and Michael, 2010).
شبکه‌های پتری دارای عناصر کم ولی کارآمد هستند که این ویژگی منجر به سادگی کار با این شبکه‌ها شده است (Devillers, and Best, 1987).
شبکه پتری را می‌توانیم با زمان ادغام کنیم تا کارایی سیستم را مورد ارزیابی قرار دهیم یعنی گلوگاه‌هایی که در سیستم زمان‌بَر هستند را پیدا کنیم (Moreno, 2007) و (Jensen, et al., 2010).
شبکه‌های پتری امکان تعریف سلسله مراتبی را نیز دارند؛ بدین صورت یک شبکه پتری بزرگ را می‌توان از مرتبط کردن چندین شبکه پتری کوچک‌تر ساخت (Devillers, and Best, 1987).
شبکه‌های پتری قدرت زیادی دارند و در آن‌ها الگوریتم‌های مختلفی جهت تحلیل شبکه‌ها ارائه شده است.
نمایش گرافیکی شبکه پتری درک مسائل را ملموس‌تر می‌کند و باعث جذابیت بیشتر می‌شود (Jensen, et al., 2010).
شبکه‌های پتری در برابر تغییرات کوچک در یک سیستم مدل‌سازی شده مقاوم هستند (Jensen, et al., 2010).
شبکه پتری را می‌توانیم با زمان ادغام کنیم تا کارایی سیستم را مورد ارزیابی قرار دهیم یعنی گلوگاه‌هایی که در سیستم زمان‌بَر هستند را پیدا کنیم (Jensen, et al., 2010).
مشکلات روش صف
شبکه‌ی پتری عملکرد بسیار مناسبی دارد و پیچیدگی‌های تحلیل در روش صف را ندارد. به طور مثال، (Sarkar, and Nabendu, 2009) برای تجزیه و تحلیل، یک الگوریتم (الگوریتم قفل متمرکز) را انتخاب کرده است که قبلاً با استفاده از تجزیه و تحلیل‌های صف بررسی شده است. سپس مجدداً آن الگوریتم را توسط شبکه پتری بسط یافته تحلیل کرده است. مشاهده شده است که نتایج به دست آمده در آن مطالعه نیز مطابق و بسیار نزدیک به نتایج به دست آمده توسط تحلیل در روش صف است ولی دشواری‌های روش صف در مدل‌سازی آن مشاهده نشده است.
معایب مدل‌سازی مارکف
با توجه به ماهیت پیچیده‌ی الگوریتم‌های کنترل همروندی، بسیار دشوار است که بخواهیم عملکرد آن‌ها را از طریق تجزیه و تحلیل ریاضی و با دقت بررسی کنیم (Singhal, 1991). در آنجا، نشان داده شده که حتی پس از تعیین برخی از مفروضات، مدل کردن دقیقِ عملکرد و بازدهی الگوریتم کنترل همروندی مرتب‌سازی زمان‌مهر پایه‌ای با کمک مدل مارکف، آنقدر پیچیده است که عملاً پیدا کردن راه حل فرم بسته‌ی آن غیر ممکن است. برای ساده‌تر کردن موضوع به این صورت عمل شد که یک تراکنش به صورت ایزوله به جای بررسی کل سیستم، تجزیه و تحلیل شد. چنین تجزیه و تحلیلی پیچیدگی قابل ملاحظه‌ای را کاهش داد. روش مورد استفاده در تجزیه و تحلیل الگوریتم‌های کنترل همروندی با مدل مارکف تقریبی است و اصولاً روش با مثال عددی نشان داده می‌شود.
لزوم انجام تحقیق
با توجه به بررسی‌های صورت گرفته و مطالعه پیشینه‌ی تحقیق، که در این بخش نیز به آن اشاره شد، این نتیجه به دست آمد که تا کنون به ارزیابی الگوریتم‌های کنترل همروندی 2PL، WW و WD بر اساس پارامترهای ذکر شده در جدول 1-1، پرداخته نشده است و تأثیر این پارامترها بر زمان پاسخ این الگوریتم‌ها، مورد بررسی قرار نگرفته است.
در این پایان‌نامه سعی داریم، براساس پارامترهای:
تعداد تراکنش‌های وارد شونده به سیستم
اندازه هر تراکنش (تعداد دستورات هر تراکنش)
تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها
تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک
به بررسی الگوریتم‌های 2PL، WW و WD بپردازیم. در این راستا از روش مدل‌سازی با استفاده از شبکه پتری رنگی که یکی از بهترین راه‌ها برای مدل‌سازی الگوریتم‌های کنترل همروندی است، استفاده نموده‌ایم. سپس به بررسی و ارزیابی الگوریتم‌ها پرداخته‌ایم.
فصل سومتکنیک‌های کنترل همروندی

مقدمه
در این فصل برخی از انواع الگوریتم‌های کنترل همروندی پایه‌ای را معرفی خواهیم کرد. در این میان تعدادی از الگوریتم‌های کنترل همروندی مانند: قفل اسلوبی و تکنیک 2PL که بیشتر مد نظر هستند را به طور مفصل توضیح خواهیم داد. علاوه بر آن تکنیک‌های WW و WD که تکنیک‌های پیش‌گیری از بن‌بست هستند را نیز به طور کامل مورد مطالعه قرار می‌دهیم. مزایا و معایب هر یک از این الگوریتم‌های کنترل همروندی پایه‌ای نیز بررسی خواهد شد. اطلاعات ذکر شده در این فصل از مرجع (روحانی رانکوهی، 1386) اقتباس شده‌اند.
تکنیک‌های کنترل همروندی و انواع آن‌ها
به طور کلی می‌دانیم که با کنترل درست اجرای همروند تراکنش‌ها، کارایی سیستم افزایش می‌یابد. اگر طرح اجرای همروند، توالی‌پذیر باشد نتیجه‌ی درست حاصل می‌شود. برای تضمین توالی‌پذیریِ طرح اجرا، از تکنیک‌های کنترل همروندی استفاده می‌شود. انواع تکنیک‌های کنترل همروندی عبارتند از:
قفل‌گذاری: روش بدبینانه
زمان‌مهر: کمی خوش‌بینانه
چند نسخه‌سازی: روش خوش‌بینانه
تأیید: روش خوش‌بینانه
ترکیبی از تکنیک‌های خوش‌بینانه و بدبینانه در سیستم پایگاهی توزیع شده
تکنیک‌های کنترل همروندی بیان شده در فوق یک سری ویژگی‌های مشترک دارند. به عبارت دیگر هرکدام از تکنیک‌های فوق از استراتژی خاصی استفاده می‌کنند، که در زیر بیان شده‌اند.
وادار کردن تراکنش به انتظار
پیروی از نظم خاص
اجرای تراکنش بدون محدودیت و از بین بردن اثرات آن‌ها در صورت طرد شدن: در صورت بروز تعارض یا برخورد، سیستم، یک یا بیش از یک تراکنش را طرد کرده و اثر اجرای ناقص آن‌ها در پایگاه داده را خنثی می‌کند.
تکنیک‌های قفل‌گذاری و انواع آن‌ها
تکنیک قفل‌گذاری جزء تکنیک‌های بدبینانه است. در سیستم مدیریت پایگاه داده‌ها، زیرسیستمی به نام زیرسیستم قفل‌گذاری وجود دارد. انواع تکنیک‌های قفل‌گذاری عبارتند از:
قرار دادن انواع قفل
قفل‌گذاری دوگانی
قفل‌گذاری چند اسلوبی
قفل‌گذاری دو مرحله‌ای (2PL)
2PL مبنایی
2PL محافظه‌کارانه
2PL شدید
2PL جسورانه
2PL دقیق
قفل‌گذاری روی چند واحد قفل شدنی (قفل‌گذاری چند سطحی)
اسلوب اعلان قصد قفل‌گذاری
تکنیک قفل‌گذاری براساس نظم خاص
پروتکل قفل‌گذاری درختی
پروتکل قفل‌گذاری جنگلی
قفل‌گذاری چند نسخه‌ای
در بخش 3-2-7، قفل چند اسلوبی و در بخش 3-2-8، 2PL مبنایی که اساس کار این پایان‌نامه هستند به طور مفصل توضیح داده خواهند شد و در مورد سایر تکنیک‌های قفل‌گذاری به معرفی آن‌ها به طور مختصر بسنده می‌شود.
تعریف قفل
قفل را از دو دیدگاه می‌توان بررسی کرد. در سطح انتزاعی، قفل امتیاز دستیابی به یک واحد داده است که توسط زیرسیستم قفل‌گذاری به یک تراکنش داده می‌شود و یا از آن بازپس گرفته می‌شود. در سطح پیاده‌سازی، قفل متغیری وابسته به یک واحد داده است و نشان‌دهنده‌ی وضع آن واحد داده نسبت به عمل قابل انجام روی آن است.
اندازه‌های واحد قفل‌شدنی
واحدی قفل می‌شود که دستیابی به آن کنترل شود. وجود چندین اندازه برای واحد قفل شدنی متناسب با ماهیت تراکنش، باعث افزایش بهره‌وری می‌شود.
اندازه‌های واحد قفل شدنی عبارتند از: فیلد، رکورد، بلاک، باگت.
فایل و پایگاه در مدل رابطه‌ای: صفت، تاپل، چندین تاپل، رابطه، چندین رابطه و کل پایگاه. لازم به ذکر است که اندازه واحد قفل شدنی قابل ارتقا است مثلاً ارتقا قفل از تاپل به رابطه.
برای سه حالت بیان شده در زیر بهتر است که اندازه قفل کوچکتر باشد.
هرچه که تراکنش نیاز به دسترسی به بخش کوچکتری را داشته باشد.
مدت قفل‌گذاری زیادتر باشد.
پایگاه بزرگ و تعداد کاربران زیادتر باشد.
کوچک یا بزرگ بودن اندازه‌ی واحد قفل‌شدنی (ریز بودن واحد قفل‌پذیر) هر یک مزایا و معایب خاصی دارد که برخی از آن‌ها در جدول 3-1، آمده است.
جدول 3-1- مزایا و معایب اندازه‌ی واحد قفل‌شدنی
فاکتور اندازه واحد قفل‌شدنی
بزرگ کوچک
تعداد واحد قفل شدنی کم زیاد
اندازه جدول قفل‌ها کوچک بزرگ
حافظه مورد نیاز برای جدول قفل‌ها کم زیاد
سربار سیستم پایین بالا
احتمال تداخل تراکنش‌ها بالا پایین
میزان همروندی پایین بالا
ساختار قفل
ساختار قفل نوعی رکورد است که فیلدهای آن عبارتند از:
کلید یا شناسه‌ای برای واحد قفل‌شدنی
نوع قفل
مقدار قفل
شناسه تراکنش (TID)

متن کامل در سایت امید فایل 

البته در بعضی شرایط ممکن است تعداد فیلدها کمتر یا بیشتر شود. مثلاً در قفل ‌دوگانی، تعداد فیلدها کمتر است.
مثالی برای لزوم قفل‌گذاری
فرض کنیدA تعداد صندلی‌های یک پرواز باشد و برنامهP به صورت زیر باشد.
R(A);
A=A+1;
W(A);
این کد به این صورت عمل می‌کند که ابتدا تعداد صندلی‌های پُر را می‌خواند. سپس یک صندلی دیگر رزرو می‌شود، در نهایت این تغییر در پایگاه داده ذخیره می‌گردد. اگر تراکنش‌های T1 و T2 که در جدول 3-2، نمایش داده شده‌اند دو اجرای این برنامه باشند، مقادیر Aدر پایگاه داده و در ناحیه‌ی کاری دو تراکنش، مانند جدول 3-3، خواهد بود.
جدول 3-2- نمایش لزوم قفل‌گذاری
T2 T1
R(A)
R(A) A=A+1
A=A+1 W(A) W(A)
جدول 3-3- نمایش ناحیه کاری
A in DB T2 T1
5 5
5 5 5
5 5 6
5 6 6
6 6 6
6 6 6
با توجه به اطلاعات موجود در جدول 3-2 و 3-3، مشاهده می‌شود که دو تراکنش به طور همروند درخواست رزرو کردن صندلی را داشتند. در نهایت و بعد از اجرای همروند باید دو صندلی رزرو می‌شد. اما به دلیل قفل‌گذاری نکردن، فقط یک صندلی اضافه شد و تعداد صندلی‌های رزرو شده بعد از انجام شدن هر دو تراکنش از پنج به شش تغییر یافت. در حالی که باید در نهایت به مقدار هفت می‌رسید.
مدیر قفل و مراحل انجام شده برای قفل‌گذاری
جدول قفل‌ها نوعی جدول درهم است و مدیر قفل، تابع درهم‌ساز را روی شناسه‌ی واحدِ داده‌ای قفل‌شدنی اعمال می‌کند. در شکل 3-1، عملیات مدیر قفل و مدیر تراکنش را مشاهده می‌نمایید.

شکل 3-1- عملیات مدیر قفل و مدیر تراکنش
نحوه در اختیار قرار دادن قفل توسط مدیر قفل
به دو شیوه قفل توسط مدیر قفل به درخواست کننده‌ها داده می‌شود:
قفل‌گذاری پویا: بر اساس درخواست تراکنش عمل می‌کند.
قفل‌گذاری ایستا: قبل از شروع تراکنش تمام قفل‌ها دریافت می‌شود و لازمه آن شناسایی تمام قفل‌ها قبل از اجراست.
توجه: چفت: نوعی قفل است که برای زمان کوتاهی گذاشته می‌شود. مثلاً چفت گذاشتن روی صفحه‌ای که قرار است از بافر به دیسک منتقل شود.
قفل چند اسلوبی
قفل اشتراکی (S) یا قفل خواندن: اگر تراکنشی روی داده‌ی D قفل S بگذارد سایر تراکنش‌ها هم می‌توانند روی D قفل S بگذارند یعنی آن را بخوانند و به D دسترسی داشته باشند.
قفل انحصاری (X) یا قفل نوشتن: اگر تراکنشی روی داده‌ی D قفل X بگذارد منحصراً همان تراکنش می‌تواند D را بنویسد و سایر تراکنش‌ها نمی‌توانند روی D قفل بگذارند.
ماتریس همایندی یا سازگاری قفل‌های چند اسلوبی
در جدول 3-4 و 3-5، ماتریس سازگاری قفل‌های چند اسلوبی مشاهده می‌شود.
جدول 3-4- ماتریس همایندی
X S
X N N
S N Y
جدول 3-5- سازگاری قفل‌های چند اسلوبی
وضعیت داده D عملیات
قفل برای خواندن Lock-S(D) یا Rlock(D)
قفل برای نوشتن Lock-X(D) یاWlock(D)
قفل‌گشایی شده Unlock(D)
پروتکل قفل چند اسلوبی برای یک تراکنش
پروتکل مجموعه قواعدی است که باید برای قفل‌گذاری توسط هر تراکنش رعایت شود و توسط مدیر قفل اِعمال می‌شود.
باید قبل از عمل R(D) آن را Rlock یا Wlock کند.
باید قبل از عمل W(D) آن را Wlock کند.
باید بعد از عمل خواندن و نوشتن، عمل Unlock را انجام دهد.
نمی‌تواند دستور Rlock(D) را اجرا کند اگر از قبل، یک قفل X روی داده‌ی D داشته باشد.
نمی‌تواند دستور Wlock(D) را اجرا کند اگر از قبل، یک قفل S یا X روی داده‌ی D داشته باشد.
نمی‌تواند دستور Unlock(D) را اجرا کند مگر اینکه از قبل، یک قفل S یا X روی داده‌ی D داشته باشد.
تغییر قفل
تقویت: تغییر قفل از S به X: یعنی اگر T، درخواست Rlock(D) اجرا کند و تنها تراکشی باشد که این دستور را اجرا می‌کند در صورت لزوم می‌تواند درخواست کند تا قفل S به X تبدیل شود. توجه شود که تقویت قفل، در صورتی که بیش از یک تراکنش روی داده‌ای قفل اشتراکی داشته باشند، باعث بروز بن‌بست می‌شود. نود و هفت درصد بن‌بست‌ها در پایگاه داده ناشی از تکنیک تقویت قفل است. در بخش 3-3 به طور کامل در مورد بن‌بست توضیح داده خواهد شد.
تضعیف: تغییر قفل از X به S را تضعیف قفل می‌گویند.
قفل چند اسلوبی و توالی‌پذیری
نکته بسیار مهم در مبحث قفل چند اسلوبی این است که این روش قفل‌گذاری، توالی‌پذیری طرح اجرا را تضمین نمی‌کند. دلیل عدم تضمین این است که تراکنش، داده تحت قفل را پیش از موعد و در واقع به طور پیشرس، قفل‌گشایی می‌کند. توجه شود که به طور کلی یک تراکنش تا هر زمان که به یک فقره داده نیاز داشته باشد، می‌تواند قفل را روی آن نگه دارد و همواره مطلوب نیست که بلافاصله پس از آخرین دستیابی به داده، قفل‌گشایی انجام شود، زیرا ممکن است توالی‌پذیری طرح اجرا تأمین نشود.
خصوصیات قفل چند اسلوبی
توالی‌پذیری طرح اجرا را تضمین نمی‌کند.
امکان بروز بن‌بست وجود دارد.
تکنیک قفل‌گذاری دو مرحله‌ای مبنایی
برای رفع مشکل عدم توالی‌پذیری قفل‌گذاری چند اسلوبی، تکنیک قفل‌گذاری دو مرحله‌ای به کار برده می‌شود. انواع تکنیک‌های قفل‌گذاری دو مرحله‌ای در بخش 3-2 نام برده شده‌اند. یکی از تکنیک‌های قفل‌گذاری دو مرحله‌ای، تکنیک قفل‌گذاری دو مرحله‌ای مبنایی است.
در تکنیک قفل‌گذاری دو مرحله‌ای مبنایی، قفل‌گذاری روی داده‌ها به تدریج که نیاز به دستیابی به آن‌ها پیش می‌آید صورت می‌گیرد و قفل‌گشایی از آن‌ها پس از دریافت تمام قفل‌های تراکنش رخ خواهد داد.
مراحل این تکنیک
قفل‌گذاری یا بسط: فقط می‌تواند داده را قفل کند.
قفل‌گشایی یا قبض: فقط می‌تواند داده را قفل‌گشایی کند.
توجه: در این تکنیک پس از برداشتن قفل، حق قفل مجدد وجود ندارد.
قضیه: پروتکل 2PL توالی‌پذیری تعارضی را تضمین می‌کند و نیازی به آزمون توالی‌پذیری نیست. (این موضوع اثبات شده است و یک قضیه‌ی مهم می‌باشد.)
لحظه یا نقطه قفل: لحظه درست قبل از برداشتن اولین قفل را لحظه یا نقطه قفل می‌گویند. لازم به ذکر است که Unlock الزاماً آخرین دستور تراکنش نیست. در شکل 3-2، پروتکل 2PL و لحظه قفل را مشاهده می‌نمایید.
لحظه قفل
آغاز
بسط
قبض
زمان
پایان
قفل
لحظه قفل
آغاز
بسط
قبض
زمان
پایان
قفل

شکل 3-2- پروتکل 2PL و لحظه قفل
مشکلات تداخل کنترل نشده
نتیجه از دست رفته: مشکل نتیجه از دست رفته زمانی رخ می‌دهد که تراکنشی، بلافاصله بعد از تراکنش دیگری که مقداری را برای داده‌ای نوشته، مقدار جدیدی را برای همان داده بنویسد.
خواندن داده ناجور: داده ناجور داده‌ای است که توسط تراکنشی که هنوز به مرحله تثبیت نرسیده، نوشته شده باشد. نحوه‌ی ایجاد داده ناجور به این صورت است که تراکنشی مثل T2 مقدار موقتِ به‌هنگام درآمده توسط تراکنشی مثل T1 را بخواند. حال اگر تراکنش T1 دچار نقص شود آنگاه تراکنش T2 داده ناجور خوانده است. به مشکل خواندن داده ناجور، مشکل وابستگی به تراکنش تثبیت نشده، نیز می‌گویند.
تحلیل ناسازگار: به مشکل تحلیل ناسازگار، مشکل حاصل جمع نادرست، نیز می‌گویند. زمان بروز مشکل، زمانی است که تراکنش T1 دو مقدار داده‌ی D1 و D2 را به‌هنگام می‌کند و تراکنش T2 یکی از این داده‌ها مثلاً D1 را پس از به‌هنگام‌سازی می‌خواند و مقدار دیگری مثلاً D2 را پیش از به‌هنگام‌سازی می‌خواند.
خواندن تکرار نشدنی: به مشکل خواندن تکرار نشدنی، مشکل فازی، هم گفته می‌شود. زمان بروز مشکل زمانی است که تراکنشی مثل T1 بخواهد داده‌ی D1 را دوباره بخواند، اما داده‌ی D1 توسط تراکنش T2 به‌هنگام شده و نتیجه عمل آن تثبیت گردیده لذا تراکنش T1 دیگر نمی‌تواند مثل قبل داده‌ی D1 را بخواند.
خصوصیات و مشکلات 2PL مبنایی
تضعیف همروندی: فرض کنید تراکنش T روی داده‌ی D1 قفل دارد. اگر تراکنش T درخواست قفل روی داده‌ی D2 راداشته باشد، نمی‌تواند قفل را از روی داده‌ی D1 بردارد، حتی اگر کارش با داده‌ی D1 تمام شده باشد. به عبارت دیگر، اگر تراکنش دیگری به D1 نیاز داشته باشد باید منتظر بماند، حتی اگر تراکنش T کارش با داده‌ی D1 تمام شده باشد. در نتیجه، پردازشِ تراکنش، با کارایی بالا، در این روش وجود ندارد.
طرد تسلسلی: طرد تسلسلی زمانی رخ می‌دهد که اگر یک تراکنش طرد شود، سلسله‌ای از تراکنش‌های دیگر هم طرد شوند. مشکل طرد تسلسلی نامطلوب بوده و در صورت بروز، برای سیستم بیشکاری دارد.
بن‌بست: مشکل بن‌بست زمانی رخ می‌دهد که حداقل دو تراکنش منتظرند تا دیگری از داده مورد نیاز، قفل بردارد. اگر تراکنشی دچار بن‌بست شود مرتباً به عنوان قربانی انتخاب شده و طرد می‌شود و هرگز اجرای آن تمام نمی‌شود. در مورد بن‌بست در بخش 3-3، به طور کامل توضیح خواهیم داد و برای رفع مشکل بن‌بست، در بخش‌های 3-3-2-1 و 3-3-2-2 به معرفی دو الگوریتم WD و WW خواهیم پرداخت.
محرومیت: محرومیت زمانی رخ می‌دهد که تراکنش برای مدت نامحدودی نتواند اجرا شود ولی تراکنش‌های دیگر به طور عادی اجرا شوند و اولویت اجرا به سایر تراکنش‌ها داده شود و تراکنش محروم نتواند قفلی را از سیستم دریافت نماید.
تغییر قفل در پروتکل 2PL
در مرحله بسط، تقویت و در مرحله قبض، تضعیف قفل را داریم. لازم به ذکر است که این امکان وجود دارد که تراکنشی که درخواست تقویت قفل دارد ناچار به انتظار باشد چرا که ممکن است داده مورد نظرش توسط تراکنش دیگری قفل اشتراکی شده باشد.
تأثیرعملیات درج در کنترل همروندی
عمل درج با عملیات حذف، خواندن و نوشتن تعارض دارد. با 2PL، اگر تراکنش Ti عمل درج D را انجام دهد، به Ti روی داده درج شده یک قفل انحصاری داده می‌شود.
تأثیرعملیات حذف در کنترل همروندی
اگر Ii=DE(D) یک دستورالعمل برای حذف داده D باشد. آنگاه یکی از سه حالت کلی زیر رخ خواهد داد.
اگر Ij=R(D) یا Ij=W(D) باشد یعنی Ij دستوری برای خواندن یا نوشتن داده D باشد؛ در این صورت Ii و Ij تعارض دارند. اگر Ii قبل از Ij بیاید، در تراکنش Tj اشتباه منطقی بروز می‌کند. اگر Ij قبل از Ii بیاید، تراکنش Ti می‌تواند عمل W(D) یا R(D) را با موفقیت انجام دهد.
اگر Ij=DE(D) باشد یعنی Ij یک دستورالعمل برای حذف D باشد؛ در این صورت Ii و Ij تعارض دارند. اگر Ii قبل از Ij بیاید، در Tj اشتباه منطقی بروز می‌کند. اگر Ij قبل از Ii بیاید، در Ti اشتباه منطقی رخ می‌دهد.
اگر Ij=IT(D) باشد یعنی Ij یک دستورالعمل برای درج داده D باشد؛ در این صورت Ii و Ij تعارض دارند. فرض می‌کنیم داده D قبل از اجرای Ii و Ij وجود نداشته باشد، اگر Ii قبل از Ij بیاید، در Tj اشتباه منطقی بروز می‌کند. اگر Ij قبل ازIi بیاید، اشتباهی پیش نمی‌آید.
اگر از 2PL استفاده شود، قبل از انجام عمل حذف D، یک قفل انحصاری روی D لازم است.
بن‌بست
در قفل‌گذاری، به میزان چشمگیری خطر بروز بن‌بست وجود دارد. بن‌بست حالتی است که در آن حداقل دو تراکنش منتظر هستند تا فقره داده‌ای را قفل را کنند که دیگری روی آن قفل ناهمایند دارد و هنوز قفل‌گشایی نکرده است. در شکل 3-3، نمونه‌ای از نحوه رخ دادن بن‌بست را مشاهده می‌نمایید. در این شکل مشاهده می‌شود که تراکنش T1 بر روی داده D1 قفل X دارد. این تراکنش در خواست قفل X بر روی داده D2 را دارد اما نمی‌تواند آن را دریافت کند و به حالت انتظار می‌رود، زیرا تراکنش T2 بر روی D2 قفل دارد. از سمت دیگر تراکنش T2 نیز به حالت انتظار رفته است، زیرا درخواست قفل X بر روی داده D1 را دارد که در اختیار T1 است. به این ترتیب هردو تراکنش منتظر یکدیگر هستند و در حالت انتظار رفته‌اند.
T1
T2
زمان
LOCK-X(D1)
LOCK-X(D2)
LOCK-X(D2)
LOCK-X(D1)
WAIT
WAIT
T1
T2
زمان
LOCK-X(D1)
LOCK-X(D2)
LOCK-X(D2)
LOCK-X(D1)
WAIT
WAIT

شکل 3-3- نمونه‌ای از نحوه رخ دادن بن‌بست

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *