دانلود با لینک مستقیم و پر سرعت .
لینک پرداخت و دانلود *پایین صفحه*
فرمت فایل : Word(قابل ویرایش و آماده پرینت)
تعداد صفحه : 19
فهرست مطالب:
چکیده
مقدمه
مدل پردازش تراکنش
تحلیل مساله کنترل همروندی
مکانیزمهای کنترل همروندی بر پایه قفل دو مرحله‌ای
پیاده سازی پایه قفل دو مرحله‌ای
قفل دو مرحله‌ای با نسخه اولیه
قفل دو مرحله‌ای با رای گیری
قفل دو مرحله‌ای متمرکز
تشخیص و ترمیم بن بست
نتیجه گیری
چکیده : در این گزارش ما به بررسی ویژگی های الگوریتمهای کنترل همروندی توزیعی که بر پایه مکانیزم قفل دو مرحله ای(2 Phase Locking) ایجاد شده اند خواهیم پرداخت. محور اصلی این بررسی بر مبنای تجزیه مساله کنترل همروندی به دو حالت read-wirte و write-write می‌باشد. در این مقال، تعدادی از تکنیکهای همزمان سازی برای حل هر یک از قسمتهای مساله بیان شده و سپس این تکنیکها برای حل کلی مساله با یکدیگر ترکیب می‌شوند.
در این گزارش بر روی درستی و ساختار الگوریتمها متمرکز خواهیم شد. در این راستا برای ساختار پایگاه داده توزیعی یک سطحی از انتزاع را در نظر می‌گیریم تا مساله تا حد ممکن ساده سازی شود.
- مقدمه : کنترل همروندی فرآیندی است که طی آن بین دسترسی های همزمان به یک پایگاه داده در یک سیستم مدیریت پایگاه داده چند کاربره هماهنگی بوجود می‌آید. کنترل همروندی به کاربران اجازه می‌دهد تا در یک حالت چند برنامگی با سیستم تعامل داشته باشند در حالیکه رفتار سیستم از دیدگاه کاربر به نحو خواهد بود که کاربر تصور می‌کند در یک محیط تک برنامه در حال فعالیت است. سخت ترین حالت در این سیستم مقابله با بروز آوری های آزار دهنده ای است که یک کاربر هنگام استخراج داده توسط کاربر دیگر انجام می‌دهد. به دو دلیل ذیل کنترل همروندی در پایگاه داده های توزیعی از اهمیت بالایی برخوردار است:
- کاربراان ممکن است به داده هایی که در کامپیوترهای مختلف در سیستم قرار دارند دسترسی پیدا کنند.
- یک مکانیزم کنترل همروندی در یک کامپیوتر از وضعیت دسترسی در سایر کامپیوترها اطلاعی ندارد.
مساله کنترل همروندی در چندین سال قبل کاملا مورد بررسی قرار گفته است و در خصوص پایگاه‌داده‌های متمرکز کاملا شناخته شده است. در خصوص این مسال در پایگاه داده توزیعی با توجه به اینکه مساله در حوزه مساله توزیعی قرار می‌گیرد بصورت مداوم راهکارهای بهبود مختلف عرضه میشود. یک تئوری ریاضی وسیع برای تحلیل این مساله ارائه شده و یک راهکار قفل دو مرحله ای به عنوان راه حل استاندارد در این خصوص ارائه شده است. بیش از 20 الگوریتم کنترل همروندی توزیعی ارائه شده است که بسیاری از آنها پیاده سازی شده و در حال استفاده می‌باشند.این الگوریتمها معمولا پیچیده هستند و اثبات درستی آنها بسیار سخت می‌باشد. یکی از دلایل اینکه این پیچیدگی وجود دارد این است که آنها در اصطلاحات مختلف بیان می‌شوند و بیان های مختلفی برای آنها وجود دارد. یکی از دلایل اینکه این پیچدگی وجود دارد این است که مساله از زیر قسمتهای مختلف تشکیل شده است و برای هر یک از این زیر قسمتها یک زیر الگوریتم ارائه میشود. بهترین راه برای فائق آمدن بر این پیچدگی این است که زیر مساله ها و الگوریتمهای ارائه شده برای هر یک را در ی.ک سطح از انتزاع نگاه داریم.
با بررسی الگوریتمهای مختلف می‌توان به این حقیقت رسید که این الگوریتمها همگی ترکیبی از زیر الگوریتمهای محدودی هستند. در حقیقت این زیر الگوریتمها نسخه‌های متفاوتی از دو تکنیک اصلی در کنترل همروندی توزیعی به نامهای قفل دو مرحله ای و ترتیب برچسب زمانی می‌باشند.
همانطور که گفته شد، هدف کنترل همروندی مقابله با تزاحمهایی است که در اثر استفاده چند کاربر از یک سری داده واحد برای کاربران بوجود می‌آید است. حال ما با ارائه دو مثال در خصوص این مسائل بحث خواهیم نمود. این دو مثال از محک معروف TPC_A مقتبس شده اند. در این مثالها، یک سیستم اطلاعات را از پایگاه داده ها استخراج کرده و محاسبات لازم را انجام داده و در نهایت اطلاعات را در پایگاه داده ذخیره می‌نماید.
حالت اول را می‌توان بروزآوری از دست رفته نامید. حالتی را تصور کنید که دو مشتری از دو سیستم مجزا بخواهند از یک حساب مالی برداشت نمایند. در این حالت فرض کنید در غیاب سیستم کنترل همروندی، هر دو با هم اقدام به خواندن اطلاعات و درج اطلاعات جدید در سیستم میکنند. در این حالت در غیاب سیستم کنترل همروندی تنها آخرین درج در سیستم ثبت میشود. این حالت در شکل 1 نشان داده شده است.
تحلیل مساله کنترل همروندی : در اینجا ما با دو رویکرد به مواجه با مساله کنترل همروندی خواهیم پرداخت. در رویکرد اول به نحوه اجرای صحیح خواهیم پرداخت و در رویکرد دوم به تجزیه مساله به بخشهای قابل حل خواهیم پرداخت.
3-1- قابلیت توالی: فرض کنید E یک ترتیب اجرای تراکنشهای t1 تا Tn باشد. در اینصورت E یک اجرای متوالی از تراکنشها است، در صورتیکه هر تراکنش قبل از اجرای تراکنش بعدی به طور کامل اجرا شده و خاتمه پذیرد. تمامی ترتیبهای اجرای متوالی از دیدگاه پایگاه داده‌ها صحیح تصور می‌شوند، چرا که خواص تراکنش اذعان می‌کند که در خاتمه اجرای متوالی صحت پایگاه داده حفظ میشود. یک ترتیب اجرای تراکنش قابل توالی (Serializable) محسوب میشود در صورتیکه نتیجه خروجی اجرای آن برابر یک اجرای متوالی از تراکنشهای مشابه باشد. در نتیجه تمام اجراهای متوالی serializable محسوب می‌شوند و نتیجه صحیحی خواهند داشت.
هدف الگوریتم کنترل همروندی این است که تضمین کند که تمامی ترتیب های اجرای تراکنش ها قابل توالی می‌باشند. تنها عملیاتی که به داده‌های پایگاه داده دسترسی پیدا میکنند dm-read و dm-write می‌باشند. بنا براین برای پایش اجرای توالی لازم است فقط dm-read و dm-write های موجود در پایگاه داده توزیعی در dm ها مختلف مدل شده و رفتار آنها کنترل شود. log فایلها می‌توانند شرح دهنده توالی dm-read ها و Dm-write ها باشند. در یک پایگاه داده توزیعی، یک ترتیب اجرا قابل توالی نامیده میشود در صورتیکه به ازای Ti که قبل از tj در توالی قرار دارد، تمامی عملیاتهای Ti قبل از tj در تمامی سایتها انجام شده باشند. این نشان دهنده این است که تمامی تراکنشها باید به ترتیب وارد شده در تمامی سایتها اجرا شوند.
دو عملیات با هم تداخل دارند اگر هر دو عملیات بر روی یک داده مشترک کار کرده و یکی از داده ها dm-write باشد. در این حالت اگر دو عملیات با هم تداخل داشته باشند، ترتیب اجرای دو عمل بر روی نتیجه نهایی تاثیر مستقیم خواهد داشت. برای روشنتر شدن موضوع به بحث در خصوص یک مثال خواهیم پرداخت. فرض کنید ایتم داده‌ای x و تراکنشهای ti و Tj موجود باشند. اگر ti اقدام به خواندن مقدار X نموده و tj اقدام به نوشتن مقدار جدیدی در x نماید. در اینصورت مقدار خوانده شده توسط ti به تقدم و تاخر عملیاتهای خواندن و نوشتن وابسته خواهد شد. بطور مشابه فرض کنید ti و tj هر دو بخواهند مقدار جدید را در x بنویسند، در اینصورت مقدار x دقیقا به این امر وابسته میشود که کدام عملیات دیرتر انجام شده است. حالت اول را تداخل خواندن- نوشتن (rw) و حالت دوم را تداخل نوشتن – نوشتن (ww) می‌نامند.
نمایش تداخل های مختلف می‌تواند به ارائه یک تعریف فرموله شده برای ترتیبهای اجرای هم ارز کمک کند. دو ترتیب اجرای تراکنش از نظر محاسباتی زمانی معادل هستند که دو شرط ذیل در آنها صادق باشد:
- هر dm-read در تراکنش، داده ای را بخواند که از ابتدا به تراکنش داده شده باشد یا داده ای باشد که توسط یک dm-write از همین تراکنش نوشته شده باشد.
- نتیجه نهایی نوشته شده در آیتم داده‌ای در هر دو ترتیب اجرا یکسان باشد.
قضیه 1: فرض کنید t که بصورت ذیل تعریف شده است مجموعه ای از تراکنشها در یک پیگاه داده باشد:
آنگاه اگر E یک ترتیب اجرا از این تراکنشها در log های l1 تا lm باشد، E قابل توالی خواهد بود اگر به ازای هر دو عملیات oi و oj که با یکدیگر تداخل دارند به ازای تمامی Log ها ترتیب یکسانی نسبت به یکدیگر داشته باشند.
قضیه فوق الذکر برای حل مسائل مربوط به ترتیب توالی در سیستم بکارمی‌رود.
3-2- یک الگو برای کنترل همروندی: در قضیه فوق تداخلهای خواندن- نوشتن و نوشتن – نوشتن بصورت مشترک در یک تعریف عمومی از تداخل ظاهر شده اند. در هر حال ما می‌توانیم مساله قابلیت توالی را با تفکیک این دو نوع تداخل بهتر بررسی کنیم. فرض کنید E یک مجموعه از log های ثبت شده در یک توالی باشد.
