بخشی از پاورپوینت
اسلاید 1 :
Interprocess Communication
اغلب نیاز است که يک پردازش با پردازشهای دیگر بتواند ارتباط داشته باشد . به عنوان مثال Shell Pipeline یا پوسته سیستم عامل بصورت پردازشهای متوالی پیاده سازی شده است . خروجی Process اول باید به Process دوم داده شود و . . . .
بنابراین نیاز است که پردازشها بتوانند با یک روش دارای ساختار مناسب با هم Communicate داشته باشند . حالا می خواهیم به برخی موضوعات مربوط به این ارتباط میان پردازشی Interprocess Communication (IPC) بپردازیم .
چند موضوع باید بحث شود :
1- چگونه یک Process می تواند اطلاعاتی را به Process دیگر انتقال دهد ؟
2- چگونه مطمئن شويم دو يا چند پروسس مزاحم همديگر نميشوند. مثلا هر دو نمی خواهند در يک فضای حافظه بنويسند.
3- وقتی پردازشها وابستگيهايی نسبت به هم دارند، دنباله صحيح پروسسها چگونه است.
اسلاید 2 :
علت رخ دادن اشکال در مثال بالا این است که پروسس B استفاده از یکی از متغیرهای مشترک را زمانی شروع می کند که پروسس A هنوز کارش را با آن متغیر مشترک تمام نکرده است .
انتخاب Primitive (عمل اولیه) مناسب برای دستیابی به Mutual Exclusion یک موضوع مهم طراحی در هر سیستم عاملی است و موضوعی است که بطور دقیق با جزئیات به آن می پردازیم .
مسئله اجتناب از شرایط مسابقه بطور انتزاعی می تواند مطرح شود .
- برخی زمانها Process مشغول Computing (محاسبات) داخلی خودش و کارهای دیگری است که به شرایط مسابقه منجر نمی شود .
-برخی زمانهایک پردازش ممکن است در حال دستیابی به فایل يا حافظه مشترک یا کارهای بحرانی دیگری باشد که منجر به شرایط مسابقه می شود .
تعریف : بخشی از برنامه که طی آن Shared Memory (حافظه مشترک) مورد دستیابی قرار می گیرد Critical region (ناحیه بحرانی) یا Critical Section (بخش بحرانی) نامیده می شود .
اگر بتوانيم کاری کنيم که هيچ دو پردازشي همزمان در بخشهای بحرانی خود نباشند میتوانيم از شرايط مسابقه جلوگيری کنيم .
اسلاید 3 :
برای اينکه پردازشهای موازی بطور صحيح و با کارآ يی بالا از داده مشترک استفاده کنند برآوردن چهار شرط زير ضروری است
1- هيچ دو پردازشی همزمان در بخش بحرانی نباشند.
2 - هيچ فرضی درباره سرعت و تعداد CPU ها در نظر گرفته نشود.
3- هيچ پردازشی هنگامی که خارج از ناحيه بحرانی اش است نبايد بقيه پردازشها را
Block کند.
هيچ پردازشی نبايد برای هميشه منتظر ورود به بخش بحرانی اش باقی بماند. 4-
اسلاید 4 :
Mutual Exclusion with Busy Waiting
در این بخش روشهای پیشنهادی برای دستیابی به انحصار متقابل ((mutual exclusion به گونه ای که وقتی یک Process مشغول Update حافظه مشترک است ، هیچ Process دیگری به ناحیه بحرانی اش وارد نشود را بررسی می کنیم .
(Disabling interrupts)غير فعال نمودن وقفه ها
(Lock Variables) استفاده از متغيرهای قفل
(Strict Alternation) تناوب قطعی
(Peterson’s Solution) راه حل پترسون
دستورالعمل TSL(Test and Set Lock)
اسلاید 5 :
(Disabling interrupts)غير فعال نمودن وقفه ها
ساده ترین راه این است که هر Process درست پس از اینکه وارد ناحیه بحرانی اش شد ، تمام Interrupt ها را غیر فعال (disable) کند و درست قبل از ترک ناحیه بحرانی اش ، آنها را دوباره فعال بکند . وقتی Interrupt ها غیر فعال شوند . هیچ Clock Interrupt ای رخ نمی دهد . CPU هم که فقط در نتیجه وقفه ( وقفه Clock و بقیه وقفه ها ) از یک Process به Process دیگر Switch می نمود ، پس با Disable شدن وقفه ها ، CPU به Process دیگر Switch نمی کند . پس وقتی یک Process ، وقفه ها را Disable کند با خیال راحت بدون اینکه Process دیگری مزاحمش شود می تواند حافظه مشترک را Update کند .
اما این رویکرد بطور کلی جالب نیست زیرا عاقلانه نیست به یک User Process قدرت خاموش کردن Interrupt ها را بدهیم . فرض کنید یک Process وقفه ها را غیر فعال بکند و دیگر هیچوقت آنها را فعال نکند . این پایان سیستم است . به علاوه اگر سیستم Multiprocessor (دارای چند ریزپردازنده) باشد ، غیر فعال نمودن وقفه ها فقط بر روی CPU ای که دستورالعمل Disable را اجرا کرده است موثر است و بقیه Processor ها می توانند Process های دیگری را اجرا کنند که به حافظه مشترک دسترسی داشته باشند .
از طرف دیگر اغلب برای ((Kernel هسته سیستم عامل مناسب است که در مورد تعداد کمی از دستورالعملها که مربوط به Update نمودن متغیرها و لیستها است ، وقفه ها را غیر فعال کند .
مثلا وقتی لیست Process های آماده اجرا در حال Update است و در یک حالت Inconsistent( ناسازگار) است ، اگر وقفه ای رخ دهد ممکن است منجر به Race Condition شود .
جمع بندی : غیر فعال نمودن وقفه ها توسط خود سیستم عامل اغلب یک تکنیک سودمند است ولی به عنوان یک مکانیزم کلی Mutual Exclusion برای User Process ها مناسب نیست .
اسلاید 6 :
(Lock Variables) استفاده از متغيرهای قفل
یک تلاش دیگر این است که از یک راه حل نرم افزاری استفاده کنیم ، فرض کنید یک متغیر مشترک به نام Lock )قفل) داشته باشیم، که در اول صفر است . هر Process که خواست وارد Critical region (ناحیه بحرانی) اش شود ، ابتدا Lock را چک می کند . اگر مقدار صفر را داشت آنوقت مقدار آن را یک می کند و وارد ناحیه بحرانی اش می شود و بلافاصله پس از خروج از ناحیه بحرانی اش مقدار Lock را صفر می کند . اگر مقدار Lock یک باشد ، Process باید صبر کند تا اینکه آن صفر شود . پس صفر به این معنی است که هیچ Process ای در ناحیه بحرانی اش نیست و یک به این معنی است که یک Process در ناحیه بحرانی اش است .
متاسفانه این ایده همان مشکلی را دارد که قبلا در مورد Spooler Directory دیدیم :
فرض کنید یک Process ای Lock را خواند و دید مقدارش صفر است و قبل از اینکه مقدار Lock را یک بکند CPU از آن گرفته شود و به Process دیگری داده شود ، و آن Process مقدار Lock را چک می کند و مقدار آن صفر است ، سپس مقدار آن را یک می کند و وارد ناحیه بحرانی اش می شود و یک مقدار کار می کند ، اگر CPU در این زمان از این Process گرفته شود و به Process اول داده شود این Process نیز مقدار Lock را یک می کند (قبلا هم یک بوده است ) و وارد ناحیه بحرانی اش می شود . حالا دو Process همزمان داخل ناحیه بحرانی شان هستند ، پس نتوانسته ایم به Mutual Exclusion برسیم .
ممکن است فکر کنید با دوبار چک کردن متغیر Lock قبل از عملیات Update می توان مشکل را حل نمود ، اما در واقع این کار کمکی نمی کند . اگر درست پس از چک دوم توسط Process اول ، Process دوم CPU بگیرد و مقدار Lock را یک کند و وارد ناحیه بحرانی اش بشود ، وقتی Process اول دوباره CPU بگیرد وارد ناحیه بحرانی اش می شود و بازهم Mutual Exclusion نخواهیم داشت .
اسلاید 7 :
مقدار Turn در ابتدا صفر است . Process 0 ، turn را چک می کند و می بیند که صفر است پس وارد ناحیه بحرانی اش می شود . Process 1 ، turn را چک می کند و می بیند که صفر است پس در یک حلقه محکمی می افتد و بطور مداوم turn را چک میکند تا زمانی که turn = 1 شود .
Busy Waiting (مشغول است در حال انتظار باشد ) : چک نمودن یک متغیر بطور پیوسته تا اینکه یک مقدار ظاهر شود ، Busy waiting نامیده می شود . معمولا باید از Busy waiting اجتناب کرد زیرا زمان CPU را تلف می کند . فقط در صورتیکه تخمین معقولی وجود دارد که انتظار کوتاه خواهد بود از Busy waiting استفاده می شود .
اگر چه روش تناوب قطعي از حالت مسابقه جلوگیری می کند (انحصار متقابل را فراهم می سازد) اما راه حل مناسبی نیست زیرا ایجاب می کند که Process ها در ورودشان به ناحیه بحرانی قطعا متناوب عمل کنند . در نتیجه شرط سوم را برآورده نمی سازد (یعنی یک Process در حالی که خارج از ناحیه بحرانی اش است پروسس های دیگر را از ورود به ناحیه بحرانی شان مانع شده و آنها را Block کرده است .) (صحت را دارد ولی کارایی بالا را ندارد ) .
اگر مثال Spooler Directory را در نظر بگیرید ، Critical region به معنای خواندن و نوشتن در Spooler directory خواهد بود : پس از آنکه Process 0 یک فایل را Print کرد نمی تواند فایل دیگری را Print کند در حالی که Process 1 مشغول انجام کار دیگری است
اسلاید 8 :
هر Process قبل از ورود به ناحیه بحرانی اش رویه Enter_region را با شماره Process خودش به عنوان پارامتر صدا می زند . (Process می تواند صفر یا یک باشد ) که باعث می شود اگر لازم باشد صبر کند تا وقتی که ورود به ناحیه بحرانی بی خطر باشد .
وقتی Process کار خودش را در ناحیه بحرانی انجام داد ، Leave_region را صدا می زند تا نشان دهد که از ناحیه بحرانی اش خارج شده تا Process های دیگر بتوانند وارد ناحیه بحرانی شان شوند .
اسلاید 9 :
دستورالعمل TSL(Test and Set Lock)
یک روش است که به کمک سخت افزار انجام می شود . اکثر کامپیوتر ها مخصوصا سیستمهای چند پردازنده دستورالعملی به نام Test and Set Lock دارند که این طور کار می کند : محتوای یک کلمه حافظه را می خواند و داخل یک Register می ریزد و سپس مقدار غیر صفر (مثلا یک) در آن خانه حافظه ذخیره می کند .
این دو عمل خواندن کلمه و ذخیره کردن درون آن تضمین می شود که تقسیم نا پذیر باشد . یعنی هیچ پروسس دیگری تا زمانیکه دستورالعمل تمام نشده نمی تواند به آن کلمه حافظه دسترسی داشته باشد .
در یک محیط چند پردازنده CPU ای که دستورالعمل TSL را اجرا می کند ، BUS حافظه را قفل می کند تا دیگر CPU ها نتوانند به حافظه دسترسی داشته باشند تا زمانیکه دستورالعمل TSL به پایان برسد . از یک متغیر مشترک به نام Lock استفاده می شود که وقتی صفر است ورود به ناحیه بحرانی امن است .
اسلاید 10 :
Monitor ها
اگر جای Empty و Mutex عوض شود .
اگر بافر کاملا پر باشد ، تولید کننده Block می شود در حالی که Mutex برابر صفر است .
بعدا وقتی که مصرف کننده سعی می کند به بافر دسترسی پیدا کند یک Down روی Mutex انجام می دهد . چون صفر است آن نیز Block می شود و برای همیشه هر دو به خواب می روند .
Hoare 1974
Hansen 1975
یک ابزار اولیه سطح بالاتر برای همزمانی به نام Monitor ارائه دادند .
کامپایلر نمی گذارد در هر لحظه بیش از یک Processor از رویه های یک Monitor استفاده کند .
Monitor ها و Semaphore ها برای سیستمهای Shared Memory قابل استفاده اند . در C و Basic و Pascal وجود ندارند .
Concurrent Euclid (1983,Holt)
سمافورها خیلی سطح پائین هستند و مانیتورها به استثنای چند زبان برنامه سازی قابل استفاده نیستند . Minix و Unix از Message Passing استفاده می کنند .
