深入分析Linux内核源码－第五章进程调度

char_yc

深入分析Linux内核源码-第五章进程调度

【摘要】本章介绍了Linux系统的时间机制，包括系统时钟和硬件时钟之间的关系、各种时间标准的转换、时钟中断tick的维护；接着介绍了进程调度的几种常见算法、何时进行内核调度及选择相应该调度的进程，并分析了调度程序的实现；最后介绍了进程切换的硬件支持和软件实现。
【关键字】Tick，系统时间，硬件CMOS时钟，Jiffies，调度算法，RR，Goodness，Schedule，进程切换，Switch_mm

第五章进程调度... 1
5.1 Linux时间系统... 1
5.1.1 时钟硬件... 1
5.1.2 时钟运作机制... 2
5.1.3  Linux时间基准... 2
5.1.4 Linux的时间系统... 3
5.2 时钟中断... 3
5.2.1 时钟中断的产生... 3
5.2.2.Linux实现时钟中断的全过程... 4
5.3 Linux的调度程序－Schedule( ) 7
5.3.1基本原理... 7
5.3.2 Linux进程调度时机... 8
5.3.3 进程调度的依据... 10
5.3.4 进程可运行程度的衡量... 10
5.3.5进程调度的实现... 11
5.4 进程切换... 14
5.4.1 硬件支持... 14
5.4.2进程切换... 16

第五章进程调度
5.1 Linux时间系统
计算机最基本的时间单元是时钟周期，例如取指令、执行指令、存取内存等。时间系统是计算机系统非常重要的组成部分，特别是对于Unix类分时系统尤为重要。时间系统主要任务是维持系统时间并且防止某个进程独占CPU及其他资源，也就是驱动进程的调度。

5.1.1 时钟硬件
大部分PC机中有两个时钟源，他们分别叫做RTC和OS（操作系统）时钟。RTC（Real Time Clock，实时时钟）也叫做CMOS时钟，它是PC主机板上的一块芯片，它靠电池供电，即使系统断电，也可以维持日期和时间。由于它独立于操作系统，所以也被称为硬件时钟，它为整个计算机提供一个计时标准，是最原始最底层的时钟数据。

Linux只用RTC来获得时间和日期；然而，通过作用于/dev/rtc设备文件，也允许进程对RTC编程。通过执行/sbin/clock系统程序，系统管理员可以配置时钟。

OS时钟产生于PC主板上的定时/计数芯片，由操作系统控制这个芯片的工作，OS时钟的基本单位就是该芯片的计数周期。在开机时操作系统取得RTC中的时间数据来初始化OS时钟，然后通过计数芯片的向下计数形成了OS时钟，它更应该被称为一个计数器。OS时钟只在开机时才有效，而且完全由操作系统控制，所以也被称为软时钟或系统时钟。下面我们重点描述OS时钟的产生。

OS时钟输出脉冲信号，接到中断控制器上，产生中断信号，触发后面要讲的时钟中断，由时钟中断服务程序维持OS时钟的正常工作。

5.1.2 时钟运作机制
RTC和OS时钟之间的关系通常也被称作操作系统的时钟运作机制。一般来说，RTC是OS时钟的时间基准，操作系统通过读取RTC来初始化OS时钟，此后二者保持同步运行，共同维持着系统时间。保持同步运行是什么意思呢？就是指操作系统运行过程中，每隔一个固定时间会刷新或校正RTC中的信息。

                      图5.2  时钟运作机制
我们可以看到，RTC处于最底层，提供最原始的时钟数据。OS时钟建立在RTC之上，初始化完成后将完全由操作系统控制，和RTC脱离关系。操作系统通过OS时钟提供给应用程序所有和时间有关的服务。

5.1.3 Linux时间基准
以上我们了解了RTC（实时时钟、硬件时钟）和OS时钟（系统时钟、软时钟）。下面我们具体描述OS时钟。OS时钟是由可编程定时/计数器产生的输出脉冲触发中断而产生的。输出脉冲的周期叫做一个“时钟滴答”。计算机中的时间是以时钟滴答为单位的，每一次时钟滴答，系统时间就会加1。操作系统根据当前时钟滴答的数目就可以得到以秒或毫秒等为单位的其他时间格式。

定义“时间基准”的目的是为了简化计算，这样计算机中的时间只要表示为从这个时间基准开始的时钟滴答数就可以了。“时间基准是由操作系统的设计者规定的。例如DOS的时间基准是1980年1月1日，Unix的时间基准是1970年1月1日上午12点，Linux的时间基准是1970年1月1日凌晨0点。

5.1.4 Linux的时间系统
OS时钟记录的时间也就是通常所说的系统时间。系统时间是以“时钟滴答”为单位的，而时钟中断的频率决定了一个时钟滴答的长短，例如每秒有100次时钟中断，那么一个时钟滴答的就是10毫秒（记为10ms），相应地，系统时间就会每10ms增1。

Linux中用全局变量jiffies表示系统自启动以来的时钟滴答数目。在/kernel/time.c中定义如下：
unsigned long volatile jiffies
在jiffies基础上，Linux提供了如下适合人们习惯的时间格式，在/include/linux/time.h中定义如下：
struct timespec {               ／*  这是精度很高的表示*／
       long tv_sec;             ／* 秒 （second） *／
       long tv_nsec;           /* 纳秒：十亿分之一秒（ nanosecond）*／
}；

struct timeval  {               ／* 普通精度   *／
       int    tv_sec;             /*  秒   *／
       int    tv_usec;           /* 微秒：百万分之一秒（microsecond）*／
};

struct timezone {                     /*  时区  *／
       int    tz_minuteswest;            ／*  格林尼治时间往西方的时差 *／
       int    tz_dsttime;                  /* 时间修正方式 *／
};

tv_sec表示秒（second），tv_usec表示微秒（microsecond），tv_nsec表示纳秒（nanosecond）。定义tb_usec和tv_nsec的目的是为了适用不同的使用要求，不同的场合根据对时间精度的要求选用这两种表示。另外，Linux还定义了用于表示更加符合大众习惯的时间表示：年、月、日。但是万变不离其宗，所有的时间应用都是建立在jiffies基础之上的。简而言之，jiffies产生于时钟中断！

5.2 时钟中断
5.2.1 时钟中断的产生
“时钟中断”是特别重要的一个中断，因为整个操作系统的活动都受到它的激励。系统利用时钟中断维持系统时间、促使环境的切换，以保证所有进程共享CPU；利用时钟中断进行记帐、监督系统工作以及确定未来的调度优先级等工作。可以说，“时钟中断”是整个操作系统的脉搏。
时钟中断的物理产生如图5.3所示：
                       
图5.3 8253和8259A的物理连接方式
脉冲信号接到中断控制器8259A_1的0号管脚，触发一个周期性的中断，我们就把这个中断叫做时钟中断，时钟中断的周期，也就是脉冲信号的周期，我们叫做“滴答”或“时标”（tick）。从本质上说，时钟中断只是一个周期性的信号，完全是硬件行为，该信号触发CPU去执行一个中断服务程序，我们就把这个服务程序叫做时钟中断。

5.2.2.Linux实现时钟中断的全过程
1. 和时钟中断相关的函数
下面我们看时钟中断触发的服务程序，该程序代码比较复杂，分布在不同的源文件中，主要包括如下函数：
时钟中断程序：timer_interrupt( )；
中断服务通用例程do_timer_interrupt();
时钟函数：do_timer( )；
中断安装程序：setup_irq( );
中断返回函数：ret_from_intr( );

前三个函数的调用关系如下：
     timer_interrupt( )
              
                 do_timer_interrupt()
      
                               do_timer( )
(1) timer_interrupt( )
    这个函数大约每10ms被调用一次，实际上， timer_interrupt( )函数是一个封装例程，它真正做的事情并不多，该函数主要语句就是调用do_timer_interrupt()函数。

(2) do_timer_interrupt()
do_timer_interrupt()函数有两个主要任务，一个是调用do_timer( )，另一个是维持实时时钟(RTC，每隔一定时间段要回写)，其实现代码在/arch/i386/kernel/time.c中， 为了突出主题，笔者对以下函数作了改写，以便于读者理解：

static inline void do_timer_interrupt(int irq， void *dev_id， struct pt_regs *regs)
{
       do_timer(regs); /* 调用时钟函数，将时钟函数等同于时钟中断未尝不可*/
     
       if(xtime.tv_sec > last_rtc_update + 660)
update_RTC();
/*每隔11分钟就更新RTC中的时间信息，以使OS时钟和RTC时钟保持同步，11分钟即660秒，xtime.tv_sec的单位是秒，last_rtc_update记录的是上次RTC更新时的值 */
}
  其中，xtime是前面所提到的timeval类型，这是一个全局变量。

(3) 时钟函数do_timer() (在/kernel/sched.c中)
void do_timer(struct pt_regs * regs)
{
       (*(unsigned long *)&jiffies)++;  /*更新系统时间，这种写法保证对jiffies操作的原子性*/

update_process_times（）;
       ++lost_ticks;
       if( ! user_mode ( regs ) )
              ++lost_ticks_system;

              mark_bh(TIMER_BH);            
       if (tq_timer)                     
              mark_bh(TQUEUE_BH);
}

其中，update_process_times（）函数与进程调度有关，从函数的名子可以看出，它处理的是与当前进程与时间有关的变量，例如，要更新当前进程的时间片计数器counter，如果counter

与时间有关的事情很多，不能全都让这个函数去完成，这是因为这个函数是在关中断的情况下执行，必须处理完最重要的时间信息后退出，以处理其他事情。那么，与时间相关的其他信息谁去处理，何时处理？这就是由第三章讨论的后半部分去去处理。上面timer_interrupt()所做的事情就是上半部分。

（4）中断安装程序
     从上面的介绍可以看出，时钟中断与进程调度密不可分，因此，一旦开始有时钟中断就可能要进行调度，在系统进行初始化时，所做的大量工作之一就是对时钟进行初始化，其函数time_init ()的代码在/arch/i386/kernel/time.c中，对其简写如下：
void __init time_init(void)
  {
xtime.tv_sec=get_cmos_time();
xtime.tv_usec=0;
setup_irq（0，＆irq0）;
}
   
   其中的get_cmos_time()函数就是把当时的实际时间从CMOS时钟芯片读入变量xtime中，时间精度为秒。而setup_irq（0，＆irq0）就是时钟中断安装函数，那么irq0指的是什么呢，它是一个结构类型irqaction，其定义及初值如下：
static struct irqaction irq0  = { timer_interrupt， SA_INTERRUPT， 0， "timer"， NULL， NULL};
setup_irq(0， &irq0)的代码在/arch/i386/kernel/irq.c中，其主要功能就是将中断程序连入相应的中断请求队列，以等待中断到来时相应的中断程序被执行。

我们将有关函数改写如下，体现时钟中断的大意：
do_timer_interrupt( )          ／*这是一个伪函数 *／
{                                            
       SAVE_ALL                    ／*保存处理机现场 *／
       intr_count += 1;              ／* 这段操作不允许被中断 *／
       timer_interrupt()             ／* 调用时钟中断程序 *／
       intr_count -= 1;               
       jmp ret_from_intr             /* 中断返回函数 *／
}
      
   其中，jmp ret_from_intr 是一段汇编代码，也是一个较为复杂的过程，它最终要调用jmp ret_from_sys_call，即系统调用返回函数，而这个函数与进程的调度又密切相关，，因此，我们重点分析jmp ret_from_sys_call。
      
2．系统调用返回函数：
  系统调用返回函数的源代码在/arch/i386/kernel/entry.S中
ENTRY(ret_from_sys_call)
         cli                 # need_resched and signals atomic test
         cmpl $0，need_resched(%ebx)
         jne reschedule
         cmpl $0，sigpending(%ebx)
         jne signal_return
restore_all:
         RESTORE_ALL

         ALIGN
signal_return:
         sti              # we can get here from an interrupt handler
         testl $(VM_MASK)，EFLAGS(%esp)
         movl %esp，%eax
         jne v86_signal_return
         xorl %edx，%edx
         call SYMBOL_NAME(do_signal)
         jmp restore_all

         ALIGN
        v86_signal_return:
         call SYMBOL_NAME(save_v86_state)
         movl %eax，%esp
         xorl %edx，%edx
         call SYMBOL_NAME(do_signal)
         jmp restore_all
  ….
reschedule:
         call SYMBOL_NAME(schedule)    # test
        jmp ret_from_sys_call

这一段汇编代码就是前面我们所说的“从系统调用返回函数”ret_from_sys_call，它是从中断、异常及系统调用返回时的通用接口。这段代码主体就是ret_from_sys_call函数，在此我们列出相关的几个函数：
（1）ret_from_sys_call：主体
（2）reschedule：检测是否需要重新调度
（3）signal_return：处理当前进程接收到的信号
（4）v86_signal_return：处理虚拟86模式下当前进程接收到的信号
（5）RESTORE_ALL：我们把这个函数叫做彻底返回函数，因为执行该函数之后，就返回到当前进程的地址空间中去了。

可以看到ret_from_sys_call的主要作用有：
检测调度标志need_resched，决定是否要执行调度程序；处理当前进程的信号；恢复当前进程的环境使之继续执行。

最后我们再次从总体上浏览一下时钟中断：
每个时钟滴答，时钟中断得到执行。时钟中断执行的频率很高：100次/秒，时钟中断的主要工作是处理和时间有关的所有信息、决定是否执行调度程序以及处理下半部分。和时间有关的所有信息包括系统时间、进程的时间片、延时、使用CPU的时间、各种定时器，进程更新后的时间片为进程调度提供依据，然后在时钟中断返回时决定是否要执行调度程序。下半部分处理程序是Linux提供的一种机制，它使一部分工作推迟执行。

5.3 Linux的调度程序－Schedule( )
5.3.1基本原理
调度的实质就是资源的分配。系统通过不同的调度算法（Scheduling Algorithm）来实现这种资源的分配。通常来说，选择什么样的调度算法取决于的资源分配的策略（Scheduling Policy），在这里只说明与Linux调度相关的几种算法及这些算法的原理。
一个好的调度算法应当考虑以下几个方面：
（1）公平：保证每个进程得到合理的CPU时间。
（2）高效：使CPU保持忙碌状态，即总是有进程在CPU上运行。
（3）响应时间：使交互用户的响应时间尽可能短。
（4）周转时间：使批处理用户等待输出的时间尽可能短。
（5）吞吐量：使单位时间内处理的进程数量尽可能多。
很显然，这5个目标不可能同时达到，所以，不同的操作系统会在这几个方面中作出相应的取舍，从而确定自己的调度算法，例如UNIX采用动态优先数调度、BSD采用多级反馈队列调度、Windows采用抢先多任务调度等等。

下面来了解一下主要的调度算法及其基本原理：
1．时间片轮转调度算法
时间片（Time Slice）就是分配给进程运行的一段时间。在通常的轮转法中，系统将所有的可运行（即就绪）进程按先来先服务的原则，排成一个队列，每次调度时把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，系统发出信号，通知调度程序，调度程序便据此信号来停止该进程的执行，并将它送到运行队列的末尾，等待下一次执行；然后，把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证运行队列中的所有进程，在一个给定的时间内，均能获得一时间片的处理机执行时间。
2．优先权调度算法
为了照顾到紧迫型进程在进入系统后便能获得优先处理，引入了最高优先权调度算法。当将该算法用于进程调度时，系统将把处理机分配给运行队列中优先权最高的进程，这时，又可进一步把该算法分成两种方式：
(1) 非抢占式优先权算法（又称不可剥夺调度：Nonpreemptive Scheduling）
在这种方式下，系统一旦将处理机（CPU）分配给运行队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可将处理机分配给另一个优先权高的进程。这种调度算法主要用于批处理系统中，也可用于某些对实时性要求不严的实时系统中。
(2) 抢占式优先权调度算法（又称可剥夺调度：Preemptive Scheduling）
该算法的本质就是系统中当前运行的进程永远是可运行进程中优先权最高的那个。在采用这种调度算法时，每当出现一新的可运行进程，就将它和当前运行进程进行优先权比较，如果高于当前进程，将触发进程调度。这种方式的优先权调度算法，能更好的满足紧迫进程的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。Linux也采用这种调度算法。
3．多级反馈队列调度
这是时下最时髦的一种调度算法。其本质是：综合了时间片轮转调度和抢占式优先权调度的优点，即：优先权高的进程先运行给定的时间片，相同优先权的进程轮流运行给定的时间片。
4．实时调度
最后我们来看一下实时系统中的调度。什么叫实时系统，就是系统对外部事件有求必应、尽快响应。在实时系统中，广泛采用抢占调度方式，特别是对于那些要求严格的实时系统。因为这种调度方式既具有较大的灵活性，又能获得很小的调度延迟；但是这种调度方式也比较复杂。

5.3.2 Linux进程调度时机
Linux的调度程序是一个叫Schedule（）的函数，这个函数被调用的频率很高，由它来决定是否要进行进程的切换，如果要切换的话，切换到哪个进程等等。我们先来看在什么情况下要执行调度程序，我们把这种情况叫做调度时机。
Linux调度时机主要有：
1、进程状态转换的时刻：进程终止、进程睡眠；
2、当前进程的时间片用完时（current->counter=0）；
3、设备驱动程序主动调用schedule；
4、进程从中断、异常及系统调用返回到用户态时；
时机1，进程要调用sleep（）或exit（）等函数进行状态转换，这些函数会主动调用调度程序进行进程调度；
时机2，由于进程的时间片是由时钟中断来更新的，因此，这种情况和时机4是一样的。
时机3，当设备驱动程序执行长而重复的任务时，直接调用调度程序。在每次反复循环中，驱动程序都检查need_resched的值，如果必要，则调用调度程序schedule()主动放弃CPU。
时机4，如前所述，不管是从中断、异常还是系统调用返回，最终都调用ret_from_sys_call（），由这个函数进行调度标志的检测，如果必要，则调用调度程序。那么，为什么从系统调用返回时要调用调度程序呢？这当然是从效率考虑。从系统调用返回意味着要离开内核态而返回到用户态，而状态的转换要花费一定的时间，因此，在返回到用户态前，系统把在内核态该处理的事全部做完。

每个时钟中断（timer interrupt）发生时，由三个函数协同工作，共同完成进程的选择和切换，它们是：schedule（）、do_timer（）及ret_form_sys_call（）。我们先来解释一下这三个函数：
schedule（）：进程调度函数，由它来完成进程的选择（调度）；
do_timer（）：暂且称之为时钟函数，该函数在时钟中断服务程序中被调用，被调用的频率就是时钟中断的频率即每秒钟100次（简称100赫兹或100Hz）；
ret_from_sys_call（）：系统调用返回函数。当一个系统调用或中断完成时，该函数被调用，用于处理一些收尾工作，例如信号处理、核心任务等等。

这三个函数是如何协调工作的呢？
前面我们看到，时钟中断是一个中断服务程序，它的主要组成部分就是时钟函数do_timer（），由这个函数完成系统时间的更新、进程时间片的更新等工作，更新后的进程时间片counter作为调度的主要依据。在时钟中断返回时，要调用函数ret_from_sys_call（），前面我们已经讨论过这个函数，在这个函数中有如下几行：
cmpl $0， _need_resched
jne reschedule
     ……
restore_all:
     RESTORE_ALL
  
reschedule:
     call SYMBOL_NAME(schedule)   
     jmp ret_from_sys_call

这几行的意思很明显：检测 need_resched 标志，如果此标志为非0，那么就转到reschedule处调用调度程序schedule（）进行进程的选择。调度程序schedule（）会根据具体的标准在运行队列中选择下一个应该运行的进程。当从调度程序返回时，如果发现又有调度标志被设置，则又调用调度程序，直到调度标志为0，这时，从调度程序返回时由RESTORE_ALL恢复被选定进程的环境，返回到被选定进程的用户空间，使之得到运行。

Linux 调度程序和其他的UNIX调度程序不同，尤其是在“nice level”优先级的处理上，与优先权调度（priority高的进程最先运行）不同，Linux用的是时间片轮转调度（Round Robing），但同时又保证了高优先级的进程运行的既快、时间又长（both sooner and longer）。而标准的UNIX调度程序都用到了多级进程队列。大多数的实现都用到了二级优先队列：一个标准队列和一个实时（“real time”）队列。一般情况下，如果实时队列中的进程未被阻塞，它们都要在标准队列中的进程之前被执行，并且，每个队列中，“nice level”高的进程先被执行。

5.3.3 进程调度的依据
调度程序运行时，要在所有处于可运行状态的进程之中选择最值得运行的进程投入运行。选择进程的依据是什么呢？在每个进程的task_struct结构中有这么五项：
need_resched、nice、counter、policy 及rt_priority
need_resched: 在调度时机到来时，检测这个域的值，如果为1，则调用schedule() 。
counter: 进程处于运行状态时所剩余的时钟滴答数，每次时钟中断到来时，这个值就减1。当这个域的值变得越来越小，直至为0时，就把need_resched 域置1，因此，也把这个域叫做进程的“动态优先级”。
nice: 进程的“静态优先级”，这个域决定counter 的初值。只有通过nice()， sched_setparam()系统调用才能改变进程的静态优先级。
rt_priority: 实时进程的优先级
policy: 从整体上区分实时进程和普通进程，因为实时进程和普通进程的调度是不同的，它们两者之间，实时进程应该先于普通进程而运行，可以通过系统调用sched_setscheduler( )来改变调度的策略。对于同一类型的不同进程，采用不同的标准来选择进程。对于普通进程，选择进程的主要依据为counter和nice 。对于实时进程，Linux采用了两种调度策略，即FIFO（先来先服务调度）和RR（时间片轮转调度）。因为实时进程具有一定程度的紧迫性，所以衡量一个实时进程是否应该运行，Linux采用了一个比较固定的标准。实时进程的counter只是用来表示该进程的剩余滴答数，并不作为衡量它是否值得运行的标准，这和普通进程是有区别的。
     
5.3.4 进程可运行程度的衡量
函数goodness（）就是用来衡量一个处于可运行状态的进程值得运行的程度。该函数综合使用了上面我们提到的五项，给每个处于可运行状态的进程赋予一个权值（weight），调度程序以这个权值作为选择进程的唯一依据。函数主体如下：
static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)
{     int weight;     ／* 权值，作为衡量进程是否运行的唯一依据 *

       weight=-1;   
       if (p->policy&SCHED_YIELD)  
        goto out;  /*如果该进程愿意“礼让（yield）”，则让其权值为－1 *／
        switch(p->policy)  
       {
              /* 实时进程*/
              case SCHED_FIFO:
              case SCHED_RR:
                     weight = 1000 + p->rt_priority;

              /* 普通进程 */
              case SCHED_OTHER:
                  {     weight = p->counter;
                    if(!weight)
                        goto out
                     /* 做细微的调整*/
                     if (p->mm=this_mm||!p->mm)
                                   weight = weight+1;
                     weight+=20-p->nice;       /*在剩余counter一样的情况下，短进程优先*/                     
                     }     
   }
out:
    return weight;   /*返回权值*/
}

其中，在sched.h中对调度策略定义如下：
#define SCHED_OTHER             0
#define SCHED_FIFO              1
#define SCHED_RR                2
#define SCHED_YIELD             0x10

这个函数比较很简单。首先，根据policy区分实时进程和普通进程。实时进程的权值取决于其实时优先级，其至少是1000，与conter和nice无关。普通进程的权值需特别说明两点：
为什么进行细微的调整？如果p->mm为空，则意味着该进程无用户空间（例如内核线程），则无需切换到用户空间。如果p->mm=this_mm，则说明该进程的用户空间就是当前进程的用户空间，该进程完全有可能再次得到运行。对于以上两种情况，都给其权值加1，算是对它们小小的奖励。

进程的优先级nice是从早期Unix沿用下来的负向优先级，其数值标志“谦让”的程度，其值越大，就表示其越“谦让”，也就是优先级越低，其取值范围为－20～＋19，因此，（20-p->nice）的取值范围就是0～40。可以看出，普通进程的权值不仅考虑了其剩余的时间片，还考虑了其优先级，优先级越高，其权值越大。

根据进程调度的依据，调度程序就可以控制系统中的所有处于可运行状态的进程并在它们之间进行选择。

5.3.5进程调度的实现  
调度程序在内核中就是一个函数，为了讨论方便，我们同样对其进行了简化，略其对SMP的实现部分。   
asmlinkage void schedule(void)
{

  struct task_struct *prev， *next， *p; ／* prev表示调度之前的进程， next表示调度之后的进程 *／  
    struct list_head *tmp;
    int this_cpu， c;

      if (!current->active_mm) BUG();/*如果当前进程的的active_mm为空，出错*／
need_resched_back:            
           prev = current;         ／*让prev成为当前进程 *／
           this_cpu = prev->processor;

if (in_interrupt()) {／*如果schedule是在中断服务程序内部执行，
就说明发生了错误*／
           printk("Scheduling in interrupt\n");
              BUG();
        }
   release_kernel_lock(prev， this_cpu); /*释放全局内核锁，并开this_cpu的中断*／
       spin_lock_irq(&runqueue_lock); ／*锁住运行队列，并且同时关中断*/
        if (prev->policy == SCHED_RR) ／*将一个时间片用完的SCHED_RR实时
               goto move_rr_last;      进程放到队列的末尾 *／
move_rr_back:
        switch (prev->state) {     ／*根据prev的状态做相应的处理*／
               case TASK_INTERRUPTIBLE:  /*此状态表明该进程可以被信号中断*/
                        if (signal_pending(prev)) { /*如果该进程有未处理的信号，则让其变为可运行状态*/
                               prev->state = TASK_RUNNING;
                                break;
                        }
                 default:     ／*如果为不可中断的等待状态或僵死状态*／
                        del_from_runqueue(prev); ／*从运行队列中删除*／
                case TASK_RUNNING:;／*如果为可运行状态，继续处理*／
         }
         prev->need_resched = 0;

     ／*下面是调度程序的正文 *／
repeat_schedule:    ／*真正开始选择值得运行的进程*／
        next = idle_task(this_cpu); /*缺省选择空闲进程*/
   c = -1000;
     if (prev->state == TASK_RUNNING)
          goto still_running;
still_running_back:
    list_for_each(tmp， &runqueue_head) { ／*遍历运行队列*／
       p = list_entry(tmp， struct task_struct， run_list);
if (can_schedule(p， this_cpu)) { ／*单CPU中，该函数总返回1*／                          int weight = goodness(p， this_cpu， prev->active_mm);
               if (weight > c)
                   c = weight， next = p;
           }
     }         
               
／* 如果c为0，说明运行队列中所有进程的权值都为0，也就是分配给各个进程的
     时间片都已用完，需重新计算各个进程的时间片 *／  
    if  (!c) {
             struct task_struct *p;
             spin_unlock_irq(&runqueue_lock);／*锁住运行队列*／
              read_lock(&tasklist_lock);  ／* 锁住进程的双向链表*／
             for_each_task(p)            ／* 对系统中的每个进程*／
             p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
             read_unlock(&tasklist_lock);
                 spin_lock_irq(&runqueue_lock);
               goto repeat_schedule;
        }


     spin_unlock_irq(&runqueue_lock);／*对运行队列解锁，并开中断*／

       if (prev == next) {     /*如果选中的进程就是原来的进程*/
            prev->policy &= ~SCHED_YIELD;
               goto same_process;
      }

          ／* 下面开始进行进程切换*／
       kstat.context_swtch++; ／*统计上下文切换的次数*／
   
        {
               struct mm_struct *mm = next->mm;
               struct mm_struct *oldmm = prev->active_mm;
              if (!mm) {  ／*如果是内核线程，则借用prev的地址空间*／
                      if (next->active_mm) BUG();
                      next->active_mm = oldmm;
                 
              } else { ／*如果是一般进程，则切换到next的用户空间*／
                       if (next->active_mm != mm) BUG();
                       switch_mm(oldmm， mm， next， this_cpu);
              }

            if (!prev->mm) { ／*如果切换出去的是内核线程*／
                  prev->active_mm = NULL;／*归还它所借用的地址空间*／
                    mmdrop(oldmm);     ／*mm_struct中的共享计数减1*／
               }
        }
   
        switch_to(prev， next， prev); ／*进程的真正切换，即堆栈的切换*／
        __schedule_tail(prev);  ／*置prev->policy的SCHED_YIELD为0 *／

same_process:
       reacquire_kernel_lock(current);／*针对SMP*／
        if (current->need_resched)    ／*如果调度标志被置位*／
               goto need_resched_back; ／*重新开始调度*／
        return;
}

   以上就是调度程序的主要内容，为了对该程序形成一个清晰的思路，我们对其再给出进一步的解释：
如果当前进程既没有自己的地址空间，也没有向别的进程借用地址空间，那肯定出错。另外， 如果schedule()在中断服务程序内部执行，那也出错.
对当前进程做相关处理，为选择下一个进程做好准备。当前进程就是正在运行着的进程，可是，当进入schedule()时，其状态却不一定是TASK_RUNNIG，例如，在exit()系统调用中，当前进程的状态可能已被改为TASK_ZOMBE；又例如，在wait4()系统调用中，当前进程的状态可能被置为TASK_INTERRUPTIBLE。因此，如果当前进程处于这些状态中的一种，就要把它从运行队列中删除。
从运行队列中选择最值得运行的进程，也就是权值最大的进程。
如果已经选择的进程其权值为0，说明运行队列中所有进程的时间片都用完了（队列中肯定没有实时进程，因为其最小权值为1000），因此，重新计算所有进程的时间片，其中宏操作NICE_TO_TICKS就是把优先级nice转换为时钟滴答。
进程地址空间的切换。如果新进程有自己的用户空间，也就是说，如果next->mm与next->active_mm相同，那么，switch_mm( )函数就把该进程从内核空间切换到用户空间，也就是加载next的页目录。如果新进程无用户空间（next->mm为空），也就是说，如果它是一个内核线程，那它就要在内核空间运行，因此，需要借用前一个进程（prev）的地址空间，因为所有进程的内核空间都是共享的，因此，这种借用是有效的。
   用宏switch_to()进行真正的进程切换，后面将详细描述。

5.4 进程切换
5.4.1 硬件支持
   Intel i386 体系结构包括了一个特殊的段类型，叫任务状态段（TSS，Task state segment）。每个任务包含有它自己最小长度为104字节的TSS段，在/include/ i386/processor.h 中定义为tss_struct结构：
struct tss_struct {
        unsigned short  back_link，__blh;
        unsigned long   esp0;
        unsigned short  ss0，__ss0h;／*0级堆栈指针，即Linux中的内核级 *／
        unsigned long   esp1;      
        unsigned short  ss1，__ss1h; ／* 1级堆栈指针，未用*／
        unsigned long   esp2;
        unsigned short  ss2，__ss2h; ／* 2级堆栈指针，未用*／
        unsigned long   __cr3;   
        unsigned long   eip;
        unsigned long   eflags;
        unsigned long   eax，ecx，edx，ebx;
        unsigned long   esp;
        unsigned long   ebp;
        unsigned long   esi;
        unsigned long   edi;
        unsigned short  es， __esh;
        unsigned short  cs， __csh;
        unsigned short  ss， __ssh;
        unsigned short  ds， __dsh;
        unsigned short  fs， __fsh;
        unsigned short  gs， __gsh;
        unsigned short  ldt， __ldth;
        unsigned short  trace， bitmap;
        unsigned long   io_bitmap[IO_BITMAP_SIZE+1];
         /*
        * pads the TSS to be cacheline-aligned (size is 0x100)
         */
        unsigned long __cacheline_filler[5];
};
   每个TSS有它自己 8字节的任务段描述符（Task State Segment Descriptor ，简称TSSD）。这个描述符包括指向TSS起始地址的32位基地址域，20位界限域，界限域值不能小于十进制104（由TSS段的最小长度决定）。TSS描述符存放在GDT中，它是GDT中的一个表项。

后面将会看到，Linux在进程切换时，只用到TSS中少量的信息，因此Linux内核定义了另外一个数据结构，这就是thread_struct 结构：
struct thread_struct {
        unsigned long   esp0;
        unsigned long   eip;
        unsigned long   esp;
        unsigned long   fs;
        unsigned long   gs;
   /* Hardware debugging registers */
         unsigned long   debugreg[8];  /* %%db0-7 debug registers */
  /* fault info */
         unsigned long   cr2， trap_no， error_code;
   /* floating point info */
         union i387_union        i387;
  /* virtual 86 mode info */
        struct vm86_struct      * vm86_info;
         unsigned long           screen_bitmap;
        unsigned long           v86flags， v86mask， v86mode， saved_esp0;
/* IO permissions */
         int             ioperm;
        unsigned long   io_bitmap[IO_BITMAP_SIZE+1];
};

用这个数据结构来保存cr2寄存器、浮点寄存器、调试寄存器及指定给Intel 80x86处理器的其他各种各样的信息。

     那么，进程到底是怎样进行切换的？从第三章我们知道，在中断描述符表（IDT）中，除中断门、陷阱门和调用门外，还有一种“任务们”。任务门中包含有TSS段的选择符。当CPU因中断而穿过一个任务门时，就会将任务门中的段选择符自动装入TR寄存器，使TR指向新的TSS，并完成任务切换。CPU还可以通过JMP或CALL指令实现任务切换，当跳转或调用的目标段（代码段）实际上指向GDT表中的一个TSS描述符项时，就会引起一次任务切换。

内核只是在初始化阶段设置TR，使之指向一个TSS，从此以后再不改变TR的内容了。也就是说，每个CPU（如果有多个CPU）在初始化以后的全部运行过程中永远使用那个初始的TSS。同时，内核也不完全依靠TSS保存每个进程切换时的寄存器副本，而是将这些寄存器副本保存在各个进程自己的内核栈中（参见上一章task_struct结构的存放）。那么，当进行任务切换时，怎样自动更换堆栈？我们知道，新任务的内核栈指针（SS0和ESP0）应当取自当前任务的TSS，可是，Linux中并不是每个任务就有一个TSS，而是每个CPU只有一个TSS。在Linux内核中只更换TSS中的SS0和ESP0，而不更换TSS本身，也就是根本不更换TR的内容。因此，在Linux内核中，TSS并不是属于某个进程的资源，而是全局性的公共资源。在多处理机的情况下，尽管内核中确实有多个TSS，但是每个CPU仍旧只有一个TSS。

5.4.2进程切换
      前面所介绍的schedule()中调用了switch_to宏，这个宏实现了进程之间的真正切换，其代码存放于include/ i386/system.h：
1   #define switch_to(prev，next，last) do {                                  \
2         asm volatile("pushl %%esi\n\t"                                  \
3                      "pushl %%edi\n\t"                                  \
4                      "pushl %%ebp\n\t"                                  \
5                      "movl %%esp，%0\n\t"        /* save ESP */          \
6                      "movl %3，%%esp\n\t"        /* restore ESP */       \
7                      "movl $1f，%1\n\t"          /* save EIP */          \
8                      "pushl %4\n\t"             /* restore EIP */       \
9                      "jmp __switch_to\n"                                \
10                      "1:\t"                                             \
11                     "popl %%ebp\n\t"                                   \
12                     "popl %%edi\n\t"                                   \
13                     "popl %%esi\n\t"                                   \
14                      :"=m" (prev->thread.esp)，"=m" (prev->thread.eip)，  \
15                       "=b" (last)                                       \
16                      :"m" (next->thread.esp)，"m" (next->thread.eip)，    \
17                       "a" (prev)， "d" (next)，                           \
18                       "b" (prev));                                      \
19 } while (0)
switch_to宏是用嵌入式汇编写成，比较难理解，为描述方便起见，我们给代码编了行号，在此我们给出具体的解释：
thread的类型为前面介绍的thread_struct结构。
输出参数有三个，表示这段代码执行后有三项数据会有变化，它们与变量及寄存器的对应关系如下：
0％与prev->thread.esp对应，1％与prev->thread.eip对应，这两个参数都存放在内存，而2％与ebx寄存器对应，同时说明last参数存放在ebx寄存器中。
输入参数有五个，其对应关系如下：
3％与next->thread.esp对应，4％与next->thread.eip对应，这两个参数都存放在内存，而5％，6％和7％分别与eax，edx及ebx相对应，同时说明prev，next以及prev三个参数分别放在这三个寄存器中。表5.1列出了这几种对应关系：
表5.1
   参数类型
参数名
内存变量
寄存器
函数参数

输出参数
0％
prev->thread.esp
  
  

1％
prev->thread.eip
  
  

2％
  
Ebx
Last

输入参数
3％
next->thread.esp
  
  

4％
next->thread.eip
  
  

5％
  
Eax
Prev

6％
  
Edx
Next

7％
  
Ebx
Prev


第2～4行就是在当前进程prev的内核栈中保存esi，edi及ebp寄存器的内容。
第5行将prev的内核堆栈指针ebp存入prev->thread.esp中。
第6行把将要运行进程next的内核栈指针next->thread.esp置入esp寄存器中。从现在开始，内核对next的内核栈进行操作，因此，这条指令执行从prev到next真正的上下文切换，因为进程描述符的地址与其内核栈的地址紧紧地联系在一起（参见第四章），因此，改变内核栈就意味着改变当前进程。如果此处引用current的话，那就已经指向next的task_struct结构了。从这个意义上说，进程的切换在这一行指令执行完以后就已经完成。但是，构成一个进程的另一个要素是程序的执行，这方面的切换尚未完成。
第7行将标号“1”所在的地址，也就是第一条popl指令（第11行）所在的地址保存在prev->thread.eip中，这个地址就是prev下一次被调度运行而切入时的“返回”地址。
第8行将next->thread.eip压入next的内核栈。那么，next->thread.eip究竟指向那个地址？实际上，它就是 next上一次被调离时通过第7行保存的地址，也就是第11行popl指令的地址。因为，每个进程被调离时都要执行这里的第7行，这就决定了每个进程（除了新创建的进程）在受到调度而恢复执行时都从这里的第11行开始。
第9行通过jump指令（而不是 call指令）转入一个函数__switch_to()。这个函数的具体实现将在下面介绍。当CPU执行到__switch_to()函数的ret指令时，最后进入堆栈的next->thread.eip就变成了返回地址，这就是标号“1”的地址。
第11～13行恢复next上次被调离时推进堆栈的内容。从现在开始，next进程就成为当前进程而真正开始执行。

下面我们来讨论__switch_to()函数。

通过寄存器eax和edx把prev和next 参数传递给__switch_to（）函数。
void __switch_to(struct task_struct *prev_p， struct task_struct *next_p)
{
        struct thread_struct *prev = &prev_p->thread，
                                *next = &next_p->thread;
        struct tss_struct *tss = init_tss + smp_processor_id();


  /* 将TSS中的内核级（0级）堆栈指针换成next->esp0，这就是next 进程在内核栈的指针*/
      tss->esp0 = next->esp0;

       ／* 保存fs和gs，但无需保存es和ds，因为当处于内核时，内核段总是保持不变*／
     ／*恢复next进程的fs和gs *／
………….

／* 如果next挂起时使用了调试寄存器，则装载0～7个寄存器中的6个寄存器，其中第4、5个寄存器没有使用 *／               
／*把next进程的I/O操作权限位图拷贝到TSS中 *／
………..
}

Linux内核的设计者用软件实现了进程切换，而且，软件实现比硬件实现的效率更高，灵活性更大。

[/url]


本文来自ChinaUnix博客，如果查看原文请点：[url]http://blog.chinaunix.net/u2/78657/showart_2061859.html