دانلود تحقیق سیستم عامل

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

این تخصیص معمولاً مسأله پیچیده ای است که توسط سیستم عامل مدیریت می شود.

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

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

شکل 10-1 ) سطوح زمانبندی
• زمانبندی سطح بالا - این زمانبندی گاهی به عنوان زمانبندی کار نامیده می شود و تعیین می کند که کدام کارها بطور فعال منابع سیستم را در اختیار می گیرد و تکمیل می شود.

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

وقتی کاری اجازه ورود پیدا کرد، یکی از فرایندهای شناخته شده سیستم خواهد شد.
• زمانبندی سطح میانی – این زمانبندی تعیین می کند که کدام فرایندها اجازه خواهد یافت در اختیار cpu قرار بگیرد.

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

بنابراین زمانبندی میانی در واقع به عنوان بافر بین ورود کارها به سیستم و تخصیص cpu به این کارها عمل می کند.
• زمانبندی سطح پائین – این زمانبندی تعیین می کند که کدامیک از فرایندهای آماده در اختیار cpu قرار خواهد گرفت (اگر cpu قابل دسترس باشد) و بطور واقعی cpu را در اختیار این فرایند قرار می دهد (فرایند را به cpu می فرستد).

زمانبندی سطح پایین به وسیله ارسال کننده انجام می شود که در هر ثانیه چندین بار عمل می کند.

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

بسیاری از سیاستها هم برای زمانبندی کار و هم برای زمانبندی فرایند مفید است.
اهداف زمانبندی
هر زمانبندی می باید دارای شرایط زیر باشد:
• عادل باشد.

زمانبندی عادل است اگر با تمامی فرایندها بطور یکسان برخورد کند و هیچ فرایندی به مدت نامعین به تأخیر نیفتد.
• حداکثر توان عملیاتی را داشته باشد.

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

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

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

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

سرباری عموماً منابعی تلف شده تلقی می شود؛ اما بخشی از منابع واقعی سیستم که سرباری را به دنبال دارد، باعث بهبود کارآیی کلی سیستم می شود.
• استفاده از منابع سیستم را متعادل سازد.

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

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

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

در انواع دیگری از سیستمها، اغلب، مسائل اقتصادی استفاده مؤثر از منابع را ضروری می سازد.
• از تأخیر به مدت نامعین بپرهیزد.

در بسیاری از موارد، تأخیر به مدت نامعین به اندازه بن بست مشکل ساز است.

خودداری از تأخیر به مدت نامعین با افزایش اولویت فرایندهای منتظر (فرایندهایی که منتظر در اختیار گرفتن منابع هستند) امکانپذیر است.

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

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

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

اگر منبع انحصاری باشد، آنگاه زمانبندی باید رفتار بهتری (سرویس بهتری) با فرایند انجام دهد تا سریعاً منبع کلیدی را آزاد کند (این سرویس بهتر از حالتی است که فرایند مورد نظر، منبع کلیدی را در اختیار داشته باشد).
• سرویس بهتری به فرایندهایی ارائه کند که رفتار بهتری از خود نشان می دهد.

برای مثال آن دسته از فرایندهایی که میزان فراخوانی و جایگزینی صفحه کمتری دارد، سرویس بهتری دریافت کند.
• وقتی بار سیستم سنگین است، سطح سرویس دهی را برای همه برنامه ها بطور مناسب کاهش دهد.

برای مثال در حالتی که بار پردازشی سیستم زیاد است از پذیرش کار جدید خودداری کند.
بسیاری از این اهداف با یکدیگر در تضاد هستند و به همین دلیل طراحی زمانبندی عملی مسأله پیچیده ای است.
معیارهای زمانبندی
برای تحقق اهداف زمانبندی می باید معیارهای زیر را در نظر گرفت:
• ورودی / خروجی گرا بودن فرایند – وقتی فرایندی cpu را در اختیار می گیرد، آیا قبل از اعلام درخواست برای هر عمل cpu , I/O را به مدت محدود استفاده می کند؟

cpu گرا بودن فرایند – وقتی فرایندی cpu را در اختیار می گیرد، آیا تمایل دارد قبل از پایان زمان کوانتوم (برهه زمانی مشخص برای اجرای فرایند) آن را در اختیار داشته باشد؟

دسته ای یا محاوره ای بودن فرایند – کاربران محاوره ای عموماً سؤالات کوچک به سیستم می فرستند و انتظار دارند سرویس فوری از سیستم دریافت کنند.

تضمین زمان پاسخ خوب توسط سیستم از اهمیت بسیاری برخوردار است.

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

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

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

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

میزان تولید خطای صفحه (page fault) توسط فرایند – عموماً ، فرایندهایی که خطای صفحه کمتری تولید می کند مجموعه کاری (working set) خود را در حافظه اصلی زودتر تشکیل می دهد.

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

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

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

هر فرایند تاکنون چقدر زمان واقعی اجرا دریافت کرده است.

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

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

چقدر زمان برای تکمیل فرایند لازم است – زمان متوسط انتظار را می توان با اجرای فرایندهایی که برای تکمیل آنها زمان کمتری لازم است، کاهش داد.

متأسفانه کمتر می توان تشخیص داد که زمان باقیمانده برای تکمیل هر یک از فرایندها چقدر است.

زمانبندی انحصاری در مقابل غیرانحصاری زمانبندی را انحصاری گویند اگر نتوان cpu را از دست فرایند پس گرفت.

زمانبندی را غیر انحصاری گویند اگر بتوان cpu را از دست فرایند آزاد کرد.

زمانبندی غیرانحصاری در سیستمهایی که بر مبنای اولویت (priority) عمل می کند، بسیار مفید است.

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

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

انتخاب زمانبندی غیرانحصاری بدون هزینه نیست و بدیهی است که تعویض متن سرباری دارد.

برای اینکه زمانبندی غیرانحصاری بطور مؤثر اجرا شود فرایندهای بیشتری می باید در حافظه اصلی نگهداری شود تا عملیات تعویض متن با سرعت بیشتری انجام شود.

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

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

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

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

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

طراح باید آگاه باشد که هر روش پیشنهادی را قبل از پیاده سازی بطور دقیق ارزیابی کند.

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

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

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

سیستم عامل یک ساعت وقفه یا زمانسنج را تنظیم می کند تا بتواند در زمان مشخص (در آینده) وقفه ای تولید کند.

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

فرایند، کنترل پردازنده را در اختیار می گیرد تا زمانی که بطور ارادی آن را رها کند، یا ساعت (clock) ، وقفه ای را به وجود آورد و یا وقفه های دیگر، توجه آن را به خود جلب کند.

اگر فرایندی در حال اجرا باشد و ساعت (clock) ، وقفه ای ایجاد کند، این وقفه باعث اجرای سیستم عامل می شود.

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

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

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

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

آنها ممکن است کسب و یا خریداری شود؛ کاملاً ایستا و یا پویا باشد؛ بطور معقول (عقلانی) اختصاص یابد و یا تحت شرایطی که سیستم به تمایز بین فرایندها نیاز دارد بطور غیر معقول اختصاص یابد، لکن دقیقاً مشخص نیست که کدامیک از روشها از اهمیت بیشتری برخوردار است.

اولویتهای ایستا در مقابل پویا اولویتهای ایستا معمولاً عوض نمی شود.

پیاده سازی آنها راحت است و نسبتاً سرباری کمتری دارد.

روشهای اولویت پویا معمولاً تغییرپذیر است.

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

پیاده سازی الگوهای اولویت پویا پیچیده تر و سرباری آنها بیشتر است.

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

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

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

این پرداخت اضافی باعث می شود که منابع سیستم از سایر کاربران پس گرفته شود.

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

زمانبندی ضرب الاجل در زمانبندی ضرب الاجل، برنامه های زمانبندی شده باید در زمان مشخص به پایان برسد.

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

کاربر معمولاً تمایل دارد مبلغی را پرداخت کند تا مطمئن شود که سیستم، کارش را بموقع تکمیل می کند.

زمانبندی ضرب الاجل بنا به دلایل زیر پیچیده است: کاربر می باید نیازمندیهای دقیق برنامه را به منابع مورد نظر معین کند.

چنین اطلاعاتی البته کمتر در دسترس است.

سیستم باید بتواند برنامه ضرب الاجل را اجرا کند، بدون اینکه سرویس دهی به دیگران را مختل کند.

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

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

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

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

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

چنین تضادهایی می باید بطور دقیق توسط طراحان سیستمهای عامل مورد توجه قرار بگیرد.

زمانبندی FIFO این زمانبندی شاید یکی از ساده ترین روشهای زمانبندی باشد (شکل 10-2).

فرایندها براساس زمان ورودشان به سیستم در صف آماده (ready list) قرار می گیرد.

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

بنابراین روشی انحصاری برای زمانبندی است.

این روش در حالت عادی به عدالت عمل می کند، لکن در برخی موارد که برنامه های بزرگ معمولاً باعث انتظار برنامه های کوچک می شود غیرعادلانه عمل می کند.

زمانبندی FIFO برای سیستمهای محاوره ای مناسب نیست زیرا نمی تواند زمان پاسخ خوبی را تضمین کند.

شکل 10-2) زمانبندی FIFO روش FIFO در سیستمهای امروزی کمتر به عنوان الگوی اصلی برای زمانبندی به کار گرفته می شود، بلکه این روش معمولاً با الگوهای دیگر ادغام می شود؛ برای مثال، بسیاری از الگوهای زمانبندی فرایندها را بر مبنای اولویت برای پردازنده می فرستند، اما فرایندهای با اولویت یکسان براساس FIFO در اختیار پردازنده قرار می گیرد.

زمانبندی نوبت دوره ای در روش زمانبندی نوبت دوره ای (شکل 10-3) ، فرایندها به صورت FIFO برای پردازنده فرستاده می شود لکن برای هر فرایند مقدار محدودی از زمان پردازنده به نام برش زمانی اختصاص می یابد.

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

در این حالت فرایند آزاد شده مجدداً به انتهای صف برگردانده می شود.

شکل 10-3) زمانبندی نوبت دوره ای روش زمانبندی نوبت دوره ای در محیطهای اشتراک زمانی مؤثر عمل می کند به گونه ای که می تواند برای کاربران محاوره ای زمان پاسخ قابل قبولی را ضمانت کند.

سرباری روش غیر انحصاری توسط روش تعویض متن کارآ، و فراهم کردن حافظه اصلی کافی برای مقیم شدن فرایندها، پائین نگهداشته می شود.

اندازه برش زمانی تعیین اندازه برش زمانی برای عملکرد مؤثر هر سیستم کامپیوتری بسیار اساسی است.

آیا اندازه برش زمانی باید بزرگ باشد یا کوچک؟

اندازه آن ثابت باشد یا متغیر؟

آیا اندازه آن برای همه کاربران یکسان باشد یا برای هر کاربر بطور جداگانه محاسبه شود؟

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

چنانچه اندازه برش زمانی خیلی بزرگ باشد، هر فرایند زمان لازم و مورد نیاز را برای تکمیل شدن در اختیار می گیرد.

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

مقدار برش زمانی دقیقاً بین صفر و بینهایت چقدر باید باشد؟

تجربه زیر را در نظر بگیرید.

فرض کنید نشانه های شماره گیری دوّار از q=0 تا وجود دارد.

از کلید شماره صفر شروع می کنیم.

با چرخش کلید، برش زمانی سیستم تغییر می کند.

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

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

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

با چرخش کلید، اندازه برش زمانی بیشتر می شود و زمان پاسخ بهبود می یابد.

سرانجام با چرخش کلید نقطه ای فرا می رسد که در آن درصد اتلاف وقت پردازنده به اندازه کافی کم می شود و کاربران سرویس بهتری دریافت می کنند.

اما هنوز هم زمان پاسخ به اندازه کافی مطلوب نیست.

همانطور که کلید بیشتر چرخانده می شود، بهبود زمان پاسخ ادامه می یابد.

در یک نقطه، کاربران پاسخهای فوری از سیستم دریافت می کنند.

اما هنوز روشن نیست که اندازه برش زمانی مقدار بهینه باشد.

کلید سرانجام یک واحد به جلو چرخانده می شود و زمان پاسخ کاملاً بهبود می یابد، اما با چرخش بیشتر مجدداً زمان پاسخ کاهش می یابد.

با بزرگتر شدن مقدار کوانتوم، مقدار آن برای هر کاربر به منظور اجرا و تکمیل (با دریافت پردازنده) به اندازه کافی بزرگ می شود.

در این حالت روش زمانبندی به روش FIFO عمل می کند به گونه ای که فرایندهای بزرگ باعث انتظار بیشتر فرایندهای کوچک می شود و زمان متوسط انتظار به واسطه اجرا و تکمیل فرایندهای بزرگتر (قبل از تسلیم کردن cpu) افزایش می یابد.

در نظر بگیرید برای اندازه برش زمانی که زمان پاسخ خوبی را ارائه می کند مقدار بهینه ای فرض شده باشد.

این مقدار در واقع کسر کوچکی از یک ثانیه است.

دقیقاً این برش زمانی چه چیزی را ارائه می کند؟

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

وقتی هر فرایند محاوره ای شروع به اجرا می کند، بطور عادی تا زمان صدور درخواست یک عمل I/O CPU را مورد استفاده قرار می دهد.

وقتی درخواست I/O توسط فرایند صادر می شود CPU را رها می کند و به فرایند دیگر تحویل می دهد.

به دلیل بزرگ بودن مقدار برش زمانی از زمان اجرای فرایند تا صدور در خواست I/O (compute-until-I/O time) ، فرایندهای مورد نظر با بیشترین سرعت به اجرای خود ادامه می دهد.

هر زمان که فرایندی CPU را در اختیار می گیرد، زمان کافی برای اجرای آن تا صدور درخواست I/O وجود دارد.

این عمل سبب کاهش سرباری مربوط به تعویض متن، بهبود عملکرد I/O و سرعت نسبی زمان پاسخ می شود.

حال دقیقاً مقدار بهینه برش زمانی چیست؟

روشن است که مقدار آن از هر سیستم به سیستم دیگر و از هر فرایند به فرایند دیگر فرق می کند و نسبت به اینکه بار (load) سیستم چقدر باشد متفاوت است.

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

در محیطهای چند برنامگی به منظور تضمین زمان پاسخ قابل قبول برای کاربران محاوره ای، هنوز هم باید CPU بطور مرتب بین فرایندها سوئیچ کند.

زمانبندی SJF این روش به صورت انحصاری، زمانبندی فرایندها را انجام می دهد به گونه ای که فرایندی که به کمترین زمان برای اجرا و تکمیل نیاز دارد، CPU را در اختیار می گیرد.

روش SJF زمان متوسط انتظار را نسبت به روش FIFO کم می کند.

بیشتر طراحان عقیده دارند که فرایندهای کوچک می باید از سرویس بهتری برخوردار باشد، لکن توافق عمومی در این مورد وجود ندارد؛ بویژه زمانی که اولویت کارها را می باید لحاظ کرد.

روش SJF به گونه ای کار را برای سرویس دهی انتخاب می کند که مطمئن می شود کار انتخاب شده تکمیل می شود و بزودی سیستم را ترک خواهد کرد.

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

مسأله روشن در مورد روش SJF داشتن اطلاعات دقیق از مدت زمان اجرای کارهاست که این اطلاعات معمولاً در دسترس نیست.

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

در محیطهای تولیدی که معمولاً کارهای مشابه با قاعده مشخص اجرا می شود، تخمین قابل قبول از مدت زمان اجرای کارها امکان پذیر است، اما در محیطهای برنامه نویسی معمولاً کاربران کمتر از مدت زمان اجرای برنامه هایشان اطلاع دارند.

روش SJF مانند روش FIFO روشی انحصاری است و لذا برای محیطهای اشتراک زمانی مناسب نیست زیرا نمی تواند زمان پاسخ خوب را تضمین کند.

زمانبندی SRT روش SRT به صورت غیر انحصاری زمانبندی فرایندها را انجام می دهد و برای سیستمهای اشتراک زمانی مفید است.

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

در روش SJF ، وقتی کاری شروع به اجرا می کند به اجرای خود ادامه می دهد تا تکمیل شود.

در روش SRT ممکن است فرایند در حال اجرا توسط فرایندی که زمان باقی مانده اجرایش کمتر است متوقف شود.

این روش همچنین نیازمند آن است که برای عملکرد مؤثر و بهینه خود، آینده فرایندها را تخمین بزند.

سرباری SRT نسبت به SJF بیشتر است و باید زمان سپری شده برای سرویس دهی به فرایندها را نگهداری کند و بتواند بین فرایندها سوئیچ کند.

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

از جهت نظری، روش SRT حداقل زمان انتظار را برای فرایندها پیش بینی می کند، لکن به دلیل سرباری مربوط به تعویض متن، این احتمال مطرح است که روش SJF در برخی مواقع بهتر عمل می کند.

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

آیا در این حالت باید فرایند در حال اجرا متوقف شود؟

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

آیا این نوع عملکرد به عنوان ارزش برای SRT تلقی می شود؟

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

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

در اینجا هم روش SRT محض، تعویض متن را انجام می دهد، اما اگر سرباری تعویض متن از اختلاف زمانهای سرویس دو فرایند بیشتر باشد، آن عمل دقیقاً باعث کاهش کارآیی سیستم خواهد شد.

نکته اساسی این وضعیت این است که طراحان سیستمهای عامل می باید بطور دقیق سرباری روشهای مدیریت منابع را در مقابل مزایای آن ارزیابی کنند.

زمانبندی HRN این روش توسط برینچ هانسن برای اصلاح برخی از نقاط ضعف SJF طراحی شد بویژه برای برطرف کردن تعصب افراط آمیز در مقابل فرایندهای بزرگ و مساعدت افراط آمیز برای فرایندهای کوچک جدیدالورود.

HRN روش انحصاری است که در آن اولویت هر فرایند تابعی از زمان سرویس و زمان انتظار است.

وقتی یک بار CPU در اختیار فرایند قرار می گیرد، اجرا می شود تا به پایان برسد.

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

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

در هر حال باید توجه داشت که مجموع (زمان سرویس + زمان انتظار) ، زمان پاسخ سیستم به فرایند مورد نظر را معین می کند.

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

بدیهی است فرایندهای I/O – گرا ممکن است مقدار کمی از زمان CPU را قبل از درخواست عمل I/O استفاده کند.

از سوی دیگر فرایندهای CPU – گرا ممکن است در صورت قابل دسترس بودن پردازنده بر مبنای زمانبندی انحصاری ساعتها وقت CPU را استفاده کند.

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

به فرایندهای I/O – گرا مساعدت کند تا از دستگاه های I/O استفاده خوبی به عمل آید.

طبیعت و ویژگی هر فرایند را هر چه سریعتر تعیین کند تا بتواند بر مبنای آن زمانبندی کند.

صفهای بازخور چند سطحی (شکل 10-4) ساختاری را فراهم می کند که این اهداف را برآورده سازد.

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

اگر فرایند مورد نظر تکمیل شود و یا CPU را به دلیل انتظار برای عمل I/O ، شبکه صفها را ترک خواهد کرد.

حال اگر برش زمانی (کوانتوم) فرایند قبل از آزادسازی اختیاری CPU به پایان رسد، فرایند مورد نظر در انتهای صف سطح پایین تر جایگذاری می شود.

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

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

معمولاً در انتهای ساختار صفها، صفی به صورت نوبت دوره ای (round robin) وجود دارد که در آن فرایند مورد نظر به صورت دوره ای به اجرای خود تا تکمیل شدن ادامه می دهد.

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

در این ساختار، فرایندهای موجود در صفهای بالاتر اولویت بیشتری دارد و به همین دلیل فرایندهای موجود در صفوف پایین تر (با افزایش مقدار برش زمانی خود) نمی تواند بطور مکرر CPU را در اختیار بگیرد.

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

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

این روش باید به گونه ای عمل کند که به فرایندهای I/O – گرا به منظور استفاده بهتر از دستگاه های I/O و نیز تأمین زمان پاسخ مقبول برای کاربران محاوره ای مساعدت بیشتری کند.

در واقع، این مساعدت به دلیل اولویت بسیار فرایندهای I/O – گرا در موقع ورود به شبکه انجام خواهد شد و CPU بطور سریع در اختیار آنها قرار خواهد گرفت.

مقدار برش زمانی در اولین صف به اندازه کافی بزرگ انتخاب می شود تا تعداد زیادی از فرایندهای I/O – گرا قبل از انقضای اولین برش زمانی بتواند تقاضای I/O را صادر کند.

زمانی که فرایندی درخواست I/O می کند، شبکه را ترک می کند و رفتار مناسبی را به شکل مطلوب دریافت خواهد کرد.

حال در نظر بگیرید که یک فرایند CPU – گرا به مقدار زیادی از زمان CPU احتیاج دارد.

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

حال اولویت فرایند مورد نظر نسبت به فرایندهای جدیدی که وارد می شود (بویژه فرایندهای I/O- گرا) پایین تر می رود.

شکل 10-4) صفهای بازخور چند سطحی سرانجام فرایند CPU – گرا پردازنده را در اختیار می گیرد، این بار با برش زمانی بزرگتر از صف بالاتر، و مجدداً برش زمانی کامل خود را استفاده کرده و آنگاه در انتهای صف پایین تر جایگذاری می شود.

فرایند مورد نظر حرکت به صفهای پایین تر را ادامه می دهد؛ زمان بیشتری بین برشهای زمانی به انتظار می نشیند و هر بار برش زمانی کامل را (با به دست گرفتن CPU) استفاده می کند.

سرانجام، فرایند CPU – گرا به پایین ترین سطح صف در شبکه می رسد و به صورت دوره ای (round robin) به اجرای خود تا تکمیل شدن ادامه می دهد.

صفهای بازخور چند سطحی برای جداسازی فرایندها و تقسیم بندی آنها براساس نیازشان به CPU ایده آل است.

در سیستمهای اشتراک زمانی، هر زمان که فرایندی شبکه صفی را ترک می کند، شماره پایین ترین سطح صفی که در آن بوده است به آن اختصاص می یابد و وقتی مجدداً وارد شبکه می شود مستقیماً به صفی فرستاده می شود که آخرین بار در آن عملیاتی بوده است.

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

اگر چنین شود مانع سرویس دهی به فرایندهای کوچک با اولویت بالا و یا فرایندهای I/O- گرا خواهد شد.

اگر فرایندها همیشه در پایین ترین سطح صفی قرار داده شود (در شبکه صفی) که آخرین بار بوده است برای سیستم امکان پذیر نخواهند بود که به تغییرات فرایندها پاسخ دهد (برای مثال، تغییر از حالت CPU – گرا به حالت I/O – گرا).

این مسأله هم می تواند با اختصاص شماره صفی که آخرین بار در آن اجرا می شد حل شود.

وقتی مجدد وارد شبکه می شود، می تواند در جای درست خود قرار داده شود.

آنگاه اگر فرایند در حال ورود به فاز جدید باشد (در صفی که از حالت CPU – گرا به حالت I/O – گرا تغییر حالت دهد) ، مجبور خواهد شد که عملکرد ضعیف سیستم را برای محاسبه و تعیین ماهیت تغییر فرایند تجربه کند.

اما در هر حال زمانبند سریعاً به این نوع تغییر پاسخ می دهد.

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

البته این کار می باید قبل از انقضای برش زمانی فرایند زمانی که CPU را در اختیار دارد انجام شود.

روش صفهای بازخور چند سطحی مثال خوبی از روش تطبیق پذیریی است.

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

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