Concurrency: Mutual Exclusion and Synchronization

صفحه 1:


صفحه 2:
© ارتباط پین فرآیندها * استفاده ی چند فرایند از ‎BS‏ ناحیه ى مشتركك # اشتراک منابع * استفاده ی چند فرایند از يك منبع مشتركك همزمان سازی فرآیندها " استفاده ی چند فرایند از یکت پیغام یا سمافور مشتر کك ۴ تخصیص زمان پردازنده 7 استفاده ی چند فرایند از یک یا چند پردازنده ی مشترک 

صفحه 3:
چند کاربرد مختله * چند برنامگی - اجرای همزمان چند برنامه ی مرتبط یک کاربرد ساختار یافته " کاربرد مى تواند شامل مجموعه ای از فرآیندهای همزمان باشد - اجرای همزمان چند فر آیند یا نخ یک برنامه #سیستم عامل ۴ سیستم عامل مجموعه ای از فرآیندها و نخها است 

صفحه 4:
الع سسسصسن سس سجن اشتراکک منابع عمومی #مدیریت تخصیص منابع © تشخيص محل خطاهای برنامه نویسی مشکل است. 

صفحه 5:
® 3 2 eed void echo() { chin = getchar(); chout = chin; putchar(chout) ; } 

صفحه 6:
® (Cine emer, ood Process Pl Process P2 chin = getchar(); a chin = getchar(); chout = chin; chout = chin; putchar(chout) ; putchar(chout) ; 

صفحه 7:
Operas isc] )8 ‏دور‎ 00 0 * دنبال كردن فرآیندهای فعال © تخصيص و بازيس كيرى منابع * زمان يردازنده * حافظه * فايلها * دستكاههاى ‎MO‏ ‎s‏ حفاظت داده و منابع * نتیجه اجرای ‎ES‏ ف رآیند نباید به سرعت اجرای ف رآیندهای همزمان ربط داشته باشد. 

صفحه 8:
* ف رآیندها از وجود همدیگر با اطلاع نیستند. * فرآیندها بطور غیر مستقیم از همدیگر اطلاع دارند. ف رآیندها بطور مستقیم از همدیگر اطلاع دارند. 

صفحه 9:
0 ميس يب معيو ةا جام سرخ # انحصار متقابل © ۳ نواحى بحرانى * در هر لحظه از زمان فقط يكك برنامه مى تواند در ناحيه بحرانى باشد. ۰ بن بست “رسا 

صفحه 10:
])0 Owoery Processes by Gkaricy 0 * نوشتن در ناحیه بحرانی باید بصورت انحصار متقابل انجام شود. #نواحی بحرانی برای اطمینان از جامعیت داده لازم هستند. 

صفحه 11:
‎cand 0‏ ا ل ۱0 ‏#تبادل پیغام ‏" نیازی به انحصار متقابل نیست. #امکان بن بست وجود دارد ‏* ممکن است هر دو فرآیند منتظر پیغام دیگری باشند. #امکان گرسنگی داریم ‏* دو فرآیند با هم پیغام مبادله می کنند در حالیکه سومی منتظر است. ‎ 

صفحه 12:
۱1 grace ‏هک اه‎ raat 0 # انحصار متقابل : در هر لحظه از زمان فقط یک فر آیند می تواند در ناحیه بحرانی باشد. پیشرفت: وقتی که فرآیند دیگری از ناحیه بحرانی استفاده نمی کنده فرآیند متقاضی نباید با تأخیر روبرو شود. فرضهای ساده: در مورد تعداد و سرعت نسبی فرآیندها نباید فرضی انجام شود. # تاخیر محدود: مدت استفاده از ناحیه بحرانی برای هر فر آیند محدود است. 

صفحه 13:


صفحه 14:
انتظار مشغولی فرآیند مرتب چکک می کند که ببیند می تواند وارد ناحیه بحرانی شود یا نه. ؟ در این حالت فرآیند تا وقتی که وارد ناحیه بحرانی نشود هیچ کار مفیدی انجام نمی دهد. * اگر فرآیندی در ناحیه بحرانی خود شکست بخورده فرآیند دیگر تا ابد مسدود خواهد بود. " فرآیندها به نوبت از ناحیه بحرانی استفاده می کنند. 

صفحه 15:
* هر فرآیند می تواند وضعیت دیگران را ببیند» اما نمی تواند آنرا تغییر دهد. * وقتی که فرآیند می خواهد وارد ناحیه بحرانی شود ابندا وضعیت دیگران را چک می کند. © اگر هیچ فرآیندی در ناحیه بحرانی نباشده فرآیند ما وضعیت خود را به ناحیه بحرانی تغییر می دهد. * متاسفانه این متد انحصار متقابل را تضمین نمی کند. * ممکن است دو فرآیند با هم ناحیه بحرانی را خالی ببیند و با هم وارد آن شوند. 

صفحه 16:
* قبل از جك كردن وضعيت ديكران» وضعيت خود را به حالت بحرانی تغییر دهیم. * اكر بعد از اين كار ديديم كه فرآيند دیگری در ناحیه بحرانی است؛ فرآيند تا خالى شدن ناحيه بحرانى مسدود مى شود. © در این حالت امکان بن بست وجود دارد- * اگر دو فرآیند همزمان بخواهند وارد ناحیه بحرانی شوند ؛ هر کدام به اشتباه فکر می کنند که دیگری در ناحیه بحرانی است وهر دو تا ابد مسدود خواهند ماند. 

صفحه 17:
فرآیند یک پرچم را به نشانه تمایل خود به استفاده از ناحیه بحرانی روشن می کند اما این آمادگی را دارد که در صورت. لزوم پرچم را خاموش ‎AS‏ سپس فرآیندهای دیگر را چک می کند. اگر کسی در ناحیه بحرانی باشد پرچم را خاموش می کند و در زمان دیگری آنرا روشن می کند. *اين عمل تا وقتی که وارد ناحیه بحرانی نشود تکرار می گردد. 

صفحه 18:
فرض کنید ناحیه بحرانی خالی است. ممکن است که دو فرآیند پرچم خود را روشن کنند؛ دیگری را چک کنند و دوباره پرچم را خاموش کنند. اين امر البته خیلی طول نخواهد کشید و بن بست اتفاق نمی افتد اما مطلوب نیست. 

صفحه 19:
# هر فرآیند یک نوبت برای ناحیه بحرانی می گیرد. * اگر فرآیند بخواهد وارد ناحیه بحرانی شود ابتدا پرچم خود را روشن می کند و منتظر نوبتش می ماند. 

صفحه 20:
(Dekker (hykoritha 

صفحه 21:
boolean flag [2]; ‘turn; ern. while (true) fs Olam wi ing m= 0 

صفحه 22:
ODN pact rac at De enc a ۵» )( © خاموش كردن وقفه * در حالت عادى وقتى فرآيندى اجرا مى شود به دو دليل ممكن است متوقف شود: *وقوع وقفه * درخواست يكك خدمت سيستم عامل ؟لذا اگر در حین اجرا وقفه را خاموش كنيم؛ انحصار متقابل تضمين می گردد. ؟اين امر استفاده های مفید وقفه را از بین می برد. ۴#در سیستمهای چند پردازنده ای» خاموش کردن وقفه در یکی از پردازنده ها انحصار متقابل را تضمین نمی کند. 

صفحه 23:
ODN pact rac at De enc a ۵» )( وجود یک دستورالعمل خاص ماشین (اسمبلی) ؟ پاید در یک سیکل اجرا شود. * لذا دستورات دیگر روی آن تاثیری ندارند. © دستور ات boolean testset (int i) { if (i == 0) { 12 1 return true; } else { return false; } 

صفحه 24:
while (true) while (!test&set(a) ) /*do nothing*/ /* critical section*/ a=0; /*remainder*/ { } 

صفحه 25:
ODN pact rac at De enc a ۵» )( #دستور عممع) ‎void exchange(int register,‏ ‎int memory) {‏ int temp; temp = memory; memory = register; register = temp; } 

صفحه 26:
/* a is shared variable initialized to 0 int ki=1; while (true) { do exchange (ki,a); while (ki!=0) /* critical section*/ exchange (a,ki); /*remainder*/ 

صفحه 27:
ON Bratz anh De ‏مه هر‎ 0 مزایا * به سیستمهای چند پردازنده ای قابل اعمال است. * ساده است. * مى توان جندين ناحيه بحرانى داشت. 

صفحه 28:
ON Bratz anh De ‏مه هر‎ 0 عیوب ؟ انتظار مشغولی وقت پردازنده را مصرف می کند. *امکان گرسنگی وجود دارد. ؟اگر یک فرآیند ناحیه بحرانی را ترک کند و چند فرآیند منتظر ورود باشند. بن نسسلتة *اكر يكك فرآيند كم اهميت داخل ناحيه بحرانى باشد و يكك فرآيند مهم به ناحیه بحرانی نیاز داشته باشد. فرآیند مهم تر يردازنده را با وقفه در اختيار عق كيرد * فرآيند كم اهميت تر تا ابد منتظر ناحيه بحرانی می ماند؛ زيرا هيجوقت به فرآيند معمولى اجازه در اختيار كرفتن بردازنده و اتمام كار داده نمى شود. 

صفحه 29:
# سمافور یکت متغییر مخصوص است که پرای میادله سیگتال از آن استفاده می گردد. اگر فرآیندی منتظر یک سیکنال باشد» تا وقتی که سیگنال نرسد مسدود می شود. #عملگرهای امد و 2۳0 وقفه پذبر نیستند. یک صف برای نگهداری از فرآیندهایی که منتظر یک سمافور هستند ؛ تشکیل می شود. 

صفحه 30:
® سمافور دارای یک متغییر است که مقدار طبیعی دارد. این متغیبر نشانگر تعداد فرآیندهایی است که می توانند بدون انتظار از سمافور استفاده کنند. # هر عمل ادا مقدار سمافور را یک واحد کم می کند. #هر عمل 2-۳1 مقدار سمافور را یک واحد افزایش می دهد. 

صفحه 31:


صفحه 32:
۱ ۹ 43 42 ۹ 8 ‏میرم موه اس { مسا مت‎ =) ‏تس (0,0) مسج‎ { ee Type queue; }; B (s.queve & ewpt()) ‏سرد‎ > (; ‏سای رم 0اه لیم‎ 5) vb 1 { P (s.uche == (1) rewove 0 process ® Brow sanke =O; BNE} chee ‏ام‎ provess ® va rend bet; { pkie he process isu; } block his process; } 

صفحه 33:
{ whie(() { uhite(() { :() (اس62 6 ۳ : ‎sewOuls); ae 1‏ مت -5 سوه امن ۳ ‎pews); 9 ۳‏ } /* ی ۳ } } 

صفحه 34:
Process Process ۱ Critical Region Value of Semaphore A B | Norma ecu lock + Blocked on. | semaphore 1 semWait(lock) ss 0 | semWait(lock) 1 ۱ semSignal(lock) ۱ | semSignal(lock) 1 | | Queue 

صفحه 35:
Grit Gets 1 یک یا چند تولید کننده داده تولید می کنند و در بافر قرار می دهند. © یک مصرف کننده داده ها را از بافر برمی دارد و مصرف می کند. ‎٩‏ در هر لحظه از زمان فقط یک مصرف کننده یا تولید کننده می توانند به بافر دسترسی داشته باشند. * این مساله در برنامه نویسی سیستم و برنامه نویسی کاربردی اتفاق می اف * یک وب سرور درخواستهای وب ورودی را به فرآیندهای منتظر ارسال می کند تا سرویس داده شوند. * اتفاقات مربوط به 66121 (صادره از صفحه کلید و ماوس) توسط سیستم عامل در یک صف قرار داده می شوند و برنامه ها آنها را مصرف می کنند. 

صفحه 36:
* می توان با یک بافر حلقوی و دو اشاره گر برای درج و حذف داده مسأله را حل کرد. عم معدم removePtr 

صفحه 37:
* جلوگیری از سرریز بافر * تولید کننده تعداد زیادی آیتم در بافر قرار می دهد و آنرا پر می کند. # جلوگیری از قحطی * تولید كننده يكك آيتم را توليد مى ‎AS‏ * مصرف کننده یک آيتم را مصرف مى کند. * مصرف کننده دوباره یک آیتم دیگر را مصرف می کند. © همزمانی مناسب ؟ انحصار متقابل ‎ite *‏ ob ‏؟ انتظار محدود (جل وگیری از بن بست)‎ 

صفحه 38:
5 60 Gewuphores 0 0 cad 0 یک سمافور برای شمارش آیتمهای موجود در بافر © یک سمافور برای شمارش جاهای خالی (<۳۸<) در بافر # یک سمافور براى قفل كردن ناحيه بحرانی 

صفحه 39:
۱ © ‏(ومجة)ادمم_مجد ,(ومجة)ادسر_وصجو‎ © sew_wui(wutex) » 5207 _post(wutex) © ‏ووو‎ +1) % O © rewoudptr=(rewovdlpir +1) % O ‏مقدار اولیه سمافور 90 برابر سایز بافر است.‎ # * مقدار اولیه سمافور 5۳7۶ برابر صفر است. * مقدار اولیه سمافور ال برابر یک است. 

صفحه 40:


صفحه 41:
sew _wrii(stie) SE _Wwuil(wuter) buPPer[ tosertPtr]= cata; ‏دوه‎ Pr =(ineertPir + 1) % O 

صفحه 42:
‎the previse problew?‏ ل ل رز( ‏) (۱)۰ ۳۷ (صنجه)لست_ مجح ‏(7۰ات)لوس_ مسر ‎Sie is‏ ‎EW, aa, sew _posl(cutex) ‎} ‎ 

صفحه 43:
۱۱( a EOL sar a as alm al aca cd Dear NS VOM cane ae pla as racial Pa Nn pet تست (وجشحم)شفسر_مجو 0 610006 (دمد؟)امصير_مجو ‎rece |;‏ رو vpew_poei( slot) nes 

صفحه 44:


صفحه 45:
ل نكا ا ل ۱ 

صفحه 46:
0 © خواننده: خواندن داده ‎e‏ 98 مت یسنده: نوشتن داده * چند خواننده می توانند داده را با هم بخوانند. * در هر زمان فقط یک نویسنده می تواند داده را بنویسد. * یک خواننده و نویسنده با هم نمی توانند در ناحیه بحرانی باشند. Reader | Oriter 00 Ov WOO Ov 

صفحه 47:
while (TRUE) { sem_wait(&mutex); readcount =readcount+1; if readcount sem_wait(& sem_post(&mutex); do reading sem_wait(&mutex) readcount=readcount-1; if readcount == 0 then sem_post(&wt); sem_post(&mutex); Qe read chit } while (TRUE) { Think_up_data(); /*noncritical section*/ sem_wait(& ); do writing Sem_post(& —); } 

صفحه 48:
#مانیتور یک ماژول نرم افزاری است. مشخصات اصلی: " متغییرهای داده ای محلی فقط توسط خود مانیتور قابل دسترسی * فرآیند با صدا زدن یکی از پروسه های مانیتور وارد آن می شود. ؟ در هر لحظه از زمان فقط یک فرآیند در داخل مانیتور در حال اجرا است. 

صفحه 49:
13 

صفحه 50:
۳ 4 char x; while (crue) { produce (x); sepa): 0 oid consuner char x7 while (crue) ( ‏ممع‎ ‎consune|s); 1 1 void main() 4 2 parbegin (producer, consumer) } ‘Js program producerconsuner */ ‘monitor boundedbufter; char buffer (8); Ane nextin, naxtouty int count; cond nctfull, aotenpty? void append (char x) 1 Af (count == N) cwait(notfull); buffer[nextin} = x; pextin = (nextin + 1) ty countess 7+ one more item in buffer */ ‘signal (notempty) > void take (char x) 1 4£ (count -~ 0) ewedt(notempty) x = buffer[nextout]; dextout = (nexcout +1) ty ‘count: esignal(notfuil); nextin = 0) nextout = 0; count = 0; 

صفحه 51:
4 #دراين روش انحصار متقابل بصورت ضمنى وجود دارد. #اطلاعاته بين فر يندها از طريق ييغام رد و بدل مى شود. send (destination, message) receive (source, message) 

صفحه 52:
# فرستنده و گیرنده می توانند در حین ارسال و دریافت پیغام مسدود شوند یا مسدود نشوند. # حالت اول: مسدود شدن فرستنده و گیرنده در هنگام مبادله پیغام. ؟ این روش وعده گاه نیز نامیده شده است. #حالت دوم: فرستنده غیر مسدود و گیرنده مسدود: * در این حالت گیرنده تا وقتی که پیغام را بطور کامل دریافت نکند مسدود می شود. اما فرستنده می تواند به کار خود ادامه دهد. #حالت سوم: فرستنده و گیرنده غیر مسدود. 

صفحه 53:
؟آدرس دهی مستقیم * فرستنده آدرس گیرنده را در پیغام قرار می دهد. * كيرنده مى تواند از پارامتر فرستنده ی پیام برای اطلاع دادن به فرستنده استفاده کند. در گيرنده دو حالت امکان پذیر است: * گیرنده دقیقاً از قبل می داند که کی برای آن پیفام می فرستد. (برای ارتباط دو فرآیند مفید است). * گيرنده از هر فرستنده ای داده قبول می کند . 

صفحه 54:
1 أدرس دهى غير مستقيم: * پیغامها به یک ساختار داده مشترکك که جعبه پستی نا 3 جعبه پستی نام دارد فرستاده می شوند. 10100 فرآیند پیغام را به جعبه پستی می فرستا 2 پستی می فرستد و دیگری پیفام را بر می دارد. # چهار حالت دارد: 

صفحه 55:


صفحه 56:
امسر ی( Message Contents 

صفحه 57:
Outed exchusion using wessuye pussicy /* program mutualexclusion */ const int n = /* number of processes */; void P(int i) 1 message msg; while (true) { receive (box, msg); /* critical section send (box, msg); /* remainder = ۶ 10 + void main() create mailbox (box); send (box, null); : parbegin (P(1), P(2), - - +, P(n))? 

صفحه 58:
‘const int ‘capacity = /* buffering capacity */ + null =/* empty message */ ; int i; void producer () {message masa; while (erce) 4 receive (mayproduce, pmsg) ; pnsg = produce(); Send (mayconsune, pmsg); 0 1 void consuner() {message cnsq; while (true) { receive (mayconsume, cms); consume (cmsg); send (mayproduce, mull); 1 > void main() 4 ‘create mailbox (mayproduce); create mailbox (mayconsune) ; for (int i = 1; i <= capacity; it+) send (mayproduce, null); parbegin (producer, consumer); 

Concurrency: Mutual Exclusion and Synchronization فصل پنجم Currency ارتباط بین فرآیندها استفاده ی چند فرایند از یک ناحیه ی مشترک اشتراک منابع استفاده ی چند فرایند از یک منبع مشترک همزمان سازی فرآیندها استفاده ی چند فرایند از یک پیغام یا سمافور مشترک تخصیص زمان پردازنده استفاده ی چند فرایند از یک یا چند پردازنده ی مشترک Concurrency چند کاربرد مختلف چند برنامگی – اجرای همزمان چند برنامه ی مرتبط یک کاربرد ساختار یافته کاربرد می تواند شامل مجموعه ای از فرآیندهای همزمان باشد – اجرای همزمان چند فرآیند یا نخ یک برنامه سیستم عامل سیستم عامل مجموعه ای از فرآیندها و نخها است Difficulties with Concurrency اشتراک منابع عمومی مدیریت تخصیص منابع تشخیص محل خطاهای برنامه نویسی مشکل است. A Simple Example void echo() { chin = getchar(); chout = chin; putchar(chout); } A Simple Example Process P1 Process P2 . . chin = . chin = getchar(); . getchar(); chout = chin; chout = chin; putchar(chout); . . putchar(chout); . . Operating System Concerns دنبال کردن فرآیندهای فعال تخصیص و بازپس گیری منابع زمان پردازنده حافظه فایلها دستگاههای I/O حفاظت داده و منابع نتیجه اجرای یک فرآیند نباید به سرعت اجرای فرآیندهای همزمان ربط داشته باشد. Process Interaction فرآیندها از وجود همدیگر با اطالع نیستند. فرآیندها بطور غیر مستقیم از همدیگر اطالع دارند. فرآیندها بطور مستقیم از همدیگر اطالع دارند. Competition Among Processes for Resources انحصار متقابل نواحی بحرانی در هر لحظه از زمان فقط یک برنامه می تواند در ناحیه بحرانی باشد. بن بست گرسنگی Cooperation Among Processes by Sharing نوشتن در ناحیه بحرانی باید بصورت انحصار متقابل انجام شود. نواحی بحرانی برای اطمینان از جامعیت داده الزم هستند. Cooperation Among Processes by Communication تبادل پیغام نیازی به انحصار متقابل نیست. امکان بن بست وجود دارد ممکن است هر دو فرآیند منتظر پیغام دیگری باشند. امکان گرسنگی داریم دو فرآیند با هم پیغام مبادله می کنند در حالیکه سومی منتظر است. Requirements for Critical Region انحصار متقابل :در هر لحظه از زمان فقط یک فرآیند می تواند در ناحیه بحرانی باشد. پیشرفت :وقتی که فرآیند دیگری از ناحیه بحرانی استفاده نمی کند ،فرآیند متقاضی نباید با تأخیر روبرو شود. فرضهای ساده :در مورد تعداد و سرعت نسبی فرآیندها نباید فرضی انجام شود. تاخیر محدود :مدت استفاده از ناحیه بحرانی برای هر فرآیند محدود است. Progress ‏Mutual Exclusion خوب ،اصال دیدی !کسی بره تو؟ آیا درها قفل دارند؟ ،اگر بدویم !اولین نفر ما هستیم ‏Oversimplifying Assumptions ‏Bounded Wait کسی بی نوبت !داخل نرود First Attempt انتظار مشغولی فرآیند مرتب چک می کند که ببیند می تواند وارد ناحیه بحرانی شود یا نه. در این حالت فرآیند تا وقتی که وارد ناحیه بحرانی نشود ،هیچ کار مفیدی انجام نمی دهد. اگر فرآیندی در ناحیه بحرانی خود شکست بخورد ،فرآیند دیگر تا ابد مسدود خواهد بود. فرآیندها به نوبت از ناحیه بحرانی استفاده می کنند. Second Attempt هر فرآیند می تواند وضعیت دیگران را ببیند ،اما نمی تواند آنرا تغییر دهد. وقتی که فرآیند می خواهد وارد ناحیه بحرانی شود ،ابتدا وضعیت دیگران را چک می کند. اگر هیچ فرآیندی در ناحیه بحرانی نباشد ،فرآیند ما وضعیت خود را به ناحیه بحرانی تغییر می دهد. متاسفانه این متد انحصار متقابل را تضمین نمی کند. ممکن است دو فرآیند با هم ناحیه بحرانی را خالی ببیند و با هم وارد آن شوند. Third Attempt قبل از چک کردن وضعیت دیگران ،وضعیت خود را به حالت بحرانی تغییر دهیم. اگر بعد از این کار دیدیم که فرآیند دیگری در ناحیه بحرانی است، فرآیند تا خالی شدن ناحیه بحرانی مسدود می شود. در این حالت امکان بن بست وجود دارد- اگر دو فرآیند همزمان بخواهند وارد ناحیه بحرانی شوند ،هر کدام به اشتباه فکر می کنند که دیگری در ناحیه بحرانی است وهر دو تا ابد مسدود خواهند ماند. Fourth Attempt فرآیند یک پرچم را به نشانه تمایل خود به استفاده از ناحیه بحرانی روشن می کند ،اما این آمادگی را دارد که در صورت\ لزوم پرچم را خاموش کند. سپس ،فرآیندهای دیگر را چک می کند .اگر کسی در ناحیه بحرانی باشد پرچم را خاموش می کند و در زمان دیگری آنرا روشن می کند. این عمل تا وقتی که وارد ناحیه بحرانی نشود تکرار می گردد. Fourth Attempt فرض کنید ناحیه بحرانی خالی است .ممکن است که دو فرآیند پرچم خود را روشن کنند ،دیگری را چک کنند و دوباره پرچم را خاموش کنند .این امر البته خیلی طول نخواهد کشید و بن بست اتفاق نمی افتد اما مطلوب نیست. Correct Solution هر فرآیند یک نوبت برای ناحیه بحرانی می گیرد. اگر فرآیند بخواهد وارد ناحیه بحرانی شود ابتدا پرچم خود را روشن می کند و منتظر نوبتش می ماند. Dekker Alghorithm Peterson Algorithm Mutual Exclusion: Hardware Support خاموش کردن وقفه در حالت عادی وقتی فرآیندی اجرا می شود به دو دلیل ممکن است متوقف شود: وقوع وقفه درخواست یک خدمت سیستم عامل لذا اگر در حین اجرا وقفه را خاموش کنیم ،انحصار متقابل تضمین می گردد. این امر استفاده های مفید وقفه را از بین می برد. در سیستمهای چند پردازنده ای ،خاموش کردن وقفه در یکی از پردازنده ها انحصار متقابل را تضمین نمی کند. Mutual Exclusion: Hardware Support ) وجود یک دستورالعمل خاص ماشین (اسمبلی . باید در یک سیکل اجرا شود . لذا دستورات دیگر روی آن تاثیری ندارند test&set دستور boolean testset (int i) { if (i == 0) { i = 1; return true; } else { return false; } } Test&set Usage while (true) { while (!test&set(a)) /*do nothing*/ /* critical section*/ a=0; /*remainder*/ } Mutual Exclusion: Hardware Support Exchange دستور void exchange(int register, int memory) { int temp; temp = memory; memory = register; register = temp; } Process i /* a is shared variable initialized to 0 int ki=1; while (true) { do exchange (ki,a); while (ki!=0) /* critical section*/ exchange (a,ki); /*remainder*/ } Mutual Exclusion Machine Instructions مزایا به سیستمهای چند پردازنده ای قابل اعمال است. ساده است. می توان چندین ناحیه بحرانی داشت. Mutual Exclusion Machine Instructions عیوب انتظار مشغولی وقت پردازنده را مصرف می کند. امکان گرسنگی وجود دارد. اگر یک فرآیند ناحیه بحرانی را ترک کند و چند فرآیند منتظر ورود باشند. بن بست: اگر یک فرآیند کم اهمیت داخل ناحیه بحرانی باشد و یک فرآیند مهم به ناحیه بحرانی نیاز داشته باشد .فرآیند مهم تر پردازنده را با وقفه در اختیار می گیرد. فرآیند کم اهمیت تر تا ابد منتظر ناحیه بحرانی می ماند ،زیرا هیچوقت به فرآیند معمولی اجازه در اختیار گرفتن پردازنده و اتمام کار داده نمی شود. Semaphores سمافور یک متغییر مخصوص است که برای مبادله سیگنال از آن استفاده می گردد. اگر فرآیندی منتظر یک سیگنال باشد ،تا وقتی که سیگنال نرسد مسدود می شود. عملگرهای waitو signalوقفه پذیر نیستند. یک صف برای نگهداری از فرآیندهایی که منتظر یک سمافور هستند ،تشکیل می شود. Semaphores سمافور دارای یک متغییر است که مقدار طبیعی دارد. این متغییر نشانگر تعداد فرآیندهایی است که می توانند بدون انتظار از سمافور استفاده کنند. هر عمل waitمقدار سمافور را یک واحد کم می کند. هر عمل signalمقدار سمافور را یک واحد افزایش می دهد. Definition of Semaphore Primitives (Counting Semaphore) struct semaphore{ int count; queueType queue; }; void semSignal(semaphore s) { s.count++; if (s.count ≤ 0) { remove a process P from s.queue; place process P on ready list; } void semWait(semaphore s) { } s.count--; if (s.count < 0) { place this process in s.queue; block this process; } } Definition of Binary Semaphore Primitives struct binary_semaphore { enum {0,1} value; queueType queue; }; void semSignalB(binary_semaphore s) { void semWaitB(binary_semaphore s) { if (s.value == 1) s.value = 0; else { place this process in s.queue; } block this process; } } if (s.queue is empty()) s.value = 1; else { remove a process P from s.queue; place process P on ready list; } Mutual Exclusion Using Semaphores semaphore s = 1; Pi { while(1) { semWait(s); /* Critical Section */ semSignal(s); /* remainder */ } } lock = 0; Pi { while(1) { while(!Test_And_Set(lock)) { }; /* Critical Section */ lock =0; /* remainder */ } } Queue Value of Semaphore lock 1 Process A Process B Critical Region Normal Execution Blocked on semaphore lock semWait(lock) 0 semWait(lock) B -1 semSignal(lock) 0 semSignal(lock) 1 Producer/Consumer Problem یک یا چند تولید کننده داده تولید می کنند و در بافر قرار می دهند. یک مصرف کننده داده ها را از بافر برمی دارد و مصرف می کند. در هر لحظه از زمان فقط یک مصرف کننده یا تولید کننده می توانند به بافر دسترسی داشته باشند. این مساله در برنامه نویسی سیستم و برنامه نویسی کاربردی اتفاق می افتد: یک وب سرور درخواستهای وب ورودی را به فرآیندهای منتظر ارسال می کند تا سرویس داده شوند. اتفاقات مربوط به ( GUIصادره از صفحه کلید و ماوس) توسط سیستم عامل در یک صف قرار داده می شوند و برنامه ها آنها را مصرف می کنند. Producer-Consumer Problem می توان با یک بافر حلقوی و دو اشاره گر برای درج و حذف داده مسأله را حل کرد. ‏insertPtr ‏removePtr Challenge جلوگیری از سرریز بافر تولید کننده تعداد زیادی آیتم در بافر ق\رار می دهد و آنرا پر می کتد. جلوگیری از قحطی تولید کننده یک آیتم را تولید می کند. مصرف کننده یک آیتم را مصرف می کند. مصرف کننده دوباره یک آیتم دیگر را مصرف می کند. همزمانی مناسب انحصار متقابل پیشرفت انتظار محدود (جلوگیری از بن بست) 2 Counting Semaphores and a mutex یک سمافور برای شمارش آیتمهای موجود در بافر یک سمافور برای شمارش جاهای خالی ( )slotsدر بافر یک سمافور برای قفل کردن ناحیه بحرانی Assembling the solution  sem_wait(slots), sem_post(slots)  sem_wait(items), sem_post(items)  sem_wait(mutex) وsem_post(mutex)  insertptr=(insertptr+1) %N  removalptr=(removalptr+1) % N . برابر سایز بافر استslots مقدار اولیه سمافور . برابر صفر استitems مقدار اولیه سمافور . برابر یک استmutex مقدار اولیه سمافور Pseudocode getItem() sem_wait(items) sem_wait(mutex) result=buffer[ removePtr ]; removePtr=(removePtr +1 ) % N sem_post(mutex) sem_post(slots) Pseudocode putItem(data) sem_wait(slots) sem_wait(mutex) buffer[ insertPtr]= data; insertPtr=(insertPtr + 1 ) % N sem_post(mutex) sem_post(items) Analysis#1 What's the precise problem? putItem(data) { getItem() { sem_wait(mutex) sem_wait(mutex) sem_wait(slots) buffer[ insertPtr]= … insertPtr=… sem_post(items) sem_wait(items) result=buffer[ removePtr ]; removePtr=… sem_post(slots) sem_post(mutex) sem_post(mutex) } } Deadlock e.g Consumer waits for producer to insert a new item but Producer is waiting for Consumer to release mutex putItem(data) { getItem() { sem_wait(mutex) #2 sem_wait(mutex) sem_wait(slots) buffer[ insertPtr]= … insertPtr=… sem_post(items) sem_post(mutex) } sem_wait(items) BLOCKS #1 result=buffer[ removePtr ]; removePtr=… sem_post(slots) sem_post(mutex) } Analysis#2 putItem(data) { getItem() { sem_wait(slots) sem_wait(items) sem_post(slots) sem_wait(mutex) buffer[ insertPtr]= … insertPtr=… sem_post(items) sem_post(mutex) } sem_wait(mutex) result=buffer[ removePtr ]; removePtr=… sem_post(mutex) } Buffer overflow when reader removes item from a full buffer: Producer inserts item too early putItem(data) { getItem() { sem_wait(slots) sem_wait(items) sem_post(slots) sem_wait(mutex) buffer[ insertPtr]= … insertPtr=… sem_post(items) sem_post(mutex) } sem_wait(mutex) result=buffer[ removePtr ]; removePtr=… sem_post(mutex) } First Reader-Writer Problem ‏ ‏ ‏ خواننده :خواندن داده نویسنده :نوشتن داده قوانین: چند خواننده می توانند داده را با هم بخوانند. در هر زمان فقط یک نویسنده می تواند داده را بنویسد. یک خواننده و نویسنده با هم نمی توانند در ناحیه بحرانی باشند. ‏Writer ‏Reader ‏No ‏OK ‏Reader ‏No ‏NO ‏Writer Reader-writer solution using semaphores Writer Reader while (TRUE) { while (TRUE) { Think_up_data(); /*noncritical section*/ sem_wait(&wrt); sem_wait(&mutex); readcount =readcount+1; if readcount == 1 then sem_wait(&wrt); sem_post(&mutex); do reading do writing Sem_post(&wrt); } sem_wait(&mutex) readcount=readcount-1; if readcount == 0 then sem_post(&wrt); sem_post(&mutex); Use read data } Monitors مانیتور یک ماژول نرم افزاری است. مشخصات اصلی: متغییرهای داده ای محلی فقط توسط خود مانیتور قابل دسترسی هستند. فرآیند با صدا زدن یکی از پروسه های مانیتور وارد آن می شود. در هر لحظه از زمان فقط یک فرآیند در داخل مانیتور در حال اجرا است. A solution to producer-consumer problem using monitor Message Passing در این روش انحصار متقابل بصورت ضمنی وجود دارد. اطالعات\ بین فرآیندها از طریق پیغام رد و بدل می شود. )send (destination, message )receive (source, message Synchronization فرستنده و گیرنده می توانند در حین ارسال و دریافت پیغام مسدود شوند یا مسدود نشوند. حالت اول :مسدود شدن فرستنده و گیرنده در هنگام مبادله پیغام. این روش وعده گاه نیز نامیده شده است. حالت دوم :فرستنده غیر مسدود و گیرنده مسدود: در این حالت گیرنده تا وقتی که پیغام را بطور کامل دریافت نکند مسدود می شود .اما فرستنده می تواند به کار خود ادامه دهد. حالت سوم :فرستنده و گیرنده غیر مسدود. Addressing آدرس دهی مستقیم: فرستنده آدرس گیرنده را در پیغام قرار می دهد. گیرنده می تواند از پارامتر فرستنده ی پیام برای اطالع دادن به فرستنده استفاده کند. در گیرنده دو حالت امکان پذیر است: گیرنده دقیقاً از قبل می داند که کی برای آن پیغام می فرستد( .برای ارتباط دو فرآیند مفید است). گیرنده از هر فرستنده ای داده قبول می کند . Addressing آدرس دهی غیر مستقیم: پیغامها به یک ساختار داده مشترک که جعبه پستی نام دارد فرستاده می شوند. فرآیند پیغام را به جعبه پستی می فرستد و دیگری پیغام را بر می دارد. چهار حالت دارد: یک نفر به یک نفر یک نفر به چند نفر چند نفر به یک نفر چند نفر به چند نفر Indirect communication paradigms Message Format Mutual exclusion using message passing A solution to producer-consumer problem using message passing