Processor Scheduling

Tags (space separated): Process Scheduling Scheduling Algorithm Operating System

Basic Concept

Definition
: Operating System Management Limited resources of the system. When multiple processes (or requests issued by multiple processes) want to use these resources, due to the limited nature of the resources, processes (requests) must be selected according to certain principles to occupy the resources. We call this Scheduling.

The purpose is to control the number of resource users and select the permission of resource users to occupy resources or occupy resources. Three levels of processor scheduling:

Advanced scheduling: job scheduling, the scheduling object is the job.
Intermediate scheduling: memory scheduling (essential It is the memory swap function)
Low-level scheduling: process scheduling, the scheduling object is a process or kernel-level thread

Job scheduling The algorithm of \)
: The time interval from when a job or process is submitted to the system until the job or process is completed.

Usually includes:

The time the job waits for scheduling on the external storage backup queue.
The time the process waits for process scheduling on the ready queue.The time the process executes on the CPU.The time the process waits for the I/O operation to complete.

Average turnaround time:

\[T = \frac{\sum_{i=1}^n T_i}{n}\]

Powered turnaround time: The turnaround time of a job and the number of people who serve it Time ratio

\[W_i = \frac{T_i}{T_s}\]

Average weighted turnaround time:\[W = \frac{\sum_ {i=1}^n \frac{T_i}{T_s}}{n}\]

Scheduling timing, switching and process
The process scheduling and switching program is the operating system kernel program. When the event requesting scheduling occurs, the process scheduler may be run. When a new ready process is scheduled, switching between processes will be performed. In theory, these three things should be executed sequentially, but in actual design, when the operating system kernel program is running, if factors that cause process scheduling occur at some point, scheduling and switching may not be possible immediately.
In modern operating systems, there are the following situations where process scheduling and switching cannot be performed:

In the process of handling interrupts: the interrupt processing process is complicated, It is difficult to switch processes in implementation, and interrupt processing is part of the system's work. It does not logically belong to a certain process and should not be deprived of processor resources.

The process is in the critical section of the operating system kernel program: after entering the critical section, it needs to access shared data exclusively. In theory, it must be locked to prevent other parallel programs from entering. After unlocking You should not switch to other processes before running to speed up the release of the shared data.

During other atomic operations that require complete shielding of interrupts: such as locking, unlocking, interrupting site protection, recovery and other atomic operations. In an atomic process, even interrupts must be masked, and process scheduling and switching should not be performed.
If conditions that cause scheduling occur during the above process, and scheduling and switching cannot be performed immediately, the system's request scheduling flag should be set, and the corresponding scheduling will not be performed until the above process is completed. with switch.
The situations where process scheduling and switching should be performed are:

When a scheduling condition occurs and the current process cannot continue to run, scheduling and switching can be performed immediately. If the operating system only performs process scheduling under this situation, it is non-deprivation scheduling.

When the interrupt processing or the trap processing is completed, before returning to the user mode program execution site of the interrupted process, if the request scheduling flag is set, process scheduling and switching can be performed immediately . If the operating system supports a run scheduler in this case, deprivation mode scheduling is implemented.

Process switching often occurs immediately after scheduling is completed. It requires saving the scene information of the current switching point of the original process and restoring the scene information of the scheduled process. When switching context, the operating system kernel pushes the context information of the original process into the kernel stack of the current process to save them and updates the stack pointer. After the kernel completes the loading of the new process's on-site information from the new process's kernel stack, updates the currently running process space pointer, resets the PC register and other related work, it starts to run the new process.
Scheduling method

Non-preemptive method

Once the processor is assigned to a process, it will continue to run, never due to clock interruption or For any other reason, the processor of the currently running process is preempted. The processor will not be allocated to other processes until the process is completed or blocked due to an event.

The system allows the scheduler to suspend an executing process and reallocate the processor assigned to the process to another process based on certain principles.
Certain principles should be followed when "preempting":
Priority principle

Time slice principle

Typical scheduling algorithm

First-come first-served scheduling algorithm ):

is the FCFS scheduling algorithm, which can be used for both job scheduling and process scheduling. The system follows the order in which jobs arrive (the one with the longest waiting time in the ready queue is given priority Job) for scheduling.
Disadvantages: The urgency of the job is not considered and can only be run sequentially

Short job (process) priority scheduling algorithm (short job first):

It is set up for short jobs, because most of the operating systems are short jobs. When the job is running, the system selects the job with the shortest running time and transfers it into the memory.

SJF (non-preemptible): The algorithm calculates the priority based on the length of the job (the time the job needs to run). The shorter the job, the higher its priority.
SPF (preemptible): Same as above, but when there is a job with a higher priority, it can preempt resources and execute them first.

Disadvantages:

The running time of the job must be predicted in advance
It is not good for the job process
Human-computer interaction cannot be achieved
Does not consider the urgency of the job

Priority-scheduling algorithm:

PSA algorithm is based on the job Urgency, the corresponding priority is given to the job from the outside, and scheduled according to the job priority.

Highest response closed priority scheduling algorithm (highest request ratio next):

The HRRN algorithm takes into account both the waiting time of the job and the job running time. It introduces a dynamic priority for no jobs:

Priority = (waiting time + required service time) / required service time

can be abbreviated as:

R = response time/required service time

Features:

If the job waiting time is the same, the shorter the service time required, the higher the priority, similar to the SJF algorithm, which is conducive to short jobs
When the job requires the same service time, then The longer the job waiting time is, the higher the priority is, similar to the FCFS algorithm, which is beneficial to long jobs
For long jobs (requiring long service time), as the waiting time is long enough, You can also get a higher priority. You will not wait forever.

Time slice rotation scheduling algorithm (RR)

Principle: The system will allocate all The ready process is arranged in a ready queue, and is set to generate sequential interrupts at regular intervals, activate the process scheduler in the system, complete the sequential scheduling, and allocate the CPU to the new queue leader process (or newly arrived urgent process).

Process switching

If a time slice has not been used up and the running process has been completed, the scheduler will be activated immediately and deleted from the execution queue. The head process of the ready queue runs and starts a new time slice.
When a time slice runs out, the timing interrupt handler is activated. If the process has not finished running, then The scheduler sends it to the end of the ready queue, schedules the head process of the ready queue to run, and starts a new time slice.

Note: The time slice is selected too If it is small, frequent execution process scheduling and process long context switching will increase system overhead; if the time slice is selected too long, the RR algorithm will degenerate into the FCFS algorithm, which cannot meet the needs of short jobs and interactive users. The time slice should be selected slightly larger than the sequential The time required for a typical interaction is that most processes complete it within a time slice.

Multi-level feedback queue scheduling algorithm (multileved feedback queue):

Settings Multiple ready queues, and assign different priorities to each queue. The higher the priority, the smaller the time slice. The queue with the highest priority enters the queue to be scheduled first
The FCFS scheduling algorithm is used between queues. Only when all processes in the high-priority queue are completed will the next queue be scheduled.
The processes in the queue are scheduled according to the rotation algorithm. New processes enter After the memory, it first enters the queue with the highest priority
When a low-priority queue is running, if a new process arrives, then after running this time slice, the CPU is immediately allocated to the new arrival jobs (preemptive).

Process scheduling algorithm in real-time system

Real-time system means that the system can respond to requests from external events in a timely manner and process these requests in a timely manner. Based on this feature, real-time systems are widely used in industry ( Common in weapons) control, multimedia and other systems.
There is a deadline in real-time systems. Hard real-time tasks (HRT) require that they must be executed before the start deadline and must end before the end deadline. Soft real-time tasks Same as above, but not strict.
There are two types of algorithms worth noting in real-time systems: Earliest Deadline First algorithm (Earliest Deadline First) and Least Laxity First algorithm (Least Laxity First). Both types of algorithms can use preemptive methods and non-preemptive scheduling, but the latter is often used for preemptive scheduling.
In m periodic real-time scheduling, the processing time of each real-time task$C_i$, cycle time$P_i$, in the case of but one processor, the conditions must be met: $\sum_{i=1}^m\frac{C_i}{P_i} $less than 1; more Under the processor condition, the condition must be met$\sum_{i=1}^m\frac{C_i}{P_i} $ is less than N, N is the number of processors.

The earliest deadline takes precedence Algorithm (EDF)

This algorithm determines the priority of tasks according to their deadlines in real-time systems.

Non-preemptive
Preemptive

Least Slack First Algorithm (LLF)

In this method, tasks are given priority according to their urgency (slack), the higher the The higher the priority of the urgent task.

The slack degree of the task = the time it must be completed - its own running time - the current time

The tasks of the system are arranged according to the slack degree A ready queue, tasks with low slack are placed at the front of the queue, that is, the scheduler executes them first.

The above is the detailed content of Detailed introduction to processor scheduling. For more information, please follow other related articles on the PHP Chinese website!