调度算法练习

1 假设一个系统中有5个进程，它们的到达时间和服务时间如下表所示，忽略I/O以及其他开销，若分别按先来先服务（FCFS）、非抢占式及抢占式的短进程优先（SPF）、高响应比优先、时间片轮转、多级反馈队列和立即抢占式多级反馈队列七种调度算法，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。

答：
2 在银行家算法中，若出现下列资源分配情况：
请问：
（1）此状态是否安全？
（2）若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？
答：（1）安全，因为存在安全序列{P0,P3,P4,P1,P2}（2）系统能分配资源，分析如下。

① Request(1,2,2,2) <= Need2(2,3,5,6);
② Request(1,2,2,2) <= Available2(1,3,5,4)改成
Available2(1,6,2,2)；
③系统先假定可为P2分配资源，并修改Available2，Allocation2和Need2向量，
由此形成的资源变化情况如下图所示：
④再利用安全性算法检查此时系统是否安全。

如下图
由此进行的安全性检查得知，可以找到一个安全序列{P2,P0,P1,P3,P4}。

作业调度之最短作业优先算法5例题解析例题一、某系统采用不能移动已在主存储器中作业的可变分区方式管理主存储器，现有供用户使用的主存空间100K,系统配有4台磁带机，有一批作业见下表：作业序号进输入井时间要求计算时间需要主存容量申请磁带机数110:0025分钟15K2台210:2030分钟60K1台310:3010分钟50K3台410:3520分钟10K2台510:4015分钟30K2台按计算时间最短者优先算法如下表：我的解释：系统首先装入1、2、4,但1结束时4沿未到达，因此先执行2;2执行完毕后，资源可以分配给3或5,考虑5的时间短优先分配5并执行，执行完5后，主存中只有4已就绪并等待执行，因此开始执行4,执行4的同时系统会将作业3装入主存，最后自然执行作业3;因此最后的顺序是：1\2\5\4\3作业序号进输入井时间进入主存时间开始计算时间结束计算时间周转时间解释110:0010:1010:00102525此时输入井中只有一个作业且满足资源要求，因此被选中运行。

2102010：2010：2510：5535作业2到达输入井，满足资源要求，装入主存，等到作业1运行完毕进入运行。

510:4010:5510:5511：1030由于作业3要求主存空间无法满足，因此作业4先行一步装入主存，当作业2让出处理器的同时，作业5满足资源要求进入主存就绪。

根据算法作业5先进入处理器运行最后作业3装入主存并运行平均周转时间：（25+35+30+55+70/5=43分钟 ［分析］解答本题时应注意如下几个问题：第一，系统采用的是多道程序设计技术，但没有限定并行工作的道数，因此， 只要当前尚未分配的资源可以满足在输入井中等待的某些作业的要求时，作业 调度可以按照给定的算法从中选择一个或多个作业装人主存储器；第二，采用可变分区方式管理主存储器，但没给出主存空间的分配算法，因而,只要有合适的空间就可分配，题中还规定可用移动技术来合并分散的空闲区； 第三，对磁带机采用静态分配；第四，进程调度采用可抢占的最高优先级调度算法，即对已被装人主存储器的作业而言优先级高的作业可抢占处理器执行；第五，虽然作业需要使用磁带机，但题意中已提示忽略磁带机和调度所花的时问，所以，解题时不必考虑外围设备的启动二八D 中断等复杂情况，只需把它们当作纯计算型的作业； 第六，由于没有规定什么时候开始进行作业调度，故在一般情况下只要输入井中有等待处理的作业就可按选定的算法去选择满足必要条件的作业。

1 假设一个系统中有5个进程，它们的到达时间和服务时间如下表所示，忽略I/O以及其他开销，若分别按先来先服务（FCFS）、非抢占式及抢占式的短进程优先（SPF）、高响应比优先、时间片轮转、多级反馈队列和立即抢占式多级反馈队列七种调度算法，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。

答：
2 在银行家算法中，若出现下列资源分配情况：
请问：
（1）此状态是否安全？
（2）若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？
答：（1）安全，因为存在安全序列{P0,P3,P4,P1,P2} （2）系统能分配资源，分析如下。

① Request(1,2,2,2) <= Need2(2,3,5,6);
② Request(1,2,2,2) <= Available2(1,3,5,4)改成
Available2(1,6,2,2)；
③系统先假定可为P2分配资源，并修改Available2，Allocation2和Need2向量，
由此形成的资源变化情况如下图所示：
④再利用安全性算法检查此时系统是否安全。

如下图
由此进行的安全性检查得知，可以找到一个安全序列{P2,P0,P1,P3,P4}。

00001) 先来先服务(FCFS)算法0000FCFS算法根据进程先后顺序进行调度，具有公平性。

0000图4-25 FCFS磁盘调度算法例，磁盘请求队列中的请求顺序分别为55、58、39、18、90、160、150、38、184，磁头初始位置是100磁道，釆用FCFS算法磁头的运动过程如图4-25所示。

磁头共移动了 (45+3+19+21+72+70+10+112+146)=498 个磁道，0000平均寻找长度=498/9=55.3。

00002) 最短寻找时间优先(Shortest Seek Time First, SSTF)算法0000SSTF算法选择与当前磁头所在磁道距离最近的磁道，0000图4-26 SSTF磁盘调度算法0000例如，磁盘请求队列中的请求顺序分别为55、58、39、18、90、160、150、38、184，磁头初始位置是100磁道，釆用SSTF算法磁头的运动过程如图4-26所示。

磁头共移动了 (10+32+3+16+1+20+132+10+24)=248 个磁道，0000平均寻找长度=248/9=27.5。

00003) 扫描(SCAN)算法（又称电梯算法上下或下上）0000SCAN算法选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象，0000图4-27 SCAN磁盘调度算法0000例如，磁盘请求队列中的请求顺序分别为55、58、39、18、90、160、150、38、184，磁头初始位置是100 磁道。

釆用SCAN算法时，要知道磁头的移动方向，假设磁头沿磁道号增大的顺序移动，则磁头的运动过程如图4-27所示。

磁头共移动了(50+10+24+94+32+3+16+1+20)=250 个磁道，0000平均寻找长度=250/9=27.8。

000004)循环扫描(Circulair SCAN, C-SCAN)算法（上上或下下）磁头移动只需要到达最远端的一个请求即可返回，不需要到达磁盘端点。

进程调度练习题第6章进程调度练习题一、单项选择题1、在分时操作系统中,进程调度经常采用(C )算法。

A 先来先服务B最高优先权C时间片轮转D随机2、（B）优先权是在创建进程时确定的，确定之后在整个进程运行期间不再改变A 先来先服务B 静态C 动态D 短作业3、以优先级为基础的进程调度算法可以保证在任何时候正在运行的进程总是非等待状态下诸进程中优先级最高的进程。

上述描述是（B）A 正确的B 错误的二、填空题1、进程调度方式通常有（非抢占式）和（抢占式）。

2、所谓进程调度就是从处于（就绪）状态的一些进程中按某种算法选择一个进程，使其占有CPU，使其该进程处于（执行）状态。

3、进程调度算法采用时间片轮转法，时间片过大，就会使轮转法转化为（FCFS）调度算法。

4、进程调度负责（处理机）的分配工作。

5、一种最常用的进程调度算法是把处理机分配给具有最高优先权的进程，而确定优先权的方法概括起来不外乎是基于（静态）特性和（动态）特性两种方法。

前者所得到的是（静态）优先权，后者所得到的是（动态）优先权。

6、在（先来先服务）调度算法中，按照进程进入就绪队列的先后次序来分配处理机。

三、概念的区别与联系1、作业调度与进程调度（1998西北大学考研试题）2、静态优先数与动态优先数。

（1998西北大学考研试题）四、解析题1、假设有一台计算机，它有1M内存，操作系统占有用200K，每个用户进程也占用200K，用户进程等待I/O的时间为80%，若增加1M内存，则CPU的利用率将提高多少？解：1M内存的情况：1）支持用户进程数：（1024K-200K）/200K=4.12 所以4个用户进程。

2）CPU利用率：先求CPU空闲（4个用户均处于等待I/O状态）概率P=（80%）4，然后再求CPU利用率1-P1-P =1-（80%）4 = 1-0.84=59%增加1M内存的情况：1）支持用户进程数：（2*1024K-200K）/200K=9.24 所以9个用户进程。

作业车间调度问题例题
例题:
假设有4个工作任务，每个任务需要的处理时间分别是4、2、3和1天。

每天最多只能处理一个任务。

如何安排任务的顺序，才能使得完成所有任务的总时间最短？
解答:
为了完成所有任务的总时间最短，我们可以采用贪心算法来解决这个问题。

首先，我们将任务按照处理时间从长到短排序，得到的顺序为4、3、2、1。

然后，我们依次安排每个任务。

由于每天最多只能处理一个任务，我们需要计算每个任务的开始时间。

首先，第一个任务的开始时间为0，完成时间为4。

然后，第二个任务可以在第一个任务完成后开始，所以它的开始时间为4，完成时间为7。

接着，第三个任务可以在第二个任务完成后开始，所以它的开始时间为7，完成时间为9。

最后，最后一个任务可以在第三个任务完成后开始，所以它的开始时间为9，完成时间为10。

综上所述，按照任务的顺序4、3、2、1来安排，完成所有任务的总时间最短为10天。

1、试证明，短作业优先的作业调度算法可以得到最短的平均响应时间。

2、设有4道作业，它们的提交时间及执行时间如表所示：
表作业的提交时间和执行时间
作业号提交时间执行时间
1 10 2.0
2 10.2 1.0
3 10.
4 0.5
4 10.
5 0.3
均周转时间和平均带权周转时间，并指出它们的调度顺序。

（时间单位：小时，以十进制进行计算）。

3、设有4个作业J1、J2、J3、J4，它们的到达时间和计算时间如表所示。

若这4个作业在一台处理机上按单道方式运行，采用响应比高者优先调度算法，试写出各作业的执行顺序、各作业的周转时间及平均周转时间。

4、书上(P115 )第21,22题。

例题1：假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间：应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间。

先来先服务算法计算结果：最短作业优先算法计算结果：最高响应比算法计算结果例题2：在两道环境下有四个作业, 已知它们进入系统的时间、估计运行时间，作业调度采用短作业优先算法，作业被调度运行后不再退出, 进程调度采用剩余时间最短的抢先调度算法（假设一个作业创建一个进程）。

请给出这四个作业的执行时间序列，并计算出平均周转时间及带权平均周转时间。

10：00，JOB1进入，只有一作业，JOB1被调入执行，10：05，JOB2到达，最多允许两作业同时进入，所以JOB2也被调入；内存中有两作业，哪一个执行？题目规定当一新作业运行后，可按作业运行时间长短调整执行次序；即基于优先数可抢占式调度策略，优先数是根据作业估计运行时间大小来决定的，由于JOB2运行时间（20分）比JOB1少（到10：05，JOB1还需25分钟），所以JOB2运行，而JOB1等待。

10：10，JOB3到达输入井，内存已有两作业，JOB3不能马上进入内存；10：20，JOB4也不能进入内存，10：25，JOB2运行结束，退出，内存中剩下JOB1，输入井中有两作业JOB3和JOB4，如何调度？作业调度算法：最短作业优先，因此JOB3进入内存，比较JOB1和JOB3运行时间，JOB3运行时间短，故JOB3运行，同样，JOB3退出后，下一个是JOB4，JOB4结束后，JOB1才能继续运行。

四个作业的执行时间序列为：JOB1：10：00—10：05，10：40—11：05 JOB2：10：05—10：25JOB3：10：25—10：30JOB4：10：30—10：40。

1【单选题】(B )有利于CPU繁忙的作业，而不利于I/O繁忙的作业。

• A 时间片轮转调度算法• B 先来先服务的调度算法• C 短作业优先算法• D 优先权调度算法解析：先来先服务(FCFS)调度算法是一种最简单的调度算法，当在作业调度中采用该算法时，每次调度是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。

FCFS调度算法比较有利于长作业，而不利于短作业。

所谓CPU繁忙型的作业，是指该类作业需要大量的CPU时间进行计算，而很少请求I/O操作。

I/O繁忙型的作业是指CPU处理时，需频繁的请求I/O操作。

2【单选题】假设有4个作业同时到达，每个作业的执行时间均为2h，他们在一台处理机上，按单道式运行，则，平均周转时间为（ B ）• A 1h• B 5h• C 2.5h• D 8h解析：4个作业，各执行时间分别是2h、4h、6h、8h，所以4个作业都完成的时间为2+4+6+8=20h。

此时，平均周转时间=各个作业完成时间之和/作业个数=20/4=5小时，完成时间不同；3【单选题】(D)优先级是在创建进程时确定，确定之后在整个运行期间不再改变。

• A 先来先服务• B 动态• C 短作业•D静态4【单选题】有三个作业J1、J2、J3 同时到达，它们的执行时间分别是T1，T2，T3，且T1<T2<T3。

系统按单道方式运行，采用短作业优先调度算法，则平均周转时间（）• A T1+T2+T3• B (3T1+2T2+T3)/3• C (T1+T2+T3)/3• D (T1+2T2+3T3)/3解析：按照短作业优先算法，执行顺序为J1、J2、J3，三个作业完成时间分别是T1、T1+T2、T1+T2+T3，所以平均周转时间是(T1+T1+T2+T1+T2+T3)/3。

5【单选题】有三个作业，运行时间分别是2h，5h，3h，假设它们同时到达，在一个CPU上按单道方式运行，则平均周转时间最小的执行顺序是（ D ）• A J1、J2、J3• B J3、J2、J1• C J2、J1、J3• D J1、J3、J2解析：在同一台处理器以单道方式运行，要想获得最短的平均周转时间，用短作业优先调度算法会有较好的效果。