مقالات و جزوه های درسی رشته کامپیوتر

فصل پنجم

همزمانی:

انحصار متقابل و همگام سازی

همه موضات محوری در طراحی سیستم عامل به مدیریت فرایند ها و نخ ها مربوط است.

 

چند برنامه ای : مدیریت فرایند فرایندهای متعدد در داخل یک کامپیوتر تک پردازنده ای.

چند پردازشی: مدیریت فرایند فرایندهای متعدد در داخل یک کامپیوتر چند پردازنده ای.

پردازش توزیعی: مدیریت فرایند فرایندهای متعدد در روی سیستم های کامپیوتری متعدد.

برای هر سه زمینه فوق مسئله هم زمانی است.

همزمانی در سه زمینه متفاوت طراحی می گردد:

 

کاربردهای متعدد: زمان پردازش کامپیوتر به طور پویا بین تعدادی کار یا کاربرد بتواند تقسیم گردد.

 

کاربرد ساختیافته: بعضی از کاربردها رابه صورت مجموعه ای از فرایندهای همزمان،به طورکارامد برنامه سازی کرد.

 

ساختار سیستم عامل: همین امتیاز ساختاردهی ،برای برنامه ساز سیستم نیز قابل اعمال است.

نیاز اصلی برای حمایت از فرآیند های همزمان، توان اعمال ا نحصار متقابل است.

 

 

یعنی وقتی به یک فرآیند قدرت انجام عملی داده شد. بتوان تمام فرایندها دیگررا از این قدرت بازداشت.

اصول همزمانی

 

در سیستم های چند پردازنده ای ،نه تنها ممکن است فرایند ها در بین یکدیگر اجرا شوند،بلکه می توانند واقعا به موازات هم و با همپوشانی اجرا گردند.

 

در این روش مشکلات زیر پیش می آید:

 

 1- اشتراک منابع سراسری پر مخاطره است.

 2- مدیریت تخصیص بهینه منابع برای سیستم عامل است

 3- تعیین محل خطای برنامه سازی مشکل می شود.

 

ملاحظات سیستم عامل در همزمانی:

سیستم عامل باید به تواند فرایندهای فعال مختلف را دنبال کند که این کار توسط بلوک های کنترل فرایند انجام می شود.

سیستم عامل باید منابع را به هر یک از فرایند ها تخصیص دهد و یا باز پس بگیرد از جمله:

 

 (وقت پردازنده، حافظه، پرونده هاريا، دستگاههای ورودی و خروجی)

 

سیستم عامل باید داده ها و منایع فیزیکی هر فرایند را در مقابل دخالت نا خواسته فرایند دیگر محافظت کند.

 نتایج یک فرایند باید مستقل از سرعت پیشرفت اجرای فرایند های همزمان دیگر باشد.

 

محاوره فراینده ها:

محاوره فرآیندها : ارتباطات بین فرآیندها و نخ ها

 

بی اطلاعی فرایند ها از یکدیگر: فرایند ها مستقل هستند.

 

اطلاع غیر مستقیم فرایندها از یکدیگر : دسترسی به بعضی از اشیاء یکدیگر.

 

اطلاع ار یکدیگر :با نام ، با یکدیگر در ارتباط هستند.

هنگامی که چند فرایند برای استفاده از یک منابع فعالیت می کنند درگیری دارند که

شرایط اساسی در راه حل صحیح :

 

انحصار متقابل در اجرای بخش بحرانی.

 

فعالیت های محدوده زمانی در هر بخش.

 

تعداد مرتبه های رفتن به ناحیه بحرانی در حضور منتظران محدود است.

هیچ فرضی نسبت به طول دستورات و سرعت اجرا نمی باشد.

 

فرایند:حلقه همیشگی.

 

در پایان بن بست به باقی فرایند ها پیامی ارسال می گردد.

 

گرسنگی.

 

همکاری فرایند ها توسط اشتراک:

 

فرایندهایی را پوشش می دهند که با یکدیگر محاوره می کنند، بدون اینکه صراحتا از یکدیگر مطلع باشند.

 

مسئله کنترل انحصار متقابل ، بن بست ،گرسنگی باز وجود دارد و داده در دو حالت ممکن خواندن و نوشتن مورد دسترسی قرار می گیرند و تنها مورد نوشتن باید در انحصار متقابل قرار گیرد.

 

همکاری فرایند ها توسط ارتباط:

 

هر فرایند محیط مجزای خود را دارد و فرایند های دیگر را در بر ندارد.

محاوره بین فرایند ها غیر مستقیم است و فرایند ها صراحتا از محل یکدیگر اطلاع شندارند.

 

ارتباط را با نوعی پیام مشخص می کنند.

 

مسئله بن بست و گرسنگی وجود دارد.

ملزومات انحصار متقابل:

انحصار متقابل باید اعمال گردد:

 

فرایندی که در بخش غیر بحرانی خود متوقف می شود ، باید طوری عمل کند که هیچ دخالتی در فرایند های دیگر نداشته باشد .

 

برای فرایندی که نیاز به دسترسی یک بخش بحرانی دارد،نباید به تاخیر انداختن نا محدود آن وجود داشته باشد ، بن بست یا گرسنگی نمی تواند مجاز باشد.

هنگامی که هیچ فرایندی در ناحیه بحرانی نیست ورود یک فرایند بدون تاخیر است.

 

هیچ فرضی در باره تعداد فرایند ها و یا سرعت آن داشت.

 

هر فرایندی تنها برای زمان محدودی در ناحیه بحرانی قرار می گیرد.

 

رویکرد نرم افزاری

را میتوان برای فرایند های همزمانی که روی ماشینهای تک پردازنده ای یا چند پردازنده ای که از حافظه مشترک استفاده می کنند پیاده سازی کرد.

 

الگوریتم DEKKER:

 

برای انحصار متقابل دو فرایند ،الگوریتمی را منتشر کرد .

امتیاز این رویکرد آن ایت که حداکثر خطاهای متداول در ایجاد برنامه های همزمان ،تشریح می شود.

 

الگوریتم Peterson :

 

آرایه سراسری flag نمایانگر وضع هر فرایند نسبت به انحصار متقابل است و متغییر سراسری turn در گیریهای همزمانی را حل می کند.

 

انحصار متقابل: حمایت سخت افزار

از کار انداختن وقفه:

 

در یک ماشین تک پردازنده ،هم زمان نمی شود فرایند ها وارد ناحیه بحرانی شوند.

 

برای ضمانت انحصار متقابل ،کافی است از مواجهه فرایند با وقفه جلوگیری شود.

چون بخش بحرانی نمی تواند وقفه داده شود، لذا انحصار متقابل ضمانت شده است.

 

کارایی اجرایی به طور متقابل کم می شود.

 

این روش در معماری چند پردازندهای کارایی ندارد.

 

 

دستور العمل آزمون و مقدار گذاری:

دراین روش هر فرایند در هنگام وارد شدن به ناحیه بحرانی مقدار متغییر را یک می کند و هنگام خارج شدن آن را صفر می کند ،هنگامی که مقدار یک می باشد هیچ فرایندی اجازه ورود به این ناحیه را ندارد.

ویژگیهای رویکرد دستورالعمل ماشین:

برای هر تعداد از فرایندها ،روی یک پردازنده و یا چند پردازنده که از حافظه مشترک استفاده می کنند ،قابل به کارگیری است.

 

ساده است و لذا وارسی آن آسان می باشد.

 

از آن برای حمایت از بخسهای بحرانی متعدد می توان استفاده کرد.

معایب رویکرد دستورالعمل ماشین:

انتظار مشغول جود دارد.

 

امکان گرسنگی وجود دارد.

راهنماها:

برای علامت دهی بین فرایند ها و اعمال یک نظام انحصار متقابل استفاده کرد.

 

اصل اساسی این است که دو یا چند فرایند بتوانند به وسیله علائم سادهای با یکدیگر همکاری کنند.

 

برای علامت دادن از متغییر ویژه ای به نام راهنما استفاده می کند.

 

برای فرستادن علامت توسط راهنمای s،فرایند اولیه signal( s ) را اجرا می کند.

 

->برای دریافت علامت توسط یک راهنمای s ،فرایند اولیه wait(s) را اجرا می کند.

 

اگر علامت مربوط ، هنوز فرستاده نشده باشد ،این فرایند تا زمان ان،معلق می ماند.

 

ناظرها:

ساختاری از زبان بزنامه سازی است که کار راهنما را انجام می دهد و کنترل آن هم ساده تر است.

ساختار ناظر در تعدادی از زبانهای برنامه سازی ازmodulaو ... وبه صورت کتابخانه ای پیاده سازی می شود.

این افراد اجازه می دهد تا قفل های ناظر در روی هر شئ

بگذارد.

در عمل مانند لیست پیوندی است.

 

ناظر با علامت:

مولفه ای نرم افزاری مشتمل بر یک یا چند رویه، دنباله ای از مقدار گذاری اولیه و داده های محلی است .

 

دارای ویژگی های :

1. متغییرهای داده محلی ناظر تنها برای رویه های خود ناظر قابل دسترسی بوده و هیچ رویه دیگری به آنها دسترسی ندارد .

 

1. یک فرایند با احضار یکی از رویه های ناظر ،وارد ان می شود.

 

1. در هر زمان تنها یک فرایند می تواند در ناظر در حال اجرا باشد.

دو تابعی که روی متغییر شرطی عمل می کند عبارتند از:

 

Cwait(c) : اجرای یک فرایند صدا کننده را روی شرط c معلق می کند.

 

Csignsl(c) : اجرای یک فرایندی که بعد از یک عمل cwait ، روی همان شرط معلق بوده است را از سر می گیرد.

 

تبادل پیام:

پیام ها برای انحصار متقابل مفید هستند.

ابزاری موثری را برای ارتباط بین فرآیندها فراهم می کند.

هنگامی که دو فرآیند با یکدیگر ارتباط برقرارمی کند ،دو نیاز بنیادی همگام سازی و ارتباط باید تامین می شود.

فرایند ها نیاز به همگامسازی دارند تا انحصار متقابل تامین شوند.

Send (destination,message)

Receive(source,message)

 

 

همگام سازی

 

در هنگام تبادل پیام سه ترکیب زیر متداول است :

مسدود شدن فرستنده ،مسدود شدن گیرنده:

گاهی به این قرار ملاقات میگویند.همگام سازی بین فرایند ها را محکم می کند.

مسدود نشدن فرستنده ،مسدود شدن گیرنده:

گیرنده تا رمان ورود پیام مسدود است.

مسدود نشدن فرستنده ، مسدود نشدن گیرنده .

آدرس دهی:

آدرس دهی مستقیم:

1. Send شامل شناسه آدرس فرایند مقصد.
2. receive یا صریح بیان می کند یا ضمنی.

آدرس دهی غیر مستقیم:

پیام ها مستقیما از فرستنده به گیرنده فرستاده نمی شوند بلکه به یک ساختمان داده مشترک ارسال می گردد.

این ساختمان داده دارای صفهایی است که به آن ها صندوق پستی می گویند.

انتساب پیام به صندوق پستی می تواند : پویا و ایستا باشد.

 

ایستا: به یک فرایند نسبت داده می شود.

 

پویا:  هنگامی که فرستنده های زیادی وجود داشته باشد.

 

 

ارتباط غیر مستقیم فرایندها:

 

 

قالب پیام:

قالب پیام شامل:

1. سرآمد:حاوی اطلاعات درباره پیام.
2. بدنه:حاوی خود پیام.

 

نظام صف بندی

FIFO  ساده ترین نظام صف بندی

 

اولیت پیام بر اساس نوع پیام

 

اولیت پیام توسط فرستنده

 

اولیت پیام توسط گیرنده (بازرسی صف پیامها و انتخاب پیام بعدی)

وضعیت صفهای فرایندها :