Linux进程调度策略.doc

Linux进程调度策略的研究摘要：进程调度是多任务操作系统的核心，本文描述了Linux进程调度的过程。Linux系统中的每个进程用task_struct结构来描述，进程调度的依据是task_struct结构中的policy、priority、counter 和rt_priority。Linux根据policy将进程划分为实时和普通两类，普通进程采用动态优先调度，实时进程采用先来先服务（FIFO）调度和时间片轮转（RR）调度。关键词：Linux，进程，调度策略，优先级，时间片1. 前言进程调度的实质是资源的分配，如何使系统能够保持较短的响应时间和较高的吞吐量，如何在多个可运行的进程中选取一个最值得运行的进程投入运行是操作系统调度器的主要任务。一个好的调度算法应该考虑到公平、高效、响应时间、周转时间、吞吐量等诸多因素。进程调度是操作系统的核心，调度算法的优劣直接关系到系统的运行效率。本文以Linux操作系统为例，详细描述其进程调度策略，以希望对进程调度过程有更为感性的认识。2. Linux进程调度原理进程是动态的，一个进程的所有信息都被放在其对应的task_struct数据结构中。每当一个新的进程创建时，一个新的task_struct结构将分配给该进程，并同时增加到进程向量的数组中。系统还有一个当前进程指针，用来指向当前正在运行的进程。task_struct实际上就是通常所说的“进程控制块”PCB，它是系统对进程控制的惟一且最有效的手段。2.1 进程调度的依据调度程序运行时，要在所有可运行状态的进程中选择最值得运行的进程投入运行。在每个进程的task_struct结构中有：policy、priority、counter、rt_priority，这4 项就是选择进程的依据。其中policy是进程的调度策略，用于区分实时进程和普通进程，实时进程优先于普通进程运行；priority是进程(包括实时和普通)的静态优先级；counter是进程剩余的时间片，它的起始值就是priority的值；由于counter在后面计算一个处于可运行状态的进程值得运行的程度goodness时起重要作用，因此，counter也可以看作是进程的动态优先级。rt_priority 是实时进程特有的，是实时进程之间的相对优先级，用于实时进程间的选择。Linux用函数goodness()来衡量一个处于可运行状态的进程值得运行的程度。该函数综合了以上提到的4项，还结合了一些其他的因素，给每个处于可运行状态的进程赋予一个权值(weight)，调度程序以这个权值作为选择进程的惟一依据。2.2 进程调度的时机Linux的调度时机分两种情况：主动调度:主动调度是指显式调用schedule()函数明确释放CPU，引起新一轮进程调度。一般发生在当前进程状态改变，例如：进程终止、进程睡眠等；进程对某些信号处理过程中断等等。被动调度:被动调度是指不显式调用schedule()函数,只是将进程PCB中调度标志need_resched 置1，而每当中断处理和系统调用返回时，核心都会主动查询need _resched的状态：如果置1，则主动调用schedule()函数。一般发生在新的进程产生时、某个进程优先级改变时、某个进程等待的资源可用被唤醒时、当前进程时间片用完等。3. Linux进程调度策略首先，Linux根据policy从整体上区分实时进程和普通进程（非实时进程），因为实时进程和普通进程度调度是不同的，实时进程应该先于普通进程而运行。然后，对于同一类型的不同进程，采用不同的标准来选择进程：对于普通进程，Linux采用动态优先调度（多级反馈轮转调度算法）的策略，选择进程的依据就是进程counter的大小。对于实时进程，Linux 采用了两种调度策略，即FIFO(先来先服务调度)和RR（时间片轮转调度）。3.1 Linux进程模型Linux中的每个进程由task_struct结构来描述。在Linux中任务和进程是相同的术语，task_struct其实就是指PCB（进程控制块）。进程PCB中涉及进程调度的域如下：Struct tast_struct Volatile long need_resched;Long counter;Long nice;Unsigned long policy;Unsigned long rt_priority;其中，need_resched域是进程调度标志，该域置位将引起新的进程调度。counter域是当前进程剩余的时间片值，随着进程的执行，时间片逐渐减小，时间片用完引起进程调度。它是进程的动态优先级，保证当前进程不会一直占有CPU，给其他进程被调度的机会。如果进程尚未终止，核心继续向该进程分配时间片，但是是否立即重新分配时间片，即向counter域赋值，则根据policy域值不同而不同。时间片初值根据时钟频率HZ的不同而采用不同的计算形式。当HZ=100时，时间片初值等于( (20 (nice)/4 + 1 )。由此可以看出nice和HZ共同决定了时间片的初值，因此nice域被称为调度量子，它的取值范围是-2019。改变nice域值，进程的动态优先级随之改变：当取负值时进程优先级增加；取正值则降低优先级。Linux进程有以下五种状态：TASK_RUNNING：无论进程是否正在占用CPU，只要具备运行条件， 都处于该状态，即正在运行处于运行状态和将要运行处于就绪状态的进程都归于此列。Linux把处于该状态的所有PCB组织成一个可运行队列run_queue，调度程序从这个队列中选择进程运行。事实上，Linux是将就绪状态和运行状态合并成了一种状态。TASK_INTERRUPTIBLE：Linux将阻塞状态划分成TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE、TASK_STOPPED三种不同的状态。处于TASK_INTERRUPTIBLE状态的进程在资源有效时被唤醒，也可以通过信号或定时中断唤醒。TASK_UNINTERRUPTIBLE：另一种阻塞状态，处于该状态的进程只有当资源有效时被唤醒，不能通过信号或定时中断唤醒。TASK_STOPPED：第三种阻塞状态，处于该状态的进程只能通过其他进程的信号才能唤醒。TASK_ZOBIE：进程已结束但尚未消亡，已经释放了大部分资源，PCB仍未被释放，是进程终止前的一个过渡状态。3.2 普通进程的调度策略动态优先调度当policy的值为SCHED_OTHER时，即普通的用户进程，采用动态优先调度，选择进程的依据是进程counter的大小。进程创建时，优先级priority被赋一个初值，一般为070之间的数字，这个数字同时也是计数器counter的初值，进程创建时两者是相等的。priority 代表分配给该进程的时间片，counter表示该进程剩余的时间片。在进程运行过程中，counter 不断减少，而priority 保持不变，以便在counter变为0的时候（该进程用完了所分配的时间片）对counter重新赋值。当一个普通进程的时间片用完以后，并不马上用priority对counter 进行赋值，只有所有处于可运行状态的普通进程的时间片(p-counter=0)都用完了以后，才用priority对counter重新赋值，这个普通进程才有了再次被调度的机会。在普通进程运行过程中，counter的减小给了其他进程得以运行的机会，即进程正在运行时可以被其他counter值更大的进程中断，但只有当该进程的counter值减为0 时才完全放弃对CPU的使用，这就相当于优先级在动态变化，所以称之为动态优先调度。Linux 中某个进程的调度策略(policy)、优先级(priority)等可以作为参数由用户自己决定，具有相当的灵活性。内核创建新进程时分配给进程的时间片缺省为200ms（更准确的，应为210ms），用户可以通过系统调用改变它。3.3 实时进程的调度策略FIFO和RR当Policy域取SCHED_FIFO或者SCHED_RR时，即实时进程，priority权值为(1000 + rt_priority)远远大于非实时进程，以确保实时进程先于非实时进程运行。实时进程的权值与时间片无关。rt_priority域是实时进程之间相对的优先级，实际应用中，根据实时进程的轻重缓急设置rt_priority域值，保证实时性要求高的进程比实时性要求低的进程更快获得CPU，体现Linux的实时性。3.3.1 先来先服务调度（FIFO）该策略是遵守POSIX 1.b标准的FIFO（先入先出）调度规则。它会一直运行，直到有一个进程因I/O阻塞，或者主动释放CPU，或者是CPU被另一个具有更高rt_priority的实时进程抢先。3.3.2 时间片轮转调度（RR）该策略是遵守POSIX 1.b标准的RR（循环round-robin）调度规则。除了时间片有些不同外，这种策略与SCHED_FIFO类似。SCHED_RR进程最先被调度并且拥有时间片，当SCHED_RR进程的时间片用完后，就被放到SCHED_RR队列和SCHED_FIFO队列的末尾，并且允许同一优先级的其他进程运行；如果同一优先级没有其他进程，该进程将继续运行下一个时间片。只要系统中有一个实时进程在运行，则任何普通进程都不能在任何CPU上运行。每个实时进程有一个rt_priority，因此，可以按照rt_priority在所有SCHED_RR进程之间分配CPU。其作用与普通进程的priority作用一样。只有root用户能够用系统调用sched_setscheduler来改变当前进程的类型(sys_nice,sys_setpriority)。此外，内核还定义了SCHED_YIELD，这并不是一种调度策略，而是截取调度策略的一个附加位。如果有其他进程需要CPU，它就提示调度程序释放CPU。4. 结论进程调度是多任务操作系统的核心。Linux根据policy将进程划分为实时和普通两类，普通进程采用动态优先调度，实时进程采用基于FIFO