فایل های مشابه شاید از این ها هم خوشتان بیاید !!!!
توضیحات محصول دانلود پاورپوینت دسته بندی الگوریتم‌ها و تحلیل و ارزیابی آن ها (کد12929)
دانلود پاورپوینت دسته بندی الگوریتم‌ها و تحلیل و ارزیابی آن ها
\nDistributed Mutual Exclusion
\n\n عنوان های پاورپوینت :
\n\n\nدسته بندی الگوریتم‌ها و تحلیل و ارزیابی آن ها
\nDistributed Mutual Exclusion
\nمقدمه
\nدسته بندی الگوریتم‌ها
\nتعاریف اولیه
\nملزومات الگوریتم های M.E.
\nمعیارهای کارآیی
\nالگوریتم لمپورت
\nالگوریتم لمپورت (درخواست ورود به CS)
\nالگوریتم لمپورت (اجرای CS)
\nالگوریتم لمپورت (خروج از CS)
\nمثال
\nچند نکته
\nالگوریتم ریکارت – آگراوالا (Ricart-Agrawala)
\nمثال
\nالگوریتم میکاوا
\nیک الگوریتم غیرمبتنی برمهره عمومی
\nیک الگوریتم غیرمبتنی برمهره عمومی-ادامه
\nالگوریتم عمومی ! (Generalized)
\nالگوریتم عمومی (Generalized)-تحلیل
\nالگوریتم‌های مبتنی بر مهره
\nالگوریتم‌های سوزوکی و کاسامی
\nالگوریتم سینگهال
\nالگوریتم درخت مبنای ریموند
\nالگوریتم درخت مبنای ریموند-درخواست CS
\n \n\n \n\n \n\n
\n\nقسمت ها و تکه های اتفاقی از فایل\n\n \n\nالگوریتم عمومی (Generalized)-تحلیل\n\nالگوریتم عمومی استراتژی‌های الگوریتم‌های ریکارت-آگراولا و میکاوا را با هم ترکیب کرده است.\n\nدر هر دو اجازه یک مجموعه لازم بود. در الگوریتم ریکارت-آگراولا، هر سایت می‌توانست GRANT را به طور همروند به تعداد زیادی سایت بدهد. در الگوریتم میکاوا، یک سایت اجازه را در هر لحظه تنها به یک سایت می‌داد.\n\nدر الگوریتم عمومی، سایت Si اجازه از نوع الگوریتم میکاوا را از همه سایت‌های موجود در Ii به دست می‌آورد و از سایت‌های Ri - Ii اجازه از نوع ریکارت-آگراوالا می‌گیرد.\n\nدر حقیقت اگر گزاره اول G2 برای همه سایت‌هایSi و Sj غلط باشد، پس الگوریتم ریکارت-آگراوالا عمل شده است. اگر گزاره دوم G2 برای همه سایت‌های Si و Sj غلط باشد پس الگوریتم میکاوا عمل شده است. اگر برای بعضی گزاره اول و برای بعضی گزاره دوم، پس الگوریتم عمومی نتیجه شده است.\n\nالگوریتم‌های مبتنی بر مهره\n\nیک مهره بین همه سایتها مشترک است و مبنای ورود به CS است.\n\nبر اساس روش جستجوی مهره الگوریتم‌های متفاوتی وجود دارد.\n\nاز Sequence# به جای زمان‌مهر استفاده می‌کنند. هر سایت شماره ترتیب خود را هر بار که تقاضای مهره می‌کند افزایش می‌دهد.\n\nاثبات ساده است ولی فقدان قحطی و بن بست، مورد دارد.\n\nالگوریتم‌های سوزوکی و کاسامی\n\nاگر سایتی که متقاضی است مهره در اختیار ندارد مهره (REQUEST) را به همه پخش می‌کند.\n\nسایت دارنده مهره، با رسیدن REQUEST مهره را به سایت درخواست کننده می‌فرستد مگر آنکه در حال اجرای CS باشد.\n\nموارد اصلی در طراحی این الگوریتم:\n\nتمایز بین درخواست‌های کهنه و درخواست‌های جدید: \n\nدرخواست فرم REQUEST (j , n) دارد.\n\nتشخیص سایت با درخواست معوق. \n\nالگوریتم‌های سوزوکی و کاسامی-ادامه\n\nآرایه صحیح LN[1..N] که LN[j] شماره ترتیب درخواستی است که Sj اخیراً اجرا کرده است. پس از اجرای CS، LN[i]=RNi[i]. اگر RNi[j]=LN[j]+1 باشد Sj متقاضی مهره است. پس از خروج از CS، سایت‌های متقاضی در صف قرار گرفته و مهره به سر صف داده می‌شود.\n\nالگوریتم:\n\nدرخواست ورود به CS\n\nاگر Si (متقاضی) مهره را در اختیار ندارد، RNi[i] را افزوده و REQUEST (i,sn) را به همه دیگر سایتها می‌فرستد.\n\nبا رسیدن REQUEST در Sj، RNj[i]=max (RNj[i],sn) . اگر Sj مهره آزاد دارد مشروط به RNj[i]=LN[i]+1 به Si می‌فرستد.\n\nالگوریتم‌های سوزوکی و کاسامی-ادامه\n\nاجرای CS: \n\nبا رسیدن مهره\n\nخروج از CS: با پایان عملیات در ناحیه بحرانی:\n\nLN[i]=RNi[i]\n\nبرای همه سایت‌های Sj که شناسه آنها در صف مهره نیست به شرط RNi[j]=LN[j]+1، شناسه آنها را به صف مهره اضافه می‌کند.\n\nاگر صف مهره پس از بروز آوری مرحله ۲، غیر خالی است، شناسه سر صف را حذف و مهره را به آن سایت ارسال می‌کند.\n\nکارآیی: 0 تا N پیغام برای هر بار ورود به CS\n\nتأخیر همگامی: 0 تا T\n\nالگوریتم سینگهال\n\nهر سایت اطلاعاتی در مورد دیگر سایتها نگه می‌دارد و بر اساس آن مجموعه سایت‌هایی که احتمالاً مهره را دارند انتخاب می‌کند و درخواست را فقط به آنها می‌فرستد. (روش heuristic)\n\nساختمان داده لازم:\n\nدر هر سایت Si دو آرایه SNi[1..N] , SVi[1..N] برای نگهداری حالت و بزرگترین شماره ترتیب از هر سایت.\n\nمهره هم دو آرایه متناظر TSN[1..N] , TSV[1..N] دارد.\n\nهر سایت در یکی از حالات زیر در هر لحظه قرار دارد:\n\nR: متقاضی ورود به CS\n\nE: اجرا\n\nH: دارنده مهره آزاد\n\nN: هیچکدام\n\nالگوریتم سینگهال-ادامه\n\nمقداردهی اولیه آرایهها به قرار زیر است:\n\nالگوریتم سینگهال-ادامه\n\nدر این مقدار دهی اولیه، برای هر دو Si و Sjیا SVi[j]=R است یا SVj[i]=R. چون انتخاب سایت‌های متقاضی مبتنی بر اطلاعات محلی است، برای هر دو سایتی که همروند متقاضی ورود به CS هستند یکی مهره را به دیگری خواهد فرستاد\n\nسایتها از هم ایزوله نخواهند بود و درخواست یک سایت به سایت دارنده مهره و یا دارنده مهره در آینده نزدیک خواهد رسید.\n\nالگوریتم سینگهال-ادامه\n\nالگوریتم:\n\nدرخواست ورود به CS: اگر متقاضی (Si) مهره را در اختیار ندارد.\n\nSNi[i]++ , SVi[i]=R \n\nارسال REQUEST (i, sn) به همه سایت‌های Sj که SVi[j]=R است. Sn = SNi[i] \n\nبا رسیدن REQUEST، اگر SNj[i] ≥ sn است درخواست دور ریخته می‌شود (کهنه) و در غیر این صورت SNj[i]=sn و بر حسب حالت فعلی مقادیری را می‌نویسد:\n\nاگر N است، SVj[i]=R\n\nاگر R است، اگر SVj[i] R است پس SVj[i]=R و ارسالREQUEST (j,SNj[j]) به Si. در غیر این صورت:\n\nاگر E است SVj[i]=R\n\nاگر H است SVj[j]=N , TSN[i]=sn , TSV[i]=R , SVj[i]=R و ارسال مهره به سایت Si. \n\nالگوریتم سینگهال-ادامه\n\nاجرای CS: با رسیدن مهره، قبل از اجرای CS مقداردهی SVi[i]=E \n\nخروج از CS:\n\nTSV [i]=N , SVi[i]=N\n\nبروزرسانی آرایه های محلی و مهره به ترتیب زیر:\n\nfor all Sj , j=1.. N\n\n if SN[j]>TSN[j]\n\n then\n\n{ TSV[j]:= SVi[j]; TSN[j]:=SNi[j] }\n\n else\n\n{ SVi[j]:= TSV[j]; SNi[j]:=TSN[j] }\n\nاگر پس SVi[i]= H، در غیر این صورت مهره را به سایت Sj بفرست که SVi[j]=R است\n\nالگوریتم سینگهال-ادامه\n\nبرای ورود به ناحیهی بحرانی، درخواست به همه سایت‌هایی ارسال می‌شود که متقاضی ورود به CS هستند. \n\nهر سایت اطلاعات خود را بر اساس اطلاعات مهره ودرخواستهای رسیده از دیگر سایتها تنظیم می کند.\n\nSVi[j]=R وقتی است که درخواستی از Sj برسد و یا مهرهای با اطلاعات جدیدتر برسد که در آن TSV[j]=R باشد. \n\nکارایی: برای ورود به CS نیازی به محاوره با کلیه سایتها نیست. میانگین ترافیک پیغامی N/2 است. \n\nتأخیر همگامی: T\n\nالگوریتم درخت مبنای ریموند\n\nسایتها یک درخت منطقی جهت‌دار می‌سازند که جهت لبهها به سمت ریشه است. ریشه نودی است که مهره را در اختیار دارد.\n\nهر سایت یک متغیر holder دارد که به همسایه بلافصل به سمت ریشه اشاره می‌کند. در ریشه holder به خودش مقداردهی می‌شود.\n\nهر سایت یک صف FIFO دارد، request-q درخواست‌های معوق همسایهها را ذخیره می‌کند.\n\nالگوریتم درخت مبنای ریموند\n\nالگوریتم درخت مبنای ریموند-درخواست CS\n\nمتقاضی، با فرض نداشتن مهره و خالی بودن request-q، درخواست را به نود بالاتر در مسیر ریشه می‌فرستد. سپس درخواست را در صف خود می‌گذارد. صف ناخالی به معنای ارسال یک درخواست به نود بالاتر است.\n\nبا دریافت درخواست، درخواست در صف و ارسال به نود سطح بالاتر، مشروط بر اینکه قبلاً درخواستی را به نود بالاتر نفرستاده باشد.\n\nوقتی ریشه درخواست را دریافت کرد، مهره را تقدیم می‌کند و holder را به آن سایت مقداردهی می‌کند.\n\nوقتی سایتی مهره را دریافت کرد، درخواست سر صف را حذف می‌کند و مهره را به آن سایت می‌فرستد و holder را به آن سایت مقدار می‌دهد. اگر request-q غیر خالی است درخواستی را به سایتی که holder اشاره می‌کند بفرست.\n\nالگوریتم درخت مبنای ریموند\n\nاجرای CS\n\nوقتی سایتی مهره را دریافت کند و خود سر صف خودش باشد، سر صف را حذف و وارد CS می‌شود.\n\nخروج از CS\n\nاگر request-q غیر خالی است، سر صف را حذف کن و مهره را به آن سایت بفرست و holder را به آن سایت مقدار بده.\n\nاگر request-q باز هم غیر خالی است، یک پیغام درخواست به محتوای holder می‌فرستد.\n\nالگوریتم درخت مبنای ریموند\n\nقضیه: در الگوریتم ریموند، یک متقاضی CS در زمان متناهی موفق می‌شود.\n\nاثبات: در واقعیت:\n\nهر سایت درخواستها را به ترتیب FIFO پردازش می‌کند.\n\nهر سایت مسیری دارد که منجر به سایت دارای مهره می‌شود.\n\nوقتی Si درخواستی دارد زنجیری از درخواستها تا Sh (دارنده مهره) ایجاد می‌شود مثلاً زنجیر \n\nوقتی Sh درخواست را از Sik می‌گیرد مهره را به او برمی گرداند.\n\nالگوریتم درخت مبنای ریموند\n\nدو حالت دارد:\n\nدرخواست Sik-1 در ابتدای صف Sik است. در نتیجه Sik مهره را به Sik-1 می‌فرستد.\n\nنیست: Sik مهره را به سایت ابتدای صف (مثلاً Sj) می‌فرستد و یک درخواست (REQUEST) هم به Sj می فرستد. درنتیجه زنجیر درخواستها به شکل \n\nدر می‌آید که Sl مجری بعدی CS خواهد بود.\n\nالگوریتم درخت مبنای ریموند\n\nتوجه: همه سایت‌های موجود در زنجیره Sj , … , Sl حداکثر یک بار وارد CS می‌شوند قبل از آنکه مهره به Sik برگردد و لذا Sik در زمان متناهی مهره را به Sik-1 و به همین ترتیب Sik-1 به Sik-2 و... می‌فرستد. در نتیجه یک سایت متقاضی نهایتاً مهره را دریافت می‌کند.\n\nکارآیی:\n\nپیغام: O(logN)\n\nتأخیر همگامی: میانگین فاصله دو سایت که پشت سر هم وارد CS می‌شوند. \n\n \n\n \n\n \n\n30 تا 70 درصد پروژه | پاورپوینت | سمینار | طرح های کارآفرینی و توجیهی | پایان-نامه | پی دی اف مقاله ( کتاب ) | نقشه | پلان طراحی | های آماده به صورت رایگان میباشد ( word | pdf | docx | doc )
