دانلود با لینک مستقیم و پر سرعت .
لینک پرداخت و دانلود *پایین مطلب*
فرمت فایل:Word (قابل ویرایش و آماده پرینت)
تعداد صفحه: 55
مقدمه :
تخصیص پردازنده های فیزیکی به فرایندها سبب اجرای فرایندها می شود. این تخصیص معمولاً مسألة پیچیده ای است که توسط سیستم عامل مدیریت می شود. در این فصل درباره چگونگی تعیین زمان تخصیص پردازنده ها و اینکه پردازنده ها به کدام فرایندها باید تخصیص یابد، بحث خواهد شد. این عمل را زمانبندی پردازنده گویند.
سطوح زمانبندی
در شکل زیر سه سطح مهم از زمانبندی مورد توجه قرار گرفته است.
شکل 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) زمانبندی نوبت دوره ای
روش زمانبندی نوبت دوره ای در محیطهای اشتراک زمانی مؤثر عمل می کند به گونه ای که می تواند برای کاربران محاوره ای زمان پاسخ قابل قبولی را ضمانت کند. سرباری روش غیر انحصاری توسط روش تعویض متن کارآ، و فراهم کردن حافظه اصلی کافی برای مقیم شدن فرایندها، پائین نگهداشته می شود.
این فقط قسمتی از متن مقاله است . جهت دریافت کل متن مقاله ، لطفا آن را خریداری نمایید