咖啡's blog

专心 专注 专业

0%

《linux 0.12内核完全剖析》--进程调度分析

发表于 更新于 分类于 ， Valine：

笔记重点:
进程调度一直是linux系统开发中相当重要的部分,但在最初版本中的调度如此简单，以至于你并不相信，但是在不断的发展过程中，首先在2.6内核版本中发展了抢占式的调度算法，在经历几次重大版本的迭代后在开发出CFS(完全公平的调度算法),不过调度算法的重点是，如何选择需要运行的进程以及保证性能。进程的运行很多时候会被外部的资源分配不及时而阻塞，这个时候进程睡眠等待，以及这个时候的合理调度，对于CPU资源的充分利用，显得尤为重要，那调度就从进程的睡眠机制开始了解。
问题：

  • 任务调度在何时发生
  • 任务调度的基本策略是什么
  • 任务切换时怎么做到的

1. 隐含的睡眠队列

建立睡眠等待队列的原因，是因为有先后顺序等待某项资源，然后要按顺序唤醒进程，就要依照这里隐含的队列顺序进行

sched.c第171行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static inline void __sleep_on(struct task_struct **p, int state)
{
	struct task_struct *tmp;

	if (!p)
		return;
	if (current == &(init_task.task))
		panic("task[0] trying to sleep");
	tmp = *p;
	*p = current;
	current->state = state;
repeat:	schedule();
  	//这里的*p的内容，有可能不是上面的*p的内容即不是当前任务，也有可能是
  	//不是当前任务是因为在其它进程执行本函数时__sleep_on设置的
	if (*p && *p != current) {
		(**p).state = 0;
		current->state = TASK_UNINTERRUPTIBLE;
		goto repeat;
	}
	if (!*p)
		printk("Warning: *P = NULL\n\r");
	if (*p = tmp)
		tmp->state=0;
}

以下这张图展示了这个队列的大概样子，上面方块代表__sleep_on函数块,需要了解这个机制，是因为很多其它的子系统也用到类似的方法，这也是了解睡眠机制的关键

隐含的睡眠队列

2. 任务调度在何时发生

任务状态发生改变的时候都会要重新调度，比如睡眠了一个进程(任务),自然就要重新选一个进程继续运行，在者要是没有任务发生改变时，时间中断回调函数，会在每10ms到来时运行一次

sched.c第324行

1
2
3
4
5
6
7
8
9
10
void do_timer(long cpl)
{
	...
    //current->counter > 0意思是当前任务还有分配给他的时间片
	if ((--current->counter)>0) return;
	current->counter=0;
	if (!cpl) return;
  	//重点：重新调度
	schedule();
}

3. 任务调度的基本策略

sched.c第120行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void schedule(void)
{
	...
/* this is the scheduler proper: */

	while (1) {
		c = -1;
		next = 0;
		i = NR_TASKS;
		p = &task[NR_TASKS];
      	//挑选一个就绪态运行的进程且时间片最大的那个进程
		while (--i) {
			if (!*--p)
				continue;
			if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
				c = (*p)->counter, next = i;
		}
      	//没有找到怎么办？你猜猜
		if (c) break;
		for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
			if (*p)
			// 这就是调整优先级的公式,对！就这么简单
				(*p)->counter = ((*p)->counter >> 1) +
						(*p)->priority;
	}
  	//切换进程
	switch_to(next);
}

备注:

  • 选取超时时间最少也就是分配的时间片最多的那个进程进行切换
  • 调度性能与进程的数目成线性关系，进程越多性能越差

4. 切换任务的代码分析

先来看看TSS段描述符的格式:

段描述符格式

然后再来看看_TSS宏，它是寻找GDT表中本进程的tss描述符的选择符号值,每个任务包含一个ldt选择符和tss选择符

1
2
3
//每个任务有一个8字节的tss选择符和8字节的ldt选择子一共16字节
//任务为n偏移2^4字节
#define _TSS(n) ((((unsigned long) n)<<4)+(FIRST_TSS_ENTRY<<3))

切换代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define switch_to(n) {\
struct {long a,b;} __tmp; \
//是不是当前任务，是就不用切换直接跳到下面标号为的地方
__asm__("cmpl %%ecx,_current\n\t" \
	"je 1f\n\t" \
	/*
	%dx装载下面的_TSS(n)，也就是tss段描述符的值
	放到%1,%1代表__tmp.b处
	*/
	"movw %%dx,%1\n\t" \ 
	/*%ecx为保存为切换出来的任务*/
	"xchgl %%ecx,_current\n\t" \
	/*长跳到__tmp.a处的任务，也就是上面tss保存到__tmp.b的进程*/
	"ljmp %0\n\t" \
	"cmpl %%ecx,_last_task_used_math\n\t" \
	"jne 1f\n\t" \
	"clts\n" \
	"1:" \
	::"m" (*&__tmp.a),"m" (*&__tmp.b), \
	"d" (_TSS(n)),"c" ((long) task[n])); \
}

结束语:

0.12版本的进程调度策略比较简单，但给了我们理解进程调度的核心意思，最新的linux代码仍然使用switch_to宏，只是已经做了非常的优化工作