جلسه 3 انواع زمان بندي (انحصاري و غیر انحصاري)، الگوریتم هاي زمان بندي ،(Round Robin ،FCFS (MLFQ ،MLQ،Priority ،HRN ،SRT ،SJF -

مقدمه

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

بخش ۱: انواع زمان‌بندی

زمان‌بندی پردازنده را می‌توان به دو دسته کلی تقسیم کرد:

۱. زمان‌بندی انحصاری (Non-Preemptive Scheduling)

در این نوع زمان‌بندی، پس از آنکه یک فرآیند، پردازنده را در اختیار گرفت، تا زمانی که اجرای آن به پایان نرسد یا خود فرآیند پردازنده را داوطلبانه آزاد نکند (مثلاً در انتظار ورودی/خروجی)، پردازنده را رها نخواهد کرد.

• ویژگی‌ها:


• پیاده‌سازی ساده‌تر.


• ممکن است منجر به زمان انتظار طولانی برای فرآیندهای کوتاه‌تر شود اگر یک فرآیند طولانی مدت پردازنده را اشغال کند.


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

۲. زمان‌بندی غیر انحصاری (Preemptive Scheduling)

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

• ویژگی‌ها:


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


• پیچیدگی بیشتر در پیاده‌سازی (نیاز به مکانیزم‌های سوئیچینگ زمینه یا Context Switching).


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

بخش ۲: الگوریتم‌های زمان‌بندی

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

۱. FCFS (First-Come, First-Served) - اولین ورود، اولین خروج

• نوع: انحصاری (Non-Preemptive)


• نحوه عملکرد: فرآیندها به ترتیبی که وارد صف آمادگی (Ready Queue) می‌شوند، پردازنده را دریافت می‌کنند.


• مزایا: ساده‌ترین الگوریتم برای پیاده‌سازی.


• معایب: مشکل “نگهبان گاری” (Convoy Effect)؛ یعنی اگر یک فرآیند طولانی مدت در ابتدا باشد، تمام فرآیندهای بعدی حتی اگر بسیار کوتاه باشند، منتظر می‌مانند. زمان انتظار و زمان چرخش می‌تواند بالا باشد.

۲. SJF (Shortest Job First) - کوتاه‌ترین کار اول

• نوع: می‌تواند انحصاری یا غیر انحصاری باشد.


• نحوه عملکرد (انحصاری): پردازنده به فرآیندی تخصیص داده می‌شود که زمان اجرای باقی‌مانده آن کوتاه‌تر است. اگر فرآیند جدیدی با زمان اجرای کوتاه‌تر وارد شد، فرآیند فعلی همچنان به اجرای خود ادامه می‌دهد تا تکمیل شود.


• نحوه عملکرد (غیر انحصاری - SRT: Shortest Remaining Time): اگر فرآیند جدیدی با زمان اجرای باقی‌مانده کوتاه‌تر از زمان اجرای باقی‌مانده فرآیند فعلی وارد صف شود، پردازنده از فرآیند فعلی پس گرفته شده و به فرآیند جدید تخصیص می‌یابد.


• مزایا: به طور متوسط بهترین زمان انتظار و زمان چرخش را ارائه می‌دهد.


• معایب: پیش‌بینی زمان اجرای آینده فرآیند دشوار است. الگوریتم انحصاری ممکن است منجر به گرسنگی (Starvation) فرآیندهای طولانی شود.

۳. Priority Scheduling - زمان‌بندی اولویت‌دار

• نوع: می‌تواند انحصاری یا غیر انحصاری باشد.


• نحوه عملکرد: به هر فرآیند یک اولویت نسبت داده می‌شود و پردازنده به فرآیندی با بالاترین اولویت (معمولاً کمترین عدد نشان‌دهنده بالاترین اولویت است) تخصیص می‌یابد.


• مزایا: امکان اولویت‌بندی وظایف مهم‌تر.


• معایب: مشکل گرسنگی؛ فرآیندهای با اولویت پایین ممکن است هرگز اجرا نشوند. برای حل این مشکل از تکنیکی به نام “بالا رفتن سن” (Aging) استفاده می‌شود که به تدریج اولویت فرآیندهای منتظر را افزایش می‌دهد.

۴. HRN (Highest Response Ratio Next) - بالاترین نسبت پاسخ‌دهی بعدی

• نوع: انحصاری (Non-Preemptive)


• نحوه عملکرد: این الگوریتم سعی می‌کند هم زمان انتظار و هم زمان اجرای فرآیند را در نظر بگیرد تا از معایب SJF و FCFS جلوگیری کند. نسبت پاسخ‌دهی به صورت زیر محاسبه می‌شود:

$$\text{Response Ratio} = \frac{\text{Waiting Time} + \text{Service Time}}{\text{Service Time}}$$

پردازنده به فرآیندی با بالاترین نسبت پاسخ‌دهی تخصیص می‌یابد.

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


• معایب: محاسبه نسبت پاسخ‌دهی برای هر فرآیند در هر بار تصمیم‌گیری زمان‌بر است.

۵. MLQ (Multi-Level Queue) - صف‌های چند سطحی

• نوع: غیر انحصاری (Preemptive)


• نحوه عملکرد: صف آمادگی به چندین صف مجزا تقسیم می‌شود. هر صف ممکن است الگوریتم زمان‌بندی خاص خود را داشته باشد (مثلاً صف فرآیندهای تعاملی از نوع Round Robin و صف فرآیندهای دسته‌ای از نوع FCFS). همچنین، تخصیص زمان بین صف‌ها نیز زمان‌بندی می‌شود (مثلاً اولویت با صف بالایی است).


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


• معایب: تخصیص منابع ثابت بین صف‌ها ممکن است انعطاف‌پذیری را کاهش دهد.

۶. MLFQ (Multi-Level Feedback Queue) - صف‌های چند سطحی با بازخورد

• نوع: غیر انحصاری (Preemptive)


• نحوه عملکرد: این الگوریتم شبیه MLQ است اما انعطاف‌پذیری بیشتری دارد. فرآیندها می‌توانند بین صف‌ها جابجا شوند. اگر فرآیندی از زمان کوانتوم خود استفاده کامل کند (یعنی زمان‌بر باشد)، به صف با اولویت پایین‌تر منتقل می‌شود. اگر فرآیندی زودتر از اتمام زمان کوانتوم خود آزاد شود (مثلاً در انتظار I/O)، ممکن است در همان صف یا صف بالاتری باقی بماند. این مکانیزم به طور خودکار فرآیندهای تعاملی را شناسایی و اولویت می‌دهد.


• مزایا: تطبیق‌پذیرترین الگوریتم؛ سعی می‌کند بهترین ویژگی‌های الگوریتم‌های دیگر را ترکیب کند و به طور خودکار رفتارهای فرآیند را تشخیص دهد.


• معایب: پیاده‌سازی پیچیده‌تر؛ نیاز به تنظیم پارامترهای متعدد (تعداد صف‌ها، الگوریتم هر صف، نحوه جابجایی فرآیندها).

۷. Round Robin (RR) - گردوراه

• نوع: غیر انحصاری (Preemptive)


• نحوه عملکرد: هر فرآیند یک واحد پردازش کوچک به نام “زمان کوانتوم” (Time Quantum) یا “Slice” دریافت می‌کند. فرآیندها به نوبت در صف اجرا می‌شوند. اگر فرآیند در طول زمان کوانتوم خود تکمیل نشود، اجرای آن متوقف شده و به انتهای صف آمادگی منتقل می‌شود.


• مزایا: منصفانه؛ زمان پاسخ‌دهی خوبی برای فرآیندهای تعاملی فراهم می‌کند.


• معایب: اگر زمان کوانتوم خیلی کوتاه باشد، سربار سوئیچینگ زمینه (Context Switching Overhead) افزایش می‌یابد. اگر خیلی طولانی باشد، شبیه FCFS عمل می‌کند و زمان پاسخ‌دهی کند می‌شود.

خلاصه نکات کلیدی

• زمان‌بندی انحصاری: فرآیند پردازنده را تا پایان آزاد نمی‌کند. پیاده‌سازی ساده‌تر اما ممکن است کارایی را کاهش دهد.


• زمان‌بندی غیر انحصاری: سیستم‌عامل می‌تواند پردازنده را پس بگیرد. کارایی بهتر، به‌ویژه برای تعاملات کاربر.


• FCFS: ساده، اما مستعد مشکل “نگهبان گاری”.


• SJF/SRT: به طور متوسط بهترین عملکرد را دارد، اما پیش‌بینی زمان اجرا دشوار است و ریسک گرسنگی وجود دارد.


• Priority: امکان اولویت‌بندی، اما نیازمند راهکاری برای جلوگیری از گرسنگی (مانند Aging).


• HRN: تعادل بین زمان انتظار و زمان اجرا، جلوگیری از گرسنگی.


• MLQ: تفکیک فرآیندها در صف‌های مجزا با سیاست‌های متفاوت.


• MLFQ: انعطاف‌پذیرترین؛ با جابجایی فرآیندها بین صف‌ها، رفتارهای مختلف را مدیریت می‌کند.


• Round Robin: منصفانه با زمان کوانتوم مشخص، مناسب برای سیستم‌های تعاملی.

تمرین پایان فصل

۱. فرآیندهای زیر با زمان رسیدن و زمان اجرای مشخص شده‌اند. الگوریتم‌های FCFS، SJF (انحصاری)، SRT (غیر انحصاری) و Round Robin (با زمان کوانتوم ۲ واحد زمانی) را برای این فرآیندها شبیه‌سازی کنید. جدول زمان‌بندی (Gantt Chart) را رسم کرده و میانگین زمان انتظار (Average Waiting Time) و میانگین زمان چرخش (Average Turnaround Time) را برای هر الگوریتم محاسبه کنید:

۲. چرا الگوریتم MLFQ به طور خودکار فرآیندهای تعاملی را شناسایی و اولویت می‌دهد؟ مکانیزم آن را توضیح دهید.

۳. مشکل گرسنگی (Starvation) در الگوریتم‌های زمان‌بندی اولویت‌دار و SJF چیست و چگونه می‌توان با استفاده از تکنیک “Aging” آن را برطرف کرد؟

۴. در یک سیستم با زمان‌بندی Round Robin، اگر زمان کوانتوم بسیار کوتاه باشد چه اتفاقی می‌افتد؟ و اگر بسیار طولانی باشد چطور؟

۵. مزیت اصلی الگوریتم HRN نسبت به FCFS و SJF چیست؟ فرمول محاسبه نسبت پاسخ‌دهی را بنویسید.