2017-06-21 13:33:43 wzhedward 阅读数 9454

这里仅对先来先服务(FCFS)以及短作业优先(SJF)两种调度算法的相关计算做一个说明和比较

首先我们必须明确:FCFS和SJF两种调度算法,只有在进程的完成时间计算上有一些区别,其他时间(周转时间等)的计算都是相同的。 周转时间

周转时间=完成时间-到达时间
带权周转时间=周转时间/服务时间(除法运算)
平均周转时间=周转时间/进程数(除法运算)
平均带权周转时间=带权周转时间/进程数(除法运算)


1. FCFS的完成时间计算步骤:

step1:找出最先到达的进程(该进程的完成时间=到达时间+服务时间);

step2 : 根据给出的到达时间,找出下一个到达的进程(该进程的完成时间=上一进程的完成时间+该进程的服务时间);

step3 :重复step2直至完成所有进程的计算;

举个例子:

进程名 A B C D E
到达时间 0 1 3 4 6
服务时间 5 7 3 8 2
完成时间 5 12 15 23 25
step1. 根据例子中给出的进程到达时间,确定A进程是最先到达的。计算出进程A的完成时间为:A的到达时间+A的服务时间=5+0=5;

step2. 根据到达时间,确定下一到达进程为B。计算出进程B的完成时间为:进程A的完成时间+进程B服务时间=5+7=12;

step3. 重复step2。根据到达时间,确定下一到达进程为C。计算出C的完成时间为:进程B的完成时间+进程C的服务时间=12+3=15...依次类推计算D和E进程的完成时间

2. SJF的完成时间计算步骤:

step1:找出最先到达的进程(该进程的完成时间=到达时间+服务时间);

step2:根据上一进程的完成时间,找到在这个完成时间内所有到达的进程,并找到这些进程中服务时间最短的那个,然后计算它的完成时间(该进程的完成时间=上一进程的完成时间+该进程服务时间);

step3:重复step2,直至完成所有进程的计算。

还是上面的那个例子:

进程名 A B C D E
到达时间 0 1 3 4 6
服务时间 5 7 3 8 2
完成时间 5 17 8 25 10
step1. 根据例子中给出的进程到达时间,确定A进程是最先到达的。计算出进程A的完成时间为:A的到达时间+A的服务时间=5+0=5;

step2.根据上一进程A的完成时间5,可确定已经到达的进程为A、B、C、D(进程E的到达时间为6,所以时间为5时进程E还没到达);其中由于C的服务时间最短,所以下一进程确定为C,C的完成时间为:A的完成时间+C的服务时间=3+5=8;

step3. 重复step2。根据上一进程C的完成时间10,可确定,已经到达的进程有A、B、C、D、E;其中由于E的服务时间最短,所以下一进程确定为E,E的完成时间为:C的完成时间+E的服务时间=8+2=10...依次可计算出其他进程的完成时间。

以上就是两种调度算法下的完成时间具体计算步骤。

2016-08-30 22:33:47 lady_lili 阅读数 11881

关于平均周转时间的一些题目

 

(1)
设一个系统中有5个进程,它们的到达时间和服务时间如下,A的到达时间为0,服务时间为3;B的到达时间为2,服务时间为6;C的到达时间为4,服务时间为4;D的到达时间为6,服务时间为5;E的 到达时间为8,服务时间为2,忽略1/0以及其他开销时间,若分别按先来先服务(fFCFS)进行CPU调度,其平均周转时间为?

 

答:

周转时间=作业完成时间减去作业开始时间

所以

A 完成时间 0+3=3 周转时间A=3-0;

B 完成时间 3+6=9 周转时间B=9-2=7;

C 完成时间 9+4=13 周转时间C=13-4=9;

D 完成时间 13+5=18 周转时间D=18-6=12;

E 完成时间 18+2=20 周转时间 E=20-8=12;

所以平均周转时间是 (3+7+9+12+12)/5=8.

 

(2)

单道批处理系统有4个作业,J1 的提交时间为8 运行时间2 J2的提交时间8.6 运行时间0.6 J3的提交时间8.8 运行时间0.2 J4的提交时间9.0 运行时间0.5 在采用响应比优先调度算法时,其平均周转时间是?

 

响应比=(作业等待时间+作业执行时间)/ 作业执行时间

J1 周转时间(8+2) -8 =2

此时

J2等待时间为(8+2-8.6)=1.4 响应比为(1.4+0.6/0.6=10/3

J3 等待时机是(8+2-8.8)=1.2 响应比(1.2+0.2/0.2=7

J4 等待时间是(8+2-9.0)=1.0 响应比(1.0+0.5/0.5=3

因为J3的响应比最高,所以J3开始运行。J3 的完成时间是10+0.2=10.2周转时间是10.2-8.8=1.4

此时

J2的等待时间是10.2-8.6=1.6 响应比( 1.6+0.6)/0.6=11/3=3.6667

J4的等待时间是10.2-9.0=1.2 响应比(1.2+0.5/0.5=3.4

因为J2的响应比高,所以J2 开始运行,J2的完成时间是10.2+0.6=10.8;周转时间10.8-8.6=2.2

这时候运行J4,J4 的完成时间是10.8+0.5=11.3 周转时间是11.3-9.0=2.3

因此平均周转时间是(2+1.4+2.2+2.3 )/4=1.975

2019-11-11 17:02:16 qq_42192693 阅读数 62

一,周转时间类

周转时间

作业被提交给系统开始,到作业完成为止的这段时间间隔。

包括:

  1. 作业在外存后备队列上的等待作业调度的时间,
  2. 进程在就绪队列上等待进程调度的时间,
  3. 进程在CPU上执行的时间,
  4. 进程等待IO操作完成的时间

平均周转时间

多个作业的周转时间的平均值

带权周转时间

作业的周转时间与系统为它提供服务的时间之比

 平均带权周转时间

多个作业的带权周转时间的平均值

二,其他时间

到达时间:进程到达等待队列/CPU的时间

开始时间:进程进入CPU的时间

完成时间:进程出去CPU的时间

服务时间:进程在CPU中运行的时间

等待时间:进程在等待队列的时间

三,公式

周转时间=等待时间+服务时间=完成时间-到达时间

平均周转时间=各个作业周转时间之和/作业数

带权周转时间=周转时间/服务时间

平均带权周转时间=各个作业带权周转时间之和/作业数

四,例子

进程:

进程 到达时间 服务时间
A 8.0 2.0
B 8.5 0.5
C 9.0 0.1
D 9.5 0.2

运行:

次序 进程 到达时间 服务时间 等待时间 开始时间 完成时间 周转时间
1 A 8.0 2.0 0.0 8.0 10.0 2.0
2 B 8.5 0.5 1.5 10.0 10.5 2.0
3 C 9.0 0.1 1.5 10.5 10.6 1.6
4 D 9.5 0.2 1.1 10.6 10.8 1.3


 

 

 

 

 

 

 

 

 

2015-04-09 11:53:01 u010275850 阅读数 44922

周转时间=作业完成时刻—作业到达时刻;

带权周转时间=周转时间/服务时间;

平均周转时间=作业周转总时间/作业个数;

平均带权周转时间=带权周转总时间/作业个数;


例:

有4个进程A,B,C,D,设它们依次进入就绪队列,因相差时间很短可视为同时到达。4个进程按轮转法分别运行11,7,2,和4个时间单位,设时间片为1。四个进程的平均周转时间为 ?

解析:由于是视为同时到达,则到达时刻均为0;根据进程轮换法可知(时间片为1):


即A的周转时间为:24; B:20 C:7 D:14

A的带权周转时间为:24/11=2.18 B:20/7=2.86 C:7/2=3.5  D:14/4=3.5

则平均周转时间为:(24+20+7+14)/4=16.25

平均带权周转时间为:(2.18+2.86+3.5+3.5)/4=3.01


2014-09-10 12:58:54 ljthdu 阅读数 6583
1、吞吐率(单位时间执行命令的个数)
具体的原理就不讲解了,下面看一下有关这几方面的题目:
 2004年
若指令流水线把一条指令分为取指、分析和执行三部分,且三部分时间分别是2ns,2ns,1ns。则100条指令全部执行完毕需ns。
(4)A.163        B.183         C.193         D.203
试题解析:
(2*100)+3=203
答案:D

2005年
若每一条指令都可以分解为取指、分析和执行三步。已知取指时间=5△t,分析时间=2△t,执行时间=5△t。如果按执行、分析、取指重叠的流水线方式执行指令,从头到尾执行完500条指令需△t。
(5)A.2492   B.2500    C.2510     D.2515
试题解析:
    500*5+5+5=2510
答案:C


2009年
某指令流水线由5段组成,第1、3、5段所需时间为△t,第2、4段所需时间分别为3△t、2△t,那么连续输入n条指令时的吞吐率(单位时间内执行的指令个数)TP为。
(4)A. n/(5 *(3+2)△t 
     B. n/((3+3+2)△t + 3(n-1)△t
     C. n/((3+2)△t + (n-3)△t 
     D. n/((3+2)△t + 5*3△t
试题解析:
TP(吞吐率)=指令总数/执行这些指令所需要的总时间
执行这些指令所需要的总时间=(△t+3△t+△t+2△t+△t)+ 3(n-1)△t。
参考答案:B


希赛出的《网络工程师考试冲刺指南》上讲:
流水线的指令执行时间=一条指令的执行时间+(n-1)*最慢子任务的时间

2、平均周转时间和平均带权周转时间
作业i的周转时间Ti = 作业完成时间-作业提交时间,n个作业的平均周转时间为=(T0+T1+T2+...+Tn-1)/n
带权周转时间Wi = 周转时间/服务时间,n个作业的平均带权周转时间为(W0+W1+W2+...+Wn-1)/n
例:设有三道作业,它们的提交时间和运行时间见下表
作业号
提交时间/时
运行时间/h
1
10:00
2
2
10:10
1
3
10:25
0.25
注:为计算方便,“时”均为十进制。
试给出在下面两种调度算法下,作业的执行顺序、平均周转时间和带权周转时间
(1)先来先服务FCFS调度算法
(2)短作业优先SJF调度算法
[分析与解答](1)采用FCFS调度算法时,作业的执行顺序是作业1à作业2à作业3。由此可得到运行表见下。
作业号
提交时刻/时
运行时间/h
开始时刻/时
完成时刻/时
1
10:00
2
10:00
12:00
2
10:10
1
12:00
13:00
3
10:25
0.25
13:00
13:25
那么,平均周转时间为
T=(∑Ti)/3=[(12-10)+(13-10:10)+(13:25-10:25)]/3=[2+2.83+3]/3=2.61h
带权平均周转时间为
W=[∑(Ti/Tir)]/3=(2/2+2.83/1+3/0.25)/3=5.28h
(2)在SJF调度算法下,作业的执行顺序是作业1à作业3à作业2;由此得运行表见下。
作业号
提交时刻/时
运行时间/h
开始时刻/时
完成时刻/
1
10:00
2
10:00
12.00
2
10:10
1
12:25
13:25
3
10:25
0.25
12:00
12:25
那么,平均周转时间为
T=(∑Ti)/3=[(12-10)+(13:25-10:10)+(12:25-10:25)]/3=[2+3.25+2]/3=2.42h
带权平均周转时间为
W=[∑(Ti/Tir)]/3=(2/2+3.25/1+2/0.25)/3=4.08h

3、最高响应比优先
响应比(系数)=作业响应时间(等待+运行)/作业运行时间=1+作业等待时间/作业运行时间
例:在一个单道的程序设计系统中,有3个作业J1J2J3,它们到达输入井的时间分别为850900930,它们需要执行的时间分别为1.5小时、0.4小时、1小时。系统在1000按响应比高者优先算法对它们进行调度,请回答:

1)作业被选中执行的次序是什么?

     (2)三个作业被选中时的响应比分别是多少?
分析 响应比=作业周转时间/作业运行时间1+作业等待时间/作业运行时间

系统在1000,计算作业的响应比:

J1为例,它的作业计算时间是1.5小时,即90分钟;J1850到达输入井,在1000时刻,J1的等待时间为70分钟,因此作业J1的响应比为:170分钟/90分钟=1.77  

同理,J2160分钟/24分钟=3.5    J3130分钟/60分钟=1.5

因此按照响应比高者优先算法,优先调度J2

1024J2完成。这时计算J1J3的响应比:

J11+(7024)分钟/90分钟=2.04    J31+(3024)分钟/60分钟=1.9  

按照响应比高者优先算法,优先调度J1

1154J1完成,系统调度J3J3的响应比为1+(302490)分钟/60分钟=3.4 因此,作业被选中执行的次序是J2J1J3

三个作业被选中时的响应比分别是:J12.04J23.5J33.4

1)作业被选中执行的次序是J2J1J3

2)三个作业被选中时的响应比分别是:J11.04J22.5J32.4

周转时间的种种

阅读数 546

操作系统调度算法

阅读数 836

没有更多推荐了,返回首页