نوع فایل: word
قابل ویرایش 53 صفحه
چکیده:
الگوریتم تشخیص گره خوردگی توزیع شده
ما الگوریتمی را برای تشخیص گره خوردگی به هنگام اجرای هم زمان عملکردهای تبادلی در شبکه پروسه‌ای توزیع شده ( مثلا سیستم توزیعی داده ها) پیشنهاد می کنیم. این الگوریتم پیشنهادی یک الگوریتم تشخیص گره خوردگی توزیع شده میباشد. برهان صحت بخش توزیع شده الگوریتم با ارائه مثالی از الگوریتم در حال عملکرد بیان شده است. ویژگیهای عملکردی الگوریتم نیز ارائه شده است .
طبقه بندی و توضیح موضوع :
( شبکه های ارتباطی کامپیوتر) ( C.2.4 (، سیستم توزیع شده، ( سیستم عملکردی) ( D.4.1) مدیریت پروسه ها ، گره خوردگی ها، (سیستم عملکردی ) ( D.4.7) طراحی و سازماندهی سیستم توزیعی.
مقدمه:
از آنجائی که اکثر سیستم‌های پروسه‌ای توزیع شده بویژه سیستم اطلاعاتی توزیع شده احرا میشوند نیاز به الگوریتم تشخیص گره خوردگی توزیع شده آشکارتر میشود. اگثریت مکتوبات در رابطه با تاخیر، منبع، گراف، و تبادل‌ها بحث‌هایی کرده‌اند. در این تحقیق هم اصطلاحات مشابهی بکار رفته است. تمامی لغات ایجاد شده توسط نویسنده در داخل گیومه بوده و حرف آغازین آن حرف بزرگ میباشد.
تعریف تبادل که در این تحقیق مورد استفاده قرار گرفته است، با تعاریف موجود در 3 و 8 همسان میباشد. واژه تبادل یک واژه انتزاعی مناسب برای پروسه های کاربری میباشد که شامل نگهداری اصولی از سیستم میباشد که اطلاعات را از یک شرایط ثابت به شرایط ثابت دیگر تغییر میدهد بطوریکه این انتقال به نظر نمی‌رسد.
اگر در حین یک انتقال خطایی رخ دهد، هر گونه تغییرات ایجاد شده توسط تبادل ناتمام باقی می ماند تا اینکه پایگاه اطلاعاتی به یک سایت ثابت بازگردد. برای دسترسی همزمان به پایگاه اطلاعاتی مکانیسم های کنترل همزمانی همچون قفل شدگی مورد استفاده قرار میگیرد.
استفاده از قفل کردن برای کنترل همزمانی این امر را میسر میکند که انجام یک تبادل ، کار تبادل دیگر را قفل کند و این تبادل به تعویق افتد. وقتی که تبادلی به تعویق می افتد، در انتظار تبادل دیگری می ماند و تبادل دوم هم در انتظار تبادل اول میماند و نتیجه آن یک تاخیر چرخه ای است که وقفه نامیده میشود.
الگوریتم های زیادی وجود دارند که در سیستم های اطلاعاتی مرکزیت یافته اند و برای تشخیص وقفه اجرا میشوند. تمامی این الگوریتم ها بر اساس تشخیص چرخه ها در گراف های تاخیری میباشد که در آن گره‌های گراف برای نشان دادن تبادل با لبه های مستقیمی که نشانگر تبادل با تاخیر میباشد، مورد استفاده قرار گرفته است. هنگامیکه چرخه ها در (TWFG) یافت میشوند، این چرخه ها از طریق انتخاب تبادلی که در چرخه وجود داردو از طریق متوقف ساختن تبادل خود نیز متوقف میشوند( معمولا این اجازه به تبادل داده میشود که فعالیت خود را با با داده اصلی خود از نو آغاز کند ). این عملکرد به هنگام توزیع (TWFG ) در قسمت های چند گانه و یا در پایگاه اطلاعاتی پیچیده تر میشود.
در یک سیستم اطلاعاتی توزیع شده گر چه تبادل تمامی تمامی فرایند ها را در قسمت ایجاد شده انجام میدهد، ولی میتواند خارج از محل اصلی خود هم کارهایی را انجام دهد. اگر یک چنین اتفاقی بیافتد، یک عامل 4 در قسمت دوری ایجاد میشود تا تبادل را در این قسمت نشان دهد. این عامل قسمتی از تبادل اصلی برای کنترل همزمانی و اصلاحات می باشد.
فهرست مطالب:
چکیده
فصل اول: مقدمه
واژه متداول الگوریتم
1-1- مقدمه
فصل دوم: کارهای مرتبط با بن بست در سیستم توزیع شده
1-2- مقدمه
2-2- وقفه های موجود در سیستم توزیع شده
3-2- تشخیص وقفه متمرکز شده
4-2- تشخیص وقفه توزیع شده
5-2- جلوگیری از وقفه توزیع شده
فصل سوم: بیان مسئله
1-3- بیان مسئله
2-3- مثال و ساده تر کردن فرضیه
1-2-3- الگوریتم تشخیص
2-2-3- دلایلی برای صحت الگوریتم
3-2-3- وقفه های اشتباه
4-2-3- مثالی برای پردازش تشخیص وقفه
5-2-3- بررسی کارایی
6-2-3- فرمول محاسبه مورد نرمال پیش بینی شده
7-2-3- محاسبه مورد پیش بینی شده
8-2-3- مقایسه با الگوریتم متمرکز شده
فصل چهارم: نتیجه‌گیری
نتیجه گیری
مراجع
منابع و مأخذ:
- GLIGOR, V.D., AND SHATTUCK, S.H. On deadlock detection in distributed systems. Computer Science Tech. Rep. 837, University of Maryland, College Park, Md., Dec. 1979.
- GOLDMAN B. Deadlock detection in computer networks. Tech. Rep. M.I.T.-LCS TR-185, Massachusetts Institute of Technology, Cambridge, Mass., Sept. 1977.
- GRAY, J.N. Notes on data base operating systems. In Operating Systems An Advanced Course,
- Bayer, R.M. Grahm, and G. Segmuller, (Eds.), Lecture Notes in Computer Science, vol. 60, Springer-Verlag, Berlin and New York, 1978.
- GRAY, J.N. A discussion of distributed systems. Res. Rep. RJ2699(34594), IBM Research Division, Sept. 1979.
- GRAY, J.N., HOMAN, P., OBERMARCK, R., AND KORTH, H. A straw man analysis of probability of waiting and deadlock. Res. Rep. RJ3066(38112), IBM Research Division, Feb. 1981 (presented at the 5th Berkeley Workshop on Distributed Data Management and Computer Networks, Feb. 1981).
- JOHNSON, D.B. Finding all the elementary cycles of a directed graph. SIAM Comput. 4,l (March 1975), 77-84.
- MENASCE, D., AND MUNTZ, R. Locking and deadlock detection in distributed data bases. IEEE Trans. Softw. Eng. SE-5,3 (May 1979), 195-202.
- OBERMARCK, R. Distributed data base. IBM Palo Alto Systems Center Tech. Bull. G320-6019, IBM, Palo Alto, Calif,, Sept. 1978.
- ROSENKRANTZ, D.J., STEARNS, R.E., AND LEWIS, P.M. II. System level concurrency control for distributed database systems. ACM Trans. Database Syst. 3,2 (June 1978), 178-198.
پروژه بررسی الگوریتم های Deadlocle و بهینه سازی آن. doc