مفاهیم سیستم عامل (2)

جلسه چهارم:

FCFS :

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

SRTN :

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

SJF :

انحصاری است، قابلیت پیش بینی و تکرار دارد.

Priority :

زمانی انحصاری است که پروسه وارد حالت Running می شود.این اولویت زمانی انحصاری است که پروسه ای در حال اجرا است و پروسه ای دیگر با اولویت بالاتر وارد صف می شود.اگر پروسه ای با اولویت بالاتر وارد صف Ready شود، ان پروسه که در حال اجرا است ،از این حالت خارج شده و پروسه ای که اولویتش بالاتر است ،اجرا می شود.
اگر اولویت دادن منصفانه باشد، Fairness است.
یک سیستم به نام Aging است که اولویت پروسه هایی را که بیش از اندازه در صف مانده است از طریق جدول PCB Waiting Time پیدا می کند تا اجرا شود.

Round Robin (قاچ زمانی) :

در این الگوریتم زمان پردازش تخصیص می شود.

این الگوریتم براساس قاچ زمانی که سیستم عامل انتخاب می کند ،پروسه ها را به حالت اجرا می برد.اگر قاچ زمانی خیلی بزرگ باشد این الگوریتم تبدیل به الگوریتم FCFS می شود.چون تا کار پروسه در طول قاچ زمانی تمام نشود، منبع را رها نمی کند و مشکلی که زمان انتخاب قاچ زمانی کوچک وجود دارد این است که پروسه به قطعات کوچک اجرا می شود و حالت سوئیچ برای پروسه توسط سیستم عامل به وجود می اید.یعنی سیستم عامل باید عملیات Push و Pop زیادی را انجام دهد.از لحاظ سیستم عامل پیاده سازی قاچ زمانی ایستا بسیار راحت است.ولی این حالت منصفانه نیست. اگر هم به صورت پویا بخواهد قاچ زمانی مختلفی را برای پروسه تخصیص دهد دچار پیچیدگی می شود و امکان دارد زمان بر باشد.این الگوریتم هم انحصاری است و هم غیر انحصاری.پروسه در داخل قاچ زمانی اجرا قرار می گیرد، انحصاری است و زمانی که قاچ زمانی تمام شده و می خواهد جای خود را به پروسه ی دیگر بدهد این حالت غیر انحصاری می شود.

الگوریتم Multi Level Queue Schduling :

مخلوطی از الگوریتم های زمانبندی در این الگوریتم استفاده می شود.
در حقیقت هر الگوریتمی که تا به حال توضیح داده شد ،به صورت جداگانه توسط سیستم عامل اجرا می شود و این عمل به این صورت است که پروسه ها در صف های مختلف قرار می گیرند هر الگوریتم در هر یک از این صف ها پروسه را انتخاب می کند و توسط یک الگوریتم زمانبندی دیگر وارد حالت Running می شود.
سطح اول پروسه های سیستمی که دارای اولویت بالایی می باشند،قرار می گیرند و توسط الگوریتم Priority و Even Driven پروسه ای را انتخاب می کند که اولویت بالایی دارد.
سطح بعدی پروسه هایی قرار می گیرند که اهمیت انها نسبت به پروسه های سیستمی پایین تر است. مثل پروسه های محاوره ای و این پروسه ها از طریق الگوریتم Round Robin یا قاچ زمانی مدیریت می شوند.
سطح سوم پروسه هایی هستند که بسیار بزرگ هستند . مانند پروسه های Bach و توسط الگوریتم FCFS مدیریت می شوند.

الگوریتم Feed Back :

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

جلسه پنجم:

گفتگوی پروسه ها به سه دسته طبقه بندی می شود:

1) بی اطلاعی پروسه ها از یکدیگر :

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

2) اطلاع غیر مستقیم پروسه ها از یکدیگر :

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

3) پروسه هایی که اطلاع مستقیم از یکدیگر دارند :

این پروسه ها با نام یکدیگر کار می کنند. امکان وابستگی نتایج یک پروسه به اطلاعات به دست امده از پروسه های دیگر وجود دارد.
چهار حالت نیز برای این پروسه ها اتفاق می افتد که باید مکانیزم هایی را رعایت کنند:
1) انحصار متقابل
2) بن بست
3) گرسنگی
4) وابستگی داده ها

رقابت پروسه ها :

هنگامی که پروسه ها نیاز به یک منبع مشترک دارند ،این پروسه ها با یکدیگر درگیر می شوند و در نهایت یکی از این پروسه ها در این درگیری برنده می شود.حال پروسه ای که در حال اجرا است پروسه های دیگر نباید حالت این پروسه را تغییر دهند و نباید به حالت Running بروند. به این حالت که پروسه ها به پروسه ای دیگر در حالت اجرا دخل و تصرفی نداشته باشند ،انحصار متقابل می گویند.
در استفاده از منابع مشترک باید مکانیزم ها و کنترل هایی را اعمال کرد تا قابلیت اطمینان خدشه دار نشود.مثلا اگر پروسه ای به سراغ منبع مشترکی می رود ،مطمئن باشیم تا تکمیل فعالیت پروسه ،پروسه ای دیگر به سراغ ان منبع مشترک نرود.به این مکانیزم انحصار متقابل یا بازداری دوجانبه می گویند.
فرض کنید دو پروسه یا بیشتر به یک منبع غیرمشترک (چاپگر) نیاز دارد.این منبع غیر مشترک را منبع بحرانی می گویند.ان قسمت از پروسه که با این منبع کار می کند ،ناحیه ی بحرانی پروسه می گویند.از ان دستورالعمل پروسه که با یک منبع مشترک یا غیر مشترک کار می کند تا اخرین دستورالعملی که با این منبع در ارتباط است ناحیه ی بحرانی پروسه می گویند.
تعریف بن بست:اگر سه پروسه به نام های P1 و P2 و P3 داشته باشیم،پروسه P1 منبع R1 ،پروسه P2 منبع R2 و پروسه P3 منبع R3 را در اختیار دارد.پروسه P1 منبع R2 ،پروسه P2 منبع R2 وپروسه P3 منبع R3 را درخواست می کند و هر پروسه منبع در اختیار خود را ازاد نمی کند.در این حالت است که بن بست اتفاق می افتد.
تعریف گرسنگی:فرض می کنیم سه پروسه P1 ، P2 ، P3 درخواست منبع R را بکنند.در رقابت بین پروسه ها پروسه P1 منبع را در اختیار بگیرد و بعد از اینکه پروسه P1 کارش با منبع R تمام شد و منبع را رها کرد ،در رقابت بین P2 و P3 ،پروسه P3 منبع R را در اختیار بگیرد.در این زمان پروسه P1 دوباره درخواست منبع R را بکند.وقتی که P3 کارش با منبع R تمام شد ،در رقابت بین پروسه های P1 و P2 دوباره P1 برنده شود.این حالت ممکن است چند بار اتفاق بیفتد و منبع به پروسه P2 نرسد. در این حالت می گویند گرسنگی اتفاق افتاده است.
همکاری پروسه ها توسط اشتراک:همکاری به وسیله ی اشتراک پروسه هایی را پوشش می دهد که با یکدیگر گفتگو می کنند .بدین معنی که از یکدیگر اطلاع دارند.یعنی اینکه پروسه P1 می داند که وقتی کارش تمام شود نتیجه به دست امده توسط پروسه دیگر استفاده خواهد شد.پروسه های متعددی به پرونده های مشترک در بانک اطلاعاتی مشترک دسترسی دارند.ممکن است هر پروسه این داده ها را بدون اطلاع پروسه ی دیگر به هنگام سازی کند،ولی بداند که پروسه های دیگر به این داده ها دسترسی دارند.
همکاری پروسه ها توسط ارتباط: پروسه ها با یکدیگر تعارف می کنند.

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

1) از میان تمام پروسه هایی که برای منبع یکسان یا شی مشترکی دارای بخش بحرانی هستند،تنها یک پروسه بتواند وارد بخش بحرانی شود.
2) سرعت نسبی پروسه ها واولوت پروسه ها نقشی در دستیابی منبع مشترک یا ورودشان به ناحیه بحرانی نداشته باشد.
3) پروسه هایی که در ناحیه ی بحرانی خود قرار گرفته اند، نباید تاثیری بر روی پروسه هایی داشته باشند که در ناحیه ی بحرانی قرار دارند.
4) نباید پروسه ها بیش از اندازه برای ورود به ناحیه بحرانی منتظر بمانند.
5) باید این تضمین وجود داشته باشد که وقتی پروسه ای در ناحیه ی بحرانی دچار مشکل شد، پروسه های دیگر بتوانند با ان منبع کار کنند.
6) دو پروسه در یک زمان محدود می توانند داخل بخش بحرانی قرار گیرند.
پروتکل هایی که پروسه ها باید رعایت کنند:
1) مذاکره
2) بخش بحرانی
3) اعلام

مذاکره:

در مذاکره پروسه ها فقط یک پروسه برای دریافت منبع برنده می شود و Winner می شود و می تواند وارد بخش بحرانی شود.

بخش بحرانی یا Critical Selection :

پروسه ای وارد بخش بحرانی شد ،پروسه های دیگر بر روی ان تاثیر نگذارند.

اعلام:

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

جلسه ششم:

رویکردهای نرم افزاری انحصار متقابل:

گام اول :

در گام اول دو پروسه را در نظر می گیریم.پروسه ی P0 و P1 که این دو منبع در رقابتی که می کنند فقط یکی می تواند وارد بخش بحرانی شود.پروسه ی دوم در این حالت به طور متناوب به بخش بحرانی سرکشی می کند تا اگر پروسه ای در حال اجرا نباشد وارد بخش بحرانی شود.مشکل این حالت این است که پروسه ی P1 پشت سر هم به بخش بحرانی سرکشی می کند و این حالت وقت CPU و خود CPU را اشغال می کند.

گام دوم :

مشکل بخش بحرانی حالت اول را ندارد.در حالت دوم وقت CPU به هدر نمی رود.هر پروسه در بخش غیربحرانی خود باقی می ماند تا پروسه دیگر وضعیت های خودش را تغییر دهد.مشکل این گام دوم این است که پروسه ی اول زمانی که Flag های پروسه ی دوم را چک می کند و می فهمد که در بخش بحرانی نیست،برای ورود به ناحیه بحرانی Flag های خودش را تغییر می دهد.این حالت انحصار متقابل را تضمین می کند . ولی مشکل این حالت این است که پروسه ی دوم قبل از اینکه وضعیت خودش را تغییر دهد ،پروسه ی اول نیز این وضعیت را تغییر می دهد.پروسه ی اول درخواست منبعی را دارد که در اختیار پروسه ی دوم است و پروسه ی دوم درخواست منبعی را دارد که در اختیار پروسه ی اول است.این حالت باعث وقوع بن بست می شود.

گام سوم :

در این گام دو پروسه ی مجزا قسمت های مختلفی را برای انتظار دارند.به این حالت که اگر پروسه ی دوم امد ودید که پروسه ی اول بیش از اندازه در ناحیه ی بحرانی خود باقی مانده است،وضعیت های بخش بحرانی را به نفع خودش تغییر می دهد.باعث می شود پروسه ی اول Terminate شود و خودش وارد بخش بحرانی شود.

گام چهارم :

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

semafor :

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

تابع Wait :

زمانی استفاده می شود که منبعی به صورت ازاد وجود ندارد و پروسه نیاز به منبع دارد.منبع هم اشغال است.تابع Signal که همان عمل اعلان را پیاده سازی می کند ،زمانی که پروسه ای منبعی را ازاد می کند با Signal یک علامت می دهد و این علامت مشخص می کند که منبع ازاد شد.
درسمافور عمومی به این شکل است که یک تعداد منبع به عنوان منابع ازاد وجود دارد.پروسه برای به دست اوردن منبع درخواست خود را به سیستم عامل اعلام می کند و سیستم نیز یک منبع از منابع ازاد را به پروسه اختصاص می دهد.این تا زمانی ادامه پیدا می کند که منابع ازاد موجود به اتمام برسد و پروسه های بعدی برای به دستگیری منبع باید در انتظار بمانند.
زمانی که پروسه منبع را ازاد می کند یک منبع از منابع اشغال را کم می کند و یک منبع به منابع ازاد اضافه می کند.

جلسه هفتم:

مدیریت حافظه:

تخصیص قسمت های فیزیکی حافظه به قسمت های منطقی پروسه یا به طور کلی تعیین مکانیزم هایی مشخص برای تخصیص حافظه ی فیزیکی به بخش منطقی پروسه ها.
معیارهای مختلفی برای محک زدن حافظه وجود دارد:
1) پیچیدگی زمانی
2) اتلاف حافظه
3) افزونگی داده ها هنگام تبدیل ادرس های مجازی به نسبی و نسبی به فیزیکی
دو بحث اساسی برای هر مکانیزم وجود دارد:
1) محافظت ( Protection ) و امنیت( Security )
2) Sharing یا اشتراک داده ها
که این دو نقیض همدیگر هستند.
مکانیزم هایی که ما در مورد انها بحث می کنیم، همه مبتنی بر تخصیص یکپارچه ی حافظه به پروسه یا انتقال یکپارچه ی پروسه به حافظه است.یعنی اینکه پروسه به صورت چندتکه ای در حافظه قرار نمی گیرد و قسمت منطقی پروسه یکجا در حافظه قرار می گیرد.
مکانیزم ها یا شمای مدیریت حافظه ای باید وجود داشته باشد که اعمال پروسه مورد بررسی قرار گیرد:

الف) Single Monitor Memory Management And Single Monitor Process :

یک شمای مدیریت حافظه است که در ان سیستم عامل در بالای حافظه قرار می گیرد و از قسمتی از حافظه پروسه به حافظه وارد می شود و سیستم عامل ناظر رفت و امد پروسه هایی است که یکجا در حافظه قرار می گیرد.در این شما پیچیدگی زمانی نداریم.سرعت بالا است.چون فقط یک پروسه اجرا می شود. Multi Program نداریم.افزونگی داده ها در تبدیل ادرس وجود ندارد.اتلاف حافظه وجود دارد.به علت اینکه ممکن است یک پروسه که 1KB است ،همانند پروسه ای که 150KB است به ان حافظه تخصیص یابد.

ب) پارتیشن بندی( Partitioning ) :

یعنی تقسیم بندی حافظه به چند قسمت و تخصیص هر قسمت به قسمت های منطقی پروسه که به دو صورت می تواند انجام گیرد:
1) پارتیشن بندی پویا
2 ) پارتیشن بندی ایستا
پارتیشن بندی ایستا:در این پارتیشن بندی در ابتدا حافظه به چند قسمت تقسیم می شود.اندازه ی پارتیشن ها یکسان نیست و بزرگترین پارتیشن به اندازه ی بزرگترین پروسه ای است که قرار است در حافظه مقیم شود.

Partition Description Table :

این پارتیشن سه فیلد دارد:

1) Base :

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

2) Size :

مشخص می کند اندازه ی پارتیشن چقدر است.

3) Allocate & Free :

مشخص می کند این پارتیشن تخصیص یافته است یا خیر؟

Internal Fragmentation :

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

1) First Fit & Next Fit :

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

2) Best Fit :

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

3) Worst Fit :

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

Partition Static Model :

پروسه ای که می خواهد وارد حافظه شود در ابتدا اندازه ی پروسه با اندازه ی Limit Register مقایسه می شود. اگر اندازه ی پروسه کوچکتر از Limit Register بود با ادرس شروع پارتیشن جمع می شود و وارد حافظه می شود.

به اشتراک گذاری در مدلStatic ) Sharing Static Model) :

زیاد از اشتراک گذاری حمایت نمی شود . در این روش یا کل پارتیشن به اشتراک گذارده می شود یا بخشی از پارتیشن با تمهیداتی کد و داده را بین پروسه هایی که همکار هستند به اشتراک می گذارد.
1) ادرس Object هایی که به اشتراک گذارده می شود ،برای سیستم عامل تعریف می شود.
2) تهیه ی چند کپی از داده ها و کدهای به اشتراک گذاری شده جهت اطمینان از صحت انها.
3) پارتیشن بین همه ی پروسه ها به اشتراک گذارده می شود.
پارتیشن های مشترک به اشتراک گذارده می شود . حسن این کار این است که افزونگی داده ها نداشته باشیم.
ادامه دارد ......
ارسال مقاله توسط عضو محترم سایت با نام کاربری : PSTdinco
/س