20、 Processor scheduling (RR time slice rotation, mlfq multi-level feedback queue, CFS fully fair scheduler, priority reversal; multiprocessor scheduling)

One 、 Simplified processor scheduling problem

Interrupt mechanism

1、 The processor is interrupted at a fixed frequency

（1）linux kernel It can be set to ：100/250/300/1000Hz

2、 interrupt / When the system call returns, you can freely select the process / Threads

Simplified assumptions for processor scheduling problems

1、 There is a processor in the system

2、 There are multiple processes in the system / Thread sharing CPU

（1） system call （ process / Part of the thread code is in syscall In the implementation of ）

（2） wait for I/O return , Do not apply CPU

Two 、 Strategy

1、RR（Round-Robin） Time slice rotation

2、 priority

（1）Unix niceness

        -20 ~ 19

The bigger the value is. , Said to CPU The lower priority the resource gets

taskset -c 0 nice -n 19 yes > /dev/null &

taskset -c 0 nice -n 9 yes > /dev/null &

niceness The value difference of 10,CPU Poor resources 10 times

3、 Dynamic priority （MLFQ）

（1） Several RR queue

         Each queue has a priority

（2） Dynamic priority adjustment strategy

         Priority scheduling high priority queues

         Use up the time slice -》NI Low value

4、CFS Completely fair scheduler

（1） Record the exact running time for each process

（2） interrupt / After the exception , Switch to the process with the least running time

         Next time interrupt / After abnormality , The current process may not be the smallest

（3） Maintain collection

        to update vrt（t）<- vrt（t）+dt

        Take the smallest vrt

         Process creation / sign out / sleep / Insert on wakeup / Delete t

3、 ... and 、 Processor scheduling

1、 Priority flipping

Low priority holds the lock waiting for high priority , Lead to high priority processes / The thread is by a low priority process / Thread blocking

（1） Priority inheritance , Low priority holds the same lock as high priority , Will inherit the priority of high priority

2、 Multiprocessor

（1） transfer ,cash Copying consumes resources

（2） Don't move , Can cause CPU waste （ It's hard for one core , Multi core onlookers ）

3、 Single threaded tasks and multithreaded tasks CPU Possession problem

4、 Different types of cores （A55、A75、A78）, To assign tasks, you need to know the core computing power