صفحه 1:
بن بست توزیع شده
gach ay سپسچداز پوس و ساروة اكز وسوس بد
منابع سيستم يا رد و بدل نمودن ييام با يكديكر
- تعريف بن بست در سيستم هاى تكى براى سيستم هاى توزيع
cual ae oud
- پیاده سازی بن بست توزیع شده بسیار ه تر است. زیرا
گره ها از حالت سرتاسری سیستم اطلاعاتی ندارند.
صفحه 2:
انواع بن بست های توزیع شده
* بن بست در اختصاص منابع
- جندين يروسس بخواهند به يك منبع دسترسى داشته باشند.
* بن بست در تبادل ييام ها
- هر يروسس در يك مجموعه منتظر ييام از يروسس هاى
مجموعه ديكر است.
EP پروسس در این حالت نمی توانند ارسال کنند. و هر کدام
منتظر دیگری است.
صفحه 3:
بن بست در اختصاص منابع
؟ ایجاد همزمان چهار شرط زير باعث بن بست می شود
.١ انحصار متقابل
Hold and Wait .2
۳ منابع انحصاری(01661001101 (No
Circular Wait .4
* در سیستم های توزیع شده پروسس کنترل کننده با دانش
از نو حالت سرتاسری سیستم وجود ندارد.
صفحه 4:
Cccp way یم
{a) Release arrives before request (b) Request arrives before release
صفحه 5:
راهکارهای مقابله با بن بست
* پیشگیری بن (Deadlock Prevention) cu.
* اجتناب از بن بست( 457010131366 106201060[16)
* شناسايى بن بست(106]6011011 ع106201001)
صفحه 6:
پیشگیری بن بست
* با نقض یکی از چهار شرط ذکر شده مى توان از بن بست
* بيشتر با حذف شرط هاى Hold-and- , Circular-wait
wait از ایجاد بن بست جلوگیری می شود.
* حذف شرط اتحصار متقابل برای دسترسی منابغ غیر ممکن
است.
صفحه 7:
۱ مرتب سازی منابع
* _ اختصاص عدد منحصر بفرد به منابع سیستم
یک پروسس در صورتی می تواند درخواست منبعی با شماره را
بدهد که منابع با شماره بالاتر [ را در اختیار نداشته باشد.
پیاده سازی در محیط توزیع شده ساده است و مقداری بالاسری
دارد.
صفحه 8:
پیشگیری بن بست
۲ روش مبتنی بر مهر زمان
*_ اختصاص شماره های اختصاصی به پروسس ها
* اولویت دهی به اعداد اختصاص داده شده با هر ترتیب مورد نظر
*_ اگر 31 در خواست منبعی کند که در اختیار 3 باشد. در صورتی که
اولویت 31 بیشتر از ژط باشد. آنگاه 1 منتظر می ماند. در غير اين
صورت آن ۲01160-026016 می شود.
* روش جلوكيرى از بن بست ها
*؟ براى هر يال (2 21-2 در كراف انتظارء 31 اولویت بالاتر از ۳ دارد.
*؟ بنابراين در كراف انتظار سيكلى نخواهيم نداشت.
صفحه 9:
۳ طرح ۲۷۷۵۲-116
*_ مبتنی بر تکنیک انحصاری است.
* _ اگر 1 در خواست منبعی کند که فعلا در اختیار باشد. در صورتی
که مهر زمان 1 كمتر از مهر زمان [2 باشد(281 قديمى تراز [2 است).
آن منتظر می wile در غیر این صورت 31 حذف یا rolled-
back(Dies) «. 935
* _ مثال: فرض کنید پروسس های ۳2 .۳1 و 3 به ترتیب دارای مهر
زمان ۵ ۱۰ و ۱۵ باشند.
* . اگر 1 در خواست منبعی کند که در اختیار 32 باشد, آن منتظر می مائد.
* _ اگر 33 در خواست منبعی کند که در اختیار 32 باشد. آن حذف می شود.
صفحه 10:
پیشگیری بن بست
۴ طرح ]۲۷۵۱0-۷۷۵
۴ _ مبتنی بر تکنیک غیرانحصاری است. نقطه مقابل روش 1۷۷۵1-116
. اكر 21 د خواست منبعی کند که در فعلا اختیار ( باشد. در صورتی که
مهر زمان 31 بیشتر از مهر زمان [ط باشد( جوان تر از ol (cus! Pj
منتظر می ماند. در غير اين صورت [282 حذف با -۲01160
(8016)1«165 می شود( توسط 1 حذف می شود و منبع از آن
گرفته می شود).
۶ مثال: فرض كنيد يروسس هاى 21.12 و 23 به ترتیب دارای مهر زمان
۵ ۱۰ و ۱۵ باشند.
۶ اگر ۳1 در خواست منبعی کند که در اختیار 2 باشد. آنگاه منبع از 32 گرفته
منی شود و 72 حذفامی شود
* اگر 33 در خواست منبعی کند که در اختیار 32 باشد. آن منتظر می ماند.
10
صفحه 11:
11
Wound-wait method
Wait-die method
صفحه 12:
12
Glide! © آزین بست فکنیکی آستا که تصمیم گیری:هآی خود رب
صورت پویا و لحظه ای انجام می دهد. در این روش هر درخواست
منبع توسط پروسس را بررسی می کند. آیا این در خواست مورد
قبول است يا خیر؟
* پیاده سازی اجتناب از بن بست توزیع شده غیر ممکن است.
- هر گره باید حالت سرتاسری سیستم توزیع شده را دنبال کند.
Ke > نمودن حللت امن سرتاسری توسط پروسس ها باید انحصار متقابل
باشد.
7 چک نمودن حالت امن سرتاسری بالاسری محاسبات بسیار زیادی دارد.
صفحه 13:
13
* در این روش به پروسس ها اجازه داده می شود. هر منبعی را در
رخ داد. شناسایی و حذف می شود.
* استفاده از گراف انتظار
7 گراف انتظار محلی در هر سایت: گره های این گراف مطابق با تمامی پروسس های سیستم
توزیع شده است که فعلا منلبع محلی سایت مورد نظر رل در اختیار دارند یا درخواست آن
منابع محلی سایت را دلده اند
- گراف انتظار سرتاسری: لین گراف از اجتماع گراف های انتظار محلی سایت ها ایجاد
می شود.
صفحه 14:
* مثال ۱ : گراف های انتظار محلی دو سایت 51 و 52
صفحه 15:
* قال ۲ گزاف اتتظارسبرتاسری فوسایت 1ص و 92ا قرمقال: ۱
هر 6
صفحه 16:
16
شناسايى بن بست
روش هاى شناسايى بن بست توزيع شده
١ متمرکز: یک سایت وظیفه شناسایی بن بست را بعهده دارد.
۷ «سلسله مزاتبی» سایت ها به صورت: ساختاز درختی رن پست را ilu سي aud
۲ توزیع شده: تمامی پروسس ها در شناسایی پن بست با هم همکاری می کنند.
صفحه 17:
17
روش هاى شناساي, بن بست توزيع شده
Table 18.1 Distributed Deadlock Detection Strategies
Centralized Algorithms Hierarchical Algorithms Distributed Algorithms
Strengths | Weaknesses | Strengths | Weaknesses | Strengths | Weaknesses
+ Not vulnerable |» Deadlock res-
= Algorithms |+ Considerable |» Not vulnera- | » May be di
areeoncep- | communica- | bletosingle | cult toconfig- | tosingle point | olutionis
tuallysimple | tionsover- point offail- | uresystem so | offailure cumbersome
andeasyto | head:every | ure that mostpo- |. No node is because sev-
imptement | nodemust | Deadlock res- | tential dead- |” swamped with | eral sites may
+ Comralsite | sendstatein- | olutiomactivi- | locks are deadlock detect the
hascomplete | formationto | tyistimitedit | localizedioth- | gerection مه
information | centralnode | most potential | erwise there | ومد lock and may
and can opti- |* Vulnerableto | deadlocks are | ™ay actually not be aware
mally resolve | failure of cen- | relatively be more ove of other
deadlocks tral node localized وعم وم nodes in-
distributed volved in the
approach deadlock
+ Algorithms
are difficult
to design
eeause of |
timing eon-
siderations
صفحه 18:
شناسایی بن بست- روش متمرکز
* هرسایت گراف انتظار محلی خود را ایجاد می کند.
۶ رات اصطان Sy galls. بروعسي سما سك سه ااه
می شود.
* یکی از سه روش زیر برای ایجاد پا تغییر گراف انتظار سرتاسری
San اسن استتقاقة شوق
موقعى كه يال جديدى به يكى از كراف هاى انتظار محلى اضافه شود يا يالى حذف شود.
به صورت پریودیک موقعی که تعدا مشخصی از تغییرات در گراف های انتظار محلی داشته باشیم.
۳ _ موقعی که گره هماهنگ کننده نياز به الكوريتم شناسايى سيكل داشته باشد.
18
صفحه 19:
شناسایی بن بست- روش متمرکز
* شناسایی بن بست برمبنای روش ۳
- اضافه نمودن شناسگرهای منحصربفرد (مهرهای زمان) به در خواست های
از سایت های مختلف
موقعی كه 31 از سایت ۸ درخواست منبعی از ژط در سایت 3 می کند.
یک پیام درخواست با مهر زمان 1 ارسال می شود.
- یال [ 31 با برچسب 18 در گراف محلی سایت ۸ اضافه می شود.
اگر 8 پیام درخواست را دریافت نملید و نتولند بلافاصله به درخواست فوق
grant pl, ارسال کند. یال فوق به گراف محلی سایت 8 اضافه مى
شود.
19
صفحه 20:
شناسایی بن بست- روش متمرکز
* الكوريتم:
١ كره هماهنك كننده يك ييام آغازين به تمامى سايت ها ارسال مى كند.
۲ _ هر سایت با دریافت پیام آغازین, گراف انتظار محلی خود رابه گره هماهنگ
کننده ارسال می کند.
۳ _ موقعی که گره هماهنگ کننده از تمامی سایت ها پاسخ دریافت نمود. گراف
انتظار سرتاسری را به صورت زیر ایجاد می کند:
@ ایجاد گراف انتظار سرتاسری, که هر گره آن به یک پروسس اختصاص داده می شود.
0 گراف شامل یال ۳ ۳1 است اگر و فقط اگر
0 یک یال [1-9ظ در یکی از گراف های انتظار محلی داشته باشیم؛ یا
۲ یک یال 317 با تعدادی پرچسب 19 در چند گراف انتظار محلی داشته باشیم.
* اكر گراف ایجاد شده سیکل داشته باشد. آنگاه سیستم در حالت بن بست قرار دارد.
20
صفحه 21:
21
شناسایی بن بست- روش متمرکز
* مثال ۳: گراف های انتظار محلی دو سایت و گراف انتظار سرتاسری ایجاد شده
و 5 Cerys
صفحه 22:
22
Consider the following hierarchical deadlock-detection algorithm, in
which the global wait-for graph is distributed over a number of
different controllers, which are organized in a tree. Each non-leaf
controller maintains a wait-for graph that contains relevant information
from the graphs of the controllers in the subtree below it. In particular,
let Sa, Ss, and Sc be controllers such that Sc is the lowest common
ancestor of S4 and Ss (Sc must be unique, since we are dealing with
a tree). Suppose that node T; appears in the local wait-for graph of
controllers $4 and Sp. Then T; must also appear in the local wait-for
graph of
* Controller Sc
* Every controller in the path from Sc to S4
* Every controller in the path from Sc to Sg
صفحه 23:
شناسایی بن بست- روش سلسله مراتبی
In addition, if T; and Tj appear in the wait-for graph of controller Sp
and there exists a path from T; to T; in the wait-for graph of one of the
children of Sp, then an edge T; — T; must be in the wait-for graph of
Sp.
Show that, if a cycle exists in any of the wait-for graphs, then the
system is deadlocked.
23
صفحه 24:
شناسایی بن بست- روش توزیع شده کامل
* الگوریتم:
\
۲
۳
24
تمامی سایت ها متئولیت یکسان در شتاسایی بن پست: دارند:
هر سایت گراق انتظار محلی خود را ایجاد می کند که آن بخشی از گراف سرناسری است.
در این حالت یک گره اضافی 36 به هر گراف انتظار محلی اضافه می کنیم.
...۳39۳0۷ پوس محلی[۳ منتظر منبعیدر ساینشیگر لسنکه قعلادر لختیر بروسس‌هیگریب اشد
[66312: يروسسواز سايتهيكر منتظر كرقتنهتبع سه فعلادر لختير بروسسرم حل لظ لست
اگر گراف انتظار محلى در يكى از سايت ها شامل سیکل بدون گره 62 باشد. در لین حالت
سپستع در حالت ین پست است.
اگر گراف انتظار محلی شامل سیکل با گره ۳626 باشد. در این حالت سیستم احتمالا د ر حالت
بن بست قرار دارد
برای اثبات
AS سبیستم در حالت بن بست است یا یره ای الگوریتم توزیعی شناسایی بن بست. اجرا شود
صفحه 25:
شناسایی بن بست- روش توزیع شده کامل
* مثال ؟: فرض كنيد دو سايت 51 و 52 دو گراف انتظار محلی به
صورت شکل زیر ایجاد نموده باشند. اگر شروع کننده شناسایی بن
نايك 81 باشد» مراحل شناسایی بن بست را شرح دهید.
PAN
site S, site S,
صفحه 26:
شناسایی بن بست- روش توزیع شده کامل
* حل مثال ۴:
- شناسایی سیکل ۳6 ۳6-۳2-۳3 در سایت 81
- ارسال سیکل فوق به 52
- تغییر گرلف انتظار محلی در سایت 52
- گراف جدید ایجاد شده به صورت شکل زیر است.
ل
2
26
صفحه 27:
27
شناسایی بن بست- روش توزیع شده کامل
* ال هد: مقال ۴رابرای,خالتی تکزار کنید. که شروع کننده: سایت
4
* حل:
- شناسایی سیکل ۳2 ۳43 ۲33 ۲۳63 ۳6۶ در سایت S2
- ارسال سیکل به 51
- تفییر گراف انتظار محلی
صفحه 28:
شناسایی بن بست- روش توزیع شده کامل
* سول: در مثال ۴اگر دو سایث همزمان شناسایی بن بسث را شروع
کنند چه مشکلی پیش می آید؟
* راه حل مشکل:
- شماره گذاری انحصاری پروسس ها با ([1۳)۳
- اگر در سایتی سیکل زیر را داشته باشیم:
Pex > Par > Pra > Pag > Pex
- سایت فوق در صورتی می تواند. شناسایی توزیع شده ین بست را شروع کند که شرط
(,1)۳>(م )10 باشد
* برای مثال قبل اگر wth ID(P1)<ID(P2)<ID(P3)<ID(P4) چون
(11()۳2(>11«)۳3 باشد. شروع کنند سایت 82 خواهد بود.
28
صفحه 29:
29
شناسایی بن بست- روش دوم توزیع شده
* به ازای هر شتی داده(:010[66 12۵18) دو پارامتر شناسگر منحصر بفرد
Di و متغییر (1001660_)1 تعریف می شود.
به ازای هر تراکنش [ چهار پارامتر زیر تعریف می شود:
شناسگر منحصربفرد [1'
متغيير Held_by(Tj)
متغییر ((0۳)1] ان ۷۷
Request_Q(Tj) صف
صفحه 30:
شناسایی بن بست- روش دوم توزیع شده
* امتال فرضن کنبدعراکش:12 متظرقعی خادهرای است: کهد
اختیار, 1.1 استتوساب. منتظر شنی داده ای است که در اختیار 10 است.
جدول توزیعی پارامترهای تراکنش را بدست آورید.
Request_Q
Ty
12
nil
30
Held_by
nil
To
Ty
Wait_for
nil
To
Ty
Transaction
qo
Ty
1۳
صفحه 31:
31
شناسایی بن بست- روش دوم توزیع شده
صفحه 32:
شناسایی بن بست- روش دوم توزیع شده
* مثال ۷: در الگوربتم شناسایی بن بست توزیع شده. جدول زیر رابا توجه شکل
گراف تراکنش های داده شده کلمل نمائید.لگر تراکتش ,]یک درخواست برای شئی
داده (121۵-0[[06) نگه داشته توسط و1 ارسال نملید. جدول تغییر یافته
پارامترها را بدست آورید و نحوه ی تشخیص بن بست را در این الگوریتم شرح دهید.
OOO)
9
32
صفحه 33:
33
شناسایی بن بست- روش دوم توزیع شده
* حل مثال ۷
وروی سلس و علد سير له مسالا (asta tem bere request
صفحه 34:
بن بست در تبادل پیام ها
* انواع
7 بن بست انتظار متقابل و دو جانبه
- عدم دسترسی بافرهای پیام ها
34
صفحه 35:
35
بن بست در تبادل پیام هاانتظار متقابل
* بن بست انتظار متقلبل در تبادل پیام موقعی رخ می دهد که هر
کدام از عضوهای پروسس یک گروه منتظر پیام از عضو دیگر از
همان گزوه استت و پیات | opt all lay
* تعریف مجموعه وابستگی(1(5)
7 برای پروسس ۳1 که متوقف و منتظر دریا
شامل تمامی پروسس های است که از ط
ely دارند.
م است. DS(Pi)
ر دریافت حداقل یک
21 در صویتیمی‌تولند به کار خود ادلمه دهد که حدلقلیک
پیام از مجموعه ولبستگی(۳1) 125 در بافشماید
صفحه 36:
فى مصسصيور لاقل jie eos play
*بن بست در یک مجموعه پروسس های ٩ را می توان به
صورت زیر تعریف انمود:
أ تمامی پروسس های مجموعه ٩ متوقف و منتظر دریافت پیام(ها)
هستند.
۲ مجموعه 5٩ شامل مجموعه های وابستگی تمامی پروسس ها با عضوهای
مجموعه ی ٩ است.
۳ پیامی بین عضوهای 5 ارسال نمی شود.
36
صفحه 37:
بن بست در تبادل پیام هاانتظار متقابل
#تجال بدو lat oil) ay. (Si gy aed oad jibes eal
بكيريد و بن بست تبادل پیام را بررسی نمایید.
©
(a) No deadlock (by Deadlock
Figure 18.16 Deadlock in Message Communication
37
صفحه 38:
بن بست در تبادل پیام ها-انتظار متقابل
* حل مثال ۸:
S={P1,P2,P3} . DS(P1)={P5,P2} . wb @Lss » -
2 منتظر دریافت پیام از 1 5, DS(P3)={P , DS(P2)={P3}
پا 35 است. چون 35 منتظر پیام نمی باشد و می تولند پیام به 31 ارسال کند. در
نتیجه پیوند (۳1,۳5) و (۳1,۳2) حذف می شوند و بنابراین بن بست نداریم.
- در شکل(6 داریم: ۰ S={P1,P2,P3,P5} . DS(P1)={P5,P2}
(25)۳2(<]۳3 و ۳) <(129)۳3. در اين شکل یک وابستگی اضافه می شود.
در اين حللت 35 منتظر پیام از 2 .۳2 منتظر پیام از 3 33۰ منتظر پیام از 21 و
1 منتظر پیام از 32 است. در نتیجه در این شکل بن بست تبادل پیام خواهیم داشت.
38
صفحه 39:
39
بن بست در تبادل پیام ها-عدم دسترسی
بافرهای پیام ها
© عموماً در شبکه های راهگزینی بسته ای وجود دارد.
* ساده ترين شکل بن بست شبکه های راهگزینی بسته ای بن بست
ذخیره سازی (Store and forward) gl> a jlesl s
است.
* برای هر گره. صف گره مجاور در یک جهت با بسته های جهت
آرسال .به گوه بعدی:پر شده است.
صفحه 40:
40
ها
بست مستقیم ذخیره سازی و انتشار به جلو
Buffer Buffer
pool full poo! full
(a) Direct store-and-forward deadlock
صفحه 41:
بن بست غير مستقيم ذخيره سازى و انتشار به جلو
* برای هر گره. صف گره مجاور در يك جهت با بسته هاى جهت
ارسال :ه دحوم ۰ هه ۱
Filled with,
packets t0 C
Filled with,
packets to D
Filled with,
packets to B
Filled with Filled with,
packets to E
(by Indirect store-and-forward deadlock 41
صفحه 42:
فتیغ:پاف: نساختیافته
منبع حافظه ی سطح صفر بدون محدودیت است و هر بسته ورودی می تولند در لین سطح
ذخیره شود.
برای سطوح ۱ تا (1): ۷ بافرهای سطوح ۱ تا برای بسته های با 1 گام (۳) اگر تمامی بافرها تا
سطح ۲ پر شده باشند, بسته های رسیده با :1 گام یا کمتر حذف می شوند.
Buffer space for
packets that h:
traveled k hops
42