-
2021-05-18 09:19:13
满意答案
phoenix810
2013.11.30
采纳率:56% 等级:11
已帮助:8957人
假设有n个作业,按照运行时间排序t1 < t2 <... tn>
平均周转时间 = (总的运行时间 + 总的等待时间)/n
其中总的运行时间是定值,n为定值,因此要平均周转时间最短既要求总的等待时间最短。
按照最短作业优先,设第i个作业的等待时间为ai.则
a1 = 0
a2 = t1
a3 = t1 + t2
....
an = t1 + t2 + ... + t(i-1)
总的等待时间为a1 + a2 + a3 + ... + an
现在只需要证明这个是最小就可以了。任意取2个作业i 和 j。 且ti < tj。交换ti和tj的顺序。
则新等待时间变成b0 b1 b2 .... b(i-1) bi b(i+1) ..... b(j-1) bj b(j+1) ... bn 其中b0 + b1 + ... + b(i-1) + bi与原来的a相等。
b(i+1) = t1 + t2 + ... + t(i-1) + tj > t1 + t2 + ... + t(i-1) + ti = a(i+1)
依次类推之后bx > ax 其中i < x < j+1.之后b与a又相等。
所以任意交换后,等待时间变大。所以最小作业优先的等待时间最小。所以平均周转时间最短。
00分享举报
更多相关内容 -
平均周转时间各种算法
2017-04-04 21:03:27平均周转时间各种算法 有5个批处理的作业(A、B、C、D和E)几乎同时到达一个计算中心,估计的运行时间分别为2、4、6、8、10分钟,它们的优先数分别为1、2、3、4、5(1为最低优先级)。对下面的每种调度算法,...平均周转时间各种算法
有5个批处理的作业(A、B、C、D和E)几乎同时到达一个计算中心,估计的运行时间分别为2、4、6、8、10分钟,它们的优先数分别为1、2、3、4、5(1为最低优先级)。对下面的每种调度算法,分别计算作业的平均周转时间。
(1)最高优先级优先
(2)时间片轮转(时间片为2分钟)
(3)FCFS(作业到达顺序为C,D,B,E,A)
(4)短作业优先[分析]
本题是一个关于作业调度算法的评价的题目。题目给出一个实际的作业序列,由考生模拟作业的调度与执行过程,并给出对于这个作业序列作业调度算法的平均周转时间,从而对比不同调度算法的性能。本题可按照单道系统情况来处理。在题目中指出5个作业几乎同时到达一个计算中心,其含义是任何调度算法(除了FCFS算法外)都可以认为这5个作业是同时到达的,在调度过程中不需考虑其到达的顺序。
最高优先级
时间片轮转
FCFS
SJF
解答
-
最短任务优先(SJF)调度策略平均周转时间最优性的证明
2021-05-03 18:44:49最短任务优先调度策略是从运筹学中借鉴到计算机领域中的一种调度算法,它描述的策略可以简单概括为:先运行最短的任务,最后是次短的任务,如此下去。理想情况下,对操作系统中运行的进程作出如下假设:
1.每一个工作运行相同的时间
2.所有的工作同时到达
3.工作一旦开始,每个工作保持运行直到完成.
4.所有工作只是用的CPU(即他们不执行IO操作)
5.每个工作的运行时间是已知的.
先放宽假设1,即任务的运行时间可以存在差异.最短任务优先调度策略是从运筹学中借鉴到计算机领域中的一种调度算法,它描述的策略可以简单概括为:先运行最短的任务,最后是次短的任务,如此下去。
假设存在任务A,B,C同时在
时刻到达,其中A执行需要100ms,B和C分别需要10ms.
则SJF 调度策略可以表示为:
定义周转时间
周转时间 = 完成时间 - 到达时间
周转时间是一个性能指标,另一种指标是公平,性能和公平在调度系统中是矛盾的,如调度程序可以优化性能,但代价是阻止一些任务运行,这就降低了公平.
可以计算在这个例子中SJF调度策略的平均周转时间为:
事实上,考虑所有工作同时到达的假设,可以证明SJF确实是一个最优的调度算法,现在给出证明.
假设被调度进程集合有n个元素.对这n个进程的任意排列
,便是一种调度方案.
设T为任意一种调度策略产生的平均周转时间,则
Ti是第i+1个执行的进程的运行时间.
对T0,T1,...,Tn-1递增排序,得Tk0 , Tk1, …… ,Tkn-1,设T'位SJF策略生成的调度方案的平均周转时间,则:
T' = [ Tk0 + (Tk0 + Tk1)+……+( Tk0 + Tk1 + ……+ Tkn-1)]/n
对比构成T和T'的每个累加项,后者永远不大于前者,T'是T中最小值.故,能够产生T'的调度方案必为理论最优,而T2调度方案是SJF生成的,得证.
因此,找到了一个用SJF进行调度的好方法,但是所有任务同时到达仍然是不符合实际的,现在假设任务可以随时到达,而不在是同时到达,会导致什么问题呢?
假设A在t=0时刻到达,且需要运行100ms,而B和C在A之后不久(t=10ms)到达,他们仍然被迫等到A完成,从而遭遇到护航问题(与当前任务相比,后来到达的任务有比较短的执行时间).
为了解决这个问题,需要放宽条件(工作必须保持运行直到完成),还需要调度程序本身的一些机制,由于系统提供了时钟中断和上下文切换,当B和C到达时调度程序可以做一些事情,比如抢占A,运行另外一个工作.根据前面的定义,工作一旦开始,必须继续直到完成,所以sjf是一种非抢占式的调度程序,因此存在上述问题.
所以这里就引出了另外一种调度程序,叫做(STCF, shortest-time to completion First)或抢占式最短作业优先算法.每当新工作进入系统时,它就会确定剩余工作和新工作作用,谁的剩余时间最少,然后调度剩余时间最少的工作.因此,在stcf中,上面的例子将按照如下时间线运行:
平均周转时间变为:
和同时到达的sjf模式一样,考虑到新的假设,STCF可以证明是最优的.考虑到所有工作同时到达,SJF是最优的.所以可以看到,stcf的最优性是符合直觉的.
结束!
-
处理机调度(FCFS、优先级法、最短作业优先法),求平均周转时间例题
2021-12-16 16:29:02衡量调度策略的最常用的几个指标是:周转时间、吞吐率、响应时间以及设备利用率等。 周转时间是指将一个作业提交给计算机系统后到该作业的结果返回给用户所需要的时间。 吞吐率是指在给定的时间内,一个计算机系统所...在多道程序设计系统中,内存中有多道程序运行,他们相互争夺处理机这一重要的资源。
处理机调度就是从就绪队列中,按照一定的算法选择一个进程并将处理机分配给它运行,以实现进程并发地执行。一、衡量调度策略的指标
衡量调度策略的最常用的几个指标是:周转时间、吞吐率、响应时间以及设备利用率等。
周转时间是指将一个作业提交给计算机系统后到该作业的结果返回给用户所需要的时间。
吞吐率是指在给定的时间内,一个计算机系统所完成的总工作量。
响应时间则是指从用户向计算机发出一个命令到计算机把相应的执行结果返回给用户所需要的时间。
设备利用率主要指输入输出设备的使用情况。
进程调度性能的衡量方法可分为定性和定量两种。二、作业的状态及其转换
一个作业从提交给计算机系统到执行结束退出系统,一般都要经历提交、收容、执行和完成等4个状态。
处理机调度可以分为4级:(1)作业调度:又称高级调度。(2)交换调度:又称中级调度。(3) 进程调度:又称低级调度。(4) 线程调度。
三、作业调度性能衡量
周转时间 = 运行时间 + 等待时间 = 作业完成时刻 - 作业到达时刻 ;
等待时间 = 上一个的周转时间 - 距离上一个的到达时间 = 上一个的等待时间 + 上一个的运行时间 - 距离上一个的到达时间
带权周转时间 = 周转时间 / 服务时间(运行时间);
平均周转时间 = 作业周转总时间 / 作业个数;
平均带权周转时间 = 带权周转总时间 / 作业个数;
特别注意:作业到达时间不是作业进内存的时间,而是发出请求,提交就开始计时,如果无法安排进内存,那么就等待,等待的这部分时间也要计数。
任务同时到达时:
四、调度算法
1、先来先服务(FCFS)调度算法
2、轮转法(round robin)
轮转法的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成比。轮转法的基本概念是将CPU的处理时间分成固定大小的时间片。如果一个进程在被调度选中之后用完了系统规定的时间片,但未完成要求的任务,则它自行释放自己所占有的CPU而排到就绪队列的末尾,等待下一次调度。同时,进程调度程序又去调度当前就绪队列中的第一个进程或作业。
时间片长度的选择是根据系统对响应时间的要求R和就绪队列中所允许的最大进程数Nmax确定的。它可表示为: q=R/Nmax
UNIX系统中进程调度采用:多级反馈队列轮转法。
3、优先级法
系统或用户按某种原则为作业或进程指定一个优先级来表示该作业或进程所享有的调度优先权。
4、最短作业优先法(shortest job first)
最短作业优先法(SJF)就是选择那些估计需要执行时间最短的作业投入执行,为它们创建进程和分配资源。五、例题
(一)假设有4道作业,它们的提交时刻及执行时间由下表给出:
计算在单道程序环境下,采用先来先服务调度算法和最短作业优先调度算法时的平均周转时间和平均带权周转时间,并指出它们的调度顺序。答:(1)先来先服务调度顺序如下:
平均周转时间:T=(2+2.7+2.8+3)/4=2.625
平均带权周转时间:W=(2/2+2.7/1+2.8/0.5+3/0.3)/4=4.825
(2)最短作业优先调度顺序如下:
(二)有5个任务A,B,C,D,E,它们几乎同时到达,预计它们的运行时间为10min,6min,2min,4min,8min。其优先级分别为3,5,2,1和4,这里5为最高优先级。对于下列每一种调度算法,计算其平均进程周转时间(进程切换开销可不考虑)。
(1)先来先服务(按A,B,C,D,E)算法。
(2)优先级调度算法。
(3)短作业调度算法。
-
操作系统-几种作业调度算法的平均带权周转时间的计算
2021-04-13 12:24:25用目录中的四种调度算法分别求出相对应的平均带权周转时间 先用通俗的语言描述一下周转时间,用这道题目做例子,AAA到达时间为0,服务时间为3,如果系统立刻处理AAA,那么它的周转时间就是3−0=33-0=33−0=3,当然... -
平均周转时间,平均等待时间
2018-07-17 22:10:46现有4个同时到达的作业J1,J2,J3和J4,它们的执行时间分别是1小时,3小时,5小时,7小时,系统按单道方式运行且采用短作业优先算法,则平均周转时间是()小时 平均周转时间:周转时间总时间/总的作业个数: 周转时间:... -
C++实现CPU调度算法先来先服务(FCFS),非抢占最短作业优先调度(SJF),优先级调度,时间片轮转调度(RR)...
2021-06-06 18:16:18• 输出:每个作业的编号、作业开始执行时间、作业结束时间以及该调度算法的平均等待时间、平均周转时间。 1. job.txt说明: 第一行:作业数 轮转片大小 第二行以后:作业编号 到达时间 执行时间 优先级 2. 输出说明... -
计算出平均周转时间和平均带权周转时间
2021-12-22 14:23:23计算出平均周转时间和平均带权周转时间 题目: 现在已知系统中有5个进程,其到达时间和要求服务时间如表所示: 进程次序: p1–p2–p3–p4–p5, 时间片大小: 4 到达时间: [0, 1, 2, 3, 4] 要求服务时间: [6, 3, 3, ... -
完成时间,周转时间,平均周转时间以及带权周转时间和平均带权周转时间
2017-06-21 13:33:43这里仅对先来先服务(FCFS)以及短作业优先(SJF)两种调度算法的相关计算做一个说明和比较 首先我们必须明确:FCFS和SJF两种调度算法,只有在... 平均周转时间=周转时间/进程数(除法运算) 平均带权周转时间=带权 -
多种调度算法的平均周转时间算例
2019-05-04 20:22:00周转时间=作业完成时刻—...平均周转时间=作业周转总时间/作业个数; 平均带权周转时间=带权周转总时间/作业个数; 有5个批处理的作业(A、B、C、D和E)几乎同时到达一个计算中心,估计的运行时间分别为2、4、6... -
FCFS计算周转时间、带权周转时间、平均周转时间和平均带权周转时间。
2020-06-07 10:45:23#include #include #include main() { char pn[10][10],t[10]; int arr[10],bur[10],... } printf("\n平均周转时间:%.2f",(float)tottat/n); printf("\n平均带权周转时间:%.2f",(float)totwt/n); getch(); return 0; } -
用C语言编程实现“先来先服务(FCFS)”算法模拟作业调度,输出平均周转时间、平均带权周转时间
2021-07-12 09:36:12** 用C语言编程实现“先来先服务(FCFS)”算法模拟作业调度,输出平均周转时间、平均带权周转时间** 要求:按作业的到达顺序输入各作业需要的运行时间,按算法调度输出平均周转时间。 例如(FCFS),输入:8(到达时间... -
SPN计算周转时间,带权周转时间,平均周转时间,平均带权周转时间
2020-06-07 10:49:17} cout 平均周转时间:" ; cout 平均带权周转时间:" ; } void JCB::makeJCB(int x) { if(x == 0) { bubbleSort1(x,length); startTime[x] = arriveTime[x]; makeTime(x); } else { int count = getCount(x); if... -
操作系统(七)| 作业调度算法【平均周转时间、平均带权周转时间、先来先服务FCFS、短作业优先SJF、高优先...
2022-04-15 20:17:00周转时间 = 进程完成时间 - 进程到达时间 平均周转时间 = 周转时间之和 / 进程个数 带权周转时间 = 周转时间 / 进程实际运行时间 平均带权周转时间 = 带权周转时间之和 / 进程个数 FSFS 平均周转时间 = [(4-0)+(7... -
周转时间, 平均周转时间, 带权周转时间
2021-06-22 16:36:19周转时间(作业周转时间)指的是从作业被提交给系统开始, 到作业完成为止的这段时间 周转时间包括四部分: 作业在外存后备队列上等待作业调度的时间 进程在就绪队列上等待进程调度的时间 进程在cpu上执行的时间 进程... -
周转时间,平均周转时间,带权周转时间
2016-11-17 14:07:27周转时间,平均周转时间,带权周转时间@(OS)这三个概念需要特别理解清楚。周转时间=作业完成时间−作业提交时间周转时间 = 作业完成时间 - 作业提交时间特别注意作业提交时间不是作业进内存的时间,而是发出请求,... -
关于【完成时间、周转时间、平均周转时间、带权周转时间和平均带权周转时间】的公式和计算
2020-07-02 16:17:26本文介绍了计算“完成时间、周转时间、平均周转时间、带权周转时间和平均带权周转时间”的公式,并且用先来先服务(FCFS)、短作业优先(SJF)两种调度算法来分析一个例题。 -
平均周转时间和平均带权周转时间怎么算?
2020-06-03 20:17:57说明分别使用FCFS、RR(时间片=1)、SJF、非剥夺式优先级调度算法以及多级队列反馈算法(第i级队列的时间片=2i-1)时,这些作业的执行情况(优先级的高低顺序依次为1到5),针对以上每种调度算法... -
操作系统进程完成时间,周转时间,带权周转时间, 平均周转时间, 带权平均周转时间计算
2020-03-27 15:17:55计算规则 周转时间=作业完成时刻-作业到达时刻; 带权周转时间=周转时间/服务时间; 平均周转时间=作业周转总时间/作业个数; 平均带权周转时间=带权周转总时间/作业个数; ... -
2.2.2操作系统(CPU利用率 系统吞吐量 周转时间 调度算法 FCFS SJF HRRN)
2022-04-10 21:04:293.周转时间 4.等待时间 5.响应时间 调度算法 1.先来先服务(FCFS, First Come First Serve) 2.短作业优先(SJF, Shortest Job First) 非抢占式 抢占式 注意几个小细节: 对FCFS和SJF两种算法的思考… ... -
进程平均周转时间
2018-04-18 10:43:14设一个系统中有5个进程,它们的到达时间和...忽略I/O以及其他开销时间,若分别按先来先服务(FCFS)进行CPU调度,其平均周转时间为_______解析:平均周转时间表示,所有进程完成任务所花的所有时间除以进程的个数A:... -
周转时间和带权周转时间的计算
2020-06-20 11:35:30试计算以下三种作业调度算法的平均周转时间T和平均带权周转时间W。 作业 提交时间 运行时间 1 6.0 1.5 2 7.0 1.0 3 7.5 0.5 4 7.6 0.1 (1)先来先服务调度算法。 (2)短... -
SJF调度算法(操作系统)短作业优先和最短剩余时间优先
2020-08-12 15:01:41SJF短作业优先算法 -
最短剩余时间调度算法_LRTF:最长剩余时间优先调度算法
2020-06-25 14:00:51最短剩余时间调度算法LRTF, which stands for Longest Remaining Time First is a scheduling Algorithm used by the operating system to schedule the incoming processes so that they can be executed in a ... -
时间片轮转法:平均周转时间
2018-06-06 15:03:31时间片轮转法(RR)算法描述:用于分时系统中的进程调度。每次调度时,总是选择就绪队列的队首进程,让其在CPU上运行一个系统预先设置好的时间片。一个时间片内没有完成运行的进程,返回到绪队列末尾重新排队,等待... -
操作系统基础:调度算法的评价指标(CPU利用率、系统吞吐量、周转时间、等待时间、响应时间)
2022-04-18 21:42:361 知识总览 2 CPU利用率 3 系统吞吐量 4 周转时间 5 等待时间 6 响应时间 7 知识回顾 -
先来先服务算法、运行时间最短者优先算法和最高响应比优先调度算法_几种CPU调度策略...
2020-11-21 12:12:24下图中,进程1因为阻塞放弃CPU资源,此时,进程2刚IO操作结束,可以获得CPU资源去被调度,进程3的时间片轮转结束,也同样可以获得CPU资源去被调度,那么,此时的操作系统应该安排哪个进程去获得CPU资源呢?...