第三章处理机调度及答案.ppt

进程管理 进程管理 处理机调度作业 1、银行家算法 某系统有R1、R2和R3共3种资源，在T0时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况见表2.2，此刻系统的可用资源向量为（2, 1, 2），问题：(中科院软件所1999年试题) ①将系统中各种资源总数和此刻各进程对各资源的需求数目用向量或矩阵表示出来；②如果此时P1和P2均发出资源请求向量Request(1, 0, 1)，为了保持系统安全性，应该如何分配资源给这两个进程？说明你所采用策略的原因；③如果②中两个请求立刻得到满足后，系统此刻是否处于死锁状态？ 【解答】 ①系统资源总数向量为（9, 3, 6） 各进程对资源需求矩阵为： ②采用银行家算法进行计算分析可知： ②采用银行家算法进行计算分析可知： 系统可以满足P2进程对资源的请求，将资源分配给P2之后，至少可以找到一个安全的执行序列，如（P2, P1, P3, P4）使各进程正常运行终结。 系统不可以将资源分配给进程P1，虽然可利用资源还可以满足进程P1现在的需求，但是一旦分配给进程P1后，就找不到一个安全执行的序列保证各进程能够正常运行终结。所以进程P1应该进入阻塞状态。 ③系统满足进程P1和P2的请求后，并没有立即进入死锁状态，因为这时所有进程没有提出新的资源申请，全部进程均没有因资源没得到满足而进入阻塞状态。只有当进程提出资源申请且全部进程都进入阻塞状态时，系统才处于死锁状态。 2、调度算法 现有如下作业序列：作业1（提交时间8.00，运行时间1.00）；作业2（提交时间8.30，运行时间3.00）；作业3（提交时间9.00，运行时间0.10）；作业4（提交时间9.30，运行时间0.50）（单位：小时，以十进制计）。 　　试用先来先服务和短作业优先调度算法处理该作业序列，问哪种作业调度算法性能更好（要求给出计算的数据和必要的步骤）。(华中科技大学2001年试题) 先来先服务调度算法： 8.00作业1到达，开始运行；8.30作业1运行0.30小时；作业2到达，等待调入系统；9.00作业1运行1.00小时，运行结束；作业2较作业3先到达，开始运行；作业3到达；9.30作业2运行0.30小时，继续运行；作业3等待调入系统；作业4到达，等待调入系统；12.00作业2运行3小时，运行结束；作业3先到达，开始运行；作业4等待调入系统；12.10作业3运行0.10小时，运行结束；作业4开始运行；12.60作业4运行0.50小时，运行结束。 该调度算法下：平均周转时间 带权平均周转时间 短作业优先算法的运行情况见表: 该调度算法下：平均周转时间　　 带权平均周转时间 由以上两种算法下得到的结果来看，短作业优先算法优于先来先服务算法。 北京大学1995年试题 有一个具有两道作业的批处理系统，作业调度采用短作业的调度算法，进程调度采用以优先数为基础的抢占式调度算法，有如下表所示的作业序列（表中所列作业优先数为进程优先数，数值越小，优先级越高）。 （1）列出所有作业进入内存的时刻及结束时刻。 （2）计算平均周转时间 作业名 到达时刻 估计运行时间 优先数 A B C D 10：00 10：20 10：30 10：50 40 30 50 20 5 3 4 6 3、调度算法 解答： 10：00 A到达，无竞争，开始运行； 10：20 B到达，进入主存，优先数为3，优于A,B开始运行 10：30 C到达，不可进入； 10：50 B结束，同时D到达，同C争夺内存，D运行时间短，被调度进入内存；A的优先数高，开始运行； 11：10 A结束，C进入内存，C的优先数高于D,开始运行； 12：00 C结束, D开始运行； 12：20 D结束。 请同学们计算平均周转时间 平均周转时间=280/4=70分钟 作业名 到达时刻 估计运行时间 优先数 A B C D 10：00 10：20 10：30 10：50 40 30 50 20 5 3 4 6 4、调度算法 某多道程序设计系统配有一台处理器和两台外设IO1、IO2，现有3个优先级由高到低的作业J1、J2和J3都已装入了主存，它们使用资源的先后顺序和占用时间分别是：(南京大学1999年试题) J1: IO2(30ms), CPU(10ms), IO1(30ms), CPU(10ms). J2: IO1(20ms), CPU(20ms), IO2(40ms). J3: CPU(30ms), IO1(20ms). 处理器调度采用可抢占的优先数算法，忽略其他辅助操作时间，回答下列问题： （1）分别计算作业J1、J2和J3从开始到完成所用的时间。 （2）3个作业全部完成时CPU的利用率。 （3）3个作业全部完成时外设I01的利用率。 【分析】 如前说述，本题在多道系统中的三个