Process scheduling usually occurs in the following situations:
In nonpreemptive scheduling, after a process starts to execute, it can always be executed unless it voluntarily abandons the CPU or is blocked.
In preemptive scheduling, if a higher priority process comes during execution, the right to use the CPU will be taken away, especially in time slice scheduling, even if the time slice is not used up. But preemption can't happen at any time, and poor design may lead to priority inversion or deadlock.
In different scenarios, in order to achieve different goals, the criteria for evaluating scheduling algorithms are different. Here we introduce some commonly used standards:
Fairness: Give each process a chance to use CPU fairly.
Balance: make the best use of all components of the system.
Throughput Throughput: The number of tasks completed per unit time.
Turnaround time: Generally speaking, in a batch processing system, the time interval between submission and completion of a batch processing task.
CPU utilization CPU CPU utilization.
Waiting time: the time that the process waits in the ready queue.
Response time: Generally speaking, in an interactive system, the interval between the user's submission of a task and the first response (the task may not be completed).
Deadline for meeting: In general, data is processed in real-time system to avoid loss or invalidation.
Next, let's look at the scheduling algorithms commonly used in three different types of systems.
1. First come, first served
This is a non-preemptive first-come-first-served algorithm. There is only one ready process queue. If a process is blocked during execution, it will enter the blocking queue, and then it will be queued as a new process to the end of the ready queue.
Advantages: easy to understand and implement.
Disadvantages: the average waiting time is often very long, which is not conducive to balancing CPU-intensive and IO-intensive processes.
2.SJF: Shortest job is preferred.
SJF is also a non-preemptive scheduling, which chooses the shortest task to execute every time.
3. The next shortest remaining time
It is a preemptive version of SJF. When a new task arrives, it will reschedule and select the task with the shortest remaining time.
The problem with SJF and the shortest remaining time Next is that it is usually difficult to judge the remaining execution time of the process. Unless this is a task that needs to be performed frequently, the approximate range of execution time can be determined according to historical statistical analysis.
1. Circular scheduling
Polling scheduling. Give each process the same time slice and execute it in turn. Generally, the time slice is 20-50msec. If it is too short, process switch will waste time, and if it is too long, the response time will be prolonged.
Advantages: Faster response than SJF.
Disadvantages: Long turnaround time.
2. Priority scheduling
Priority scheduling assigns priority to each process, and high priority is executed first, which is also a time slice scheduling algorithm. Priority can be assigned statically or dynamically. In order to prevent high-priority processes from occupying CPU all the time, it can be reduced after sequential execution. Other scheduling algorithms can be used between processes with the same priority, such as round robin scheduling, and different scheduling algorithms can be used for different queues.
Advantages: Introduction is preferred.
3. Multiple queues
In order to avoid frequent process switch of processes with long execution time, time slices with different lengths can be allocated between different priority queues. After the process is executed once, it will be assigned other priorities with longer execution time. For example, if a process needs 100 quantum, it will allocate 1 for the first time, allocate 2 next time, and allocate 4, 8, 16, 32, 64 next time. Compared with the pure polling algorithm that only allocates 1 at a time, it reduces the number of process scheduling.
4. Guaranteed scheduling
None of the algorithms mentioned above can guarantee the CPU time that the process can get, but in some cases, we need to ensure the opportunity and time for the process to use CPU. For example, when n users log in at the same time, it is generally necessary to ensure that each user can get 1/n CPUs, or we can buy VPN service to get certain bandwidth guarantee according to different user levels. This algorithm is called guaranteed scheduling. In the implementation, you need to keep track of the CPU allocated to each process. Compared with the promised allocation, the process with the smallest proportion will get the next use right.
5. Lottery schedule
The lottery scheduling algorithm introduces randomness and issues a lottery ticket for each process. Scheduling is like a lottery. Whoever wins the lottery gets resources. The process with higher priority can get multiple lottery tickets, which improves the winning probability.
The interesting thing about lottery scheduling is that processes can give each other lottery tickets. For example, process 1 pending is on process 2, and it can give all its lottery tickets to process 2 to improve its chances of being scheduled. Return the lottery ticket to process 1 after process2.
6. Fair share scheduling
Let's consider a situation where all processes do not belong to one user, which is very common in Linux systems. If user 1 has 99 processes and user2 has only 1 processes, according to the previous algorithm, user 1 may get 99% CPU, while user2 has only 1%. In order to achieve fairness at the user level, it is necessary to consider which user the process belongs to when scheduling.
There are two real-time systems:
In real-time systems, the task time is generally short, and the scheduler needs to make all processes complete before the deadline. For events that occur periodically, if the period of the event is, the event processing time (the time that needs to occupy CPU) is, and only in this way can it be scheduled.
Can the scheduling algorithm only be implemented by the operating system? Does the process have the right to say which scheduling algorithm to use? The answer is yes. The mechanism is separated from the policy, and the operating system provides various implementation mechanisms and system calls. The process passes parameters to the OS to specify which scheduling policy to use.
If the thread is implemented in user mode, then two levels of scheduling are needed, with the OS responsible for scheduling the process and the process responsible for scheduling the thread. If the thread is implemented in kernel mode, the operating system directly schedules the thread, regardless of which process it belongs to.