Process Scheduling Algorithms
In operating systems, process scheduling algorithms determine how the CPU allocates time slices to different processes.
Process scheduling algorithms are one of the core components of an operating system, responsible for selecting the next process to execute from the ready queue. Here are common process scheduling algorithms and their characteristics:
- First-Come-First-Served (FCFS)
Rules: Processes are executed in the order they arrive at the ready queue.
Characteristics:
Non-preemptive; once a process starts running, it releases the CPU only when completed or blocked.
Favorable to long processes; short processes may experience “starvation” while waiting for long processes.
May result in longer average waiting time (convoy effect).
- Shortest Job First (SJF)
Rules: Prioritize processes with the shortest expected running time.
Variants:
Non-preemptive: New processes are scheduled only after the current process finishes running.
Preemptive (Shortest Remaining Time Next, SRTN): When a new process arrives, if its running time is shorter than the remaining time of the current process, it preempts the CPU.
Characteristics:
Theoretically optimal in terms of average waiting time, but requires 预知 the running time of processes (difficult to implement in practice).
May cause “starvation” for long processes. The drawback is how to accurately predict which process has a shorter execution time.
- Priority Scheduling
Rules: Each process is assigned a priority, and the process with the highest priority is executed first.
Variants:
Non-preemptive: The highest priority process is selected only after the current process finishes.
Preemptive: A higher priority process immediately preempts the CPU when it arrives.
Characteristics:
May cause “starvation” for low-priority processes (can be alleviated by an aging strategy that dynamically increases the priority of long-waiting processes).
Priority can be determined statically or dynamically (e.g., I/O-bound processes have higher priority).
- Round Robin (RR)
Rules:
Each process is allocated a fixed time quantum (e.g., 10-100ms); the CPU is forced to switch to the next ready process when the time quantum expires.
The ready queue adopts a circular queue structure.
Characteristics:
Preemptive, suitable for time-sharing systems, ensuring fairness.
If the time quantum is too large, it degrades to FCFS; if too small, it causes frequent context switches with high overhead.
Average response time is relatively short.
- Multilevel Queue
Rules:
Divide the ready queue into multiple independent queues (e.g., foreground interactive queue, background batch queue), and each queue can be configured with a different scheduling algorithm (e.g., RR for foreground, FCFS for background).
Queues usually adopt fixed priority or time slice allocation strategies.
Characteristics:
Handles processes of different natures separately, but “starvation” may occur between queues.
- Multilevel Feedback Queue (MLFQ)
Rules:
Combines multilevel queues with dynamic priority adjustment:
New processes enter the highest priority queue (with a short time quantum).
If a process does not complete within the time quantum, it is demoted to the next queue (with a longer time quantum).
Processes in low-priority queues may have their priority increased to prevent “starvation”.
Characteristics:
Balances response time and throughput, and is a commonly used algorithm in practical systems (e.g., Unix, Windows).
- Fair Share Scheduling
Rules: Allocate CPU resource shares by user or group (e.g., User A accounts for 30%, User B accounts for 70%).
Characteristics: Prevents a single user or group from monopolizing resources, suitable for multi-user systems.
- Real-Time Scheduling Algorithms
Application scenarios: Real-time systems (e.g., industrial control, aerospace), requiring strict satisfaction of deadlines.
Classification:
Hard real-time: Deadlines must be met (e.g., missile control systems).
Soft real-time: Deadlines should be met as much as possible (e.g., video streams).
Common algorithms:
Earliest Deadline First (EDF): Dynamic priority, selects the process with the earliest deadline.
Rate Monotonic Scheduling (RMS): Static priority, processes with shorter periods have higher priority.
Comparative Summary
| Algorithm | Preemptive | Characteristics | Application Scenarios |
| FCFS | No | Simple, but with long average waiting time | Batch processing systems |
| SJF/SRTN | Optional | Optimal average waiting time | Theoretical models |
| Priority Scheduling | Optional | May cause starvation | General systems (requires aging) |
| Round Robin | Yes | Fair, short response time | Time-sharing systems |
| Multilevel Feedback Queue | Yes | Balances response and throughput | General operating systems (e.g., Linux) |
| Real-Time Scheduling | Yes/No | Guarantees deadlines | Real-time systems |
Practical systems (e.g., Linux) usually combine multiple algorithms. For example, the Completely Fair Scheduler (CFS) achieves fairness based on time slices and virtual runtime. Meanwhile, learning these scheduling algorithms is also reflected in our daily projects. We can learn the ideas of these scheduling algorithms to select appropriate application scenarios to improve system performance and stability. Here are some examples:
Case 1: Interactive Systems (e.g., desktop operating systems)
需求特点 (Requirement Characteristics):
Need quick response to user operations such as mouse and keyboard (low latency).
Run multiple applications simultaneously (e.g., browser, editor), requiring fair allocation of CPU resources.
Recommended Algorithms: Multilevel Feedback Queue (MLFQ) + Round Robin (RR)
MLFQ: Place interactive processes (e.g., GUI) in high-priority queues (short time quantum) to ensure quick response.
RR: Processes in the same queue execute in turn to prevent a single application from monopolizing the CPU.
Practical application: Linux’s CFS (Completely Fair Scheduler) dynamically adjusts priorities through virtual runtime (vruntime), similar to the MLFQ idea.
Effects:
User click operations can respond immediately (high-priority queues are processed first).
Background compilation tasks are automatically demoted to low-priority queues without affecting the foreground experience.
Case 2: Batch Processing Systems (e.g., scientific computing clusters)
需求特点 (Requirement Characteristics):
A large number of long-running computing tasks (e.g., numerical simulation, data analysis).
Goal is to maximize throughput (number of tasks completed per unit time).
Recommended Algorithm: Non-preemptive variant of Shortest Job First (SJF)
Reason: Short tasks are executed first, reducing average waiting time and improving overall throughput.
Optimization: If task time cannot be predicted, an approximate SJF can be used (e.g., predicting based on historical running time).
Practical applications:
In Hadoop/YARN resource scheduling, MapReduce tasks are sorted by estimated execution time, with short tasks scheduled first.
Note: To avoid “starvation” of long tasks, an aging mechanism can be combined (gradually increasing the priority of long-waiting tasks).
Case 3: Real-Time Control Systems (e.g., autonomous driving, industrial robots)
需求特点 (Requirement Characteristics):
Tasks have strict deadlines (e.g., sensor data processing must be completed within 10ms).
Timeouts may cause system failures (hard real-time requirements).
Recommended Algorithm: Earliest Deadline First (EDF)
Rules: Dynamically select the task with the earliest deadline for execution.
Example:
Task A: Needs to be completed within 5ms, taking 2ms.
Task B: Needs to be completed within 8ms, taking 3ms.
Scheduling order: A → B (because A has an earlier deadline).
Effects:
All tasks can be completed before their deadlines (provided the system load is manageable).
Key: Must be combined with resource reservation (e.g., CPU utilization does not exceed 70%).
Case 4: Cloud Computing Virtual Machine (VM) Scheduling
需求特点 (Requirement Characteristics):
Multi-tenants share physical resources, requiring performance isolation (e.g., preventing a single VM from occupying too much CPU).
Balancing fairness and resource utilization.
Recommended Algorithm: Fair Share Scheduling
Rules: Allocate CPU according to the share purchased by tenants (e.g., Tenant A purchases 30% of resources, Tenant B purchases 70%).
Practical applications:
VMware ESXi’s Shares mechanism: Allocates CPU time proportionally.
Kubernetes’ Resource Quotas: Limits CPU usage per namespace.
Effects:
Tenant B’s tasks can obtain more CPU but will not completely starve Tenant A.
During traffic bursts, idle resources can be temporarily borrowed by other tenants (e.g., AWS’s Burstable Instances).
Case 5: Hybrid Load Systems (e.g., database servers)
需求特点 (Requirement Characteristics):
Handle both OLTP (short-term high-concurrency queries) and OLAP (long-term analysis queries).
OLTP requires low latency, and OLAP requires high throughput.
Recommended Algorithm: Multilevel Queue
Design:
High-priority queue: OLTP queries (RR algorithm, short time quantum).
Low-priority queue: OLAP queries (FCFS algorithm, preemptable).
Practical applications:
PostgreSQL’s background worker processes have lower priority than user queries.
Adjust process priority through nice values (Linux).
Effects:
User queries can always be executed first, ensuring response time.
OLAP tasks make full use of resources when the system is idle.
Summary: How to Choose a Scheduling Algorithm?
Clarify requirements: Response time, throughput, fairness, or real-time performance?
Analyze load characteristics: Are there more short tasks or long tasks? Are there strict deadlines?
Balance overhead: Such as the cost of context switching in round robin.
Dynamic adjustment: Practical systems often combine multiple algorithms (e.g., MLFQ + fair share).
These are mainly theoretical knowledge. It is important to know their existence so that you don’t have to reinvent the wheel when needed. You can quickly understand these ideas and start implementing them directly. Only by applying them in projects can you gain deeper experience and understanding, and practical ability is also crucial.
