CPU Scheduler

The CPU is one of the most critical resources in a computer system. In a multiprogramming environment, multiple processes share the CPU resource simultaneously, inevitably leading to competition among these processes for access to the CPU. The core problem that CPU scheduling aims to solve is how to allocate the CPU to one process from among those currently ready, such that the utilization of the CPU under this allocation is maximized while ensuring all processes can execute smoothly. Processor scheduling is divided into job scheduling and processor (process) scheduling.

Three Levels of CPU Scheduling

In an operating system, CPU scheduling refers to the process of deciding which processes should be scheduled for execution on the CPU based on specific policies and algorithms. CPU scheduling typically consists of three levels: High-level scheduling (Job Scheduling), Medium-level scheduling (Memory/Page Scheduling), and Low-level scheduling (Process Scheduling).

  1. High-level Scheduling (Job Scheduling)

    • Also known as job scheduling, this is the level of scheduling performed in a multiprogramming environment. Its primary task is to select appropriate jobs from the job queue, load them into memory, and allocate system resources (such as memory space and devices) to these jobs. The goal of high-level scheduling is to improve the overall throughput and resource utilization of the entire system. Since high-level scheduling involves loading jobs from secondary storage into main memory, it has a relatively large overhead and typically occurs when a job is submitted or completed.

  2. Medium-level Scheduling (Memory/Page Scheduling)

    • Also known as memory scheduling or page swapping/scheduling, this level operates within paging systems. Its primary task is to select suitable processes or pages for loading into memory based on available memory conditions, or to swap inactive processes/pages out of memory, thereby controlling memory usage and improving memory utilization efficiency. The goal of medium-level scheduling is to reduce the overhead associated with page swapping through reasonable replacement policies and provide sufficient memory space for process scheduling.

  3. Low-level Scheduling (Process Scheduling)

    • Also known as processor scheduling or context switching, this level operates at the process level. Its primary task is to select a process from the ready queue and allocate the CPU to it so that execution begins. The goal of low-level scheduling is to maximize CPU utilization, minimize response time, and achieve fair process scheduling. Common low-level scheduling algorithms include First-Come-First-Served (FCFS), Shortest Job Next (SJF), Round Robin (RR), etc.

These three levels of scheduling work in tandem to complete the task of process scheduling together. High-level scheduling is responsible for job selection and resource allocation, medium-level scheduling handles memory management and page swapping, while low-level scheduling selects runnable processes and allocates the CPU to them. Through reasonable scheduling policies and algorithms, it is possible to achieve efficient utilization of system resources, fair process scheduling, and high-performance operation of the system.

Processor Scheduling Queue Models

  • Scheduling queue model with only processor (process) scheduling
  • Queue models featuring both high-level and low-level scheduling
  • Scheduling queue model incorporating all three levels of scheduling

Methods, Triggers, and Processes of Process Scheduling

Method

Preemptive and Non-preemptive scheduling are two distinct methods used in process scheduling to determine whether a running process can be forcibly deprived of its CPU execution time. Below is an introduction to these two scheduling methods:

  1. Preemptive Scheduling

    • Preemptive scheduling refers to the capability of the operating system to forcibly preempt currently executing processes so that the CPU can be allocated to other processes with higher priority. In preemptive scheduling, a running process can be interrupted; its execution is halted, and the CPU is reassigned to a process with a higher priority. Preemptive scheduling typically relies on process priorities, Round Robin (RR), or other scheduling algorithms for context switching decisions.
    • The advantage of preemptive scheduling lies in its ability to respond promptly to requests from high-priority processes, thereby enhancing system responsiveness and real-time performance. However, frequent process transitions increase the overhead associated with scheduling and may lead to significant costs related to context switches. Therefore, when choosing preemptive scheduling, there is a need to balance between real-time requirements and overall system performance.

  2. Non-preemptive Scheduling

    • Non-preemptive scheduling refers to an environment where the operating system lacks the ability to forcibly preempt running processes until they voluntarily release the CPU or enter a blocked state. Once a process obtains access to the CPU under non-preemptive scheduling, it will continue executing uninterrupted until completion or active relinquishment of control.
    • The advantage of non-preemptive scheduling is that it reduces the overhead associated with context switching and avoids performance degradation caused by frequent interruptions. However, if a single process occupies the CPU for an extended period, other processes with higher priority may be blocked, leading to increased response times and suboptimal resource utilization.

The choice between preemptive and non-preemptive scheduling depends on system requirements and performance objectives. Preemptive scheduling is generally more suitable for real-time systems or environments requiring high responsiveness. Conversely, non-preemptive scheduling might be more appropriate for non-real-time systems or scenarios where maximizing resource usage is the primary concern.

Trigger

The triggers that cause process scheduling in an operating system typically include the following three situations:

  1. Creation of a New Process: When a new process is created and added to the ready queue, the scheduler selects a runnable process at this moment and allocates the CPU to it for execution initiation. This ensures that the newly created process has an opportunity to run and utilize system resources effectively.
  2. Termination of a Running Process: When a running process completes its execution tasks or terminates due to abnormal conditions (such as errors or interrupts), the scheduler selects the next ready process at this moment and switches the CPU to it. This ensures continuous utilization of the CPU, avoiding idle time periods.
  3. Blocking of a Running Process: When a running process issues a block request—for example, while waiting for an I/O operation to complete or awaiting an event—the scheduler selects the next ready process at this moment and allocates the CPU to it. This prevents blocked processes from occupying CPU resources, thereby enhancing system concurrency and resource utilization efficiency.

At these triggers, the process scheduler will select a suitable next process based on predetermined scheduling algorithms and policies. Common scheduling algorithms include First-Come-First-Served (FCFS), Shortest Job Next (SJF), Round Robin, etc. Through reasonable scheduling decisions, it is possible to achieve fair process scheduling, optimize system performance and resource utilization, and meet the diverse needs of different application types.

Process

Process scheduling is a critical procedure within an operating system responsible for selecting appropriate processes and allocating CPU resources. It typically involves the following steps:

  1. Save Context Information of the Current Running Process: When the scheduler decides to switch from the currently running process, it must first save the context information (also known as the state) of that process. This includes saving critical data such as register states, the Program Counter (PC), and stack pointers. By preserving this information, the system ensures that a process can resume execution in exactly the same state after switching.
  2. Select the Next Process to Run: After saving the context information of the current running process, the scheduler selects an appropriate candidate from the ready queue as the next process based on predetermined algorithms and policies. Selection criteria may include process priority, remaining execution time (burst time), waiting time, etc. The choice of scheduling algorithm directly impacts process fairness, response time, and system throughput.
  3. Restore Context Information for the Newly Selected Process: Once a new process is selected to run, the scheduler restores relevant register states, PC, stack pointers, etc., from its saved context information. Consequently, the newly selected process can continue execution from where it was previously suspended while continuing to utilize CPU resources effectively.

The above steps constitute the fundamental flow of process scheduling. It ensures that multiple processes share a single CPU reasonably through round-robin execution, achieving efficient resource utilization and fair process scheduling. The specific implementation details for each step depend on the design characteristics of the operating system and the chosen scheduling algorithm.

Single Processor Scheduling Algorithms

Principles

Single processor scheduling algorithms are used to schedule multiple processes on a single processing unit. Below are several common principles guiding the design and implementation of such algorithms:

  1. Fairness: The scheduling algorithm should strive to ensure fairness among all processes, meaning every process has an opportunity to obtain CPU resources for execution. This can be achieved through reasonable priority settings or Round Robin mechanisms. Fairness ensures that all processes within the system receive appropriate service levels.
  2. Response Time: A good scheduling algorithm should provide quick response times by allocating the CPU as soon as possible to newly arrived processes or those with long waiting queues. Shorter response times improve interactive performance and offer a better user experience.
  3. Throughput: The algorithm should aim to maximize system throughput, defined as the number of completed processes per unit time. High throughput increases resource utilization efficiency and working productivity, allowing more processes to be executed within a given timeframe.
  4. Resource Utilization: Scheduling algorithms should utilize CPU resources efficiently, avoiding scenarios where the processor is either excessively idle or over-utilized. Through effective allocation of CPU time slices (quantums) and reasonable process switching strategies, resource utilization can be optimized to ensure maximum usage of available CPU capacity.
  5. Predictability: The scheduling algorithm should exhibit a degree of predictability regarding process execution behavior and resource requirements. Predictable algorithms assist system administrators and application developers in performance tuning and resource planning by providing reliable estimates of future behavior.

In practical applications, specific single processor scheduling algorithms can be selected or adjusted based on varying system needs and performance goals. Common single processor scheduling algorithms include First-Come-First-Served (FCFS), Shortest Job Next (SJF), Round Robin (RR), Priority Scheduling, etc. Each of these algorithms possesses distinct advantages and applicability across different scenarios and workloads.

Commonly Used Algorithms

Below is a brief introduction to commonly used scheduling algorithms:

  1. First-Come-First-Served (FCFS): FCFS is a non-preemptive algorithm that schedules processes in the order of their arrival. Once a process enters the ready queue, it receives CPU access and runs until completion or voluntary blocking; only then does the next waiting process get scheduled. While this method is simple and intuitive, it can lead to excessively long wait times for longer jobs, a phenomenon known as "starvation."
  2. Round Robin (RR): RR is a preemptive algorithm where each process is assigned a fixed time slice (quantum). When the quantum expires, control of the CPU switches to the next process in the queue. If a process does not complete its work within its allocated time slice, it returns to the end of the ready queue. Round Robin ensures fairness and responsiveness but may result in frequent context switches and associated overheads.
  3. Priority Scheduling: This algorithm schedules processes based on their assigned priority levels, which can be static (assigned by a system administrator) or dynamic (calculated based on process characteristics or historical behavior). The process with the highest priority is scheduled first; if multiple processes share the same maximum priority, FCFS logic applies. Priority scheduling allows flexible assignment of priorities according to requirements but may lead to issues like "priority inversion" and starvation.
  4. Multilevel Feedback Queue (MLFQ): MLFQ is a dynamic algorithm that organizes processes into multiple queues with varying time slice sizes for different priority levels. Initially, all processes enter the highest-priority queue. If a process exhausts its quantum without completing execution, it drops one level of priority and moves to the next lower queue. Processes waiting excessively long may also be promoted in priority. MLFQ effectively balances the execution of short jobs against long ones while providing adaptability and flexibility.

Each of these scheduling algorithms has unique characteristics suitable for different scenarios and requirements. In practical applications, appropriate algorithms can be selected based on system properties and performance metrics, or combinations of multiple algorithms can be employed to create tailored scheduling strategies.

Real-Time Scheduling

Real-time scheduling is an algorithm designed specifically for real-time systems where the execution time of tasks is critical for maintaining system correctness and reliability. In such systems, tasks must complete within specified deadlines while adhering to strict timing constraints.

Real-time scheduling algorithms are generally categorized into two types: Hard Real-Time Scheduling and Soft Real-Time Scheduling.

  1. Hard Real-Time Scheduling:
    • Tasks under hard real-time scheduling must execute strictly according to their predetermined deadlines. Failure of a task to complete before its deadline is considered a system failure. Common algorithms for hard real-time systems include Earliest Deadline First (EDF) and Shortest Execution Time First (SETF). These algorithms prioritize tasks based on their respective deadlines or execution times, ensuring that all critical tasks meet their strict timing requirements.
  2. Soft Real-Time Scheduling:
    • Soft real-time scheduling allows for a certain degree of deadline violation; while the task's completion time can be delayed beyond its specified limit, this delay must remain within acceptable bounds defined by the system constraints. These algorithms typically consider task priority and importance to maximize overall system performance and utility. Common examples include standard Priority Scheduling and Earliest Deadline First (EDF).

The primary objective of real-time scheduling is to maximize task satisfaction rates while maintaining high system performance, all subject to strict timing requirements. This necessitates that the algorithm reasonably allocates CPU resources by making decisions based on factors such as deadlines, priorities, execution times, etc. Designing effective real-time algorithms requires careful consideration of the system's real-time demands, specific task characteristics and constraints, along with the inherent complexity and overheads associated with various scheduling mechanisms.