PS: In a multi-process concurrent environment, although conceptually, there are multiple processes executing at the same time, but under a single CPU, at any time Only one process can be in the execution state, and the other processes are in the non-execution state. So the question is, how do we determine which process is executed at any time and which is not executed? This involves an important part of process management: process scheduling, follow this article to review process scheduling together!

First, process scheduling basics

1.1 Process scheduling definition

　　Process schedulingis an important part of operating system process management, its The task is to select the next process to run.

1.2 Process scheduling goals

　　 First of all, the general program tasks are divided into three types: CPU computing intensive For different types of programs, scheduling needs to achieve different goals. For IO-intensive, response time is the most important; for CPU-intensive, turnaround time The most important; and for the balanced type, a balance between response and turnover is more important.

　　 Therefore, the goal of process scheduling is to minimize the average response time, maximize the system throughput, keep the various functional components of the system busy, and provide a seemingly fair mechanism .

PS: Why do you want to keep all the functional parts of the system busy? Because the CPU is very expensive, leaving it idle is a waste, so keeping the CPU busy is very important. Just as life is very precious, we will not waste our lives unless we keep learning to stay fulfilled.

2. Basic scheduling algorithm

2.1 First come first serve algorithm

　　 First-come, first-served (FCFS) algorithm is one of the most common algorithms, it is a fair concept in human nature. The advantage is that simple and easy to implement, the disadvantage is that short jobs may become Very slow, because there is a long work in front of it, which will cause the user’s interactive experience to be relatively poor.

　　 For example, when queuing for business, the business you want to handle can be done in a few minutes, but the one person in front of you is very complicated and takes 1 hour, then you need to be behind him Waiting for a long time, so you think: if everyone takes turns to handle 10 minutes of affairs, then how great! So the time slice rotation algorithm appeared.

2.2 Time slice rotation algorithm

　　Time slice rotation is an improvement of the FCFS algorithm. Its main purpose is to improve the response time of short programs. The implementation method is Periodic process switching. Time slice rotation the focus is on the choice of time slice, and many factors need to be considered: if it’s running When there are many processes, the time slice needs to be shorter; when the number of processes is small, the time slice can be appropriately longer. Therefore, the choice of time slice is a comprehensive consideration, weighing the interests of all parties and making an appropriate compromise.

　　 However, the system response time of time slice rotation is not always shorter than the response time of FCFS. Time slice rotation is a kind of big pot meal, but in real life it is taking the route of “some people get rich first, get rich first lead to get rich later”. For example, if there are 30 tasks, one of the tasks only takes 1 second to execute, while the other 29 tasks take 30 seconds to execute. If for some reason, this one-second task ranks behind the other 29 tasks. Rotation, it needs to wait for 29 seconds to execute (assuming the time slice is 1 second). As a result, the response time and interactive experience of this task become very poor. Therefore, the short-task priority algorithm is proposed.

2.3 Short task priority algorithm

　　 The core of the short task priority algorithm is All tasks are not all the same, but are differentiated by priority. Specifically, short tasks have higher priority than long tasks span>, and we always schedule high priority tasks to run first.

　　Short task priority algorithm is divided into two types: one is non-preemptive, the other is Preemptive. Non-preemptive type When a task that is already running on the CPU ends or is blocked, from candidate tasks Select the process with the shortest execution time to execute. and preemptive is every time a new process is added, all processes (including processes running on the CPU) need to be checked , Whoever runs in a short time.

　　 Since short tasks always run the program with the shortest execution time, the average system response time is in the above algorithms Medium is the best, which is also the advantage of the short-task priority algorithm. But the short task priority algorithm also has disadvantages: First, it may cause long tasks to fail to get CPU time and cause “muscle hungry”. The second is How do I know how long each process needs to run? So in order to solve the first shortcoming, a priority scheduling algorithm was proposed. The second shortcoming can be estimated by some heuristic methods, and many artificial intelligence algorithms can do this.

2.4 Priority scheduling algorithm

　　Priority scheduling algorithm gives each process a priority, and each process needs to be switched When, find a process with the highest priority for scheduling. In this way, if a long process is given a high priority, the process will no longer be “starved”. In fact, the short task priority algorithm itself is a priority scheduling, but it gives higher priority to short processes.

　　The advantage of this algorithm is that it can give important processes a high priority to ensure that important tasks can get CPU time, its disadvantages There are two: one is low-priority processes may be “starved”, and the other is Response time cannot be guaranteed. The first shortcoming can be solved by dynamically adjusting the priority of the task. For example, if a process waits for too long, its priority will surpass the priority of other processes due to continuous improvement. Level to get the CPU time. The second shortcoming can be solved by setting the priority of a process to the highest, but even if the priority is set to the highest, if everyone sets their process priority to the highest, the response time is still not guaranteed.

2.5 Hybrid scheduling algorithm

　　 The previous algorithms have certain shortcomings, so can there be a hybrid algorithm? Their advantages, abandon their shortcomings, this is the so-called hybrid scheduling algorithm. The hybrid scheduling algorithm divides all processes into different categories, and each category is a priority. If two processes are in different categories, the process in the higher priority category will be executed first; if they are in For the same category, the time slice rotation algorithm is used to execute. The schematic diagram of the hybrid scheduling algorithm is shown in the figure below:

2.5 Process scheduling process

< img alt="share picture" style="display: block; margin-left: auto; margin-right: auto;" src="/wp-content/uploads/images/os/ostheory/1626797042241.png" >

3. Priority inversion for scheduling exceptions

3.1 What is priority inversion?

　　 Priority inversion refers to is a low-priority task holding a shared resource required by a high-priority task. In this way, high-priority tasks are blocked due to lack of resources until the low-priority tasks release resources. This actually caused the priority of these two tasks to be upside down.

3.2 The manifestation of priority inversion

　　(1)Low priority processes that do not hold resources hinder the need for resources The execution of the high-priority process of ;

　　(2)The priority process that holds the resource hinders the high-priority process that needs the resource The execution of the process;

3.3 Prevention of priority inversion

　　 (1) For the first form, you can use The method of interrupt prohibition, its core is to protect the critical section by disable interruption.

　　 (2) For the second form, cannot let low-priority processes hold the resources needed by high-priority processes , You can through the upper limit of priority and priority inheritance to achieve.

　　 Priority upside down problem, we will learn in detail later, and then we will talk about it in detail. Of course, If you want to know what’s going on, please see the next breakdown.

Reference materials

Zou Hengming, “The Philosophical Principles of Operating System”, Machinery Industry Press