进程调度量化分析中的概率模型应用

进程调度量化分析中的概率模型应用摘要：进程调度算法是计算机操作系统核心算法之一。通过简化进程的状态转换关系及概率论的相关理论，在给定了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分布。即 pNT=K=tkk!e-t k=1,2,3.其中：N(s)表示在时刻s处于就绪状态的进程数，表示到达率。（2)每个进程的CPU服务时间vn相互独立,具有相同的负指数分布：pvnt0 t, CPU处于不断忙碌中Lq就绪队列长度均值2(-)Lq=1-与CPU利用率相关wq进程在就绪队列中的等待时间均值(-)该指标也可以理解为进程在就绪队列中的平均响应时间，wq=Ww进程逗留时间均值1-不考虑在外存后被队列的等待时间表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