搜索
研究Unix、Lunix和Windows等3种操作系统的进程调度策略摘要：本文对Unix、Lunix和Windows三种操作系统的进程调度策略进行了详细的分析。Lunix系统对普通进程的调度策略－动态优先调度，对于实时进程采用了两种调度策略，FIFO(先来先服务调度)和RR（时间片轮转调度）；UNIX系统的进程调度采用的算法是，多级反馈列轮转调度法；而Windows系统其调度方式比较复杂，它的处理器调度的调度单位是线程而不是进程，是基于优先级的抢先式多处理器调度，依据优先级和分配时间片来调度。最后对它们的进程调度方式进行了对比研究，分析出了各种调度算法的优缺点、以及在哪些情况下用什么样的调度方式最合适。关键词：操作系统进程调度算法实时优先级引言：无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。进程调的实质是资源的分配，如何使系统能够保持较短的响应时间和较高的吞吐量，如何在多个可运行的进程中选取一个最值得运行的进程投入运行是调度器的主要任务。进程调度包括两个方面的内容：何时分配CPU时间（调度时机）即调度器什么时候启动；如何选择进程（调度算法）即调度器该怎么做。进程调度有以下两种基本方式：非剥夺方式:分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。剥夺方式:当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程、优先原则、时间片原则。Linux进程调度策略调度程序要在所有处于可运行状态的进程中选择最值得运行的进程投入运行。在每个进程的task_struct结构中有：policy、priority、counter、rt_priority，这4项就是选择进程的依据。policy是进程的调度策略，用来区分两种进程-实时和普通；priority是进程(实时和普通)的优先级；counter是进程剩余的时间片，它的大小完全由priority决定；rt_priority是实时优先级，这是实时进程所特有的，用于实时进程间的选择。.首先，Linux根据policy从整体上区分实时进程和普通进程，因为实时进程和普通进程度调度是不同的，它们两者之间，实时进程应该先于普通进程而运行，然后，对于同一类型的不同进程，采用不同的标准来选择进程：1.普通进程的调度策略－动态优先调度。当policy的值为SCHED_OTHER时，是普通的用户进程，采用动态优先调度，选择进程的依据是进程counter的大小。进程创建时，优先级priority被赋一个初值，一般为0～70之间的数字，这个数字同时也是计数器counter的初值，进程创建时两者是相等的。priority代表分配给该进程的时间片，counter表示该进程剩余的时间片。在进程运行过程中，counter不断减少，而priority保持不变，以便在counter变为0的时候（该进程用完了所分配的时间片）对counter重新赋值。当一个普通进程的时间片用完以后，并不马上用priority对counter进行赋值，只有所有处于可运行状态的普通进程的时间(p-counter==0)都用完了以后，才用priority对counter重新赋值，这个普通进程才有了再次被调度的机会。在普通进程运行过程中，counter的减小给了其他进程得以运行的机会，即进程正在运行时可以被其他counter值更大的进程中断，但只有当该进程的counter值减为0时才完全放弃对CPU的使用，这就相当于优先级在动态变化，所以称之为动态优先调度。2．对于实时进程，Linux采用了两种调度策略，即FIFO(先来先服务调度)和RR（时间片轮转调度）。图1时间片轮转调度示意图因为实时进程具有一定程度的紧迫性，所以衡量一个实时进程是否应该运行，Linux采用了一个比较固定的标准。实时进程的counter只是用来表示该进程的剩余时间片，并不作为衡量它是否值得运行的标准。实时进程的counter只是用来表示该进程的剩余时间片，并不作为衡量它是否值得运行的标准，这和普通进程是有区别的。上面已经看到，每个进程有两个优先级，实时优先级就是用来衡量实时进程是否值得运行的。Unix进程调度策略UNIX系统是单纯的分时系统，所以没有设置作业调度。UNIX系统的进程调度采用的算法是，多级反馈列轮转调度法。其核心思想是先从最高休先级就绪队列中取出排在队列最前面的进程，当进程执行完一个时间片仍未完成则剥夺它的执行，将它放入到相应的队列中取出下一个就绪进程投入运行（如图2所示）。多级反馈队列调度算法即能使高优先级的作业得到响应又能使短作业(进程)迅速完成。多级反馈队列调度算法描述：1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。3、对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。图2该算法的具体运作方式：假设系统中有3个反馈队列Q1,Q2,Q3，时间片分别为2，4，8。现在有3个作业J1,J2,J3分别在时间0，1，3时刻到达。而它们所需要的CPU时间分别是3，2，1个时间片。（1）时刻0J1到达。于是进入到队列1，运行1个时间片，时间片还未到，此时J2到达。（2）时刻1J2到达。由于时间片仍然由J1掌控，于是等待。J1在运行了1个时间片后，已经完成了在Q1中的2个时间片的限制，于是J1置于Q2等待被调度。现在处理机分配给J2。（3）时刻2J1进入Q2等待调度，J2获得CPU开始运行。(4)时刻3J3到达，由于J2的时间片未到，故J3在Q1等待调度，J1也在Q2等待调度。(5)时刻4J2处理完成，由于J3，J1都在等待调度，但是J3所在的队列比J1所在的队列的优先级要高,于是J3被调度，J1继续在Q2等待。(6)时刻5J3经过1个时间片完成。(7)时刻6由于Q1已经空闲，于是开始调度Q2中的作业，则J1得到处理器开始运行。(8)时刻7J1再经过一个时间片，完成了任务。于是整个调度过程结束。从上面的例子看，在多级反馈队列中，后进的作业不一定慢完成。Windows进程调度策略Windows的进程调度比较复杂，以Windows2000/XP为例。Windows2000/XP的处理器调度的调度单位是线程而不是进程，是基于优先级的抢先式多处理器调度，依据优先级和分配时间片来调度；而且Windows2000/XP在单处理器系统和多处理器系统中的线程调度是不同的线程调度机制。Windows操作系统的调度系统总是运行优先级最高的就绪线程。在同一优先级的各线程按时间片轮转算法（如图1）进行调度。如果一个高优先级的线程进入就绪状态，当前运行的线程可能在用完它的时间片之前就被抢先。可触发线程调度的事件：一个线程进入就绪状态；一个线程的时间片结束；线程由于调用系统服务而改变优先级或被系统本身改变其优先级；正在运行的线程被改变了所运行的处理器（在多处理器系统中）。Windows2000/XP内部使用32个线程优先级，范围从0到31，数值越大，优先级越高。实时线程优先级：16～31；可变线程优先级：1～15；级别0保留为系统使用，仅用于对系统中空闲物理页面进行清零的零页线程。当一个线程被调度进入运行状态时，它运行一个称为时间配额的时间片，时间配额是Windows2000/XP允许一个线程连续运行的最大时间长度。Windows在单处理器系统中的线程调度Windows2000/XP基于线程实现优先级驱动的抢先式多任务的方式如下：1．主动切换一个线程可能因为进入等待某个对象而主动放弃处理器的使用。当该线程等待的事件出现时，它会排到相应优先级的就绪队列尾。通常进入等待状态线程的时间配额不会被重置，而是在等待事件出现时，线程的时间配额被减1，相当于1/3个时钟间隔；如果线程的优先级大于等于14，在等待事件出现时，线程的优先级被重置。2．抢先当一个高级优先级线程进入就绪状态时，正在处于运行状态的低优先级线程被抢先。可能在两种情况下出现：（1）高优先级线程的等待完成，即一个线程等待的事件出现。（2）一个线程的优先级被增加或减少。调度器只是根据线程优先级判断一个线程是否被抢先，而不管线程是处于用户态还是内核态。当线程被抢先时，它被放回相应优先级的就绪队列的队首。（1）处于实时优先级的线程在被抢先时，时间配额被重置为一个完整的时间片；（2）处于动态优先级的线程在被抢先时，时间配额不变，重新得到处理机使用权后将运行到剩余的时间配额用完。3.时间配额用完处于运行状态的线程用完它的时间配额时，Windows2000/XP会中断该线程的运行，判断是否需要降低该线程的优先级，并查找是否有其他高优先级或相同优先级的线程等待运行。——如果该线程的优先级降低了，Windows2000/XP会寻找一个优先级高于该线程的新设置值的就绪线程来调度；——如果该线程的优先级没有降低，并且有其他优先级相同的就绪线程，Windows2000/XP将选择相同优先级的就绪队列中的下一个线程进入运行状态，刚用完时间配额的线程被排到就绪队列的队尾。——如果没有优先级相同的就绪线程可运行，刚用完时间配额的线程将得到一个新的时间配额并继续运行。3.结束当线程完成运行时，它的状态从运行状态转到终止状态。Windows在对称多处理器系统上的线程调度亲合关系Affinity（1）描述该线程可在哪些处理器上运行（2）线程的亲合掩码是从进程的亲合掩码继承得到（3）SetProcessAffinityMask或SetThreadAffinityMask函数可以指定亲合掩码线程的首选处理器和第二处理器（1）首选处理器：线程运行时的偏好处理器，是基于进程控制块的索引值在进程创建时随机选择的。SetThreadIdealProcessor函数可以设置线程的首选处理器。（2）第二处理器：线程第二个选择的运行处理器。就绪线程的处理器选择当线程进入运行状态时，首先试图调度该线程到一个空闲处理器上运行。如果有多个空闲处理器，则调度顺序为线程的首选处理器、线程的第二处理器、当前执行处理器，如果它们都不是空闲的，则依据处理器标识从高到低扫描系统中的空闲处理器状态，选择找到的第一个空闲处理器。如果线程进入就绪状态时，所有处理器都处于繁忙状态，则将检查一个处于运行状态或备用状态的线程，判断它是否可抢先。检查的顺序为线程的首选处理器、线程的第二处理器，如果它们都不在线程的亲合掩码中，则将依据活动处理器掩码选择该线程可运行的编号最大的处理器。特定的处理器调度线程在多处理器系统，Windows2000/XP不能简单地从就绪队列中取第一个线程，它要在亲合掩码限制下寻找一个满足下列条件之一的线程。（1）线程的上一次运行是在该处理器上；（2）线程的首选处理器是该处理器；（3）处于就绪状态的时间超过2个时间配额；（4）优先级大于等于24；如果能找不到满足要求的线程，它将从就绪队列的队首取第一个线程进入运行状态。最高优先级就绪线程可能不处于运行状态空闲线程一个处理器上没有可运行的线程时，Windows2000/XP会调度相应处理器上对应的空闲线程。在多处理器系统中，每个处理器都有一个对应的空闲线程。对比总结：上文分别对Unix、Lunix和Windows三种操作系统的进程调度策略进行了