تحقیق درباره بررسی تشخیص بن بست در سیستم‌های توزیع شده

فرمت فایل : word (قابل ویرایش) تعداد صفحات : 97 صفحه

فهرست مطالب

مقدمه................................................................. 1

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

1-1- مفاهیم پایه......................................................... 3

1-2- انواع مدلهای بن‌بست بر اساس سیستم تبادل پیام.......................... 3

1-3- انواع مدلهای بن‌بست بر اساس نوع درخواست............................ 3

1-4- شرایط وجود بن‌بست.................................................. 5

1-5- طبقه‌بندی الگوریتم‌های تشخیص بن‌بست................................ 5

فصل دوم: مروری بر الگوریتم‌های تشخیص بن‌بست............................. 9

مقدمه....................................................................10

2-1- نمونه‌ای از الگوریتم متمرکز جهت تشخیص بن‌بست در سیستمهای توزیع‌شده..... 10

2-1-1- الگوریتم هو- رامامورتی........................................... 10

2-2- نمونه‌ای از الگوریتم‌های تشخیص بن‌بست سلسله‌مراتبی................... 11

2-2-1- الگوریتم منساس – مانتر............................................ 11

2-2-2- الگوایتم هو – رامامورثی....................................... 11

2-3- نمونه‌هایی از الگوریتم‌های توزیع‌شده............................... 11

2-3-1- الگوریتم تشخیص بن‌بست چندی – مسیرا – هاس...................... 11

2-3-2- الگوریتم محاسبه پخش کردن چندی – مسیرا – هاس..................... 12

2-3-3- الگوریتم براچا – توگ............................................. 13

2-3-4- الگوریتم منساس و مانتز2-3-5- الگوریتم ابرمارک..................... 13

2-3-5- الگوریتم ابرمارک................................................ 14

2-3-6- الگوریتم بدالض...................................................... 15

فصل سوم: مروری بر الگوریتم‌های تشخیص بن‌بست توزیع شده تعقیب یال.......... 20

مقدمه............................................................... 21

3-1- بررسی الگوریتم‌های تشخیص بن‌بست تعقیب یال......................... 22

3-1-1- الگوریتم میچل و مریت........................................... 22

3-1-2- الگوریتم سینها و ناتارجان......................................... 23

3-1-3- الگوریتم چودهاری – کوهلر – استنکویچ و توسلی................... 23

3-1-4- الگوریتم سینقال و شمکالیانی........................................ 24

3-1-5- تشخیص بن‌بست توزیع شده و حل آن بر اساس ساعتهای سخت‌افزاری....... 24

3-2- ارائه روشی برای حذف بن‌بست نادرست در الگوریتم‌های تشخیص بن‌بست...... 25

3-3- نتیجه‌گیری........................................................... 27

فصل چهارم: الگوریتم‌های تشخیص بن‌بست توزیع شده تحمل خطاپذیر............. 29

مقدمه........................................................ 30

4-1- مروری بر الگوریتم‌های تحمل‌پذیر خطا جهت تشخیص بن‌بست.............. 31

4-2- معرفی مدل سیستم تشخیص خرابی بر اساس شاخص زمان اتصال.............. 33

4-3- یک الگوریتم تشخیص بن‌بست توزیع شده تحمل‌پذیر خطا................... 34

4-4- اثبات درستی الگوریتم.............................................. 37

4-5- نتیجه‌گیری......................................................... 38

فصل پنجم: تشخیص و حل بن‌بست در سیستمهای نماینده موبایل................. 39

مقدمه............................................................... 40

5-1- معرفی سیستمهای نماینده موبایل(نسل آینده سیستمهای توزیع شده)............... 41

5-2- تشخیص بن‌بست توزیع‌شده در سیستمهای نماینده موبایل.................. 41

5-3- معایب الگوریتم اصلی و مشکلات کارایی الگوریتم...................... 44

5-4- الگوریتم تشخیص بن‌بست توزیع شده مبتنی بر اولویت بهبودیافته................. 47

5-4-1- آنالیز کارایی الگوریتم بهبودیافته.................................... 48

5-4-2- اثبات درستی الگوریتم............................................ 49

5-5- نتیجه‌گیری....................................................... 50

نتیجه‌گیری.............................................................. 51

فهرست منابع............................................................... 53

پیوست‌ها................................................................ 55

 

جدول 2-1- مقایسه الگوریتم های بررسی شده تشخیص بن بست.................... 17

جدول 2-2- مقایسه کارایی الگوریتم های بررسی شده........................... 19

جدول 3-1- مقایسه مدل های الگوریتم های بررسی شده کلاس تعقیب یال......... 27

جدول3-2-  بررسی صحت الگوریتم های بررسی شده.......................... 28

مقدمه

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

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

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

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

تشخیص بن بست در سیستم‌های توزیع شده

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

قالب بندی:word

تعدادصفحه:62

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

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

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

 فهرست:

مقدمه  

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

1-1- مفاهیم پایه       

1-2- انواع مدلهای بن‌بست بر اساس سیستم تبادل پیام  

1-3- انواع مدلهای بن‌بست بر اساس نوع درخواست       

1-4- شرایط وجود بن‌بست      

1-5- طبقه‌بندی الگوریتم‌های تشخیص بن‌بست  

فصل دوم: مروری بر الگوریتم‌های تشخیص بن‌بست  

مقدمه  

2-1- نمونه‌ای از الگوریتم متمرکز جهت تشخیص بن‌بست در سیستمهای توزیع‌شده        

2-1-1- الگوریتم هو- رامامورتی

2-2- نمونه‌ای از الگوریتم‌های تشخیص بن‌بست سلسله‌مراتبی     

2-2-1- الگوریتم منساس – مانتر        

2-2-2- الگوایتم هو – رامامورثی         

2-3- نمونه‌هایی از الگوریتم‌های توزیع‌شده       

2-3-1- الگوریتم تشخیص بن‌بست چندی – مسیرا – هاس       

2-3-2- الگوریتم محاسبه پخش کردن چندی – مسیرا – هاس   

2-3-3- الگوریتم براچا – توگ  

2-3-4- الگوریتم منساس و مانتز2-3-5- الگوریتم ابرمارک        

2-3-5- الگوریتم ابرمارک        

2-3-6- الگوریتم بدالض

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

مقدمه  

3-1- بررسی الگوریتم‌های تشخیص بن‌بست تعقیب یال   

3-1-1- الگوریتم میچل و مریت

3-1-2- الگوریتم سینها و ناتارجان       

3-1-3- الگوریتم چودهاری – کوهلر – استنکویچ و توسلی        

3-1-4- الگوریتم سینقال و شمکالیانی   

3-1-5- تشخیص بن‌بست توزیع شده و حل آن بر اساس ساعتهای سخت‌افزاری    

3-2- ارائه روشی برای حذف بن‌بست نادرست در الگوریتم‌های تشخیص بن‌بست   

الف

 

3-3- نتیجه‌گیری       

فصل چهارم: الگوریتم‌های تشخیص بن‌بست توزیع شده تحمل خطاپذیر      

مقدمه  

4-1- مروری بر الگوریتم‌های تحمل‌پذیر خطا جهت تشخیص بن‌بست      

4-2- معرفی مدل سیستم تشخیص خرابی بر اساس شاخص زمان اتصال  

4-3- یک الگوریتم تشخیص بن‌بست توزیع شده تحمل‌پذیر خطا  

4-4- اثبات درستی الگوریتم    

4-5- نتیجه‌گیری       

فصل پنجم: تشخیص و حل بن‌بست در سیستمهای نماینده موبایل   

مقدمه  

5-1- معرفی سیستمهای نماینده موبایل(نسل آینده سیستمهای توزیع شده)        

5-2- تشخیص بن‌بست توزیع‌شده در سیستمهای نماینده موبایل  

5-3- معایب الگوریتم اصلی و مشکلات کارایی الگوریتم   

5-4- الگوریتم تشخیص بن‌بست توزیع شده مبتنی بر اولویت بهبودیافته   

5-4-1- آنالیز کارایی الگوریتم بهبودیافته

5-4-2- اثبات درستی الگوریتم 

5-5- نتیجه‌گیری       

نتیجه‌گیری     

فهرست منابع   

تحقیق درباره بررسی و ارزیابی عملکرد و کاریرد سیستم های توزیع شده

فرمت فایل : word (قابل ویرایش) تعداد صفحات : 148 صفحه

مقدمه

قبل از ابداع کامپیوترهای شخصی،  عملا" برنامه های توزیع شده ای  وجود نداشته است . در آن دوران ، استفاده از کامپیوتر،  شامل نشستن پشت یک ترمینال و برقراری ارتباط با یک سیستم بزرگ (Mainframe) بود. با اینکه ترمینال ها در  چندین ساختمان و یا حتی محل فیزیکی قرار می گرفتند ،  ولی عملا"  یک کامپیوتر مرکزی وجود داشت که مسئولیت  انجام تمامی پردازش ها و ذخیره سازی  داده ها را برعهده می گرفت .

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

تعریف سیستم توزیع شده:

هر سیستمی که بر روی مجموعه ای از ماشین ها که دارای حافظه اشتراکی نیستند، اجرا شده و برای کاربران به گونه ای اجرا شود که گویا بر روی یک کامپیوتر می باشند ، یک سیستم توزیع شده است.

در یک سیستم توزیع شده :

یک نرم افزار یا مجموعه نرم افزاری واحد و متحد الشکل بر روی هر گره اجرا می شود.

همه ماشینها یک کرنل مشابه را اجرا می کند. هر کرنل منابع خود را کنترل می کند

 چرا به برنامه های توزیع شده نیاز داریم ؟

در این رابطه دلایل متعددی عنوان می شود که مهمترین آنان عبارتند از :

هزینه سیستم های Mainfarme  . یکی از اولین دلایل مهم ، هزینه های بالای سیستم های Mainframe است . این مسئله از دو زاویه متفاوت قابل بررسی است : هزینه بالای سرمایه گذاری اولیه که بسیاری  از سازمان ها و موسسات توان مالی آن را ندارند و دوم اینکه در این مدل ، دارای صرفا" یک نقطه  آسیب پذیر با ریسک بالا می باشیم .

مالکیت اختصاصی داده ها. یکی از فاکتورهای مهم دیگر،  سیاست های مربوط به مالکیت داده ها است . سازمان ها و موسسات که  دارای داده های اختصاصی خود می باشند،  علاقه مند به واگذاری مسئولیت مدیریت داده های مربوطه ،  به سایر مکان های فیزیکی نمی باشند .

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

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

قابلیت اطمینان:

در دسترس بودن یک فاکتور مهم مرتبط با این سیستم ها است. طراحی نباید به گونه ای باشد که نیاز به اجرای همزمان کامپوننت های اساسی باشد. افزونگی بیشتر داده هاه باعث افزایش در دسترس بودن شده اما ناسازگاری را بیشتر میکند.

قدرت تحمل نقص(Fault tolerance) باعث پوشاندن خطاهای ایجاد شده توسط کاربر می شود.

 کارآیی:

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

 قابلیت گسترش:

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

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

انتقال پیام Message Passing

فراخوانی از راه دور رویه ها Remote Procedure Call

سیستم توزیع شده از دید لایه بندی ها

برنامه های کاربردی

DBMS,TPS, …

سیستم عامل توزیع شده

سخت افزار

بخشهای اصلی سیستم عامل توزیع شده

مدیریت فایل مدیریت منابع مدیریت حافظه مدیریت فرآیندهاKernel

سیستم عامل توزیع شده باید امکانات Encapsulating منابع را مهیا سازد. کرنل و سرورها هر دو وظیفه مدیریت منابع را بر عهده دارند و چون شامل منابع نیز می باشند، باید موارد زیر را مهیا سازند:

مجتمع سازی داده ها و سرویس ها Encapsulating

پردازش همزمان

محافظت داده ها

نحوه دسترسی به منابع

کلاینتها با مشخص سازی منابع در آرگومان عملیات (فراخوانی از راه دور رویه ها در سرور یا فراخوانی سیستم در کرنل)به آنها دسترسی پیدا می کنند.

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

فصل دوم

محاسبات توری

(Grid computing)

مقدمه‌ای بر محاسبات توری (Grid computing)

مسأله گرید

گرید و مفاهیم دیگر از محاسبات توزیعی

محاسبات توری چیست؟

فواید محاسبات توری

بهره برداری از منابع مورد استفاده

ظرفیت پردازنده موازی

منابع مجازی و سازمانهای مجازی باری مشارکت

دستیابی به منابع اضافی

توازن منابع

قابلیت اطمینان

مدل معماری گرید

ارزیابی معماری گرید

ارزیابی معماری محاسبات گرید و مدل‌های گرید Adoption

استانداردها برای محیط‌های گرید

استاندارد OGSI

استاندارد گرید FTP

استاندارد WSRF

استانداردهای مرتبط با سرویس‌های وب

معرفی امنیت گرید (گرید Security)

نیازهای امنیتی گرید

چالش‌های امنیتی موجود در محیط یک گرید

دامنه‌های امنیتی گرید

اصول امنیت

اصطلاحات مهم در رابطه با امنیت گرید

The Certificate Authority

اسناد دیجیتالی

انواع متفاوت Certificate‌‌ها

چگونگی دسترسی به گرید

Authentication & Aithorization

SSL Handshake

طراحی گرید

اهداف راه حل

توپولوژی گرید

Intra گرید

Extra گرید

Inter گرید

بررسی برخی از پروژه‌های گرید

Search for Extra Terrestrial Intelligence: SETI @ Home NaREGI

Folding @ Home

Google

(Basic Local Alignment Search tool) BLAST

گرید Sim چیست؟

معماری سیستم

موجودیت‌های گرید Sim

ادامه...