پاورپوینت پروتکل های کنترل همروندی



موضوع ارائه : پروتکل های کنترل همروندی

پروتکل های کنترل همروندی

7/8 – پروتکل های مبتنی بر قفل ( lock- based )
7/9 – پروتکل های مبتنی بر گراف (gragh – based )
7/10 – پروتکل های مبتنی بر مهر زمانی

قفل :
امتیاز دستیایی به یک واحد داده است که توسط زیر سیستم قفل گذاری ( در سیستم مدیریت پایگاه داده ) به یک تراکنش داده می شود و یا از او پس گرفته می شود.

7/8 – پروتکل های مبتنی بر قفل ( lock- based )

پروتکل های مبتنی بر قفل کاربردی ترین روش کنترل همروندی می باشند.
در این روش که بر اساس تخصیص داده ها به تراکنش هاست ، هر گاه تراکنشی بخواهد برای خواندن یا نوشتن به داده ای دسترسی داشته باشد ، ابتدا درخواست قفل مناسب با آن دستور را به واحدی به نام مدیر قفل ( lock manager) می دهد.

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

ادامه صفحه قبل

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

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

1-7/8 – سازگاری قفل ها
به طور کلی دو نوع قفل مرسوم است :

الف : قفل دو حالتی ( باینری – binary )
در این حالت داده یا قفل است یا باز . اشتراک داده ها وجود ندارد و درخواست تراکنش ها فقط در صورت باز بودن قفل داده اجابت می شود.

ب : قفل اشتراکی – انحصاری (shared – exclusive)
به منظور بالا بردن سطح همروندی تراکنش ها و امکان به اشتراک گذاشتن داده ها ، قفل ها به دو نوع اشتراکی (s) و انحصاری (x) تقسیم می شوند.

ادامه صفحه قبل

قفل اشتراکی برای خواندن (read) داده استفاده می شود. پس در صورت نیاز به اجرای دستور خواندن باید در خواست قفل اشتراکی بدهیم و مدیر قفل به سایر تراکنش ها نیز اجازه قفل اشتراکی و خواندن داده را می دهد.

قفل انحصاری برای نوشتن (write) داده استفاده می شود.
داده ی مربوطه را به طور انحصاری قفل و آن را در اختیار تراکنش مربوطه قرار می دهد. هیچ تراکنش دیگری به هیچ وجه نمی تواند تا باز شدن این قفل به آن داده دسترسی داشته باشد.

جدول 7/2 : جدول سازگاری قفل های S و X

چند نکته :

1 – هر تراکنش قبل از هر اجرای دستور R و W باید درخواست قفل مربوطه را به مدیر قفل بدهد. چنانچه این درخواست با توجه به جدول سازگاری اجابت شود در این صورت می تواند دستور R یا W را اجرا کند.

2- چنانچه درخواست قفلی اجابت نشود تراکنش به حالت انتظار (wait) می رود تا قفل های روی آن داده آزاد شود و حالت سازگار پیش بیاید.

3 – چندین تراکنش می توانند به طور همزمان یک داده را از نوع s قفل کرده و همزمان بخوانند . اما چنانچه تراکنشی داده ای را از نوع x قفل کرده باشد دیگر هیچ تراکنشی نمی تواند هیچ نوع قفلی روی آن داده بزند.

4 – در خواست قفل های s و x روی داده Q برای تراکنش i را به ترتیب با si (Q) و xi(Q) نمایش می دهیم و ui(Q) هم یعنی قفل تراکنش i توسط سیستم آزاد می شود.

5- قفل گذاری داده ها میتواند با دانه بندی های (granularity) مختلف ( از لحاظ اندازه داده ) انجام گیرد. مثلا قفل روی صفت ، جدول یا کل بانک اطلاعات و …
به طور کلی هر چه دانه بندی ریزتر (fine grain ) باشد درجه همروندی بالا می رود و سر بار نیز افزایش می یابد.
هر چه دانه بندی درشت تر (coarse grain ) باشد همروندی و نیز سر بار کمتر خواهد بود.
معمولا واحد قفل گذاری صفحه یا قطعه (segment or page) می باشد.

6 – به منظور پیاده سازی واحد مدیر قفل از جدولی به نام جدول قفل (lock table) استفاده می شود که در هر لحظه وضعیت استفاده تراکنش ها از داده ها، نوع قفل ها، اشتراک داده ها و … را در بر دارد.

7 – استفاده از قفل گذاری برای تضمین درست بودن زمانبندی کفایت نمی کند بلکه باید قفل ها را با رعایت پروتکل ها به کار بست.

مثال : معادل زمانبندی S1 را با استفاده از قفل های اشتراکی و انحصاری بنویسید.

S1 : r1(A)w1(A)a1w2(A)w2(B)c2

:حل
S2 : s1(A)r1(A)x1(A)w1(A)a1u1(A)x2(A)w2(A)x2(B)w2(B)u2(A)u2(B)c2

می توان اینگونه نیز نمایش داد:

S(A),r(A),x(A),w(A),u(A),a S2: t1
t2 x(A),w(A),x(B),w(B),u(A),u(B),c

3-7/8- پروتکل قفل دو مرحله ای ((2PL
سناریوی زیر را در نظر بگیرید:
در زمانبدی S5 تراکنش T9 مبلغی از حساب بانکی A به حساب بانکی B منتقل می نماید از دستورهای des و inc برای کاهش و افزایش موجودی استفاده شده است.
تراکنش همروندی T10 جمع موجودی دو حساب را محاسبه می کند.

با وجود اینکه همه قوانین قفل گذاری رعایت شده باز هم نتیجه T10غلط است!
این مشکل از انجا ناشی می شود که در جدول سازگاری قفل ها فقط روی داده مشترک تمرکز شده است که دو مشکل همروندی
( تغییرات گم شده و خواندن داده تثبیت نشده ) را حل می کند و مشکل سوم ( بازیابی ناهنگام )حل نشده باقی می ماند.
برای حل این مشکل پروتکل های قفل گذاری معرفی گردیده اند.
پروتکل های قفل گذاری به باز کردن قفل نیز می پردازند.

پروتکل قفل دو مرحله ای تضمین می کند که در زمانبندی پی در پی پذیر در برخورد باشد و سه مشکل همروندی را نیز حل کند.
این پروتکل شامل دو مرحله است :

1- مرحله رشد growing))
که در این مرحله تراکنش فقط می تواند قفل بگیرد اما نمی تواند قفل آزاد نماید.

2- مرحله نقصان یا عقب نشینی (shrinking)
در این مرحله تراکنش فقط می تواند قفل ها را ازاد نماید ولی نمی تواند قفل جدیدی روی هیچ داده ای بگیرد .

الف ) پروتکل B2PL :
این پروتکل قفل دو مرحله ای پایه است ، تراکنش ها شروع به گرفتن قفل های مورد نیاز و اجرای دستورات خود می کنند و به محض اینکه یکی از تراکنش ها قفلی را ازاد کرد وارد مرحله دوم می شود که از این پس هیچ قفلی را نمی تواند بگیرد .

ادامه صفحه قبل

مهمترین مزیت این پروتکل این است که تضمین می کند تراکنش ها به ترتیب نقطه قفل( نقطه ای که تراکنش اخرین قفلش را گرفته است) پی در پی پذیر شوند .
در پروتکل B2PL امکان بروز بن بست وجود ندارد .

ب ) پروتکل C2PL :
در این پروتکل هر تراکنش قبل از اینکه شروع به اجرای اولین دستورش کند باید تمام قفل های مورد نیازش را گرفته باشد و اگر موفق نشد دوباره در صف قرار گیرد .

ادامه صفحه قبل

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

پ ) پروتکل S2PL :
برای تضمین عدم وقوع سقوط های ابشاری در پروتکل قفل دو مرحله ای محض ( S2PL) باز کردن قفل های x تا بعد از اتمام تراکنش (commit یا abort ) به تعویق می افتتد قفل های s می توانند کمی زود تر ( بعد از اخرین دستور تراکنش و قبل از commit یا (abort باز شوند در بقیه موارد مشابه B2PL عمل می کند .

ادامه صفحه قبل

مزیت اصلی این پروتکل
1- تضمین توام پذیری و ترمیم پذیری
2- کم کردن پیام ها در بانک اطلاعات نامتمرکز است زیرا نیازی به پیام های باز کردن قفل ندارد.

ت ) پروتکل SC2PL :
به منظور داشتن مزایای دو پروتکل C2PL و S2PL در کنار هم از تلفیق آنها پروتکلی به نام SC2PL ارایه شده که در آن قفل کردن دادها از قوانین C2PL و ازاد کردن آنها از قواعد S2PL تبعیت می کند .

مثال : معادل B2PL و C2PL و S2PL و SC2PL زمانبندی S5 به صورت زیر است:

توضیح B2PL : تراکنش T9 قفل داده A را باز نمی کند تا قفل B به او داده شود . بنابر این T10 نمی تواند B را منتقل نماید و کارش تا رها شدن B به تعویق می افتد در این صودت دو تراکنش به صورت پی درپی پذیری روی هر دو داده کار می کند و نتیجه هر دو صحیح است .

7/9- پروتکل مبتنی بر گراف :

در این پروتکل مجموعه تمام داده های مورد نظر
D={d1,d2….,dn} به صورت یک گراف جهت دار فاقد حلقه (DAG ) در می آید به این گراف گراف بانک اطلاعات گفته می شود .

ادامه صفحه قبل

در این گراف اگر بین هر دو گره d1 ,d2 (داده ای متمایز ) لبه ای به شکل dj di وجود داشته باشد آن وقت هر تراکنش که می خواهد از داده dj استفاده نماید قبل از dj داده di را نیز قفل می کند (یعنی کل مسیر مورد نیاز را قفل کند )
نوعی خاصی از این پروتکل ها پروتکل درختی است که در بانک اطلاعاتی سلسله مراتبی کاربرد داشته است در این پروتکل از قفل باینری یا s/x استفاده می شود .

مثال :
در درخت زیر زمانبندی S11 قفل باینری به صورت زمانبندی S12 اخذ می کند .
S11: W1(E) ,W2(D) ,W1(C) ,W2( E) ,W2( F)

A
B
C
D
E
F

 
S12: 11(E) ,w1 (E) ,u1 (E ) ,12(D), w2(D) ,u2(D),11(A),11(C), w1(C)
u1(c), u1(A) ,12(A), 12(B), 12(E), w2(E) ,u2(E) ,12(F) ,w2(F) ,u2(F) , u2(B), u2(A)

پروتکل های درختی پی در پی پذیری در برخورد و فاقد بن بست بودن را تضمین می کند .
مشکل این پروتکل : داده هایی که نیاز به دسترسی به آنها نیست هم باید قفل شوند که باعث افزایش سربار اضافی،سطح همروندی را کاهش می دهد .

7/10- پروتکل های مبتنی بر مهر زمانی:
این پروتکل ها در بانک اطلاعات نامتمرکز به کار می رود .
هر تراکنش به محض ورود به مهر زمانی تصاعدی ( مثلا زمان ورود تراکنش به سیستم ) تخصیص داده می شود .
مهر زمانی تراکنش Ti را با Ts(Ti) نمایش می دهد .
دو تراکنش Tiو Tj که Tj دیر تر وارد سیستم شده باشد Ts(Tj) > Ts(Ti).
بر این اساس پروتکل های مبتنی بر مهر زمانی تراکنش ها را به ترتیب مهر زمانی آنها به صورت پی در پی پذیر اجرا می کند .

ادامه صفحه قبل

در سیستم های متمرکز مهر زمانی را با ساعت سیستم تولید می کند .

در سیستم های نامتمرکز از یک ساعت برای تخصیص مهر زمانی سراسری استفاده می کنند یا از زوج مرتب مهر زمانی محلی سایت و idخود سایت به عنوان مهر زمانی کمک گرفت.

برای هر داده Q مهر زمانی خواندن و نوشتن ان به صورت زیر تعریف می شود:

W-TS(Q) : مهر زمانی نوشتن داده Q برابر است با بزرگترین مهر زمانی تراکنشی که به طور موفقیت آمیز روی Q نوشته شده است .

R-TS(Q) : مهر زمانی خواندن داده Q برابر است با بزرگترین مهر زمانی تراکنشی که به طور موفقیت آمیز Q را خوانده .

با اعمال قواعد زیر پروتکل های مبتنی بر مهر زمانی تضمین می کنند که به دستوات R و Wکه با هم برخورد دارند به ترتیب مهر زمانی اجرا شوند و زمان بندی های مربوطه پی در پی پذیر باشند .

1) – قواعد خواندن :
فرض کنید تراکنش Ti شامل یک دستور read(Q) است.

الف ): اگر TS(Ti) <= W-TS (Q) انگاه تراکنش Tiداده ای را می خواهد که مقدارش انگاه که بعدآ نوشته می شود پس در این صورت با دستور خواندن تراکنش موافقت نمی شود و تراکنش رد reject می شود .

ب) : اگر TS(Ti)>=W-TS(Q) آنگاه دستور خواندن تراکنش Ti اجرا می شود و مهر زمانی خواندن Q با ماکزیمم بین مهر زمانی Ti و مهر زمانی خواندن Q مقدار دهی می شود .

تذکر : رد (REJECT) شدن تراکنش به معنی در انتظار ماندن یا سقوط یا شروع مجدد می باشد .

2 ) قواعد نوشتن
فرض کنید که تراکنش Tiشامل یک دستور write(Q) باشد .
الف ) – اگر TS(Ti)<R-TS(Q) یاTS(Ti)<W-TS(Q) باشد انگاه با دستور نوشتن تراکنش موافقت نمی شود و تراکنش Ti رد reject) ) می شود .
ب )- در غیره این صورت دستور نوشتن اجرا می شود و مهر زمانی نوشتن Q نیز با TS(Ti) مقدار دهی میشود .

شکل 7/4 لبه ها در گراف پی در پی پذیر پروتکل مبتنی بر مهر زمانی
تراکنش با مهر زمانی کوچکتر
تراکنش با مهر زمانی بزرگتر

اگر هیچ تراکنشی به حالت انتظار نرود ( یعنی رد شدن تراکنش به معنی شروع مجدد باشد ) این پروتکل فاقد بن بست نیز خواهد بود اما ممکن است ترمیم پذیر نباشد .

مثال : زمانبدی r1(B),r2(B),r1(B),w1(B),r3(C),w2(A) را با پروتکل S2PL و مهر زمانی بنویسید .
حل :
الف ) با پروتکل S2PL

S1(A),r1(A),s2(B),r2(B),s1(B),r1(B),x1(B),s3(C),r3(C),c3,u3(C),x2(A)

انتظار انتظار

ب) باپروتکل مهر زمانی می توان دید که .TS(T1)<TS(T2)<TS(T3) اجرای زمانبندی نیز در شکل زیر مشاهده می شود .

2-7/8- بن بست (deadlock) و قحطی (starvation)
زمانبندی زیر را در نظر بگیرید:
انتظار x(A) T7 x(B)w(B)
انتظار s(A)r(A)s(B) T8

T8 در خواست قفلی می دهد که با قفل زده شده T7 روی B سازگاری ندارد و به حالت انتظار می رود. متقابلا همین مشکل برای T7 روی داده A پیش می آید. در این حالت یک انتظار چرخشی بین تراکنش های T7 T8 بوجود آمده که هیچ یک نمی توانند کار خود را ادامه دهند. این انتظار چرخشی منجر به وقوع بن بست شده است.
در حالت کلی این انتظار ممکن است بین چندین تراکنش روی دهد.

ادامه صفحه قبل

یک راه حل بن بست این است که یکی از این تراکنش ها را ساقط کنیم تا قفل هایش آزاد شود و دیگری بتواند با گرفتن آن قفل به کارش ادامه دهد.

مشکل دیگری که پیش می آید قحطی نام دارد.
بدین صورت که مثلا یک تراکنش که قصد زدن قفل X روی داده ای را دارد منتظر دنباله ای از تراکنش ها بماند که همگی قفل S روی همان داده می زنند و این انتظار به پایان نرسد. در این صورت تراکنش درخواست دهنده قفل X دچار قحطی شده است.

7/11 – روش های مدیریت بن بست
سیستم وقتی دچار بن بست می شود که مجموعه ای از تراکنش ها برای همیشه منتظر یکدیگر باشند.

مهمترین استراتژی های مدیریت به قرار زیر می باشند:

1-7/11 – چشم پوشی (ignore)
در این حالت برخورد با بن بست به برنامه نویس یا مدیر سیستم یا … واگذار می شود.

2-7/11 – فرصت (timeout)
تراکنشی که به حالت انتظار می رود فقط برای مدت زمان معینی منتظر بماند و پس از آن در صورت سرویس نگرفتن ساقط شود.
این روش بن بست را میشکند و روشی بسیار ساده است اما امکان بروز قحطی وجود دارد.
تعیین مقدار مناسب برای فرصت کار مشکل و پیچیده ای است.

3-7/11- پیشگیری (prevention)
این روش تضمین می کند که سیستم هرگز دچار بن بست نشود.
بدین منظور می توان :
از پروتکل هایی استفاده نمود که در آن هر تراکنش قبل از شروع به اجرا تمام قفل های مورد نیازش را بگیرد. مثل (SC2PL , C2PL)
بین داده ها ترتیبی در نظر گرفته و تراکنش ها بر اساس این ترتیب مجاز به قفل کردن باشند ( مثل پروتکل های مبتنی بر گراف)

4-7/11- اجتناب ( avoidance )
تراکنش ها به پیش می روند و هنگام درخواست داده احتمال وقوع بن بست بررسی و از آن اجتناب می شود.

ادامه صفحه قبل

یکی از روش ها استفاده از مهر زمانی مخصوص بن بست است و یکی از روش های زیر را می توان اعمال کرد:

روش wait-die : تراکنش پیرتر (با مهر زمانی کمتر) منتظر تراکنش جوان تر می ماند تا قفل مربوطه را آزاد کند. در مقابل تراکنش جوانتر هرگز منتظر نمی ماند بلکه ساقط می شود ( می میرد) ممکن است یک تراکنش چندین بار بمیرد.

روش wound-wait : تراکنش پیرتر به جای انتظار تراکنش جوان تر را می کشد (قبضه ای preemptive )نام دارد. تراکنش جوان تر منتظر تراکنش پیرتر می ماند.

در این روش بر خلاف wait-die تراکنش پیرتر اولویت بالاتری دارد وبا کشتن تراکنش جوان تر فرایند اجرا را به قبضه خود در می آورد.

نکته : روش wound-wait ممکن است کمتر منجر به ساقط شدن تراکنش ها شود زیرا از تعداد تراکنش های پیرتر کاسته می شود.

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

مثال: فرض کنید T1 درخواست قفل روی داده Q دارد و T1 داده Q را قفل ناسازگار کرده است. در این صورت طبق جدول زیر عمل خواهد شد:

5-7/11- تشخیص و رفع بن بست
در این روش چنانچه بن بستی اتفاق بیفتد مشخص و حل می گردد.
برای تشخیص بن بست گرافی به نام گراف انتظار رسم می کنیم که گره های آن تراکنش ها هستند و لبه Ti Tj در صورتی وجود دارد که تراکنش Ti منتظر Tj باشد.
چنانچه گراف انتظار تراکنش ها فاقد حلقه (cycle) باشد بن بست وجود ندارد.

تشخیص بن بست با یافتن حلقه در گراف انتظار انجام می شود و برای رفع آن باید این حلقه را از بین برد. برای شکستن یک حلقه می توان یکی از گره هایی که در این حلقه شرکت دارند را حذف کرد یعنی تراکنشی را به عنوان قربانی (victim) انتخاب و آن را ساقط کرد.

انتخاب قربانی خود روش های مختلفی دارد معمولا سعی می کنیم تراکنشی را به عنوان قربانی انتخاب کنیم که ساقط کردن آن حداقل هزینه را به دنبال داشته باشد.

مثال : گراف انتظار زمانبندی S10 با قفل باینری به صورت زیر می باشد:

می توان یکی از تراکنش ها را به عنوان قربانی ساقط نمود تا دیگری بتواند ادامه دهد.

T2
T4

مهمتریت معیار های انتخاب قربانی عبارت اند از:

تعداد حلقه هایی از گراف انتظار که این تراکنش در آن شرکت دارد و با ساقط شدن آن این حلقه ها شکسته خواهند شد.
حجم کاری که تا کنون در آن تراکنش صورت گرفته است .
تعداد بروز رسانی های انجام شده در آن
حجم کاری از تراکنش که برای اتمام آن باقی مانده است.

یک راهکار برای مشکل قحطی این است که تعداد دفعات ساقط شدن به عنوان فاکتوری در انتخاب قربانی در نظر گرفته شود.
اگر با ساقط شدن یک قربانی بن بست از بین نرود قربانی بعدی را ساقط می کنیم.

با سپاس