【操作系统之进程调度算法习题】

这篇具有很好参考价值的文章主要介绍了【操作系统之进程调度算法习题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1.第一题

在一个具有三道作业的批处理系统中，作业调度采用先来先服务(FCFS) 调度算法,进程调度采用
短作业优先调度算法。现有如下所示的作业序列,

【操作系统之进程调度算法习题】

注意
1.具有三道作业的批处理系统指的是内存最多能有3个作业;
2.表格样式是考试时候的格式，练习时候也按这个格式练习各作业的周转时间分别是:不需要写
单位p1__ p2__ p3__ p4__ p5___

解答：

周转时间 = 作业完成时间 - 进入系统时间(进入输入井时间)

作业	进入输入井时间	运行时间	进入内存时间	开始时间	完成时间	周转时间
P1	8:00	30	`8:00`	`8:00`	`8:30`	30
P2	8:10	15	`8:10`	`8:45`	`9:00`	50
P3	8:25	5	`8:25`	`8:30`	`8:35`	10
P4	8:30	20	`8:30`	`9:00`	`9:20`	50
P5	8:35	10	`8:35`	`8:35`	`8:45`	10

解析:

由题意可知: 进入到内存后，采用的是短作业优先调度算法，并且题目没说是抢占式（抢占式就是强行停止当前正在运行的作业，去运行刚刚进来的更短运行时间的作业）。

明白好前提条件后，我们开始模拟作业运行过程：

第一步：8:00这时只有P1在输入井当中，故此时运行P1，P1的开始时间就为8:00，因为P1需要完成30，故完成时间为8:30，得到P1的周转时间为：8:30 - 8:00 = 30。

第二步：在P1的运行过程中（8:00~8:30)之间，因为内存可以存放3个作业，P2和P3进入了输入井后直接进入了内存中等待P1运行完成。

第三步：当P1刚刚运行完成，P1退出内存，P4刚好进入内存，此时内存中有P2、P3以及P4，按照短作业优先调度算法，此时应该是P3开始运行，所以P3的开始时间为8:30，需要运行5，故完成时间为8:35，完成时间减去进入系统时间得到P3的周转时间为8:35 - 8:25 = 10。

第四步：当P3运行完成，P3退出内存，这时P5刚刚恰好进入内存，此时内存中有P2、P4以及P5，按照短作业优先调度算法，此时应该是P5开始运行，所以P5的开始时间为8:35，需要运行10，故完成时间为8:45，完成时间减去进入系统时间得到P5的周转时间为8:45 - 8:35 = 10。

第五步：当P5运行完成，P5退出内存，此时内存中还有P2、P4，按照短作业优先调度算法，此时应该是P2开始运行，所以P2的开始时间为8:45，需要运行15，故完成时间为9:00，完成时间减去进入系统时间得到P5的周转时间为9:00 - 8:10 = 50。

第六步：当P2运行完成，P2退出内存，此时内存中还有P4，此时P4开始运行，所以P4的开始时间为9:00，需要运行20，故完成时间为9:20，完成时间减去进入系统时间得到P4的周转时间为9:20 - 8:30 = 50。

注意：周转时间 = 完成时间 - 进入系统时间，而不是完成时间 - 进入内存时间！！！

2. 第二题

【操作系统之进程调度算法习题】

采用不抢占的高相应比优先调度算法进行调度，则各进程运行周转时间分别是：（不用单位）

p1__

p2__

p3__

p4__

p5__

解答：

响应比=作业周转时间/作业处理时间=（作业处理时间+作业等待时间）/作业处理时间=1+（作业等待时间/作业处理时间）

等待时间=最后一个的提交时间-该作业到达的时间
作业执行规则，响应比高的先执行
周转时间=完成时间-提交时间

0时刻只有P1，故先处理P1，因为是不抢占式，所以可以得出P1的周转时间：如下表格所示

进程	到达时刻	运行时间	等待时间	响应比	周转时间
P1	0	10	`0`	`1+(0/10)=1`	`10-0=10`
P2	1	1
P3	2	2
P4	3	1
P5	4	5

P1处理完成之后，已经到了10时刻，这时进程2、进程3、进程4已经进程5都已经到达。此时比较响应比来决定谁下一个运行。通过计算我们发现P2进程的响应比最高，故P2先运行，得到P2的周转时间

进程	到达时刻	运行时间	等待时间	响应比	完成时间	周转时间
P1	0	10	`0`	`1+(0/10)=1`	10	`10-0=10`
P2	1	1	`10-1=9`	`1+(9/1)=10`	11	`11-1=10`
P3	2	2	`10-2=8`	`1+(8/2)=5`
P4	3	1	`10-3=7`	`1+(7/1)=8`
P5	4	5	`10-4=6`	`1+(6/5)`

P2处理完成之后，已经到了11时刻。此时比较响应比来决定谁下一个运行。通过计算我们发现P4进程的响应比最高，故P4先运行，得到P4的周转时间

进程	到达时刻	运行时间	等待时间	响应比	完成时间	周转时间
P1	0	10	`0`	`1+(0/10)=1`	10	`10-0=10`
P2	1	1	`10-1=9`	`1+(9/1)=10`	11	`11-1=10`
P3	2	2	`10-2=8`	`1+(9/2)=5.5`
P4	3	1	`10-3=7`	`1+(8/1)=9`	12	`12-3=9`
P5	4	5	`10-4=6`	`1+(7/5)`

P4处理完成之后，已经到了12时刻。此时比较响应比来决定谁下一个运行。通过计算我们发现P3进程的响应比最高，故P3先运行，得到P3的周转时间

进程	到达时刻	运行时间	等待时间	响应比	完成时间	周转时间
P1	0	10	`0`	`1+(0/10)=1`	10	`10-0=10`
P2	1	1	`10-1=9`	`1+(9/1)=10`	11	`11-1=10`
P3	2	2	`10-2=8`	`1+(10/2)=6`	14	`14-2=12`
P4	3	1	`10-3=7`	`1+(8/1)=9`	12	`12-3=9`
P5	4	5	`10-4=6`	`1+(8/5)`

P3处理完成之后，只剩下P5进程了，故得到P5的周转时间

进程	到达时刻	运行时间	等待时间	响应比	完成时间	周转时间
P1	0	10	`0`	`1+(0/10)=1`	10	`10-0=10`
P2	1	1	`10-1=9`	`1+(9/1)=10`	11	`11-1=10`
P3	2	2	`10-2=8`	`1+(10/2)=6`	14	`14-2=12`
P4	3	1	`10-3=7`	`1+(8/1)=9`	12	`12-3=9`
P5	4	5	`10-4=6`	`1+(10/5)`	19	`19-4=15`

3. 第三题

3.某多道程序设计系统中配有一台处理器CPU和两台输人输出设备I01, I02, 现有三个进程P1、P2、
P3同时存在，它们使用资源的先后顺序和占用时间分别是:
进程P1: l02 (30ms) ，CPU (5ms) ，I01 (30ms) ，CPU (10ms)
进程P2: I01 (20ms) ，CPU (2ms) ，I02 (40ms) 。
进程P3: CPU (30ms) ，I01 (20ms)
假设I0设备是不可抢占的，进程调度采用”最短剩余时间优先”调度算法，且忽略调度等所需时间，
进程P1、P2、P3从开始到完成所用的时间分别是多少ms?不需要写单位ms

P1___

P2___

P3___