Linux 内核学习笔记：进程 1 的创建及执行（第 2 部分） —— 任务调度

本文是上一博文 Linux 内核学习笔记：进程 1 创建及执行（第 1 部分）的续篇。

任务调度

名词辩解

为了准确，在这里我们将我们常说的进程调度改称为任务调度，原因主要是：

• 在 Linux 0.11 （其他 Linux 版本也一样，可通过 ulimit -a 查看）最多支持“同时存在” 64 个进程，因为系统资源是有限的（跟 GDT 容量、内存有限等有关）
• 进程的进程号可能是远远大于操作系统支持“同时存在”的进程数的，因为进程可创建也可销毁，只要“同时存在”的进程数是小于等于系统支持的进程数就行了；而且进程号是一直在累加的，即在不考虑特殊情况（溢出，如 long pid，pid 是存在溢出的风险的）的情况下，存在或已销毁的进程的进程号是不会一样的
• 这些“同时存在”的进程由 task[64] 数组来统一管理。task[64] 中每一项指向这些进程中的某一个进程（具体指向的是该进程的进程描述符 task_struct ）或为 NULL。另外，task[64] 中的每一项可以重复使用，如 task[64] 中某项指向的进程已被销毁，那这一项就可以给其他新建的进程用
• task[64] 每一项指向的内容都称为一个任务。我们平常所说的“进程调度”实际是对 task[64] 进行遍历，即对 task[64] 中每一项指向的进程进行遍历，然后切换到符合要求的进程。而这些进程都可称为任务。
• 综上，用“任务调度”这个说法来代替“进程调度”的说法更为具体和准确。

注：

• 上边提到的“同时存在”是指“同时存在而还未被系统销毁”的进程。
• task[64] 定义如下：

  // include/linux/sched.h -----------------------
  extern struct task_struct *task[NR_TASKS];	// NR_TASKS = 64

任务调度

这是内核第一次做任务调度。现在执行的是进程 0 的代码。从这里开始，进程 0 准备切换到进程 1 去执行。

《Linux 内核设计的艺术》指出在 Linux 0.11，在以下两种情况下会发生任务切换：

1. 允许进程运行的时间结束
   进程在创建时，都被赋予了有限的时间片，以保证所有进程每次都只执行有限的时间。一旦进程的时间片被削减为 0，就说明这个进程此次执行的时间用完了，立即切换到其他进程去执行，实现多进程轮流执行。
2. 进程被挂起
   当一个进程需要等待外设提供的数据，或等待其他程序的运行结果……或进程已经执行完毕时，在这些情况下，虽然还有剩余的时间片，但是进程已经不具备进一步执行的“逻辑条件”了。如果还等着时钟中断产生后再切换到别的进程去执行，就是在浪费时间，应立即切换到其他进程去执行。

在上一博文 Linux 内核学习笔记：进程 1 创建及执行（第 1 部分）最后我们说到，进程 0 开始执行如下代码：

// init/main.c ---------------------------------
static inline _syscall0(int,pause)
......

void main(void)
{
	......
	sti();
	move_to_user_mode();
	if (!fork()) {		/* we count on this going ok */
		init();
	}

	for(;;) pause();
}

调用 sys_pause

pause 函数的执行流程跟 fork 函数的类似，都是通过 int 0x80 跳转到 system_call，再根据输入参数调用具体的服务程序。pause 函数具体的服务程序如下：

// kernel/sched.c ------------------------------
int sys_pause(void)
{
	// 将进程 0 设置为可中断等待状态，如果产生某种中断，或其他进程给这个进程发送特定信号……
	// 才有可能将这个进程的状态改为就绪态
	current->state = TASK_INTERRUPTIBLE;
	schedule();
	return 0;
}

调用 schedule

调用的 schedule() 函数定义如下：

// kernel/sched.c ------------------------------
/*
 *  'schedule()' is the scheduler function. This is GOOD CODE! There
 * probably won't be any reason to change this, as it should work well
 * in all circumstances (ie gives IO-bound processes good response etc).
 * The one thing you might take a look at is the signal-handler code here.
 *
 *   NOTE!!  Task 0 is the 'idle' task, which gets called when no other
 * tasks can run. It can not be killed, and it cannot sleep. The 'state'
 * information in task[0] is never used.
 */
void schedule(void)
{
	int i,next,c;
	struct task_struct ** p;

/* check alarm, wake up any interruptible tasks that have got a signal */

	for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
		if (*p) {
			if ((*p)->alarm && (*p)->alarm < jiffies) {
					(*p)->signal |= (1<<(SIGALRM-1));
					(*p)->alarm = 0;
				}
			if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
			(*p)->state==TASK_INTERRUPTIBLE)
				(*p)->state=TASK_RUNNING;
		}

/* this is the scheduler proper: */

	while (1) {
		c = -1;
		next = 0;
		i = NR_TASKS;
		p = &task[NR_TASKS];
		while (--i) {
			if (!*--p)
				continue;
			// 找出就绪态中 counter 最大的进程
			if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
				c = (*p)->counter, next = i;
		}

		// 如果比较得出有 counter 大于 0 的结果，跳出循环，执行任务切换
		if (c) break;

		// 否则就根据每个任务的优先权值，更新每一个任务的 counter 值，然后继续外循环（while(1)）
		// counter 值的计算方式为：counter=counter/2+priority
		for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
			if (*p)
				(*p)->counter = ((*p)->counter >> 1) +
						(*p)->priority;
	}
	switch_to(next);
}

切换到进程 1

调用 switch_to

// include/linux/sched.h -----------------------
extern struct task_struct *current;
......

/*
 * Entry into gdt where to find first TSS. 0-nul, 1-cs, 2-ds, 3-syscall
 * 4-TSS0, 5-LDT0, 6-TSS1 etc ...
 */
#define FIRST_TSS_ENTRY 4
#define _TSS(n) ((((unsigned long) n)<<4)+(FIRST_TSS_ENTRY<<3))
......

/*
 *	switch_to(n) should switch tasks to task nr n, first
 * checking that n isn't the current task, in which case it does nothing.
 * This also clears the TS-flag if the task we switched to has used
 * tha math co-processor latest.
 */
// 输入：%0 - 存放新 TSS 的偏移地址（*&__tmp.a），%1 - 存放新 TSS 的段选择符（子）（*&__tmp.b）
//	dx - 新任务 n 的段选择符（子），ecx - 新任务指针 task[n]
#define switch_to(n) {\
struct {long a,b;} __tmp; \		// 为 ljmp 的 cs、eip 准备的数据结构
__asm__("cmpl %%ecx,_current\n\t" \	// 任务 n 是当前任务吗？（current = task[n]?）
	"je 1f\n\t" \			// 如果是就不用切换任务了
	"movw %%dx,%1\n\t" \		// 将新任务的选择子 => *&__tmp.b
	"xchgl %%ecx,_current\n\t" \	// current = task[n]；ecx = 被切换的任务
	"ljmp %0\n\t" \			// 执行长跳至 *&__tmp，造成任务切换
					// 执行任务切换回来后才会继续执行下面的语句
	"cmpl %%ecx,_last_task_used_math\n\t" \	// 新任务上次使用过协处理器吗？
	"jne 1f\n\t" \			// 没有则跳转，退出
	"clts\n" \			// 新任务上次使用过协处理器，清 CR0 的 TS 标志
	"1:" \
	::"m" (*&__tmp.a),"m" (*&__tmp.b), \
	"d" (_TSS(n)),"c" ((long) task[n])); \
}

上述代码比较难以理解的是 switch_to 这个函数中的一个重要的点——任务门描述符：

• ljmp 通过通过 CPU 的任务门机制，将 CPU 各个寄存器值保存到进程 0 的 TSS 中，将进程 1 的 TSS 数据恢复给 CPU 的各个寄存器，实现从 0 特权级的内核代码切换到 3 特权级的进程 1 代码执行。在这里，进程 1 的 TSS 选择子为 _TSS(1)=0b110 000 -> 0 特权级，在 GDT，TSS 在 GDT 下标为 6。
• 设置任务门的目的是为了在多进程环境下进行进程切换，通过它切换到另一个进程。而这一切换是通过进程的 TSS 实现的，因为进程的入口点包括段基地址和偏移量都存放在 TSS 中。在这里，任务门描述符内的偏移量没有意义。
• 任务门描述符格式如下（也可参照之前博文 Linux 内核学习笔记：预备知识之“存储器管理基础”“门描述符”部分）：
  图片来源：《Linux 内核完全注释》
• TSS 格式（注意不是 TSS 描述符）如下：
  图片来源：《Linux 内核完全注释》

注：这里还是有问题的，就是 __tmp 如何跟任务门描述符格式一一对应起来，特别是“段选择符（子）”。

返回 fork

在上一博文 Linux 内核学习笔记：进程 1 创建及执行（第 1 部分）我们提到，进程 1 并不会完全复制进程 0 的所有属性，而是会进行微调：

// kenel/fork.c --------------------------------
int copy_process(int nr,long ebp,long edi,long esi,long gs,long none,
		long ebx,long ecx,long edx,
		long fs,long es,long ds,
		long eip,long cs,long eflags,long esp,long ss)
{
	......

	*p = *current;	/* NOTE! this doesn't copy the supervisor stack */
	......

	p->tss.esp0 = PAGE_SIZE + (long) p;	// 重要！esp0 是内核指针。见本文前头的 task_union 部分
	......

	p->tss.eip = eip;	// 重要！就是参数的 eip，是 int 0x80 压栈的，指向的是：if (__res >= 0)
	......

	p->tss.eax = 0;		// 重要！决定 main 函数中 if(!fork()) 后面的分支走向
}

这些代码说明，当内核调度进程 1 开始运行时，将会跟其父进程（进程 0）一样从 int 0x80 的下一行 if (__res >= 0) 开始执行，并且置返回值 __res 为 0 （p->tss.eax = 0），也即 fork 函数返回 0：

// include/unistd.h ----------------------------	// unistd -> unix standard
#define __NR_fork	2
......

#define _syscall0(type,name) \
type name(void) \
{ \
long __res; \
__asm__ volatile ("int $0x80" \		// int 0x80 是所有系统调用函数的总入口，fork() 是其中之一
					// 它将导致 CPU 硬件自动将 ss esp eflags cs eip 按序压栈
					// 在这里，压栈的 eip 指向的是下一条语句 if (__res >= 0)
	: "=a" (__res) \		// 返回值存放到 %eax
	: "0" (__NR_##name)); \		// __NR_fork -> %eax
if (__res >= 0) \			// int 0x80 中断返回后，将执行这一句
	return (type) __res; \
errno = -__res; \
return -1; \
}
......

int fork(void);

// init/main.c ---------------------------------
static inline _syscall0(int,fork)	// fork 函数。fork 是一个函数指针常量，有地址含义
......

void main(void)
{
	......
	sti();
	move_to_user_mode();
	if (!fork()) {		// fork 在子进程（进程 1） 返回 0
		init();		// 在子进程（进程 1）开始执行
	}
}

上述代码可用图表示如下：
图片来源：《Linux 内核设计的艺术》

注：从这里我们才真正知道，通过 fork 函数派生的子进程会跟其父进程在派生后从同一位置开始执行，而且在父、子进程中 fork 函数返回的值不一样。

调用 init

init 函数定义如下：

// init/main.c ---------------------------------
static inline _syscall1(int,setup,void *,BIOS)
......

#define DRIVE_INFO (*(struct drive_info *)0x90080)
......

struct drive_info { char dummy[32]; } drive_info;	// 2 个硬盘的进程的基本参数表大小总共为 32B
......

int main(void)
{
	......
 	drive_info = DRIVE_INFO;
	......
	if (!fork()) {		// fork 在子进程（进程 1） 返回 0
		init();		// 在子进程（进程 1）开始执行
	}
}
......

void init(void)
{
	int pid,i;

	setup((void *) &drive_info);
	......
}

调用 setup

setup 函数的调用跟 fork、pause 函数的调用有点类似；略有区别的是 setup 函数不是通过 _syscall0 而是通过 _syscall1 实现的；具体的实现过程基本类似，也是通过 int 0x80、_system_call、call _system_call_table (,%eax,4)、sys_setup：

// include/unistd.h ----------------------------
#define __NR_setup	0	/* used only by init, to get system going */
......

#define _syscall1(type,name,atype,a) \
type name(atype a) \
{ \
long __res; \
__asm__ volatile ("int $0x80" \
	: "=a" (__res) \
	: "0" (__NR_##name),"b" ((long)(a))); \
if (__res >= 0) \
	return (type) __res; \
errno = -__res; \
return -1; \
}

// include/linux/sys.h -------------------------
extern int sys_setup();
......

fn_ptr sys_call_table[] = { sys_setup,...}

// kenel/system_call.s -------------------------
.align 2
_system_call:
	......
	push %ds	# 下面 6 个 push 都是 copy_process() 的参数
	push %es
	push %fs
	pushl %edx
	pushl %ecx		# push %ebx,%ecx,%edx as parameters
	pushl %ebx		# to the system call
	movl $0x10,%edx		# set up ds,es to kernel space
	mov %dx,%ds
	mov %dx,%es
	movl $0x17,%edx		# fs points to local data space
	mov %dx,%fs
	call _sys_call_table(,%eax,4)	# sys_call_table 定义在 include/linux/sys.h
					# 调用地址 = _sys_call_table + %eax * 4
					# 在这里，%eax = __NR_setup，所以调用地址为 _sys_call_table + 8，查 sys_call_table 可知，该地址刚好指向 sys_setup
					# 调用 call _sys_call_table(,%eax,4) 本身也会压栈保护现场。这个压栈体现在 copy_process() 函数的第 6 个参数 `long none`。
	......

// kenel/blk_drv/hd.c --------------------------
/* This may be used only once, enforced by 'static int callable' */
int sys_setup(void * BIOS)
{
	......
}

注：之前在进程 0 调用的 pause 函数的 int 0x80 中断还没返回，现在 setup 函数又产生了一个中断。

调用 sys_setup

以防博文过长，接下来内容请见续篇。