بخشی از پاورپوینت
اسلاید 1 :
محروميت متقابل:( هم زماني در سيستم هاي درهم ريخته)
سيستم هاي درگير با فرايند هاي چند گانه اغلب به صورت برنامه ريزي شده به
استفاده مناطق بحراني مي رسند . وقتي كه يك فرايند براي خواندن يا به روز در
آوردن تحت اطلا عات مربوط خاص در ساختار هاست . اين وارد يك واحد
بحراني مي شود براي رسيدن به محروميت متقابل و تضمين مي كنند كه ديگر فرايند ها استفاد خواهند كرد از ساختارهاي اظلا عاتي مربوط به صورت هم زماندر سيستم هاي پردازشگر منفرد ، مناطق بحراني حفظ مي كنند مخابره ها را ، مانيتور ها را ساختار مشابه را . ما اكنون به مثال هاي چند از چگونگي مناطق بحراني و محروميت متقابل كه مي توانند در سيستم هاي بخش مورد استفاده قرار مي گيرند نگاه مي كنيم براي يك رده بندي و فهرست منابع ديگر روش ها RAYNAL را
ببنديد ديگر كاها را از ElabbadiوAgrabbadliوchandyوsandersمورد بحث قرار مي گيرند
اسلاید 2 :
1.2.3 يك الگوريتم مركزي:
مستقيم ترين روش براي رسيدن به محروميت هاي متقابل در يك سيستم بخشي براي وانمود كردن اينكه چگونه اين در يك سيستم با يك پردازشگر انجام مي شود مي باشد يك فرايند انتخاب مي شود به عنوان همراه ، كه يك فرايند مي خواهد وارد يك منطقه بحراني شود اين يك پيام در خواست مي فرستد براي بيان همراهي در منطقه بحراني اين مي خواهد وارد شود و اجازه مي خواهد . اگرديگر فرايند ها در منطقه بحراني باشند همراه كننده يك پاسخ را براي اجاره به عقب مي فرستند، همان طور در شكل 8-3 ديده مي شود وقتي پاسخ رسيد ، درخواست فرايند وارد يك منطقه بحراني مي شود . اكنون فرض مي كنيم كه ديگر فرايند ، 2 در شكل8-3 ، براي اجازه براي ورود به منطقه بحراني مشابه است همراهي مي كنند مي داند كه يك فرايند متفاوت در منطقه بحراني وجود دارد بنابراين اين نمي تواند اجازه اهدا را بدهد در شكل (b)8-3 ، همراه كننده فقط اجتناب مي كند از پاسخ . بنابراين فرايند 2 متوقف مي شود كه منتظر يك پاسخ است . اين مي تواند يك پاسخ را بفرستد كه مي گويد اجازه داده شده ، روش ورودي .
اسلاید 3 :
اين رديف ها درخواست مي شوند از 2 براي دادن زمان وقتي فرايند (1) در منطقه بحراني وجود دارد . اين يك پيام را براي اجازه همراهي مي فرستد كه دسترس مي باشد همانطور كه در شكل (2)8-3 است. همراه كننده اولين آيتم را براي صف هاي در خواست هاي آن دارد و مي فرستد يك پيام اهدايي را . اگر فرايند متوقف شود اين غير متوقف است و وارد منطقه بحراني مي شود . اگر يك پيام واضع اجازه فرستاده ، فرايند براي دريافت ترافيك وتردد مي شود يا بعداً متوقف مي شود. روش ، وقتي اهدايي را ببندد . اين مي تواند وارد منظقه بحراني شود . اين آسان است براي ديدن ضمانت هاي الگوريتم در محروميت متقابل همراه كننده فقط اجازه مي دهد يك فرايند در زمان براي هر منطقه بحرانياين در خواست مي كند و اجازه مي دهد به اهدايي در ترتيبي در آن دريافت شوند . فرايند منتظر نيست .اين طرح آسان است براي اجرا ، و نيازي دارد فقط به 3 پيام در هر استفاده از منطقه بحراني ( در خواست – اهدا – رهايي) اين مي تواند مورد استفاده قرار گيرد براي منبع بيشتر نسبت به فقط كنترول مناطق بحراني.رويكرد مركزي كردن خلاصه است .
اسلاید 4 :
3.2.2الگوريتم در هم ريخته :
داشتن يك نقطه شكست به صورت مكرر غير قابل پذيرش است پس محققان محدوديت متقابل در هم ريخته را جستجو كرده اند لمپورت در سال 1978 همزمان ساعتي را براي اولين بار ارائه داد. رسكارت و آگرا والا در سال 1981 آن را مناسب تر ساختند . در اين جا بخشها و روش هاي آنها را مورد بحث قرار خواهيم داد . الگوريتم ريكارت و آگراوا لا نيز دارند به اينكه يك ترتيب يكي از همه حوادث در ستم داشته باشند . براي هر جفت از حوادث مثل پيامها ، اين بايد غير مبهم باشد كه يك بار اولين بار اتفاق مي افتد
الگوريتم لمپورت در بخش3.1.1 يك روش براي رسيدن به اين ترتيب است و مي تواند مورد استفاده قرار گيرد براي ورود به يك منطقه بحراني اين يك پيام را شامل نام منطقه بحراني شامل مي شود ، اين ميخواهد وارد شود. اين دو فرايند آن و زمان جاري آن است . اين پيام رابه همه ديگر فرايند ها مي فرستند كه شامل خودش مي باشد . فرستادن پيام به نظر مي رسد قابل خواندن باشد كه هر پيام پذيرفته است. تبادل گروهي اگر در دسترس باشد مي تواند مورد استفاده قرار گيرد به جاي پيامهاي فردي.
اسلاید 5 :
اين موارد تشخيص داده شده اند:
- اگردريافت گر در منطقه بحراني نباشد و نخواهد وارد شود اين يك پيام okبه عقب مي فرستد به فرستنده.
- اگر دريافت گر در نقطه بحراني باشد اين پاسخ نمي دهد در عوض اين صفوف در خواست مي كنند
- اگر دريافت گر مي خواهد وارد منطقه بحراني شود اما هنوز انجام نشده . اين مقايسه مي كند زمان رادر پيام ورودي با يك محتوي در پيامي كه هركس مي فرستد. پايين ترين آن برنده مي شوند . اگر پيام دريافتي پايين تر باشد دريافت گر يك پيام ok به عقب مي فرستد. اگر پيام يك زمان پايين تر داشته باشد دريافت گر صفوف ورودي را درخواست مي كندو چيزي نمي فرستد.
بعد از فرستادن در خواست ها پرسش اجازه براي ورود به يك منطقه بحراني يك فرايند به عقب فرستاده مي شود و منتظر مي ماند تا كسي اجازه را بدهد . بزودي همه اجازه ها در آن است . اين ممكن است منطقه بحراني وارد شود . وقتي اين منطقه بحراني مجمد داشته باشد . اين پيام هاي ok را مي فرستد به همه فرايند ها روي رديف آن و آنها را از همه حذف مي كند . اجازه دهيد تلاش كنيم براي درك اينكه چرا الگوريتم كار مي كند اگر متضادي وجود ندارد اين به روشني كار مي كند.
علاوه فرض كنيد كه فرايند تلاش دارد براي درك منطقه بحراني مشابه به صورت همزمان همانطور كه در شكل (9-3) نشان داده مي شود:
اسلاید 6 :
شكل 9-3 دو فرايند مي خواهند وارد منطقه بحراني شوند در لحضه مشابه . (b) فرايند 0 پايين ترين زمان را دارد پس برنده است . (c) . وقتي فرايند 0 اجرا شود اين يك OK مي فرستد پس 2 مي تواند وارد منطقه بحراني شود .
فرايند 0 يك در خواست براي هر كس مي فرستد با زمان 8 در حاليكه در زمان مشابه ، فرايند 2 براي هر كسي در خواستي زمان 12 مي فرستد فرايند
ميل دارد به ورود به منطقه بحراني پس اين يك OK مي فرستد به فرستنده . فرايند 0و2 هر دو تضاد را مي بينند و زمان را مقايسه مي كنند.
در فرايند 2 از دست دادند را مي بيند پس اين اجازه را به 0 مي دهد با فرستادن پيام OK . فرايند O اكنون صفوف را در خواست مي كند از 2 براي فرايند اخير و وارد منطقه بحراني مي شود همان طور كه در شكل (B) 9-3 ديده مي شود . وقتي اين به پايان مي رسد اين درخواست را از2 صف آن انتقال مي دهد و يك پيام OK رابه فرايند (2) مي فرستد اجازه مي دهند براي ورود به منطقه بحراني همانطور كه در شكل (C) 9-3 ديده مي شود .
اسلاید 7 :
. الگوريتم كار مي كند زيرا در مورد يك تضاد است . پايين ترين زمان برنده مي شود و هركس مافق است با ترتيب زماني . توجه شود كه مو قعييت در شكل 9-3 ضرورتاً متفاوت است اگر فرايند 2 پيام خود را اخيراً در زمان مي فرستد پس فرايند 0 آن را مي گيرد و اجازه آن را قبل از ساخت در خواست مي فرستد . در اين مورد 2 توجه مي شود كه اين خودش در يك منطقه بحراني در زمان در خواست است وبه صف در مي آيد كه اين به جاي فرستادن يك پاسخ است . همانطور با الگوريتم مركزي كه در بالا مورد بحث قرار گرفت محروميت متقابل بدون ضامن و بن بست است.عدد پيام نياز دارد به هر موجودي كه اكنون(1-8)2 است جايي كه كل نمره پروسه ها در سيستم Nاست بهترين همه نقطه مفردي است از موجودي هاي شكست نقطه منفرد شكست بوسيله نقاط N جابجا مي شود از شكست.اگر هر پروسه بشكند اين شكست براي پاسخ به درخواست هاست.اين سكوت تفسير مي شود همانطور كه عدم پذيرش اجازه است. از آنجا كه توانايي يكي از پروسه هاي N شكست خورده زمان هاي N است به بزرگي يك همراه كننده ي منفرد شكست مي خورد ما كنترل مي كنيم جابجايي را براي يك الگوريتم با يك زمان N كه بر ترين زمان است و نياز به ترانيك شبكه بيشتر دارد.
الگوريتم مي تواند سر هم بندي شود بوسيله بخش مشابهي كه ما بعدا پيشنهاد مي كنيم
اسلاید 8 :
وقتي يك درخواست مي آيد،دريافت گر يك پاسخ را مي فرستد.همچنين اهدا كردن يا معيار كردن اجازه زماني كه يك در خواست يا يك پاسخ از دست داده مي شودشامل مقصد باشد كه معيار است.بعد از يك در خواست كه معيار مي شودفرستنده بايد متوقف شود و منتظر باشد براي پيام OK .ديگر مشكل براي اين الكوريتم يك تبادل گروهي است كه مي بايست مورد استفاده قرار گيرد يا هر پروسه كه بايد عضو گروهي را در ليست خود نگه دارد شامل پروسه هايي كه وارد گروه مي شوند و ترك گروه و روش كار مي كنند با بهترين نوع با گروه هاي كوچك پروسه هايي كه هرگز اعضاي گروه آنها تغيير نمي كند.سر انجام. يكي از مسائل با الگور يتم مركزي ساخت آن به صورت دستي است كه در خواستها مي توانند منتهي شوند به يك تنگنادر الگوريتم آشفته و درهم ريخته همه پروسه ها در همه تصميمات مربوط هر كسي را وارد مي كندبه انجام دقيق چيزهاي مشابه كه به صورت موازي كه به كمك بيشتر منتهي مي شود.بهبود هاي مختلف ممكن است براي اين الگوريتم براي مثال گرفتن اجازه از هر كسي براي ورود به يك منطقه بحراني واقعا زياده روي است. همه ي آنها نياز به يك روش براي جلوگيري از 2پروسه از ورود به منطقه ي بحراني به صورت همزمان دارند.الگوريتم ميتواند تعريف شود براي اجازه دادن به يك پروسه براي ورود به يك منطقه ي بحراني وقتي اين اجازه را جمع آوري مي كند از يك روش اصلي ساده از ديگر پروسه ها نسبت به ديگر همه ي آنها.
اسلاید 9 :
البته،در اين گوناگوني بعد از يك پروسه اخاز داده ميشود به يك پروسه براي ورود به يك منطقه ي بحراني.اين نمي تواند اجازه مشابه رابه ديگر پروسه ها بدهد تا اولين نوع آن كه اجازه داده مي شود .ديگر پيشرفت ها ممكن است اين الگوريتم آهسته تر است،پيچيده تر است ،گران تر است و يك مركز گرايي اصلي است.چرا اين تحت اين مسائل مورد مطالعه قرار مي گيرد؟ براي يك چيز ،اين نشان مي دهد يك الكوريتم در هم ريخته را در نهايت امكان،برخي چيزها روشن نيست وقتي ما شروع مي كنيم.با اشاره به خلاصه اي از آن ،ما ممكن است تحريك كنيم تئوريسين هايي را براي تلاش براي توليد الگوريتم هايي كه واقعاٌ مفيد مي باشند.سرانجام،مثل خوردن اسفناج و يادگيري لاتين در دبيرستان برخي چيزها خوب مي گويند براي شما در برخي روش هاي انتزاعي.
اسلاید 10 :
3.2.2 يك الگوريتم حلقه اي علامتي:
يك رويكرد متفاوت براي رسيدن به محروميت متقابل در يك سيستم در هم ريخته در شكل10-3 شرح داده شده .در اينجا ما يك شبكه ي اتوبوس داريم همانطور كه در شكلa 1-1-3 نشان داده شده با ترتيب ارثي از پروسه ها.در نرم افزار يك حلقه ي قانوني در هر پروسه كه علامت گذاري شده با يك موقعيت در يك حلقه ساخته شدههمانطور كه در شكل b10-3 نشان داده شده.موقعيت هاي حلقه ممكن است جمع آوري شود در ترتيب عددي آدرس هاي شبكه يا برخي از ابزار ديگر.همه موضوع ها در هر پروسه مي داند كه چه كسي در خط بعدي بعد از خودش مي باشد.وقتي حلقه شروع مي شود پروسه 0 يك علامت مي دهد.علامت اطراف حلقه منتشر مي شود.اين پروسه k رابه پروسه ي k+1 عبور مي دهددر نقطه اي به نقطه ديگر.وقتي يك پروسه دريافت مي كند يك علامت را از همسايه خود اين چك مي شودبراي ديدن اينكه اگر تلاش شود براي ورود به يك منطقه ي بحراني.اگر پروسه وارد منطقه شود،همه ي كار آن نياز دارد به كار و ترك منطقه.بعد از اينكه اين نياز است.اين عبور مي دهد علامت را در طول حلقه .اين اجازه نمي دهد به ورود به دومين منطقه بحراني در علامت مشابه.اگر يك پروسه علامت آن بدست آيد بوسيله ي همسايه آن و علاقه اي به ورود به منطقه ي بحراني نداشته باشد اين قسط آن را در طول آن عبور مي دهد.
