操作系统解答题练习

问答题练习 1、（3分）请列出操作系统所具有的功能中的三个功能。 参考：处理机管理，内存管理，设备管理，文件管理，用户界面 2、（3分）请列出用户界面的三个形式。 参考答案：命令界面，程序界面和图形界面 1、设进程的到达时间和完成进程所需的运行时间（服务时间）如上所示。请用短进程非抢占式调度算法计算各进程的开始运行时间、结束运行时间，周转时间、和等待时间，并计算平均周转时间。 参考答案： 进程 到达 时间 服务 时间 开始 时间 结束 时间 周转 时间 等待 时间 A 0 100 0 100 100 0 B 1 10 101 111 110 100 C 2 100 111 211 209 109 D 3 1 100 101 98 97 平均周转时间T=129.25               2、（3分）处理机调度算法的效果可以用周转时间和带权周转时间来度量。请说明这两者有什么异同？ 参考答案：两者都是从作业提交到完成的时间来度量算法的优劣。但后者考虑作业的等待时间对于作业本身的服务时间的相对影响因素，因此当作业的差异性很大时，评价更客观些。 3.在单道批处理系统中，下列三个作业采用先来先服务的调度算法和最高响应比优先算法进行调度，哪一种调度算法的性能较好？请完成下表。 作业 提交时刻 运行时刻 开始时刻 完成时刻 周转时间/min 带权周转时间 1 10:00 2:00         2 10:10 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 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       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个作业，其提交时刻和估计运行时间为下表所示： 作业 提交时刻 估计运行时间/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: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 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 12:00 50 平均作业周转时间T=88.3min           1、（2分）生产者消费者的互斥同步问题叙述如下： 生产者生产产品，放入有n个缓冲区的缓冲池中，每个缓冲区只能放一个产品。消费者从缓冲池中取产品消费，不允许从空缓冲区中取产品。有多个生产者进程与多个消费者进程并发进行，任何时刻只允许一个进程访问缓冲池。生产者进程和消费者进程分别从缓冲池中的同一位置开始，顺序循环地使用缓冲池，放产品或取产品。当缓冲池的n个缓冲区都满时，生产者进程必须在缓冲池外等待。当缓冲池的n个缓冲区都空时，消费者进程必须在缓冲池外等待。 使用记录型信号量对生产者消费者问题的解答如下： 设置整型量n，设定缓冲池（临界资源）中的缓冲区总数 设置互斥信号量mutex，初值1，记录对缓冲池的互斥访问 设置信号量empty，初值n，记录缓冲池中空缓冲区数 设置信号量full，初值0，记录缓冲池中满缓冲区数 生产者和消费者的并发程序如上面的流程图所示。 请回答下面的问题 （1）、（1分）如果将生产者进程中的两个P操作语句（S2和S3）的执行次序反过来，可能会造成死锁。试其原因，发生死锁时缓冲池中的缓冲区有几个是满的？ 参考答案：n个 （2）、（1分）如果将消费者进程中的两个P操作语句（X1和X2）的执行次序反过来，可能会造成死锁。试分析其原因，发生死锁时缓冲池中的缓冲区有几个是满的？ 参考答案：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资源的数量为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，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     | 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 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    |  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 存在安全序列 （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 |  A  B  C  D    |  A B C D    |  A B C D    |  A  B  C  D    | P0         |  1  1  0  0      |  0 0  0 0    |  0 0  1 2    |  1  1  1  2    |  true P1        |  1  1  0  2      |  1 0  0 2    |  1 7  5 0    |  2  8  6  2    |  true P2        |  2  8  6  2      |  0 0  2 0    |  0 6  3 2    |  2  14  9  4    |  true P3        |  2  14  9  4      |  0 6  4 6    |  0 0  1 4    |  2  14  10  4    |  true P4        |  2  14 10  8    |  0 3  3 0    |  1 4  2 0    |  3  8  12  8    |  true 存在安全系列（P0,P2,P3,P4,P1），因此可满足需求，可分配所需要资源。 1、（1分） 给定段表如下： 段号  |    段基地址    |    段长 0        |    210            |    500 1        |    2350          |    20 2        |    100            |    90 3        |    1350          |    590 4        |    1938          |    95 试求分段地址(3, 500)所对应的物理地址？  参考答案：1850 2、（1分）在分页式存储管理中，快表被用来提高访问内存中的数据的存取速度。假定查找快表需要10ns，访问内存一次需要100ns，如果采用二级页表结构，而快表的命中率是60%，问对于内存数据的平均存取时间是多少? 参考答案：0.6*(10+100) + 0.4*(10+300) = 190 4、（1分）设有一分页管理系统，管理总共16个存储块，每个页面大小为1024，问物理地址至少应有多少位？ 参考答案：16个存储块的块号最多需要4位，每块有1024个存储单元，即所需的地址数需要10位，所以物理地址总长为14位。 5、（1分）设有一分页管理系统，能够管理的逻辑地址空间最多可有16个页面，每个页面大小为1024，问逻辑地址至少应有多少位？ 参考答案：页号占4位，页面占10位，逻辑地址至少要有14位。 6、（1分）假定地址长度为16位，页面大小为1024。问二进制分页地址(1000 10, 1000 1000)的二进制逻辑地址的表示 参考答案：1000  1010001000 7、（1分）假定地址长度为16位，页面大小为1024。问二进制逻辑地址(0001 0001 0001 0001)的二进制分页地址的表示 参考答案：0100  010******* 8、（1分）在一个段式存储管理系统中，其段表为： 段号      内存起始地址      段长 0          210            500 1          2350            20 2          100            90 3          1350            590 4          1938            95 试求表中逻辑地址（0,430）（2,120）对应的物理地址是什么？ 参考答案：逻辑地址（0，430）表示段号为2，即段首地址为210，对应的物理地址为：210+430=640 逻辑地址（2，120）因为段内地址120>段长90，所为该段为非法段，越界。 10、（5分）请求分页存储管理中，假定系统为某进程分配了3个物理块，开始时3个物理块都为空，进程运行时的页面走向为：7, 0, 1, 0, 3, 0, 7, 0, 1, 4, 6, 3, 6, 0, 1, 3, 6, 1, 3, 2。如果使用先进先出置换算法，请问缺页率是多少？ 参考答案：75% 11、（5分）在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面访问顺序为4，3，2，1，4，3，5，4，3，2， 1，5，当分配给该作业的物理块数M为4时，试写出页面访问的过程，并计算访问中所发生的缺页次数和缺页率？ 参考答案：产生缺页次数8次，缺页率为8/12≈66.7% 12、（20分）对于如下的页面访问序列： 1 ， 2 ， 3 ， 4 ， 1 ， 2 ， 5 ， 1 ， 2 ， 3 ， 4 ， 5 当内存块数量分别为 3 和 4 时，试问：使用 FIFO 和LRU 置换算法产生的缺页中断次数和缺页中断率分别是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断） 参考答案： FIFO 淘汰算法： 页面 1 2 3 4 1 2 5 1 2 3 4 5 块1 1 1 1 4 4 4 5     5 5   块2   2 2 2 1 1 1     3 3   块3     3 3 3 2 2     2 4     缺 缺 缺 缺 缺 缺 缺     缺 缺                             内存块为 3 时，缺页中断（或称缺页次数、页面故障）为 9 缺页中断率为75%； 页面 1 2 3 4 1 2 5 1 2 3 4 5 块1 1 1 1 1     5 5 5 5 4 4 块2   2 2 2     2 1 1 1 1 5 块3     3 3     3 3 2 2 2 2 块4       4     4 4 4 3 3 3   缺 缺 缺 缺     缺 缺 缺 缺 缺 缺                           内存块为 4 时，缺页中断为 10 ，缺页中断率为83%。 LRU 淘汰算法： 页面 1 2 3 4 1 2 5 1 2 3 4 5 块1 1 1 1 4 4 4 5     3 3 3 块2   2 2 2 1 1 1     1 4 4 块3     3 3 3 2 2     2 2 5   缺 缺 缺 缺 缺 缺 缺     缺 缺 缺                           内存块为 3 时，缺页中断为 10 ，缺页中断率为83%； 页面 1 2 3 4 1 2 5 1 2 3 4 5 块1 1 1 1 1 1 1 1 1 1 1 1 5 块2   2 2 2 2 2 2 2 2 2 2 2 块3     3 3 3 3 5 5 5 5 4 4 块4       4 4 4 4 4 4 3 3 3   缺 缺 缺 缺     缺     缺 缺 缺                           内存块为 4 时，缺页中断为 8 缺页中断率为66.7%。 1. 假定磁盘有200个柱面，编号为0~199，当前存取臂的位置在143号柱面上并刚刚完成125号柱面的服务请求。如果请求队列的先后顺序是：86,147,91,177,94,150,102,175,130；试问：为了完成上述请求，下列算法存取臂所移动的总量是多少？并计算存取臂移动的顺序。（1）先来先服务算法FCFS；（2）最短查找时间优先算法SSTF；（3）扫描算法SCAN；（4）电梯调度算法。 参考答案： （1）先来先服务算法FCFS 为565 ，依次为143 -86 -147 -91 -177 -94 -150 -102 -175 -130 （2）最短查找时间优先算法SSTF 为162 ，依次为143 -147 -150 -130 -102 -94 -91 -86 -175 -177 （3）扫描算法SCAN 为169 ，依次为143 -147 -150 -175 -177 -199 -130 -102 -94 -91 -86 （4）电梯调度为125，依次为143 -147 -150 -175 -177 -130-102 -94 -91 -86