Home > Article > Operation and Maintenance > Detailed introduction to processor scheduling
Tags (space separated): Process Scheduling Scheduling Algorithm Operating System
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
Usually includes: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.
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:\[W_i = \frac{T_i}{T_s}\]
\[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
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:
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.
Certain principles should be followed when "preempting":
Priority principle
Time slice principle
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
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
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.
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.
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.
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).
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.
This algorithm determines the priority of tasks according to their deadlines in real-time systems.
Non-preemptive
Preemptive
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!