【Linux内核分析与应用-陈莉君】进程的调度

1.基本调度模型-调度复杂度为O(n)

进程的调度实际上就是从就绪队列中选择一个进程投入CPU运行,从图中可以看出:
调度的主战场就是就绪队列,
核心就是调度算法,
实质性的动作是进程的切换,
对于以时间片调度为主的调度,时钟中断就是驱动力,确保每个进程在CPU上运行一定的时间,
在调度的过程中用户还可以通过系统调用NICE来调整优先级,比如降低自己的优先级等.
当然也涉及进程状态的转换,新创建的进程就加入到就绪队列中,退出的进程就从队列中删除.
从图中我们还可以看出所有CPU的所有进程都存放在了一个就绪队列中,从中选中一个进程进程
调度的过程实际上就是对队列线性查找的过程,因此其算法复杂度为O(n),详细调度过程和
代码的分析查看教材中进程的调度内核和源码.
上图是针对2.4内核代码分析,看起来比较简单,本次课程主要讲解进程调度的演变过程,以指导
大家阅读高版本的内核源代码.

2.调度的主战场-就绪队列

 

3.进程调度-进程优先级

问题：
什么是实时进程？什么是普通进程？

归一化优先级：
是由静态优先级，调度优先级和调度策略计算而得到的.

动态优先级：
可以在运行的过程中动态调整的优先级.

可进入源码查看相关字段.

4.O(1)进程调度模型

 

前面我们介绍的O(n)调度器中只有一个全局的就绪队列,这严重地影响了其扩展性,因此
就引入了O(1)调度,在O(1)调度中引入了每一个CPU一个就绪队列的概念,也就是说系统中
所有的就绪进程呈现进过负载均衡模块挂入各个CPU的就绪队列上，然后又主调度器和
周期性调度器驱动该CPU上的调度行为.

看一下O(1)调度的优先级队列,为什么说它是O(1)呢？
O(1)调度器的基本优化思路就是把原来就绪队列上的单链表变成了多个链表，
也就是说每个优先级的进程被挂入到不同的链表里面.

优先级队列的结构是怎样的呢？
我们给出struct prio_array这个数据定义,
struct prio_array{
   unsigned int nr_active;
   unsigned long bitmap[BITMAP_SIZE];
   struct_head queue[MAX_PRIO];
}

O(1)调度器一共支持140个优先级,因此队列成员中就有
140个分别表示各个优先级的链表头,不同优先级的进程挂入不同的链表中；
bitmap时表示各个优先级进程链表是空还是非空;
nr_active表示这个队列中有多少个任务.

在这些队列中，100-139是普通进程的优先级,其他的都是实时进程的优先级.
因此在O(1)调度器中,实时进程和普通进程被区分对待,普通进程根本不会影响
实时进程的调度.


从本小结第三张图中可以看到就绪队列中有两个优先级队列,他们分别用来管理
活跃队列(时间片还有剩余的队列)和时间片耗尽的队列.随着系统的运行,活跃
队列中的任务一个个耗尽其时间片,挂入到时间片耗尽的队列里面,当活跃队列
中的任务为空的时候,两个队列互换,开始新一轮的调度过程.

虽然在O(1)的调度器中，任务组织的形式发生了变化,但是其核心的思想仍然和
O(n)的调度是一致的,都是把CPU的资源分成一个一个的时间片,分配给每一个就绪
的进程,进程用完其额度后就被抢占等待下一轮调度周期的到来.


主调度器：
就是schedule函数,其主要功能就是从该CPU的就绪队列中找到一个最合适的进程
调度执行.其基本思路就是从活跃队列中查找,首先在当前活跃队列的位图中寻找
第一个非空的进程链表，然后在该链表中找到的第一个节点就是最适合下一个调度
的进程.由于没有遍历整个链表的操作，因此这个调度器的算法复杂度就是一个常量,
从而解决了O(n)的复杂度的问题.

5.机制与策略分离调度模型

O(1)调度器使用非常复杂的算法来判断进程是不是交互式进程以及是不是进程交互的子树,
即使是这样还依旧会出现卡顿的现象,那么如何解决这个问题呢?能不能不被用户的具体需求
所捆绑而又能满足灵活多变的需求呢？
再一次的我们用到了机制与策略分离的思想.
这个模型就是调度器里面的调度与策略分离调度器.
功能层面上来看,进程调度仍然分成两部分:
1.负载均衡；
2.在各个CPU的主调度器和周期性调度器的驱动下进行单个CPU上的调度.

struct_class:
next               --指定下一个比自己低一级的优先级调度类
enqueue_task       --指定入队的函数
dequeue_task       --指向出队的函数
check_preempt_curr --表示当前CPU上正在运行的进程是否可以被抢占
pick_next_task     --核心函数,从就绪队列中选择一个最适合运行的进程,这个是调度器比较核心的操
做,例如我们依据什么去挑选最合适的进程,这是每一个调度器需要管住宿的问题.

6.调度模型-CFS-完全公平调度

CFS调度器的目标是保证每一个进程的完全公平调度,CFS调度没有时间片的概念了,
而是分配CPU使用时间的比例,理想的状态的下,每个进程都能获得相同的时间片,
而且同时运行在CPU上,但实际上,一个CPU同一时刻运行的进程只能有一个,也就是说
当一个进程占用CPU的时候,其他CPU必须等待,CFS为了实现公平必须惩罚当前正在
运行的进程以使那些正在等待的进程下次再被调度.

CFS调度器的算法中使用了红黑树,在具体实现的时候,CFS通过每个进程的虚拟运行
时间来衡量哪个进程最值得被调度,CFS中的就绪队列就是一颗以虚拟时间为键值的
红黑树.虚拟时间越小的进程就越靠近红黑树的最左端,因此调度器每次都选择位于
红黑树最左端的那个进程,该进程的虚拟之间是最小的.

虚拟运行时间是如何计算出来的呢？
虚拟运行时间是通过进程的实际运行的时间和进程的权重计算出来的.

在CFS这个模型中就把进程优先级这个概念弱化了,而是强调进程的权重,一个进程
的权重越大,就说明这个进程进程越需要运行,因此其虚拟运行时间就越小,这样
被调度的机会就越大.

7.总结

进程调度是操作系统很重要的部件,主要功能是将系统中的任务调度到各个CPU中去
执行,以满足以下需求：
1.对于分时的进程，调度器必须是公平的;
2.快速的系统响应时间;
3.系统有高的吞吐量；
4.功耗小.

一般将进程分为普通进程和实时进程,
对于实时进程,快速响应最重要.
对于普通进程,一般要兼顾2,3,4点的需求.

这些需求可能是互相冲突的,调度器在设计的时候必须综合考虑各种因素.


代码阅读作业：
2.4版本入门
根据兴趣看高版本的代码