مقاله فارسی الگوريتم

چكيده : در اين گزارش ما به بررسي ويژگي هاي الگوريتمهاي كنترل همروندي توزيعي كه بر پايه مكانيزم قفل دو مرحله اي(2 Phase Locking) ايجاد شده اند خواهيم پرداخت. محور اصلي اين بررسي بر مبناي تجزيه مساله كنترل همروندي به دو حالت read-wirte و write-write مي‌باشد. در اين مقال، تعدادي از تكنيكهاي همزمان سازي براي حل هر يك از قسمتهاي مساله بيان شده و سپس اين تكنيكها براي حل كلي مساله با يكديگر تركيب مي‌شوند.
در اين گزارش بر روي درستي و ساختار الگوريتمها متمركز خواهيم شد. در اين راستا براي ساختار پايگاه داده توزيعي يك سطحي از انتزاع را در نظر مي‌گيريم تا مساله تا حد ممكن ساده سازي شود.
1. مقدمه : كنترل همروندي فرآيندي است كه طي آن بين دسترسي هاي همزمان به يك پايگاه داده در يك سيستم مديريت پايگاه داده چند كاربره هماهنگي بوجود مي‌آيد. كنترل همروندي به كاربران اجازه مي‌دهد تا در يك حالت چند برنامگي با سيستم تعامل داشته باشند در حاليكه رفتار سيستم از ديدگاه كاربر به نحو خواهد
بود كه كاربر تصور مي‌كند در يك محيط تك برنامه در حال فعاليت است. سخت ترين حالت در اين سيستم مقابله با بروز آوري هاي آزار دهنده اي است كه يك كاربر هنگام استخراج داده توسط كاربر ديگر انجام مي‌دهد. به دو دليل ذيل كنترل همروندي در پايگاه داده هاي توزيعي از اهميت بالايي برخوردار است:
كاربراان ممكن است به داده هايي كه در كامپيوترهاي مختلف در سيستم قرار دارند دسترسي پيدا كنند.
يك مكانيزم كنترل همروندي در يك كامپيوتر از وضعيت دسترسي در ساير كامپيوترها اطلاعي ندارد.
مساله كنترل همروندي در چندين سال قبل كاملا مورد بررسي قرار گفته است و در خصوص پايگاه‌داده‌هاي متمركز كاملا شناخته شده است. در خصوص اين مسال در پايگاه داده توزيعي با توجه به اينكه مساله در حوزه مساله توزيعي قرار مي‌گيرد بصورت مداوم راهكارهاي بهبود مختلف عرضه مي‌شود. يك تئوري رياضي وسيع براي تحليل اين مساله ارائه شده و يك راهكار قفل دو مرحله اي به عنوان راه حل استاندارد در اين خصوص ارائه شده است. بيش از 20 الگوريتم كنترل همروندي توزيعي ارائه شده است كه بسياري از آنها پياده سازي شده و در حال استفاده مي‌باشند.اين الگوريتمها معمولا پيچيده هستند و اثبات درستي آنها بسيار سخت مي‌باشد. يكي از دلايل اينكه اين پيچيدگي وجود دارد اين است كه آنها در اصطلاحات مختلف بيان مي‌شوند و بيان هاي مختلفي براي آنها وجود دارد. يكي از دلايل اينكه اين پيچدگي وجود دارد اين است كه مساله از زير قسمتهاي مختلف تشكيل شده است و براي هر يك از اين زير قسمتها يك زير الگوريتم ارائه مي‌شود. بهترين راه براي فائق آمدن بر اين پيچدگي اين است كه زير مساله ها و الگوريتمهاي ارائه شده براي هر يك را در ي.ك سطح از انتزاع نگاه داريم.
با بررسي الگوريتمهاي مختلف مي‌توان به اين حقيقت رسيد كه اين الگوريتمها همگي تركيبي از زير الگوريتمهاي محدودي هستند.
در حقيقت اين زير الگوريتمها نسخه‌هاي متفاوتي از دو تكنيك اصلي در كنترل همروندي توزيعي به نامهاي قفل دو مرحله اي و ترتيب برچسب زماني مي‌باشند.
همانطور كه گفته شد، هدف كنترل همروندي مقابله با تزاحمهايي است كه در اثر استفاده چند كاربر از يك سري داده واحد براي كاربران بوجود مي‌آيد است. حال ما با ارائه دو مثال در خصوص اين مسائل بحث خواهيم نمود. اين دو مثال از محك معروف TPC_A مقتبس شده اند. در اين مثالها، يك سيستم اطلاعات را از پايگاه داده ها استخراج كرده و محاسبات لازم را انجام داده و در نهايت اطلاعات را در پايگاه داده ذخيره مي‌نمايد.
حالت اول را مي‌توان بروزآوري از دست رفته ناميد. حالتي را تصور كنيد كه دو مشتري از دو سيستم مجزا بخواهند از يك حساب مالي برداشت نمايند. در اين حالت فرض كنيد در غياب سيستم كنترل همروندي، هر دو با هم اقدام به خواندن اطلاعات و درج اطلاعات جديد در سيستم ميكنند. در اين حالت در غياب سيستم كنترل همروندي تنها آخرين درج در سيستم ثبت مي‌شود. اين حالت در شكل 1 نشان داده شده‌ است.

شكل 1 نمايش حالت بروز آوري از دست رفته
حالت دوم حالتي است كه در آن اطلاعات صحيح از پايگاه داده استخراج نمي‌شود. در اين حالت فرض كنيد دو مشتري بخواهند كارهاي ذيل را انجام دهند.
مشتري 1: بخواهد يك چك 1 ميليوني را به حساب X واريز و از حساب Y برداشت نمايد.
مشتري 2: بخواهد بيلان حساب مالي X و Y شامل كل موجودي را نمايش دهد.
در غياب كنترل همروندي همانطور كه در شكل 2 نشان داده شده‌است، تزاحم بين پروسس ها بوجود خواهد آمد. فرض كنيد در زماني كه مشتري 1 اطلاعات را از حساب Y خوانده و اطلاعات حساب X را دريافت نموده و 1 ميليون از حساب Y برداشت نموده ولي هنوز
1 ميليون به حساب X و اريز نكرده مشتري 2 اطلاعات كل دو حساب را دريافت نموده و نتيجه را چاپ نمايد. در اين حالت مشتري شماره 2 اطلاعاتي را كه به عنوان بيلان نمايش مي‌دهد 1 ميليون از مقدار واقعي كمتر است. اين حالت يك فرق اساسي با حالت اول دارد و آن اين است كه در اين حالت نتيجه نهايي در پايگاه داده درست خواهد بود در حاليكه اطلاعات دريافت شده بصورت موقت غلط خواهند بود.

شكل 2 خواندن اطلاعات نادرست از سيستم
مساله كنترل همروندي در پايگاه داده هاي توزيعي تا حدودي شبيه مساله دوبه‌دو ناسزگاري در سيستم عامل مي‌باشد. در مساله دوبه‌دو ناسازگاري، هماهنگي جهت دسترسي به منابع سيستم ائم از حافظه، ابزارهاي ورودي و خروجي و CPU و …. بوجود مي‌آيد. در
اين حالت راه حلهاي گوناگوني ائم از قفلها، سمافورها، مونيتورها و … پيشنهاد شده است.
كنرتل همروندي و دوبه‌دو ناسگاري از اين جهت كه هر دو دسترسي به منابع مشترك را كنترل ميكنند با هم شباهت دارند. با اين حال راه حلي كه براي يكي بكار مي‌رود قابل بهره برداري براي ديگري نيست. فرض كنيد پردازه هاي P1 و P2 بخواهند از نقاط مختلف كدهاي خود به منابع R1 و R2 دسترسي پيدا كنند. در سيستم عامل دسترسي مجزاي ذيل قابل قبول است. P2 از R1 استفاده كند، P2 از R1 استفاده كند، P2 از R2 استفاده نموده و سپس P1 از R2 استفاده نمايد. در پايگاه داده اين روند اجرا مورد قبول نيست و مشكلاتي را ايجاد مي‌كند. فرض كنيد P1 بخواهد از R1 مبلغي را به R2 انتقال دهد. در اين حالت اگر P2 مقادير R1 وR2 را چك كند مقادير غير صحيح را دريافت مي‌كند.
2. مدل پردازش تراكنش: براي اينكه روند اجراي عمليات در سيستمهاي پايگاه داده هاي توزيعي براي خواننده مشخص شود ما در اينجا يك مدل از پايگاه داده‌هاي توزيعي را ارائه مي‌دهيم. سپس نحوه عملكرد مكانيزم كنترل همروندي را در اين مدل بيان خواهيم نمود. در اين مدل پايگاه داده، يك پايگاه داده توزيعي مجموعه از سايتهاست كه توسط يك شبكه به هم متصل شده‌اند. هر سايت يك كامپيوتر است كه يكي يا هر دوي برنامه هاي ذيل را اجرا مي‌كند. برنامه‌ها شامل يك مدير تراكنش يا TM و يك مدير داده يا DM است. TM مسئول مديريت تعامل كاربر با پايگاه داده است و DM مسئول نگهداري داده‌ها است. شبكه نيز يك وسيله ارتباطي كامپيوتر – كامپيوتر است. فرض بر اين است كه شبكه كاملا امن مي‌باشد و پيامها را با همان ترتيبي كه وارد سيستم مي‌شوند به مقصد ارسال مي‌شود. فرض بر اين است كه تعداد داده هاي موجود در سيستم شامل X ، Y و Z است كه داده هاي منطقي موجود در سيستم را تشكيل مي‌دهند. داده هاي ذكر شده فقط واحد داده هاي منطقي هستند و ما با سايز و قالب و جزئيات آنها كاري نخواهيم داشت.
هر پايگاه داده در اين سيستم يك نسبت دهي مقادير بصورت منطقي به اين داده هاي منطقي است. هر داده منطقي مي‌تواند در يك يا بيشتر از يك DM ذخيره شود. افزونگي داده در اثر ذخيره داده در چندين DM براي افزايش دسترسي به داده‌ها است. هر كپي از داده ذخيره شده آيتم داده ناميده مي‌شود. نسخه هاي متعدد داده X را بصورت X1,X2,… نشان داده مي‌شوند. كاربران با DDBMS از طريق اجراي تراكنشها تعامل دارند. تراكنشها مي‌توانند پرس و جو هاي ON-LINE باشند كه با زبان استاندارد پرس و جو ارسال شده اند. از طرفي تراكنشها مي‌توانند عملياتي باشند كه از طريق برنامه هاي نوشته شده به سيستم داده مي‌شوند. الگوريتمهاي كنترل همروندي، كاري با نوع تراكنشهاي موجود در سيستم ندارند و محاسبات انحام شده در اين تراكنشها تاثيري در روند اين الگوريتمها ندارد. بر خلاف اينها اين الگوريتمها تمام تصميم گيري هاي خود را بر اساس داده هايي كه اين تراكنشها به آنها دسترسي پيدا مي‌كنند انجام مي‌دهند. دسترسي ها مي‌توانند از نوع خواندن يا نوشتن باشند. فرض بر اين است كه محاسبات در تراكنشها كامل بوده و اگر تراكنش در يك پايگاه داده به تنهايي اجرا شود، پايگاه داده در حالت صحيح و مانا قرار گرفته و نتايج كاملا صحيحي در بر خواهد داشت. مجموعه منطقي خواندني يك تراكنش مجموعه اي از آيتمهاي داده اي است كه تراكنش مي‌خواند. اين امر در شكل 3 نمايش داده شده است.

شكل 3 مدل اجراي تراكنشها
صحت يك الگوريتم كنترل همروندي بر اساس نياز كاربران به اجراي تراكنشها تعريف مي‌شود. در اينجا مي‌توان دو شرط اساسي را مي‌توان براي اجراي صحيح تراكنشها مي‌توان در نظر گرفت. شرط اول
اين است كه كاربران انتظار دارند تراكنشهايي را كه در سيستم ثبت مي‌كنند، نهايتا اجرا شود. شرط دو م اين است كه كاربران انتظار دارند تراكنشهاي ارسالي دقيقا مانند زماني كه تراكنش در يك سيستم مجزا يا در يك محيط موازي چند برنامه، اجرا مي‌شود اجرا شود و نتايج آن در هر دوحالت كاملا مشابه باشد. تحقق اين شرايط دقيقا اهداف يك الگوريتم كنترل همروندي را مشخص مي‌كنند. يك سيستم DDBMS چهار جزء اصلي را در برخواهد داشت: تراكنش، TM، DM و داده‌ها. تراكنشها با TM ارتباط دارند. TM ها با DM ها ارتباط برقرار مي‌كنند و DM ها داده ها را مديريت مي‌كنند. TM ها با ساير TM ها ارتباط برقرار نمي‌كنند.
TM ها بر تركانش ها و اجراي آنها نظارت مي‌كنند. هر تراكنش در پايگاه داده هاي توزيعي فقط با يك TM در ارتباط است. اين بدين معنا است كه هر تراكنش تمام عمليات پايگاه داده خود را به TM مربوط به خود ارسال مي‌كنند. تمامي عملياتهاي توزيعي كه بايستي توسط تراكنش انجام شود توسط TM مزبور مديريت مي‌شود. چهار عمليات مختلف توسط واسط TM براي تراكنشها قابل تعريف است. READ(X) مقدار جاري X را در وضعيت فعلي پايگاه داده هاي منطقي برمي‌گرداند. WRITE(X,NEWVALUE) مقدار X را در حالت جاري پايگاه داده‌هاي منطقي به مقدار NEWVALUE تغيير مي‌دهد. همچنين با استفاده از BEGIN و END ابتدا و انتهاي يك تراكنش براي يك TM مشخص مي‌شود.
3-تحليل مساله كنترل همروندي : در اينجا ما با دو رويكرد به مواجه با مساله كنترل همروندي خواهيم پرداخت. در رويكرد اول به نحوه اجراي صحيح خواهيم پرداخت و در رويكرد دوم به تجزيه مساله به بخشهاي قابل حل خواهيم پرداخت.
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 هاي ثبت شده در يك توالي باشد. ما
چند رابطه را مي‌توانيم بين تراكنشهاي موجود در E تعريف كنيم. براي هر جفت تراكنش TI و TJ خواهيم داشت:
قضيه 2: اگر روابط RWR و WW بصورت غير حلقوي بوده و يك ترتيب كلي براي اين روابط بتوان متصور شد.
بنا بر قضيه فوق مي‌توان الگوريتمهاي كنترل همروندي را مورد ارزيابي و بررسي قرار داده و صحت آنها را از طريق اثبات رياضي محك زد. تشخيص تداخلهاي RW و WW براي كشف ايراد در الگوريتمهاي كنترل همروندي كاربرد فراواني دارد. قضيه 2 به ما اجازه مي‌دهد تا مساله كنترل همروندي را به قسمتهاي كوچكتر تقسيم نموده و بتوان هر يك از اين قسمتها را بطور مستقل بررسي نمود.
4-مكانيزمهاي كنترل همروندي بر پايه قفل دو مرحله‌اي : قفل دو مرحله اي با تشخيص روشن تداخل بين عملياتهاي همروند و جلوگيري از آنها، بين عملياتهاي خواندن و نوشتن همزماني بوجود مي‌آورد. قبل از اينكه يك تراكنش X را بخواند بايد يك قفل خواندن بر روي X قرار دهد و قبل از اينكه يك تراكنش روي داده X بنويسد، بايد يك قفل نوشتن روي X قرار دهد. تصاحب قفلها با توجه به دو قانون بدست مي‌آيد.:
تراكنشهاي مختلف نمي‌توانند قفلهايي كه باعث ايجاد تداخل مي‌شوند بدست آورند.
زماني كه يك تراكنش شروع به آزاد كردن قفلهاي خود نمود، ديگر نمي‌تواند قفل ديگري بدست آورد.
قفلهايي كه باعث تزاحم مي‌شوند با توجه به نوع همزمان سازي مشخص و تعريف مي‌شوند. براي حالت RW دو قفل زماني با هم تداخل دارند كه دو شرط در آنها صدق كند:
هر دو قفل بر روي يك داده واحد باشند.
يكي قفل نوشتني و ديگري قفل خواندني باشد.
براي حالت WW دو قفل زماني با هم تداخل دارند كه دو شرط در آنها صدق كند:
هر دو قفل بر روي يك داده واحد باشند.
هر دو قفل از نوع نوشتني باشند.
قانون دوم ايجاب ميكند كه هر تراكنش براي بدست آوردن قفل دو فاز را طي كند. فاز اول كه فاز دستيابي به قفلهاست، تراكنش اقدام به بدست آوردن قفلهاي لازم مي‌كند. در فاز دوم كه فاز تخليه است، تراكنش به مرور زمان قفلهاي خود را آزاد مي‌كند. هنگامي كه تراكنش خاتمه پيدا مي‌كند كليه قفلها رها مي‌شوند.
روشهاي مختلفي براي الگوريتمهاي قفل دو مرحله‌اي پيشنهاد شده است. يكي از اين روشها اين است كه تراكنش قفلهاي مورد نياز را قبل از اجراي اصلي خود بدست آورد. اين نسخه از قفل دو مرحله‌اي را پيش تعريف مي‌نامند. برخي از سيستمهاي تراكنشها را مجبور مي‌كنند تا قفلهاي خود را تا پيش از خاتمه نگه دارند. قفل دو مرحله‌اي يك تكنيك صحيح ايجاد قابليت توالي است. اين امر با بررسي سيستم از لحظه عدم وجود حلقه و دور در روابط RWR و WW مشخص است. ترتيب اجراي تراكنشها با ترتيب بدست آوردن قفلها مشخص مي‌گردند. نقطه اي كه در آن تراكنش تمامي قفلهاي مورد نياز خود را بدست آورده است را نقطه تصاحب قفل مي‌نامند. روشهاي مختلفي براي ايجاد الگوريتم قفل دو مرحله اي در سيستمهاي توزيعي وجود دارد كه در قسمت بعد مورد بررسي قرار مي‌گيرد.
5-پياده سازي پايه قفل دو مرحله‌اي : در پياده سازي پايه الگوريتم قفل دو مرحله‌اي يك ماژول نرم افزاري ايجاد مي‌شود كه روند دريافت و آزاد سازي قفلها را بر اساس ويژگي هاي الگوريتم قفل دو مرحله‌اي كنترل مي‌كند.
يك روش براي پياده سازي توزيعي اين الگوريتم اين است كه ماژولهاي نرم افزاري را بين اجزاي پايگاه‌داده توزيع نمائيم. براي اينكار هر ماژول را در DM يعني آنجائيكه X داده تحت
كنترل است قرار دهيم. اگر يك قفل قابل تخصيص نباشد، درخواست براي قفل در يك صف انتظار قرار داده مي‌شود. قفلهاي نوشتن بطور خودكار با انجام عمل WRITE آزاد مي‌شوند. در اينصورت براي آزاد نمودن قفلهاي خواندني بايستي عمليات اضافه تعريف نمود. آزاد نمودن قفلها با نوشتن اطلاعات و آغاز فاز تخليه آغاز مي‌شود. هرگاه يك قفل آزاد مي‌شود عملياتهاي موجود در صف شروع به ادامه مي‌كنند.
توجه داشته باشيد كه اين پياده سازي افزونگي داده را به درستي پوشش داده و مشكل افزونگي داده و صحت و مانايي اطلاعات را حل مي‌كند. اگر اين روش براي همزمان سازي هاي RW بكار رود، تراكنش مي‌تواند هر كپي داده اي را كه در دسترس بود بخواند و هر قفل خواندني كه مهيا بود را بدست آورد. در هر صورت اگر بخواهد داده را بروزآوري كند، يعني مقدار جديدي به داده اي نسبت دهد بايد بر روي تمام افزونه‌هاي دادهاي مورد نظر، مقدار جديد را ثبت كند و داده را بروز كند كه مستلزم بدست آوردن قفل نوشتن بر روي تمامي نسخه هاي داده اي است.
6-قفل دو مرحله‌اي با نسخه اوليه : قفل دو مرحله‌اي با نسخه اوليه يك تكنيك از نوع قفله دو مرحله‌اي است كه كه به افزونگي داده توجه خاصي دارد. يك كپي از هر داده منطقي به عنوان يك كپي يا نسخه اوليه از داده مزبور مطرح مي‌شود. قبل از دسترسي به هر گونه كپي از داده هاي منطقي، قفل صحيح بايد از كپي اوليه اخذ شود.
براي قفلهاي خواندني اين روش تعامل و ارتباطات بيشتري را نياز دارد.فرض كنيد كه ‏T يك تراكنش باشد كه بخواهد داده X را بخواند. در اينصورت اگر X1 كپي اوليه از X باشد و XI براي خواندن توسط تراكنش در دسترس باشد، تراكنش بايستي با X1 كه كپي اوليه داده است تعامل داشته و قفل خود را بدست آورد و پس از آن نيز با تعامل با XI داده مورد نظر خود را از XI بخواند.
براي قفلهاي نوشتني بر عكس پياده سازي پايه قفل دو مرحله اي تراكنش احتياجي به تعامل بيشتر با ساير DM ها ندارد. در پياده سازي پايه قفل دو مرحله اي، اگر يك تراكنش مي‌خواست داده X را بروز كند، لازم بود تا بر تمامي نسخه هاي X قفل نوشتني بزند و سپس عمل نوشتن را بر روي تمامي نسخه هاي X انجام دهد اما در اينجا فقط لازم است كه تراكنش قفل نوشتن را بر روي كپي اوليه قرار دهد و در صورت بدست آوردن قفل، بايد عمليات نوشتن را مانند روش قبل بر روي تمامي نسخه هاي X انجام دهد.
6-قفل دو مرحله‌اي با راي گيري : قفل دو مرحله اي با راي گيري پياده‌سازي ديگري از روشهاي قفل دو مرحله اي است كه در آن افزونگي داده بيشتر مد نظر قرار گرفته است. اين روش شكل تغيير يافته الگوريتم توافق اكثريت توماس است و تنها براي همزمان سازيهاي WW مناسب است.
براي فهم بهتر اين روش بهتر است آنرا در داخل روش TWO PHASE COMMIT توصيف كنيم. فرض كنيد يك تراكنش بخواهد بر روي داده X مقدار جديدي را بنويسد، در اينصورت درخواست قفل به تمامي نسخه هاي داده X ارسال شود. در صورتيكه قفل قابل تخصيص باشد، DM دريافت كننده قفل بايستي يك پيام تخصيص قفل صادر نمايد. در صورتيكه قفل قابل تخصيص نباشد نيز يك پيام بلوكه شدن در خواست قفل ارسال مي‌گردد. در صورتيكه پيامها از DM هاي مختلف برگشت داده شد، حال TM ارسال كننده درخواست قفل اقدام به تصميم‌گيري مي‌نمايد. در صورتيكه تعداد قفلهاي اخذ شده داراي اكثريت باشند، آنگاه TM دقيقا مانند حالتي عمل ميكند كه قفلهاي لازم را بر روي نسخه داده اي مزبور بدست آورده است. در اين حالت TM باقي عمليات يعني نوشتن بر روي داده مزبور را انجام مي‌دهد. در صورتيكه قفلهاي لازم بر روي داده مورد نظر به تعداد اكثريت نباشد، TM منتظر دريافت پاسخ تخصيص قفل از DM هايي كه پاسخ بلوكه شدن قفل را ارسال نمودند، مي‌شود. در اين حالت با دريافت
پاسخ جديد از DM هايي كه قبلا درخواست را بلوكه كردند، TM تعداد قفلهاي لازم را بررسي مي‌كند. در صورت اخذ اكثريت آرا، اجراي خود را ادامه مي‌دهد. از آنجائيكه فقط يك تراكنش مي‌تواند در هر لحظه اكثريت قفلهاي نوشتن را بدست آورد در نتيجه فقط در هر لحظه فقط بك تراكنش مي‌تواند بر روي اطلاعات تغييرات اعمال نمايد. در هر لحظه فقط يك تراكنش مي‌تواند در فاز نوشتن خود قرار داشته باشد. در نتيجه تمامي نسخه هاي X داراي يك ترتيب مشخص و مشترك از مقادير مي‌باشند. نقطه قفل يك تراگنش جايي است كه يك تراكنش توانسته است اكثريت قفلهاي لازم را براي نوشتن براي هر آيتم داده‌اي در مجموعه نوشتاري خود بدست آورد. براي بروز آوري هاي با حجم بالا ، تراكنش بايستي اكثريت قفلهاي نوشتن را بر روي تمامي آيتمهاي داده اي نوشتني خود قبل از ارسال دستورات نوشتن بدست آورد.
در حقيقت، قفل دو مرحله اي با راي گيري مي‌تواند براي همزمان سازي عمليات هاي RW سازگار شود. براي اينكار براي خواندن يك نسخه داده‌اي بايستي قفل خواندن از تمامي نسخه هاي داده اي درخواست شود. در صورتيكه اكثريت قفل خواندن از DM ها بدست آيد مي‌تواند اطلاعات مورد نظر را بخواند. اين روش روش بسيار خوب و قدرتمندي است ولي در اين روش براي خواندن يك آيتم داده اي بايستي از تمامي سايتهايي كه داراي يك نسخه از آيتم داده‌اي مذكور هستند قفل خواندن اخذ شود كه عملا سيستم را بسيار كند مي‌كند.
7- قفل دو مرحله‌اي متمركز : بجاري توزيع نمودن زمانبندها بر روي سايتهاي مختلف، همه زمانبندها را بر روي يك سايت متمركز خواهيم نمود. در اين خالت اگر يك تراكنش بخواهد به يك داده X دسترسي پيدا كند بايد از سايت مذكور درخواست قفل مناسب بر روي داده مذكور نمايد. در اين وضعيت داده ممكن است بر روي يك سايت غير از سايت زمانبند مركزي قرار داشته باشد.
فرض كنيد تراكنشT بخواهد داده X را بخواند در اينصورت بايستي T يك قفل خواندن را از سايت مركزي درخواست نمايد. در اين حالت اگر قفل تخصيص داده شود تراكنش مي‌تواند اطلاعات را از يكي از سايتهايي كه داراي Xهستند درخواست نمايد. در غير اينصورت بايد منتظر دريافت مجوز تخصيص ثقفل خواندن از سوي سايت زمانبند مركزي باشد. در حالتي كه داده X بر روي سايت مركزي زمانبند نيز باشد، درخواست قفل و داده بطور مشترك به سايت مركزي ارسال مي‌شود، در صورتيكه قفل قابل تخصيص باشد، عمليات خواندن به همراه تخصيص قفل انجام مي‌شود. براي عمليات بروز آوري و نوشتن نيز فرآيند تخصيص قفل به همين نحو است با اين تفاوت كه بعد از تخصيص قفل و اعلام به درخواست كننده از سوي سايت مركزي زمانبندي، سايت درخواست كننده موظف است تمامي كپي هاي نسخه هاي اطلاعاتي را بروز نمايد. اين روش نيز مانند قفل دو مرحله‌اي كپي اوليه مستلزم نقل و انتقال مضاعف پيام مي‌باشد.
8-تشخيص و ترميم بن بست : در اين خصوص روشهاي مختلفي ارائه شده است. مهمترين روش ارائه شده روش ترسيم گراف تخصيص منابع مي‌ياشد. در خصوص بروز آوري اين گراف در حالت توزيع شده مراتب مختلفي مطرح مي‌شود كه در اين مقال نمي‌گنجد. در خصوص روش قفل دو مرحله‌اي متمركز نيازي به نگهداري توزيع شده اين گراف و تكنيكهاي بروزآوري آن نمي‌باشد و لي در ساير انواع روشهاي قفل دو مرحله‌اي به نگهداري اين گراف و مديريت نگهداري آن و تصميم گيري بر اساس آن نياز مبرم وجود دارد.
4-نتيجه گيري :.در اين گزارش با توجه به توسعه سيستمهاي پايگاه‌ توزيعي، بحث كنترل همروندي و صحت و مانايي اطلاعات در حضور همروندي مطرح مي‌شود. در بين سه روش پايه اي موجود براي كنترل همروندي، يعني روشهاي قفل دو مرحله‌اي، برچسب زماني متوالي و روش خوش بينانه، روش قفل دو مرحله اي مورد تجزيه و
تحليل قرار گرفت. در اين خصوص يك مقدمه براي تشريح مساله كنترل همروندي بيان شد.
در اين گزارش مزاياي روش قفل دو مرحله‌اي بيان شده و علل صحت اين روش تشريح شده است. نهايتا ميتوان گفت از آنجائيكه اين روش از نظر صحت عملكرد كاملا اثبات شده است، مي‌تواند در پايگاه داده‌هاي توزيعي مورد استفاده قرار گيرد.
5-تقدير و تشكر : بر خود لازم مي‌دانيم، از راهنمايي‌ها و كمكهاي جناب آقاي دكتر مسعود رهگذر، استاديار گروه مهندسي برق و كامپيوتر دانشكده فني دانشگاه تهران و نيز جناب آقاي مهندس مهدي عمادي، تشكر و قدرداني نمائيم.

فایل : 19 صفحه

فرمت : Word