linux 0.01 初始化及进程调度

Linux0.01时Linus在1991年发布的第一个Linux版本，最初的这个版本的Linux代码量并不多，但是很多开始的设计在之后的多个版本中都一直保留，一般来说操作系统的设计分块一般不会有大的改动，主要包括启动加载初始化、内存管理、进程调度以及文件系统等。在The Linux Kernel Archive可以下载Linux内核源代码，Linux0.01代码分块来说主要包括boot、fs、include、kernel、lib、mm、tools和Makefile文件，主要包含了启动、文件系统、头文件、内核、内存管理等。

1 引导启动

一般来说，绝大多数x86硬件上的系统启动过程应该都是相似的，都是在硬件通电之后执行BIOS硬件程序，BIOS将系统的引导扇区（512B）加载到0x7c00处，BIOS自检之类的事情做完之后就会跳转到0x7c00执行引导扇区的入口。需要注意的就是此时的代码均为16位，为了兼容以前的系统即使现在的系统可能都到64位了，但是启动的时候还是得从16位实模式开始，后面会经过一系列过程开启保护模式进入32位。几乎任何一个x86平台的os应该都要经历这样的过程，不同的就是在加载启动过程中，不同的系统在启动过程中处理的方式可能不同，如下是linux-0.01引导时的流程图。

引导程序一开始被BIOS加载到0x7c00处，开始执行，然后做的第一件事情就是将自身也就是从0x7c00开始的512B的代码给挪动到0x90000处，这样的目的是为了给以后将会加载到这里的系统sys代码腾位置。引导扇区代码加载到0x90000之后就不会再移动了，0x7c00移动自身之后马上跳转到0x90000处执行剩下的任务，剩下的任务包括先读硬盘将sys开始加载到0x10000处，注意读硬盘是需要通过中断来进行的，这里使用的中断只能是BIOS中断，这就是为什么要将sys加载到0x10000处的原因，因为BIOS中断处理程序都在更低的内存区间。

关中断

这里在加载系统代码到0x10000之后一个重要的操作就是关闭中断，这里关闭的中断其实就是BIOS中断，前面提到BIOS中断处理程序都在比较低的内存区间，那么这里关中断的目的其实就比较明显了，就是不再使用BIOS中断，并且将系统代码移动到从0x00000开始的区间。然而现在关中断的目的其实还不止于此，在进入保护模式之前，需要进行一系列操作来建立起保护模式的分段分页以及中断机制，在这些全部建立完成之前是不能允许中断的，因为还没有建立起相应的中断相应程序。

实模式和保护模式

进入保护模式之前还是需要谈一谈实模式与保护模式之间的区别，最直接的区别就是16位模式下寄存器只能够处理16位的数，访存时采用的cs:ip的方式来进行，将cs代码段寄存器的值左移一位加上ip的值就是访存地址，所以16位实模式下能够访问的内存地址其实是20位，最大地址为0xfffff，也就是说最多能够使用1MB的内存。相应的保护模式能够处理32位数能够直接访问4GB的内存就要宽松得多，当然这中间需要打开A20地址才能够进行访问。

实模式和保护模式的区别还不止于此，之所以称16位为实模式是因为cs:ip访问的就是对应的物理地址，而进入保护模式之后能够控制代码段的访问权限，并且在经过分页之后有虚拟地址和物理地址的区别，用户进程不再能够直接访问物理地址。

在将关闭中断并将sys移动到0x00000之后，通过设置idt、gdt，打开A20、设置中断向量等一系列操作来允许保护模式，然后跳转到0x00000处进入32位入口。需要注意的是在进入32位入口之后，还需要通过在32位模式中再次设置一次gdt、idt等，其中过程较为繁琐，不再赘述。

2 初始化

Linux0.01的初始化部分内容比较少，主要包括从读取CMOS调整时间、设置终端键盘及串行口、设置软中断，以及进行调度初始化，之后进行缓冲区及硬盘的初始化。在这些全部都设置完全之后这里才最终打开了中断，值得一提的是操作系统中的系统调用都是依托于trap的，而trap实现的本质还是利用了中断机制，系统调用的目的就是能够从用户态切换到内核态并执行相应的功能。

void main(void)		
{			
	time_init();
	tty_init();
	trap_init();
	sched_init();
	buffer_init();
	hd_init();
	sti();
	move_to_user_mode();
	if (!fork()) {		
		init();
	}

	for(;;) pause();
}

用户态和内核态

关于用户态和内核态的区分，体现了来自Unix/Linux的设计哲学，就是对不同的操作赋予不同的执行等级，特别重要的操作只能由内核来执行，而不能让用户态随意执行，这样的设计与x86的硬件结构也相对应，x86中cpu执行指令分为0-3四个特权级别，一般的系统如Linux实际上都只使用了0特权级作为内核态，使用3特权级作为用户态。这里Linux的初始化在打开中断之后使用move_to_user_mode()切换到用户态，使得当前进程实际上也是一个用户态的进程，也就是说在Linux0.01中没有完全在内核态执行的进程，即使进程0（也就是现在正在执行的这个进程）也是执行在用户态的。

在Linux中除了进程0其它所有的进程都是从某个进程fork得到的子进程，fork是一个系统调用会切换到内核态进行进程的创建等操作，这里进程0使用fork创建了一个子进程1执行init()函数，进程1在执行完init()函数之后其实就退出了，但是在init()的过程中会使用execve来创建进程2来进行交互终端以及bash的启动过程，这里不再赘述。

需要注意的就是这里的进程0实际上是一个空闲进程，基本上啥也不干，不停的调用pause，而pause实际上也是一个系统调用，会切换到内核态调用schedule进行进程调度。也就是说在没有其它进程能执行的时候进程0会被调度，而进程0被调度执行又会调用schedule来调度其它进程执行。

3 进程

对于Linux而言，进程控制块应该是最重要的结构了，linux-0.01中task_struct的内容不多，我还是进行了一定的删减，剩下的是与进程调度相关的内容，首先就是进程的状态state字段了，Linux进程主要包括5中状态，分别为RUNNING、INTERRUPTIBLE、UNINTERRUPTIBLE、ZOMBIE和STOPPED，分别体现了进程当前所处的状态，这几种状态中只有RUNNING是能够被调度执行的，INTERRUPTIBLE和UNINTERRUPTIBLE状态是因访问某种资源而被阻塞，ZOMBIE和STOPPED状态是进程退出时的状态。

struct task_struct {
	long state;	
	long counter, priority, signal;
	//信号处理函数指针、alarm及运行时间等
	//exit_code及pid、父进程id等
	int tty;	/* -1 if no tty, so it must be signed */
	struct m_inode * pwd, * root;
	struct file * filp[NR_OPEN];
	struct desc_struct ldt[3];	/* 1 - cs 2 - ds& ss */
	struct tss_struct tss;
};

进程控制块中priority字段表示进程的运行优先级，在调度的时候会被用到，linux-0.01进程切换时使用的是硬切换，也就是借助TSS来进行切换，而现在更多的系统采用的都是软切换，直接进行运行上下文的切换，软切换相对硬切换性能要高不少。

进程管理

Linux-0.01使用一个大小为64的数组来管理进程，并且有一个current指针永远指向当前正在执行的进程控制块，前面提到所有的进程都由其父进程fork得到，进程0是所有进程的父进程，这里的INIT_TASK就是进行进程0进程控制块的初始化，现在current指针也是指向了进程0。

#define NR_TASKS 64
struct task_struct * task[NR_TASKS] = {& (init_task.task), };
static union task_union init_task = {INIT_TASK,};
struct task_struct *current = & (init_task.task);

进程调度

前面提到进程0的功能就是不断的调用pause，进程0其实就是空闲进程idle,当没有其它进程执行的时候就会调度进程0，然后进程0又会执行schedule()让出cpu。

for(;;) pause()//进程0一直循环执行于此

int sys_pause(void) //pause通过系统调用进入内核态
{ //设置进程状态为可被打断，然后schedule()其它进程来执行
	current->state = TASK_INTERRUPTIBLE;
	schedule();
	return 0;
}

Linux-0.01进程调度的核心在schedule函数，直白点说就是要找一个能够执行的进程让它执行，问题在于那么多进程抢着要执行该让谁来执行就成了调度策略的问题，首先前面提到进程所处的状态，如果进程因为某些资源而等待，那么肯定不能让其执行，或者进程已经退出或者没有完全退出而成了僵尸进程都是不能够执行的。

void schedule(void) {
	int i,next,c;
	struct task_struct ** p;
	for(p = /*从进程控制块数组结尾往前遍历*/ )
		/* 检查并唤醒alarm时间到了或者被信号中断的interruptible的进程*/

	/* 选择下一个执行的进程*/
	while (1) {
		c = -1;
		while (--i) {//从后往前遍历进程控制块数组
			if (!*--p) continue; //控制块地址为空，继续找下一个
			if ((*p)->state == TASK_RUNNING & &  (*p)->counter > c)
				c = (*p)->counter, next = i;
		} //这里其实就是查找可执行并且counter最大的进程控制块
		if (c) break;
		for(p = /*从进程控制块数组结尾往前遍历*/ )
			if (*p) //更新counter=counter/2+priority
	}
	switch_to(next); 
}

从调度的逻辑中就可以看出来，首先是遍历所有的进程控制块，检查并唤醒alarm时间到了或者被信号中断的interruptible的进程，将其状态设为可执行。下一步才是要从可执行的进程中寻找最应该执行的那一个，linux-0.01比较进程的方式是使用进程的counter字段，让counter字段最大的那个进程执行。如果所有的counter都小于0的话，优先级字段priority就派上用场了，借助priority来更新counter，这样优先级大的进程会提前被调度执行。

schedule的调用路径：

  • sys_pause：让当前进程释放cpu、被调度
  • sleep_on(p)：请求的资源被p所持有，故而睡眠并调度其它程序，睡眠期间不可被打断
  • interruptible_sleep_on（p)：功能同sleep_on，只是睡眠期间可被打断
  • do_timer：超时了，调度
  • tty_write：终端写数据了，调度
  • release(p)：释放进程控制块p，及其所有资源，调度
  • do_exit：进程退出，调度