操作系统-linux0.11进程调度函数分析

0 引言

进程是操作系统分配资源的最小单位；线程是程序执行的最小单位。计算机上运行着几十上百个程序，对于每个程序而言，他们都是独享CPU的，操作系统制造了这一有多个CPU的假象。这一假象得以维持的基础就在于进程之间的切换，而进程切换则需要用到进程调度，具体的进程调度内容可以看之前的博文：。

但是空说无凭，理论还是需要结合实际，这篇博文将从linux0.11入手，看一个实际的调度函数。

1 源码分析

1.1 时间片轮转

在BIOS引导进入系统后，会执行系统的main函数（init/main.c）：

void main(void)		/* This really IS void, no error here. */
{			/* The startup routine assumes (well, ...) this */
/*
 * Interrupts are still disabled. Do necessary setups, then
 * enable them
 */
 	...
	sched_init();
    ...
	move_to_user_mode();

	if (!fork()) {		/* we count on this going ok */
		init();
	}
	for(;;) pause();
}

其中进行了很多的初始化操作，包括 sched_init，这便是内核调度程序的初始化子程序(kernel/sched.c)，其定义如下：

void sched_init(void)
{
	...
	outb_p(0x36,0x43);		/* binary, mode 3, LSB/MSB, ch 0 */
	outb_p(LATCH & 0xff , 0x40);	/* LSB */
	outb(LATCH >> 8 , 0x40);	/* MSB */
    
	set_intr_gate(0x20,&timer_interrupt);
    ...
}

sched_init 初始化了8253定时器（微机原理与接口技术学过的），8253每10ms发出一个中断请求信号。然后设置了一个中断服务程序 timer_interrupt，即每10ms中断一次，执行一次 timer_interrupt 。

timer_interrupt 在kernel/system_call.s中定义，为一段汇编程序：

.align 2
timer_interrupt:
	push %ds		# save ds,es and put kernel data space
	push %es		# into them. %fs is used by _system_call
	push %fs
	pushl %edx		# we save %eax,%ecx,%edx as gcc doesn't
	pushl %ecx		# save those across function calls. %ebx
	pushl %ebx		# is saved as we use that in ret_sys_call
	pushl %eax
	movl $0x10,%eax
	mov %ax,%ds
	mov %ax,%es
	movl $0x17,%eax
	mov %ax,%fs
	incl jiffies
	movb $0x20,%al		# EOI to interrupt controller #1
	outb %al,$0x20
	movl CS(%esp),%eax
	andl $3,%eax		# %eax is CPL (0 or 3, 0=supervisor)
	pushl %eax
	call do_timer		# 'do_timer(long CPL)' does everything from
	addl $4,%esp		# task switching to accounting ...
	jmp ret_from_sys_call

可以发现，其核心为一句 call do_timer，即调用 do_timer 函数。

do_timer 函数在kernel/sched.c中定义，

void do_timer(long cpl)
{
	...
	if ((--current->counter)>0) return;
	current->counter=0;
    // 内核中不调度
	if (!cpl) return;
	schedule();
}

其调用了一个 schedule(), 这个 schedule() 函数选出下一个要执行的进程，并且切换到它，这是今天的主角！

通过上面的分析可以发现，counter 扮演了时间片的角色，每一次8253产生中断会调用中断服务程序，使 counter 减1，减到0则调用调度函数 schedule()，这是一个十分明显的round robin（时间片轮转）策略。

1.2 优先级调度

先看看 schedule() 函数的全貌吧，只看片段容易盲人摸象：

/*
 *  '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;
			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);
}

schedule() 函数中，第一个for循环处理了很多信号的响应，这不是调度的重点（毕竟next代表选出的下一个要运行的进程，这一段还没有next相关的操作呢。。。）。

重点聚焦于 while (1) 循环，毕竟注释也写了，这是调度程序的主要部分。

下面的代码展示了调度策略，从任务数组的最后一个任务开始循环处理，跳过不含任务的数组槽。选择就绪任务中 counter 值最大的任务（说明），若有 counter 值不为0的结果或系统没有一个可运行任务（此时next为0）存在，则选择next对应进程进行切换。

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;

若就绪任务中 counter 值全为0，则根据每个任务的优先权值更新每一个任务（全部任务，包含阻塞的）的 counter 值。

for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
    if (*p)
        (*p)->counter = ((*p)->counter >> 1) + (*p)->priority;

从上面的式子也可以看出来，若某些任务一直执行 counter 调整，其 counter 值是趋向于 2 * (*p)->priority 的（级数，自己可以算一下）。

综上，schedule() 函数的行为为：

1. 找 counter 值最大的任务调度， counter 表示了优先级。
2. counter 代表的优先级可以动态调整。

因为2的存在，阻塞的进程再就绪后，其优先级会高于非阻塞进程。阻塞是因为发生了I/O，而I/O则是前台进程的特征，所以该调度策略照顾了前台进程。

2 总结

正如Linus Torvalds所说，这确实是个GOOD CODE！！！

短短的一点代码实现的一个简单的算法，包含了优先级、时间片轮转等多种算法，解决了大多数任务的需求，大佬牛逼，给大佬打call！！！

3 参考文献

[1] Linux内核完全注释：基于0.11内核 · 赵烔

[2] 哈工大操作系统课程 · 李治军