Linux中进程的调度

Deadline > Realtime > Fair，这意味着 Linux 选择下一个任务执行的时候，会按照此优先级顺序进行选择，也就是说先从 dl_rq 里选择任务，然后从 rt_rq 里选择任务，最后从 cfs_rq 里选择任务

Linux将按照优先级分为两种，优先级数值越小的优先级越高，实时任务优先级在099，普通任务在100139，针对不同的任务有不同的调度策略

普通任务

Deadlind和RT调度器

• 调度策略

  • SCHED_DEADLIND ：按照deadline继续调度，距离当前时间点最近的deadline的任务会被调度

  • SCHED_FIFO：对于相同优先级的任务按照先来先到的原则，但是优先级更高的任务可以抢占优先级低的任务

  • SCHED_RR：对于相同优先级发任务轮流运行，每个任务都有一定的时间片，时间片用完会被放到队尾保证相同优先级任务的公平性，但是高优先级任务可以抢占低优先级任务

• 运行队列

  • dl_rq、rt_rq

实时任务

CSF调度器

• 调度策略

  • SCHED_NORMAL：普通任务使用的调度策略

  • SCHED_BATCH：后台任务的调度策略，不和终端进行交互，因此在不影响其他需要交互的任务可以适当降低优先级

• CFS完全公平调度算法

  • 理念：实现任务运行的公平性，保障每个任务的运行时间差不多

  • 使用虚拟运行时记录进程已经消耗了多少CPU时间，如果消耗得少那么就优先被调度；同时根据进程的权重计算虚拟运行时的增加，权重越高的进程虚拟运行时增加得越少（比如同样是增加了250ns的虚拟运行时，权重低的进程实际获取的CPU时间只有200ns，权重高的进程获得300ns）

    • 权重有优先级得来，但是会保证权重不会高于实时任务的优先级

• 运行队列cfs_rq

  • 使用红黑树实现，按照虚拟运行时排序，最左侧的叶子节点就是下一次会被调度的任务

Linux进程调度器发展

O(n)调度器

• 设计理念

  • 将时间分成大量时间片，每个时间片开始时调度器从就绪队列中选择优先级最高的进程执行。进程可以用尽这个时间片，如果用不完剩下的时间会增加到下一个时间片中

• 时间片设计

  • 根据进程的静态优先级分配一个默认的时间片，优先级越高获得的时间片越大

  • 静态优先级

    • 进程创建时初始的优先级

  • 动态优先级

    • 每次进程调度的过程中会基于进程的静态优先级和进程剩下的时间片计算一个动态优先级

• 数据结构

  • 使用全局队列

  • 每一层进程调度都需要遍历队列寻找最高优先级的进程

O(1)调度器

• 设计理念

  • 与O(n)调度器基本一致，但是获取最高优先级的进程是O(1)

• 时间片设计

  • 进程的优先级数字越小优先级越高

  • 与O(n)调度器类似，但是O(1)调度器会根据平均休眠时间调整优先级（与用户交互越多的进程优先级越高）

• 数据结构

  • 进程的优先级是0-139，O(1)调度器生成139个队列，进程根据优先级存放到对应的队列中，按照优先级执行，可以O(1)获取最高优先级的进程

• 进程的运行顺序和时间片太依赖优先级，同时优先级是基于与用户交互频率，如果假设不成立那么调度器就有问题

完全公平调度器CFS