<> Processor scheduling
one , What is processor scheduling ?
Is from the ready queue Select a process according to a certain algorithm and Assign the processor to it to run
two , Three levels of scheduling
1, Advanced scheduling ： From the backup queue of external storage choose n Jobs , Establish the corresponding process for it （ establish PCB） （ nothing - > Create state - > Ready ）
Advanced scheduling is the scheduling between external memory and memory , A job can only be transferred in once , Call up once , When the job is transferred in, the corresponding PCB, Delete on transfer out Corresponding PCB
2, Intermediate-Level Scheduling ： Decide which suspended process to recall to memory （ Blocking pending - > Blocking state ）
（ To solve the problem of insufficient memory , The process in suspension is moved to external memory ）
3, Low level scheduling ： From ready queue , According to a certain strategy , Assign the processor to him （ Ready - > Running state ）
<> Process scheduling （ Low level scheduling ）
one , Timing of process scheduling
1, When do I need process scheduling ?
（1） The currently running process actively abandons the processor ;
（2） The currently running process passively abandons the processor
2, When can't process scheduling ?
（1） In the process of processing interrupt . The operation process of interrupt is complex , Hardware support is required , It is difficult to switch processes during an interrupt clock
（2） Process in Operating system kernel program critical area in （ Switch at this time , May cause errors ）
（3） During primitive execution .
two , Process scheduling mode
（1） Non deprivation scheduling mode ： Only processes are allowed to actively abandon the processor
（2） Deprivation scheduling mode ： When a process is executing , If there is a more urgent process task , Pause the executing process immediately , Assign processors to emergency processes
three , Process switching and process
1, What is process switching ?
Process switching refers to a process giving up the processor , A process in which a processor is occupied by another process
2, Process switching
（1） Save various operation book data of the original process
（2） Various data recovery for new processes
<> Evaluation index of scheduling algorithm
one ,CPU Utilization calculation
two , Calculation of system throughput
three , Calculation of turnaround time
four , waiting time
five , response time
<> scheduling algorithm
one , First come, first served （FCFS）
（1） Algorithmic thought ： Mainly from “ fair ” From the perspective of
（2） algorithmic rule ： According to the operation / process Service in the order of arrival
（3） For job / Process scheduling ：
When used for job scheduling , Consider which job arrives in the backup queue first ; For process scheduling , Consider which process arrives first Ready queue
（4） No preemption
（5） advantage ： fair , The algorithm is simple to implement
（6） shortcoming ： Favorable for long-term operation , Short work is unfavorable
（7） Will not lead to hunger
two , Short homework first SJF
（1） Algorithmic thought ： Pursue minimum average waiting time , Minimum average turnaround time , Minimum average weighted turnaround time
（2） algorithmic rule ： Shortest job / process Give priority to services
（3） For job / Process scheduling
（4）SJF and SPF Non preemptive algorithm , The shortest remaining time first algorithm yes Preemptive
（5） advantage ： Shortest average waiting time , average turnaround time
（6） shortcoming ： unfair , Unfavorable to long-term operation
（7） Can lead to hunger
three , High response ratio is preferred HRRN
（1） Algorithmic thought ： Comprehensive consideration of operation / process Waiting time and required service time
（2） algorithmic rule ： At every scheduling Calculate various operations / process Response ratio of , Priority shall be given to those with high response ratio , Serve it
（3） For job / Process scheduling
（4） Non preemptive
（5） advantage ： Will not lead to hunger , Relative fairness
four , Time slice rotation
（1） Algorithmic thought ： Serve each process in a fair rotation , Let each process get a response within a certain time
（2） algorithmic rule ： In the order in which the processes are in the ready queue , Take turns to execute a time slice , If you haven't finished running by the time , Just deprive the processor , Put the process back End of ready queue
（3） For job / process dispatch
（4） It is preemptive
（5） advantage ： fair , Fast response , It won't cause hunger
（6） shortcoming ： Due to high frequent switching processes , It will increase the cost , And there is no distinction between the urgency of the task
five , priority scheduling
（1） Algorithmic thought : According to the urgency of the task , To determine the processing order
（2） algorithmic rule ： Scheduling time Select the job with the highest priority / process
（3） For job / process dispatch
（4） seize , Non preemptive
（5） Suitable for real-time operating system
（6） shortcoming ： Can cause hunger
six , Multilevel feedback queue scheduling algorithm （ Put together optimum ）
(1) Algorithmic thought : Tradeoffs with other scheduling algorithms
（2） algorithmic rule ：
1, Set multi-level ready queue , Queue at all levels Priority from high to low , Time slice from small to large
2, When a new process arrives , First in 1 Level queue , Wait in line according to the first come, first come principle Assigned time slice ;
If you run out of time slices , The process is not over yet , Then it enters the queue of the next level ;
If it is already Lowest level queue , Then put it back at the end of the team .
3, Only when k Level queue is empty ,k+1 Level queue To be assigned to a time slice
（3） For job / Process scheduling
（4） It is preemptive ： When k Processes in the tier queue are running , If stay 1~ k -1 A new process has entered the tier queue , The new process will preempt the processor
（5） advantage ： For each type of process Relative fairness
（6） shortcoming ： Can lead to hunger
Technology