创作人QQ：851301776，邮箱：lfr890207@163.com
? ? ? ? 欢迎大家一起技术交流，本博客主要是自己学习的心得体会,只为每天进步一点点！
个人座右铭：
? ? ? ? ?1.没有横空出世，只要厚积一定发。
? ? ? ? ?2.你可以学历不高，你可以不上学，但你不能不学习
?
一、调度器
1.核心调度器
调度器的实现是基于两个函数：周期性调度函数和主调度函数。这些函数根据现有进程的优先级分配CPU时间。这也是为什么整个方法称之为优先调度的原因。
（1）周期性调度器函数
????????函数名：scheduler_tick
????????周期性调度器在scheduler_tick中实现，如果系统正在活动中，内核会按照频率自动调用该函数，该函数主要有两个任务：
????????a.更新相关统计量：管理内核中与整个系统和各个进程的调度相关的统计量。期间执行的主要操作是对各种计数器加1.主要函数：update_rq_clock()/calc_global_load_tick()
????????b.激活负责当前进程的调度类的周期性调度方法。
（2）主调度器函数
? ? ? ? 在内核中的许多地方，如果要将CPU分配给与当前活动进程不同的另一个进程，都会直接调用主调度器函数（schedule）。
? ? ? ? 主调度器负责将CPU的使用权从一个进程切换到另一个进程，周期性调度器只是定时更新调度相关的统计信息。cfs队列实际上是用红黑树组织的，rt队列是用链表组织的。
2.调度类及运行队列
（1）调度类
? ? ? ? 为方便添加新的调度策略，Linux内核抽象一个调度类sched_class,目前为止实现5种调度类：
? ? ? a.停机调度类：支持限期调度类，迁移线程的优先级必须比限期进程的优先级高，能够抢占所有其他进程，才能够快速处理调度器发出的迁移请求，把进程从当前处理器迁移到其他处理器。
? ? ? ?b.限期调度类：使用优先算法（红黑树）把进程按照绝对截止期限从小到大排序，每次调度时选择绝对截止期限最小的进程。
? ? ? ?c.实时调度类：为每个调度优先级维护一个队列（struct list_head queue[MAX_RT_PRIO]),位图bitmap用来快速查找第一个非空队列，数据组queue的下标是实时进程的调度优先级，下标越小，优先级越高。
? ? ? ?d.公平调度类：使用完全公平调度算法，引入虚拟运行时间：
? ? ? ? 虚拟运行时间=实际运行时间*nice? ?0对应的权重/进程的权重? ?
? ? ? ? nice 0对应权重是1024，nice n-1的权重大概是nice n权重的1.2倍左右
? ? ? e.空闲调度类：每个处理器上有一个空闲线程，即0号线程。空闲调度类的优先级最低，仅当没有选择其他进程可以调度的时候，才会执行调度空闲线程。
（2）运行队列
? ? ? ? ? 每个处理器有一个运行队列，结构体是rq，rq是描述就绪队列，其设计是为每一个CPU就绪队列，本地进程在本地队列上排序;
? ? ? ? struct rq结构体中嵌入公平运行队列cfs、实时运行队列rt、限期运行队列dl、停机调度类和空闲调度类，在每个处理器上只有一个内核线程，不需要运行队列，直接定义成员stop/idle分别指向迁移线程的空闲线程。
3.调度进程
? ? ? ? 主动调度进程的函数是schedule（），它会把工作委托给函数__schedule()去处理。
? ? ? ? 函数__schedule的主要处理流程如下:
? ? ? ? a.调用函数pick_next_task（）以选择下一个进程
? ? ? ? ? ? ?停机调度器选择下一个进程：pick_next_task_stop
? ? ? ? ? ? ?限期调度类选择下一个进程：pick_next_task_dl
? ? ? ? ? ? ?实时调度类选择下一个进程：pick_next_task_rt
? ? ? ? ? ? ?公平调度类选择下一个进程：pick_next_task_fair
? ? ? ? b.调用context_switch（）以切换进程
? ? ? ? ? ?切换进程主要包括以下几方面：
? ? ? ? ? ? ? ? --切换用户虚拟地址空间，ARM64架构使用默认的switch_mm_irqs_off. 函数为switch_mm
? ? ? ? ? ? ? ? --切换寄存器，宏switch_to把这项工作委托给函数__switch_to;
4.调度时机
? ? 进程调度简称的时机如下：
? ? ? ?a.进程主动调用schedule()函数
? ? ? ?b.周期性的调度，抢占当前进程，强迫当前进程让出处理器
? ? ? ?c.还行进程的时候，被唤醒的进程可能抢占当前进程
? ? ? ?d.创建新进程的时候，新进程可能抢占当前进程
（1）主动调度
? ? ? ? 进程在用户模式下运行的时候，无法直接调用schedule()函数，只能通过系统调用进入内核模式，如果系统调用需要等待某个资源，如互斥锁或信号量，就会把进程的状态设置为睡眠状态，然后调用schedule()函数来调度进程。
? ? ? ? 内核态和用户态切换：
? ? ? ? 内核态：CPU可以访问内存所有的数据，包括外围设备（网卡、硬盘等），CPU也可以将自己从一个程序切换至另一个程序
? ? ? ? 用户态：只能首先的访问，并且不允许访问外围设备，占用CPU的能力被剥夺，CPU资源可以被其他进程获取。
（2）周期调度
? ? ? ? 有些进程不主动让出CPU，内核只能依靠周期性的时钟中断夺回处理器的控制权，时钟中断是调度器的脉搏，时钟中断处理程序检查当前进程的执行时间有没有超过限额，如果超过限额，设置需要重新调度的标志。当时钟中断处理程序准备返点处理器还给被打断的进程时，如果被打断的进程在用户模式下运行，就检查有没有设置需要重新调度的标志，如果设置了，调用schedule函数以调度进程。
二、SMP调度
在SMP系统中，进程调度器必须支持如下：
? ?a.需要使用每个处理器的负载尽可能均衡
? ?b.可以设置进程的处理器亲和性，即运行进程在那些处理器上执行
? ?c.可以把进程从一个处理器迁移到另一个处理器
1.进程的处理器亲和性
? ? ? ? 设置进程的处理器亲和性，通俗就是把进程绑定到某些处理器，只允许进程在某些处理器上执行，默认是可以在所有处理器上执行.
? ? ? ? 应用编程接口内核只有2个系统调用：
? ? ? ? ????????a.sched_setaffinity:设置进程的处理器亲和性掩码
? ? ? ????????? b.sched_getaffinity:用来获取进程的处理器亲和性掩码
? ? ? ? 内核线程可以使用两个函数来设置处理器的亲和性掩码：
? ? ? ? ? ? ? ? a.kthread_bind用来把一个刚刚创建的内核线程绑定到一个处理器
? ? ? ? ? ? ? ? b.set_cpus_allowed_ptr用来设置内核线程的处理器亲和性掩码
2.限期调度类的处理器负载均衡
? ? ? ? 限期调度类的处理器负载均衡很简单，调度选择下一个限期进程的时候，如果当前正在执行的进程是限期进程，将会试图从限期进程超载的处理器把限期进程搞过来。
? ? ? ? 限期进程超载定义：
? ? ? ? ? ? ? ? a.限期运行队列至少有两个限期进程
? ? ? ? ? ? ? ? b.至少有一个限期进程绑定到多个处理器
3.实时调度类的处理器负载均衡
? ? ? ? 实时调度类的处理器负载均衡和限期调度器类相似。调度器选择下一个实时进程时，如果当前处理器的实时运行队列中的进程的最好调度优先级比当前正在执行的进程的调度优先级低，将会试图从实时超载的进程处理器把可推送实时进程拉过来。
? ? ? ? 实时进程超载定义：
? ? ? ? ? ? ? ? a.实时运行队列至少有两个实时进程
? ? ? ? ? ? ? ? b.至少有一个可推送实时进程
4.公平调度类的处理器负载均衡
? ? ? ? 目前多处理器系统有两种体系结构：NUMA和SMP。
? ? ? ? 处理器内部的拓扑如下：
? ? ? ? ? ? ? ? a.核（core）：一个处理器包含多个核，每个核独立的一级缓存，所有核共享二级缓存。
? ? ? ? ? ? ? ? b.硬件线程：也成为逻辑处理器或者虚拟处理器，一个处理器或者核包含多个硬件线程，硬件线程共享一级缓存和二级缓存。MIPS处理器的叫法是同步多线程（Simultaneous Multi-Threading,SMT）,英热尔对它的叫法是超线程。
三、附
1.用户态和内核态的切换流程
? ? ? ? 用户态-->内核态（发生系统调用的时候、发生异常的时候：缺页异常、外设产生中断的时候）
2.内核常用内存分配函数
? ? ? ? ????????alloc_pages/vmalloc/kmem_cache_alloc/kmalloc(malloc)/dma_calloc_coherent/ioremap