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


Round Robin





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


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


3 Raise the priority of threads

Assign a large time quota to threads

Raise thread priority :( For variable priority threads only )1








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 )