Lecture 5: Concurrency in Operating Systems PDF

‫سیستم عامل‬ Operating system Click to edit Master subtitle style Lecture 5 Concurrency: Mutual Exclusion and Synchronization ‫ انحصار متقابل و همگام سازی‬:‫همزمانی‬ ‫‪2‬‬ ‫‪[email protected]‬‬...

‫سیستم عامل‬ Operating system Click to edit Master subtitle style Lecture 5 Concurrency: Mutual Exclusion and Synchronization ‫ انحصار متقابل و همگام سازی‬:‫همزمانی‬ ‫‪2‬‬ ‫‪[email protected]‬‬ ‫همزمانی‪:‬‬ ‫‪ ‬همزمانی در سه زمینه زیر اجرا میشود‪:‬‬ ‫‪ ‬کاربرد های متعدد‬ ‫ چند برنامه ای‬ ‫‪ ‬کاربرد ساخت یافته‬ ‫ کاربرد ها میتوانند مجموعه ای از فرآیند های همزمان باشند‪.‬‬ ‫‪ ‬ساختار سیستم عامل‬ ‫ سیستم عامل مجموعه ای از نخها و فرآیند هاست‪.‬‬  ‫‪3‬‬ ‫‪[email protected]‬‬ ‫موضوعات محوری در طراحی سیستم عامل‪:‬‬ ‫‪ ‬چند برنامه ای ‪ :‬مدیریت فرآیندهای متعدد در داخل یک سیستم تک پردازنده‬ ‫ای‬ ‫‪ ‬چند پردازشی‪ :‬مدیریت فرآیندهای متعدد در داخل یک سیستم چند پردازنده‬ ‫ای‬ ‫‪ ‬پردازش توزیعی ‪:‬مدیریت فرآیندهای متعدد که روی سیستم های کامپیوتری‬ ‫متعدد و توزیع شده اجرا میشوند‪.‬‬  ‫‪4‬‬ ‫‪[email protected]‬‬ ‫مشکالت سیستم تک پردازنده ای‪:‬‬ ‫‪ ‬اشتراک منابع سراسری پر مخاطره است‬ ‫‪ ‬مدیریت تخصیص بهینه منابع به فرآیندها توسط سیستم عامل دشوار است‪.‬‬ ‫‪ ‬یافتن محل خطای برنامه نویسی مشکل است‪.‬‬ ‫‪5‬‬ ‫‪[email protected]‬‬ ‫همزمانی‪:‬‬ ‫‪ ‬همزمانی گروهی از موضوعات طراحی را در بر میگیرد‪:‬‬ ‫‪ ‬ارتباط بین فرآیندها‬ ‫‪ ‬اشتراک منابع و رقابت برای آنها‬ ‫‪ ‬همگام سازی فعالیتهای فرآیند های متعدد‬ ‫‪ ‬توزیع وقت پردازنده در بین فرآیند ها‬  ‫‪6‬‬ ‫‪[email protected]‬‬ ‫مباحث مطرح در ارتباط بین فرآیندها‬ ‫در طراحی سیستم عامل‪ ،‬سه موضوع زیر در رابطه با ارتباط بین فرآیندها مطرح است‪:‬‬ ‫‪ (1‬همگام سازی (‪)Synchronization‬‬ ‫اگر بین فرآیندها وابستگی وجود داشته باشد‪ ،‬ترتیب درست انجام کارها باید رعایت شود‪.‬‬ ‫‪ (2‬تبادل اطالعات (‪)Communication‬‬ ‫فرآیندها می توانند با مکانیسم هایی چون "حافظه مشترک‪ ،‬تبادل پیام‪ ،‬فایل مشترک و‬ ‫لوله" با یکدیگر تبادل اطالعات کنند‪.‬‬ ‫‪ (3‬رقابت فرآیندها‬ ‫فرآیندها درفعالیت های بحرانی یکدیگر مداخله نکنند و شرایط رقابتی (‪Condition‬‬ ‫‪ )Race‬برای آنها رخ ندهد‪.‬‬  7 [email protected] :‫یک مثال ساده‬ Process P1 Process P2.. in = getchar();.. in = getchar(); chout = chin; chout = chin; putchar(chout);.. putchar(chout);..  ‫‪8‬‬ ‫‪[email protected]‬‬ ‫موارد مهم در سیستم عامل همزمانی‪:‬‬ ‫‪ ‬با در نظر گرفتن مساله همزمانی فرآیند ها‪ ،‬در طراحی سیستم عامل باید موارد‬ ‫زیر را در نظر داشت‪.‬‬ ‫‪ ‬سیستم عامل باید بتواند فرآیند های فعال را دنبال کند‪.‬‬ ‫‪ ‬سیستم عامل باید بتواند منابع را به فرآیندها تخصیص دهد و بگیرد‪.‬‬ ‫‪ ‬سیستم عامل باید داده ها و منابع هر فرآیند را از دسترسی سایر فرآیندها‬ ‫محافظت کند‪.‬‬ ‫‪ ‬نتایج یک فرآیند باید مستقل از سرعت پیشرفت فرآیندهای دیگر باشد‪.‬‬  ‫‪9‬‬ ‫‪[email protected]‬‬ ‫محاوره فرآیندها‪:‬‬ ‫‪ ‬فرآیندهای مستقل‪( :‬بی اطالعی فرآیند ها از یکدیگر) اینها فرآیند های مستقل‬ ‫از یکدیگرند خواستار همکاری با یکدیگر نیستند و تبادل اطالعاتی ندارند‪.‬‬ ‫‪ ‬فرآیندهای همکار‪ :‬دو روش برای تبادل داده بین فرآیندهای همکار وجود دارد‪.‬‬ ‫‪ ‬اطالع غیر مستقیم فرآیند ها از یکدیگر(استفاده از حافظه مشترک)‪ :‬اینها‬ ‫فرآیند هایی هستند که لزوما از شناسه یکدیگر آشنا نیستند‪ ،‬ولی در دسترسی به‬ ‫بعضی اشیاء مثل بافر ورودی خروجی با یکدیگر مشترکند‪.‬‬ ‫‪ ‬اطالع مستقیم از یکدیگر (ارسال و دریافت پیام)‪ :‬اینها فرآیندهایی هستند‬ ‫که قادرند با استفاده از شناسه‪ ،‬با یکدیگر ارتباط برقرار کنند و برای کار مشترک بر‬ ‫روی بعضی فعالیت ها ساخته شده اند‪.‬دستورات ‪ send‬و ‪ receive‬بجای حافظه‬ ‫مشترک استفاده می شود‪.‬‬ 10 [email protected] :‫محاوره فرآیندها‬  ‫‪11‬‬ ‫‪[email protected]‬‬ ‫ملزومات انحصار متقابل‪:‬‬ ‫‪ ‬انحصار متقابل باید اعمال گردد‪ :‬از میان فرآیندهایی که برای منبع یکسان یا شیء‬ ‫مشترکی دارای بخش بحرانی هستند‪ ،‬تنها یک فرآیند مجاز است در بخش بحرانی خود‬ ‫باشد‪.‬‬ ‫‪ ‬فرآیندی که در بخش غیربحرانی خود متوقف میشود‪ ،‬باید طوری عمل کند که هیچ‬ ‫دخالتی در عملکرد فرآیند های دیگر نداشته باشد‪.‬‬ ‫‪ ‬برای فرآیندی که نیاز به دسترسی یه یک بخش بحرانی دارد نباید امکان به تاخیر‬ ‫انداختن نامحدود آن وجود داشته باشد‪ ،‬بن بست یا گرسنگی نمی تواند مجاز باشد‪.‬‬ ‫‪ ‬هنگامی که هیچ فرآیندی در بخش بحرانی خود نیست‪ ،‬هر فرآیندی که متقاضی ورود‬ ‫به بخش بحرانی خود باشد‪ ،‬باید بدون تأخیر مجاز به ورود باشد‪.‬‬ ‫‪ ‬هیچ فرضی در مورد سرعت نسبی فرآیندها یا تعداد آنها نمیتوان نوشت‪.‬‬ ‫‪ ‬هر فرآیندی فقط برای مدت زمان محدوددی در داخل بخش بحرانی خود می ماند‪.‬‬  ‫‪12‬‬ ‫‪[email protected]‬‬ ‫رقابت میان فرآیند ها برای منابع‪:‬‬ ‫‪ ‬در مورد فرآیند های رقیب با سه مسئله کنترلی مواجهیم‪:‬‬ ‫‪ ‬انحصار متقابل(بخش بحرانی)‬ ‫ در هر لحظه فقط یک برنامه اجازه دارد به بخش بحرانی خود وارد شود‪.‬‬ ‫ به عنوان مثال در هر لحظه تنها یک فرآیند اجازه دارد پیامی را به چاپگر بفرستد‪.‬‬ ‫‪ ‬بن بست‬ ‫ هنگام اعمال انحصار متقابل‪ ،‬در صورتیکه یک فرآیند کنترل منبعی را در اختیار بگیرد و در‬ ‫انتظار منبع دیگری برای اجرا یاشد ممکن است بن بست رخ دهد‪.‬‬ ‫‪ ‬گرسنگی(قحطی)‬ ‫ ممکن است یکی از فرآیندهای مجموعه برای مدتی نامحدود از دسترسی به منابع مورد‬ ‫نیازش محروم بماند‪ ،‬چرا که سایر فرآیند ها منابع را به طور انحصاری بین یکدیگر مبادله‬ ‫میکنند‪.‬به این حالت گرسنگی می گویند‪.‬‬  ‫‪13‬‬ ‫‪[email protected]‬‬ ‫انحصار متقابل(بخش بحرانی)‬ ‫‪ ‬فرض کنید چند فرآیند برای دسترسی به یک منبع غیر اشتراکی مانند چاپگر رقابت‬ ‫می کنند‪.‬در طی اجراء‪ ،‬هر یک از فرآیندها‪ ،‬فرمان هایی را به دستگاه ورودی‪ /‬خروجی‬ ‫ارسال می کنند‪.‬چنین منبعی را منبع بحرانی و بخشی از برنامه که از آن استفاده‬ ‫میکند را بخش بحرانی آن برنامه می گوییم‪.‬‬ ‫‪ ‬مهم این است که در یک زمان‪ ،‬تنها یک برنامه مجاز است تا در بخش بحرانی خود‬ ‫باشد‪.‬‬ ‫‪ ‬بخش هایی از برنامه که رفتار آنها با عوامل مشترک‪ ،‬ایجاد رقابت می کنند‪ ،‬را ناحیه‬ ‫بحرانی ( ‪ )Critical Region‬می گویند‪.‬‬  ‫‪14‬‬ ‫‪[email protected]‬‬ ‫بن بست ( ‪)Deadlock‬‬ ‫‪ ‬اعمال انحصار متقابل دو مسئله کنترلی‪ ،‬بن بست وگرسنگی را به وجود می آورد‪.‬‬ ‫‪ ‬دو فرآیند ‪ P1‬و ‪ P2‬و دو منبع بحرانی ‪ R1‬و ‪ R2‬مفروض است که هر یک از‬ ‫فرآیندها برای انجام عمل خود به هر دو منبع نیاز دارند‪.‬اگر منبع ‪ R1‬به ‪ P2‬و‬ ‫منبع ‪ R2‬به ‪ P1‬داده شود‪ ،‬هر یک منتظر منبع دیگر می باشند و هیچ یک از‬ ‫فرآیندها‪ ،‬منبعی را که در اختیار دارد را رها نمی کند تا فرآیند دیگر آن را‬ ‫دریافت کرده و بخش بحرانی خود را انجام دهد‪.‬بنابراین هر دو فرآیند در بن‬ ‫بست قرار می گیرند‪.‬‬ ‫‪ ‬به زبان ساده بن بست یعنی تا ابد منتظر ورود به ناحیه بحرانی خود بودن‪.‬‬  ‫‪15‬‬ ‫‪[email protected]‬‬ ‫گرسنگی‪ ،‬قحطی‬ ‫‪ ‬فرض کنید هر یک از سه فرآیند ‪ P1‬و ‪ P2‬و ‪ P3‬متناوباً نیازمند دسترسی به‬ ‫منبع ‪ R‬هستند‪.‬‬ ‫‪ ‬وقتی ‪ P1‬این منبع را در اختیار گیرد‪ P2 ،‬و ‪ P3‬در انتظار آن منبع‪ ،‬به تاخیر‬ ‫انداخته می شوند‪.‬با خروج ‪ P1‬از ناحیه بحرانی‪ ،‬یکی از ‪ P2‬یا ‪ P3‬باید ‪ R‬را در‬ ‫اختیار گیرند‪.‬اگر‪ P3‬منبع ‪ R‬را بگیرد و قبل از پایان بخش بحرانی مجدداً ‪P1‬‬ ‫درخواست ‪ R‬را بکند و بعد از پایان ‪ ، P3‬اجازه به ‪ P1‬داده شود و مکرراً این‬ ‫عمل بین ‪ P1‬و ‪ P3‬ادامه یابد‪ P2 ،‬به صورت نامحدود از دسترسی به منبع ‪R‬‬ ‫محروم می ماند و گرسنگی می کشد‪.‬‬ ‫‪ ‬به عبارت دیگر گرسنگی یعنی به مدت نامعلوم و بدون حد باالی مشخص‪ ،‬منتظر‬ ‫فرآیندهای دیگر بودن‪.‬‬  ‫‪16‬‬ ‫‪[email protected]‬‬ ‫رویکردهای انحصار متقابل‬ ‫راه حل های مشکل ناحیه بحرانی ملزوماتی دارد‪ ،‬به عبارت دیگر برای اینکه همکاری درست و کارا‬ ‫بین فرآیندهای هم روند برقرار باشد‪ ،‬باید شروطی داشته باشد از جمله‪:‬‬ ‫‪ ‬انحصار متقابل (‪)Mutual Exclusion‬‬ ‫از بین فرآیندهایی که برای یک منبع یکسان دارای ناحیه بحرانی هستند‪ ،‬در هر لحظه فقط یک فرآیند‬ ‫مجاز است که در ناحیه بحرانی خود باشد‪.‬‬ ‫‪ ‬پیشرفت (‪)Progress‬‬ ‫فرآیندی که فعال تصمیم به ورود به ناحیه بحرانی را ندارد و در ناحیه غیربحرانی می باشدو دستورالعمل‬ ‫های عادی برنامه خود را اجرا می کند‪ ،‬نباید در تصمیم گیری برای ورود فرآیندهای دیگر به ناحیه بحرانی‬ ‫شرکت کند‪(.‬امکان ممانعت نداشته باشد)‬ ‫‪ ‬انتظار محدود (‪)Bounded Waiting‬‬ ‫باید مدت انتظار فرآیندهایی که نیاز به ورود به ناحیه بحرانی دارند‪ ،‬محدود باشد‪.‬یعنی نباید دچارگرسنگی‬ ‫و بن بست شوند‪.‬‬ ‫‪ ‬البته عالوه بر رعایت سه شرط فوق‪ ،‬مسئله را باید در حالت کلی حل کرد و فرضی برای ساده‬ ‫سازی راه حل به کار نبرد‪.‬همچنین الگوریتم حالت قطعی و غیر تصادفی داشته باشد‬  ‫‪17‬‬ ‫‪[email protected]‬‬ ‫راه حل های مسئله انحصار متقابل‬ ‫برای تحقق انحصار متقابل‪ ،‬پیشنهادهای مختلفی وجود دارد‪.‬این راه حل ها را به‬ ‫صورت چهار رویکرد دسته بندی می کنیم‪:‬‬ ‫‪ (1‬راه حلهای با حمایت سخت افزار(با کمک دستورالعمل های خاص ‪)CPU‬‬ ‫‪ (2‬راه حلهای نرم افزاری‬ ‫‪ (3‬راه حلهای با حمایت سیستم عامل (با کمک فراخوان های سیستمی خاص)‬ ‫‪ (4‬راه حلهای با حمایت زبان برنامه سازی (با کمک کامپایلر)‬  ‫‪18‬‬ ‫‪[email protected]‬‬ ‫رویکردهای انحصار متقابل با حمایت سخت افزار‬ ‫‪ ‬می توان به کمک راه حل هایی که از دستورالعمل های ویژه ماشین استفاده می کنند‪ ،‬و نیاز‬ ‫به حمایت ازطرف پردازنده دارند‪ ،‬مسئله انحصار متقابل را حل کرد‪.‬این راه حل ها عبارتند از‪:‬‬ ‫دستورالعمل از کار انداختن وقفه ها‬ ‫‪(1‬‬ ‫‪ (2‬دستورالعمل های ویژه ماشین‪ :‬این دستورالعمل ها در یک چرخه دستورالعمل واحد انجام‬ ‫میشوند‪ ،‬و در معرض دخالت دستورالعمل های دیگر نیستند یعنی به صورت اتمیک و تجزیه‬ ‫ناپذیر انجام میشوند‪.‬‬ ‫‪.A‬دستور العمل ‪)Test and Set Lock(TSL‬‬ ‫‪.B‬دستورالعمل ‪SWAP‬‬  ‫‪19‬‬ ‫‪[email protected]‬‬ ‫انحصار متقابل‪ :‬از کار انداختن وقفه ها‬ ‫‪ ‬در این راه حل‪ ،‬هر فرآیند باید به محض ورود به ناحیه بحرانی‪ ،‬تمام وقفه ها را از کار‬ ‫بیندازد و دقیقا قبل ازخروج از ناحیه بحرانی‪ ،‬همه وقفه ها را مجددا فعال سازد‪.‬در این‬ ‫صورت پردازنده نمی تواند از فرآیندی به فرآیند دیگر سوئیچ کند‪ ،‬چون وقفه ساعت غیر‬ ‫فعال است‪.‬بنابراین وقتی که فرآیندی وقفه ها را غیر فعال میکند‪ ،‬می تواند بدون ترس‬ ‫از دخالت فرآیندهای دیگر‪ ،‬به خواندن و نوشتن در حافظه مشترک بپردازد‪.‬‬ ‫‪ ‬از کار انداختن وقفه‪ ،‬انحصار متقابل را ضمانت میکند‪.‬‬ ‫‪ ‬معایب‪:‬‬ ‫‪‬این رویکرد در معماری چند پردازشی کار نمیکند‪ ،‬چرا که در یک سیستم چند‬ ‫پردازشی در هر لحظه بیش از یک فرآیند در حال اجراست‪.‬‬ ‫‪‬از معایب این روش اینست که امکان دارد فرایندی وقفه ها را بعد از غیر فعال‬ ‫کردن‪ ،‬مجددا فعال نکند‪.‬‬  20 [email protected] ‫ از کار انداختن وقفه ها‬:‫انحصار متقابل‬ :‫ رویکرد از کار انداختن وقفه ها برای انحصار متقابل به صورت زیر است‬ P(int i) { while(TRUE) { disable_interrupts( ); critical_section( ); enable_interrupts( ); non_critical_section( ); } }  ‫‪21‬‬ ‫‪[email protected]‬‬ ‫انحصار متقابل‪ :‬دستورالعمل های ویژه ماشین‬ ‫دستورالعمل آزمون و مقدار گذاری)‪:TSL(Test and Set Lock‬‬ ‫‪ ‬محتویات یک کلمه از حافظه (‪ )lock‬را خوانده و در ثبات قرار میدهد‪.‬سپس مقدار ‪ 1‬را در‬ ‫همان آدرس از حافظه ذخیره می کند‪.‬این عملیات غیر قابل تقسیم انجام می شوند و تا اینکه‬ ‫اجرای دستورالعمل تمام نشود‪ ،‬هیچ فرآیند و یا پردازنده دیگری نمی تواند به این کلمه از‬ ‫حافظه دسترسی پیدا کند‪.‬‬  ‫‪22‬‬ ‫‪[email protected]‬‬ ‫انحصار متقابل‪ :‬دستورالعمل های ویژه ماشین‬ ‫‪ ‬این راه حل‪ ،‬انحصار متقابل و پیشرفت را رعایت‬ ‫)‪boolean testset (int i‬‬ ‫می کند ولی انتظار محدود به دلیل گرسنگی را‬ ‫{‬ ‫رعایت نمی کند‪.‬‬ ‫)‪if (i == 0‬‬ ‫{‬ ‫;‪i = 1‬‬ ‫;‪return true‬‬ ‫}‬ ‫‪else‬‬ ‫{‬ ‫;‪return false‬‬ ‫}‬ ‫}‬  ‫‪23‬‬ ‫‪[email protected]‬‬ ‫انحصار متقابل‪ :‬دستورالعمل های ویژه ماشین‬ ‫دستورالعمل معاوضه‪:SWAP‬‬ ‫‪ ‬می توان از دستورالعملی به نام ‪ ،swap‬برای نوشتن یک روال ورود به ناحیه بحرانی استفاده‬ ‫کرد‪.‬این دستور می تواند در یک عمل واحد غیر قابل تقسیم‪ ،‬محتویات یک رجیستر پردازنده‬ ‫را با محتویات یک کلمه حافظه‪ ،‬جابجا کند‪.‬‬ ‫‪ Xchg ‬نام دیگر ‪ swap‬می باشد‪.‬‬ ‫‪ ‬انحصار متقابل و پیشرفت را رعایت می کند ولی انتظار محدود به دلیل گرسنگی را رعایت‬ ‫نمیکند‪.‬‬ ‫)‪void exchange(int register, int memory‬‬ ‫{‬ ‫;‪int temp‬‬ ‫;‪temp = memory‬‬ ‫;‪memory = register‬‬ ‫;‪register = temp‬‬ ‫}‬  ‫‪24‬‬ ‫‪[email protected]‬‬ ‫انحصار متقابل‪ :‬دستورالعمل های ویژه ماشین‬ ‫‪ ‬مزایا ‪:‬‬ ‫‪ ‬برای هر تعداد از فرآیندها‪ ،‬روی یک پردازنده و یا چند پردازنده‪ ،‬که از حافظه مشترک‬ ‫استفاده میکنند‪ ،‬قابل به کار گیری است‪.‬‬ ‫‪ ‬ساده است و بنابراین وارسی آن آسان است‪.‬‬ ‫‪ ‬از آن برای حمایت از بخش های بحرانی متعدد میتوان استفاده کرد که در آن هر بخش‬ ‫بحرانی میتواند با متغیر خاص خود تعریف شود‪.‬‬ ‫‪ ‬معایب‪:‬‬ ‫‪ ‬انتظار مشغولی وجود دارد‪.‬‬ ‫‪ ‬امکان گرسنگی وجود دارد‪ :‬هنگامی که فرآیندی بخش بحرانی خود را ترک میکند‬ ‫وبیش از یک فرآیند در انتظار است‪.‬‬ ‫‪ ‬امکان بن بست وجود دارد‪ :‬اگر یک فرآیند با اولویت پایین در بخش بحرانی خود باشد‬ ‫و به یک فرآیند با اولویت باالتر نیاز داشته باشد‪ ،‬و همینطور فرآیند اولویت باالتر در انتظار‬ ‫ورود به بخش بحرانی باشد بن بست رخ میدهد‪.‬‬  ‫‪25‬‬ ‫‪[email protected]‬‬ ‫رویکردهای نرم افزاری انحصار متقابل‬ ‫‪ ‬راه حل های نرم افزاری مستقیما توسط برنامه ها استفاده می شوند و وجود حافظه اشتراکی‬ ‫ضروری می باشد‪.‬‬ ‫‪ ‬در این راه حل ها از دستورالعمل های خاص توسط سخت افزار استفاده نمیشود و حمایتی از‬ ‫سیستم عامل و زبان های برنامه سازی نداریم‪.‬‬ ‫‪ ‬روشهای ارائه شده عبارتند از‪:‬‬ ‫‪ ‬الگوریتم ‪( Decker‬پنج مرحله تالش)‬ ‫‪ (1‬تالش اول (تناوب قطعی) ‪ /‬با استفاده از متغیر ‪turn‬‬ ‫‪ (2‬تالش دوم با استفاده از پرچم مشترک ‪flag‬‬ ‫‪ (3‬تالش سوم با استفاده از متغیرهای قفل ‪lock‬‬ ‫‪ (4‬تالش چهارم (ادب و تعارف) با استفاده از متفیر نوبت ‪ turn‬و پرچم ‪flag‬‬ ‫‪ (5‬تالش پنجم (راه حل صحیح)‬ ‫‪ ‬الگوریتم پترسون ‪Peterson‬‬  ‫‪26‬‬ ‫‪[email protected]‬‬ ‫تالش اول‬ ‫هر فرآیند مقدار متغیر ‪ Turn‬را بررسی می کند‪ ،‬اگر برابر شماره آن فرآیند بود به بخش‬ ‫‪‬‬ ‫بحرانی خود وارد میشود‪.‬‬ ‫انتظار مشغولی دارد یعنی فرآیند همواره در حال چک کردن است تا ببیند آیا میتواند به بخش‬ ‫‪‬‬ ‫بحرانی خود وارد شود یا نه‪.‬‬ ‫اگر فرآیندی چه در بخش بحرانی و چه در خارج آن با شکست مواجه شود‪ ،‬فرآیند دیگر‬ ‫‪‬‬ ‫مسدود می ماند‪.‬‬ ‫در این حالت فرآیند تا وقتی که وارد ناحیه بحرانی نشود‪ ،‬هیچ کار مفیدی انجام نمی دهد‪.‬‬ ‫‪‬‬ ‫فرآیندها به نوبت از ناحیه بحرانی استفاده می کنند‪.‬‬ ‫‪‬‬ ‫ساختاری که در باال گفته شد ساختار همروال است؛ هم روال ها برای این طراحی شدند تا‬ ‫‪‬‬ ‫بتوانند کنترل اجرا را بین یکدیگر عقب و جلو ببرند‪.‬‬ ‫این فن تنها برای ساخت دادن به یک فرآیند واحد است‪ ،‬و برای حمایت از پردازش همزمان‬ ‫‪‬‬ ‫کافی نیست‬  ‫‪27‬‬ ‫‪[email protected]‬‬ ‫تالش اول‬ ‫‪ ‬در این روش از یک متغیر سراسری مشترک به نام ‪ turn‬استفاده شده که دو مقدار ‪ 0‬یا ‪ 1‬را‬ ‫می تواند بگیرد‪.‬مقدار اولیه ‪ turn‬برابر صفر است‪.‬بنابراین ابتدا ‪ P0‬می تواند وارد ناحیه‬ ‫بحرانی شود‪.‬در این حالت ‪ P1‬در حلقه ‪ while‬منتظر می ماند تا ‪ P0‬از ناحیه بحرانی خارج‬ ‫شده و ‪ turn‬را یک کند‪.‬در این صورت ‪ P1‬می تواند وارد ناحیه بحرانی شود‪.‬برنامه فرایندها‬ ‫به صورت زیر است‪:‬‬  ‫‪28‬‬ ‫‪[email protected]‬‬ ‫تالش اول‬ ‫بررسی شرط ها در تالش اول‪:‬‬ ‫‪ ‬انحصار متقابل‪ :‬راه حل گفته شده انحصار متقابل را تضمین می کند و امکان ندارد که ‪ P0‬و ‪ P1‬با‬ ‫هم وارد ناحیه بحرانی شوند‪.‬‬ ‫‪ ‬پیشرفت‪ :‬این روش شرط پیشرفت را رعایت نمی کند‪.‬چون اگر ‪ P1‬وارد ناحیه بحرانی شود و کارش‬ ‫تمام شده و به بخش غیر بحرانی برود‪ ،‬در این حالت ‪ turn‬برابر صفر می باشد‪.‬حال نوبت ‪ P0‬است که‬ ‫وارد ناحیه بحرانی شود‪ ،‬ولی می خواهد به مدت طوالنی در ناحیه غیر بحرانی بماند و تا زمانی که وارد‬ ‫ناحیه بحرانی نشود و متغیر ‪ turn‬را یک نکند ‪ P1‬نمی تواند وارد ناحیه بحرانی شود‪.‬در این سناریو‪،‬‬ ‫‪P1‬توسط فرایندی منتظر مانده بود که در ناحیه بحرانی نبود و جلوی پیشرفت اش را گرفته بود‪.‬‬ ‫‪ ‬انتظار محدود‪ :‬در این روش قحطی نداریم‪ ،‬چون فرایندها به صورت یک در میان و نوبتی وارد ناحیه‬ ‫بحرانی می شوند‪.‬همچنین بن بست نیز نداریم‪.‬بنابراین شرط انتظار محدود رعایت می شود‪.‬‬ ‫‪ ‬معایب روش‪:‬‬ ‫‪ ‬سرعت عملیات توسط فرایند کندتر تعیین می شود‪ ،‬چون فرایندها برای دسترسی به ناحیه بحرانی‬ ‫باید به صورت یک در میان عمل کنند‪.‬‬ ‫‪ ‬اگر فرایندی در ناحیه بحرانی از کار بیفتد‪ ،‬فرایند دیگر تا ابد منتظر خواهد ماند‪.‬‬  ‫‪29‬‬ ‫‪[email protected]‬‬ ‫تالش دوم‬ ‫‪ ‬در این روش از یک بردار دودویی استفاده میشود که در آن ]‪ Flag[i‬مربوط به فرآیند ‪ i‬است‪.‬‬ ‫‪ ‬هر فرآیند میتواند مقدار مربوط به فرآیند دیگر را بیازماید‪ ،‬ولی نمیتواند آنرا تغییر دهد‪.‬‬ ‫‪ ‬هنگامی که فرآیند میخواهد وارد ناحیه بحرانی خود شود ابتدا مقدار سایر فرآیند ها را بررسی‬ ‫میکند‪.‬‬ ‫‪ ‬اگر هیچ فرآیندی در بخش بحرانی خود نبود (یا ‪ Flag‬برای همه فرآیند ها ‪ False‬بود) فرآیند‬ ‫بالفاصله مقدار ‪ Flag‬خود را ‪ True‬میکند و وارد بخش بحرانی خود میشود‪.‬هنگام خروج‬ ‫فرآیند مقدار ‪ Flag‬را به ‪ False‬برمیگرداند‪.‬‬ ‫‪ ‬در این صورت اگر فرآیندی در ناحیه بحرانی خود شکست بخورد‪ ،‬فرآیند دیگر تا ابد مسدود‬ ‫است‪.‬‬ ‫‪ ‬این روش انحصار متقابل را تضمین نمی کند‪.‬‬  ‫‪30‬‬ ‫‪[email protected]‬‬ ‫تالش دوم‬ ‫‪ ‬در این روش هر فرایند دارای کلید مجزا برای ورود به ناحیه بحرانی است تا اگر‬ ‫فرایندی قصد استفاده از ناحیه بحرانی را نداشت‪ ،‬فرایند دیگر بتواند به ناحیه‬ ‫بحرانی خود دسترسی داشته باشد‪.‬برنامه فرایندها به صورت زیر است‪:‬‬  ‫‪31‬‬ ‫‪[email protected]‬‬ ‫تالش دوم‬ ‫بررسی شرط ها در تالش اول‪:‬‬ ‫‪ ‬انحصار متقابل‪ :‬این روش انحصار متقابل رعایت نمی شود‪.‬یعنی حتی از روش اول هم بدتر‬ ‫است‪.‬درنظر بگیرید زمانی که دو فرایند ‪ p0‬و ‪ p1‬همزمان فلگ های طرف مقابل چک کنند و‬ ‫‪ false‬ببینند و پرچم خود را ‪ true‬کرده و باهم وارد ناحی بحرانی میشوند‪.‬‬ ‫‪ ‬پیشرفت‪ :‬این روش شرط پیشرفت را رعایت می کند‬ ‫‪ ‬انتظار محدود‪ :‬این روش شرط انتظار محدود را رعایت نمی کند‪ ،‬چون امکان قحطی دارد‪.‬در‬ ‫این تالش امکان ورود پی در پی یک فرایند به ناحیه بحرانی و عدم دستیابی فرایند دیگر به‬ ‫ناحیه بحرانی وجود دارد‪.‬‬ ‫‪ ‬یکی از معایب این روش این است که اگر فرایندی در ناحیه بحرانی از کار بیفتد‪ ،‬فرایند دیگر‬ ‫تا ابد منتظر خواهد ماند‪.‬‬  ‫‪32‬‬ ‫‪[email protected]‬‬ ‫تالش سوم‬ ‫‪ ‬فرآیند ‪ P1‬قبل از بررسی سایر فرآیند ها مقدار پرچم وضعیت خود را برای ورود‬ ‫به ناحیه بحرانی می نشاند‪.‬‬ ‫‪ ‬هنگامی که فرآیند دیگری مثل ‪ P2‬در ناحیه بحرانی است و پرچم فرآیند ‪، P1‬‬ ‫‪ True‬است فرآیند ‪ P1‬تا زمانی که فرآیند ‪ P2‬از ناحیه بحرانی خارج شود در حالت‬ ‫مسدود میماند‪.‬‬ ‫‪ ‬امکان بن بست وجود دارد‪.‬هنگامی که دو فرآیند ‪ Flag‬خود را برای ورود به ناحیه‬ ‫بحرانی ‪ True‬میکنند‪ ،‬در این صورت هر فرآیند باید در انتظار فرآیند دیگر برای‬ ‫رهایی ناحیه بحرانی باشد‪.‬‬  ‫‪33‬‬ ‫‪[email protected]‬‬ ‫تالش سوم‬ ‫بررسی شرط ها‪:‬‬ ‫‪ ‬انحصار متقابل‪ :‬اگر یکی از فرایندها بتواند وارد ناحیه بحرانی شود‪ ،‬چون قبل از بررسی ‪ flag‬مقابل‪،‬‬ ‫‪ flag‬خود را ‪ TRUE‬کرده ‪ ،‬جلوی ورود فرایند مقابل را میگیرد‪.‬بنابراین شرط انحصار متقابل برقرار‬ ‫است‪.‬‬ ‫‪ ‬پیشرفت‪ :‬این روش شرط پیشرفت را رعایت می کند‪(.‬با همان استدالل تالش دوم)‬ ‫‪ ‬انتظار محدود‪ :‬در این روش شرط انتظار محدود رعایت نمی شود‪ ،‬چون امکان بن بست وجود دارد‪.‬‬ ‫سناریو‪ :‬فرض کنید که ‪ ،P0‬پرچم خود را ‪ TRUE‬کند ولی قبل از بررسی [‪[flag 1‬در برنامه ‪ ،P0‬به‬ ‫‪ P1‬سوئیچ شود و ‪ P1‬پرچم خود را ‪TRUE‬کند‪.‬در این صورت هر دو فرایند تا ابد در حلقه انتظار‬ ‫گرفتار میشوند و بن بست رخ می دهد‪.‬‬  ‫‪34‬‬ ‫‪[email protected]‬‬ ‫تالش چهارم‬ ‫‪ ‬در تالش قبلی هر فرایند می تواند روی حق خود برای ورود به بخش بحرانی اش‬ ‫پافشاری کند؛ اما در این روش هر فرآیند ‪ Flag‬خود را مقدار دهی میکند تا تمایل خود‬ ‫را برای ورود به ناحیه بحرانی نشان دهد‪.‬اما آماده است ‪ Flag‬خود را برای احترام به‬ ‫سایر فرآیند ها تغییر دهد‪.‬‬ ‫‪ ‬سایر فرآیند ها بررسی میشوند‪ ،‬اگر یکی از آنها در بخش بحرانی بود مقدار ‪ Flag‬به‬ ‫‪ False‬باز میگردد و بعدا دوباره مقدار دهی میشود تا تمایل خود را برای ورود به ناحیه‬ ‫بحرانی نشان دهد‪.‬این چرخه تا زمان ورود ادامه دارد‪.‬‬ ‫‪ ‬چرخه تست ‪ Flag‬میتواند به طور نامحدود گسترش یابد‪ ،‬اما این یک بن بست نیست‬ ‫چرا که بن بست زمانی رخ میدهد که چند فرآیند بخواهند به بخش بحرانی وارد شوند‬ ‫ولی هیچ کدام نتوانند‪.‬به این حالت بن باز گفته میشود‪ ،‬چرا که هر تغییری در سرعت‬ ‫نسبی دو فرآیند چرخه را شکسته و موجب ورود به ناحیه بحرانی میشود‪.‬‬ 35 [email protected] ‫تالش چهارم‬  ‫‪36‬‬ ‫‪[email protected]‬‬ ‫تالش چهارم‬ ‫بررسی شرط ها‪:‬‬ ‫‪ ‬انحصار متقابل‪ :‬راه حل گفته شده انحصار متقابل را تضمین می کند‪(.‬با‬ ‫استدالل تالش سوم)‬ ‫‪ ‬پیشرفت‪ :‬این روش شرط پیشرفت را رعایت می کند‪(.‬با همان استدالل تالش‬ ‫دوم و سوم)‬ ‫‪ ‬انتظار محدود‪ :‬در این روش شرط انتظار محدود رعایت نمی شود‪ ،‬چون ممکن‬ ‫است یک فرایند به مدت نامعلوم و بدون حد باالی مشخص‪ ،‬گرفتار قسمت‬ ‫تاخیر )(‪ delay‬شود و فرایند مقابل به دفعات وارد ناحیه بحرانی شود‪.‬بنابراین‬ ‫به دلیل امکان گرسنگی‪ ،‬شرط انتظار محدود رعایت نمی شود‪.‬‬  ‫‪37‬‬ ‫‪[email protected]‬‬ ‫تالش پنجم‬ ‫‪ Decker ‬بعد از چهار تالش ناموفق‪ ،‬یک راه حل درست که شرایط انحصار‬ ‫متقابل‪ ،‬انتظار محدود و پیشرفت را با هم رعایت می کند‪ ،‬ارائه داد‪.‬‬ ‫‪ ‬در این روش متغیر نوبت را با متغیرهای پرچم ترکیب کرد‪.‬این الگوریتم در زیر‬ ‫آورده شده است‪.‬‬  ‫‪38‬‬ ‫‪[email protected]‬‬ ‫تالش پنجم‬ ‫هنگامی که ‪ P0‬بخواهد وارد بخش بحرانی خود شود‪ ،‬در ‪ flag‬مربوط به خود مقدار‬ ‫‪TRUE‬می گذارد‪.‬سپس ‪ flag‬مربوط به‪ P1‬را بررسی می کند که دو حالت رخ می دهد‪:‬‬ ‫‪ ‬الف‪[flag 1[ -‬برابر ‪TRUE‬باشد‪:‬‬ ‫‪ ‬اگر ‪ turn‬برابر یک باشد‪ P0 ،‬به ‪ P1‬احترام گذاشته و با ‪ FALSE‬کردن پرچمش‬ ‫منتظر می ماند‪.‬در این هنگام ‪ P0‬کاری انجام نمی دهد تا ‪turn‬برابر صفر شود و‬ ‫سپس ‪ flag‬خودش را ‪ TRUE‬می کند‪.‬‬ ‫‪ ‬ب‪[flag 1[ -‬برابر ‪FALSE‬باشد‪:‬‬ ‫‪ P0 ‬وارد بخش بحرانی شده و بعد از خروج از بخش بحرانی‪ ،‬در ‪ flag‬خود مقدار‬ ‫‪ FALSE‬می گذارد تا بخش بحرانی را آزاد کند و در ‪ turn‬مقدار ‪ 1‬را قرار می دهد‬ ‫تا حق پافشاری را به ‪ P1‬واگذارد‪.‬‬ ‫‪39‬‬ ‫‪[email protected]‬‬ ‫خالصه ای از وضعیت تالش های ‪Decker‬‬ ‫تالش های‬ ‫انتظار محدود‬ ‫پیشرفت‬ ‫انحصار متقابل‬ ‫‪Decker‬‬ ‫‪‬‬ ‫‪-‬‬ ‫‪‬‬ ‫تالش اول‬ ‫‪-‬‬ ‫‪‬‬ ‫‪-‬‬ ‫تالش دوم‬ ‫‪-‬‬ ‫‪‬‬ ‫‪‬‬ ‫تالش سوم‬ ‫‪-‬‬ ‫‪‬‬ ‫‪‬‬ ‫تالش چهارم‬ ‫‪‬‬ ‫‪‬‬ ‫‪‬‬ ‫تالش پنجم‬  ‫‪40‬‬ ‫‪[email protected]‬‬ ‫الگوریتم پترسون‬ ‫چندین سال بعد‪ ،‬پترسون راه حل ساده و زیبایی را برای حل مسئله انحصار متقابل ارائه کرد‪.‬‬ ‫‪‬‬ ‫این الگوریتم به سادگی برای ‪ n‬فرایند نیز قابل تعمیم است‪.‬‬ ‫‪‬‬ ‫در این روش هم از آرایه برداری دودویی ‪ Flag‬و هم از متغیر ‪ Turn‬استفاده میشود‪.‬‬ ‫‪‬‬ ‫هر فرآیند برای ورود به ناحیه بحرانی ابتدا مقدار ‪ Flag‬خود را ‪ True‬میکند و سپس در انتظار‬ ‫‪‬‬ ‫مقدار ‪ Turn‬میماند‬  ‫‪41‬‬ ‫‪[email protected]‬‬ ‫الگوریتم پترسون‬ ‫بررسی شرایط‪:‬‬ ‫‪ ‬الگوریتم پترسون شرایط انحصار متقابل‪ ،‬انتظار محدود و پیشرفت را با هم رعایت‬ ‫می کند‪.‬و مشکل بن بست و قحطی ندارد‪.‬‬ ‫‪ ‬این الگوریتم ساده ترین و کوتاهترین راه حل نرم افزاری است‪.‬‬ ‫‪ ‬معایبی که در هر یک از تالش های ‪ Decker‬و همچنین روش ‪Peterson‬‬ ‫وجود دارند‪ ،‬عبارتنداز‪:‬‬ ‫‪ ‬اگر یکی از فرایندها در داخل ناحیه بحرانی از کار بیفتد‪ ،‬فرایند دیگر تا ابد‬ ‫منتظر می ماند‪.‬‬ ‫‪ ‬مبتنی بر انتظار مشغول می باشند‪.‬‬  ‫‪42‬‬ ‫‪[email protected]‬‬ ‫راهکارهای سیستم عامل و زبان برنامه سازی برای تدارک همزمانی‬ ‫راهکارهای سیستم عامل و زبان برنامه سازی برای تدارک همزمانی عبارتند از‪:‬‬ ‫‪ (1‬سمافور(راهنما)‪:‬‬ ‫سمافور یک ساختار شامل یک شمارنده صحیح و یک صف است‪.‬روشی بسیار قدرتمند اما پیچیده است‪.‬‬ ‫ناظر (مانیتور)‬ ‫‪(2‬‬ ‫مانیتور ساختاری از زبان برنامه سازی است که همان کار سمافور را انجام می دهد و کنترل آن هم ساده تر است‪.‬‬ ‫سمافور اغلب توسط سیستم عامل پشتیبانی می شود و می تواند توسط زبان برنامه سازی نیز پشتیبانی شود‪ ،‬اما‬ ‫مانیتور بایدفقط توسط زبان برنامه سازی پشتیبانی شود‪.‬ساختار مانیتور در زبانهای برنامه سازی به صورت برنامه‬ ‫کتابخانه ای پیاده سازی شده است‪.‬این به افراد اجازه می دهد تا قفلهای مانیتور را روی هر شیئی بگذارند‪.‬مانیتور‬ ‫مولفه ای نرم افزاری‪ ،‬مشتمل بر یک یا چند رویه‪ ،‬دنباله ای از مقدارگذاری های اولیه و داده های محلی است‪.‬‬ ‫‪ (3‬تبادل پیام‬ ‫وقتی فرآیندها با یکدیگر محاوره می کنند‪ ،‬نیازهای همگام سازی و ارتباط باید تامین شود‪.‬فرآیندها نیاز به همگام‬ ‫سازی دارند تا انحصار متقابل اعمال گردد‪.‬ممکن است فرآیندهایی که با یکدیگر همکاری می کنند نیاز به تبادل‬ ‫اطالعات داشته باشند‪.‬یک رویکرد در فراهم کردن این دو عمل‪ ،‬تبادل پیام است‪.‬عمل واقعی تبادل پیام به شکل دو‬ ‫دستور ‪ send‬و ‪ recive‬ارائه می شود‪.‬‬  ‫‪43‬‬ ‫‪[email protected]‬‬ ‫راهنما )‪(Semaphore‬‬ ‫‪ ‬راه حل های نرم افزاری و سخت افزاری دارای نقاط ضعف زیادی هستند‪.‬‬ ‫‪ ‬سمافور دارای قدرت زیادی در برقراری انحصار متقابل می باشد و همچنین از عهده‬ ‫انواع مختلف مسائل همگام سازی بر می آید‪.‬‬ ‫‪ ‬راهنما یا سمافور یک سیستم ارتباطی هستند که از پرچم ها استفاده میکنند‪.‬دو‬ ‫ایستگاه کاری فرستنده وگیرنده وجود دارد که این دو باید به وضوح همدیگر را ببینند‪.‬‬ ‫‪ ‬معموال برای مسافت های طوالنی تعدادی ایستگاه تکرار کننده بین فرستنده و گیرنده‬ ‫وجود دارد‪.‬‬ ‫‪ ‬راهنما‪ ،‬مکانیسمی است که از دسترسی دو یا چند فرآیند به منابع مشترک به طور‬ ‫همزمان جلوگیری میکند‪.‬به عنوان مثال در یک راه آهن راهنما از برخورد قطار ها با‬ ‫هم در یک ریل مشترک جلوگیری میکند‪.‬در صورتیکه به راهنما توجهی نشود‬ ‫تضمینی وجود ندارد که قطار ها با هم برخورد نکنند به طور مشابه درکامپیوتر در‬ ‫صورت عدم توجه به راهنما احتمال اغتشاش فرآیندها وجود دارد‪.‬‬ ‫‪44‬‬ ‫‪[email protected]‬‬ ‫راهنما )‪(Semaphore‬‬ ‫‪ ‬زمانی که یک پیام راهنما فرستاده میشود‪ ،‬دو ایستگاه‬ ‫وجود دارد ‪ :‬فرستنده و گیرنده‪.‬‬ ‫‪ ‬هر ایستگاه از دو نفر تشکیل شده ‪ :‬عالمت دهنده و‬ ‫دستیار‪.‬‬ ‫‪ ‬عالمت دهنده پرچم ها را نگه میدارد و دستیار پیام ها‬ ‫را ضبط میکند و نتیجه را به عالمت دهنده میدهد‪.‬‬ ‫‪ ‬راهنما ها مانند پرچم ها عمل میکنند به همین دلیل به‬ ‫آنها راهنما گفته میشود‪.‬‬ ‫‪ ‬یک راهنما میتواند ‪ On‬یا ‪ Off‬باشد‪.‬یک فرآیند میتواند‬ ‫یک پرچم را ‪ On‬یا ‪ Off‬کند‪.‬اگر پرچم ‪ On‬باشد و‬ ‫فرآیندی بکوشد تا آنرا ‪ On‬کند‪ ،‬آن فرآیند تا زمانی که‬ ‫پرچم ‪ Off‬شود منتظر می ماند‪.‬‬  ‫‪45‬‬ ‫‪[email protected]‬‬ ‫ساختار راهنما )‪(Semaphore‬‬ ‫سمافور یک ساختار شامل فیلدهای زیر است‪:‬‬ ‫‪ (1‬شمارنده صحیح (‪)count‬‬ ‫از شمارنده برای شمارش تعداد ‪ wakeup‬هایی که می خواهند هدر بروند‪ ،‬استفاده‬ ‫می شود‪.‬با این کار این سیگنال ها برای استفاده های بعدی ذخیره می شوند‪.‬‬ ‫‪ (2‬صف (‪)queue‬‬ ‫از صف برای نگهداری فرایندهای بلوکه شده بر روی سمافور استفاده می شود‪.‬‬ ‫‪ ‬توسط ‪ ،Dijkstra‬دو تابع ‪ wait‬و ‪ signal‬مطرح شدند که به ترتیب تعمیم‬ ‫یافته ‪ sleep‬و ‪ wakeup‬هستند‪.‬‬  ‫‪46‬‬ ‫‪[email protected]‬‬ ‫انواع سمافور‬ ‫‪ ‬سمافورها بر دو نوعند‪:‬‬ ‫‪ ‬عمومی‪ :‬شمارنده می تواند مثبت‪ ،‬صفر و یا منفی باشد‪.‬‬ ‫‪ ‬دودویی‪ :‬شمارنده فقط مقادیر صفر و یک را دریافت می کند‪.‬‬ ‫‪ ‬قدرت سمافور دودویی معادل با سمافور عمومی است‪.‬‬ ‫‪ ‬در سمافورها صفی برای نگهداری فرایندهای بلوکه شده استفاده می شود‪.‬اگر خروج از‬ ‫این صف به ترتیب ورود باشد(‪)FIFO‬؛ به آن سمافور قوی می گویند و اگر این چنین‬ ‫نباشد‪ ،‬به آن سمافور ضعیف میگویند‪.‬‬ ‫‪ ‬در سمافور ضعیف‪ ،‬امکان گرسنگی وجود دارد‪.‬‬ ‫‪ ‬در بعضی از متون از حرف ‪ P‬یا ‪ down‬به جای ‪ wait‬و از حرف ‪ V‬یا ‪ up‬به جای‬ ‫‪ signal‬استفاده میشود‪.‬‬  47 [email protected] ‫توابع سمافور عمومی‬ struct semaphore{ int count; queueType queue; }; void semWait(semaphore s) void semSignal(semaphore s) { { s.count--; s.count++; if (s.count < 0) if (s.count ≤ 0) { { place this process in s.queue; remove a process P from s.queue; block this process; place process P on ready list; } } } }  48 [email protected] ‫توابع سمافور دودویی‬ struct binary_semaphore { enum {0,1} value; queueType queue; }; void semWaitB(binary_semaphore s) void semSignalB(binary_semaphore s) { { if (s.value == 1) if (s.queue is empty()) s.value = 1; s.value = 0; else else { { remove a process P from s.queue; place this process in s.queue; place process P on ready list; block this process; } } } }  ‫‪49‬‬ ‫‪[email protected]‬‬ ‫عملیات روی راهنمای عمومی‬ ‫‪ ‬یک راهنما میتواند با یک مقدار غیر منفی صحیح مقدار دهی اولیه شود‪.‬‬ ‫‪ ‬عمل ‪ Wait‬مقدار راهنما را یک واحد کاهش میدهد‪.‬اگر مقدار منفی شود آنگاه‬ ‫فرآیندی که دستور ‪ Wait‬را اجرا کرده مسدود میشود(در صف مسدود قرار‬ ‫میگیرد)‪.‬‬ ‫‪ ‬عمل ‪ Signal‬مقدار راهنما را یک واحد افزایش میدهد‪.‬اگر مقدار مثبت نباشد‬ ‫آنگاه فرآیندی که توسط دستور ‪ Wait‬مسدود شده بود آزاد میگردد‪.‬‬ ‫‪ ‬غیر این ‪ 3‬عمل راه دیگری برای دستکاری سمافور وجود ندارد‪.‬‬  ‫‪50‬‬ ‫‪[email protected]‬‬ ‫انحصار متقابل به وسیله سمافورها‬ ‫برای حل یک مسئله با سمافور‪ ،‬باید بدانیم که‪:‬‬ ‫;‪semaphore mutex =1‬‬ ‫‪ (1‬به چند سمافور نیاز است‪.‬‬ ‫)‪void p(int i‬‬ ‫‪ (2‬مقدار اولیه شمارنده هر سمافور چند باید باشد‪.‬‬ ‫{‬ ‫‪ (3‬عمل ‪ signal‬و ‪ wait‬در کجای برنامه باید‬ ‫)‪while(TRUE‬‬ ‫روی سمافور انجام شود‪.‬‬ ‫{‬ ‫;)‪wait(mutex‬‬ ‫مسئله انحصار متقابل برای دو فرایند ‪ p1‬و ‪p2‬‬ ‫;) (‪critical-section‬‬ ‫توسط برنامه مقابل پیاده سازی شده است‪.‬در این‬ ‫;)‪signal(mutex‬‬ ‫برنامه عمل ‪ wait‬قبل از ورود به ناحیه بحرانی و‬ ‫عمل ‪ signal‬بعد از خروج از ناحیه بحرانی روی‬ ‫سمافور دودویی ‪mutex‬با مقدار اولیه ‪ 1‬انجام شده ;) (‪non-critical-section‬‬ ‫}‬ ‫است‪:‬‬ ‫}‬  ‫‪51‬‬ ‫‪[email protected]‬‬ ‫انحصار متقابل به وسیله سمافورها‬ ‫‪ ‬فرض کنیم ‪ P1‬اول اجرا شود‪.‬با اجرای تابع ‪، wait‬چون مقدار سمافور یک است‪،‬آن را‬ ‫صفر میکند و وارد ناحیه بحرانی می شود‪.‬در زمانی که ‪ P1‬در ناحیه بحرانی است‪ ،‬اگر‬ ‫‪ P2‬سعی به ورود به ناحیه بحرانی داشته باشد‪ ،‬چون سمافور برابر صفر است‪ ،‬این‬ ‫فرایند بلوکه شده و در صف قرار می گیرد‪.‬بعد از خروج ‪P1‬از ناحیه بحرانی‪ ،‬تابع‬ ‫‪signal‬را اجرا کرده و چون صف خالی نیست‪P2 ،‬که در صف قرار دارد را آزاد می‬ ‫کند و ‪ P2‬میتواند وارد ناحیه بحرانی شود‪.‬‬ ‫‪ ‬می توان با استفاده از سمافور عمومی‪ ،‬انحصار متقابل را برای بیش از دو فرایند نیز‬ ‫پیاده سازی کرد‪.‬‬ ‫‪ ‬پیاده سازی انحصار متقابل به کمک سمافور دارای مزایایی است از جمله‪ :‬تامین شرط‬ ‫های انحصارمتقابل‪،‬پیشرفت و انتظار محدود ‪.‬این روش عادالنه است‪ CPU،‬را تلف‬ ‫نمیکند‪.‬‬  52 [email protected] ‫مثالی از مکانیسم سمافور‬ Value of Semaphore Process Process Critical Region Queue lock A B Normal Execution Blocked on semaphore 1 semWait(lock) lock 0 semWait(lock) B -1 semSignal(lock) 0 semSignal(lock) 1  ‫‪53‬‬ ‫‪[email protected]‬‬ ‫ناظر )‪(Monitor‬‬ ‫‪ ‬همگام سازی فرایندها با سمافور پیچیده است‪ ،‬در واقع تنها مشکل سمافور در‬ ‫سیستمی که حافظه مشترک دارد‪ ،‬پیچیدگی استفاده از آن در حل مسائل همگام‬ ‫سازی می باشد‪.‬اگر برنامه نویس در استفاده از سمافور دقت الزم را نکند‪،‬ممکن است‬ ‫دچار بن بست شود‪.‬‬ ‫‪ ‬مانیتور ساختاری از زبان برنامه سازی است که همان کار سمافور را انجام می دهد و‬ ‫کنترل آن هم ساده تر است‪.‬سمافور اغلب توسط سیستم عامل پشتیبانی می شود و‬ ‫می تواند توسط زبان برنامه سازی نیز پشتیبانی شود‪ ،‬اما مانیتور باید فقط توسط زبان‬ ‫برنامه سازی پشتیبانی شود‪.‬‬ ‫‪ ‬ساختار مانیتور در زبانهای برنامه سازی به صورت برنامه کتابخانه ای پیاده سازی شده‬ ‫است‪.‬این به افراد اجازه می دهد تا قفل های مانیتور را روی هر شیئی بگذارند‪.‬مانیتور‬ ‫مولفه ای نرم افزاری‪ ،‬مشتمل بر یک یا چند رویه‪ ،‬دنباله ای از مقدارگذاری های اولیه و‬ ‫داده های محلی است‪.‬‬  ‫‪54‬‬ ‫‪[email protected]‬‬ ‫ناظر )‪(Monitor‬‬ ‫‪ ‬مانیتور یک ماژول نرم افزاری از مجموعه ای از رویه ها‪ ،‬متغیر ها‪ ،‬و ساختمان‬ ‫داده هاست‪.‬‬ ‫‪ ‬پردازش ها در هر زمان میتوانند زیربرنامه های داخل مانیتور را فراخوانی کرده و‬ ‫اجرا کنند‪.‬‬ ‫‪ ‬مشخصات اصلی‪:‬‬ ‫‪ ‬متغییرهای داده ای محلی فقط توسط خود مانیتور قابل دسترسی هستند‪.‬‬ ‫‪ ‬فرآیند با صدا زدن یکی از پروسه های مانیتور وارد آن می شود‪.‬‬ ‫‪ ‬در هر لحظه از زمان فقط یک فرآیند در داخل مانیتور در حال اجرا است‪.‬‬  ‫‪55‬‬ ‫‪[email protected]‬‬ ‫ویژگیهای مهم ناظر‬ ‫‪ ‬متغیر ها و داده های محلی ناظر تنها برای رویه های خود ناظر قابل دسترس است و‬ ‫هیچ رویه دیگری به آنها دسترسی ندارد‪.‬‬ ‫‪ ‬یک فرآیند با احضار یکی از رویه های ناظر وارد آن میشود‪.‬‬ ‫‪ ‬در هر زمان تنها یک فرآیند میتوان در ناظر در حال اجرا باشد‪ ،‬فرآیند های دیگری که‬ ‫ناظر را احضار کرده اند تا فراهم شدن ناظر معلق خواهند ماند‪(.‬برقراری انحصار‬ ‫متقابل)‬ 56 [email protected] ‫ساختار ناظر‬  ‫‪57‬‬ ‫‪[email protected]‬‬ ‫متغیرهای شرطی( ‪)variable condition‬‬ ‫مانیتور با استفاده از متغیرهای شرطی که تنها از داخل مانیتور‪ ،‬قابل دسترس هستند‪ ،‬از‬ ‫‪‬‬ ‫همگام سازی حمایت می کند‪.‬برای این کار از دو تابع کتابخانه ای ( ‪condition(cwait‬و‬ ‫( ‪condition(csignal‬که ساختاری از زبان برنامه سازی هستند‪ ،‬استفاده می کنند‪.‬در‬ ‫بعضی از منابع‪ ،‬از ‪c‬اول این دستورها استفاده نمی شود‪.‬‬ ‫اگر فرایندی (‪c(cwait‬را صدا بزند‪ ،‬پشت شرط ‪ c‬به خواب می رود‪.‬اگر فرایندی‬ ‫‪‬‬ ‫(‪c(csignal‬را صدا بزند‪ ،‬یک پیغام بیدار باش برای فرایندهایی که پشت شرط ‪ c‬خوابیده اند‬ ‫می فرستد که فقط یکی از آنها توسط زمانبند سیستم بیدار می شود‪.‬‬ ‫متغیرهای شرطی‪ ،‬شمارنده نیستند و مانند سمافور نمی توانند سیگنال ها را برای استفاده‬ ‫‪‬‬ ‫آینده‪ ،‬ذخیره کنند‪.‬‬ ‫امتیازی که مانیتورها نسبت به سمافورها در همگام سازی فرایندها دارند‪ ،‬این است که تمام‬ ‫‪‬‬ ‫اعمال همگام سازی درمحدوده مانیتور است‪.‬بنابراین کشف خطاها و تعیین اینکه همگام‬ ‫سازی صحیح انجام شده است‪ ،‬ساده تر می باشد‪.‬‬ ‫کامپایلر(نه برنامه نویس) انحصار متقابل را به صورت خودکار در مانیتور برقرار می سازد‬ ‫‪‬‬  ‫‪58‬‬ ‫‪[email protected]‬‬ ‫تبادل پیام (‪)Passing Message‬‬ ‫‪ ‬بطور کلی میتوان گفت سمافور ها سطح پایین هستند‪ ،‬و کار کردن با آنها مشکل است‪.‬‬ ‫مانیتور ها نیز به جز چند زبان برنامه نویسی غیر معروف غیر قابل استفاده اند‪.‬عالوه بر‬ ‫این هیچ کدام از این دو‪ ،‬امکانات الزم برای تبادل اطالعات بین کامپیوتر ها در‬ ‫کامپیوتر های توزیع شده را ندارند بنابرین تکنیک دیگری به نام تبادل پیام ابداع شد‪.‬‬ ‫‪ ‬پیام ها یک مکانیزم ساده و مناسب جهت همگام سازی و ارتباط دهی بین فرآیندها‬ ‫در یک محیط غیرمتمرکز و توزیع شده اند‪.‬‬ ‫‪ ‬بسیاری از سیستم عامل های چند برنامگی از پیام های بین فرآیند ها پشتیبانی‬ ‫میکنند‪.‬‬ ‫‪ ‬پیام مجموعه ای از اطالعات است که بین فرآیندهای ارسال کننده و دریافت کننده مبادله‬ ‫میشود‪.‬‬ ‫‪ ‬قالب پیام قابل انعطاف و قابل تبادل توسط هر زوج گیرنده و فرستنده است‪.‬‬  ‫‪59‬‬ ‫‪[email protected]‬‬ ‫تبادل پیام (‪)Passing Message‬‬ ‫‪ ‬در این روش انحصار متقابل بصورت ضمنی وجود دارد‪.‬‬ ‫‪ ‬عمل واقعی تبادل پیام به شکل دو اولیه زیر ارائه می شود‪.‬این اولیه ها‪ ،‬فراخوان‬ ‫سیستمی هستند که می توان آنها را در رویه های کتابخانه ای قرار داد‪:‬‬ ‫)‪send (destination, message‬‬ ‫)‪receive (source, message‬‬ ‫‪ ‬فراخوان ‪،send‬پیامی را از آدرسی که در فضای آدرس فرایند مبدا قرار دارد را‬ ‫برداشته (‪ )message‬را به فرایند مقصد(‪)destination‬ارسال می کند‪.‬‬ ‫‪ ‬فرخوان ‪، recevie‬یک پیام را از فرایند مبدا ( ‪)source‬دریافت کرده و آن را‬ ‫در آدرس مشخص شده ( ‪ )message‬قرار می دهد‪.‬‬  ‫‪60‬‬ ‫‪[email protected]‬‬ ‫آدرس دهی در تبادل پیام‬ ‫‪.1‬آدرس دهی مستقیم‪:‬‬ ‫‪ ‬رویه ‪ Send‬شامل شناسه مشخص فرآیند مقصد است‪.‬‬ ‫‪ ‬رویه ‪ Receive‬میتوان به یکی از دو صورت زیر داده شود‪:‬‬ ‫ فرآیند گیرنده صراحتاً فرآیند فرستنده را تعیین کند بنابراین فرآیند باید از قبل بداند‬ ‫از کدام فرآیند باید انتظار پیام داشته باشد‪.‬‬ ‫ مشخص کردن فرآیند مبدأ مورد انتظار غیر ممکن است در این حالت پارامتر مبدأ از‬ ‫رویه ‪ Receive‬دارای مقداریست که با انجام عمل دریافت برگشت داده میشود‪.‬‬  ‫‪61‬‬ ‫‪[email protected]‬‬ ‫آدرس دهی‪:‬‬ ‫‪ (2‬آدرس دهی غیر مستقیم‪:‬‬ ‫‪ ‬پیامها مستقیماً از فرستنده به گیرنده ارسال نمیشوند‪ ،‬بلکه به یک ساختمان‬ ‫داده مشترک که شامل صفهایی است که میتوانند پیامها را به طور دائمی‬ ‫نگه دارند ارسال میشود‪.‬‬ ‫‪ ‬صف ها معموالً صندوقهای پستی )‪ (Mail box‬نامیده میشوند‪.‬‬ ‫‪ ‬یک فرآیند پیام را به صندوق پستی ارسال میکند و فرآیند دیگر آن را از‬ ‫صندوق پستی بر میدارد‪.‬‬ ‫‪ ‬اگر بین فرستنده ها و گیرنده ها رابطه چند به یک وجود داشته باشد‪ ،‬به‬ ‫صندوق پستی‪" ،‬درگاه" می گویند‪.‬‬ ‫‪ ‬چهار حالت دارد‪ :‬یک به یک ‪ /‬یک به چند ‪ /‬چند به یک‪ /‬چند به چند‬ ‫‪62‬‬ ‫‪[email protected]‬‬ ‫ارتباط غیر مستقیم فرآیند ها‬ ‫یک به یک‬ ‫چند به یک‬ ‫یک به چند‬ ‫چند به چند‬  ‫‪63‬‬ ‫‪[email protected]‬‬ ‫همگام سازی ( ‪)Synchronization‬‬ ‫‪ ‬می توان به کمک ‪ send‬و ‪ receive‬امکان هماهنگی بین فرایندها را ایجاد کرد؛ تبادل پیام‬ ‫بین دو فرایند متضمن سطحی از همگام سازی بین آنها می باشد‪.‬‬ ‫‪ ‬زمانی که فرایندی‪ send ،‬را اجرا می کند‪ ،‬دو امکان وجود دارد‪:‬‬ ‫‪ ‬فرایند فرستنده تا دریافت پیام مسدود می شود‪(.‬حالت همگام)‬ ‫‪ ‬فرایند فرستنده‪ ،‬بدون توجه به عمل انجام شده‪ ،‬اجرایش ادامه می یابد‪(.‬حالت ناهمگام)‬ ‫‪ ‬زمانی که فرایندی ‪ receive‬را اجرا می کند‪ ،‬دو امکان وجود دارد‪:‬‬ ‫‪ ‬اگر پیامی قبال فرستاده شده‪ ،‬این پیام دریافت شده و اجرا ادامه می یابد‪(..‬حالت همگام)‬ ‫‪ ‬اگر پیام منتظری وجود نداشته باشد‪ ،‬فرایند تا رسیدن پیام مسدود می ماند‪(.‬حالت ناهمگام)‬ ‫‪ ‬بنابراین فرستنده و گیرنده هر دو می توانند مسدود شونده یا مسدود نشونده باشند‪(.‬منتظر‬ ‫برای پیام)‬  ‫‪64‬‬ ‫‪[email protected]‬‬ ‫حالتهای فرستنده گیرنده‬ ‫‪ (1‬مسدود شدن فرستنده‪ ،‬مسدود شدن گیرنده‪:‬‬ ‫‪ ‬هم فرستنده و هم گیرنده تا زمانی که پیام تحویل داده شود مسدودند‪.‬‬ ‫‪ ‬گاهی به آن قرار مالقات هم گفته میشود‪.‬‬ ‫‪ ‬این ترکیب همگام سازی محکم بین فرآیندها را میسر میکند‪.‬‬ ‫‪ (2‬مسدود نشدن فرستنده‪ ،‬مسدود شدن گیرنده‪:‬‬ ‫‪ ‬فرستنده به کار خود ادامه میدهد‪.‬‬ ‫‪ ‬گیرنده تا زمانی که پیام تحویل داده شود‪ ،‬مسدود است‪.‬‬ ‫‪ ‬این مفید ترین ترکیب است‪ ،‬چرا که اجازه میدهد یک پیام یا بیشتر در اسرع وقت به‬ ‫مقصد های متنوع ارسال شود‪.‬‬ ‫‪ (3‬مسدود نشدن گیرنده‪ ،‬مسدود شدن فرستنده‬ ‫‪ (4‬مسدود نشدن فرستنده‪ ،‬مسدود نشدن گیرنده‪:‬‬ ‫‪ ‬انتظار هیچ یک از دو طرف ضروری نیست‬  ‫‪65‬‬ ‫‪[email protected]‬‬ ‫قالب پیام‬ ‫‪ ‬قالب پیام به اهداف امکانات پیام دهی و اینکه این امکانات روی یک کامپیوتر یا‬ ‫یک سیستم توزیعی اجرا میشوند بستگی دارد‪.‬‬ ‫‪ ‬بعضی سیستم عاملها برای حداقل کردن سربار پردازش و حافظه پیامهای کوچک‬ ‫با طول ثابت را ترجیح داده اند‪.‬‬ ‫‪ ‬قالب کلی پیام های طول متغیربه دو بخش تقسیم میشود‪:‬‬ ‫‪ ‬سرآمد(‪ :)Header‬حاوی اطالعات مربوط به پیام‬ ‫‪ ‬بدنه(‪ :)Body‬حاوی خود پیام‬ ‫‪66‬‬ ‫‪[email protected]‬‬ ‫قالب پیام‬ ‫‪ ‬سرآیند(‪:)Header‬‬ ‫‪ ‬اطالعات مبدأ و مقصد مورد نظر پیام‬ ‫‪ ‬طول پیام‬ ‫‪ ‬اطالعات کنترلی‬ ‫ اشاره گر برای ایجاد لیستی از پیام ها‬ ‫ شماره ترتیب برای پیگیری تعداد‬ ‫و ترتیب انتقال پیامها‬ ‫‪ ‬بدنه)‪:(Body‬‬  ‫‪67‬‬ ‫‪[email protected]‬‬ ‫پیاده سازی انحصار متقابل توسط تبادل پیام‬ ‫‪ ;n const‬تعداد فرایندها =‬ ‫‪ ‬از تبادل پیام می توان برای اعمال‬ ‫)‪void p(int i‬‬ ‫انحصار متقابل استفاده کرد‪.‬فرض‬ ‫{‬ ‫)‪while(true‬‬ ‫میکنیم که‪ send‬مسدود نشونده و‬ ‫{‬ ‫‪ receive‬مسدود شونده است‪.‬یعنی‬ ‫;)‪receive(mutex , msg‬‬ ‫وقتی فرایندی می خواهد اطالعاتی را‬ ‫‪‬‬ ‫دریافت کند‪ ،‬با اجرای ‪ ،receive‬بلوکه‬ ‫;)‪send(mutex , msg‬‬ ‫می شود تا اطالعات برایش فرستاده‬ ‫‪‬‬ ‫شود‪.‬‬ ‫}‬ ‫‪ ‬مجموعه ای از فرایندهای همزمان در‬ ‫}‬ ‫صندوق پستی ‪ mutex‬شریکند و می‬ ‫) (‪void main‬‬ ‫توانند از این صندوق پستی برای ارسال‬ ‫{‬ ‫;)‪create_mailbox(mutex‬‬ ‫و دریافت پیام استفاده کنند‪.‬‬ ‫;)‪send(mutex , null‬‬ ‫;) )‪Par begin( P(1) , P(2), …,P(n‬‬ ‫}‬  ‫‪68‬‬ ‫‪[email protected]‬‬ ‫پیاده سازی انحصار متقابل توسط تبادل پیام‬ ‫‪ ‬صندوق پستی با پیامی با محتوای تهی مقدار گذاری اولیه شده است‪.‬‬ ‫‪ ‬فرایندی که می خواهد وارد بخش بحرانی خود شود‪ ،‬ابتدا سعی می کند پیامی دریافت‬ ‫نماید‪.‬اگر صندوق پستی خالی باشد‪ ،‬مسدود می گردد‪.‬‬ ‫‪ ‬هنگامی که فرایندی پیام را به دست میآورد‪ ،‬بخش بحرانی خود را انجام داده و سپس‬ ‫پیام را به صندوق پستی بر میگرداند‪.‬در نتیجه این پیام نقش نشانه ای را بازی می‬ ‫کند که از فرایندی به فرایند دیگر منتقل می شود‪.‬‬ ‫‪ ‬اگر بیش از یک فرایند عمل دریافت را همزمان انجام دهند‪ ،‬در این صورت‪:‬‬ ‫‪ (1‬اگر پیامی باشد‪ ،‬تنها به یک فرایند داده شده و بقیه مسدود می شوند‪.‬‬ ‫‪ (2‬اگر صندوق پستی خالی باشد‪ ،‬تمام فرایندها مسدود می گردند‪.‬موقعی که پیامی‬ ‫فراهم میشود‪ ،‬تنها یکی از فرایندهای مسدود فعال شده و پیام به همان فرایند‬ ‫داده شود‪.‬‬ ‫‪ ‬این فرض ها در تمام امکانات تبادل پیام‪ ،‬برقرار است‪.‬‬  ‫‪69‬‬ ‫‪[email protected]‬‬ ‫مساله تولید کننده و مصرف کننده‬ ‫( ‪)Producer/Consumer Problem‬‬ ‫‪ ‬یک یا چند تولید کننده داده تولید می کنند و در بافر قرار می دهند‪.‬‬ ‫‪ ‬یک مصرف کننده داده ها را از بافر برمی دارد و مصرف می کند‪.‬‬ ‫‪ ‬در هر لحظه از زمان فقط یک مصرف کننده یا تولید کننده می توانند به بافر‬ ‫دسترسی داشته باشند‪.‬‬ ‫‪ ‬این مساله در برنامه نویسی سیستم و برنامه نویسی کاربردی اتفاق می افتد‪:‬‬ ‫‪ ‬یک وب سرور درخواستهای وب ورودی را به فرآیندهای منتظر ارسال می‬ ‫کند تا سرویس داده شوند‪.‬‬ ‫‪ ‬اتفاقات مربوط به ‪(GUI‬صادره از صفحه کلید و ماوس) توسط سیستم عامل‬ ‫در یک صف قرار داده می شوند و برنامه ها آنها را مصرف می کنند‪.‬‬  70 [email protected] ‫مساله تولید کننده و مصرف کننده‬ producer: ‫تولید کننده‬ consumer: ‫مصرف کننده‬ while (true) while (true) { { while (in