前言

上一篇文章，通过系统调用引出了中断以及分段机制和保护模式相关内容，并进行了简单说明。本篇将在中断基础上，从时间片轮转和任务切换的角度切入，进一步地探究linux内核。

时间片轮转

时间片轮转是操作系统实现并发的方式，简单地说，操作系统为每个进程分配一定的时间片，当前进程的时间片用尽，则切换到下一个就绪进程进行执行。实现时间片轮转的方式很容易想到，根据上一篇举例的时钟中断，我们可以设计实现如下

1. 设置定时芯片隔N毫秒发出时钟中断
2. 设计时钟中断的执行程序完成以下步骤
   • 获取当前任务结构
   • 将当前任务时间片-1
   • 判断当前任务时间片是否剩余
   • 若时间片有剩余，则中断返回，继续执行当前任务
   • 若时间片用尽，则根据CPL权限标志判断当前任务为内核任务，还是用户任务
   • 若为内核任务，直接中断返回。（因为内核任务不允许被抢占）
   • 若为用户任务，则执行任务调度，完成任务切换
3. 将设计好的中断程序与时钟中断向量号绑定。即修改idt

实际上，linux内核也是这么干的。根据源码，可以进行印证。
设置定时芯片隔N毫秒发出时钟中断 kernel\sched.c

 // 下面代码用于初始化 8253 定时器。通道 0，选择工作方式 3，二进制计数方式。通道 0 的
 // 输出引脚接在中断控制主芯片的 IRQ0 上，它每 10 毫秒发出一个 IRQ0 请求。LATCH 是初始
 // 定时计数值。
outb_p(0x36,0x43); /* binary, mode 3, LSB/MSB, ch 0 */
outb_p(LATCH & 0xff , 0x40); /* LSB */ // 定时值低字节。
outb(LATCH >> 8 , 0x40); /* MSB */ // 定时值高字节。

将设计好的中断程序与时钟中断向量号绑定。即修改idt kernel\sched.c

	set_intr_gate(0x20,&timer_interrupt);

设计时钟中断的执行程序 kernel\system_call.s

_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

此处具体代码不进行注释了，需要注意的是，上述中断执行程序最后会调用do_timer，并且将CPL放入eax，作为do_timer的参数（ps:c语言函数汇编后会自动在函数名前加上下划线，如_do_timer）
do_timer kernel/sched.c

void do_timer(long cpl)
{
	extern int beepcount;
	extern void sysbeepstop(void);

	if (beepcount)
		if (!--beepcount)
			sysbeepstop();

	if (cpl)//cpl表示当前被中断的进程是用户态还是内核态
		current->utime++;//给用户程序运行时间+1
	else
		current->stime++;//内核程序运行时间+1

	if (next_timer) {// next_timer 是连接jiffies变量的所有定时器的事件链表
	// 可以这样想象，jiffies是一个时间轴，然后这个时间轴上每个绳结上绑了一个事件，运行到该绳结就触发对应的事件
		next_timer->jiffies--;
		while (next_timer && next_timer->jiffies <= 0) {
			void (*fn)(void);
			
			fn = next_timer->fn;
			next_timer->fn = NULL;
			next_timer = next_timer->next;
			(fn)();
		}
	}
	if (current_DOR & 0xf0)//取高四位
		do_floppy_timer();
	if ((--current->counter)>0) return;
	current->counter=0;//counter进程的时间片为0，task_struct[]是进程的向量表 
	//counter在哪里用？ 进程的调度就是task_struct[]中检索，找时间片最大的进程对象来运行 直到时间片为0退出 之后再进行新一轮调用
	//counter在哪里被设置？ 当task_struct[]所有进程的counter都为0，就进行新一轮的时间片分配
	if (!cpl) return;
	schedule();//这个就是进行时间片分配
}

上述代码实现了前述具体过程

• 获取当前任务结构
• 将当前任务时间片-1
• 判断当前任务时间片是否剩余
• 若时间片有剩余，则中断返回，继续执行当前任务
• 若时间片用尽，则根据CPL权限标志判断当前任务为内核任务，还是用户任务
• 若为内核任务，直接中断返回。（因为内核任务不允许被抢占）
• 若为用户任务，则执行任务调度，完成任务切换schedule()

任务调度与任务切换

进一步地，看看schedule()做哪些事情。这部分我直接摘抄《linux内核完全注释》书中内容。

内核中的调度程序用于选择系统中下一个要运行的进程。这种选择运行机制是多任务操作系统的基础。调度程序可以看作为在所有处于运行状态的进程之间分配 CPU 运行时间的管理代码。由前面描述可知，Linux 进程是抢占式的，但被抢占的进程仍然处于 TASK_RUNNING 状态，只是暂时没有被 CPU 运行。进程的抢占发生在进程处于用户态执行阶段，在内核态执行时是不能被抢占的。为了能让进程有效地使用系统资源，又能使进程有较快的响应时间，就需要对进程的切换调度采用一定的调度策略。在 Linux 0.12 中采用了基于优先级排队的调度策略。

schedule()函数首先扫描任务数组。通过比较每个就绪态（TASK_RUNNING）任务的运行时间递减滴答计数 counter 的值来确定当前哪个进程运行的时间最少。哪一个的值大，就表示运行时间还不长，于是就选中该进程，并使用任务切换宏函数切换到该进程运行。如果此时所有处于 TASK_RUNNING 状态进程的时间片都已经用完，系统就会根据每个进程的优先权值 priority，对系统中所有进程（包括正在睡眠的进程）重新计算每个任务需要运行的时间片值 counter。

void schedule(void)
{
	int i,next,c;
	struct task_struct ** p;

/* check alarm, wake up any interruptible tasks that have got a signal */
//忽略一部分关于alarm的代码

/* this is the scheduler proper: */
	// 以下思路，循环task列表 根据counter大小决定进程切换
	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最大的task
				c = (*p)->counter, next = i;
		}
		if (c) break;//如果c找到了，就终结循环，说明找到了
		//进行时间片的重新分配
		for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
			if (*p)//这里很关键，在低版本内核中，是进行优先级时间片轮转分配，这里搞清楚了优先级和时间片的关系
			//counter = counter/2 + priority
				(*p)->counter = ((*p)->counter >> 1) +
						(*p)->priority;
	}
	//切换到下一个进程 这个功能使用宏定义完成的
	switch_to(next);
}

swtich_to : linux/sched.h 用于进行任务的切换

#define switch_to(n) {\
struct {long a,b;} __tmp; \
__asm__("cmpl %%ecx,_current\n\t" \
	"je 1f\n\t" \
	"movw %%dx,%1\n\t" \
	"xchgl %%ecx,_current\n\t" \
	"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])); \
}

内联汇编的语法在此不展开，主要切换语句为 ljmp %0 可简单等同于 ljmp _TSS(n)

_TSS(n)表示第n个任务对应的TSS段选择符。相当于通过ljmp TSS段选择符这一单条语句便能实现任务的切换，这是CPU自动完成的。为了解释清楚这一点，引出TSS的介绍

TSS任务状态段

用于恢复一个任务执行的处理器状态信息被保存在称为任务状态段 TSS（Task state segment）的段中。下图给出了 32 位 CPU 使用的 TSS 的格式。TSS 段中各字段可分成两大类：动态字段和静态字段。

简而言之，TSS是用来存放任务上下文的一段存储空间。每当CPU切换任务时，只需要切换当前的TSS即可。那么CPU如何知道当前的TSS在哪呢？

回忆上一篇保护模式的寻址过程，CPU寻址需要根据段寄存器中的段选择符从GDT中找到对应段描述符，从而获取段基址。那么TSS的位置也一样，其同样是一块内存空间，需要寻址。因此，GDT中需要存储关于TSS的段描述符，并且tr寄存器专门用于存放TSS的段选择符。

换言之，CPU根据tr中的段选择符，找到存放于GDT上的TSS段选择符，从而能够获得TSS的线性地址，从而知晓当前任务上下文。同时我们可以知道，CPU切换任务时，无需将上下文压栈，而是更新并记录到对应TSS段中即可。正是CPU自己实现了通过TSS切换的机制，在编写内核过程中，这部分的代码就十分简洁。整个过程如下图所示

TSS的创建与销毁等内容个人认为放在任务管理部分介绍会更好，因此在此先不展开。