编程知识 cdmana.com

Linux Process Scheduling Algorithm

First come, first served (FCFS)

   First come, first served scheduling algorithm : The simplest scheduling algorithm , It can be used for job scheduling , It can also be used for program scheduling , When this algorithm is used in job scheduling , The system will schedule jobs according to the order of arrival , Priority from the backup queue , Select one or more jobs at the head of the queue , Put them in memory , Allocate the required resources 、 Create a process , And then put in “ Ready queue ”, Until the process runs to completion or after an event is blocked , The process scheduler assigns processors to other processes

advantage : It's good for long work ( process ) and CPU Busy work ( process )
shortcoming : It's not good for short work ( process ) and I/O Busy work ( process )

Short process priority (SPF)

   Short process priority (SPF) Scheduling algorithm , Is to select a process from the ready queue with the shortest estimated runtime , Assign the processor to it , To carry out immediately , Until the completion or occurrence of an event that blocks , To release the processor
advantage : comparison FCFS Algorithm , The algorithm can improve the average turnaround time and average weighted turnaround time , Shorten the waiting time of the process , Improve system throughput
shortcoming : The algorithm does not consider the urgency of the job , There is no guarantee that urgent work will be handled in a timely manner , Long term work ( process ) There is no guarantee of the implementation of

Rotation scheduling

   Time slice rotation scheduling algorithm is mainly suitable for time-sharing system . In this algorithm , The system queues all ready processes in the order of arrival time , The process scheduler always selects the first process in the ready queue to execute , That is, the principle of first come, first serve , But it can only run one time slice , Such as 100ms. After using a time slice , Even if the process doesn't finish its run , It must also release the processor to the next ready process , The stripped process returns to the end of the ready queue to re queue , Waiting to run again .

   In the time slice rotation scheduling algorithm , The size of time slice has a great influence on system performance . If the time slice is big enough , So that all processes can be executed in a time slice , Then the time slice rotation scheduling algorithm degenerates into a first come first served scheduling algorithm . If the time slice is small , The processor will switch between processes too frequently , Increase the cost of the processor , And the real time spent running user processes will be reduced . Therefore, the size of time slice should be chosen appropriately .

   The length of the time slice is usually determined by the following factors : Response time of the system 、 The number of processes in the ready queue and the processing power of the system

Priority scheduling

   Priority scheduling algorithm is also called priority scheduling algorithm , This algorithm can be used for job scheduling , It can also be used for process scheduling , The priority in the algorithm is used to describe the urgency of job running

   In job scheduling , The priority scheduling algorithm selects one or more jobs with the highest priority from the backup job queue , Put them in memory , Allocate the necessary resources , Create a process and put it in the ready queue . In process scheduling , The priority scheduling algorithm selects the process with the highest priority from the ready queue , Assign the processor to it , Put it into operation

Multi level feedback queue scheduling

Multi level feedback queue algorithm (Round Robin with Multiple Feedback) It is the synthesis and development of rotation algorithm and priority algorithm

Set up multiple ready queues , Give them different priorities , If it's going down step by step , queue 1 The highest priority . The execution time slice length of each queue is also different , The lower the priority, the longer the time slice , If you double step by step .
After the new process enters memory , Put in the queue first 1 At the end of , Press FCFS Algorithm for scheduling ; If by queue 1 A time slice cannot be completed , Then reduce the input to the queue 2 At the end of , According to the same FCFS Algorithm for scheduling ; Go on like this , Down to the last queue , Then press “ Time slice rotation ” Algorithm scheduling until complete .
Only if the higher priority queue is empty , To schedule the execution of processes in lower priority queues . If a new process enters a higher priority queue while the process is executing , The new process will be carried out first , And put the preempted process at the end of the original queue

advantage :
1. Take care of short processes to improve system throughput and reduce average turnaround time .
2. In order to get better I/O Equipment utilization and reduced response time while taking care of I/O Type process .
3. There is no need to estimate the execution time of the process , Dynamic adjustment

版权声明
本文为[Ran1366]所创,转载请带上原文链接,感谢

Scroll to Top