خلاصه فصل ۷ سیستم عامل: هماهنگی فرآیندها

خلاصه فصل ۷ سیستم عامل: هماهنگی فرآیندها

اسلاید 1: خلاصه ی فصل 7 سیستم عاملاستاد : آقای عسکری قاسمپوری میلاد جعفریرضا زاهدیآذین مهرپورشاداعضای گروه :

اسلاید 2: فصل هفتمهماهنگی فرآیندها

اسلاید 3: فصل هفتم : هماهنگی فرآیندها در فصل 4 مدلی از سیستم را اجرا کردیم که شامل تعدادی از فرآیندهای ترتیبی همکار بوده است که همگی به طور ناهماهنگ اجرا می شدند و احتمالا داده های مشترکی داشتند. این مدل را با استفاده از الگوی میانگیر (بافر) محدود ، به عنوان نمایشی از سیستم های عامل ، توضیح داریم.راه حل حافظه مشترک برای مسئله بافر محدود در نظر می گیریم : گفتیم که حداکثر یک Buffer- size قلم داده می تواند به طور همزمان در بافر وجود داشته باشد . برای برطرف کردن این عیب از یک شمارنده برای بافر استفاده می کنیم که دارای مقدار است با ورود هر قلم شمارنده اضافه و با حذف یک قلم شمارنده کم می شود.

اسلاید 4: فصل هفتم : هماهنگی فرآیندها کد مربوط به تولید کننده – مصرف کننده به صورت زیر تغییر می کند :while(1) { /* produce an item in nextproduced */ while (counter == buffersize) /* do nothing */ buffer[in] = nextproduced; in = (in+1)%buffer-size; Counter++; }while(1) { while (counter == 0) /* do nothing */nextproduced = buffer[out]; out = (out+1)%buffer-size;Counter--;/*consume the item in next consumed */}تولید کنندهمصرف کننده

اسلاید 5: فصل هفتم : هماهنگی فرآیندها این دو روال به طور جداگانه درست عمل می کنند اما به طور همزمان ممکن است به درستی عمل نکنند مثلا اگر Counter = 5 و فرآیندهای تولیدکننده و مصرف کننده دستورات “Counter++” و “Counter--” را همزمان اجرا کنند مقدار Counter ممکن است 4، 5، 6 باشد ولی مقدار درست 5 و وقتی تولید می شود که هر کدام به طور جداگانه عمل کنند.علت رسیدن به حالت نادرست دسترسی همزمان فرآیندها به داده ی مشترک Counter است.

اسلاید 6: فصل هفتم : هماهنگی فرآیندها حالت مسابقه ( Race Condition ) چنین وضعیتی که چندین فرآیند به طور همزمان به داده ای دسترسی دارند و نتیجه اجرا به ترتیب دستیابی فرآیندها بستگی دارد ، Rase Condition می گوییم.راه حل مقابله با Race Condition برای مقابله با حالت مسابقه باید تضمین شود که در هر زمان تنها یک فرآیند به متغیر Counter دسترسی داشته باشد که برای چنین کاری نیاز به هماهنگی فرآیندهاست.

اسلاید 7: فصل هفتم : هماهنگی فرآیندها 2-7 مسئله ناحیه بحرانی سیستمی با n فرآیند { P0 , P1 , … , Pn-1 } را در نظر بگیرید. هر فرآیند بخشی کد به نام ناحیه بحرانی (Critical Section) دارد که فرآیند ممکن است در آن متغیرهای مشترک را تغییر دهد ، جدولی را بروز کند ، فایلی را بنویسد ، و ...ویژگی مهم این است هنگامیکه یک فرآیند در حال اجرای ناحیه ی بحرانی خودش است ، هیچ فرآیند دیگری نباید اجازه داشته باشد ناحیه بحرانی خودش را اجرا کند. بنابراین اجرای ناحیه ی بحرانی توسط فرآیندها ، از نظر زمانی انحصار متقابل (mutually exclusive) است.

اسلاید 8: فصل هفتم : هماهنگی فرآیندها مسئله ناحیه بحرانی طراحی پروتکلی است که فرآیندها می توانند به صورت همکار عمل کنند ، هر فرآیند برای ورود به ناحیه ی بحرانی خودش ، باید اجازه بگیرد. بخشی از کد که درخواست اجازه صادر می کند ، ناحیه ی ورودی (entry) نام دارد و بقیه کد را ناحیه باقیمانده می نامند.

اسلاید 9: فصل هفتم : هماهنگی فرآیندها راه حل مسئله ناحیه ی بحرانی باید 3 نیازمندی را برآورده کند :Mutual exclusive : اگر فرآیند P1 در حالت اجرای ناحیه ی بحرانی اش باشد ، هیچ فرآیند دیگری نباید اجازه ی اجرای ناحیه بحرانی اش را داشته باشد.پیشروی : اگر هیچ فرآیندی در ناحیه ی بحرانی اش نباشد ولی فرآیندهایی باشند که بخواهند وارد ناحیه ی بحرانی خودشان شوند ، آنگاه فقط فرآیندهایی که در حال اجرای ناحیه ی باقیمانده خودشان نیستند می توانند برای ورود به ناحیه ی بحرانی خودشان انتخاب شوند و این اتفاق نمی تواند بطور نامحدود به تعویق بیفتد.انتظار محدود : پس از اینکه فرآیندی درخواست ورود به ناحیه ی بحرانی خود را کرد، قبل از پذیرفتن آن درخواست،تعداد دفعاتی که سایر فرآیندها می توانند وارد ناحیه ی بحرانی خود شوند ، محدود است ، یعنی آن فرآیند نمی تواند به مدت نا محدود منتظر بماند.

اسلاید 10: فصل هفتم : هماهنگی فرآیندها 1-2-7 راه حل های دو فرآیندی در این قسمت به الگوریتم هایی می پردازیم که در هر زمان فقط بروی دو فرآیند عمل می کنند. فرآیندها با P0 و P1 مشخص می شوند برای سهولت وقتی از Pi استفاده می کنیم برای نشان دادن فرآیند بعدی از Pj استفاده می کنیم که j==1-iساختار کلی فرآیند نمونه Pido{ ناحیه ورودیناحیه بحرانی ناحیه خروجناحیه باقیمانده}while(1);

اسلاید 11: فصل هفتم : هماهنگی فرآیندها 1-1-2-7 الگوریتم 1 اولین راه حل این است که از متغیر مشترکی به نام turn استفاده کنیم که مقدار اولیه آن 0 است. فرآیند Pi اجازه دارد وارد ناحیه ی بحرانی خود شود turn = i اگر این راه حل تضمین می کند که در هر زمان فقط یک فرآیند وارد ناحیه ی بحرانی اش شود اما نیازمندی پیشروی را برآورده نمی کند زیرا دقیقا مشخص می کند که چه فرآیندی باید وارد ناحیه ی بحرانی خودش شود.ساختار فرآیند Pi در الگوریتم 1do{ while (turn!=0);ناحیه بحرانی turn=j;ناحیه باقیمانده}while(1);

اسلاید 12: فصل هفتم : هماهنگی فرآیندها 2-1-2-7 الگوریتم 2مشکل الگوریتم 1 این است که اطلاعات کافی در مورد حالت هر فرآیند نگهداری نمی کند بلکه فقط مشخص می کند کدام فرآیند اجازه ی ورود به ناحیه ی ورود به ناحیه ی بحرانی خودش را دارد که برای حل این مشکل به جای متغیر turn از آرایه زیر استفاده می شود : مقدار اولیه عناصر آرایه false است boolean flag[2] اگر flag[i] =true باشد نشان می دهد که Pi آماده ورود به ناحیه ی بحرانی اش است.

اسلاید 13: فصل هفتم : هماهنگی فرآیندها هر فرآیند برای ورود به ناحیه ی بحرانی منتظر می ماند تا flag مربوط به فرآیند ناحیه ی بحرانی false شود و هر فرآیند هنگام خروج از ناحیه ی بحرانی flag مربوط به خود را false می کندساختار فرآیند Pi در الگوریتم 2do{ falg[i]=true; While (flag[j]);ناحیه بحرانی falg[i]=false;ناحیه باقیمانده}while(1);

اسلاید 14: فصل هفتم : هماهنگی فرآیندها در این روش:شرط انحصار متقابل برقرار استشرط پیشروی برقرار نیست مثال: برای تشریح مسئله فوق این دنباله را در نظر می گیریم :T0 : P0 Sets flag[0] = TrueT1 : P1 Sets flag[1] = Trueاکنون P0 و P1 در حلقه while گیر می کنند.این الگوریتم به زمانبندی دقیق دو فرآیند بستگی دارد. این دنباله می تواند در محیطی باشد که چندین فرآیند به طور همزمان در حال اجرا هستند و یا بلافاصله بعد از T0 وقفه رخ دهد و CPU از یک فرآیند به فرآیند دیگر برود.

اسلاید 15: فصل هفتم : هماهنگی فرآیندها 3-1-2-7 الگوریتم 3در این روش فرآیندها دارای دو متغیر مشترکندساختار فرآیند Pi در الگوریتم 3do{ falg[i]=true; turn=j; While (flag[j] && turn=j );ناحیه بحرانی falg[i]=false; ناحیه باقیمانده}while(1);در آغاز flag[0] = flag[1] = false استBoolean flag[2];Int turn;

اسلاید 16: فصل هفتم : هماهنگی فرآیندها فرآیند Pi برای ورود به ناحیه ی بحرانی ابتدا flag[1] را True می کند. اگر هر دو فرآیند سعی کنند همزمان وارد ناحیه ی بحرانی شوند ، turn در آن واحد می خواهد i و j شود. اما فقط یک دستور انتساب بعدی انجام می شود و مقدار قبلی از بین می رود. مقدار نهایی turn مشخص می کند کدامیک از دو فرایند ، زودتر اجازه ورود به ناحیه ی بحرانی را پیدا می کنند.

اسلاید 17: فصل هفتم : هماهنگی فرآیندها این روش ویژگی های زیر را دارا می باشد :Mutually exclusive: هر فرآیند Pi وقتی می تواند وارد ناحیه ی بحرانی اش شود که یا flag[i] = false یا turn = i . اگر دو فرآیند بخواهند همزمان وارد ناحیه ی بحرانی شوند آنگاه flag[0] = flag[1] = True که بدین ترتیب P0 و P1 نمی توانند همزمان حلقه while خود را اجرا کنند چرا که مقدار turn می تواند در یک زمان 0 یا 1 باشد.شرط پیشرویشرط انتظار محدود

اسلاید 18: فصل هفتم : هماهنگی فرآیندها برای اثبات ویژگی 2 و 3 در صورتی می توان مانع از ورود فرآیند Pi به ناحیه ی بحرانی اش شد که یا flag[j] = True و turn = True در حلقه while گیر کند. اگر Pj آماده ورود به ناحیه ی بحرانی نباشد آنگاه flag[j] = false و Pi می تواند وارد ناحیه ی بحرانی می شود.اگر turn = j باشد و Pj وارد ناحیه بحرانی می گردد. وقتی Pj وارد ناحیه بحرانی flag[j] = false می گردد و Pi اجازه پیدا می کند تا وارد ناحیه ی بحرانی خود شود.اگر Pj مقدار flag[j] را برابر True قرار دهد باید turn = i نیز باشد اما چون Pi در حین اجرای دستور while ، مقدار turn را تغییر نمی دهد ، Pi حداکثر پس از یک بار ورود Pj در ناحیه ی بحرانی (انتظار محدود) ، به ناحیه بحرانی خودش وارد می شود (پیشروی)

اسلاید 19: فصل هفتم : هماهنگی فرآیندها 2-2-7 راه حل های چند فرآیندیالگوریتم نانوایی (bakery algorithm) برای حل ناحیه ی بحرانی به اندازه ی n فرایند است که این الگوریتم را برای محیط توزیعی طراحی شد.این الگوریتم به هر مشتری هنگام ورود شماره ای می دهد و مشتری بعدی که باید خدمات بگیرد مشتری است که شماره ی کوچکتری دارد در ضمن الگوریتم تضمین نمی کند که شماره ی مشتریان یکسان نباشد اگر شماره ی مشتریان یکسان بود مشتریی که نام کوچکتری دارد زودتر خدمات می گیرد.i<j اگرشماره یکسانPj و Pi اگر انتخاب می شود Pi

اسلاید 20: فصل هفتم : هماهنگی فرآیندها ساختمان داده های مشترک عبارتند از :boolean choosing[n];int number[n]; این الگوریتم شرط های سه گانه را داراست.ساختار فرآیند Pi بر الگوریتم Backery در شکل زیر نشان داده شده است :مقدار اولیه ی این ساختمان داده ها به ترتیب false و 0 است.do{ Choosing[i]=true; Number[i]=max(number[0], number[1], …,number[n-1]+1); Choosing[i]=false; For(j=0;j<n;j++){ while(choosing[j]); while((number[j]!=0)&&(number[j,j]<number[i,i])); }ناحیه بحرانی number[i]=0; ناحیه باقیمانده}while(1);

اسلاید 21: فصل هفتم : هماهنگی فرآیندها 3-7 ویژگی های سخت افزاری برای هماهنگی فرآیندبرای مسئله ی ناحیه بحرانی در محیط تک پردازنده ای کافی است اجازه ندهیم در حین تغییر متغییرهای عمومی ، وقفه ای رخ دهد. اولین روش در محیط چند پردازنده ای امکان پذیر نیست چرا که غیر فعال کردن وقفه ها در یک محیط چند پردازنده ای می تواند موجب اتلاف وقت شود زیرا پیام به تمام پردازنده ها ارسال می شود بنابر این اغلب ماشین ها دستورات سخت افزاری خاصی را تدارک می بینند که می توان کلمه ای را تست کند یا محتویاتش را تغییر دهد یا اتمی محتویات دو کلمه را عوض کند.

اسلاید 22: فصل هفتم : هماهنگی فرآیندها دستور Test And Setبه طور اتمیک اجرا می شود یعنی به عنوان یک واحد بدون وقفه اجرا می شود بنابراین اگر دو دستور Test And Set همزمان ، هر کدام در یک CPU اجرا شوند ، به صورت ترتیبی اجرا می شوند.boolean Test And Set (boolean & target){boolean rv = target;target = true;return rv;}

اسلاید 23: فصل هفتم : هماهنگی فرآیندها اگر ماشین از دستور Test And Set پشتیبانی کند برای پیاده سازی انحصاری یک متغیر بولین به نام lock تعریف می کنیم و مقدار اولیه آنرا false در نظر می گیریم. ساخت فرآیند Pi در اینجا آمده است.do{ while (TestAndSet(lock));ناحیه ی بحرانی lock = false;ناحیه ی باقیمانده }while(1);

اسلاید 24: فصل هفتم : هماهنگی فرآیندها دستور Swapدستور Swap بر روی محتویات دو کلمه کار می کند که این دستور نیز مانند Test And Set به طور اتمیک اجرا می شود.void swap(boolean & a ,boolean & b){Boolean temp = a;a = b;b = temp;} این الگوریتم ها نیازمندی انتظار محدود را برآورده می کنند.

اسلاید 25: فصل هفتم : هماهنگی فرآیندها الگوریتمی که در زیر آمده از دستور Test And Set استفاده می کند و تمام نیازمندیهای سه گانه ناحیه ی بحرانی را برآورده می کند. ساختمان داده های مشترک عبارتند از:boolean waiting[n];boolean lock;برای اثبات اینکه الگوریتم mutually exclusive را رعایت می کند :می دانیم که فرآیند Pi وقتی می تواند وارد ناحیه ی بحرانی شود که waiting = false یا key = false باشد و key وقتی می تواند false باشد که دستور Test And Set اجرا شده باشد. اولین فرآیندی که دستور Test And Set را اجرا می کند می فهمد که key = false و بقیه فرآیندها باید منتظر بمانند.متغیر waiting[i] در صورتی false می شود که فرآیند دیگری از ناحیه ی بحرانی اش خارج شود. برای برقراری انحصار مقابل فقط یک waiting[i] می تواند false باشد. مقدار اولیه این ساختمان داده ها false است.

اسلاید 26: فصل هفتم : هماهنگی فرآیندها 4-7 سمافورهاسمافور یک متغیر صحیح است که صرف نظر از مقداردهی اولیه ، فقط از طریق دو عمل استاندارد اتمیک به نام های wait و signal قابل دستیابی است که گاهی نام P را به wait و V را به signal نسبت می دهندتعاریف wait و signal به صورت مقابل است :wait(s){ while(s≤0) ;//no-op s--;} signal(s){ s++;}

اسلاید 27: فصل هفتم : هماهنگی فرآیندها هنگامیکه یک فرآیند در حال تغییر مقدار سمافور است هیچ فرآیند دیگری نمی تواند مقدار همان سمافور را در همان زمان تغییر دهد.در حالت wait(s) ، تست مقدار سمافور S (s≤0) و تغییر احتمالی آن (s--) باید بدون وقفه انجام شود.1-4-7 کاربرد سمافورهامسئله ی ناحیه ی بحرانی n فرآیند را می توانیم با استفاده از سمافورها حل کنیم.n فرآیند دارای سمافور مشترکی به نام mutex هستند که مقادیر اولیه آن 1 است و هر فرآیند Pi به صورت زیر سازمان دهی می شود.do{ wait(mutex);ناحیه بحرانی signal(mutex);ناحیه باقیمانده }while(1);

اسلاید 28: فصل هفتم : هماهنگی فرآیندها 2-4-7 پیاده سازی سمافورعیب عمده ی راه حل های انحصار متقابل و تعریف سمافوری که ارائه شد این است همه ی آن ها نیازمند انتظار مشغول هستند (busy waiting). انتظار مشغول در سیستم های چند برنامه ای با یک CPU ، زمان CPU را هدر می دهد اما این روش در سیستم های چند پردازنده ای مفید است چرا که دیگر نیاز به صرف زمان زیادی برای تعویض بستر نیست و فرآیند تنها می بایست در مدت زمان قفل منتظر بماند.برای رفع مشکل busy waiting تعریف عملیات wait و signal را تغییر می دهیم. وقتی فرایندی wait را اجرا می کند ، در صورتیکه مقدار سمافور مثبت نباشد ، باید منتظر بماند و به جای busy waiting فرآیند خودش را مسدود می کند.

اسلاید 29: فصل هفتم : هماهنگی فرآیندها عملیات انسداد ، فرآیندی را در صف انتظار وابسته به آن سمافور قرار می دهد و حالت فرآیند به حالت انتظار تبدیل می شود. سپس کنترل به زمانبند CPU می رود تا فرآیند دیگری را برای اجرا انتخاب کند.فرآیندی که در انتظار سمافور S مسدود است ، در اثر عملیات signal ، توسط فرآیند دیگر ، باید دوباره شروع به اجرا نماید که شروع دوباره ی فرآیند با عملیات wakeup انجام می شود که فرآیند را از حالت انتظار به حالت آمادگی می برد. سپس این فرآیند در صف آمادگی قرار می گیرد.هر سمافور دارای یک مقدار صحیح و لیستی از فرآیندهاست. وقتی فرآیندی باید منتظر سمافور بماند ، به لیستی از فرآیندها اضافه می شود. عملیات signal فرآیندی را از لیستی از فرآیندها حذف می کند و آن را آماده می کند.

اسلاید 30: فصل هفتم : هماهنگی فرآیندها عملیات wait سمافور می تواند به صورت زیر پیاده سازی شود:void wait(semaphore S){ S.value--; if(S.value<0){ add this process to S.L; block(); } عملیات block ، فرآیندی که آنرا فرخوانی کرده به تعویق می اندازد

اسلاید 31: فصل هفتم : هماهنگی فرآیندها عملیات signal سمافور نیز می تواند به صورت زیر پیاده سازی شود:void signal(semaphore S){ S.value++; if(S.value<=0){ remove a process P from S.L; wakeup(p); } عملیات wakeup(p) اجرای فرآیند مسدود شده P را از سر می گیردنکته : عملیات block و wakeup به صورت فرخوان های سیستم در سیستم عامل پیاده سازی شده اند

اسلاید 32: فصل هفتم : هماهنگی فرآیندها 3-4-7 بن بست ها و حالت گرسنگیپیاده سازی سمافور با صف انتظار ، ممکن است منجر به این شود که دو یا چند سمافور دائما منتظر رویدادی باشند که توسط یکی از فرآیندهای منتظر ناشی شود. رویداد مورد انتظار ، اجرای عملیات است ( به این حالت بن بست می گوییم )تشریح بن بست با مثال : دو فرآیند P0 و P1 وجود دارند و S و Q در سمافور مقدار یک هستند.فرض کنید P0 عملیات wait(S) را اجرا کند و سپس P1 عملیات wait(Q) را اجرا نماید. به همین ترتیب وقتی P1 عملیات wait(S) را اجرا می کند باید منتظر بماند تا P0 عملیات signal(S) را اجرا کند چون این دو عملیات signal نمی توانند اجرا شوند ، P0 و P1 به بن بست می رسند . P0 P1 wait(S); wait(Q); wait(Q); wait(S); Signal(S); Signal(Q);Signal(Q); Signal(S);......

اسلاید 33: فصل هفتم : هماهنگی فرآیندها مسئله دیگر در مورد بن بست انسداد یا گرسنگی است. در این وضعیت ، فرآیندها در داخل سمافور به طور نامحدود منتظر می ماند. انسداد نامحدود در صورتی اتفاق می افتد که فرآیندهایی را از صف مربوط به سمافور حذف یا اضافه کنیم که به ترتیب LIFO سازماندهی شده است.4-4-7 سمافورهای دودوییسمافورهای دودویی بر خلاف سمافورهای شمارشی که در بخش قبل گفته شد می تواند تنها مقادیر 0 یا 1 را بپذیرد. (سمافورهای شمارشی می توانند هر مقدار صحیحی را بپذیرند)پیاده سازی سمافورهای شمارشی با استفاده از سمافور دودویی:(c یک مقدار صحیح) C= مقدار اولیه سمافورS سمافور شمارشی = SS1 = 1 , S2 = 0 سمافور دودویی = S1,S2

اسلاید 34: فصل هفتم : هماهنگی فرآیندها wait(s);C--if(C<0){ signal(s1)wait(s2)}signal(s1) wait(s1);C++;if(C<=0) signal(s2)else signal(s1)عملیات signal در Sعملیات Wait در S

اسلاید 35: فصل هفتم : هماهنگی فرآیندها 5-7 مسائل کلاسیک هماهنگی فرآیندها1-5-7 مسئله بافر محدودساختار کلی الگوی بافر محدود بدین صورت است که فرض می کنیم انبار بافرها حاوی n بافر است و هر بافر می تواند یک قلم داده را ذخیره کند.سمافور mutex انحصار متقابل را برای دستیابی به انبار بافر فراهم می کند و مقدار اولیه آن یک است.سمافورهای empty و full به ترتیب تعداد بافرهای خالی و پر را شمارش می کنند.

اسلاید 36: فصل هفتم : هماهنگی فرآیندها ساختار فرآیند تولید کننده :do{ … produce an item in next P … wait(empty); wait(mutex); … add nextP to buffer; … signal(mutex); signal(full); }while(1); n = مقدار اولیه empty 0 = مقدار اولیه full

اسلاید 37: فصل هفتم : هماهنگی فرآیندها ساختار فرآیند مصرف کننده :do{ wait(full); wait(mutex); … remove an item from buffer to nextC … signal(mutex); signal(empty); … consume the item in nextC; … }while(1);

اسلاید 38: فصل هفتم : هماهنگی فرآیندها 2-5-7 مسئله خوانندگان و نویسندگانیک شی داده مثل فایل را رکورد ، بین فرآیندهای همزمان به اشتراک گذاشته می شود که بعضی از فرآیند ها ممکن است نخواهند محتویات شی را بخوانند ولی بعضی دیگر ممکن است بخواهند شی داده را تغییر دهند. فرآیندهایی که فقط عمل خواندن را انجام می دهند را خوانندگان و بقیه نویسندگان می نامیم.اگر دو خواننده همزمان به شی داده مشترک دستیابی داشته باشند مشکلی ایجاد نمی شود اما اگر نویسنده و فرآیند دیگر ( نویسنده یا خواننده ) به طور همزمان به شی مشترک دستیابی داشته باشند ، مشکل ایجاد می شود.برای رفع این مشکل لازم است نویسندگان دستیلبی انحصاری به شی مشترک داشته باشند ( مسئله خوانندگان – نویسندگان)

اسلاید 39: فصل هفتم : هماهنگی فرآیندها مسئله خوانندگان و نویسندگان شکل های گوناگونی دارد و شامل اولویت های نیز هستند.اولین مسئله ی خوانندگان و نویسندگان ، هیچ فرآیندی منتظر نماند مگر اینکه خواننده ای قبلا اجازه دستیابی به شی مشترک را کسب کرده باشد( منجر به گرسنگی نویسندگان می شود)دومین مسئله خوانندگان – نویسندگان : وقتی نویسنده ای آماده ی نوشتن شد ، عمل نوشتن را هر چه زودتر انجام می دهد ( یعنی اگر نویسنده ای منتظر دستیابی به شی باشد ، هیچ خواننده ای شروع به خواندن نمی کند) (منجر به گرستگی خواننده می شود)به همین دلیل شکل های دیگری از مسئله طراحی شد.

اسلاید 40: فصل هفتم : هماهنگی فرآیندها راه حل برای اولین مسئله خوانندگان – نویسندگان :سمافور wrt=1, mutex = 1readcount = 0 ساختار فرآیند نویسنده : wait(wrt);…writing is performed…signal(wrt);readcount : مشخص می کند چند فرآیند در حال خواندن شی مشترک هستندMutex : تضمین می کند وقتی متغیر readcount تغییر می کند انحصار متقابل برقرار می کند

اسلاید 41: فصل هفتم : هماهنگی فرآیندها ساختار فرآیند خواننده :wait(mutex);readcount ++if(readcount ==1) wait(wrt);signal(mutex);... reading is performed... wait(mutex);readcount --if(readcount ==0) signal(wrt);signal(mutex);

اسلاید 42: فصل هفتم : هماهنگی فرآیندها 3-5-7 مسئله غذا خوردن فیلسوفانپنج فیلسوف را در نظر بگیرید که زندگی خود را صرف فکر کردن و غذا خوردن می کنند. فیلسوفان دارای یک میز دایره ای هستند که پنج صندلی دارد و هرکدام متعلق به یک فیلسوف است . در مرکز یک دیس از برنج قرار دارد و پنج قاشق نیز بروی میز واقع است.وضعیت غذا خوردن فیلسوفانRICE

اسلاید 43: فصل هفتم : هماهنگی فرآیندها وقتی فیلسوفی در حال فکر کردن است ، تعاملی با همکارانش ندارد. گاهی یک فیلسوف گرسنه می شود و سعی می کند قاشق نزدیک خود (قاشق بین او و همکاران چپ و راست) را بردارد. فیلسوف در هر زمان فقط یک قاشق می تواند بردارد.بدیهی است که فیلسوف نمی تواند قاشقی که دست همکارانش است را بردارد.اگر فیلسوف گرسنه ، هر دو قاشق را در آن واحد در اختیار داشته باشد ، بدون وقفه می تواند به خوردن ادامه دهد.هنگامیکه کار خوردن تمام شد هر دو قاشق را به روی میز می گذارد و دوباره شروع به فکر کردن می کند.

اسلاید 44: فصل هفتم : هماهنگی فرآیندها تذکر : مسئله غذا خوردن فیلسوفان نمایش ساده ای از نیاز به تخصیص چندین منبع بین فرآیندهای مختلف است که بدون بست و گرسنگی انجام می شود.یک راه حل سادهبرای مسئله غذا خوردن فیلسوفان این است که هر قاشق با یک سمافور نمایش داده شود.هر فیلسوف برای بدست آوردن یک قاشق ، عملیات wait را بروی آن سمافور اجرا می کند و با اجرای عملیات signal بروی سمافور مناسب ، قاشق را آزاد می کند لذا داده مشترک به صورت زیراست که مقدار اولیه ی عناصر chopstick برابر یک است.Semaphore chopstick[5];

اسلاید 45: فصل هفتم : هماهنگی فرآیندها do{ wait(chopstick[i]); wait(chopstick[(i+1)%5]; … eat... signal(chopstick[i]); signal(chopstick[(i+1)%5]); … think …}while(1);ساختار فیلسوف i:

اسلاید 46: فصل هفتم : هماهنگی فرآیندها اگرچه این راه حل تضمین می کند که هیچ دو همسایه ای به طور همزمان نمی خورند اما منجر به بن بست می گردد.تشریح بن بست در راه حل فوق : اگر هر پنج فیلسوف همزمان گرسنه شوند و هر کدام قاشق سمت چپ خود را تصاحب کنند اکنون تمام عناصر chopstickبرابر با صفر خواهند بود. وقتی هر فیلسوفی سعی می کند قاشق سمت راست خودش را بگیرد ، به تعویق می افتد.

اسلاید 47: فصل هفتم : هماهنگی فرآیندها 6-7 مناطق بحرانیاستفاده نادرست از سمافورها ممکن است منجر به خطاهای تنظیم وقت شود که کشف آن ها مشکل است.مثال :اگر ترتیب اجرای عملیات wait و signal عوض شودممکن است جندین فرآیند به طور همزمان در حال اجرای ناحیه ی بحرانی باشد.Signal(mutex); … ناحیه بحرانی …wait(muntex);

اسلاید 48: فصل هفتم : هماهنگی فرآیندها فرض کنید به جای signal(mutex) از wait(mutex) استفاده می کند که در این حالت بن بست اتفاق می افتد.همچنین اگر wait(mutex) یا signal(mutex) یا هر دو را حذف کنیم ، یا انحصار متقابل از بین می رود یا بن بست رخ می دهد.ساختار منطقه بحرانی یا ناحیه ی مشروط (Critical Region) : یک ساختار هماهنگی سطح بالا می باشد که جهت حل مشکلات مطرح شده در بالا ارائه می گردید.در ساختار منطقه ی بحرانی و ساختار ناظر که در جلوتر بیان می شود. فرض بر این است که یک فرآیند حاوی داده ی محلی ، و یک برنامه ترتیبی است که می تواند بروی آن داده ها عمل کند.

اسلاید 49: فصل هفتم : هماهنگی فرآیندها داده محلی فقط از طریق آن برنامه قابل دستیابی است که در همان فرآیند بسته بندی شده است یعنی هیچ فرآیندی نمی تواند مستقیما به داده ی محلی فرآیند دیگر دستیابی داشته باشد.پیاده سازی ساختار منطقه مشروط مقدار اولیه :Mutex = 1 First-delay = 0 Second-delay = 0

اسلاید 50: فصل هفتم : هماهنگی فرآیندها wait(mutex); while(!B){ first-count ++; if(second-count>0) signal(second-delay); else signal(mutex); wait(first-delay); first-count --; second-count++; if( first-count>0) signal(first-delay); else signal(second-delay); wait(second-delay); second-count --;} S;if(first-count>0) signal(first-delay);else if(second-count>0) signal(secind-delay);else signal(mutex);

اسلاید 51: فصل هفتم : هماهنگی فرآیندها دستيابي انحصار متقابل به ناحيه بحراني توسط Mutex فراهم مي‌شود. اگر فرآيندي نتواند به دليل نادرست بودن شرط منطقي B وارد ناحيه بحراني شود در سمافور first-delay مي‌ماند. فرآيندي كه در سمافور first-delay منتظر است، قبل از اجازه‌ي ارزتيابي مجدد شرط منطقي B (عبارت B، يك عبارت منطقي است كه دستيابي به ناحيه‌ي بحراني را مشروط مي‌سازد وقتي فرآيندي سعي مي‌كند وارد ناحيه بحراني شود عبارت منطقي B را ارزيابي مي‌كند)، به سمافور Second-delay منتقل مي‌گردد. تعداد فرآيندهاي منتظر در سمافورهاي first-delay second-delay به ترتيب توسط first-delay و second-delay مشخص مي‌شوند.

اسلاید 52: فصل هفتم : هماهنگی فرآیندها وقتي فرآيندي از ناحيه بحراني خارج مي‌شود، ممكن است شرط صنعتي B را تغيير دهد كه منجر به جلوگيري از ورود فرآيند ديگر به ناحيه بحراني‌اش گردد. فرآيند قبل از ورود به ناحيه بحراني عبارت منطقي B را تست مي‌كند كه در صورت ارزش درستي وارد ناحيه بحراني مي‌شود و در غير اينصورت بايد در سمافورهاي first-delay و second-delay منتظر بماند.

اسلاید 53: فصل هفتم : هماهنگی فرآیندها 7-7 ناظرها (Minitor)ساختار سطح بالاي ديگر ناظر است كه براي حل مسائل وايجاد دو به دو ناسازگاري پيشنهاد مي‌شود مونيتورمجموعه‌اي از زيربرنامه‌ها، متغيرها و ساختمان داده‌اي است كه همگي در يك ماژول خاص بسته‌بندي شده‌اند. ماجول مربوط به مونيتور، بين چندين فرآيند به اشتراك گذاشته مي‌شود. ساختار مونيتور يا ناظر تضمين مي‌كند كه در هر زمان فقط يك فرآيند در داخل ناظر فعال باشد. Monitor monitor-name{ shared variable declaration Procedure body P1(….){ …. } Procedure body P2(….){ …. } . . . Procedure body Pn(….){ …. } { initialization code }}

اسلاید 54: فصل هفتم : هماهنگی فرآیندها علاوه بر محتوياتي كه در بالا براي مونيتور ذكر شد، مانيتور مي‌تواند حاوي متغيرهايي از نوع‌هاي Condition باشد كه مي‌توان عمل wait و signal را بروي آن تعريف كرد. فرآيندي كه عمل wait را بر روي متغير condition صدا زند بلوكه مي‌شود. اگر فرآيند ديگري به اين علت كه فرآيند اول در داخل مونيتور قرار داشت متوقف شده بود، پس از رخداد بالا، مي‌تواند به اجراي خود ادامه داده و وارد مونيتور شود. عمل Signal دقيقاً يك فرآيند به تعويق افتاده را از سرگيري مي‌كند. اگر هيچ فرآيندي به تعويق نيفتاده باشد، عمليات Signal تأثيري نخواهد داشت.

اسلاید 55: فصل هفتم : هماهنگی فرآیندها داده های مشترککد مقدار دهی اولیه......عملیاتصف ورودیشكل رو به رو شماتيك يك ناظر را نشان مي‌دهد كه بيانگر اين است كه در هر زمان فقط يك فرآيند در داخل ناظر فعال است.

اسلاید 56: فصل هفتم : هماهنگی فرآیندها داده های مشترککد مقدار دهی اولیه......عملیاتصف ورودیxyصف وابسته به شرایط Xو Yشكل زير مونيتور با متغيرهاي (x,y) Condition را نشان مي‌دهد.

اسلاید 57: فصل هفتم : هماهنگی فرآیندها نحوه‌ي استفاده از مونيتور در فرآيندهاي توليد كننده – مصرف كننده: Monitor produeer-consumer; Full, empty; condition Procedure enter; Begin If count=N then wait (full) Enter-item; Count=count+1; If count=1 signal (empty) End; Procedure remove; Begin If count = 0 then wait (empty); Remove – item; Count = count – 1; If count = N – 1 Then signal (full); End;Count = 0; مقداردهي اوليه//end monitor; Procedure producer Begin While true do Begin Produce – item; Producer-consumer. Enter; End; End; Procedure consumer Begin While true Do Begin Producer-consumer. Remove; Consume-item; End; End;

اسلاید 58: فصل هفتم : هماهنگی فرآیندها 8-7 هماهنگي در سيستم‌هاي عامل1-8-7 هماهنگي در سولاريس 2 سيستم عامل سولاريس 2 طراحي شد تا محاسبات بي‌درنگ را انجام دهد، چند بندي باشد و از چند پردازنده‌اي پشتيباني كند. براي كنترل دستيابي به نواحي بحراني، سولاريس 2 انحصارهاي تطبيقي (adaptive metex)، متغيرهاي شرطي، سمافورها، قفل‌هاي خواننده – نويسنده وصف ويژه (Turn stile) را تدارك مي‌بيند. سولاريس 2، سمافورها و متغيرهاي شرطي را به روش يكساني پياده‌سازي مي‌كند.

اسلاید 59: فصل هفتم : هماهنگی فرآیندها 2-8-7 همگامي در ويندوز 2000 ويندوز 2000 يك هسته چندبندي است كه از كاربردهاي بي‌درنگ و چندپردازنده نيز پشتيباني مي‌كند. وقتي هسته ويندوز 2000 در يك سيستم تك پردازنده‌اي به يك منبع عمومي دستيابي دارد، موقتاً وقفه‌هايي را براي انجام اداره كنندگان وقفه‌اي مي‌فرستد كه ممكن است به آن منبع عمومي دستيابي داشته باشند. در سيستم چند پردازنده‌اي، ويندوز 2000 با استفاده از قفل‌هاي چرخشي منابع عمومي را محافظت مي‌كند. همانند سولاريس 2، هسته از قفل‌هاي چرخشي براي سگمنت‌هاي كد كوتاه استفاده مي‌كند. علاوه بر اين، به دلايل كارآيي، هسته تضمين مي‌كند كه تا زماني كه بندي قفل چرخشي را در اختيار دارد، قبضه نخواهد شد. براي همگامي بندها در خارج از هسته، ويندوز 2000 از اشياي توزيع كننده (Dispatcher Object) استفاده مي‌كند.

اسلاید 60: فصل هفتم : هماهنگی فرآیندها 9-7 تراكنش‌هاي اتمي انحصار متقابل ناحيه بحراني تضمين‌ مي‌كند كه ناحيه‌هاي بحراني به طور اتميك اجرا شوند يعني اگر دو ناحيه بحراني به طور همزمان اجرا شوند، حاصل آنها مثل حالتي است كه آنها به طور تربيتي اجرا مي‌شوند. اين خاصيت براي آن است كه اطمينان حاصل كنيم كه هر ناحيه بحراني، يك واحد منطقي از كار را ايجاد مي‌كند كه يا كاملاً اجرا مي‌شود يا اصلاً اجرا نمي‌شود. 1-9-7 مدل سيستم تراكنش: مجموعه‌اي از دستورات (عمليات) كه يك عمل منطقي را انجام مي‌دهد تراكنش (Transaction) نام دارد.نكته مهم در رابطه با پردازش تراكنش‌ها، حفظ ويژگي‌ اتمي، صرفنظر از امكان خرابي سيستم كامپيوتري است.

اسلاید 61: فصل هفتم : هماهنگی فرآیندها راهكارهاي تصمين اتمي بودن تراكنش: محيطي كه در هر زمان فقط يك تراكنش قابل انجام است حالتي كه چندين تراكنش به طور همزمان مي‌توانند فعال باشند اثر تراكنش تصديق شده نمي‌تواند توسط لغو تراكنش، خنثي شود. نكته: هر تراكنش دنباله‌اي از عمليات read و write كه توسط عمليات Commit يا abort خاتمه مي‌يابد.Commit: اعلام مي‌كند كه تراكنش با موفقيت اجرا شده Abort: اعلام مي‌كند كه اجراي تراكنش به دليل خطاهاي منطقي، متوقف شده است تراكنش تصديق شده/ لغو شده: تراكنشي كه به طور كامل اجرا شده است، تصديق شده و گرنه لغو شده است.

اسلاید 62: فصل هفتم : هماهنگی فرآیندها براي تعيين اينكه سيستم چگونه بايد خاصيت اتمي را تضمين كند مي‌بايست خواص دستگاههاي ذخيره كننده‌ي داده مورد نياز تراكنش‌ها را شناسايي كنيم. دستگاههاي ذخيره داده‌ها بر حسب سرعت نسبي، ظرفيت و قابليت ترميم خرابي متمايز مي‌شوند.  حافظه ناپايدار: اطلاعات موجود در حافظه ناپايدار بر اثر خرابي سيستم ازبين مي‌روند. (حافظه اصلي و پنهان)  حافظه پايدار: اطلاعات موجود در حافظه پايدار بر اثر خرابي سيستم از بين نمي‌روند. (ديسك‌ها، نوارها)  حافظه ماندگار: حافظه‌اي كه اطلاعات آن از بين نمي‌روند. براي اين منظور بايد كپي‌هاي متعددي از اطلاعات روي ديسك تهيه شود و اطلاعات تحت كنترل خاصي بروز شوند.

اسلاید 63: فصل هفتم : هماهنگی فرآیندها 2-9-7 ترميم بر اساس سابقه يك روش حصول اطمينان از اتمي‌بودن تراكنش اين است كه، سابقه تغييرات اطلاعات توسط تراكنش، در حافظه ماندگار ذخيره شود. متداولترين انجام اين كار اين است كه ساختمان داده‌اي به نام سابقه بر روي حافظه تشكيل شود. هر ركورد سابقه، يك عمليات از نوشتن تراكنش را توصيف مي‌كند و داراي فيلدهاي زي راست:  نام تراكنش: نام منحصر به فرد تراكنشي كه عمليات Write را انجام داد  نام قلم داده: نام منحصر به فرد قلم داده‌اي كه نوشته شده است  مقدار قديمي: مقدار قلم داده قبل از عمل نوشتن  مقدار جديد: مقدار قلم داده پس از عمل نوشتن

اسلاید 64: فصل هفتم : هماهنگی فرآیندها 3-9-7 نقاط كنترلي وقتي سيستم خراب شود، بايد با استفاده از سابقه، تراكنش‌هايي را كه نياز به داده‌هاي قديمي و تراكنش‌هايي كه نياز به داده‌هاي جديد دارند، تعيين كنيم. در واقع براي اينكار بايد كل سابقه را جستجو كنيم. اين روش دو عيب عمده دارد: جستجو در سابقه منحصر به هدر رفتن وقت مي‌شود. اغلب تراكنش‌هايي كه بر اساس الگوريتم ما دوباره بايد اجرا شوند، قبلاً داده‌هايي را بروز كرده‌اند و سابقه مي‌گويد كه آنها بايد اصلاح شوند. گر چه اين عمل ضرري ندارد اما زمان ترميم طولاني مي شود.  براي كاهش اين سربارها، مفهوم نقاط كنترلي را مطرح مي‌كنيم. در حين اجرا، سيستم سابقه را تشكيل مي‌دهد. علاوه بر اين، سيستم متناوباً نقاط كنترلي را نيز اجرا مي‌كند.

اسلاید 65: فصل هفتم : هماهنگی فرآیندها 4-9-7 تراكنش‌هاي اتمي همزمان چون هر تراكنش اتمي است، نتايج اجراي همزمان تراكنش‌ها بايد معادل حالتي باشد كه آنها به ترتيب دلخواهي به طور سريال اجرا مي‌شوند، اين خاصيت كه قابليت سريال‌سازي (Serialization) نام دارد، به اين ترتيب بدست مي‌آيد كه هر تراكنش در يك ناحيه بحراني اجرا شود. يعني تمام تراكنش‌ها در يك سمافور Mutex مشترك هستند كه مقدار اوليه آن 1 است، وقتي تراكنشي شروع به اجرا مي‌كند، اولين كارش اجراي عمليات wait (Matex) است. پس از اينكه تراكنش تصديق يا لغو شد، عمليات Signal (Mutex) را اجرا مي‌كند. 1-4-9-7 قابليت سريال‌سازي سيستمي با اقلام داده‌اي A و B را در نظر بگيريد كه هر دو توسط تراكنش‌هاي T0 و T1 خوانده و نوشته مي‌شوند. فرض كنيد اين تراكنش‌ها به طور دائمي اجرا مي‌شوند. به طوريكه ابتدا T0 و سپس T1 اجرا مي‌شوند اين ترتيب اجرا زمانبندي نام دارد.

اسلاید 66: فصل هفتم : هماهنگی فرآیندها T1T01Read (A)1Write (A)1Reud (B)1Write (B)Read (A)Write (A)Reud (B)Write (B)شكل زير زمانبندي سريال كه در آن T0 و سپس T1 اجرا مي‌شود نشان مي‌دهد زمانبندي سريال: زمانبنديي كه در آن، هر تراكنش به طور اتمي اجرا مي‌شود. هر زمانبندي سريال متشكل از دنباله‌اي از دستورات از تراكنش‌هاي مختلف است كه دستورات مربوط به يك تراكنش، با هم در آن زمانبندي ظاهر مي‌شود. بنابراين براي يك مجموعه n تراكنشي، تعداد زمانبندي سريال معتبر n است.

اسلاید 67: فصل هفتم : هماهنگی فرآیندها 2-4-9-7 پروتكل قفل كردن يك روش براي حصول اطمينان از قابليت سريال‌سازي اين است كه به هر قلم داده يك قفل نسبت داده شود. در نتيجه نياز به پروتكل قفل‌كردن است تا شيوه قفل كردن و باز كردن قفل را مشخص مي‌كند. يك قلم داده به شكل‌هاي گوناگوني مي‌تواند قفل شود كه در اينجا 2 حالت اشاره شده: حالت اشتراك: اگر تراكنش Ti داراي قفل حالت اشتراك بروي قلم داده Q باشد كه با S نشان داده شود، آنگاه Ti مي‌تواند Q را بخواند ولي نمي‌تواند بنويسيد. حالت انحصاري: اگر تراكنش Ti داراي قفل حالت انحصاري بروي قلم داده Q باشد كه با X نشان داده مي‌شود، آنگاه Ti مي‌تواند Q را بخواند و بنويسيد.

اسلاید 68: فصل هفتم : هماهنگی فرآیندها يك پروتكل كه قابليت سريالسازي را تضمين مي‌كند پروتكل قفل دو مرحله‌اي است. اين پروتكل مستلزم اين است كه هر تراكنش درخواست قفل كردن و بازكردن قفل را در دو مرحله انجام دهد: مرحله رشد: تراكنش ممكن است قفلي را ايجاد كند اما ممكن است قفلي را باز نكند. مرحله كوچك شدن: تراكنش ممكن است قفل‌هايي را باز كند ولي قفل‌هاي جديدي را ايجاد نمي‌كند. 3-4-9-7 پروتكل‌هاي زماني روش ديگر براي تضمين ترتيب قابليت سريالسازي (علاوه بر اين حالت كه، در زمان اجرا با اولين قفلي كه هر دو تراكنش درخواست مي‌كنند و شامل حالت‌هاي ناسازگاري‌اند، تعيين مي‌شود)، اين است كه، از قبل ترتيبي بين تراكنش‌ها انتخاب شود. متداولترين انجام اين كار استفاده از الگوي زماني است.

اسلاید 69: فصل هفتم : هماهنگی فرآیندها دو روش ساده براي پياده‌سازي اين الگو وجود دارد: استفاده از ساعت سيستم به عنوان مهر زماني. يعني مهرزماني يك تراكنش برابر با مقدار ساعت سيستم در زمان ورود تراكنش به سيستم است. استفاده از شمارنده منطقي به عنوان مهر زماني. يعني مهرزماني يك تراكنش برابر با مقدار شمارنده در هنگام ورود تراكنش به سيستم است. مهرهاي زماني تراكنش‌ها، ترتيب قابليت سريالسازي را مشخص مي‌كند.