Linux的进程调度
班级：09计本3班 学号：0904013012 姓名:吴宏
Linux 的进程调度是基于分时技术（time-sharing ）。允许多个进程“并发”运行就意味着CPU的时间被粗略地分成“片”，给每个可运行进程分配一片。 当然，单处理器在任何给定的时刻只能运行一个进程。当一个并发执行的进程其时间片或时限（quantum ）到期时还没有终止，进程切换就可以发生。分时依赖于定时中断，因此，对进程是透明的。为保证CPU分时，不需要在程序中插入额外的代码。
操作系统技术是最核心的软件技术，它是其它应用软件得以运行的平台，应用软件的开发必须基于对相应平台(操作系统)的技术的理解和掌握。在我国，由于受知识产权的限制，无法窥视到Windows或Unix等的内部结构，迫切需要开发具有自主知识产权的操作系统，特别是应用于特定领域的专用操作系统。由于Linux性能优越，公开源代码且完全免费，所以拿来做底版是非常合适的选择。但是首先我们需要完全了解Linux的实现细节。
在Linux内核5大模块中，进程管理处于最核心的地位，而进程调度又是其中的关键部分。本文通过对Linux内核进程调度相关的若干关键技术进行研究，归纳总结出了Linux进程调度的思想和机制，对我们开发特定需求的操作系统具有积极的指导作用。
一、 Linux进程及其状态
Linux的进程与其它操作系统中的进程相同，都是指在一个独立的虚拟地址空间里运行的程序及其上下文。但在进程的状态划分方面，Linux有其独特之处，而这些独特之处又极大地影响着Linux的各种特性和性能，包括本文所关注的进程调度问题。Linux将进程状态定义为5种： 1、运行态
进程正在使用CPU运行的状态，称为运行态。处于运行态的进程又称为当前进程。 2、可运行态
进程已分配到除CPU外所需要的其它资源，等待系统把CPU分配给它之后即可投入运行。 3、等待态
又称睡眠态，它是进程正在等待某个事件或某个资源时所处的状态。等待态进一步分为可中断的等待态和不可中断的等待态。处于可中断等待态的进程可以由信号解除其等待态。处于不可中断等待态的进程，一般是直接或间接等待硬件条件，它只能用特定的方式来解除，例如使用唤醒函数wake_up()等。 4、暂停态
进程需要接受某种特殊处理而暂时停止运行所处的状态。通常进程在接收到外部进程的某个信号进入暂停态，例如，正在接受调试的进程就处于这种状态。 5、僵死态
进程的运行已经结束，但它所占的资源还未释放，父进程也还没有询问其状态，该进程处于僵死态。
这5种状态之间可相互转换，理解进程状态及其转换对于把握调度时机非常关键。
Linux的进程在处理机上运行时，处理机提供了两种不同的的执行状态：内核态和用户态。内核态又称系统态，它具有较高的特权，能执行特权指令，能访问所有的寄存器和存储区域，能直接控制所有的系统资源。系统调用、中断处理就是处于内核态下。用户态是进程的普通执行状态，它具有较低的特权，不能执行特权指令，只能访问进程的存储空间，不能与系统硬件相互作用，不能访问系统资源。由内核态向用户态的转换关系着调度时机问题。 二、Linux的进程调度 1、调度方式
Linux系统采用抢占调度方式，又称可剥夺调度方式。采用这种调度方式时，对于当前运行的进程而言，当有更紧急的进程到来时，系统将剥夺当前进程使用处理机的权利，立即停止它在处理机上的运行，而把处理机分配给那个更紧急的进程。
2、 调度策略
Linux的进程分为普通进程和实时进程，两者采用不同的调度策略,在基于优先级的算法下，实时进程优先于普通进程。Linux进程的调度策略有三种：
符号常量 SCHED_OTHER SCHED_FIFO SCHED_RR
表1 Linux的进程调度策略
一个进程的调度策略用对应的任务结构体中的policy域来表示。首先，调度程序根据policy区分实时进程和普通进程，如果有一个实时进程准备运行，那么它总是先被运行。在时间片轮转的调度策略下，每一个实时进程依次运行；而在先进先出的策略下，每一个可以运行的实时进程按照它在调度队列中的顺序运行，这个顺序不会改变。对于普通进程，调度程序永远选择优先级最高的进程来运行。
总而言之，Linux的进程调度策略是一种基于优先级的调度策略，并融合了时间片轮转调度策略。 3、 调度依据和方法
如上所述，对于普通进程，调度程序将选择优先级最高的进程来运行，那么，调度程序依据什么来确定进程的优先级呢？正如2.2所说，进程调度的依据就是任务结构体中的4个域。调度程序将会综合这4个因素，并结合一些其他的因素，给每个处于可运行状态的进程赋予一个权值，以这个权值作为优先级，来选择进程。具体地说，调度程序将会调用一个叫做goodness()的函数来计算一个处于可运行状态的进程的权值，函数的主体如下：
inline int goodness(struct task_struct *p, struct task_struct *prev, int this_cpu) {
int weight;
if (p->policy != SCHED_OTHER) return 1000 + p->rt_priority;
意义 普通进程的时间片轮转算法 实时进程的先进先出算法 实时进程的时间片轮转算法 weight = p->counter; if(weight > 0)
return weight;
/*以下是针对对称多处理器的调度*/
…… }
由于goodness函数调用频率相当高，因此被申明成inline，这样可以提高函数调用的效率。第一个参数就是待计算权值的进程。函数体中，首先检查进程的调度策略，如果是实时进程，则仅仅参考其rt_priority域，而不理会其它域；否则对于普通进程，以counter域做为权值并将其返回。
关于时间片这个概念，和其它操作系统一样，就是指“时钟滴答”，只是不同操作系统对一个时钟滴答的定义不同而已（Linux将其定义为10ms）。在进程运行过程中，每过一个时钟滴答，时钟中断处理程序就将当前进程的counter域的值减1，这样，到某一个时刻，可运行态进程中就会有优先级大于当前进程的进程，当发生进程调度时，调度程序就会用它取代当前进程。所以，Linux采用的是一种动态优先级抢占式调度。当所有处于可运行态的普通进程的时间片都用完了以后，将用priority对counter重新赋值，这些普通进程就有了再次被调度的机会。
4、 调度时机
首先要明确两种不同情况：一种情况是需要重新调度，但是可能并不马上执行调度程序，而仅仅是将当前进程的need_reched域置位，待将来某个时刻才真正执行调度程序；另一种情况是立即直接执行调度程序来完成调度。调度的时机有下面5种：
1、增加一个新进程
此时，内核需要比较增加的进程与当前进程的counter值，如果前者比后者高，则将当前进程的need_reched域置位。 2、进程状态转换时
当正在运行的进程调用sleep()系统调用进入等待态，或exit()系统调用退出执行时，这些系统调用会立即直接执行调度程序来完成调度。 3、系统调用执行完毕返回用户态时
在这种情况下，系统调用返回时，将执行ret_with_reschedule程序段。该程序段将判断当前进程的need_reched域，如果置位，则执行调度程序。 4、中断处理完毕返回到用户态时
这种情况与上一种情况做相似处理。 5、当前进程的时间片使用完毕
当前进程的counter域已被减为0了，这种情况与第2种情况做相似处理。 三、进程调度方法分析
Linux 系统中，为了高效地调度进程，将进程分威两类：实时进程和普通进程( 又称非实时进程或一般进程) ，实时进程的优先级要高于其他进程，如果一个实时进程处于可执行状态，它将先得到执行．实时进程又有两种策略：时间片轮转和先进先出，在时间片轮转策略中。每个可执行实时进程轮流执行一个时间片，而先进先出策略每个进程按各自在运行队列中的顺序执行且顺序不能变化。在Linux 中，进程调度策略共定义了3 种：
Linux 系统中的每个进程用task ，struct 结构来描述，进程调度的依据是
task —struct 结构中的policy 、priority 、counter 和rt —priority ，PCB 中设置Policy 数据项，其值用于反映针对不同类型的进程而采用的调度策略。SCHED —RR 和SCHED —FIFO 用于实时进程。分别表示轮转调度策略和先进先出调度策略；SCHED —OTHER 表示普通进程，也按照轮转调度策略处理。这三类调度策略均基于优先级．PCB 中设置Priority 数据项，其值为普通进程的调度优先级．普通进程的可用时间片的初始值即为该值，该值通过系统调用是可以改变的。PCB 中设置rt ～p riority 数据项，其值是实时进程专用的调度优先级，实时进程的可用时间片的初始值即为该值．该优先级也可以用系统调用来修改，PCB 中设置counter 数据项。用于进程可用时间片时值的计数，初始值为rt —priority 或Priority 。进程启动后该值随时钟周期递减。
结论
在专用Linux中，通用Linux的进程调度机制仍然是以进程调度为核心的。开发这种专用Linux时，我们可以在原有基础上加以改造，例如当我们需要实时性很强的操作系统时，可以对进程调度的依据和时机等进行修改。但是应该始终遵循上述的内核原则，这样开发出来的操作系统才能继承原有Linux高效、稳定、易于扩展的特性。
简单、巧妙和高效是贯穿整个Linux内核的原则，从对进程调度部分机制的分析我们可以见其一斑。Linux的进程调度部分采用了简单的动态优先级调度策略，而衡量优先级的标准也只是简单的剩余时间片。另外，由于Linux内核对中断的响应和处理采用了“前半截”和“后半截”的机制，在调度程序中关键段部分采用了内联函数和汇编语言宏，在调度时机的安排上精心设计，所有这些因素，都使得Linux的进程调度部分在理论上易于理解，在运行中稳定高效。而这一切的原因，又归功于Linux中直观、巧妙的进程状态和执行状态的定义。可见，正是在进程调度这个操作系统最核心的部分中，从一开始的概念定义到最终的机制实现，都做到了简单、巧妙，浑然一体，相互配合，才使得Linux能够超越其它操作系统。 参考文献：
[1] 陈利君，linux操作系统内核分析，人民邮电出版社，2000
[2] 李善平等，Linux内核2.4版源代码分析大全，机械工业出版社，2002 [3] Richard Petersen，linux: The Complete Reference，McGraw-Hill，1999 [4] 赵炯，Linux内核完全注释，机械工业出版社，2004
相关推荐：
loading