پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری

word
120
2 MB
31023
1393
کارشناسی ارشد
قیمت: ۱۲,۰۰۰ تومان
دانلود فایل
  • خلاصه
  • فهرست و منابع
  • خلاصه پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری

    پایان‌نامه کارشناسی ارشد دانشکده فنی و مهندسی

    گروه کامپیوتر

    چکیده:

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

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

    آزمایش‌ها چندین بار تکرار و نتایج میانگین‌گیری شدند. با مقایسه و انجام بررسی‌ها، این نتیجه به دست آمد که در حالت کلی الگوریتم زخمی کردن-منتظر گذاشتن نسبت به دو الگوریتم دیگر زمان اجرای بهتری دارد. الگوریتم منتظر گذاشتن-میراندن از نظر زمان اجرا با اختلاف زیادی در سطح بدتری نسبت به دو الگوریتم دیگر قرار دارد و الگوریتم قفل‌گذاری دو مرحله‌ای مبنایی به دلیل امکان رخ دادن بن‌بست، مشکلات فراوانی دارد.

     

    واژه‌های کلیدی: کنترل همروندی، شبکه پتری رنگی، ارزیابی، قفل‌گذاری دو مرحله‌ای مبنایی، زخمی کردن-منتظر گذاشتن، منتظر گذاشتن-میراندن، بن‌بست، پیش‌گیری از بن‌بست

    فصل اول

     

     

    1-1-        مقدمه

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

     

    پارامتر الگوریتم(ها) پیاده‌سازی یا مدل‌سازی مرجع
    تعداد تراکنش‌های وارد شونده به سیستم مقایسه یک الگوریتم امن و یک الگوریتم غیر امن برای پایگاه داده‌های بلادرنگ پیاده‌سازی در مقیاس کوچک (Hedayati, Kamali, Shakerian and Rahmani, 2010)
    اندازه هر تراکنش (تعداد دستورات هر تراکنش) الگوریتم مرتب‌ سازی زمان‌مهر پایه‌ای مدل‌سازی توسط مدل مارکف (Singhal, 1991) و
    (روحانی رانکوهی، 1386)
    تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها یک مکانیزم بر اساس قفل دو مرحله‌ای پیاده‌سازی در مقیاس کوچک (Al-Jumah, Hossam, and El-Sharkawi, 2000)
    تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک یک مکانیزم بر اساس قفل دو مرحله‌ای پیاده‌سازی در مقیاس کوچک (Al-Jumah, et al., 2000)

     

     

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

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

     

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

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

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

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

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

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

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

    فصل دوم

     

    پیشینه‌ی تحقیق

    مقدمه

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

     

    2-1-        اهمیت الگوریتم‌های کنترل همروندی پایگاه داده‌ها

    مدت زمان زیادی است که حفظ ثبات و سازگاری داده‌های به اشتراک گذاشته شده در سیستم پایگاه داده‌ها‌، مورد مطالعه قرار گرفته است (Shu, and Young, 2002). مطالعاتی که در زمینه‌ی ارزیابی الگوریتم‌های کنترل همروندی پایگاه داده‌ها صورت می‌گیرند، نه تنها در پایگاه داده‌های معمولی و پایگاه داده‌های بلادرنگ[2]، بلکه در سیستم پایگاه داده‌ی توزیع شده‌، پایگاه داده مبتنی بر وب، سیستم‌های بلادرنگ سخت[3] و مانند آن‌ها نیز کاربردهای اساسی دارند. نشان داده شده است که الگوریتم‌های قفل متمرکز و توزیع شده در اغلب مواقع، رفتارهایی مشابه در مواجه شدن با سیستم، مدل و مفروضات مشخص شده‌ انجام می‌دهند (Sarkar, and Nabendu, 2009). همچنین در (Shu, and Young, 2002) پروتکل کنترل همروندی چند نسخه‌ای به گونه‌ای بیان شده است که برای سیستم پایگاه داده متمرکز و توزیع شده مشابه است. تنها برخی موارد جزیی باید در یک محیط توزیع شده، به صورت اضافه‌تر از حالت متمرکز در نظر گرفته شوند. این موارد شامل افزودن تعدادی فیلد محدود است. این فیلدها شامل تخصیص ورژن داده، اطمینان از تثبیت[4] شدن و تجزیه‌ناپذیری[5] است.

     

    2-2-         برخی از انواع پایگاه داده‌ها

    در اینجا لازم است به تعریف جزیی برخی از پایگاه داده‌های نام برده شده در این بخش بپردازیم.

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

    ب) پایگاه داده‌ی توزیع شده‌: در طول سال‌های اخیر، توزیع شدگی به عنوان یک مسئله‌ی مهم برای پایگاه داده‌ها مورد بررسی قرار گرفته است (Ozsu, 1985). این مسئله دلایل منطقی بسیاری مانند توزیع طبیعی سازمان‌ها دارد. پایگاه داده توزیع شده مجموعه‌ای از قطعات مختلف است. به بیان دیگر بیش از یک شبکه از کامپیوترهای متصل، با یکدیگر ارتباط منطقی دارند. در یک پایگاه داده توزیع شده، مجموعه‌ای از داده‌ها می‌توانند در سراسر چندین مکان فیزیکی توزیع شوند. از آنجا که این پایگاه داده به صورت توزیع شده است، کاربران مختلف می‌توانند بدون تداخل با یکدیگر، به آن دسترسی داشته باشند. اهمیت ارزیابی الگوریتم‌های پایه‌ای کنترل همروندی پایگاه داده‌ها در جایی مشخص می‌شود که سیستم مدیریت پایگاه داده‌ها (DBMS)[6] باید همروندی را در پایگاه داده‌ها برقرار کند و به صورت دوره‌ای پایگاه داده‌های پراکنده را همگام‌سازی کند تا مطمئن شود که همه آن‌ها دارای داده‌های سازگار هستند (Mousavi, Naji, and Ebrahimi, 2013). سیستم‌های پایگاه داده توزیع شده (DDBS)[7] در سال‌های اخیر مورد توجه بیشتری قرار گرفته اند. به نظر می‌رسد که این زمینه برای برخی از کارهای تجزیه و تحلیل و مقایسه‌ای آماده است (Sarkar, and Nabendu, 2009) و (Ozsu, 1985).

    ج) پایگاه داده مبتنی بر وب: سیستم پایگاه داده‌ی مبتنی بر وب سیستمی است که هم ویژگی‌های پایگاه داده‌ی توزیع شده و هم ویژگی‌های پایگاه داده‌ی بلادرنگ را دارد. البته، مشکلات کنترل همروندی در پایگاه داده‌ی مبتنی بر وب، پیچیده‌تر و دشوارتر از پایگاه داده‌های توزیع شده معمولی می‌باشد (Han, Jiang, and Luo, 2004).

    Abstract

    The issue of concurrency control in database is very important and vital. Any concurrent transaction should be taken in database management system could lead to conflict. The conflict occurs due to incorrect values in existing database which lead to incompatibility and interference in executed transaction which has been taken. The concurrency control algorithms, to insure the concurrent action many transactions has been designed to work concurrently with a common data. In regard of concurrency control database so many researches have been done that resulted in, that the various algorithms the control of database. Considering that various algorithms in this field and reality are getting increasingly important day by day, In the field of concurrency control algorithms evaluation there are a lot to be done.

    In this thesis, firstly the concurrency control algorithms of Two-Phase Locking in addition to Wound-Wait and Wait-Die techniques which are the part of preventing Deadlock techniques, has been modeled. Since the Colored Petri Net has a great capability and one of the best methods in analyzing the concurrency control mechanism, modeling using Colored Petri and CPN tools software are shown. For better understanding one simple case study has been presented, in which consists of three transactions and two resources. Hence the algorithms mentioned are evaluated. The evaluation is carried out using parameters and criterion such as the number of transactions entering the system, the number of commands, and the number of relevant and irrelevant data between transactions, and the number of relevant data in transactions without irrelevant data, has been taken place.

    The experiments have been repeated several times and the results are averaged. With comparison and examinations this result has been obtained, that in general Wound-Wait algorithm has better time performance in comparison with the other two algorithms. Wait-Die algorithm has worse time performance than the other two algorithms, and the Two Phase Locking algorithm curries a lot of problems due to the probability of Deadlock occurrence.

     

    Keywords: Concurrency Control, Colored Petri Net, Evaluation, Two-Phase Locking, Wound-Wait, Wait-Die, Deadlock, Preventing Deadlock

  • فهرست و منابع پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری

    فهرست:

    فصل اول: مقدمه

    1-1- مقدمه. 2

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

    فصل دوم: پیشینه‌ی تحقیق

    مقدمه. 7

    2-1- اهمیت الگوریتم‌های کنترل همروندی پایگاه داده‌ها 7

    2-2- برخی از انواع پایگاه داده‌ها 8

    2-3- انواع روش‌های پیاده‌سازی و مدل‌سازی الگوریتم‌های کنترل همروندی.. 9

    2-3-1- پیاده‌سازی در مقیاس کوچک... 9

    2-3-2- مدل‌سازی و شبیه‌سازی توسط مدل مارکف... 11

    2-3-3- مدل‌سازی و شبیه‌سازی توسط شبکه‌های پتری.. 12

    2-4- پارامترهای ارزیابی.. 14

    2-4-1- پارامترهای منابع سیستم. 14

    2-4-2- پارامترهای حجم کاری.. 15

    2-5- پارامترها و آزمایش‌های انجام شده 16

    2-6- برخی از مزایا و معایب روش‌های مدل‌سازی و شبیه‌سازی.. 18

    2-7- لزوم انجام تحقیق.. 20

    فصل سوم: تکنیک‌های کنترل همروندی

    مقدمه. 22

    3-1- تکنیک‌های کنترل همروندی و انواع آن‌ها 22

    3-2- تکنیک‌های قفل‌گذاری و انواع آن‌ها 23

    3-2-1- تعریف قفل.. 24

    3-2-2- اندازه‌های واحد قفل‌شدنی.. 24

    3-2-3- ساختار قفل.. 25

    3-2-4- مثالی برای لزوم قفل‌گذاری.. 26

    3-2-5- مدیر قفل و مراحل انجام شده برای قفل‌گذاری.. 27

    3-2-6- نحوه در اختیار قرار دادن قفل توسط مدیر قفل.. 28

    3-2-7- قفل چند اسلوبی.. 28

    3-2-7-1- ماتریس همایندی یا سازگاری قفل‌های چند اسلوبی.. 28

    3-2-7-2- پروتکل قفل چند اسلوبی برای یک تراکنش.... 29

    3-2-7-3- تغییر قفل.. 30

    3-2-7-4- قفل چند اسلوبی و توالی‌پذیری.. 30

    3-2-7-5- خصوصیات قفل چند اسلوبی.. 30

    3-2-8- تکنیک قفل‌گذاری دو مرحله‌ای مبنایی.. 30

    3-2-8-1- مشکلات تداخل کنترل نشده 31

    3-2-8-2- خصوصیات و مشکلات 2PL مبنایی.. 32

    3-2-8-3- تغییر قفل در پروتکل 2PL.. 33

    3-2-8-4- تأثیرعملیات درج در کنترل همروندی.. 33

    3-2-8-5- تأثیرعملیات حذف در کنترل همروندی.. 33

    3-3- بن‌بست... 34

    3-3-1- راه حل‌های مشکل بن‌بست... 35

    3-3-2- تکنیک‌های زمان‌مهر. 36

    3-3-2-1- الگوریتم WD.. 37

    3-3-2-2- الگوریتم WW... 37

    3-3-2-3- خصوصیات الگوریتم WD و WW... 37

    فصل چهارم: شبکه‌های پتری

    مقدمه. 39

    4-1- مختصری در مورد شبکه‌های پتری.. 39

    4-2- تفاوت UML و پتری.. 39

    4-3- تاریخچه شبکه‌های پتری.. 40

    4-4- ویژگی‌های شبکه‌های پتری.. 40

    4-5- اجزای شبکه‌ی پتری.. 40

    4-5-1- تعریف اجزای شبکه‌ی پتری.. 41

    4-5-2- وظایف اجزای شبکه‌ی پتری.. 41

    4-6- تعریف چهارگانه شبکه‌های پتری.. 42

    4-7- گراف شبکه پتری.. 42

    4-8- چند مثال از گراف شبکه پتری.. 43

    4-9- رفتار شبکه‌های پتری.. 43

    4-10- گذار توانا 44

    4-11- مثالی از اجرای یک شبکه پتری.. 44

    4-12- قوانین مربوط به فایر شدن گذار، در شبکه پتری.. 45

    4-13- شبکه‌های پتری به بن‌بست رسیده، زنده و غیر زنده 46

    4-14- انواع شبکه‌های پتری و نحوه‌ی نشانه‌گذاری آن‌ها 47

    4-15- فلوچارت‌ها و شبکه‌های پتری.. 47

    4-16- انواع پتری.. 48

    4-16-1- شبکه پتری رنگی.. 48

    4-16-2- شبکه پتری زمانی.. 49

    4-16-3- شبکه پتری سلسله مراتبی.. 50

    فصل پنجم: نحوه‌ی مدل‌سازی مکانیزم‌های 2PL، WW و WD با پتری رنگی

    مقدمه. 52

    5-1- مختصری در مورد مدل‌سازی مکانیزم‌های 2PL، WW و WD.. 52

    5-1-1- مدل 2PL.. 52

    5-1-2- مدل‌های WW و WD.. 53

    5-2- مجموعه‌های رنگ... 53

    5-2-1- مجموعه‌های رنگ در مدل 2PL.. 53

    5-2-2- مجموعه‌های رنگ در مدل‌های WW و WD.. 54

    5-2-3- توضیحات مجموعه‌های رنگ... 55

    5-3- نشانه‌گذاری اولیه. 58

    5-3-1- نشانه‌گذاری اولیه در مدل 2PL.. 58

    5-3-2- نشانه‌گذاری اولیه در مدل‌های WW و WD.. 59

    5-3-3- توضیحات نشانه‌گذاری اولیه. 59

    5-4- متغیرها 61

    5-4-1- متغیرهای مدل 2PL.. 61

    5-4-2- متغیرهای مدل‌های WW و WD.. 62

    5-5- شرح توابع مدل و عملکردهای آن‌ها 62

    5-5-1- شرح توابع مشترک بین مدل‌های 2PL، WW و WD.. 63

    5-5-2- شرح توابع مدل 2PL.. 63

    5-5-3- شرح توابع مدل‌های WW و WD.. 76

    5-6- اولویت‌های معین شده برای تعیین فایر شدن گذار مورد نظر از بین گذارهای فعال.. 72

    5-7- نحوه‌ی مدل‌سازی‌ها 73

    5-7-1- نحوه مدل‌سازی مدل 2PL.. 73

    5-7-2- نحوه مدل‌سازی مدل‌های WW و WD.. 75

    فصل ششم: ارزیابی مدل‌های 2PL، WW و WD

    مقدمه. 79

    6-1- مختصری در مورد اهمیت ارزیابی پایگاه داده‎ها 79

    6-2- پارامتر تعداد تراکنش‌های وارد شونده به سیستم. 80

    6-2-1- بررسی مدل 2PL.. 80

    6-2-2- بررسی مدل WW.. 80

    6-2-3- بررسی مدل WD.. 81

    6-2-4- مقایسه‌ی مدل‌های 2PL، WW و WD براساس پارامتر تعداد تراکنش‌ها 82

    6-3- پارامتر تعداد دستورات هر تراکنش.... 83

    6-3-1- بررسی مدل 2PL.. 83

    6-3-2- بررسی مدل WW... 84

    6-3-3- بررسی مدل WD.. 85

    6-3-4- مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد دستورات تراکنش‌ها 86

    6-4- پارامتر تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها 88

    6-4-1- بررسی مدل 2PL.. 88

    6-4-2- بررسی مدل WW... 89

    6-4-3- بررسی مدل WD.. 90

    6-4-4- مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد داده‌های مشترک و غیر مشترک تراکنش‌ها 91

    6-5- پارامتر تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک... 92

    6-5-1- بررسی مدل 2PL.. 92

    6-5-2- بررسی مدل WW... 93

    6-5-3- بررسی مدل WD.. 94

    6-5-4- مقایسه مدل‌های 2PL، WW و WD براساس پارامتر تعداد داده‌های مشترک در تراکنش‌هایی بدون داده غیر مشترک... 96

    6-6- نتیجه‌گیری.. 97

    6-7- پیشنهادات.. 100

    مراجع.. 102

     

    منبع:

    مراجع لاتین:

    Al-Jumah, N. B., Hossam, S. H. and El-Sharkawi, M., (2000), Implementation and modeling of two-phase locking concurrency control—a performance study, Information and Software Technology, Vol. 42, No. 4, pp. 257-273.

    Chen, J., Wang, Y. F. and Wang, J. P., (2011), Concurrency control protocol for real-time database and the analysis base on petri net, Advanced Materials Research, Vols. 143-144, pp. 12-17.

    Devillers, R. and Best, E., (1987), Sequential and concurrent bihavior in petri net theory, Theorical computer science, Vol. 55, No. 1, pp. 87-136.

    Gilmore, S., (1997), Programming in standard ML'97: A tutorial introduction, Edinburgh, Laboratory for Foundations of Computer Science the University of Edinburgh.

    Halder, A., (2006), A study of petri nets modeling, analysis and simulation, india, india University Aerospace Engineering.

    Han, Y., Jiang, C. and Luo, X., (2004), A study of concurrency control in web-based distributed real-time database system using extended time petri nets, Parallel Architectures, Algorithms and Networks (ISPAN’04), in Proceedings of the 7th International Symposium on IEEE, pp. 67-72.

    Harper, R., (2001), Programming in standard ML, Pittsburgh United States, Carnegie Mellon University.

    Harper, R., Rothwell, N. and Mitchell, K., (1989), Introduction to standard ML, Pittsburgh United States, School of Computer Science Carnegie Mellon University.

    Hedayati, M, Kamali, S. H., Shakerian, R. and Rahmani, M., (2010), Evaluation of performance concurrency control algorithm for secure firm real-time database systems via simulation model, Networking and Information Technology (ICNIT), International Conference on IEEE, pp. 260-264.

    Jenq, B-C., Twichell, B. C. and Keller, T. W., (1989), Locking performance in a shared nothing parallel database machine, Knowledge and Data Engineering, Transactions on IEEE, Vol. 1, No. 4, pp. 530-543.

    Jensen, K., Kristensen, L. M. and Wells, L., (2010), Coloured petri nets and CPN Tools for modelling and validation of concurrent systems, International Journal on Software Tools for Technology Transfer, Vol. 9, Nos. 3-4, pp 213-254.

    Jie, H., Fengying, L. and Huijiao, W., (2010), Petri net based model for concurrent control of database system, International Conference on Intelligent Computing and Integrated Systems (ICISS), pp. 813-815.

    Lee, J., (1999), Precise serialization for optimistic concurrency control, Data & Knowledge Engineering, Vol. 29, No. 2, pp. 163-178.

    Li, Z. W., Hu, H. and Zhou, M. C., (2004), An algorithm for an optimal set of elementary siphons in petri nets for deadlock control, Systems, Man and Cybernetics, International Conference on IEEE, Vol. 5, pp. 4849 - 4854.

    Mikkilineni, K. P., Chow, Y. C. and Su, S. Y. W., (1988), Petri-net-based modeling and evaluation of pipelined processing of concurrent database queries, Software Engineering, Transactions on IEEE, Vol. 14, No. 11.

    Moreno, R. P. and Villarroel Salcedo, J. S., (2007), Performance evaluation of petri nets execution algorithms, Systems, Man and Cybernetics, International Conference on IEEE, pp. 1400-1407.

    Mousavi, S. M. A., Naji, H. R. and Ebrahimi, A. R., (2013), Optimization of majority protocol for controlling transactions concurrency in distributed databases by multi-agent systems, International Journal of Applied Operational Research, Vol. 3, No. 1, pp. 95-108.

    Murata, T., Petri nets: properties, analysis and applications, in Proceedings of  IEEE, Vol. 77, No. 4, pp. 541-580.

    Ozsu, M. T., (1985), Modeling and analysis of distributed database concurrency control algorithms using an extended petri net formalism, Software Engineering, Transactions on IEEE, Vol. SE-11, No. 10, pp. 1225-1240.

    A-Pashazadeh, S., (2012), Modeling a concurrency control Mechanism in distributed databases using hierarchical colored petri net, International Conference on Information and Computer Applications (ICICA), Singapore, Vol. 24, pp.286-289.

    B-Pashazadeh, S., (2012), Modeling and verification of deadlock potentials of a concurrency control mechanism in distributed databases using hierarchical colored petri net, International Journal of Information and Education Technology (IJIET), Vol. 2, No. 2, pp. 77-82.

    Paulson, L. C., (1996), ML for the working programmer, (2th ed.), NY. USA, Press Cyndicate of the University of Cambridge.

    Sarkar, B. B., and Nabendu, C., (2009), Modeling & analysis of transaction management for distributed database environment using Petri Nets, In Nature & Biologically Inspired Computing (NaBIC), World Congress on IEEE, pp. 918-923.

    Seatzu, C., Cabasino, M. P., and Giua, A., (2013), Introduction to petri nets, Control of Discrete-Event Systems (LNCIS), Vol. 433, pp. 191–211.

    Shu, L. C. and Young, M., (2002), Versioning concurrency control for hard real-time systems, Journal of Systems and Software, Vol. 63, No. 3, pp. 201-218.

    Singhal, M., (1991), Performance analysis of the basic timestamp ordering algorithm via Markov modeling—performance evaluation, Performance Evaluation, Vol. 12, No. 1, pp. 17-41.

    Voss, K., (1997), Prototyping and verifying distributed database systems using executable high-level Petri net models, Systems, Man, and Cybernetics,. Computational Cybernetics and Simulation., International Conference on IEEE, Vol. 4, pp. 3395-3400.

    Yilmaz, B., (2008), Applications of petri nets, Izmir, Graduate School of Engineering and Sciences of˙Izmir Institute of Technology.

    Zhen, C. and Li, K., (2009), Improved distributed concurrency control algorithm based on real-time database systems, Computational Intelligence and Software Engineering, (CiSE), International Conference on IEEE, pp. 1-3.

    Zoltan, E., Carlos, M. V. and Victor, M., (2006), Recent advances in formal languages and applications, Berlin Heidelberg, Springer-Verlag,.

     

    مراجع فارسی:

    روحانی رانکوهی، م. ت.، (1386)، سیستم مدیریت پایگاه داده‌ها: (مفاهیم و تکنیک‌ها)، ویراست دوم، چاپ سوم، تهران



تحقیق در مورد پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری , مقاله در مورد پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری , پروژه دانشجویی در مورد پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری , پروپوزال در مورد پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری , تز دکترا در مورد پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری , تحقیقات دانشجویی درباره پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری , مقالات دانشجویی درباره پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری , پروژه درباره پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری , گزارش سمینار در مورد پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری , پروژه دانشجویی در مورد پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری , تحقیق دانش آموزی در مورد پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری , مقاله دانش آموزی در مورد پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری , رساله دکترا در مورد پایان نامه ارزیابی برخی الگوریتم ‌های کنترل همروندی در سیستم مدیریت پایگاه داده ‌ها، از طریق مدل ‌سازی با پتری

ثبت سفارش
تعداد
عنوان محصول
بانک دانلود پایان نامه رسا تسیس