انواع روش‌های پیاده‌سازی و مدل‌سازی الگوریتم‌های کنترل همروندی
برای ارزیابی الگوریتم‌های کنترل همروندی اولین نکته‌ای که باید مد نظر گرفته شود، شیوه‌ی نمایش الگوریتم است. شیوه‌ی نمایش الگوریتم می‌تواند از راه‌های زیر باشد.

( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

• • پیاده‌سازی در مقیاس کوچک

• • مدل‌سازی و شبیه‌سازی: مدل‌سازی را می‌توان با ابزارهای متفاوتی انجام داد. ابزارهایی از جمله:

• • مدل مارکف

• • شبکه‌های پتری^[۱۴]

پیاده‌سازی در مقیاس کوچک
در زیر بعضی از نمونه‌های پیاده‌سازی الگوریتم در مقیاس کوچک آورده شده است.
۱- یک مکانیزم بر اساس قفل دو مرحله‌ای از طریق پیاده‌سازی در مقیاس کوچکی بررسی شده است (Al-Jumah, et al., 2000). قفل دو مرحله‌ای، یک مکانیزم کنترل همروندی است که در بیشتر سیستم‌های پایگاه داده‌های تجاری مورد استفاده قرار می‌گیرد. در مکانیزم قفل دو مرحله‌ای، یک تراکنش برای دسترسی به یک آیتم داده، باید قفل مناسب (خواندن و یا نوشتن) را بر روی آیتم داده قرار دهد. قرار دادن قفل با صدور یک درخواست قفل صورت می‌پذیرد. لازم به ذکر است که روشی که درخواست قفل تراکنش‌ها را تنظیم می‌کند و بررسی می‌کند که قفل به کدام درخواست داده شود، قطعاً بر عملکرد و بازدهی سیستم تأثیر می‌گذارد. در (Al-Jumah, et al., 2000)، یک مدل کلی برای پردازش تراکنش ارائه شده است. در این مدل، یک تراکنش از چند مرحله تشکیل شده است و در هر مرحله تراکنش می‌تواند درخواست قفل کردنِ یک یا تعداد بیشتری از آیتم‌های داده را داشته باشد.
۲- چند مورد از تکنیک‌های کنترل همروندی سیستم مدیریت پایگاه داده‌ها که به طور معمول استفاده می‌شوند کمی بهبود داده شده‌اند و از طریق پیاده‌سازی در مقیاس کوچک، بررسی شده‌اند (Zhen, and Li, 2009). در سیستم پایگاه داده‌ی بلادرنگ، داده‌ها از طریق خوانده شدن، نوشته شدن و اجرای همروند تراکنش‌های بلادرنگ می‌توانند سازگاری پایگاه داده را تضعیف کنند. الگوریتم کنترل همروندی باید برای اطمینان از توالی‌پذیریِ زمان‌بندی تراکنش‌ها و سیستم پایگاه داده‌ی بلادرنگ و همچنین برای حفظ سازگاری داده‌ها مورد استفاده قرار گیرد. در واقع در (Zhen, and Li, 2009) برخی پروتکل‌های کنترل همروندیِ پایگاه داده‌ی بلادرنگ سنتی، بهبود داده شده‌اند.
۳- (Shu, and Young, 2002) نیز یکی دیگر از مواردی است که از طریق پیاده‌سازی در یک مقیاس کوچک‌، سیستم‌های بلادرنگ سخت را بررسی کرده است.
۴- یک الگوریتم امن جدید و پیاده‌سازی یک الگوریتم غیر امن به همراه عملکرد آن در (Hedayati, et al., 2010) مورد بررسی قرار گرفته است. به عبارت دیگر یک الگوریتم همروندی خوش‌بینانه امن جدید برای پایگاه داده‌های بلادرنگ امن پیشنهاد شده است. این الگوریتم و یک الگوریتم غیر امن پیاده‌سازی شده‌اند و عملکرد و بازدهی‌شان ارزیابی گردیده است. همچنین معیارهایی برای اندازه‌گیری امنیت در سیستم‌های پایگاه داده‌ی بلادرنگ معرفی شده است. نتایج نشان می‌دهد که الگوریتم پیشنهادی در آنجا، از لحاظ امنیتی بودن و به موقع بودن به طور نسبتاً خوبی در مقایسه با الگوریتم غیر امن کارش را انجام می‌دهد. اما پیاده‌سازی الگوریتم‌ها برای ارزیابی با دشواری زیادی انجام شده است.
۵- (Lee, 1999) به بررسی توالی‌پذیری روش کنترل همروندی خوش‌بینانه می‌پردازد؛ این کار را از طریق پیاده‌سازی آن انجام می‌دهد. با وجود این واقعیت که پیاده‌سازی تراکنش‌ها در اکثر سیستم‌های مدیریت پایگاه داده‌های تجاری، با بهره گرفتن از قفل برای کنترل همروندی صورت می‌گیرد، کنترل همروندی خوش‌بینانه نیز توجه بسیاری به دست آورده است. کنترل همروندی خوش‌بینانه در انواع جدیدی از برنامه‌های کاربردی داده‌های فشرده، مانند طراحی به کمک کامپیوتر و مهندسی نرم‌افزار به کمک کامپیوتر استفاده شده است. در آن مقاله به توصیف و تجزیه و تحلیل یک الگوریتم کنترل همروندی جدید اشاره می‌شود که به عنوان یک نوع جدید از یک الگوریتم کنترل همروندی خوش‌بینانه، توالی‌پذیری را ایجاد می‌کند. این الگوریتم، از بسیاری الگوریتم‌های خوش‌بینانه بهتر عمل می‌کند. ارزیابی مدل و مقایسه آن با برخی مدل‌های دیگری با کمی دشواری انجام شده است و به اجبار، ارزیابی برای حجم کاری خاصی انجام شده است (Lee, 1999).
۶- یک الگوریتم جدید برای کنترل همروندی در سیستم‌های پایگاه داده توزیع شده از طریق پیاده‌سازی در مقیاس کوچک ارائه شده است (Mousavi, et al., 2013). بررسی‌ها روی موارد و پارامترهای خاصی صورت گرفته است. تعداد پیام‌های رد و بدل شده بین گره‌ها در الگوریتم‌ها، به دلیل دشواری‌هایی که در پیاده‌سازی در مقیاس کوچک وجود دارد به طور جداگانه مشخص شده و ثابت مانده است. سپس زمان اجرای الگوریتم‌ها در ۲۰ تکرار با تعداد گره‌های متفاوت ( در ابتدا ۵ گره، سپس ۱۵ و ۲۰ گره) بررسی شده است.
مدل‌سازی و شبیه‌سازی توسط مدل مارکف
در اینجا نمونه‌ای از مدل‌سازی توسط مدل مارکف بیان شده است. قفل کردن و زمان‌مهر دو روش برای کنترل همروندی در سیستم‌های پایگاه داده هستند. اگرچه مطالعاتی در زمینه‌ی عملکرد، بازدهی و تحلیل تکنیک قفل در پیشینه‌ تحقیق آن وجود دارد، اما به نظر می‌رسد که تا حد زیادی، مطالعه عملکرد، بازدهی و تحلیل الگوریتم‌های کنترل همروندی بر پایه زمان‌مهر، ناشناخته باقی مانده است. از آنجا که کلاس بزرگی از الگوریتم‌های کنترل همروندی با بهره گرفتن از زمان‌مهر وجود دارد، یک نیاز قوی به مطالعه عملکرد، بازده و تحلیل کردن این الگوریتم حس می‌شود. (Singhal, 1991) نیز به تجزیه و تحلیل عملکرد و بازده الگوریتم مرتب‌سازی زمان‌مهر پایه‌ای، برای کنترل همروندی در سیستم‌های پایگاه داده پرداخته است. در آن مقاله فرض شده است که یک تراکنش، وضعیت متوسطِ سیستم و تمام تراکنش‌ها را نشان می‌دهند و با عملکرد متوسط در حالت پایدار، اجازه می‌دهد که به جای توزیع‌های احتمال‌ها با میانگین کار کنیم. بنابراین، روش مورد استفاده در تجزیه و تحلیل تقریبی است و روش با مثال عددی نشان داده شده است. مجموعه‌ای از معیارهای اندازه گیری عملکرد و بازده برای مقادیر مختلفی از پارامترهای مدل مطرح شده است. در آنجا بیان شده است که نتایج حاصل از تجزیه و تحلیل تا حدودی مانند یک مطالعه شبیه‌سازی معتبر، مورد تأیید است. با اینکه این روش تقریبی است اما تکنیک‌های مشابه به آنچه در فوق بیان شد نیز توسط محققان دیگر استفاده شده و به مطالعه عملکرد و بازده الگوریتم قفل پرداخته است.
مدل‌سازی و شبیه‌سازی توسط شبکه‌های پتری
یکی از ابزارهای شبیه‌سازی الگوریتم‌های کنترل همروندی شبکه‌های پتری هستند. به طور کلی شبکه‌های پتری ابزار امیدوار کننده و بسیار مفیدی برای مدل‌سازی و تحلیل کردن اطلاعات سیستم‌هایی هستند که عملیات همروند، همزمان، ناهمزمان، موازی و یا توزیع شده دارند (Han, et al., 2004). شبکه‌های پتری در اصل برای مدل‌سازی ناهمزمان و جریان کنترل همروندی طراحی شده‌اند و (Mikkilineni, Chow, and Su, 1988) این موضوع را به بهترین وجه نشان می‌دهد. در زیر نمونه‌های مختلفی از کاربرد انواع شبکه‌های پتری، در زمینه‌ی شبیه‌سازی الگوریتم‌های کنترل همروندی را مشاهده می‌نمایید.
۱- یک مدل شبکه پتری زمانی، برای انجام تراکنش‌های همروندِ سیستم پایگاه داده‌ی مبتنی بر وب ارائه شده است (Han, et al., 2004). این مدل بدون بن‌بست است، توالی‌پذیر است، از راه‌اندازی‌های مجدد بی‌فایده و انتظارهای بیهوده جلوگیری می‌کند. در آن مقاله مدل‌های شبکه پتریِ مربوط به تمام سایت‌ها، به یک مدل کاهش داده شده است. یعنی از طریق ترکیب و هماهنگ‌سازیِ مدل‌های مختلف، فقط یک مدل شبکه پتری برای انجام تراکنش‌های همروند جهانی ایجاد شده است. همچنین مقیاس مدل شبکه پتری برای هر سایت با بهره گرفتن از تکنیک‌های خاصی، قبل از ترکیب کردن، تا حد زیادی کاهش داده شده است. این روش مشکل زیاد بودنِ تعداد وضعیت‌ها و تجزیه و تحلیل‌های شبکه‌های پتری را حل می‌کند. در آخر نیز، شرط کافی و لازم برای بررسی اینکه آیا در نهایت، در کلِ سیستم بن‌بست وجود دارد یا نه، ارائه شده است.
۲- تئوری بیان شده در (Chen, Wang and Wang, 2011) از طریق شبکه پتری اثبات شده است و به کمک شبکه پتری نشان داده شده است که پروتکل پیشنهادی امکان‌پذیر و مؤثر است و می‌تواند نیازهای تراکنش بلادرنگ را برطرف کند. در نهایت، از طریق نظریه شبکه پتری درستی این موضوع ثابت شده است. در واقع در (Chen, et al., 2011) بر اساس ویژگی‌های سیستم پایگاه داده‌ی بلادرنگ، یک پروتکل کنترل همروندی برای پایگاه داده‌های بلادرنگ ارائه شده است. براساس آزمایش انجام شده در آن مقاله نشان داده می‌شود که پروتکل کنترل همروندی پایگاه داده‌ی بلادرنگ می‌تواند کارایی پردازش تراکنش‌های سیستم پایگاه داده‌ی بلادرنگ را افزایش دهد. بررسی کارایی و عملکرد مدل از طریق شبکه پتری اثبات شده است.
۳- نتایج حاصل از مطالعه و ارزیابی عملکرد و بازدهی الگوریتم‌های کنترل همروندی در پایگاه داده توزیع شده در (Sarkar, and Nabendu, 2009) گزارش شده است. در واقع یک مدل‌سازی جایگزین و روش ارزیابی عملکرد و بازدهی برای الگوریتم‌های کنترل همروندی پایگاه داده توزیع شده ارائه شده است که در بررسی بیشتر تنظیمات توزیع شده به طور کلی مفید است. پتری ویژگی‌هایی دارد که می‌تواند به عنوان یک ابزار ارزیابی عملکرد و بازدهی مورد استفاده قرار گیرد. اعتبارسنجی برخی از نمونه‌های نتایج به دست آمده از شبیه‌سازی پتری، با تجزیه و تحلیل صف مورد مقایسه قرار گرفته است. ارزیابی عملکرد و بازدهی در پتری، تحت سناریوهای واقع بینانه‌تر است. زیرا مفروضات گزارش شده در روش تجزیه و تحلیل از طریق صف به شدت محدود شده هستند، با این حال، لازم به ذکر است که این فرضیات معمولاً توسط بسیاری از مطالعات عملکرد و بازدهی در این حوزه ایجاد شده‌اند و مورد استفاده قرار می‌گیرند.
۴- ویژگی‌های همزمان و ناهمزمانِ شبکه‌های پتری به خوبی با همان ویژگی‌های ذاتی در معماری پردازش همروند در پایگاه داده‌ها مطابق است (Mikkilineni, et al., 1988). نتایج عملکرد و بازدهی حاصل از شبیه‌سازی انجام شده با پتری، در واقع عملکرد دقیق سیستم واقعی را ارائه می‌دهد. با این حال مدل‌سازی عملکرد و بازده عملیات پایگاه داده‌ای که در آن مقاله ارائه شده است نتوانسته به طور کامل از تمام قابلیت‌های مدل‌های شبکه پتری استفاده کند.
۵- مدل‌سازی پروتکل تثبیت دو مرحله‌ای برای مدیریت تراکنش در محیط توزیع شده با بهره گرفتن از شبکه پتری زمانی، مورد مطالعه قرار گرفته است (Sarkar, and Nabendu, 2009).
۶- کنترل همروندی تراکنش‌های پایگاه داده با بهره گرفتن از شبکه پتری معمولی بر اساس پروتکل قفل دو مرحله‌ای، صورت گرفته است (Jie, Fengying, and Huijiao, 2010). به عبارت دیگر خصوصیات رسمی و مشخصات صوری برای کنترل همروندی تراکنش‌های پایگاه داده با بهره گرفتن از شبکه پتری معمولی بر اساس پروتکل قفل دو مرحله‌ای مورد مطالعه قرار گرفته است و این اطمینان را حاصل می‌کند که توالی‌پذیری همروندی زمان‌بندها بررسی شده است.
۷- یک پروتکل براساس پروتکل قفل دو مرحله‌ای برای پایگاه داده توزیع شده با بهره گرفتن از شبکه پتری رنگی مدل شده است (Voss, 1997).
۸- روش‌های کپی اصلی و اولیه با بهره گرفتن از پتری سطح بالا که همان شبکه پتری رنگی است مدل شده‌اند (Seatzu, et al., 2013).
۹- یک مدل جدید از کنترل همروندی برای پایگاه داده توزیع شده، بر اساس پروتکل قفل دو مرحله‌ای با بهره گرفتن از شبکه پتری رنگی مدل شده است (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).