操作系统 多处理机习题

1. 有两个程序，程序 A 依次使用 CPU 计 10s，使用设备甲计 5s，使用 CPU 计 5s，使用设备乙计 10s，使用 CPU 计 10s。 程序 B 依次使用设备甲计 10s，使用 CPU 计 10s，使用设备乙计 5s，使用 CPU 计 5s，使用设备乙计 10s。在单道程序环境下先执行程序 A 再执行程序 B，计算 CPU 的利用率是多少？在多道程序环境下，CPU 的利用率是多少？解答：单道环境下，CPU 运行时间为（ 10+5+10）s+(10+5)s=40s,两个程序运行总时间为40s+40s=80s,故利用率是 40/80=50%多道环境下，运行情况如下图所示，CPU 运行时间为 40s，两个程序总时间为 45s，故利用率为 40/45=88.9%2. 设某计算机系统有一个 CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程 A 先得到 CPU 运行，进程 B 后运行。进程 A 的运行轨迹为：计算50ms，打印信息 100ms，再计算 50ms，打印信息 100ms，结束。进程 B 的运行轨迹为：计算 50ms，输入数据 80ms，再计算 100ms，结束。试画出它们的时序关系图（可以用甘特图） ，并说明：（1 ） 开始运行后，CPU 有无空闲等待？若有，在哪些时间内等待？计算 CPU 的利用率。（2 ） 进程 A 运行时有无等待现象？若有，在什么时候发生等待现象？（3 ） 进程 B 运行时有无等待现象？若有，在什么时候发生等待现象？进程运行情况如下：1）CPU 在 100-150ms 时间段内空闲，利用率为 250/300=83.3%2）进程 A 为无等待现象3）进程 B 为有等待现象，0-50ms ， 180-200ms3. 设内存中有 3 道程序 A、B、C，它们按 A、B、C 的优先次序执行。它们的计算和 I/O操作的时间见表 1-1。假设 3 道程序使用相同设备进行 I/O 操作，即程序以串行方式使用设备，试画出单道运行和多道运行的时间关系图（调度程序的执行时间忽略不计） 。在两种情况下，完成 3 道程序分别需要多长时间（多道运行时采用抢占式调度策略） 。表 1-1 程序执行情况程序操作 A B C计算 30 60 20I/O 操作 40 30 40计算 10 10 20单道批处理系统中，有四个作业，其有关情况如下表所示，在采用响应比高者优先调度算法时分别计算其平均周转时间 T 和平均带权周转时间 W。作业 J1 J2 J2 J3提交时间/h 8.0 8.6 8.8 9.0运行时间/h 2.0 0.6 0.2 0.5答：分析响应比高者优先调度算法是指每次调度作业运行时，先计算后备作业队列中每个作业的响应比，然后挑选响应比最高的投入运行。在第 8 小时，因为只有作业 J1 到达，系统先将作业 J1 投入运行。作业 J1 运行两个小时后完成。这时三个作业都已到达，要计算三个作业的响应比，然后使响应比最高的投入运行。三个作业的响应比为：作业 J2 的响应比=1+（10.0-8.6 ）/0.6=3.33作业 J3 的响应比=1+（10.0-8.8 ）/0.2=7作业 J4 的响应比=1+（10.0-9.0 ）/0.5=3从计算的结果来看，作业 J3 的响应比最高，所以让作业 J3 先执行，作业 J3 执行 0.2小时后完成，此时作业 J2 和作业 J4 的响应比为：作业 J2 的响应比=1+（10.2-8.6 ）/0.6=3.67作业 J3 的响应比=1+（10.2-9.0 ）/0.5=3.4从计算结果来看，作业 J2 的响应比最高，所以再让 J2 执行。可见，四个作业的执行次序为：作业 J1，作业 J3，作业 J2，作业 J4. 计算结果如下表：作业号 到达时间 运行时间 开始时间 完成时间 周转时间 带权周转时间1 8.0 2.0 8.0 10.0 2.0 1.02 8.6 0.6 10.2 10.8 2.2 3.673 8.8 0.2 10.0 10.2 1.4 74 9.0 0.5 10.8 11.3 2.3 4.6平均周转时间为：T=（2.0+2.2+1.4+2.3）/4=1.975平均带权周转时间为：W=（1.0+3.67+7+4.6 ） /4=3.98假定要在一台处理机上执行下列作业：作业 执行时间 优先级1 10 32 1 13 2 34 1 45 5 2且假定这些作业在时刻 0 以 1,2,3,4,5,的顺序到达。说明分别使用 FCFS、RR（时间片=1） 、SJF 以及非剥夺方式优先级调度算法时，这些作业的执行时间。针对上述每种调度算法，给出平均周转时间和平均带权周转时间。解答：时间类型 P1 P2 P3 P4 P5 平均时间算法运行时间 10 1 2 1 5 3.8周转时间 10 11 13 14 19 13.4FCFS加权周转时间 1 11 6.5 14 3.8 7.26周转时间 19 2 7 4 14 9.2RR加权周转时间 1.9 2 3.5 4 2.8 2.84周转时间 19 1 4 2 9 7SJF加权周转时间 1.9 1 2 2 1.8 1.74周转时间 16 1 18 19 6 12优先级加权周转时间 1.6 1 9 19 1.2 6.36所以，FCFS 的平均周转时间为 13.4，平均加权周转时间为 7.26RR 的平均周转时间为 9.2，平均加权周转时间为 2.84SJF 的平均周转时间为 7，平均加权周转时间为 1.74非剥夺式优先级调度算法的平均周转时间为 12，平均加权周转时间为 6.36结论：SJF 的平均周转时间肯定是最短的，计算完毕后可以利用这个性质检验。在一个单道批处理系统中，一组作业的提交时间和运行时间如下表所示：作业 提交时间 运行时间（小时）1 8:00 1.02 8:50 0.503 9:00 0.204 9:10 0.10试计算以下三种作业调度算法的平均周转时间 T 和平均带权周转时间 W：（1 ） 先来先服务（2 ） 短作业优先（3 ） 响应比高者优先解答FCFS 调度算法的作业调度情况见下表作业 提交时间 运行时间 开始时间 结束时间 周转时间 带权周转时间1 8.0 1.0 8.0 9.0 1.0 1.02 8.5 0.5 9.0 9.5 1.0 2.03 9.0 0.2 9.5 9.7 0.7 3.54 9.1 0.1 9.7 9.8 0.7 7.0平均周转时间 (1.0.70)/4.85T平均带权周转时间 (1.023.570)/43.5WSJF 调度算法的作业调度情况见下表：作业 提交时间 运行时间 开始时间 结束时间 周转时间 带权周转时间1 8.0 1.0 8.0 9.0 1.0 1.02 8.5 0.5 9.3 9.8 1.3 2.63 9.0 0.2 9.0 9.2 0.2 1.04 9.1 0.1 9.2 9.3 0.2 2.0平均周转时间 (1.03.20)/4.675T平均带权周转时间 611W响应比高者优先：8.0 时只有 1 号作业，所以肯定是 1 号得到 CPU，9.0 时 1 号作业执行完毕，2 号作业响应比为（9.0-8.5+0.5）/0.5=2， 3 号作业响应比为（9.0-9.0+0.2）/0.2=1, 2号的响应比大于 3 号，9.0 时调度 2 号作业，9.5 时 2 号作业执行完毕，此时 3 号作业响应比为（9.5-9.0+0.2 ）/0.2=3.5 ， 4 号作业响应比为（9.5-9.1+0.1）/0.1=5，4 号的响应比大于3 号，所以先调度 4 号作业。高响应比优先调度算法的作业调度情况见下表作业