بخشی از پاورپوینت
اسلاید 1 :
آموزش Operating system(سيستم عامل)با استفاده از:امکانات اسلاید های کامپیوتری ( نرم افزار 2003 PowerPoint) بخش (زمان بندی پروسسها Process Scheduling )
اسلاید 2 :
بنام خداوند بخشنده ومهربان
مقدمه
همان طور که می دانید درس سیستم عامل یکی از دروس اصلی وتخصصی رشته کامپیوتر در مقطع کاردانی وکارشناسی می باشد وشامل بحث های مختلفی مثل مدیریت پردازش ها ،مدیریت ذخیره ، مدیریت سیستم های I/O است.
اینجانب باتوجه به علاقه ای که به مباحث (زمان بندی پروسسها Process Scheduling ) از بخش مدیریت پردازش ها داشتم وهمچنین تجاربی که در تدریس این مباحث در کلاسهای کنکور (کاردانی به کارشناسی ) بدست آوردم اقدام به طراحی وتالیف این فایل آموزشی (جزوه حاضر) بصورت ارائه با اسلایدهای کامپیوتری نمودم تا مطالب بصورت نمادهای گرافیگی بسرعت وراحت مورد استفاده دانشجویان وعلاقمندان قرار گیرد امید که مقبول افتد.
اسلاید 3 :
زمان بندی پروسسها Process Scheduling
Scheduler (زمانبند) : بخشی از سیستم عامل است که تصمیم می گیرد از بین پروسسهای آماده اجرا CPU به کدام یک داده شود . برا ی این تصمیم گیری از الگوریتمی استفاده می شود که الگوریتم زمان بندی (ُScheduling Algorithm) نامیده می شود .
ملاکهایی که یک الگوریتم زمانبندی خوب باید دارا باشد عبارت است از :
1- عدالت ((Fairness : هر پروسس سهم عادلانه ای از CPU را دریافت نماید .
2- کارایی (ٍٍٍٍEfficiency) : CPU بیکار نماند و وقتی پروسس امکان جلو رفتن ندارد CPU به پروسس دیگری داده شود .
3- زمان پاسخ (Response Time) : زمان پاسخ ، زمان پاسخ به فرمانهای Interactive کاربر است .
4- حداقل بودن زمان بازگشت (Turnaround Time) : زمان بازگشت برای یک کار Batch طول زمان از لحظه ورود آن به سیستم تا لحظه پایان یافتن (کامل شدن) آن می باشد .
5- حداکثر شدن Throughput: تعداد کارهایی است که در واحد زمان انجام می شود .
زمانبندی
زمانبندی انحصاری (Nonpreemptive) (اجرا تا تکمیل)
زمانبندی غیر انحصاری (Preemptive)
اسلاید 4 :
زمانبندی Round Robin :
یکی از رایج ترین و ساده ترین الگوریتمهای زمانبندی است . پیاده سازی آن بسیار ساده است . کافی است یک لیستی از پروسسهای آماده اجرا نگهداری شود .
به هر پروسس یک Quantum (کوانتم) یا Time-slice (برش زمانی) CPU داده می شود . اگر پروسس در پایان کوانتم هنوز خاتمه نیافته باشد ، CPU از آن گرفته می شود و به پروسس بعدی در صف داده می شود .
اندازه Quantum چقدر باشد ؟
فرض کنید Context switch ، 5 میلی ثانیه طول بکشد .
اگر طول کوانتم 20 میلی ثانیه باشد
20% = (20 + 5) / 5 = میزان اتلاف
اگر طول کوانتم را 500 میلی ثانیه در نظر بگیریم
1% > 505/5 =( 5 + 500 )/ 5 = میزان اتلاف
اغلب کوانتم برابر 100 میلی ثانیه را مناسب می دانند .
اسلاید 5 :
پس از گذشت یک : quantum
پس از گذشت دو : quantum
زمانبندی اولویت (Priority Scheduling Algorithm) :
در زمانبندی Round Robin همه پروسسها دارای اولویت یکسان بودند .
نیاز به اعمال فاکتورهای خارجی منجر به زمانبندی دارای اولویت می شود .
اسلاید 6 :
اولویت می تواند به صورت ایستا وپویا نسبت داده شود .
مثال : درکامپیوترهای نظامی
مثال : درسایتهای کامپیوتری کارتهای طلایی نقره ای وبرنز و..
اولویتها میتوانند بطور پویا تعیین شوند مثلا به پروسسهای I/O limited اولویت f/ 1 نسبت دهیم که f کسری ازآخرین کوانتم است که پروسس cpu رادر دست داشته .
اگر کوانتم 100میلی ثانیه باشد وپروسس p1 ، 20 میلی ثانیه ا ز cpu استفاده کرده باشد
f = 20/100
5 = f/1= اولویت p1
اگرکوانتم 100میلی ثانیه باشد و پروسسp2 ، 2میلی ثانیه از CPUاستفاده کرده باشد :
f = 2/100
= 1/f =50 اولویت p2
اسلاید 7 :
میتوان از کلاسهای اولویت (priority classes) استفاده کرد :
دراین روش پروسسهادرکلاسهای اولویت قرارداده میشوند . زمانبندی بین کلاسها اولویت داراست ولی زمانبندی درداخل هر کلاس Round Robin است .
Queue Headers
Priority 4
Priority 3
Priority 2
Priority 1
Runable Processes
(Highest priority)
(Lowest priority)
اسلاید 8 :
زمانبندی صفحه های چندگانه (multiple queues)
CTSSدارای زمانبندی اولویت دار بود ولی سرعت تعویض پروسس در آن کم بود .
طراحان CTSS متوجه شدند اگر به پروسسهای CPU-Limited به جای اختصاص دادن مکرر کوانتم های کوچک کوانتم های طولانی تر داده شود Throughput سیستم بالاتر می رود .
از کلاسهای اولویت استفاده کردند .
صف پروسسهایی که 1 کوانتم اجرا می شوند
صف پروسسهایی که 2 کوانتم اجرا می شوند
صف پروسسهایی که 4 کوانتم اجرا می شوند
صف پروسسهایی که 8 کوانتم اجرا می شوند
صف پروسسهایی که 16 کوانتم اجرا می شوند
.
بالاترین اولویت
کاهش اولویت
.
اسلاید 9 :
اگر پروسس از تمامی کوانتم های خود در یک کلاس بطور کامل استفاده کند و هنوز کامل نشده باشد در کلاس پایین تر قرار می گیرد .
در سیستم XDS 940 : ازکلاسهای اولویت مطابق شکل زیر استفاده می شود .
ترمینال
I/O
کوانتم های کوتاه
کوانتم های طولانی
اسلاید 10 :
زمانبندی ابتدا کوتاهترین کار Shortest Job First (SJF) :
این الگوریتم مخصوص کارهای دسته ای (Batch) می باشد.
وقتی چند کار Batch با اولویت یکسان وجود دارد . این الگوریتم می گوید CPU باید به پروسسی داده شود که Turnaround time کوچکتر ی دارد (یعنی آن پروسسی که زودتر خاتمه می یابد.)
(a)
Turnaround Time A: 8ثانیه
Turnaround Time B: 12 ثانیه
Turnaround Time C: 16 ثانیه
Turnaround Time D: 20 ثانیه
8+12+16+20
14 ثانیه
8 4 4 4
اسلاید 11 :
(b)
Turnaround Time D : 4 ثانیه
Turnaround Time C : 8 ثانیه
Turnaround Time B:12 ثانیه
Turnaround Time A:20 ثانیه
4+8+12+20
11 ثانیه
4 4 4 8
اسلاید 12 :
پروسس
زمان
Aaa
B ba+b
Cca+b+c
Dda+b+c+d
4a+3b+2c+d
آن پروسسی که زمان بازگشت کوتاهتری دارد((Shortest Job) باید ابتدا اجرا شود
(Shortest Job First)
اسلاید 13 :
زمانبندی تضمین شده (Guaranteed Scheduling Algorithm )
تضمین کنیم که به پروسس سهم عادلانه ای از وقت CPU را اختصاص دهیم .
اگر n پروسس در حال کار باشند باید هر یک بتوانند 1/n از وقت Cpu را در اختیار گیرند .
زمان نامی پروسس = n/ زمان طی شده
زمان واقعی استفاده شده را سیستم عامل ثبت کرده است .
نسبت زمان واقعا استفاده شده به زمان نامی را برای هر پروسس محاسبه می کند :
نسبت 0.5 یعنی پروسس نصف سهم واقعی خود را دریافت کرده و نسبت دو به این معنی است که پروسس دو برابر سهم واقعی خود را به دست آورده است .
طبق این الگوریتم cpu باید به پروسسی داده شود که از میان پروسسهای موجود کمترین سهم را داشته باشد .
1.5 0.80 0.75 0.5
1.75 1.2 0.75 0.70 0.6
1.45 1.05 0.72 0.65 0.7
اسلاید 14 :
زمانبندی بخت آزمایی (قرعه کشی ) (Lottery Scheduling )
به پروسسها بلیطهای بخت آزمایی بدهیم هر بار که الگوریتم زمانبندی اجرا می شود یک بلیط را به طور تصادفی برنده انتخاب کند .
پروسسی که این بلیط را دارد cpu به آن داده شود .
جورج اورول (George Orwell) می گوید “ همه پروسسها مساویند ولی برخی از پروسسها مساویترند " باید به پروسسهای مهمتر بلیطهای بیشتری بدهیم تا شانس برنده شدن آنها افزایش یابد .
فرض کنید 100 بلیط وجود دارد پروسس A 20 بلیط در اختیار دارد و پروسس B 80 بلیط در اختیار دارد شانس A برای برنده شدن 20% و شانسB 80% است .
پروسسی که کسر f از بلیطها را در اختیار دارد در قرعه کشی کسر f از زمان CPU را نیز به دست خواهد آورد .
اسلاید 15 :
زمانبندی بلادرنگ : Real-time Scheduling
سیستم بلادرنگ (Real time) سیستمی است که در آن زمان پاسخگویی به وقایع خیلی اهمیت دارد. به عنوان مثال یک نیروگاه اتمی را در نطر بگیرید ، برخی کمیتها باید تحت کنترل دقیق باشند مثلا در اثر پرتاپ نوترونها به اتمها ، نوترونهای جدیدی آزاد می شوند و نوترونهای آزاد شده به اتمهای دیگر برخورد می کند و نوترونهای جدید آزاد میشود و بهمین ترتیب . اگر تعداد نوترونهای آزاد شده از یک حدی بیشتر باشد انفجار نوترونی اتفاق می افتد.پس غلظت نوترونها باید تحت کنترل دقیق باشد . حتی یک ثانیه بعد یا یک دقیقه یا یک ساعت بعد از انفجار اگر پاسخ دهد ، هیچ ارزشی ندارد.
سیستم مانیتورینگ بخش I.C.U یک بیمارستان یک مثال دیگر از سیستم Rea-time است.
سیستمهای Real-time به دو دسته تقسیم می شوند :
بلادرنگ سخت Hard Real-time
بلادرنگ نرم Soft Real-time
اسلاید 16 :
بلادرنگ سخت (Hard Real-time) سیستمی است که در یک مهلت زمانی یا پاسخ میدهد یا هیچ ، مانند مثالهای فوق.
سیستم بلادرنگ نرم سیستمی است که در بعضی از مواقع آماده نشدن پاسخ در مهلت زمانی تعیین شده قابل تحمل است مانند سیستم پخش یک قطعه موسیقی از روی CD یا پخش یک Video-Clip از روی یک VCD .
- در یک سیستم بلادرنگ وقایعی رخ می دهد ؛ برنامه به تعدادی پروسس تقسیم می شود و هر پروسس برای پاسخگویی به یک نوع واقعه است.
وقایع در یک سیستم بلادرنگ به دو دسته تقسیم می شوند:
وقایع
متناوب Periodic
غیر متناوب Aperiodic
اسلاید 17 :
وقایع متناوب با دوره تناوب مشخص تکرار می شوند .
وقایع غیر متناوب به صورت تصادفی رخ می دهند ( زمان رخ داد مشخصی ندارند)
از آنجا که پردارش مربوط به هر واقعه بخشی از زمان CPU را اشغال می کند ، ممکن است پاسخ کلیه وقایع در مهلت مشخص امکان پذیر نباشد . مخصوصا اگر قدرت پردازش بالا نباشد . فرض کنید وقایع متناوب عبارتند از :
E1
E2
.
.
.
Em
E مخفف Event است .
اگر فرض کنیم process مربوط به واقعه i ، Ciثانیه وقت CPU را اشغال می کند؛ آنگاه :
CiFi = زمان اشغال شده در ثانیه از وقت CPU برای واقعه i
اسلاید 18 :
و کل زمان صرف شده از CPU در یک ثانیه برای پاسخگویی به وقایع عبارتست از :
CiFi = C1F1+C2F2+…..CmFm
i=1
I =
بدیهی است اگر مقدار I کوچکتر یا مساوی یک ثانیه باشد یعنی قدرت پردازش سیستم برای پلسخگویی به کلیه وقایع کافی است . لذا شرط اینکه سیستم قادر به پاسخگویی به کلیه وقایع باشد این است که
i=1
i=1
CiFi <= 1 یا
Ci /Pi <=1
در این صورت می گویند سیستم قابل زمانبندی (Schedulable)است .
)از زمان Process Switch صرفنظر شده .)
اسلاید 19 :
مثال : فرض کنید یک سیستم بلادرنگ از سه واقعه متناوب با دوره های تناوب 100، 200 ،500 میلی ثانیه
تشکیل شده است .اگر هر واقعه به ترتیب به 50 و 30و100 میلی ثانیه زمان CPU نیاز داشته باشد،
(الف) آیا سیستم فایل زمانبندی (Schedulable) است ؟
Ci / Pi = c1/p1 + c2/P2 +C3/P3=50/100+30/200+100/500= 0.5+0.15+0.2=0.85<=1
i=1
لذا قابل زمانبندی است
(ب) اگر واقعه چهارمی با دوره تناوب 1 ثانیه اضافه شود آیا سیستم هنوز قابل زمانبندی است؟
Ci / Pi = c1/p1 +..+C4/P4=0.85 + C4/1<=1
i=1
C4<=0.15ثانیه
C4<=150ms
لذا فقط در صورتیکه Process مربوطه به P4 حداکثر به 150 میلی ثانیه زمان CPU نیاز داشته باشد ، سیستم قابل زمانبندی است.
اسلاید 20 :
برخی از الگوریتمهای زمانبندی بلادرنگ :
1- الگوریتم نرخ یکنواخت (Rate Monotonic Algorithm) :
یک الگوریتم دارای اولویت است که به هر پروسس ، اولویتی متناسب با فرکانس آن رخداد اختصاص داده شود . به عنوان مثال اگر Process 1 ، دارای دوره تناوب 20 میلی ثانیه است و به آن اولویت 50 داده می شود و به Process2 ، دارای دوره تناوب 100 میلی ثانیه است اولویت 10 داده می شود
