进程调度量化分析中的概率模型应用摘要：进程调度算法是计算机操作系统核心算法之一。通过简化进程的状态转换关系及概率论的相关理论，在给定了6个假设条件和2个近似分布的条件下本文建立了进程调度的概率模型，在该模型的指导下，深入分析进程调度的定量化指标。关键词：概率模型，进程调度，泊松分布1.前言进程调度算法的功能是按一定的调度策略选择处于就绪队列中的进程在处理机上运行。处理机利用率和系统吞吐量都与进程调度算法的好坏直接相关, 其算法设计直接影响操作系统的整体性能。通过几个定量指标来评价进程调度性能的重要性也就不言而喻了。进程调度算法的评价是一个较复杂的系统工程期。一般有两类方法。一类是基于具体调度算法的性能分析。常见的进程调度算法有FIFO、SCBF、HPF、RR、HRN和MFQ。这些调度算法各有其优缺点, 一般只从系统吞吐量的高低、周转时间长短等方面做定性的分析。另一类是基于样本统计的性能评价方法。这种方法是通过一定数量的样本来定性分析这些调度算法的性能。由于具有代表性样本的设计难度和样本数量的限制, 其性能评价具有一定的片面性。本文将建立一个进程调度的简化概率模型, 在此基础上给出六个定量评价指标。综合分析进程调度算法的综合性能。2. 进程调度的概率模型21 进程状态分析在多道程序系统中, 处理机的分配和调用都是以进程为单位。进程从创建而产生, 由调度而执行，由撤销而死亡。在这个过程中, 进程表现出了不同的状态。进程创建是进程管理的第一步, 是给进程分配除CPU之外的资源的过程。这个阶段称为进程处于建立状态。进程创建完毕后, 新进程将被插入就绪队列等待处理机的调用。此时,称该进程处于就绪状态。 一个就绪进程获得CPU,称该进程正处于执行态。进程从就绪态到执行态的过程就是分派程序执行调度算法的结果,进程在执行过程中。也有可能由于某事件而暂时无法继续执行,不得不放弃CPU。此时,称进程处于阻塞态。进程进入执行态除了可能来自就绪态外，也可能来自于阻塞态。进程执行完毕后, 还得作必要的善后处理工作，称这种状态为终止状态。图l表明了这些状态之间的转换关系。就绪创建 许可 I/O完成 调度 时间片用完阻塞终止执行 I/O请求 释放图1 进程五种状态转换22 模型建立的假设条件影响进程调度的因素比较多，为了使得评价模型简单实用。我们忽略了一些次要因素。下面是模型建立的假设条件。(1)本模型仅实用于多道批处理系统,不适合分时系统与实时系统.(2)所有进程的执行都是一次性的，要么不执行(等待),要么一次执行完成。(3)所有进程的执行过程中都不会出现死锁现象。(4)所有进程遵循有闲让进，忙则等待的原则。(5)新进程进入就绪队列的过程不会停止。(6)系统是单核的，在某一时刻仅有一个进程在执行。 根据上述假设,可以将图2简化为： 进程终止 CPU服务 就绪队列 进程图2 进程调度的简化模型图其中：排队规则体现了就绪进程按什么方式和顺序接受CPU服务。一般有：先来先服务、优先权服务、短作业优先和随机服务等。23 进程调度的概率模型基于以上假设和大量的统计数据表明：一段时问间隔内，进入就绪队列的进程数近似符合参数为入的Poisson分布。如果我们同时假设每个进程的CPU服务时问也近似符合负指数分布,则根据排队论的相关知识不难得出：单CPU简化进程调度的概率模型就是MMl排队模型【1】。具体而言,(1)在时问问隔段t内，进入就绪状态的进程数符合参数为k的Poisson分布。即 其中：N(s)表示在时刻s处于就绪状态的进程数，表示到达率。（2)每个进程的CPU服务时间相互独立,具有相同的负指数分布：24 MMl排队模型任何一个排队过程都包括以下三个过程：到达过程；排队过程；服务过程。如果一个排队系统仅有一个服务系统，到达顾客数服从泊松分布，服务时间服从负指数分布和FIFO排队过程，则该排队系统被称为MMl系统。241 建模 FCFS调度算法是最简单的进程调度算法。算法描述：当一个进程处于就绪状态，就进入就绪队列。当前进程停止运行时，就从就绪队列中选等待时间最长的进程运行。将FCFS调度算法的处理过程模拟如图3所示的服务摸型，该模型由一个队列和单CPU组成。假设进程到达就绪队列的过程是速率为的泊松流，CPU的服务时闻服从负指数分布，服务速率为。操作系统中处予就绪状态的进程数目是有限的并且棚对比较小，CPU的服务速率较大。因此FCFS服务模型可以认为是一个MMl随机服务模型【2】。CPU Arriving Departing ProcessesProcesses图3 FCFS服务模型242 FCFS算法平均响应时间分析对于交互式系统或者实时系统，响应时间是用户所关心的。特别是当系统中有大量进程共存时，仍要保证每个用户都有可以接受响应的速度而并不感到明显的延迟。根据测定，当这种延迟超过150ms时，使用者就会明显地感觉到【3】。响应时间是评价算法的一个重要标准，所以响应时间越小越好。根据公式，如果越大，越小，T越小。这与直觉一样，如果不变，进程平均服务时间l越短，则就绪队列中进程的等待时间就越短，平均响应时间就越短。如果=，则T将趋于无穷大，此时系统性能是最差的。25 基于概率模型的进程调度评估基于MM1排队模型，我们可以得到进程调度算法的定量指标【4】。见表1：指标定义数值说明平均到达率单位时间内到达就绪排队列的进程数平均服务率单位时间内CPU执行的进程数进程到达就绪队列的时间均值每个CPU的平均执行时间CPU的利用率当, CPU处于不断忙碌中就绪队列长度均值与CPU利用率相关进程在就绪队列中的等待时间均值该指标也可以理解为进程在就绪队列中的平均响应时间，w进程逗留时间均值不考虑在外存后被队列的等待时间表1 定量指标表从上表不难看出进程调度性能仅仅与平均到达率和平均服务有关。而由于平均到达率是不可控的，提高性能就转移到提高平均服务率上面。平均服务率是单位时间内CPU执行的进程数与CPU的性能和每个进程需要CPU服务时间的长短有关。假定CPU性能一定如果执行的进程需要CPU服务的时间越少那么平均服务率就越大。从而进程逗留时间均值和进程在就绪队列中的等待时间均值越少。基于排队规则而产生的不同算法如先来先服务、优先权服务、短作业优先和随机服务等必然导致单位时间内CPU执行的进程数的不同。显然一段时间间隔内短作业优先算法的CPU平均服务率最高。先来先服务算法优先考虑的是等待时间最短的进程，而优先权服务则优先考虑的是优先权大的进程，随机服务算法是随机选择进程。这三种算法的不同主要体现在优先考虑对象的不同，对单个进程有较强的意义【4】。3讨论为了使得进程调度的概率模型简单和易于建立我们给出了6个假设条件和两个近似分布。其中第6个假设条件可以去掉那么我们所对应系统就是多处理机系统。建立的模型就是MM1排队模型。两个近似分布即Poisson分布和负指数分布也仅仅是我们的参考结果。迄今为止，还没有发现严格的证明。因此本文所阐述的模型也仅仅是一个理论上粗糙的近似。相关参数的确定需要进一步细致的研究。 参考文献【l】 任泰明如何用数学模型定量评价进程调度算法的性能。兰州石化职业技术学院学报，2001，l(1)；79【2】 Dimltri Bertsekas,Robert GallagerData Networks2nd EditionPrentice HalL 1991150269【3】 跨德操，胡希明Linux内核源代码情景分析(第一版)浙波：浙江大学出版社，2001。356【4】 徐光辉随机服务系统理论(第二版)M北京：科学出版社1986【5】 何炎祥操作系统原理(第一版)上海：上海科学技术文献出版社，1999466473