kk Blog —— 通用基础

date [-d @int|str] [+%s|"+%F %T"]

linux进程调度之FIFO和RR调度策略

http://blog.chinaunix.net/uid-24774106-id-3379478.html

严格地说,对于优先级对于实时进程和普通进程的意义是不一样的。

1、在一定程度上,实时进程优先级高,实时进程存在,就没有普通进程占用CPU的机会,(但是前一篇博文也讲过了,实时组调度出现在内核以后,允许普通进程占用少量的CPU时间,取决于配置)。

2、对于实时进程而言,高优先级的进程存在,低优先级的进程是轮不上的,没机会跑在CPU上,所谓实时进程的调度策略,指的是相同优先级之间的调度策略。如果是FIFO实时进程在占用CPU,除非出现以下事情,否则FIFO一条道跑到黑。
a)FIFO进程良心发现,调用了系统调用sched_yield 自愿让出CPU
b) 更高优先级的进程横空出世,抢占FIFO进程的CPU。有些人觉得很奇怪,怎么FIFO占着CPU,为啥还能有更高优先级的进程出现呢。别忘记,我们是多核多CPU ,如果其他CPU上出现了一个比FIFO优先级高的进程,可能会push到FIFO进程所在的CPU上。
c) FIFO进程停止(TASK_STOPPED or TASK_TRACED状态)或者被杀死(EXIT_ZOMBIE or EXIT_DEAD状态)
d) FIFO进程执行了阻塞调用并进入睡眠(TASK_INTERRUPTIBLE OR TASK_UNINTERRUPTIBLE)。

如果是进程的调度策略是时间片轮转RR,那么,除了前面提到的abcd,RR实时进程耗尽自己的时间片后,自动退到对应优先级实时队列的队尾,重新调度。

1
2
3
4
5
6
7
8
struct sched_param {
	/* ... */
	int sched_priority;
	/* ... */
};
int sched_setscheduler (pid_t pid,
				int policy,
				const struct sched_param *sp);

sched_setscheduler函数的第二个参数调度方法 :

1
2
3
4
5
6
#define SCHED_OTHER 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#ifdef __USE_GNU
# define SCHED_BATCH 3
#endif

SCHED_OTHER表示普通进程,对于普通进程,第三个参数sp->sched_priority只能是0
SCHED_FIFO 和SCHED_RR表示实时进程的调度策略,第三个参数的取值范围为[1,99]。
如果sched_setscheduler 优先级设置的值和调度策略不符合的话,会返回失败的。

应用层和内核层的优先级含义是不同的:
首先说实时进程:实时进程的优先级设置可以通过sched_setsheduler设置,也可以通过sched_setparam设置优先级的大小。 int sched_setparam (pid_t pid, const struct sched_param *sp);

在用户层或者应用层,1表示优先级最低,99表示优先级最高。但是在内核中,[0,99]表示的实时进程的优先级,0最高,99最低。[100,139]是普通进程折腾的范围。应用层比较天真率直,就看大小,数字大,则优先级高。ps查看进程的优先级也是如此。有意思的是,应用层实时进程最高优先级的99,在ps看进程优先级的时候,输出的是139.

对于普通进程,是通过nice系统调用来调整优先级的。从内核角度讲[100,139]是普通进程的优先级的范围,100最高,139最低,默认是120。普通进程的优先级的作用和实时进程不同,普通进程优先级表示的是占的CPU时间。深入linux内核架构中提到,普通优先级越高(100最高,139最低),享受的CPU time越多,相邻的两个优先级,高一级的进程比低一级的进程多占用10%的CPU,比如内核优先级数值为120的进程要比数值是121的进程多占用10%的CPU。

内核中有一个数组:prio_to_weight[20]表示的是默认优先级120的权重,数值为1024,prio_to_weight[21]表示nice值为1,优先级为121的进程的权重,数值为820。这就到了CFS的原理了

1
2
3
4
5
6
7
8
9
10
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,
};

假如有1台电脑,10个人玩,怎么才公平。
1 约定好时间片,每人玩1小时,玩完后记账,张XX 1小时,谁玩的时间短,谁去玩
2 引入优先级的概念,李四有紧急情况,需要提高他玩电脑的时间,怎么办,玩1个小时,记账半小时,那么同等情况下,李四会比其他人被选中玩电脑的频率要高,就体现了这个优先级的概念。
3 王五也有紧急情况,但是以考察,不如李四的紧急,好吧,玩1个小时,记账45分钟。
4 情况有变化,听说这里有电脑,突然又来了10个人,如果按照每人玩1小时的时间片,排在最后的那哥们早就开始骂人了,怎么办?时间片动态变化,根据人数来确定时间片。人越多,每个人玩的时间越少,防止哥们老捞不着玩,耐心耗尽,开始骂人。

这个记账就是我们prio_to_weight的作用。我就不多说了,prio_to_weight[20]就是基准,玩一小时,记账一小时,数组20以前的值是特权一级,玩1小时记账20分钟之类的享有特权的,数组20之后是倒霉蛋,玩1小时,记账1.5小时之类的倒霉蛋。 CFS这种调度好在大家都能捞着玩。

对于FIFO而言,一旦sleep过后,高优先级运行,低优先级是没戏运行的,同等优先级的进程,先运行的不运行完,后运行的也没戏。
对于RR而言,高优先级的先运行,同等优先级的进程过家家,你玩完,我玩,我玩完你再玩,每个进程耗费一个时间片的时间。对于Linux,RR时间片是100ms:

1
#define DEF_TIMESLICE        (100 * HZ / 1000)