زمان‌بندی پردازنده برای کنکور: یک مثال، پنج الگوریتم، روی جدول زمانی

مثال و سه تعریف

• زمان بازگشت: زمان پایان منهای زمان ورود.
• زمان انتظار: زمان بازگشت منهای زمان اجرا؛ یعنی کل وقتی که فرایند آماده بوده ولی پردازنده را نداشته.
• تعویض متن: هر بار که پردازنده از یک فرایند به فرایند دیگری می‌رود.

FCFS: اول آمده، اول اجرا

فرایندها به ترتیب ورود و هر کدام تا آخر اجرا می‌شوند. نمودار زمانی: P1 از ۰ تا ۶، P2 از ۶ تا ۹، P3 از ۹ تا ۱۷، P4 از ۱۷ تا ۱۹ و P5 از ۱۹ تا ۲۳. زمان‌های انتظار ۰، ۵، ۷، ۱۴ و ۱۴ است و میانگینشان ۸٫۰.

P4 فقط ۲ واحد کار دارد ولی ۱۴ واحد منتظر می‌ماند، چون پشت P3 گیر کرده است. به این «اثر کاروان» می‌گویند: یک فرایند بلند، فرایندهای کوتاه پشت سرش را معطل می‌کند.

SJF غیرانحصاری: کوتاه‌ترین کار بعدی

هر وقت پردازنده آزاد شد، از بین فرایندهای آماده کوتاه‌ترین را انتخاب کن و تا آخر اجرایش کن. در زمان ۰ فقط P1 آماده است و تا ۶ اجرا می‌شود. در زمان ۶ همهٔ بقیه آماده‌اند و ترتیب بر اساس زمان اجرا می‌شود P4، P2، P5، P3. نمودار: P1 [۰–۶]، P4 [۶–۸]، P2 [۸–۱۱]، P5 [۱۱–۱۵]، P3 [۱۵–۲۳]. میانگین زمان انتظار ۵٫۸.

SRTF: کوتاه‌ترین زمان باقی‌مانده

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

• زمان ۰: فقط P1 هست و اجرا می‌شود.
• زمان ۱: P2 با ۳ واحد می‌آید و از باقی‌ماندهٔ P1 یعنی ۵ کمتر است؛ P1 کنار گذاشته می‌شود.
• زمان ۴: P2 تمام می‌شود. آماده‌ها P1 با ۵، P3 با ۸ و P4 با ۲‌اند؛ P4 اجرا می‌شود.
• زمان ۶: P4 تمام می‌شود. P5 با ۴ از P1 با ۵ کوتاه‌تر است و اجرا می‌شود.
• زمان ۱۰: P1 ادامه پیدا می‌کند تا ۱۵ و بعد P3 تا ۲۳.

نمودار: P1 [۰–۱]، P2 [۱–۴]، P4 [۴–۶]، P5 [۶–۱۰]، P1 [۱۰–۱۵]، P3 [۱۵–۲۳]. زمان‌های انتظار ۹، ۰، ۱۳، ۱ و ۱ و میانگین ۴٫۸؛ کمترین میانگین بین همهٔ الگوریتم‌های این مثال. SRTF در حالت کلی هم میانگین زمان انتظار را کمینه می‌کند، ولی به یک شرط غیرواقعی: باید زمان اجرای فرایندها را از قبل بدانی.

نوبت چرخشی: هر فرایند یک کوانتوم

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

کوانتوم ۲

نمودار: P1 [۰–۲]، P2 [۲–۴]، P3 [۴–۶]، P1 [۶–۸]، P4 [۸–۱۰]، P2 [۱۰–۱۱]، P5 [۱۱–۱۳]، P3 [۱۳–۱۵]، P1 [۱۵–۱۷]، P5 [۱۷–۱۹]، P3 [۱۹–۲۳]. میانگین زمان انتظار ۹٫۲ با ۱۰ تعویض متن.

کوانتوم ۴

نمودار: P1 [۰–۴]، P2 [۴–۷]، P3 [۷–۱۱]، P4 [۱۱–۱۳]، P1 [۱۳–۱۵]، P5 [۱۵–۱۹]، P3 [۱۹–۲۳]. میانگین زمان انتظار ۸٫۶ با ۶ تعویض متن.

اگر کوانتوم از بلندترین زمان اجرا بزرگ‌تر باشد، هیچ فرایندی قطع نمی‌شود و نوبت چرخشی دقیقاً FCFS می‌شود. اگر خیلی کوچک باشد، تعویض متن‌ها زیاد می‌شود و وقت پردازنده صرف جابه‌جایی می‌شود.

خلاصهٔ مقایسه

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

سه اشتباه رایج

اشتباه ۱: زمان انتظار را از صفر حساب کردن

زمان انتظار از لحظهٔ ورود حساب می‌شود، نه از صفر. P5 در FCFS در زمان ۱۹ شروع می‌شود ولی زمان انتظارش ۱۴ است، نه ۱۹، چون در زمان ۵ وارد شده بود.

اشتباه ۲: قرارداد صف در نوبت چرخشی

اگر ترتیب ورود فرایند تازه و بازگشت فرایند قطع‌شده را برعکس بگیری، کل نمودار زمانی عوض می‌شود. قبل از حل، قرارداد صورت سؤال را ببین؛ اگر چیزی نگفته، قرارداد رایج همان است که بالا گفتیم.

اشتباه ۳: گرسنگی

SJF و SRTF ممکن است یک فرایند بلند را تا ابد منتظر بگذارند اگر فرایندهای کوتاه پشت سر هم برسند. P3 در این مثال با ۱۳ واحد انتظار این را نشان می‌دهد. راه حل رایج «سالمندی» است: اولویت فرایندی که زیاد منتظر مانده کم‌کم بالا می‌رود.

پرسش‌های پرتکرار

کدام الگوریتم کمترین میانگین زمان انتظار را دارد؟

SRTF، یعنی نسخهٔ انحصاری SJF. در مثال این درس‌نامه میانگینش ۴٫۸ بود. ولی باید زمان اجرای فرایندها را از قبل دانست و فرایندهای بلند ممکن است گرسنه بمانند.

اگر کوانتوم نوبت چرخشی خیلی بزرگ باشد چه می‌شود؟

هیچ فرایندی قطع نمی‌شود و نوبت چرخشی دقیقاً همان FCFS می‌شود. در این مثال با کوانتوم ۱۰۰، نمودار و میانگین زمان انتظار دقیقاً مثل FCFS درآمد.

اثر کاروان چیست؟

در FCFS، یک فرایند بلند که زودتر رسیده، همهٔ فرایندهای کوتاه پشت سرش را معطل می‌کند و میانگین زمان انتظار را بالا می‌برد. در این مثال P4 با ۲ واحد کار، ۱۴ واحد منتظر ماند.

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

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

قدم بعدی تو

همین پنج فرایند را با نوبت چرخشی و کوانتوم ۳ زمان‌بندی کن و میانگین زمان انتظار را حساب کن. بعد فرایند P6 با ورود ۶ و اجرای ۱ را به مثال SRTF اضافه کن: P6 کی اجرا می‌شود و آیا فرایندی را قطع می‌کند؟

جواب‌ها: با کوانتوم ۳ نمودار P1 [۰–۳]، P2 [۳–۶]، P3 [۶–۹]، P4 [۹–۱۱]، P1 [۱۱–۱۴]، P5 [۱۴–۱۷]، P3 [۱۷–۲۰]، P5 [۲۰–۲۱]، P3 [۲۱–۲۳] است و میانگین زمان انتظار ۸٫۲. در SRTF، P6 درست در زمان ۶ می‌رسد، همان لحظه‌ای که P4 تمام می‌شود؛ پس فرایندی را قطع نمی‌کند، فقط چون از P5 کوتاه‌تر است از ۶ تا ۷ اجرا می‌شود و P5 یک واحد عقب می‌افتد.