[linux]进程（五）——进程调度

浏览数：34 / 时间：2015年06月20日

14，进程调度：

进程调度概念：
进程调度程序决定哪个进程投入运行，何时运行以及运行多长时间。
linux是抢占式多任务操作系统，
linux在2.6.23内核中采用的是“完全公平调度算法”简称CFS

进程调度前提：
cpu一个处理器在同一时刻只能运行一个进程
进程响应快，后台吞吐量大，避免进程饥饿等

linux进程调度的一些策略：
决定什么时候以什么样的方式选择一个新进程运行这组规则称为调度策略。
（1）进程可以分为两种：IO消耗型和处理器消耗型，通常IO消耗型的优先级大于处理器消耗型
（2）进程优先级
（3）时间片，时间片表明了进程被抢占前所能运行的持续的时间

内核态线程（轻量级进程）和用户态进程如何区别调度：

linux下的内核进程称为轻量级进程，每个进程下仅对应一个用户线程；
用户级同一进程下的多个线程，被一一映射到具有相同ID的多个内核进程下。由于具有相同的ID，所以，这些进程可以共享文件和内存等资源。也就是说，LINUX中，ID相同的进程间调度切换时，不需要切换上下文。

linux用户态一个进程里的多个线程是如何调度的

用户线程之间的调度由在用户空间实现的线程库实现。

进程调度的基本单位：

调度的基本单位是task_struct结构体~，

LINUX下面线程是 lightweight process就是轻量级的进程。一句话线程是共享了部分资源(地址空间、文件句柄、信号量等等)的进程。所以线程也按照进程的调度方式来进行调度。

linux进程的调度算法
linux允许多个不同的调度算法并存，每个调度算法都有自己可以负责的一些进程，对于普通进程的调度算法是CFS，实时进程也有自己的调度类
CFS算法：CFS完全放弃了时间片，而是分配给进程一个处理器比重，通过nice值来计算进程获得处理器的使用权重，
CFS为每个进程都引入了获得时间片的底线，称为最小粒度，默认值是1ms
实时调度算法和策略
linux提供了两种实时调度策略，SCHED_FIFO和SCHED_RR,这两种调度算法类总比SCHED_NORMAL被先执行，SCHED_FIFO调度的进程除非被
优先级更高的进程抢占，否则一直运行到自己主动退出。SCHED_FIFO是不带时间片的，而SCHED_RR是带时间片的，SCHED_RR里的进程执行
完分配给它的时间片就不再运行了~

linux下调度的实现

cfs不再说什么优先级，而统一改称权值，不同的权值的进程在相同真实时钟流逝中其虚拟时钟走的不同，也就是其vruntime的增量不同
CFS算法，虚拟运行时间：CFS通过每个进程的虚拟运行时间（vruntime）来衡量哪个进程最值得被调度。CFS中的就绪队列是一棵以vruntime为键值的红黑树，
虚拟时间越小的进程越靠近整个红黑树的最左端。因此，调度器每次选择位于红黑树最左端的那个进程，该进程的vruntime最小
static const int prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};
一次调度间隔的虚拟运行时间 = 实际运行时间 * (NICE_0_LOAD / 权重)
其中，NICE_0_LOAD是nice为0时的权重。也就是说，nice值为0的进程实际运行时间和虚拟运行时间相同。
权重越大，虚拟运行时间越小，进程获得调度的概率就会更大。

那么被调用的进程会运行多久了：一个进程被调度的最大一直运行时间=(系统调度周期)*(本进程的权值/本运行队列的总权值)

cfs如何保证一段时间内每个进程都能得到执行？答：内核有一个调度延迟的概念，即保证每个进程在一段时间内都能被运行一次的时间间隔，通过/proc/sys/kernel/sched_latency_ns控制，默认为20ms，第二个控制参数sched_nr_latency表示一个调度延迟周期内处理的最大的活动进程数目。

当一个系统调度周期结束后，系统的虚拟时间归一化~都变为一样~

真实时钟步伐	进程1(权值1)虚拟时钟步伐	进程2(权值2)虚拟时钟步伐	进程3(权值3)虚拟时钟步伐
1/6	*2/6*	0	0
2/6	2/6	*1/6*	0
3/6	2/6	1/6	*1/9*
4/6	2/6	1/6	*2/9*（vruntime依然最小，依然是进程3运行）
5/6	2/6	*2/6*	2/9
6/6	2/6	2/6	*3/9*
7/6	*4/6*	2/6	3/9
8/6	4/6	*3/6*	3/9
9/6	4/6	3/6	*4/9*
10/6	4/6	3/6	*5/9*
11/6	4/6	*4/6*	5/9
12/6	4/6	4/6	*6/9*
13/6	*6/6*	4/6	6/9
14/6	6/6	*5/6*	6/9
15/6	6/6	5/6	*7/9*
16/6	6/6	5/6	*8/9*
17/6	6/6	*6/6*	8/9
18/6	6/6	6/6	*9/9*

图表1.cfs原理实例表（黑体为运行路径）

当一个进程新加入到队列中应该如何决定其虚拟运行时间？

答：在place_entity()函数，这个函数有一个initial参数,这是为了区别两种不同情况下的vruntime调整,一种情况是新创建进程的情况，它的initial值为1.另外一种情况是唤醒一个进程时的vruntime调整.，在第一种情况下,新创建的进程都以cfs_rq->min_vruntime都为一个基础,在其后的一段时间后得到调度.这段时间的大小为sched_vslice(),它其实就是将sched_slice()转换为虚拟运行时间，在第二种情况下,是调整唤醒进程的vruntime值,这种情况比较复杂.首先,为什么要对唤醒进程的时间进行调整呢?我们来考虑一个这样的问题:假设进程A睡眠了较长时间,以后被唤醒,如果没有调整其vruntime值,就会使得其vruntime远小于cfs_rq->min_vruntime.这样的后果就是,在其后相当长的一段时间内,进程A都会独占CPU,造成了其它进程不能及时得到响应.那怎么调整呢?有以下两个情况:
1):如果进程睡眠的时间很短,也就是se->vruntime仍然大于cfs_rq->min_vruntime.这种情况下,不需要对se->vruntime进程调整.
2):如果进程睡眠时间较长,那当然要对睡眠进程的时间做一个补偿,因此,就将cfs_rq->min_vruntime适当减一个差值做为进程的vruntime值,当然,这种情况下,不能使调整之后的值比之前的vruntime还要小

pick_next_task_fair()函数用于从cfs_rq中选择下一个应该被调度的进程，红黑树中最左边的节点虚拟时间比当前进程虚拟时间小就一定会被调度？调度粒度

调度周期保存在sysctl_sched_wakeup_granularity中，最小为4ms？

进程调度涉及的相关数据结构

(1)runqueue

每个CPU都有一个属于自己的就绪队列
每个 CPU 的就绪队列按时间片是否用完分为两部分，分别通过 active 指针和 expired 指针访问，active 指向时间片没用完、当前可被调度的就绪进程，
expired 指向时间片已用完的就绪进程。每一类就绪进程都用一个 struct prio_array 的结构表示：

[cpp] view plain copy

struct prio_array {
int nr_active; /* 本进程组中的进程数 */
struct list_head queue[MAX_PRIO];
/* 以优先级为索引的 HASH 表，见下 */
unsigned long bitmap[BITMAP_SIZE];
/* 加速以上 HASH 表访问的位图，见下 */
};

每个cpu的就绪队列的结构体是struct rq,如下所示：

[cpp] view plain copy

struct rq{
unsigned long_nr_running;
struct cfs_rq cfs; //CFS调度器
struct rt_rq rt;
‘‘‘‘‘
};
struct cfs_rq {
struct load_weight load;
unsigned long nr_running;
u64 min_vruntime; //记录了队列上所有进程的最小运行虚拟时间
struct rb_root tasks_timeline;
struct rb_node *rb_leftmost; //红黑树最左边的节点，即即将被调度的进程
struct sched_entity *curr;

（2）进程描述符中与调度相关的几个结构体

[cpp] view plain copy

struct task_struct {
...
int prio, static_prio, normal_prio;
unsigned int rt_priority;
struct list_head run_list;
const struct sched_class *sched_class; //该进程所属于的调度器类
struct sched_entity se; //可调度实体，调度器可以根据此来操作各个进程
unsigned int policy;
cpumask_t cpus_allowed; //用来限制进程在哪个cpu运行
unsigned int time_slice;
...

进程调度涉及的具体代码：
调度器的主入口函数是schedule()函数，在schedule（）里会去挑选优先级最高的一个调度类，每个调度类都有一个自己的一个可运行队列，
然后由调度类去挑选谁是下一个运行的进程。schedule（）函数里会调用的是pick_next_task()函数，
进程的睡眠和唤醒
进程的睡眠过程为：进程把自己设置为休眠状态，从可执行的红黑树移出，放入等待队列，然后调用schedule（）函数选择和执行下一个进程，
进程的唤醒过程和进程的睡眠过程正好相反。
等待队列：
等待队列就是等待一些事情发生的进程组成的链表，进程休眠就是将自己放入等待队列

typedef struct __wait_queue_head wait_queue_head_t;
linux内核使用等待队列的步骤
1，声明一个等待队列头：
wait_queue_head_t read_wq;
2，通过init_waitqueue_head（）来动态创建一个等待队列
init_waitqueue_head(read_wq);
3,在内核代码中等待某个条件满足从而唤醒等待队列
int ret = wait_event_interruptible(read_wq,rx_done);
4,在其它地方唤醒等待队列

wake_up(&read_wq);

唤醒方式：wake_up (唤醒时要检测条件是否为真，如果还为假则继续睡眠，唤醒前一定要把条件变为真)

等待队列内核代码的实现

linux内个用wake_queue_head_t来代表等待队列，如下所示：

[cpp] view plain copy

struct __wait_queue_head {
wq_lock_t lock;
struct list_head task_list;
};
typedef struct __wait_queue_head wait_queue_head_t;

等待队列链表中的元素类型为wait_queue_t,我们可以称之为等待队列项：

[cpp] view plain copy

struct __wait_queue {
unsigned int flags;
#define WQ_FLAG_EXCLUSIVE 0x01 //独占等待标志，一次只唤醒一个进程
void *private; //private成员用来存放已经被初始化的current进程
wait_queue_func_t func; //默认的唤醒函数，默认等待队列项名字为_wait，默认唤醒函数为autoremove_wake_function(),该函数最终调用到try_to_wakeup()函数
struct list_head task_list;
};
#define __wait_event_interruptible(wq, condition, ret)
do {
DEFINE_WAIT(__wait); \
for (;;) {
prepare_to_wait(&wq, &__wait, TASK_INTERRUPTIBLE //如果当前等待队列头为空则将当前进程_wait加入等待队列，并将当前进程状态设置为TASK_INTERRUPTIBLE
if (condition)
break;
if (!signal_pending(current)) //检查当前进程是否有信号处理，返回不为0表示有信号需要处理。
schedule();
continue; //for (;;) 循环的作用是让进程被唤醒后再一次去检查一下condition是否满足。
主要是为了防止等待队列上的多个进程被同时唤醒后有可能其他进程已经抢先资源占有过去造成资源又变为不可用，因此最好再判断一下。
} \
ret = -ERESTARTSYS //如果返回值-ERESTARTSYS,并且当前调度的信号具备-ERESTARTSYS //属性,系统就会在用户信号函数返回之后再执行该系统调用。
break; \
} \
finish_wait(&wq, &__wait); \
} while (0)
68 prepare_to_wait(wait_queue_head_t *q, wait_queue_t *wait, int state)
69 {
70 unsigned long flags;
71
72 wait->flags &= ~WQ_FLAG_EXCLUSIVE;
73 spin_lock_irqsave(&q->lock, flags);
74 if (list_empty(&wait->task_list))
75 __add_wait_queue(q, wait);
76 set_current_state(state); //将当前进程的状态设置为TASK_INTERRUPTIBLE状态
77 spin_unlock_irqrestore(&q->lock, flags);
78 }
130 static inline void __add_wait_queue_tail(wait_queue_head_t *head,
131 wait_queue_t *new)
132 {
133 list_add_tail(&new->task_list, &head->task_list);
134 }