edf调度算法

Ⅰ PD称为什么控制算法

PD称为基于优先级的调度算法（Priority-driven scheling-PD），基于优先级的调度算法给每个进程分配一个优先级，在每次进程调度时，调度器总是调度那个具有最高优先级的任务来执行。根据不同的优先级分配方法，基于优先级的调度算法可以分为如下两种类型[Krishna01][Wang99]：1、静态优先级调度算法：这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级。静态优先级的分配可以根据应用的属性来进行，比如任务的周期，用户优先级，或者其它的预先确定的策略卜搭碧。RM（Rate-Monotonic）调度算法是一种典型的静态优先级调度算法，它根据任务的执行周期的长短来决定调度优先级，那些具有小的执行周期的任务具有较高的优先级。2、动态优先级调枝困度算法：这种调度算法根据任务的资源需求来动态地分配任务的优先级，其目的就是在资源分配和调度时有更大的灵活性。非实时系统中就有很多这种调度算法，比如短作业优先的调度算法。在实时调度算法中， EDF算法是使用最多的一种动态优先级调度算法，该算法给就绪队列中的各型举个任务根据它们的截止期限（Deadline）来分配优先级，具有最近的截止期限的任务具有最高的优先级。

Ⅱ 股票中的edf是什么意思

EDF全称Earliest Deadline First。最早截止时间优先算法（EDF）也称为截止时间驱动调度算法（DDS），是一种动态调度算法。EDF在调度时，任务的优先级根据任务的截止时间动态分配。截止时间越短，优先级越高。如果一个任务集负载U<=1，则是可调度的。EDF 调度算法已被证明是动态最优调度， 而且是充要条件。处理机利用率最大可达100% 。但瞬时过载时， 系统行为不可预测， 可能发生多米诺骨牌现象， 一个任务丢失时会引起一连串的任务接连丢失。
拓展资料
股票中的标的是什么意思：标的证券是投资者融入资大乎旅金可买入的证券和证券公司可对投资者融出的证券。证券交易所按照从严到宽、从少到多、逐步扩大的原则，根据融资融券业务试点的进展情况，在满足证券交易所规定的证券范围内审核、选取试点初期标的证券的名单，并向市场公布。证券公司在上述范围内确定并公布该公司允许的标的证券。证券交易所规定融资买入标的证券和融券卖出标的证券限于其认可的上市股顷颂票、证券投资基金、及其他证券。
作为标的证券的股票应当符合的条件
1、在证券交易所上市交易满3个月；
2、融资买入标的股票的流通股本不少于1亿股或流通市值不低于5亿元，融券卖出标的股票的流通股本不少于2亿股或流通市值不低于8亿元；
3、股票发行公司的股东人数不少于4000人；
4、近3个月内日均换手率不低于基准指数日均换手率的20%，日均涨跌幅的平均值与基准指数涨跌幅的平均值的偏离值不超过4个百分点滚凳；且波动幅度不超过基准指数波动幅度的500%以上； 日均换手率是指过去3个月内标的证券或基准指数每日换手率的平均值。
日均涨跌幅是指过去3个月内标的证券或基准指数每日涨跌幅绝对值的平均值。 波动幅度是指过去3个月内标的证券或基准指数最高价与最低价之差对最高价和最低价的平均值之比。 对于基准指数，在上海交易所是指上证综合指数，在深圳交易所是指深证综合指数和中小板指数。
5、股票发行公司已完成股权分置改革；
6、股票交易未被证券交易所实行特别处理；
7、证券交易所规定的其他条件。

Ⅲ 实时调度的单处理器实时调度

问题描述：假设一任务集S={t1,t2,t3,...,tn}，周期分别是T1,T2,...,Tn，执行时间为c1,c2,...,cn，deadline为D1,D2,...,Dn，Di=Ti。任务ti可以被抢占。
CPU利用率用U=sum(ci/Ti)来表示。对于单处理器，U<=1是S可调度的前提条件，否则S不可调度。 任务按单调速率优先级分配（RMPA）的调度算法，称为单调速率调度（RMS）。RMPA是指任务的优先级按任务周期T来分配。它根据任务的执行周期的长短来决定调度优先级，那些具有小的执行周期的任务具有较高的优先级，周期长的任务优先级低。
不考虑n=1的情况。RMS是单处理器下的最优静态调度算法。1973年Liu和Layland发表的这篇文章的前半部分首次提出了RM调度算法在静态调度中的最优性. 它的一个特点是可通过对系统资源利用率的计算来进行任务可调度性分析, 算法简单、有效, 便于实现。不仅如此, 他们还把系统的利用系数(utilization factor)和系统可调度性联系起来, 推导出用RM调度所能达到的最小系统利用率公式. 同时, 这篇论文中透露出来的证明思想和方法也被人们所效仿. 下面就让我们来看看这篇文章中关于RM调度算法的重要结论。
任何一个结论都有一个模型假设, 让我们先列出这里的假设:
(A1) 所有的任务请求都是周期性的,必须在限定的时限内完成；
(A2) 任务的作业必须在该任务的下一个作业发生之前完成, 这样避免了考虑队列问题; 在这里, 我们对任务和作业不作特别的区分, 因为一个任务请求就是一个作业。
(A3) 任务之间都是独立的,每个任务的请求不依赖于其他任务请求的开始或完成；
(A4) 每个任务的运行时间是不变的,这里任务的运行时间是指处理器在无中断情况下用于处理该任务的时间；
(A5) 所有的非周期性任务都在特殊的情况下运行,比如系统初始化或系统非正常紧急处理程序。
(A6) 其它一些假设, 比如, 单处理器, 可抢占调度, 任务切换的时间忽略不计等等。 (1) 任务T i (P i, Ci, D i) 模型: 周期为P i,计算时间为Ci, 时限D i 为周期终点。任务在周期起点释放, 高优先级任务可抢占低优先级任务的执行。
(2) 优先级分配方法: 静态固定分配。优先级与周期成反比, 周期越短优先级越高。
(3) 可调度性分析: 如果任务集满足下式, 则该任务集可调度。
定理1：n个独立的周期任务可以被RMPA调度，如果U<=n(2^(1/n)-1)。
一个任务的响应时间(response time)是指一个任务请求到这个任务实际完成的时间跨度. 在静态调度中, 任务的临界时刻(critical instant)这个概念被首先提出来. 它被定义为一个特定的时刻, 如果在这个时刻任务请求到来, 那么会导致这个任务的响应时间最大（A critical instant of a task is the time atwhich the release of a task will proce the largestresponse time）. 由此得出
定理1: 一个任务的临界时刻就是比这个任务优先级高的所有任务同时发出请求的时刻.
（Lemma: For any task, the critical instant occurs if thattask is simultaneously released with all higher prioritytasks .）
证明: 由于一个任务的响应时间是它自己的负载时间加上被其它优先级高的任务所打断的时间. 由于自己的负载时间是固定的, 我们考虑在什么时候任一高优先级的任务会有最长的打断时间. 显然, 只有当这一高优先级的任务与该任务同时请求处理时, 才能可能产生最大的打断时间.
如果有任务1和任务2，且任务1的优先级比任务2高，那么任务2的响应时间会被任务1延迟。

当任务1的请求到来的更早，那么任务2的响应时间就更长了。

定理1的价值在于它找到了一个用于证明一个调度算法能否调度任一任务集的充分必要条件。那就是所有任务同时请求执行的情况下，每个任务仍能满足各自的期限, 那么这个任务集就可以被这个调度算法调度.
有了这个推论, 我们就可以证明RM调度的最优性了.
定理2: 如果一个任务集能够被静态调度, 那么RMS算法就能够调度这个任务集. 从这个意义上说, RMS是最优的静态调度算法.
这个定理的证明方法就是有名的交换法. 证明思路如下:
假设一个任务集S采用其他静态优先级算法可以调度,那么总有这样两个优先级相邻的任务i和j, 有Ti>Tj,而Pi≤Pj.把Ti和Tj的优先级Pi和Pj互换,明显可以看出这时S仍然可以调度, 因为在所有任务同时请求的情况下, 交换这两个任务不会影响其它任务的完成时间, 同时这两个任务都可以在各自期限内完成. 按照这样的方法,其他任何静态优先级调度最终都可以转换成RM调度.
RMS已被证明是静态最优调度算法, 开销小, 灵活性好, 是实时调度的基础性理论。即使系统瞬时过载, 也完全可预测哪些任务丢失时限。缺点是处理机利用率较低, 最坏的情况下，当n→∞时, 不超过ln2 (≈ 70%)。另外, RMS是充分但非必要条件。而在一般情况下，对于随机的任务集大约只有88%. 70%或者88%的处理器利用率对于许多实时应用来说是一个严重的限制，动态调度算法如最早截止期最先（earliest deadline first，EDF）或者最少空闲时间最先（least laxity first，LLF）已经被证明是最优的，并且能够实现100% 的处理器利用率. 最早截止时间优先算法（EDF）也称为截止时间驱动调度算法（DDS），是一种动态调度算法。EDF指在调度时，任务的优先级根据任务的截止时间动态分配。截止时间越短，优先级越高。EDF有如下定理：
定理2：如果一个任务集按EDF算法调度，当且仅当U<=1。
EDF的特点
(1) 任务模型: 与RMS 调度相同。
(2) 优先级分配方法: 动态分配, 距要求时限所剩时间越短优先级越高。
(3) 可调度性分析: 如果任务集满足下式, 则该任务集可调度。
EDF 调度算法已被证明是动态最优调度, 而且是充要条件。处理机利用率最大可达100% 。但瞬时过载时, 系统行为不可预测, 可能发生多米诺骨牌现象, 一个任务丢失时会引起一连串的任务接连丢失。另外, 它的在线调度开销比RMS大。 最短空闲时间优先算法（LLF）也是一种动态调度算法。LLF指在调度时刻，任务的优先级根据任务的空闲时间动态分配。空闲时间越短，优先级越高。空闲时间=deadline-任务剩余执行时间。LLF可调度条件和EDF相同。
理论上，EDF和LLF算法都是单处理器下的最优调度算法。但是由于EDF和LLF在每个调度时刻都要计算任务的deadline或者空闲时间，并根据计算结果改变任务优先级，因此开销大、不易实现，其应用受到一定限制。

Ⅳ 如何用C语言实现EDF，LSF调度算法

#include<stdio.h>voidmain()指磨旁{char*a[3][3]={{"sssd","sda","scsdf"唯橡},{"ere","edf","vadfd"},{"sah","hyt","tye"}};inti,j;游辩for(i=0;i<3;i++)for(j=0;j<3;j++)printf("%s",a[i][j]);}

Ⅳ 电梯调度算法...

不管你是在北上广还是在港澳台，甚至三四线城市，凡是有规模的地区，高楼比比皆是。不管是写字楼，还是大型商城，让你最头痛的就是乘电梯，尤其是在赶时间的时候。

每天早上，那些差5分钟就迟到的程序员，在等电梯时，一般会做两件事：

前者可能是写字楼里上班族惯有的精神类疾病，但后者肯定是程序员的职业病。本文对“骂电梯”不给予任何指导性建议。

但说起电梯调度算法，我觉得还是可以给大家科普一下，好为大家在等电梯之余，打发时间而做出一点贡献。

（电梯调度算法可以参考各种硬盘换道算法，下面内容整理自网络）

先来先服务（FCFS-First Come First Serve）算法，是一种随即服务算法，它不仅仅没有对寻找楼层进行优化，也没有实时性的特征，它是一种最简单的电梯调度算法。

它根据乘客请求乘坐电梯的先后次序进行调度。此算法的 优点是公平、简单，且每个乘客的请求都能依次地得到处理，不会出现某一乘客的请求长期得不到满足的情况 。

这种方法在载荷较轻松的环境下，性能尚可接受，但是在载荷较大的情况下，这种算法的性能就会严重下降，甚至恶化。

人们之所以研究这种在载荷较大的情况下几乎不可用的算法，有两个原因：

最短寻找楼层时间优先（SSTF-Shortest Seek Time First）算法，它注重电梯寻找楼层的优化。最短寻找楼层时间优先算法选择下一个服务对象的原则是 最短寻找楼层的时间。

这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。

在重载荷的情况下，最短寻找楼层时间优先算法的平均响应时间较短，但响应时间的方差较大 ，原因是队列中的某些请求可能长时间得不到响应，出现所谓的“ 饿死”现象 。

扫描算法（SCAN） 是一种按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。

它进行寻找楼层的优化，效率比较高，但它是一个 非实时算法 。扫描算法较好地解决了电梯移动的问题，在这个算法中，每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的。

所有的与电梯运行方向相同的乘客的请求在一次电向上运行或向下运行的过程中完成， 免去了电梯频繁的来回移动 。

扫描算法的平均响应时间比最短寻找楼层时间优先算法长，但是响应时间方差比最短寻找楼层时间优先算法小， 从统计学角度来讲，扫描算法要比最短寻找楼层时间优先算法稳定 。

LOOK 算法是扫描算法（SCAN）的一种改进。对LOOK算法而言，电梯同样在最底层和最顶层之间运行。

但 当 LOOK 算法发现电梯所移动的方向上不再有请求时立即改变运行方向 ，而扫描算法则需要移动到最底层或者最顶层时才改变运行方向。

SATF（Shortest Access Time First）算法与 SSTF 算法的思想类似，唯一的区别就是 SATF 算法将 SSTF 算法中的寻找楼层时间改成了访问时间。

这是因为电梯技术发展到今天，寻找楼层的时间已经有了很大地改进， 但是电梯的运行当中等待乘客上梯时间却不是人为可以控制 。

SATF 算法考虑到了电梯运行过程中乘客上梯时间的影响 。

最早截止期优先（EDF-Earliest Deadline First）调度算法是最简单的实时电梯调度算法，它的 缺点就是造成电梯任意地寻找楼层，导致极低的电梯吞吐率。

它与 FCFS 调度算法类似，EDF 算法是电梯实时调度算法中最简单的调度算法。 它响应请求队列中时限最早的请求，是其它实时电梯调度算法性能衡量的基准和特例。

SCAN-EDF 算法是 SCAN 算法和 EDF 算法相结合的产物。SCAN-EDF 算法先按照 EDF 算法选择请求列队中哪一个是下一个服务对象，而对于具有相同时限的请求，则按照 SCAN 算法服务每一个请求。它的效率取决于有相同 deadline 的数目，因而效率是有限的。

PI（Priority Inversion）算法将请求队列中的请求分成两个优先级，它首先保证高优先级队列中的请求得到及时响应，再搞优先级队列为空的情况下在相应地优先级队列中的请求。

FD-SCAN（Feasible Deadline SCAN）算法首先从请求队列中找出时限最早、从当前位置开始移动又可以买足其时限要求的请求，作为下一次 SCAN 的方向。

并在电梯所在楼层向该请求信号运行的过程中响应处在与电梯运行方向相同且电梯可以经过的请求信号。

这种算法忽略了用 SCAN 算法相应其它请求的开销，因此并不能确保服务对象时限最终得到满足。

以上两结介绍了几种简单的电梯调度算法。

但是并不是说目前电梯调度只发展到这个层次。目前电梯的控制技术已经进入了电梯群控的时代。

随着微机在电梯系统中的应用和人工智能技术的发展，智能群控技术得以迅速发展起来。

由此，电梯的群控方面陆续发展出了一批新方法，包括：基于专家系统的电梯群控方法、基于模糊逻辑的电梯群控方法、基于遗产算法的电梯群控方法、基于胜景网络的电梯群控方法和基于模糊神经网络的电梯群控方法。

本人设置的电梯的初始状态，是对住宅楼的电梯的设置。

(1)建筑共有21层，其中含有地下一层（地下一层为停车场）。
(2)建筑内部设有两部电梯，编号分别为A梯、B梯。
(3)电梯内部有23个按钮，其中包括开门按钮、关门按钮和楼层按钮，编号为-1，1，2，3，4……20。
(4)电梯外部含有两个按钮，即向上运行按钮和向下运行按钮。建筑顶层与地下一层例外，建筑顶层只设置有向下运行按钮，地下一层只设置有向上运行按钮。
(5)电梯开关门完成时间设定为1秒。电梯到达每层后上下人的时间设定为8秒。电梯从静止开始运行到下一层的时间设置为2秒，而运行中通过一层的时间为1秒。
(6)在凌晨2：00——4：30之间，如若没有请求信号，A梯自动停在14层，B梯自动停在6层。
(7)当电梯下到-1层后，如果没有请求信号，电梯自动回到1层。

每一架电梯都有一个编号，以方便监控与维修。每一架电梯都有一实时监控器，负责监控电梯上下，向电梯升降盒发送启动、制动、加速、减速、开关电梯门的信号。若电梯发生故障，还应向相应的电梯负责人发送求救信号。

电梯内部的楼层按钮：

这样就表示乘客将要去往此层，电梯将开往相应层。当电梯到达该层后，按钮恢复可以使用状态。

电梯内部开门按钮：

如若电梯到了乘客曾经按下的楼层，但是无乘客按开门按钮，电梯将自动在停稳后1秒后自动开门。

电梯内部关门按钮：

电梯外部向上按钮：

电梯外部向下按钮：

你肯能意识到 哪个算法都不是一个最佳方案，只是它确实解决了一定情况的问题 。但是对一个优秀的程序员而言，研究各种算法是无比快乐的。也许你下一次面试，就有关于调度算法的问题。

Ⅵ 设有周期性实时任务集如下表所示，用 edf 算法和 rms 算 法是否可以调度

分布式实时谨唤皮调度算法可以分为两类：
1）以RMS为基础的广义RMS调度
2）以风车调度Sr为基础的DSr调度 定义：设?X={Xi}是一个分布式的任务集合，1≤i≤n，分布式系统中有祥差m个节点，对于Xi∈X,Xi={Ti1,?Ti2,…，?Tim}，Tij是Xi在Nj节点上的任务，Xi有距离约束ci。链慎对于Tij?有执行时间eij。
定义lk=ck/2“lg(ck/cl)， Bik=lk·2lg(ci/lk)”。
ΦNj(lk）=∑eij/Bik,（i=1..n）为调度任务集在节点Nj上的密度。
选择一个使∑ΦNj(lk)，j=1..m）最小值的lk作为系统的划分基r*。?
算法前提： 所有的任务有相同的执行节点，每个任务在网络节点上有同样的距离约束。

Ⅶ 什么是最早截止时间优先调度算法

最早截如伏止时间优先（Earliest Dealine First， EDF）是实时系统中常用的一种调度算法，系统中有多个任务时，由调度算法扒者决定哪个任务当前占用处理器，那么EDF算法就是按照任务的截止时间（deadline）来确定任务的执行顺序，最早截止的任务先执春橡薯行。

Ⅷ linux环境下的进程调度算法有哪些

第一部分： 实时调度算法介绍

对于什么是实时系统，POSIX 1003.b作了这样的定义：指系统能够在限定的响应时间内提供所需水平的服务。而一个由Donald Gillies提出的更加为大家接受的定义是：一个实时系统是指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错。

实时系统根据其对于实时性要求的不同，可以分为软实时和硬实时两种类型。硬实时系统指系统要有确保的最坏情况下的服务时间，即对于事件的响应时间的截止期限是无论如何都必须得到满足。比如航天中的宇宙飞船的控制等就是现实中这样的系统。其他的所有有实时特性的系统都可以称之为软实时系统。如果明确地来说，软实时系统就是那些从统计的角度来说，一个任务（在下面的论述中，我们将对任务和进程不作区分）能够得到有确保的处理时间，到达系统的事件也能够在截止期限到来之前得到处理，但违反截止期限并不会带来致命的错误，像实时多媒体系统就是一种软实时系统。

一个计算机系统为了提供对于实时性的支持，它的操作系统必须对于CPU和其他资源进行有效的调度和管理。在多任务实时系统中，资源的调度和管理更加复杂。本文下面将先从分类的角度对各种实时任务调度算法进行讨论，然后研究普通的 Linux操作系统的进程调度以及各种实时Linux系统为了支持实时特性对普通Linux系统所做的改进。最后分析了将Linux操作系统应用于实时领域中时所出现的一些问题，并总结了各种实时Linux是如何解决这些问题的。

1. 实时CPU调度算法分类

各种实时操作系统的实时调度算法可以分为如下三种类别[Wang99][Gopalan01]：基于优先级的调度算法（Priority-driven scheling-PD）、基于CPU使用比例的共享式的调度算法（Share-driven scheling-SD）、以及基于时间的进程调度算法（Time-driven scheling-TD），下面对这三种调度算法逐一进行介绍。

1.1. 基于优先级的调度算法

基于优先级的调度算法给每个进程分配一个优先级，在每次进程调度时，调度器总是调度那个具有最高优先级的任务来执行。根据不同的优先级分配方法，基于优先级的调度算法可以分为如下两种类型[Krishna01][Wang99]：

静态优先级调度算法：

这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级。静态优先级的分配可以根据应用的属性来进行，比如任务的周期，用户优先级，或者其它的预先确定的策略。RM（Rate-Monotonic）调度算法是一种典型的静态优先级调度算法，它根据任务的执行周期的长短来决定调度优先级，那些具有小的执行周期的任务具有较高的优先级。

动态优先级调度算法：

这种调度算法根据任务的资源需求来动态地分配任务的优先级，其目的就是在资源分配和调度时有更大的灵活性。非实时系统中就有很多这种调度算法，比如短作业优先的调度算法。在实时调度算法中， EDF算法是使用最多的一种动态优先级调度算法，该算法给就绪队列中的各个任务根据它们的截止期限（Deadline）来分配优先级，具有最近的截止期限的任务具有最高的优先级。

1.2. 基于比例共享调度算法

虽然基于优先级的调度算法简单而有效，但这种调度算法提供的是一种硬实时的调度，在很多情况下并不适合使用这种调度算法：比如象实时多媒体会议系统这样的软实时应用。对于这种软实时应用，使用一种比例共享式的资源调度算法（SD算法）更为适合。

比例共享调度算法指基于CPU使用比例的共享式的调度算法，其基本思想就是按照一定的权重（比例）对一组需要调度的任务进行调度，让它们的执行时间与它们的权重完全成正比。

我们可以通过两种方法来实现比例共享调度算法[Nieh01]：第一种方法是调节各个就绪进程出现在调度队列队首的频率，并调度队首的进程执行；第二种做法就是逐次调度就绪队列中的各个进程投入运行，但根据分配的权重调节分配个每个进程的运行时间片。

比例共享调度算法可以分为以下几个类别：轮转法、公平共享、公平队列、彩票调度法（Lottery）等。

比例共享调度算法的一个问题就是它没有定义任何优先级的概念；所有的任务都根据它们申请的比例共享CPU资源，当系统处于过载状态时，所有的任务的执行都会按比例地变慢。所以为了保证系统中实时进程能够获得一定的CPU处理时间，一般采用一种动态调节进程权重的方法。

1.3. 基于时间的进程调度算法

对于那些具有稳定、已知输入的简单系统，可以使用时间驱动（Time-driven:TD）的调度算法，它能够为数据处理提供很好的预测性。这种调度算法本质上是一种设计时就确定下来的离线的静态调度方法。在系统的设计阶段，在明确系统中所有的处理情况下，对于各个任务的开始、切换、以及结束时间等就事先做出明确的安排和设计。这种调度算法适合于那些很小的嵌入式系统、自控系统、传感器等应用环境。

这种调度算法的优点是任务的执行有很好的可预测性，但最大的缺点是缺乏灵活性，并且会出现有任务需要被执行而CPU却保持空闲的情况。

2. 通用Linux系统中的CPU调度

通用Linux系统支持实时和非实时两种进程，实时进程相对于普通进程具有绝对的优先级。对应地，实时进程采用SCHED_FIFO或者SCHED_RR调度策略，普通的进程采用SCHED_OTHER调度策略。

在调度算法的实现上，Linux中的每个任务有四个与调度相关的参数，它们是rt_priority、policy、priority（nice）、counter。调度程序根据这四个参数进行进程调度。

在SCHED_OTHER 调度策略中，调度器总是选择那个priority+counter值最大的进程来调度执行。从逻辑上分析，SCHED_OTHER调度策略存在着调度周期（epoch），在每一个调度周期中，一个进程的priority和counter值的大小影响了当前时刻应该调度哪一个进程来执行，其中 priority是一个固定不变的值，在进程创建时就已经确定，它代表了该进程的优先级，也代表这该进程在每一个调度周期中能够得到的时间片的多少； counter是一个动态变化的值，它反映了一个进程在当前的调度周期中还剩下的时间片。在每一个调度周期的开始，priority的值被赋给 counter，然后每次该进程被调度执行时，counter值都减少。当counter值为零时，该进程用完自己在本调度周期中的时间片，不再参与本调度周期的进程调度。当所有进程的时间片都用完时，一个调度周期结束，然后周而复始。另外可以看出Linux系统中的调度周期不是静态的，它是一个动态变化的量，比如处于可运行状态的进程的多少和它们priority值都可以影响一个epoch的长短。值得注意的一点是，在2.4以上的内核中， priority被nice所取代，但二者作用类似。

可见SCHED_OTHER调度策略本质上是一种比例共享的调度策略，它的这种设计方法能够保证进程调度时的公平性--一个低优先级的进程在每一个epoch中也会得到自己应得的那些CPU执行时间，另外它也提供了不同进程的优先级区分，具有高priority值的进程能够获得更多的执行时间。

对于实时进程来说，它们使用的是基于实时优先级rt_priority的优先级调度策略，但根据不同的调度策略，同一实时优先级的进程之间的调度方法有所不同：

SCHED_FIFO：不同的进程根据静态优先级进行排队，然后在同一优先级的队列中，谁先准备好运行就先调度谁，并且正在运行的进程不会被终止直到以下情况发生：1.被有更高优先级的进程所强占CPU；2.自己因为资源请求而阻塞；3.自己主动放弃CPU（调用sched_yield）；

SCHED_RR：这种调度策略跟上面的SCHED_FIFO一模一样，除了它给每个进程分配一个时间片，时间片到了正在执行的进程就放弃执行；时间片的长度可以通过sched_rr_get_interval调用得到；

由于Linux系统本身是一个面向桌面的系统，所以将它应用于实时应用中时存在如下的一些问题：

Linux系统中的调度单位为10ms，所以它不能够提供精确的定时；

当一个进程调用系统调用进入内核态运行时，它是不可被抢占的；

Linux内核实现中使用了大量的封中断操作会造成中断的丢失；

由于使用虚拟内存技术，当发生页出错时，需要从硬盘中读取交换数据，但硬盘读写由于存储位置的随机性会导致随机的读写时间，这在某些情况下会影响一些实时任务的截止期限；

虽然Linux进程调度也支持实时优先级，但缺乏有效的实时任务的调度机制和调度算法；它的网络子系统的协议处理和其它设备的中断处理都没有与它对应的进程的调度关联起来，并且它们自身也没有明确的调度机制；

3. 各种实时Linux系统

3.1. RT-Linux和RTAI

RT -Linux是新墨西哥科技大学（New Mexico Institute of Technology）的研究成果[RTLinuxWeb][Barabanov97]。它的基本思想是，为了在Linux系统中提供对于硬实时的支持，它实现了一个微内核的小的实时操作系统（我们也称之为RT-Linux的实时子系统），而将普通Linux系统作为一个该操作系统中的一个低优先级的任务来运行。另外普通Linux系统中的任务可以通过FIFO和实时任务进行通信。RT-Linux的框架如图 1所示：

图 1 RT-Linux结构

RT -Linux的关键技术是通过软件来模拟硬件的中断控制器。当Linux系统要封锁CPU的中断时时，RT-Linux中的实时子系统会截取到这个请求，把它记录下来，而实际上并不真正封锁硬件中断，这样就避免了由于封中断所造成的系统在一段时间没有响应的情况，从而提高了实时性。当有硬件中断到来时， RT-Linux截取该中断，并判断是否有实时子系统中的中断例程来处理还是传递给普通的Linux内核进行处理。另外，普通Linux系统中的最小定时精度由系统中的实时时钟的频率决定，一般Linux系统将该时钟设置为每秒来100个时钟中断，所以Linux系统中一般的定时精度为 10ms，即时钟周期是10ms，而RT-Linux通过将系统的实时时钟设置为单次触发状态，可以提供十几个微秒级的调度粒度。

RT-Linux实时子系统中的任务调度可以采用RM、EDF等优先级驱动的算法，也可以采用其他调度算法。

RT -Linux对于那些在重负荷下工作的专有系统来说，确实是一个不错的选择，但他仅仅提供了对于CPU资源的调度；并且实时系统和普通Linux系统关系不是十分密切，这样的话，开发人员不能充分利用Linux系统中已经实现的功能，如协议栈等。所以RT-Linux适合与工业控制等实时任务功能简单，并且有硬实时要求的环境中，但如果要应用与多媒体处理中还需要做大量的工作。

意大利的RTAI( Real-Time Application Interface )源于RT-Linux，它在设计思想上和RT-Linux完全相同。它当初设计目的是为了解决RT-Linux难于在不同Linux版本之间难于移植的问题，为此，RTAI在 Linux 上定义了一个实时硬件抽象层，实时任务通过这个抽象层提供的接口和Linux系统进行交互，这样在给Linux内核中增加实时支持时可以尽可能少地修改 Linux的内核源代码。

3.2. Kurt-Linux

Kurt -Linux由Kansas大学开发，它可以提供微秒级的实时精度[KurtWeb] [Srinivasan]。不同于RT-Linux单独实现一个实时内核的做法，Kurt -Linux是在通用Linux系统的基础上实现的，它也是第一个可以使用普通Linux系统调用的基于Linux的实时系统。

Kurt-Linux将系统分为三种状态：正常态、实时态和混合态，在正常态时它采用普通的Linux的调度策略，在实时态只运行实时任务，在混合态实时和非实时任务都可以执行；实时态可以用于对于实时性要求比较严格的情况。

为了提高Linux系统的实时特性，必须提高系统所支持的时钟精度。但如果仅仅简单地提高时钟频率，会引起调度负载的增加，从而严重降低系统的性能。为了解决这个矛盾， Kurt-Linux采用UTIME所使用的提高Linux系统中的时钟精度的方法[UTIMEWeb]：它将时钟芯片设置为单次触发状态（One shot mode），即每次给时钟芯片设置一个超时时间，然后到该超时事件发生时在时钟中断处理程序中再次根据需要给时钟芯片设置一个超时时间。它的基本思想是一个精确的定时意味着我们需要时钟中断在我们需要的一个比较精确的时间发生，但并非一定需要系统时钟频率达到此精度。它利用CPU的时钟计数器TSC (Time Stamp Counter)来提供精度可达CPU主频的时间精度。

对于实时任务的调度，Kurt-Linux采用基于时间（TD）的静态的实时CPU调度算法。实时任务在设计阶段就需要明确地说明它们实时事件要发生的时间。这种调度算法对于那些循环执行的任务能够取得较好的调度效果。

Kurt -Linux相对于RT-Linux的一个优点就是可以使用Linux系统自身的系统调用，它本来被设计用于提供对硬实时的支持，但由于它在实现上只是简单的将Linux调度器用一个简单的时间驱动的调度器所取代，所以它的实时进程的调度很容易受到其它非实时任务的影响，从而在有的情况下会发生实时任务的截止期限不能满足的情况，所以也被称作严格实时系统（Firm Real-time）。目前基于Kurt-Linux的应用有：ARTS（ATM Reference Traffic System）、多媒体播放软件等。另外Kurt-Linux所采用的这种方法需要频繁地对时钟芯片进行编程设置。

3.3. RED-Linux

RED -Linux是加州大学Irvine分校开发的实时Linux系统[REDWeb][ Wang99]，它将对实时调度的支持和Linux很好地实现在同一个操作系统内核中。它同时支持三种类型的调度算法，即：Time-Driven、 Priority-Dirven、Share-Driven。

为了提高系统的调度粒度，RED-Linux从RT-Linux那儿借鉴了软件模拟中断管理器的机制，并且提高了时钟中断频率。当有硬件中断到来时，RED-Linux的中断模拟程序仅仅是简单地将到来的中断放到一个队列中进行排队，并不执行真正的中断处理程序。

另外为了解决Linux进程在内核态不能被抢占的问题， RED-Linux在Linux内核的很多函数中插入了抢占点原语，使得进程在内核态时，也可以在一定程度上被抢占。通过这种方法提高了内核的实时特性。

RED-Linux的设计目标就是提供一个可以支持各种调度算法的通用的调度框架，该系统给每个任务增加了如下几项属性，并将它们作为进程调度的依据：

Priority：作业的优先级；

Start-Time：作业的开始时间；

Finish-Time：作业的结束时间；

Budget：作业在运行期间所要使用的资源的多少；

通过调整这些属性的取值及调度程序按照什么样的优先顺序来使用这些属性值，几乎可以实现所有的调度算法。这样的话，可以将三种不同的调度算法无缝、统一地结合到了一起。

Ⅸ 时间片轮转调度算法的算法

多级反馈队列调度算法
(1) 设置多个就绪队列,并为各个队列赋予不同的优先级. 第一个队列的优先级最高,第二个队列次之,其余各队列的优先权逐个降低.
该算法赋予各个队列中进程执行时间片的大小也各不相同:
在优先权愈高的队列中,为每个进程所规定的执行时间片就愈小.
例如:第二个队列的时间片要比第一个队列的时间片长一倍,……,第i+1个队列的时间片要比第i个队列的时间片长一倍.
(2) 当一个新进程进入内存后,首先将它放入第一队列的末尾,按FCFS原则排队等待调度.当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按FCFS原则等待调度执行;如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列,……,如此下去,当一个长作业(进程)从第一队列依次降到第n队列后,在第n队列中便采取按时间片轮转的方式运行.
(3) 仅当第一队列空闲时,调度程序才调度第二队列中的进程运行; 仅当第1~(i-1) 队列均空时,才会调度第i队列中的进程运行.如果处理机正在第i队列中为某进程服务时,又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列),则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在运行的进程放回到第i队列的末尾,把处理机分配给新到的高优先权进程.?
性能
(1)终端型作业用户
(2) 短批处理作业用户
(3) 长批处理作业用户
满足了多数用户的需求 优先权调度算法
1,优先权调度算法的类型
非抢占式优先权算法
在这种方式下,系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成; 或因发生某事件使该进程放弃处理机时,系统方可再将处理机重新分配给另一优先权最高的进程.这种调度算法主要用于批处理系统中;也可用于某些对实时性要求不严的实时系统中.
抢占式优先权调度算法
系统同样把处理机分配给优先权最高的进程,使之执行.但在其执行期间,只要又出现了另一个其优先权更高的进程,进程调度程序就立即停止当前进程(原优先权最高的进程)的执行,重新将处理机分配给新到的优先权最高的进程.
这种抢占式的优先权调度算法,能更好地满足紧迫作业的要求,常用于要求比较严格的实时系统中, 以及对性能要求较高的批处理和分时系统中.
2,优先权的类型
(1) 静态优先权
静态优先权是在创建进程时确定的,且在进程的整个运行期间保持不变.
一般地,优先权是利用某一范围内的一个整数来表示的,例如,0~7或0~255中的某一整数, 又把该整数称为优先数.只是具体用法各异:有的系统用0表示最高优先权,当数值愈大时,其优先权愈低;而有的系统恰恰相反.
确定进程优先权的依据有如下三个方面:
1.进程类型.(系统进程/用户进程)
2.进程对资源的需求.(需求量的大小)
3.用户要求.(用户进程紧迫程度)
(2) 动态优先权
动态优先权是指在创建进程时所赋予的优先权,可以随进程的推进或随其等待时间的增加而改变的,以便获得更好的调度性能.
例如,我们可以规定,在就绪队列中的进程,随其等待时间的增长,其优先权以速率a提高.若所有的进程都具有相同的优先权初值,则显然是最先进入就绪队列的进程,将因其动态优先权变得最高而优先获得处理机,此即FCFS算法.
优先权的变化规律可描述为:
由于等待时间与服务时间之和,就是系统对该作业的响应时间,故该优先权又相当于响应比RP.据此,又可表示为:
3,高响应比优先调度算法
由上面的式子可以得到以下结论:
(1) 如果作业的等待时间相同,则要求服务的时间愈短,其优先权愈高,因而该算法有利于短作业.
(2) 当要求服务的时间相同时,作业的优先权决定于其等待时间,等待时间愈长,其优先权愈高,因而它实现的是先来先服务.
(3) 对于长作业,作业的优先级可以随等待时间的增加而提高,当其等待时间足够长时,其优先级便可升到很高, 从而也可获得处理机.
该算法照顾了短作业,且不会使长作业长期得不到服务 1. 非抢占式调度算法
为每一个被控对象建立一个实时任务并将它们排列成一轮转队列,调度程序每次选择队列中的第一个任务投入运行.该任务完成后便把它挂在轮转队列的队尾等待下次调度运行.
2. 非抢占式优先调度算法.
实时任务到达时,把他们安排在就绪队列的对首,等待当前任务自我终止或运行完成后才能被调度执行.
3. 抢占式调度算法
1）基于时钟中断的抢占式优先权调度算法.
实时任务到达后,如果该任务的优先级别高于当前任务的优先级并不立即抢占当前任务的处理机,而是等到时钟中断到来时,调度程序才剥夺当前任务的执行,将处理机分配给新到的高优先权任务.
2）立即抢占的优先权调度算法.
在这种调度策略中,要求操作系统具有快速响应外部时间中断的能力.一旦出现外部中断,只要当前任务未处于临界区便立即剥夺当前任务的执行,把处理机分配给请求中断的紧迫任务，实时进程调度，实时进程抢占当前。 1 实现实时调度的基本条件
1-1. 提供必要的信息-就绪时间.
1-2. 开始截止时间和完成截止时间.
1-3. 处理时间.
1-4. 资源要求.
1-5. 优先级.
2. 系统处理能力强
在实时系统中,通常都有着多个实时任务.若处理机的处理能力不够强,则有可能因处理机忙不过来而使某些实时任务不能得到及时处理, 从而导致发生难以预料的后果.假定系统中有m个周期性的硬实时任务,它们的处理时间可表示为Ci,周期时间表示为Pi,则在单处理机情况下,系统可调度必须满足下面的限制条件:
当系统不可调度时解决的方法是提高系统的处理能力,其途径有二:
其一仍是采用单处理机系统,但须增强其处理能力, 以显着地减少对每一个任务的处理时间;
其二是采用多处理机系统.假定系统中的处理机数为N,则应将上述的限制条件改为:
3. 采用抢占式调度机制
当一个优先权更高的任务到达时,允许将当前任务暂时挂起,而令高优先权任务立即投入运行.采用这种方式去满足那些开始截止时间即将到来的任务.?
4. 具有快速切换机制
应具有的能力:
(1) 对外部中断的快速响应能力.为使在紧迫的外部事件请求中断时系统能及时响应,要求系统具有快速硬件中断机构,还应使禁止中断的时间间隔尽量短,以免耽误时机(其它紧迫任务).?
(2) 快速的任务分派能力.在完成任务调度后,便应进行任务切换.为了提高分派程序进行任务切换时的速度, 应使系统中的每个运行功能单位适当的小,以减少任务切换的时间开销.实时调度实例
一, 最早截止时间优先算法(EDF)
EDF算法用于非抢占调度方式
优先级:根据任务的开始截止时间来确定任务的优先级.
二,最低松弛优先算法(LLF)
例如:系统中有两个周期性实时任务A和B,任务A要求每20ms执行一次,执行时间为10ms;任务B要求每50ms执行一次,执行时间为25ms.这样可知A和B每次必须完成的时间和开始截止时间如图所示
优先级:根据任务紧急程度来确定任务优先级
A和B任务每次必须完成的时间
A1 (10) A2 (30) A3(50) A4 (70) A5(90) A6 (110) A7(130) A8(150)
0 、10、 20、 30 、40、 50 、60、 70、 80 、90 、100 、110、 120、130、 140、 150
B1(25) B2(75) B3(125)
A和B任务每次必须开始的时间
时间(ms) A截止时间 B截止时间 调度对象
0 A1(10) B1(25) A1
10 A2(20) B1(15) B1
30 A2(0) B1(15) A2
40 A3(10) B1(5) B1
45 A3(5) B2(30) A3
55 A4(15) B2(20) B2
70 A4(0) B2(20) A4
松弛度
松弛度
( 20-10-0 ) ( 50-25-0 )
(40-10-10 ) ( 50-25-10 )
(40-10-30) (50-5-30)
(60-10-40) (50-5-40)
(60-10-45) (100-25-45)
(80-10-55) (100-25-55)
(80-10-70) (100-10-70 )
3.4.1 多处理器系统的类型
(1) 紧密耦合(Tightly Coupted)MPS.
这通常是通过高速总线或高速交叉开关,来实现多个处理器之间的互连的.它们共享主存储器系统和I/O设备,并要求将主存储器划分为若干个能独立访问的存储器模块,以便多个处理机能同时对主存进行访问.系统中的所有资源和进程,都由操作系统实施统一的控制和管理.
3.4 多处理机系统中的调度
从处理器之间耦合的紧密程度上划分:
松散耦合(Loosely Coupled)MPS.
在松散耦合MPS中,通常是通过通道或通信线路,来实现多台计算机之间的互连.每台计算机都有自己的存储器和I/O设备,并配置了OS来管理本地资源和在本地运行的进程.因此,每一台计算机都能独立地工作, 必要时可通过通信线路与其它计算机交换信息,以及协调它们之间的工作.
根据系统中所用处理器的相同与否划分:
(1) 对称多处理器系统SMPS. 在系统中所包含的各处理器单元,在功能和结构上都是相同的,当前的绝大多数MPS都属于SMP系统.例如,IBM公司的SR/6000 Model F50, 便是利用4片Power PC处理器构成的.?
(2) 非对称多处理器系统.在系统中有多种类型的处理单元,它们的功能和结构各不相同,其中只有一个主处理器,有多个从处理器：
1. 对称多处理器系统中的进程分配方式
在SMP系统中,所有的处理器都是相同的,因而可把所有的处理器作为一个处理器池(Processor pool),由调度程序或基于处理器的请求,将任何一个进程分配给池中的任何一个处理器去处理.在进行进程分配时,可采用以下两种方式之一.
1) 静态分配(Static Assigenment)方式
2) 动态分配(Dynamic Assgement)方式?
3.4.2 进程分配方式
静态分配(Static Assigenment)方式
一个进程从开始执行直到完成,都被固定分配到一个处理器上去执行.
2) 动态分配(Dynamic Assgement)方式
系统中设置有公共的就绪队列.分配进程时,可以将进程分配到任何一个处理器上.
动态分配方式的主要优点是消除了各处理器忙闲不均的现象
2. 非对称MPS中的进程分配方式?
对于非对称MPS,其OS大多采用主—从(Master-Slave)式OS,即OS的核心部分驻留在一台主机上(Master),而从机(Slave)上只是用户程序,进程调度只由主机执行.每当从机空闲时,便向主机发送一索求进程的信号,然后,便等待主机为它分配进程.在主机中保持有一个就绪队列,只要就绪队列不空,主机便从其队首摘下一进程分配给请求的从机.从机接收到分配的进程后便运行该进程,该进程结束后从机又向主机发出请求.
缺点:对主机要求高,出现故障导致整个系统瘫痪
1. 自调度(Self-Scheling)方式
1) 自调度机制?
在系统中设置有一个公共的进程或线程就绪队列, 所有的处理器在空闲时,都可自己到该队列中取得一进程(或线程)来运行.在自调度方式中,可采用在单处理机环境下所用的调度算法,如先来先服务(FCFS)调度算法,最高优先权优先(FPF)调度算法和抢占式最高优先权优先调度算法等.
3.4.3 进程(线程)调度方式
2) 自调度方式的优点?
1,系统中的公共就绪队列可按照单处理机系统中所采用的各种方式加以组织;其调度算法也可沿用单处理机系统所用的算法,即很容易将单处理机环境下的调度机制移植到多处理机系统中
2,只要系统中有任务(公共就绪队列不空)就不会出现处理机空闲的情况,也不会发生处理器忙闲不均的现象,因而有利于提高处理器的利用率.
3)自调度方式的缺点
3.4.4进程调度过程
1、进程名：作为进程的标识。
指针：进程按顺序排成循环链表，用指针指出下一个进程的进程控制块首地址，最后一个进程中的指针指出第一个进程的进程控制块首地址。
2、要求运行时间：假设进程需要运行的单位时间数。
已运行时间：假设进程已经运行的单位时间数，初值为0。
状态：可假设有两种状态，就绪状态和结束状态。进程的初始状态都为就绪状态。
3、每次运行所设计的处理器调度程序调度进程之前，为每个进程任意确定它的要求运行时间。
4、此程序是模拟处理器调度，因此，被选中的进程并不实际启动运行，而是执行
已运行时间+1
来模拟进程的一次运行，表示进程已经运行过一个单位时间。
.5、在所设计的程序中应有显示或打印语句，能显示或打印每次被选中的进程名以及运行一次后进程队列的变化。
6、为进程任意确定要求运行时间，运行所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。
7、设有一个就绪队列，就绪进程按优先数（优先数范围0－100）由小到大排列（优先数越小，级别越高）。当某一进程运行完一个时间片后，其优先级应下调（如优先数加2或3）。
8、例如一组进程如下表： 进程名 A B C D E F G H J K L M 到达时间 0 1 2 3 6 8 12 12 12 18 25 25 服务时间 6 4 10 5 1 2 5 10 4 3 15 8

Ⅹ 编写代码实现作业的三种调度算法

#include<windows.h>
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
const int maxnum=100;
int N; /*进程数*/
double start[maxnum],endtime[maxnum],arrive[maxnum],runtime[maxnum],zhou[maxnum];
double averagezhou; // 平均周转时间
double average_zhou; //平均带权周转时间
char name; //进程名
double dqzhou[maxnum]; //带权周转时间
typedef struct node
{
char name[10]; //进程名
int round; //进程时间轮转时间片
int cputime; //进程占用CPU时间
int needtime; //进程到完成还要的时间
char state; //进程的状态
struct node *next; //链指针
}PCB;
PCB *finish,*ready,*tail,*run; /*队列指针*/

void firstin() /*将就绪队列中的第一个进程投入运行*/
{
run=ready; /*就绪队列头指针赋值给运行头指针*/
run->state='R'; /*进程状态变为运行态*/
ready=ready->next; /*就绪对列头指针后移到下一进程*/
}
void print1(PCB *q) /*进程PCB输出*/
{
printf("进程名 已运行时间 还需要时间 时间片 状态\n");
printf(" %-10s%-15d%-10d%-10d %-c\n",q->name,q->cputime,q->needtime,q->round,q->state);
}
void print() /*输出函数*/
{
PCB *p;
if(run!=NULL) /*如果运行指针不空*/
print1(run); /*输出当前正在运行的PCB*/
p=ready; /*输出就绪队列PCB*/
while(p!=NULL)
{
print1(p);
p=p->next;
}
p=finish; /*输出完成队列的PCB*/
while(p!=NULL)
{
print1(p);
p=p->next;
}
}
void insert(PCB *p2) //轮转法插入函数
{
tail->next=p2; //将新的PCB插入在当前就绪队列的尾
tail=p2;
p2->next=NULL;
}
void create() /*创建进程PCB*/
{
PCB *p;
int i,time;
char na[10];
ready=NULL;
finish=NULL;
run=NULL;
printf("请输入进程名称和所需要CPU的时间:\n");
for(i=1;i<=N;i++)
{
p=(PCB *)malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
if(i==1)
p->state='R';
else
p->state='W';
p->round=1; /*时间片*/
if(ready!=NULL)
insert(p);
else
{
p->next=ready;
ready=p;
tail=p;
}
}
printf("------------------------------------------------------------------\n");
print(); /*输出进程PCB信息*/
run=ready; /*将就绪队列的第一个进程投入运行*/
ready=ready->next;
run->state='R';
}
void RR() //时间片轮转调度
{
while(run!=NULL)
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
if(run->needtime==0) /*运行完将其变为完成态，插入完成队列*/
{
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
firstin(); /*就绪对列不空，将第一个进程投入运行*/
}
else
if(ready!=NULL) /*如就绪队列不空*/
{
run->state='W'; /*将进程插入到就绪队列中等待轮转*/
insert(run);
firstin(); /*将就绪对列的第一个进程投入运行*/
}
printf("------------------------------------------------------------------\n");
print(); /*输出进程信息*/
}
}

void FCFS(double *arrive,double *runtime,double n) //先来先服务调度算法
{
start[0]=arrive[0]; //开始执行时间=到达时间
endtime[0]=start[0]+runtime[0]; //完成时间=开始时间+服务时间
zhou[0]=endtime[0]-arrive[0]; //周转时间=完成时间-到达时间
dqzhou[0]=zhou[0]/runtime[0];
for(int i=0;i<n;i++)
{
if(endtime[i-1]>arrive[i]||endtime[i-1]==arrive[i])
endtime[i]=endtime[i-1]+runtime[i];
else
endtime[i]=arrive[i]+runtime[i];
zhou[i]=endtime[i]-arrive[i];
dqzhou[i]=zhou[i]/runtime[i];
averagezhou+=zhou[i];
average_zhou+=dqzhou[i];
}
averagezhou=averagezhou/n;
average_zhou=average_zhou/n;
cout<<"完成时间为:"<<endl;
for(int j=0;j<n;j++)
cout<<endtime[j]<<" "<<endl;
cout<<"周转时间为:"<<endl;
for(int k=0;k<n;k++)
cout<<zhou[k]<<" "<<endl;
cout<<"带权周转时间为:"<<endl;
for(int m=0;m<n;m++)
cout<<dqzhou[m]<<" "<<endl;
cout<<"平均周转时间为:"<<endl;
cout<<averagezhou<<" "<<endl;
cout<<"平均带权周转时间为:"<<endl;
cout<<average_zhou<<" "<<endl;
}

void SJF(double *arrive,double *runtime,double n) //短作业优先调度算法
{
int end[maxnum]; //用于标记进程是否已经执行，应经执行end[i]=1,否则为0;
for(int k=0;k<n;k++)
end[k]=0;
int temp,now=0,next=1,p=1; //now表示刚执行完的进程号，next表示下一个要执行的进程号
start[0]=arrive[0]; //开始执行时间=到达时间
endtime[0]=start[0]+runtime[0]; //完成时间=开始时间+服务时间
zhou[0]=endtime[0]-arrive[0]; //周转时间=完成时间-到达时间
dqzhou[0]=zhou[0]/runtime[0]; //带权周转时间=周转时间/服务时间
averagezhou=zhou[0];
average_zhou=dqzhou[0];
end[now]=1; //执行完的进程设置为1；
for(int i=1;i<n;i++)
{
int j;
for(j=1;j<n;)
{
if(arrive[j]<endtime[now]||arrive[j]==endtime[now])
j++;
else
break;
}
temp=j;
int min=p;
for(j=1;j<=temp;j++)
{
if(runtime[min]>runtime[j] && end[j]==0)
min=j;
}
next=min;
endtime[next]=endtime[now]+runtime[next];
zhou[next]=endtime[next]-arrive[next];
dqzhou[next]=zhou[next]/runtime[next];
averagezhou+=zhou[next];
average_zhou+=dqzhou[next];
end[next]=1;
now=next;
next=p;
while(end[p]!=0)
p++;
}
averagezhou=averagezhou/n;
average_zhou=average_zhou/n;
cout<<"完成时间为:"<<endl;
for(int j=0;j<n;j++)
cout<<endtime[j]<<" "<<endl;
cout<<"周转时间为:"<<endl;
for(k=0;k<n;k++)
cout<<zhou[k]<<" "<<endl;
cout<<"带权周转时间为:"<<endl;
for(int m=0;m<n;m++)
cout<<dqzhou[m]<<" "<<endl;
cout<<"平均周转时间为:"<<endl;
cout<<averagezhou<<" "<<endl;
cout<<"平均带权周转时间为:"<<endl;
cout<<average_zhou<<" "<<endl;
}

int EDF() //最早截止时间的调度算法
{
int arrive_A,arrive_B; //标记进程A,进程B的到达时间
int zhouqi_A,zhouqi_B,serve_A,serve_B; //进程的周期时间和服务时间
int i,j,a=0,b=0,ka=0,kb=0; //ka,kb为开关,i,j,a,b为进程下标
int num_a=0,num_b=0; //服务累计时间
printf("输入进程A的周期时间,服务时间: ");
scanf("%d%d",&zhouqi_A,&serve_A);
printf("输入进程B的周期时间,服务时间: ");
scanf("%d%d",&zhouqi_B,&serve_B);
for(int T=0;T<=100;T++)
{
if(num_a==serve_A) //进程A完成
{
num_a=serve_A+1;
printf("当T=%d时",T);
printf("进程A%d结束\n",a);
if(num_b<serve_B)
{
printf(" 调用进程B%d\n",b);
kb=1;
}
ka=0;
}
if(num_b==serve_B)
{
num_b=serve_B+1;
printf("当T=%d时",T);
printf("进程B%d结束\n",b);
if(num_a<serve_A)
{
printf(" 调用进程A%d\n",a);
ka=1;
}
kb=0;
}
if(T%zhouqi_A==0 && T%zhouqi_B==0)
{
arrive_A=arrive_B=T;
j=++a;
i=++b;
printf("当T=%d时,进程A%d和进程B%d同时产生，此时，",T,j,i);
if(zhouqi_A<=zhouqi_B)
{
printf("调用进程A%d，阻塞进程B%d\n",j,i);
ka=1;
kb=0;
}
else
{
printf("调用进程B%d，阻塞进程A%d\n",i,j);
ka=0;
kb=1;
}
num_a=num_b=0;
}
if(T%zhouqi_A==0&&T%zhouqi_B!=0)
{
arrive_A=T;
printf("当T=%d时",T);
printf("进程A%d产生 ",++a); //不可能与进程A竞争处理器
num_a=0;
if(num_b<serve_B) //进程B没有完成
if(arrive_B+zhouqi_B>arrive_A+zhouqi_A) //若进程B最早截止时间大于进程A的,则执行进程A
{
printf("进程A%d执行。\n",a);
ka=1;
kb=0;
}
else //若进程B最早截止时间小于等于进程A的
printf("进程B%d继续执行。\n",b);
else //进程B完成
{
printf("进程A%d执行。\n",a);
ka=1;
}
}
if(T%zhouqi_A!=0 && T%zhouqi_B==0)
{
arrive_B=T;
printf("当T=%d时",T);
printf("进程B%d产生，",++b); //不可能与进程B竞争处理器
num_b=0;
if(num_a<serve_A) //进程A没有完成
if(arrive_B+zhouqi_B>=arrive_A+zhouqi_A) //进程A的最早截止时间不小于B
printf("进程A%d继续执行。\n",a);
else
{
printf("进程B%d执行。\n",b);
kb=1;
ka=0;
}

else //进程A完成
{
printf("进程B%d执行。\n",b);
kb=1;
}
}
if(ka)
num_a++;
if(kb)
num_b++;
}
return 1;
}

int main()
{
system("color 0b"); //设置颜色
cout<<"最早截止时间的调度算法如下: "<<endl<<endl;
EDF();
int n;
cout<<endl;
cout<<"请输入进程的数目: ";
cin>>n;
cout<<"请按进程到达时间从小到大依次输入n个进程的到达时间: "<<endl;
for(int i=0;i<n;i++)
cin>>arrive[i];
cout<<"请按上面进程的顺序依次输入n个进程的服务时间: "<<endl;
for(int j=0;j<n;j++)
cin>>runtime[j];
cout<<"先来先服务调度算法如下: "<<endl;
FCFS(arrive,runtime,n);
cout<<endl<<endl;
cout<<"短作业优先调度算法如下: "<<endl;
SJF(arrive,runtime,n);
cout<<endl<<endl;
printf("轮转调度算法如下:\n\n");
printf("输入创建进程的数目:\n");
scanf("%d",&N);
create();
RR();
return 0；
}