1、问答题 练习 1、（ 3分）请列出操作系统所具有的功能中的三个功能。 参考答案：处理机管理，内存管理，设备管理，文件管理，用户界面 2、（ 3分）请列出用户界面的三个形式。 参考答案：命令界面，程序界面和图形界面 1、设进程的到达时间和完成进程所需的运行时间（服务时间）如上表所示。请用短进程非抢占式调度算法计算各进程的开始运行时间、结束运行时间，周转时间、和等待时间，并计算平均周转时间。 参考答案： 进程 到达 时间 服务 时间 开始 时间 结束 时间 周转 时间 等待 时间 A 0 100 0 100 100 0 B 1 10 101 111 110 100 C 2 100 111 211
2、209 109 D 3 1 100 101 98 97 平均周转时间 T=129.25 2、（ 3分）处理机调度算法的效果可以用周转时间和带权周转时间来度量。请说明这两者有什么异同？ 参考答案： 两者都是从作业提交到完成的时间来度量算法的优劣。但后者考虑作业的等待时间对于作业本身的服务时间的相对影响因素，因此当作业的差异性很大时，评价更客观些。 3.在单道批处理系统中，下列三个作业采用先来先服务的调度算法 和最高响应比优先算法进行调度，哪一种调度算法的性能较好？请完成下表。 作业 提交时刻 运行时刻 开始时刻 完成时刻 周转时间/min 带权周转时间 1 10:00 2:00 2 10:10
3、1:00 3 10:25 0:25 平均周转时间 T= 平均带权周转时间 W= 参考答案： 先来先服务调度算法： 作业 提交时刻 运行时刻 开始时刻 完成时刻 周转时间/min 带权周转时间 1 10:00 2:00 10:00 12:00 120 1 2 10:10 1:00 12:00 13:00 170 17/6 3 10:25 0:25 13:00 13:25 180 36/5 平均周转时间 T=156.67min 平均带权周转时间 W=3.68 最高响应比优先调度算法： 作业 提交时刻 运行时刻 开始时刻 完成时刻 周转时间/min 带权周转时间 1 10:00 2:00 10:00
4、 12:00 120 1 2 10:10 1:00 12:25 13:25 195 3.25 3 10:25 0:25 12:00 12:25 120 4.8 平均周转时间 T=145min 平均带权周转时间 W=3.02 综上所述，最高响应比调度算法性能较好。 4. 如果限制为两道的多道程序系统中，有 4 个作业进入系统，其进入系统时刻、估计运行时间为下图所示。系统采用 SJF作业调度算法，采用 SRTF进程调度算法，请填充下面表格。 作业 进入系统时刻 估计运行时 间 /min 开始运行时 刻 结束运行 时刻 周转时间 /min 1 10:00 30 2 10:05 20 3 10:10
5、5 4 10:20 10 平均周转时间 T= 平均带权周转时间 W= 参考答 案： 作业 进入系统时刻 估计运行时间 /min 进入内存时刻 开始运行时刻 结束运行时刻 周转时间 /min 1 10:00 30 10:00 10:00 11:05 65 2 10:05 20 10:05 10:05 10:25 20 3 10:10 5 10:25 10:25 10:30 20 4 10:20 10 10:30 10:30 10:40 20 平均周转时间 T=31.25min 平均带权周转时间 W=2.3 5. 有一个 4道作业的操作系统，若在一段时间内先后到达 6个作业，其提交时 刻和估计运行
6、时间为下表所示： 作业 提交时刻 估计运行时间 /min 1 8:00 60 2 8:20 35 3 8:25 20 4 8:30 25 5 8:35 5 6 8:40 10 系统采用剩余 SJF调度算法，作业被调度进入系统后中途不会退出，但作业运行时可被剩余时间更短的作业所抢占。 （ 1）分别给出 6 个作业的执行时间序列，即开始执行时间、作业完成时间、作业周转时间。 （ 2）计算平均作业周转时间。 参考答案： 作业 提交时 刻 估计运行时间/min 进入内存时刻 剩余时间/min 开始时间 完成时间 周转时间/min 1 8:00 60 8:00 40 8:00 10:35 155 2 8
7、:20 35 8:20 30 8:20 9:55 95 3 8:25 20 8:25 15 8:25 8:45 20 4 8:30 25 8:30 25 9:00 9:25 55 5 8:35 5 8:45 5 8:45 8:50 15 6 8:40 10 8:50 10 8:50 9:00 20 平均周转时间 T=60min 6. 有一个具有三道作业的多道批处理系统，作业调度采用短作业优先调 度算法，进程调度采用以优先数为基础的抢占式调度算法。在下表所示的作业序列中，作业优先数即为进程优先数，数越小则优先级越高。 作业 到达时刻 估计运行时间 /min 优先数 A 10:00 40 5 B
8、10:20 30 3 C 10:30 60 4 D 10:50 20 6 E 11:00 20 4 F 11:10 10 4 试填充下表： 作业 进入内存时刻 运行结束时刻 作业周转时间 /min A B C D E F 平均作业周转时间 T= 参 考答案： 作业 进入内存 时刻 开始运行 时刻 运行结束时刻 作业周转时 间 /min A 10:00 10:00 12:40 160 B 10:20 10:20 10:50 30 C 10:30 10:50 11:50 80 D 10:50 12:40 13:00 130 E 12:00 12:00 12:20 80 F 11:50 11:50
9、12:00 50 平均作业周转时间 T=88.3min 1、（ 2分）生产者消费者的互斥同步问题叙述如下： 生产者生产产品，放入有 n个缓冲区的缓冲池中，每 个缓冲区只能放一个产品。消费者从缓冲池中取产品消费，不允许从空缓冲区中取产品。有多个生产者进程与多个消费者进程并发进行，任何时刻只允许一个进程访问缓冲池。生产者进程和消费者进程分别从缓冲池中的同一位置开始，顺序循环地使用缓冲池，放产品或取产品。当缓冲池的n 个缓冲区都满时，生产者进程必须在缓冲池外等待。当缓冲池的 n个缓冲区都空时，消费者进程必须在缓冲池外等待。 使用记录型信号量对生产者消费者问题的解答如下： 设置整型量 n，设定缓冲池（
10、临界资源）中的缓冲区总数 设置互斥信号量 mutex，初值 1，记录对缓冲池 的互斥访问 设置信号量 empty，初值 n，记录缓冲池中空缓冲区数 设置信号量 full，初值 0，记录缓冲池中满缓冲区数 生产者和消费者的并发程序如上面的流程图所示。 请回答下面的问题 （ 1）、（ 1分）如果将生产者进程中的两个 P操作语句（ S2 和 S3）的执行次序反过来，可能会造成死锁。试分析其原因，发生死锁时缓冲池中的缓冲区有几个是满的？ 参考答案： n个 （ 2）、（ 1 分）如果将消费者进程中的两个 P 操作语句（ X1 和 X2）的执行次序反过来，可能会造成死锁。试分析其原因，发生死锁时缓冲池中的
11、缓冲区有几个是满 的？ 参考答案： 0个（或 n个全是空的） 2、（ 5分）设两个进程并发访问一个打印机分配表， A进程申请打印机，从打印机分配表读入状态字，进程 B 向打印机分配表写入状态字。这两个进程对打印机分配表的操作是互斥的，用 P/V操作表示进程 A和 B的操作过程。 参考答案： 设互斥信号量 S=1 进程 A ： 进程 B： P(S); P(S); 读入打印机分 配表； 修改打印机分配表； V（ S）； V（ S）； 1、（ 8分）设系统中有三种类型的资源（ A， B， C）和五个进程（ P1，P2， P3， P4， P5）， A 资源的数量 17， B 资源的数量为 5， C 资
12、源的数量为 20。在 T0时刻系统状态如表所示。系统采用银行家算法来避免死锁。 请回答下列问题： （ 1） T0 时刻是否为安全状态？若是，请给出安全序列。 （ 2）若进程 P4请求资源（ 2， 0， 1），能否实现资源分配？为什么？ （ 3）在（ 2）的基础上，若进程 P1 请求资源（ 0， 2， 0），能否实现资源分配？ 参考答案： （ 1） T0 时刻为安全状态。其中的一个安全序列为（ P4， P5， P3，P2， P1） （其他可能的安全序列有：（ P4， P5， X， X， X），（ P4，P2， X， X， X）， （ P4， P3， X， X， X），（ P5， X， X， X，
13、 X） （ 2）可以为 P4 分配资源，因为分配后的状态还是安全的，其安全序列的分析如下表： | Work | Need | Allocation | Work+Allocation | Finish | A B C | A B C | A B C | A B C P4 | 0 3 2 | 0 2 0 | 4 0 5 | 4 3 7 | True P5 | 4 3 7 | 1 1 0 | 3 1 4 | 7 4 11 | True P1 | 7 4 11 | 3 4 7 | 2 1 2 | 9 5 13 | True P2 | 9 5 13 | 1 3 4 | 4 0 2 | 13 5 15
14、| True P3 | 13 5 15 | 0 0 6 | 4 0 5 | 17 5 20 | True （ 3） 进程 P1再请求资源 （ 0， 2， 0）， 则不能为之分配资源。 2、（ 15分）考虑一个系统在某个时刻的状态如表所示。 应用银行家算法回答下列问题： （ 1）填写 Need矩阵的内容 （ 2）系统是否处于安全状态？ （ 3）如果进程 P1发出请求（ 0， 4， 2， 0），这个请求能否被满足？ 参考答案： （ 1） 根据银行家算法 ， 可列出 Need矩阵如下表 ： 进程 | Need | Allocation | Max | Available | A B C D | A
15、B C D | A B C D | A B C D P0 | 0 0 0 0 | 0 0 1 2 | 0 0 1 2 | 1 5 2 0 P1 | 0 7 5 0 | 1 0 0 0 | 1 7 5 0 | P2 | 1 0 0 2 | 1 3 5 4 | 2 3 5 6 | P3 | 0 0 2 0 | 0 6 3 2 | 0 6 5 2 | P4 | 0 6 4 6 | 0 0 1 4 | 0 6 5 6 | （ 2） 利用安全性算法 ， 列出下表 ： 进程 | Work | Need | Allocation | Work+Allocation | Finish | A B C D |
16、A B C D | A B C D | A B C D | P0 | 1 5 2 0 | 0 0 0 0 | 0 0 1 2 | 1 5 3 2 | true P1 | 1 5 3 2 | 1 0 0 2 | 1 7 5 0 | 2 12 8 2 | true P2 | 2 12 8 2 | 0 0 2 0 | 0 6 3 2 | 2 18 11 4 | true P3 | 2 18 11 4 | 0 6 4 6 | 0 0 1 4 | 2 18 12 8 | true P4 | 2 18 12 8 | 0 7 5 0 | 1 0 0 0 | 3 18 12 8 | true 存在安全序列 （
17、 P0,P2,P3,P4,P1） 系统处于安全状态。 （ 3） 进程 P1发出请求 （ 0， 4， 2， 0）， 可进行分配 ， 结果得到如下表 ： 进程 | Need | Allocation | Max | Available | A B C D | A B C D | A B C D | A B C D P0 | 0 0 0 0 | 0 0 1 2 | 0 0 1 2 | 1 1 0 0 P1 | 0 3 3 0 | 1 4 2 0 | 1 7 5 0 | P2 | 1 0 0 2 | 1 3 5 4 | 2 3 5 6 | P3 | 0 0 2 0 | 0 6 3 2 | 0 6 5 2 | P4 | 0 6 4 6 | 0 0 1 4 | 0 6 5 6 | 用安全性算法检查 ， 列出 进程 | Work | Need | Allocation | Work+Allocation | Finish
