A priority scheduling algorithm

1. First come, first served Scheduling algorithm (FCFS)

When this algorithm is used in job scheduling, each schedule selects one or more jobs from the standby job queue that enter the queue first, calls them into memory, allocates resources to them, creates processes for them, and then puts them into the ready queue. When FCFS algorithm is adopted in process scheduling, each schedule selects a process that first enters the queue from the ready queue, allocates processors to it, and puts it into operation. The process runs until the completion or the occurrence of an event and blocked before abandoning the processor, the characteristics are: the algorithm is relatively simple, can achieve basic fairness.

2. Short-job (process) priority scheduling algorithm

Short Job First (SJF) scheduling algorithm selects one or more jobs with the shortest estimated running time from the backup queue and calls them into memory to run. The short process first (SPF) scheduling algorithm selects a process with the shortest estimated running time from the ready queue and assigns the processor to it, so that it can execute immediately and execute until completion, or re-schedule when an event occurs and the processing is blocked and abandoned. This algorithm does not take care of urgent jobs.

Two high priority priority scheduling algorithm

The highest priority priority (FPF) scheduling algorithm is introduced to take care of urgent jobs and make them get priority after entering the system. When the algorithm is used in job scheduling, the system will select several jobs with the highest priority from the backup queue and load them into memory. When used for process scheduling, the algorithm assigns the processor to the process with the highest priority in the ready queue.

1. Non-preemptive priority algorithm

In this way, once the system assigns the processor to the process with the highest priority in the ready queue, the process will continue to execute until it completes. Or an event causes the process to abandon the handler. This scheduling algorithm is mainly used in batch processing system. It can also be used in some real-time systems with lax requirements on real-time performance.

2. Preemptive priority scheduling algorithm

In this way, the system also assigns the processor to the process with the highest priority for execution. However, as soon as another process with a higher priority appears during its execution, the process scheduler immediately stops the execution of the current process (the original process with the highest priority) and reassigns the processor to the new process with the highest priority. Obviously, this preemptive priority scheduling algorithm can better meet the requirements of urgent jobs, so it is often used in real-time systems with strict requirements, as well as batch and time-sharing systems with high performance requirements.

3. High response ratio priority scheduling algorithm

In batch processing system, short job first algorithm is a better algorithm, but its main disadvantage is that long job can not be guaranteed. If we can introduce the aforementioned dynamic priority for each job and make the priority of the job increase at rate A as the waiting time increases, then long jobs must have a chance to be assigned to the processor after waiting a certain amount of time. The change rule of the priority can be described as follows:

  • (1) If the waiting time of the job is the same, the shorter the service time is required, the higher the priority is. Therefore, this algorithm is conducive to short jobs.
  • (2) When the service time is the same, the priority of the job is determined by its waiting time, the longer the waiting time, the higher the priority, so it realizes the first come, first served.
  • (3) For a long job, the priority of the job can be increased with the increase of waiting time. When the waiting time is long enough, the priority of the job can be increased to a high level, so that the processor can be acquired. In short, the algorithm not only takes care of short jobs, but also considers the order of job arrival, so that long jobs will not be unserved for a long time. Therefore, this algorithm achieves a good compromise. Of course, when using this algorithm, the response ratio must be calculated before each scheduling, which will increase the system overhead.

The third is the scheduling algorithm based on time slice

1. Time slice rotation method

In the early time slice rotation method, the system arranged all ready processes into a queue according to the principle of first come, first served, and allocated CPU to the first queue process and ordered it to execute a time slice each time. Time slices range in size from a few ms to several hundred ms. When the execution time slice runs out, a timer sends a clock interrupt request, the scheduler will stop the execution of the process according to the signal, and send it to the end of the ready queue; The processor is then assigned to a new queue leader process in the ready queue, which also executes a time slice. In this way, all processes in the ready queue can obtain the execution time of the processor in a given time slice.

2. Multi-level feedback queue scheduling algorithm

  • (1) Multiple ready queues should be set up, and different priorities should be assigned to each queue. The first queue has the highest priority, the second queue has the lowest priority, and the remaining queues have their priorities reduced one by one. The size of the execution time slice assigned to each process in the queue is also different. In the queue with higher priority, the execution time slice assigned to each process is smaller. For example, the second queue’s slice is twice as long as the first queue’s slice… , the time slice of queue I +1 is twice as long as queue I.
  • (2) When a new process enters the memory, it is first put into the end of the first queue and queued for scheduling according to the FCFS principle. When it is the turn of the process to execute, if it can complete within the time slice, it is ready to leave the system; If it is not completed at the end of a time slice, the scheduler puts the process to the end of the second queue and waits for the schedule to execute again according to FCFS principles. If it does not complete after running a time slice in the second queue, then it is put in the third queue in turn… So, when a long job (process) is relegated from queue 1 to queue NTH, queue NTH takes a time-slice rotation.
  • (3) Only when the first queue is idle, the scheduler schedules the processes in the second queue to run; The processes in queue I are scheduled to run only when queues 1 to (i-1) are empty. If a new process enters the queue with a higher priority (any queue from 1 to (I-1)) while the processor is serving a process in the i-th queue, the new process will preempt the processor of the running process, that is, the scheduler will put the running process back to the end of the I-th queue. Assign a processor to a newly arrived high-priority process. In the multi-stage feedback queue scheduling algorithm, if the time slice of the first queue is slightly larger than the processing time required by most human-computer interactions, it can better meet the needs of various types of users.