دانلود فایل پاورپوینت سیستم های عامل توزیع شده

بخشی از پاورپوینت

--- پاورپوینت شامل تصاویر میباشد ----

اسلاید 1 :

مقدمه

در مواردي سايت‌ها بايد با هم به توافقي برسند. مثلاً تصميم به Ab rt يا C mmit در DBSs.

هر سايت بايد از مقادير سايت‌هاي ديگر مطلع باشد.

تصميم در غياب خطا ::

تصميم در حضور خطا û؟ چرا كه سايت‌هاي خطادار مقادير غلطي مي‌فرستند.

فرض: وجود يك مدل عمومي از خطا: ارسال پيغام مشكوك به ديگران، پايين بودن سايت، پاسخ درست ندادن به پيغام‌ها.

نكته: پردازه‌هاي سالم خبري از پردازه‌هاي خراب ندارند.

اسلاید 2 :

مدل

تا‌ پردازنده در سيستم وجود دارد كه m تاي آنها خطادار هستند.

سيستم منطقاً كاملاً مرتبط است.

تنها خطاي پردازنده مطرح است و خطاي رسانه ارتباطي نداريم.

براي سادگي فرض بر توافق روي مقدار صفر و يك است.

محاسبات همگام: پردازنده‌هاي سيستم در يك حالت قفلي/مرحله‌اي عمل مي‌كنند. هر پردازه پيغامي كه در مرحله قبل ارسال شده بود را دريافت مي‌كند، محاسبه‌اي انجام مي‌دهد و پيغام‌هايي را ارسال مي‌كند.

   هر مرحله را يك r u d مي‌ناميم. تأخير پيغامي يا سرعت كند يك پردازنده كل محاسبات را كند مي‌كند.

پيغام‌ها -Authe ticated‌ هستند: پردازنده‌اي مي‌تواند پيغامي را جعل كند و يا محتويات ان را عوض كند و سپس آن را رله كند.

اسلاید 3 :

ازريابي كارايي

زمان : تعداد دور

ترافيك پيغامي

سربار حافظه‌اي

اسلاید 4 :

دسته‌بندي مسائل توافقي

1- توافق Byza ti e

   مقدار اوليه‌اي كه قرار است روي آن توافق شود توسط پردازنده‌اي بي‌خطا اعلام و همه پردازنده‌هاي بي‌خطا مجبور به توافق روي آن مقدار هستند.

  راه‌حل اين مسئله بايد:

1- توافق: توافق همه پردازنده‌هاي بي‌خطا روي آن مقدار مشترك.

2- اعتبار: اگر پردازنده مبدأ بي‌خطاست، مقدار توافق شده همان مقدار اوليه باشد.

نكته: اگر مبدأ خطادار باشد، پردازنده‌هاي بي‌خطا روي هر مقدار مشتركي مي‌توانند توافق كنند.

مهم نيست كه پردازنده‌هاي خطادار روي چه مقدار مشتركي توافق كرده‌اند و يا اصلاًً توافق كرده‌اند. 

اسلاید 5 :

دسته‌بندي مسائل توافقي(ادامه)

2- اجماع

   هر پردازنده مقدار اوليه خود را منتشر مي‌كند. همه پردازنده‌هاي بي‌خطا بايد روي مقدار مشتركي توافق كنند.

3- سازگاري محاوره‌اي(I teracti e C siste cy)

  هر پردازنده مقدار اوليه خاص خود را دارد. همه پردازنده‌ها روي مجموعه يكساني توافق مي كنند.

اگر پردازنده‌اي خطا دارد (مثل j )، سپس همه پردازنده هاي بي‌خطا مي‌توانند روي هر مقدار مشترك براي j توافق داشته باشند (.( j 

اسلاید 6 :

راه‌حل براي مسئله توافق Byza ti e

اولين بار توسط لمپورت

پردازنده‌ها مقاديرشان را مي‌فرستند و مقادير دريافت شده را رله مي‌كنند.

پردازنده‌هاي خطادار ممكن است بقيه را گيج كنند ( به خاطر فرستادن مقادير گمراه كننده يا رله مقادير جعلي).

مهم است كه پردازنده‌هاي بي‌خطا از خطادارها در امان باشند. تعداد خطادارها نبايد از سقفي تجاوز كند.

Pease و همكارانش نشان دادند كه اگر m (تعداد خطادارها) از           تجاوز كند نمي‌توان به توافق رسيد.

اسلاید 7 :

نتيجه غيرممكن:

  توافق Byza ti e نمي‌تواند بين سه پردازنده كه يكي از آنها خطادار است حاصل شود. اگر سه پردازنده P0، P1 و P2 را در نظر بگيريم كه هر يك دو مقدار صفر و يك دارند:

  P0 آغاز مي‌كند. دو حالت:

1-  P0 بدون خطا و مثلاً P2 خطادار است. P0 مقدار خود را پخش مي‌كند.

اسلاید 8 :

2-  P0 خطادار است و P1 و P2 سالم.

با سه پردازنده كه يكي خطادار است نمي‌توان توافق داشت.

اسلاید 9 :

الگوريتم Lamp rt-Sh stak-Pease

مشهور به الگوريتم پيغام‌هاي شفاهي ral Msgs ( M(m)) كه مسئله را براي 3m+1( يا بيشتر) پردازنده در حضور حداكثر m پردازنده خطادار حل مي‌كند.

M(0)

1- پردازنده مبدأ مقدار اوليه‌اش را براي همه مي‌فرستد.

2- هر پردازنده، مقداري را كه از مبدأ گرفته است استفاده مي‌كند (اگر مقداري دريافت نكرد صفر در نظر مي گيرد).

اسلاید 10 :

الگوريتم Lamp rt-Sh stak-Pease (ادامه)

M(m) (m>0)    

.1پردازنده مبدأ مقدار اوليه‌اش را براي همه مي‌فرستد.

.2براي هر i، اگر i مقداري باشد كه پردازنده از مبدأ دريافت مي‌كند (اگر دريافت نكند پيش فرض صفر است)، پردازنده i به عنوان مبدأ جديد عمل كرده و M(m-1) را آغاز مي‌كند كه i را به -2 پردازنده ديگر مي‌فرستد (به جز مبدأ و خودش).

.3براي هر i و j (i¹j) اگر j مقداري باشد كه i از j دريافت كرده است (با استفاده از M(m-1) در قدم 2)، سپس پردازنده i مقدر زير را محاسبه مي كند و به كار مي‌برد (به عنوان تصميم).

Maj r ty( 1, 2, …, -1)