CPU dispatch ： control , Coordination process pair CPU Competition ; According to a certain scheduling algorithm , Select a process from the ready sequence , hold CPU The right to use is given to the selected process ; If there is no ready process , The system will schedule a system idle process or idle process ;
System scenario ：N Processes ready , Wait up CPU function ;M individual CPU,M>=1; Need decision ： Which process is assigned which CPU
CPU Scheduling problems to be solved 3 Question ：what： According to what principles is the next process to be implemented , scheduling algorithm ;when： Appropriate choice , Scheduling timing ;how： How to make the selected process CPU function , Scheduling process ( Context switching of processes )
CPU Scheduling timing ： Event occurrence —- The currently running process is paused —- After the hardware mechanism responds —- Enter the operating system , Handle corresponding events —- After processing ： The state of some processes will change , Some new processes may also be created —- The ready queue has changed —- Process scheduling is required. Select a process from the ready queue according to the preset scheduling algorithm . Including the following 4 Cases ：
The process terminated normally or Terminated due to some error
New process creation or A waiting process becomes ready
When a process enters the waiting state from the running state
When a process changes from running state to ready state
Scheduling process —— Process switching ： Give up a process CPU, Occupied by another process CPU Process of ; It includes the preservation of various states of the original running process and the restoration of various states of the new process . Two things to do when switching ：
1 Switch global page directory with Load a new address space
2 Switch kernel stack and hardware context , The hardware context includes all the information that the kernel needs to execute the new process , as CPU Correlation register
Specific steps of context switching ： process a lower CPU, process b upper CPU
Save process a Context of ( Program counter , Program status word , Other registers )
Update the process with new status and other relevant information a of PCB
Put process a Move to the appropriate queue ( be ready , block ..)
Will process b The status of is set to running status
Slave process b of PCB Restore context in ( Program counter , Program status word , Other registers ..)
Context switching overhead ： Direct cost ： The time used by the kernel to complete the switch CPU time ; Overhead ： Cache cache, Buffer cache ,TLB invalid
CPU Scheduling algorithm metrics ：
throughput ： Number of processes completed per unit time
Turnaround time ： The time between the request and the completion of each process
response time ： Time from request to first response
other :CPU Utilization rate ,CPU Percentage of time spent doing effective work ; waiting time , The time each process waits in the ready queue
Process priority ( number )：
priority , Reflect urgency ;
Priority number , Reflect priority ,UNIX A small number of priorities has a high priority ;
static state , Dynamic priority . Long waiting dynamic priority high
Preemption and non preemption ：
seize ： When high priority processes are ready , The system can forcibly deprive processes with low priority CPU Give priority to high priority processes first
non preemption ： Unless you give up CPU, Otherwise, it will run all the time
I/O Intensive and CPU Intensive ：
I/O Intensive ,I/O type , Frequent I/O, It usually takes a lot of time to wait I/O Operation complete ; General I / O program pair i/o More friendly
CPU Intensive , Need a lot of CPU Time to calculate
Time slice
A time period , Assign to dispatcher CPU Process of , The length of time the process is allowed to run
How to select a time slice ： Consider process switching overhead , Requirements for response time , Number of ready processes ,CPU ability , Process behavior
Scheduling algorithm used in batch processing system ： First come, first served , Shortest job first , Shortest remaining time first , Highest response ratio priority
Algorithm selection principle ： throughput , Turnaround time ,CPU Utilization rate , Fair service
First come, first served FCFS： fifo , Use in order of process readiness CPU, non-preemptive
fair , Simple implementation , A short process after a long process takes a long time , Not conducive to the user experience
Shortest job first SJF： The process with the shortest completion time shall be executed first , non-preemptive
Shortest remaining time first SRTN： namely sjf Preemptive version of , When a newly ready process has a shorter completion time than the currently running process , The system preempts the current process , Select a new ready process to execute
Short job first scheduling algorithm ： Shortest average turnaround time ( If all processes can run at the same time ); unfair ( A steady stream of short tasks are coming , Long tasks may not be run for a long time , Produce hunger
Highest response ratio priority HRRN： Trade off , First come, first serve and short homework first learn from each other
Scheduling time , First calculate the response ratio of each process R; after , Always choose R Highest process execution
Response ratio R= Turnaround time / processing time =( processing time + waiting time )/ processing time = 1+( waiting time / processing time )
Scheduling algorithm used in interactive system ： round-robin scheduling , Highest priority scheduling , Multilevel feedback queue , Shortest process first ; Pursuit index ： response time , Fair balance ;
Time slice rotation scheduling algorithm ： target ： Improve average response time for short tasks , Solve periodic switching , Each process is assigned a time slice , Clock interrupt – Rotation .
How to choose the right time slice ： Too long – Greater than typical interaction time – Degenerate into first come first serve algorithm , Extended response time for short processes ; Too short – Less than typical interaction time – Process switching waste CPU time ; Empirical value 50ms about ;
Advantages and disadvantages of time slice rotation algorithm ： fair , Conducive to interactive computing , Fast response time , Due to process switching , The time slice rotation algorithm costs high overhead ,RR It is beneficial for processes of different sizes , But it may be bad for processes of the same size
Virtual rotation algorithm ： All I/O Type process , From waiting to ready , Enter auxiliary queue , Scheduling algorithm when selecting process , First select the process from the secondary queue , Until the secondary queue is empty , Then execute the ready queue , The time slice rotation algorithm is improved I/O Injustice of type process
Highest priority scheduling algorithm ：
Select the process with the highest priority and put it into operation ;
System processes are generally higher than user processes ; The foreground process is generally higher than the background process ; Operating system preference i/o Type process ;
Priority can be static , It can also be dynamic ： The priority number can determine the priority
Ready queues can be organized by priority
Simple implementation ; unfair , It is easy to cause starvation in processes with low priority
priority inversion problem ：
Priority based preemptive ： A low priority process occupies the resources required by a high priority process , Make the high priority process wait for the low priority process to run ;
influence ： System error ; High priority process stalled , Resulting in reduced system performance
Solution ：
(1) Set upper priority limit ： All processes entering the critical zone , Give it a high priority , Easy to finish first , Give back control of the critical area , Not entering the critical zone , Give low priority ;
(2) priority inheritance ： Low hinders high , He can inherit this high priority , Finish the task first , Return the critical area
(3) Use interrupt prohibition ： Processes that enter the critical zone no longer respond to interrupts , He didn't respond to the interrupt until he was out of the critical zone , It protects the process , Let him do it , Until the critical area is returned
Multilevel feedback queue scheduling algorithm ：
Set up multiple ready queues , The first level queue has the highest priority
Allocate time slices of different lengths to processes in different ready queues , Minimum first level queue time slice , Level reduction , The time slice becomes longer
The first level queue is empty yes , Scheduling in the second level queue , and so on
Each queue is scheduled according to time slice rotation
When a new creation process is ready , All enter the first level queue
When the process runs out of time slices , And give up CPU, Enter the next level ready queue
Give up due to blocking CPU Process entry
Comparison of various scheduling algorithms
FCFS
Round Robin
SJF
SRTN
HRRN
Feedback
Design of multiprocessor scheduling algorithm ：
It's not just about deciding which process to choose to execute , You have to decide where to go CPU Upper execution ;
To consider processes in multiple CPU Cost of migrating between , As far as possible, the process should always be in the same place CPU Upper execution , Consider the load balancing problem
Scheduling algorithm used in typical operating system ：
UNIX： Dynamic priority number method
5.3BSD： Multilevel feedback queue method
Linux： preemptive scheduling
Windows： Priority based preemptive multitask scheduling
Solaris： Integrated scheduling algorithm
Linux Evolution process of scheduling algorithm ：
Linux2.4 Simple priority based scheduling
Linux2.6 O(1) scheduling algorithm
Linux2.6 SD Scheduler patch
Linux2.6 RSDL Scheduler patch
Linux2.6 CFS scheduling algorithm ( Fully fair scheduling algorithm )
Windows Thread scheduling for ：
The scheduling unit is thread ( because Windows The system supports kernel level threads )
Dynamic priority based , preemptive scheduling , Combined with the adjustment of time quota
basic thought ：
Ready threads enter different ready queues according to priority
The operating system always selects the highest priority ready thread to run
Threads with the same priority are scheduled according to time slice rotation
many CPU Multiple threads are allowed to run in parallel in the system
Windows Thread scheduling ：
Condition that triggers thread scheduling ： The priority of a thread has changed
A thread changed its affinity processor set
Normal thread termination or Terminated due to some error
New thread creation or A waiting thread becomes ready
When a thread enters blocking state from running state
When a thread changes from running state to ready state
thread priority ：
windows use 32 Thread priority , Divide 3 class ：
16-31： Real time priority thread , Once determined, the priority will not be changed
1-15： Variable priority ： It can be raised or lowered within a certain range , Basic priority , Current priority
0： Zero page thread ： Used to clear the physical page of the system
time quantum ： Give more time quota , It's like giving a process more time to run
Windows Thread scheduling strategy ：
Active switching
seize ： When a thread is preempted , It is put back to the head of the ready queue of the corresponding priority ; When a thread at real-time priority is preempted , The time quota is reset to a full time quota , On again CPU When running, a complete time quota is run ; When a thread with variable priority is preempted , Time quota unchanged , Regain CPU The remaining time quota will run after . Distinguish between two different types of threads
Time quota used up ：1
2
3 thread a The priority of is not reduced ： If there are other ready threads in the queue , Select the next thread to execute ,a Return to the end of the original ready queue ; If there are no other ready threads in the queue , System to thread a Reassign a new time quota , Keep him running ;
thread a The priority of is reduced ：Windows A higher priority thread will be selected to run ;
Thread priority promotion and time quota adjustment ：1
2
3 Raise the priority of threads
Assign a large time quota to threads
Raise thread priority ：( For variable priority threads only )1
2
3
4
5
6
7
8
9I/O Operation complete
Semaphore or time wait end
The thread in the foreground process completes a wait operation
Wake up window thread due to window activity
The thread has been in the ready state for more than a certain time and has not been scheduled to run ( There is hunger )
Technology