Shulou(Shulou.com)06/03 Report--

This article mainly introduces "what are the classical process scheduling algorithms". In daily operations, I believe that many people have doubts about the classical process scheduling algorithms. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts about "what are the classical process scheduling algorithms?" Next, please follow the editor to study!

Many of the pictures in the article come from the online courses I saw when I took the postgraduate entrance examination, which should still be found on the B station. You can take a look at the series of operating systems produced by the postgraduate entrance examination. It is suitable for the examination, but it is not very suitable for the spring and autumn recruitment, because the knowledge points are too detailed. All the edges and corners will talk about it. You can pick a few chapters to see. The mental map of the full text is as follows:

1. The concept of scheduling

When CPU has a lot of tasks to deal with, because of its limited resources, these things cannot be handled at the same time. This requires the determination of certain rules to determine the order in which these tasks are processed, which is the problem of scheduling. In addition to the next process scheduling, there are also job scheduling, memory scheduling and so on.

Review the three-state model of the process:

"running": the process occupies that CPU is running.

"ready": the process is ready to run, waiting for the system to allocate CPU to run.

Blocking / wait: the process does not have the conditions to run and is waiting for the completion of an event.

The so-called process scheduling is to select a process from the ready queue (blocking) of a process according to a certain algorithm and assign CPU to it to run, in order to realize the concurrent execution of the process. This is the most basic (lowest-level) scheduling in the operating system, and process scheduling must be configured in general operating systems. The frequency of process scheduling is very high, usually tens of milliseconds.

two。 Non-preemptive process scheduling algorithm

Non-preemptive means that when a process is running, it runs until the process finishes or when an event occurs that blocks the CPU to another process.

Correspondingly, preemption means that when a process is running, it can be interrupted to give up the CPU to other processes.

① first come, first served FCFS

First-come-first-served scheduling algorithm (First Come First Serve,FCFS): scheduling according to the order in which processes arrive. "first-arrived processes are scheduled first", that is, the longer the waiting time, the more priority to get the service.

Advantages: fairness and simple implementation of the algorithm

Disadvantages: it is disadvantageous to short processes. The short process after the long process needs to wait a long time, the response time of the short process is too long, and the user interaction experience will become worse.

② shortest job first SJF

Shortest Job / process first scheduling algorithm (Shortest Job First,SJF): "each time you schedule, select the currently arrived process with the shortest running time".

The shortest job priority algorithm is opposite to the first-come-first-served algorithm, the first-come-first-served algorithm is disadvantageous to the short process, while the shortest job priority algorithm is disadvantageous to the long-term. Because if there is a short process coming all the time, then the long process will never be scheduled, and the long process may starve to death and wait for the completion of the short job.

③ High response ratio priority HRRN

High response ratio priority algorithm (Highest Response Ratio Next,HRRN): only when the currently running process actively abandons CPU (normal / abnormal completion, or active blocking), it needs to be scheduled. "when scheduling, calculate the response ratio of all ready processes, and assign CPU to the process with the highest response ratio." Response ratio = (waiting time of the process + running time required by the process) / elapsed time required by the process

3. Preemptive process scheduling algorithm

Preemption means that when a process is running, it can be interrupted to give up the CPU to other processes. There are generally three principles of preemption, namely, the time slice principle, the priority principle and the short task priority principle.

① minimum remaining time first SRTN

The shortest remaining time first (Shortest Remaining Time Next,SRTN) algorithm is a preemptive version of the shortest job first.

"when a new process arrives, compare the entire elapsed time it needs with the remaining elapsed time of the current process. If the new process takes less time, suspend the current process and run the new process, otherwise the new process waits. "

② round robin scheduling algorithm RR

Round robin scheduling algorithm (Round Robin,RR) is also known as time slice scheduling algorithm: each time the scheduler allocates CPU to the first process of the ready queue using a specified time interval, which is usually called 10ms ~ 200ms. "each process in the ready queue takes turns running a time slice, and when the time slice is exhausted, it forces the current running process to release CPU resources and queue to the end of the ready queue to wait for the next round of scheduling." Therefore, a process generally needs to be rotated multiple times to complete.

The round robin algorithm treats every process equally, just as everyone is lined up, one by one, and everyone runs for a while and then re-queues to run.

It should be noted that the length of the time slice is a key factor:

If the time slice is set too short, it will lead to frequent process context switching and reduce the efficiency of CPU.

If the time slice is set too long, the total time consumed by each rotation increases as the number of processes in the ready queue increases, that is, the corresponding speed of each other process slows down. Even if the time slice is large enough for the process to complete all its tasks, the RR scheduling algorithm degenerates to the FCFS algorithm.

4. The highest priority scheduling algorithm HPF

The RR scheduling algorithm has the same policy for all processes, and if there are too many user processes, it may cause the kernel's service process response to fall behind. In the operating system, the kernel process is much more important than the user process, after all, it is related to the stability of the whole system.

The highest priority scheduling algorithm (Highest Priority First,HPF) is to select the highest priority process from the ready queue to run. How is the priority of the process set? Divided into static priority or dynamic priority:

"static priority": when a process is created, the priority is given in advance, and the priority of the process does not change throughout the run. Generally speaking, kernel processes take precedence over user processes.

Dynamic priority: adjust the priority according to the dynamic changes of the process. For example, as the running time of the process increases, reduce its priority appropriately; as the waiting time of the process in the ready queue increases, increase its priority appropriately.

In addition, it should be noted that the highest priority algorithm is not a fixed preemptive policy or non-preemptive policy, "the system can specify which strategy to use in advance":

Non-preemptive: when a high-priority process appears in the ready queue, select the high-priority process after running the current process.

Preemptive: when a high priority process appears in the ready queue, the CPU resources of the currently running process are forcibly deprived and allocated to the higher priority process to run.

At this point, the study of "what are the classic process scheduling algorithms" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.