<> 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