تحصيلات تکميلي

تاريخ دفاع : 4/7/80

رشته و گرايش : کامپيوتر-نرم افزار

استاد مشاور : -

نام و نام خانوادگي : محسن خواجه ميرزايي

دانشکده : فني و مهندسي

استاد راهنما : دکتر کامران زماني فر

ارزيابي الگوريتمهاي كنترل همروندي در سيستم مديريت پايگاه داده توزيع شده رابطه‎اي

چکيده

اجراي همروند تراكنش‎ها در يك سيستم مديريت پايگاه داده توزيع شده ، ممكن است منجر به ناسازگاري‎هايي در پايگاه داده شود . ناسازگاري بر اثر مقادير نادرستي است كه براي داده‎هاي موجود در پايگاه داده بر اثر تداخل اجراء تراكنشها بوجود مي‎آيد . الگوريتمهاي كنترل همروندي ، جهت تضمين اجراء همروند چندين تراكنش كه بصورت موازي با داده‎هاي مشترك كار مي‎كنند طراحي شده‎اند . مسالة كنترل همروندي در پايگاه داده‎هاي توزيع شده امري ضروري و با اهميت مي‎باشد . در اين زمينه مطالعات و تحقيقات فراواني صورت گرفته است كه نتيجة آن الگوريتمهاي متنوع كنترل همروندي مي‎باشد . با توجه به الگوريتمهاي متنوع در اين زمينه و اين واقعيت كه روز به روز بر اهميت و ارزش پايگاه داده‎هاي توزيع شده افزوده مي‎شود ، اما هنوز كارآيي الگوريتمها در مقايسه با يكديگر مشخص نيست . يك تقسيم‎بندي بر روي الگوريتمهاي مزبور ، صورت مي‎گيرد و سه الگوريتم Wound_wait(WW) و Immediate_Restart(IRS) و Optimistic(OPT) از اين تقسيم‎بندي بوسيلة شبيه‎سازي مورد ارزيابي و مقايسه قرار مي‎گيرند . يك مدل جامع به عنوان يك مبنا و چهار چوب واحد براي ارزيابي الگوريتمها مورد استفاده قرار مي‎گيرد . در اين ارزيابي از معيارهاي نرخ تكميل تراكنش ( ميزان تراكنش تكميل شونده در يك مدت زماني معين ) ، زمان پاسخ ( مدت زمان تكميل تراكنش ) و نرخ برخورد ( ميزان برخورد بين تراكنشها در يك اجراء ) استفاده مي‎شود . نتايج حاصل براي طراحان پايگاه داده توزيع شده مي‎تواند بسيار مفيد باشد. در بار كاري كم ، هر سه الگوريتم داراي نرخ تكميل تراكنش يكسان مي‎باشند . اما با افزايش بار كاري ، الگوريتم OPT ، شديدا دچار ترشينگ مي‎شود . ديرتر از همه ، در الگوريتم IRS ترشينگ رخ مي‎دهد. OPT در بار كاري كم از نرخ Abort پايين‎تري نسبت به الگوريتمIRS بر خوردار مي‎باشد . اما در بار كاري بالا نرخ Abort الگوريتم OPT بالاتر از IRS قرار مي‎گيرد . در بار كاري كم الگوريتم OPT داراي كمترين زمان پاسخ بوده ، اما با افزايش بار كاري ، زمان پاسخ OPT بالاتر از همه قرار مي‎گيرد . زمان پاسخ در بار كاري بالا در الگوريتم WW پايين‎تر از دو الگوريتم ديگر مي‎باشد . هر سه الگوريتم بر اثر تكرارسازي ، دچار افزايش زمان پاسخ مي‎شوند . رفتار سه الگوريتم نسبت به يكديگر در حالت تكرارسازي مشابه حالت بدون تكرارسازي مي‎باشد . الگوريتمOPT در بار كاري كم ، كمترين ميزان افزايش زمان پاسخ را بر اثر تكرارسازي دارد . تاثير پذيري WW از تكرارسازي همواره كمتر از تاثيرپذيري IRS است . براي شروع مجدد تراكنش در الگوريتم IRS ، بهترين زمان براي تاخير شروع مجدد مقدار Adaptive مي‎باشد . اين مقدار برابر متوسط زمان پاسخ تراكنشهاي موجود در سيستم مي‎باشد . استفاده از مقدار Adaptive براي WW در بار كاري كم هيچ تاثيري در ميزان نرخ برخورد ندارد ؛اما در بار كاري بالا ميزان نرخ برخورد را كاهش مي‎دهد.