操作系统作业题(含答案)(20220114175722).pdf

作业一：作业管理1、 有三道程序A、B、C 在一个系统中运行，该系统有输入、输出设备各1 台三道程序A、B、C 构成如下：A：输入 32 秒，计算8 秒，输出5 秒B：输入 21 秒，计算14 秒，输出 35 秒C：输入 12 秒，计算32 秒，输出 15 秒问： （1）三道程序顺序执行的总时间是多少？（2）充分发挥各设备的效能，并行执行上述三道程序，最短需多少时间（不计系统开销）？并给出相应的示意图作业一解答过程：1、 （ 1）三道程序顺序执行的总时间是：32+8+5+21+14+35+12+32+15=174秒 2）充分发挥各设备的效能，并行执行上述三道程序，最短需 90 秒 （按 BCA 顺序执行），示意图如下：注：按 ABC 执行需 117s，按 ACB 执行需 126s，按 BAC 执行需 112s，按 BCA 执行需 90s，按 CAB 执行114s，按 CBA 执行需 99s时间（秒）90 输入计算输出输入计算输出输入计算输出程序 C 程序 B 21 35 程序 A 0 70 65 85 作业二：进程管理1、 有以下 5 条语句，请画出这5 条语句的前趋图 （PPT 第 3 章）S1： y=x+1 R(x) W(y) S2： c=f-w R(f,w) W(c) S3： d=r-y R(r,y) W(d) S4： x=a+b R(a,b) W(x) S5： r=c+y R(c,y) W(r) 2、 设有 k 个进程共享一临界区，对于下述情况，请说明信号量的初值、含义，并用P，V操作写出有关互斥算法。

1）一次只允许一个进程进入临界区；（2）一次允许 m（mk ）个进程进入临界区作业二解答过程：1、前趋图：2、 （ 1）一次只允许一个进程进入临界区：设 s 为互斥信号量，初值为1，表示有1 个空闲且可用的共享临界资源对任一进程Pi（1i k） ：P(s) V(s) 信号量 s 的变化范围为-(k-1) , ,-1,0,1 其中，s=1 表示有 1 个空闲且可用的临界资源，且没有进程进入类名为s 的临界区； s=0表示有 1 个进程在临界区中（该临界资源已被某进程占用），但无等待使用该临界资源的进程；s=-n(1n k-1 ，n 为整数 )表示有1 个进程在临界区中，且有n 个进程等待使用该临界资源2）一次允许m（mk）个进程进入临界区：设 s 为互斥信号量，初值为m，表示有m 个空闲且可用的共享临界资源，即可允许m个进程同时进入该临界区对任一进程Pi（1i k） ：P(s) S4 S2 S1 S5 S3 V(s) 信号量 s 的变化范围为-(k-m) , ,-1,0,1,m 其中，s= m 表示有 m 个空闲且可用的临界资源，且没有进程进入类名为s的临界区； s=j(1jm，j 为整数 )表示有 m-j 个进程正在该临界区中，且仍有j 个空闲且可用的临界资源，但无等待使用该临界资源的进程；s=0 表示有 m 个进程在临界区中，目前无空闲且可用的临界资源，但无等待使用该临界资源的进程；s=-n(1nk-m， n 为整数 )表示有 m 个进程在临界区中，目前无空闲且可用的临界资源，且有 n 个进程等待使用该临界资源。

作业三：进程管理1、 假若一个街道交通如下图所示，若有一长度大于两个路口距离的车，可以从东南西北四个方向开来，问（1）何时会发生死锁？（2）请提出一种可预防死锁发生的简单方法2、 某超市市场科容纳100 人同时购物，入口处备有篮子，每个购物者可取1 只篮子入内购物，出口处结账并归还篮子（出、入口仅容1 人通过）请试用 P，V 操作及信号量写出如下情况的购物同步算法：（1）1 个出入口，且一次只允许1 人通过；（2）1 个入口， n 个出口（ n1 且为整数）3、设有无穷多个缓冲区和无穷多个信息，甲进程把信息逐个写入每个缓冲区，乙进程则逐个地从缓冲区中取出信息试问：（1）两个进程间的制约关系；（2）用 P，V 操作写出两个进程的同步算法，并给出信号量的初值；（3）指出信号量的值的变化范围及取值的含义北作业三解答过程：1、 （ 1）何时会发生死锁？（2）请提出一种可预防死锁发生的简单方法设 4 个路口为4 个资源，其信号量分别设为S1，S2，S3 和 S4，初值均为1，代表资源空闲可用，下面用P， V 操作预防死锁问题：方向进程：P（S1，S2） V（S1， S2）方向进程：P（S2，S4） V（S2，S4）方向进程：P（S3，S4） V（S3，S4）方向进程：P（S1，S3） V（S1， S3）信号量 S1，S2，S3 和 S4 的变化范围均为-m , ,-1,0,1 （m 为正整数）。

北方向方向方向方向路口S1 路口S2 路口S3 路口S4 北2、 （ 1）1 个出入口，且一次只允许1 人通过：设超市容量信号量为S，初值为 100；购物进程为Pi，购物信号量为mutex，初值为1购物进程 Pi 同步描述：P（S）P（mutex） V（ mutex） P（mutex） V（ mutex）V（ S）信号量 S 的变化范围为-m , ,-1,0,1 ,100（ m 为正整数）；信号量 mutex 的变化范围为-99 ,-1,0,1 2）1 个入口， n 个出口（ n1 且为整数）设购物进程为Pi,；超市容量信号量为S，初值为100；入口互斥信号量为mutex1，初值为 1；出口互斥信号量为mutex2，初值为 1购物进程 Pi 同步描述：P（S）P（mutex1） V（ mutex1） P（mutex2） V（ mutex2）V（ S）信号量 S 的变化范围为-m , ,-1,0,1 ,100（m 为正整数）；信号量mutex1 和 mutex2的变化范围均为-99 ,-1,0,1 3、 （ 1）两个进程间的制约关系：乙进程不能先于甲进程执行，而甲进程不受乙进程约束 2）设置 1 个信号量S，S表示甲进程写满的缓冲区的个数，S 初值为 0，表示缓冲区为空，则甲、乙两进程的同步算法描述为甲进程：i=0 i=i+1 V（S）乙进程：j=0 j=j+1 P（S） （3）信号量S 的变化范围为 -1, +中的整数，当S=-1 时表示缓冲区从未被写入信息或缓冲区信息被乙进程读空，且乙进程要求进一步读缓冲区中的信息，即乙进程超前甲进程欲读取缓冲区的信息而受阻。

作业四：作业、进程调度1、下面哪几种调度算法适合于作业调度，哪些适合进程调度？（1）先来先服务（2）轮转法（ 3）短作业优先（4）优先级高者优先（5）长作业优先2、作业调度算法选择作业的原则可以是保证系统吞吐量大、对用户公平合理或者充分发挥系统资源的利用率下表给出了3 种简单的作业调度算法：调度算法吞吐量大公平合理发挥资源利用率先来先服务最短作业优先最高相应比优先（1）请指出每种算法主要是体现了上述哪种原则在对应的行列上打上记号）（2）如果在实际系统中只采用上述3 种简单算法的任一种，都只能体现其中一种原则而其它原则得不到反映为此， 给出下列能反映多种原则的调度算法，并假定完全根据优先数从高到低顺序挑选作业，作业优先数按下述公式计算：R(优先数 )=(作业等待时间)2+1/(作业要求运行时间) 请问这种算法反映了上述原则中的哪些原则？并简述理由3、假设有4 道作业，它们的提交时刻及运行时间由下表给出：作业号提交时刻 /小时执行时间 /小时1 10.00 2 2 10.20 1 3 10.40 0.5 4 10.50 0.3 计算在单道程序环境下，采用先来先服务调度算法、最短作业优先调度算法和最高响应比优先调度算法时的平均周转时间和平均带权周转时间，并指出他们的调度顺序。

作业四解答过程：1、适用于作业调度用的算法：（1） （3） （4） （5） ，适用于进程调度用的算法：（1） （2） （4） 2、 （ 1）调度算法吞吐量大公平合理发挥资源利用率先来先服务最短作业优先最高相应比优先（ 2）该算法体现了先来先服务原则和最短作业优先原则理由如下：体现先来先服务原则：假若两作业运行时间相同，但到达时间不同，早到达的作业等待时间长，根据公式计算，它的优先数大，则优先调度体现最短作业优先原则：假若两道作业同时到达，但运行时间不等，根据公式计算，运行时间短的作业其优先数高，因而优先调度3、 （ 1）先来先服务（FCFS）调度：调度顺序为1 2 34作业号到达时间结束时间周转时间带权周转时间1 10.00 12.00 2 1.00 2 10.20 13.00 2.8 2.80 3 10.40 13.50 3.1 6.20 4 10.50 13.80 3.3 11.00 平均周转时间T=(2+2.8+3.1+3.3)/4=2.8 小时平均带权周转时间W=(1+2.8+6.2+11)/4=5.25小时（ 2）最短作业优先（SJF）调度：调度顺序为1432作业号到达时间结束时间周转时间带权周转时间1 10.00 12.00 2 1 4 10.50 12.30 1.80 6 3 10.40 12.80 2.40 4.8 2 10.20 13.80 3.60 3.6 平均周转时间T=(2+1.8+2.4+3.6)/4=2.45小时平均带权周转时间W=(1+6+4.8+3.6)/4=3.85小时（ 3）最高响应比优先（HRN）调度：调度顺序为1432。

响应比 =(作业执行时间+作业等待时间)/作业执行时间从下表可见，在作业1 完成时刻（ 12.00） ，作业 2、3、4 的响应比最高的为4；在作业4 完成时刻（ 12.30） ，作业 2、3 的响应比最高的为3作业号等待时间执行时间响应比2 1.80 1 2.8 3 1.60 0.5 4.2 4 1.50 0.3 6 2 2.1 1 3.1 3 1.9 0.5 4.8 作业号到达时间结束时间周转时间带权周转时间1 10.00 12.00 2 1 4 10.50 12.30 1.80 6 3 10.40 12.80 2.40 4.8 2 10.20 13.80 3.60 3.6 平均周转时间T=(2+1.8+2.4+3.6)/4=2.45小时平均带权周转时间W=(1+6+4.8+3.6)/4=3.85小时作业五：存储管理1、假定某页式虚拟系统中，页面大小为100 个单元，某作业占有实页面数为M=3 ，它的访问地址（走向）序列为75，175，66，267，32， 102，333，166，22，255，256（数字为虚存的逻辑地址） （1）请指出这些单元对应的页面访问顺序序列；（2）按先来先服务 （ FIFO）页面淘汰算法求出缺页率f，并画出图表表示之； （ 3）按最近最久未使用（LRU）页面置换算法求出缺页率f，并画出图表表示之。

2、有系统其主存容量为1024K（字节），有 6 个作业同时到达，各作业要求主存量和运行时间如下表所示假定系统初启时，将主存1024K 按作业的编号顺序分给各道作业，并假定是多 CPU 下，分配到主存的作业都可以立即运行请问：（1）1 秒后，主存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？（2）2 秒后，主存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？（3）在（ 2）后，此时有一个作业7 要求进入主存，它需要主存量为30K，按上述两种算法应把那一块空白区分给它，并画出分配后的链接情况作业编号需主存量（ K）运行时间（ s）1 200 2 2 120 1 3 100 3 4 50 1 5 80 3 6 320 2 作业五解答过程：1、 （ 1）访问序列为0，1，0， 2，0，1，3，1，0，2， 22）FIFO：页面0 1 0 2 0 1 3 1 0 2 2 1 0 1 1 2 2 2 3 3 0 0 0 2 0 0 1 1 1 2 2 3 3 3 3 0 0 0 1 1 2 2 2 缺页缺页率 f=5/11=45.45% 3）LRU ：页面0 1 0 2 0 1 3 1 0 2 2 1 0 1 0。