linux内核进程调度以及定时器实现机制（看完悟了！）
一、2.6版以前内核进程调度机制简介
Linux的进程管理由进程控制块、进程调度、中断处理、任务队列、定时器、bottom half队列、系统调用、进程通信等等部分组成。
进程调用分为实时进程调度和非实时进程调度两种。前者调度时，可以采用基于动态优先级的轮转法（RR），也可以采用先进现出算法（FIFO）。后者调度时，一律采用基于动态优先级的轮转法。某个进程采用何种调度算法由改进程的进程控制块中的某些属性决定，没有专门的系统用来处理关于进程调度的相关事宜。Linux的进程调度由schedule（）函数负责，任何进程，当它从系统调用返回时，都会转入schedule（），而中断处理函数完成它们的响应任务以后，也会进入schedule（）。
1、进程控制块数据结构
Linux系统的进程控制块用数据结构task_struct表示，这个数据结构占用1680个字节，具体的内容不在这里介绍，详细内容见《Linux内核2.4版源代码分析大全》第二页。
进程的状态主要包括如下几个：
TASK_RUNNING 正在运行或在就绪队列run-queue中准备运行的进程，实际参与进程调度。
TASK_INTERRUPTIBLE 处于等待队列中的进程，待资源有效时唤醒，也可由其它进程通过信号或定时中断唤醒后进入就绪队列run-queue。
TASK_UNINTERRUPTIBLE 处于等待队列的进程，待资源有效时唤醒，不也可由其它进程通过信号或者定时中断唤醒。
TASK_ZOMBIE 表示进程结束但尚未消亡的一种状态（僵死），此时，进程已经结束运行并且已经释放了大部分资源，但是尚未释放进程控制块。
TASK_STOPPED 进程暂停，通过其它进程的信号才能唤醒。
所有进程（以PCB形式）组成一个双向列表。next_task和prev_task就是链表的前后向指针。链表的头尾都是init_task（init进程）。不过进程还要根据其进程ID号插入到一个hash表当中，目的是加快进程搜索速度。
【文章福利】小编推荐自己的Linux内核技术交流群:【891587639】整理了一些个人觉得比较好的学习书籍、视频资料共享在群文件里面，有需要的可以自行添加哦！！！（含视频教程、电子书、实战项目及代码)
2、进程调度
Linux进程调度由schedule（）执行，其任务是在run-queue队列中选出一个就绪进程。
每个进程都有一个调度策略，在它的task_struct中规定（policy属性），或为SCHED_RR,SCHED_FIFO，或为SCHED_OTHER。前两种为实时进程调度策略，后一种为普通进程调度策略。
用户进程由do_fork（）函数创建，它也是fork系统调用的执行者。do_fork（）创建一个新的进程，继承父进程的现有资源，初始化进程时钟、信号、时间等数据。完成子进程的初始化后，父进程将它挂到就绪队列，返回子进程的pid。
进程创建时的状态为TASK_UNINTERRUPTIBLE，在do_fork（）结束前被父进程唤醒后，变为TASK_RUNNING。处于TASK_RUNNING状态的进程被移到就绪队列中，当适当的时候由schedule（）按CPU调度算法选中，获得CPU。
如果进程采用轮转法，当时间片到时（10ms的整数倍），由时钟中断触发timer_interrupt（）函数引起新一轮的调度，把当前进程挂到就绪队列的尾部。获得CPU而正在运行的进程若申请不到某个资源，则调用sleep_on（）或interruptible_sleep_on（）睡眠，并进入就绪队列尾。状态尾TASK_INTERRUPTIBLE的睡眠进程当它申请的资源有效时被唤醒，也可以由信号或者定时中断唤醒，唤醒以后进程状态变为TASK_RUNNING，并进入就绪队列。
首先介绍一下2.6版以前的的调度算法的主要思想，下面的schedule（）函数是内核 2.4.23 中摘录的：
3、进程上下文切换
首先进程切换需要做什么？它做的事只是保留正在运行进程的"环境"，并把将要运行的进程的"环境"加载上来，这个环境也叫上下文。它包括各个进程"公用"的东西，比如寄存器。
下一个问题，旧的进程环境保存在那，新的进程环境从那来，在i386上，有个tss段，是专用来保存进程运行环境的。在Linux来说，在结构task_struct中有个类型为struct thread_struct的成员叫tss，如下：
然后下面就是load进程next的ldt，页表，fs，gs，debug寄存器。
因为Linux一般并不使用ldt，所以它们一般会指向一个共同的空的ldt段描述符，这样就可能不需要切换ldt了，如果进程next和prev是共享内存的话，那么页表的转换也就不必要了（这一般发生在clone时）。
二、2.6版内核对进程调度的优化
1.新调度算法简介
2.6版本的Linux内核使用了新的调度器算法，称为O（1）算法，它在高负载的情况下执行得非常出色，并在有多个处理器时能够很好地扩展。
2.4版本的调度器中，时间片重算算法要求在所有的进程都用尽它们的时间片后，新时间片才会被重新计算。在一个多处理器系统中，当进程用完它们的时间片后不得不等待重算，以得到新的时间片，从而导致大部分处理器处于空闲状态，影响SMP的效率。此外，当空闲处理器开始执行那些时间片尚未用尽的、处于等待状态的进程时，会导致进程开始在处理器之间“跳跃”。当一个高优先级进程或交互式进程发生跳跃时，整个系统的性能就会受到影响。
新调度器解决上述问题的方法是，基于每个CPU来分布时间片，并取消全局同步和重算循环。调度器使用了两个优先级数组，即活动数组和过期数组，可以通过指针来访问它们。活动数组中包含所有映射到某个CPU且时间片尚未用尽的任务。过期数组中包含时间片已经用尽的所有任务的有序列表。如果所有活动任务的时间片都已用尽，那么指向这两个数组的指针互换，包含准备运行任务的过期数组成为活动数组，而空的活动数组成为包含过期任务的新数组。数组的索引存储在一个64位的位图中，所以很容易找到最高优先级的任务。
新调度器的主要优点包括：
SMP效率如果有工作需要完成，所有处理器都会工作。 等待进程没有进程需要长时间地等待处理器，也没有进程会无端地占用大量的CPU时间。SMP进程映射进程只映射到一个CPU，而且不会在CPU之间跳跃。SMP进程映射进程只映射到一个CPU，而且不会在CPU之间跳跃。 负载平衡调度器会降低那些超出处理器负载能力的进程的优先级。 交互性能即使在高负载的情况下，系统花费很长时间来响应鼠标点击或键盘输入的情况也不会再发生。
2.6版内核中，进程调度经过重新编写，调度程序不需每次都扫描所有的任务，而是在一个任务变成就绪状态时将其放到一个名为“当前”的队列中。当进程调度程序运行时，只选择队列中最有利的任务来执行。这样，调度可以在一个恒定的时间里完成。当任务执行时，它会得到一个时间段，或者在其转到另一线程之前得到一段时间的处理器使用权。当时间段用完后，任务会被转移到另一个名为“过期”的队列中。在该队列中，任务会根据其优先级进行排序。
从某种意义上说，所有位于“当前”队列的任务都将被执行，并被转移到“过期”队列中。当这种事情发生时，队列就会进行切换，原来的“过期”队列成为“当前”队列，而空的“当前”队列则变成“过期”队列。由于在新的“当前”队列中，任务已经被排列好，调度程序现在使用简单的队列算法，即总是取当前队列的第一个任务进行执行。这个新过程要比老过程快得多。
2、2.6版新调度算法分析
2.2.6版新调度算法分析
3、2.6版新调度算法流程图
三、内核中断及定时器实现分析
定时器是Linux提供的一种定时服务的机制。它在某个特定的时间唤醒某个进程，来做一些工作。Linux初始化时，init_IRQ（）函数设定8253的定时周期为10ms（一个tick值）。同样，在初始化时，time_init（）用setup_irq（）设置时间中断向量irq0，中断服务程序为timer_interrupt。
在2.4版内核及较早的版本当中，定时器的中断处理采用底半机制，底半处理函数的注册在start_kernel（）函数中调用sechd_init（），在这个函数中又调用init_bh(TIMER_BH, timer_bh)注册了定时器的底半处理函数。然后系统才调用time_init（）来注册定时器的中断向量和中断处理函数。
在中断处理函数timer_interrupt（）中，主要是调用do_timer（）函数完成工作。do_timer（）函数的主要功能就是调用mark_bh（）产生软中断，随后处理器会在合适的时候调用定时器底半处理函数timer_bh（）。在timer_bh（）中，实现了更新定时器的功能。 2.4.23 版的do_timer（）函数代码如下（经过简略）：
四、系统调用的实现过程
Linux系统调用的形式与POSIX兼容，也是一套C语言函数名的集合，入fock（），read（）等等共221个。系统调用是通过INT 0x80软中断调用进入内核，然后根据系统调用号分门别类的进行服务。
系统调用号：文件include/asm-i386/unistd.h为每一个系统调用规定了唯一的编号，这个编号与真正的响应函数之间的关系是利用系统调用号为数组的下标，可以在sys_call_table（系统调用表数组）中查找对应的响应函数的sys_name的入口地址。
系统调用表：系统调用表sys_call_table是一组宏定义，将系统调用的编号和相应的内核系统调用处理函数的入口地址绑定。
内核宏定义syscallN（）用于系统调用的格式转换和参数的传递。其中N取0～6之间的任意整数。参数个数为N的系统调用由syscallN负责格式转换和参数传递。对系统调用的初始化，即是对INT 0x80的初始化。系统启动时，汇编子程序setup_idt准备了256项的idt表。设置0x80号软中断服务程序system_call，这个就是所有系统调用的总入口。
当进程需要进行系统调用时，必须以C语言函数的形式写一句系统调用命令。该命令如果已经在某个头文件中由相应的syscallN（）展开，则用户程序必须包含该头文件。当进程执行到系统调用命令时，实际上执行的是syscallN（）展开的函数。系统调用的参数由个寄存器传递，然后执行INT 0x80中断，以内核态进入入口地址system_call。
从system_call入口的汇编程序的主要功能是：
保存寄存器当前值； 检验是否为合法的系统调用 根据系统调用表sys_call_table和EAX持有的系统调用号找出并转入系统调用响应函数； 从该响应函数返回后，让EAX寄存器保存函数返回值，跳转至ret_from_sys_call（arch/i386/kernel/entry.S）。
以ret_from_sys_call入口的汇编程序段在Linux进程管理中起着十分重要的作用。所有系统调用结束前，以及大部分中断服务程序返回前，都会跳转至此入口地址。反过来，该段程序也不仅仅为系统调用服务，它还要处理中断嵌套、bottom half队列、CPU调度、信号等事务。
