Overview & Definition (परिचय तथा परिभाषा)
Scheduling is the method by which an operating system decides which of the ready processes will be allocated the CPU at any given time. It is a core function that determines the order of execution, aiming to make efficient use of system resources while meeting user and application requirements.
Core Concepts (मुख्य अवधारणाहरू)
1. Types of Schedulers
- Long‑term scheduler (Job scheduler): Controls the admission of jobs to the ready queue, influencing the degree of multiprogramming.
- Medium‑term scheduler (Swapper): Temporarily removes processes from main memory (swapping) to improve balance between I/O and CPU bound jobs.
- Short‑term scheduler (CPU scheduler): Makes rapid decisions (milliseconds) about which ready process gets the CPU next.
2. Common Scheduling Algorithms
- First‑Come, First‑Served (FCFS)
- Shortest Job First (SJF) – preemptive and non‑preemptive
- Priority Scheduling
- Round Robin (RR)
- Multilevel Queue
- Multilevel Feedback Queue
3. Performance Criteria (Factors that affect the scheduler’s performance)
- CPU Utilization: Keep the CPU busy as much as possible.
- Throughput: Number of processes completed per unit time.
- Turnaround Time: Total time taken from submission to completion of a process.
- Waiting Time: Time a process spends in the ready queue awaiting CPU.
- Response Time: Time from request submission to first response (critical for interactive systems).
- Fairness (Equity): Each process receives a reasonable share of CPU time.
- Predictability & Real‑time Constraints: Ability to meet deadlines in real‑time environments.
- Overhead: Time spent by the scheduler itself (context switches, decision making).
Key Points / Rules / Functions
- A good scheduler maximizes CPU utilization while minimizing waiting and response times.
- Different algorithms prioritize different criteria; e.g., SJF minimizes average waiting time, RR improves response time.
- Preemptive scheduling can improve responsiveness but increases overhead due to more context switches.
- Priority inversion is a problem where a low‑priority process holds resources needed by a high‑priority one; solutions include priority inheritance.
- Real‑time systems require deterministic scheduling (e.g., Rate‑Monotonic, Earliest‑Deadline‑First).
Comparison Table
| Criterion | Goal | Typical Algorithm Emphasis | Impact on Overhead |
|---|---|---|---|
| CPU Utilization | Keep CPU busy | FCFS, SJF, RR | Low to moderate |
| Throughput | Max processes completed per hour | SJF (short jobs first) | Low |
| Turnaround Time | Minimize total time per process | SJF, Priority | Low to moderate |
| Waiting Time | Reduce time in ready queue | RR, Multilevel Feedback | Moderate (more context switches) |
| Response Time | Fast first response for interactive jobs | RR, Priority (preemptive) | Higher due to preemption |
| Fairness | Equal CPU share for all processes | RR, Multilevel Queue | Moderate |
| Real‑time Guarantees | Meet deadlines deterministically | Rate‑Monotonic, EDF | Potentially high (tight control) |
Practical Application / Real‑world Relevance
Understanding scheduling is essential for:
- Loksewa & Civil Service Exams: Questions on OS fundamentals, process management, and performance metrics.
- Computer Operator Training: Monitoring CPU load, interpreting
toporTask Manager, and troubleshooting sluggish systems. - System Administration: Choosing appropriate scheduler settings (e.g., Linux CFS vs. deadline scheduler) for servers, embedded devices, or real‑time applications.
- Software Development: Designing applications that are CPU‑friendly, avoiding starvation, and using thread priorities wisely.
Quick Review Questions & Answers (अभ्यासका लागि प्रश्नोत्तर)
- What is the primary purpose of a short‑term scheduler?
To select which ready process gets the CPU next, usually within milliseconds. - Which scheduling algorithm generally provides the lowest average waiting time?
Shortest Job First (SJF) – when job lengths are known. - Define ‘context switch’ and its effect on scheduler overhead.
A context switch saves the state of the current process and loads the state of the next; it adds CPU overhead, especially in preemptive algorithms. - What problem does ‘priority inversion’ describe?
When a low‑priority process holds a resource needed by a high‑priority process, causing the high‑priority one to wait. - Match the criterion with the most suitable algorithm:
- Fast response for interactive users – Round Robin
- Maximum throughput – SJF
- Deterministic deadlines – Earliest Deadline First (EDF)
Use these questions to test your recall before the exam. Revisiting the table and key points will help you answer related multiple‑choice questions quickly.