در هر وقفه در سيستم عامل ساعت, سیستم عامل اجرا میشود تا تصمیم بگیرد که آیا به پروسس در حال اجرا اجازه ادامه کار را بدهد یا اینکه چون پروسس به اندازه کافی از زمان CPU استفاده کرده آن را معلق نماید تا CPU به پروسس دیگری تخصیص داده شود. فرکانس این وقفه در سيستم عاملهای ساعت معمولا بین 50تا60 بار در ثانیه است . این نوع زمانبندی که در آن پس از تمام شدن برش زمانی معین , CPU از گرفته میشود زمانبندی غیر انحصاری نام دارد.
اولویت
اولویتها میتوانند بصورت اتوماتیک توسط سیستم نسبت داده شوند و یا از خارج سیستم تعیین گردند, مثلاً ممکن است یک کاربر کار فوری داشته
باشدو حاضر باشد به خاطر بدست آوردن سرویس بالاتر هزینه بیشتری بپردازد , یعنی اولویت را بخرد .
مثلا ً ممکن است در آغاز یک برنامه اولویت پائینی داشته باشد ولی به تدریج اولویت آن بهبود یابد.
معیار های زمانبندی در سیستم عامل
1. عدالت (fairness) یعنی اطمینان از اینکه هر پروسس سهم عادلانه و منصفانهای از CPU را دریافت کند.
2. کارایی یا بهره وری (utilization- Efficiency) CPU یعنی اینکه CPU در تمام زمانها (حتی الامکان) مشغول باشد
3. زمان پاسخ (Response Time) یعنی به حداقل رساندن زمان پاسخ برای فرمانهای محاورهای کاربر. این زمان معمولاً با سرعت ابزار خروجی محدود میشود.
4. زمان برگشت (یا گردش کار Turnaround) یعنی به حداقل رساندن زمانی که کاربران دستهای باید منتظر بمانند تا خروجی آنها پدید آید . فاصله زمانی از لحظه تحویل کار تا لحظه تکمیل کار را زمان برگشت مینامند ولی زمان پاسخ مدت زمانی است که از صدور یک تقاضا تا تولید اولین پاسخ آن طول میکشد (نه زمان خروجی کل برنامه)
زمان بارگذاری در حافظه +زمان عملیات I/O +زمان اجراء+ زمان انتظاردر صف آماده = زمان گردش کار
5. توان عملیاتی یا گذردهی (throughput) به تعداد پردازشهایی که در واحد زمان تکمیل میشوند توان عملیاتی میگویند. الگوریتم زمانبندی باید به گونهای باشد که این معیار را افزایش دهد .
6. زمان انتظار (waiting time) الگوریتم زمانبندی CPU, بر میزان زمان اجرای پردازش یا اعمال I/O اثر نمیکند, بلکه فقط در زمان صرف شده جهت انتظار در صف آماده اثر میگذارد. زمان انتظار , مجموع پریودهای زمانی صرف شده در صف آماده میباشد.
زمانبندی صفهای چند گانه Multiple queues
هنگامی که بتوان فرآیندها را به سادگی به دستههای متفاوت طبقه بندی کرد از این روش استفاده میگردد.
در الگوریتم صفهای چندگانه, صف آماده, به صف های جداگانه مختلفی تجزیه میشود و هر پردازش وارد یک صف میگردد. اولویت صفها با هم فرق داشته و هر صفی الگوریتم زمانبندی خود را دارد
ساده ترین الگوریتم زمانبندی CPU ,الگوریتم اول آمده, اول سرویس شده (first come- first served =FCFS) میباشد . گاهی اوقات به این روش (first In First Out)FIFO نیز میگویند. در این روش هر پردازش در سیستم عاملی که اولین در خواست CPU را صادر کند , اولین پروسسی خواهد بود که آن را به دست میآورد .
از این روش در سیستمهای اشتراک زمانی استفاده شده تا زمانهای پاسخ برای کاربران محاورهای بصورت مناسب گارانتی شود.
حد پایین برش زمانی توسط دو عامل تعیین میشود یکی اینکه باید این برش خیلی بزرگتر از زمان تعویض متن باشد مثلاً هزاران برابر.
دیگر آنکه مقدار برش زمانی بایستی کمی بزرگتر از زمان لازم برای یک فعل و انفعال نوعی باشد چرا که در غیر اینصورت هر کار کوچکی نیاز به چندین برش زمانی خواهد داشت و کارایی سیستم به علت تعویض متنهای متعدد کم میشود.
در الگوریتم (Shortest Job First) که روشی انحصاری است CPU به پردازش داده میشود که کوچکترین انفجار محاسباتی بعدی را دارد.
البته اصطلاح مناسبتر , «کوتاهترین انفجار محاسباتی بعدی»میباشد. زیرا این زمانبندی بر اساس طول مدت انفجار CPU بعدی عمل میکند و نه بر اساس طول کل پردازش در سیستم عامل . اگر دو پردازش در سیستم عامل مدت انفجار محاسباتی یکسانی داشته باشد براساس FCFS زمانبندی میشوند. این الگوریتم میتواند انحصاری و غیر انحصاری باشد.
این الگوریتم مخصوصاً برای کارهای دستهای که از قبل زمان اجرای آن کارها , مشخص و معین باشد به کار میرود .
مهمترین مشکل در SJF آگاهی از طول درخواست بعدی CPU میباشد. هیچ راهی که طول انفجار محاسباتی بعدی را برای ما مشخص سازد وجود ندارد.
لذا در صورت لزوم مجبوریم آن را پیش بینی کنیم . یعنی انتظار داشته باشیم که طول انفجار بعدی خیلی شبیه طول انفجارهای قبلی باشد.
بالا ترین نسبت پاسخ(HRRN)
زمانبندی Highest Response Ratio Next) HRRN) نوعی زمانبندی انحصاری است که بعضی از مشکلات SJF را برطرف میسازد. در SJF نظر افراطی خوبی نسبت به کارهای کوتاه و برعکس نظر افراطی بدی نسبت به کارهای طولانی وجود دارد به طوری که ممکن است مشکل قحطی زدگی رخ دهد. در این زمانبندی اولویت ها دینامیک است.
کارهای کوتاهتر اولویت بیشتری داشته و زودتر اجراء میشوند. کارهای طولانی نیز که مدت زیادی در صف انتظار بوده اند اولیت بیشتری کسب کرده وبالاخره در یک زمان معین اجراء میشوند. بدین ترتیب مشکل قحطی زدگی برطرف میشود
بلا درنگReal time) )
در سیستم بلادرنگ سخت , پردازش در سیستم عامل ها میبایست در یک زمان تخمین شده اجراء و اتمام شوند., مانند سیستم کنترل موشک . چنین تضمینی در یک سیستم با حافظه ثانویه یا حافظه مجازی غیر ممکن است . در سیستم بلادرنگ نرم (مانند پخش موسیقی) زمان پاسخگویی به پردازش در سیستم عامل مهم است ولی مانند بلادرنگ سخت , حیاتی نیست .
• الگوریتم نرخ یکنواخت (Rate monotonic) : در این الگوریتم به هر پردازش در سیستم عامل اولویتی متناسب با فرکانس رخداد آن واقعه نسبت داده میشود. مثلاً به پردازشی که هر20 میلی ثانیه تکرار میشود, اولویت 50 و به پردازشی که هر 100 میلی ثانیه تکرار میشود, اولیت 10 داده میشود. این الگوریتم از نوع غیرانحصاری است . میتوان اثبات کرد که این الگوریتم بهینه است.
• الگوریتم ابتدا زودترین مهلت (Earliest deadline first) در این الگوریتم پردازش در سیستم عاملی ابتدا اجراء میشود که فرصتش از همه کمتر است یعنی نزدیکترین مهلت را دارد . این مهلت برای وقایع متناوب برابر زمان رخداد واقعه بعدی میباشد.
• الگوریتم کمترین سستی (least laxity) زمان سستی یک پردازش در سیستم عامل زمانی است که میتواند آماده باقی مانده و اجراء نشود. مثلاً اگر یک پردازش در سیستم عامل به 200 میلی ثانیه وقت CPU احتیاج داشته باشد. و250 میلی ثانیه نیز مهلت داشته باشد که کارش را تمام کند, زمان سستی او برابر 250-200=50 میلی ثانیه میباشد. در این الگوریتم پردازشی ابتدا اجراء میگردد که کوچکترین زمان سستی را دارد.
زمانبندی LPT
در زمانبندی (Longest Processing Time) هر گاه که پردازندهای آزاد میگردد, از بین کارهای باقی مانده طولانیترین کار را برای اجرا انتخاب میکند. هرچند که این الگوریتم بهینه نیست ولی غالباً منحصر به زمانبندیهایی با طول معقول میشود.
نظرات شما عزیزان: