1、作业一：作业管理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
2、 秒（按 BCA 顺序执行） ，示意图如下：时间（秒）90输入计算输出输入计算输出输入计算输出程序 C程序 B21 35程序 A0 7065 85注：按 ABC 执行需 117s，按 ACB 执行需 126s，按 BAC 执行需 112s，按 BCA 执行需90s，按 CAB 执行 114s，按 CBA 执行需 99s。作业二：进程管理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,
3、y) W(r)2、 设有 k 个进程共享一临界区，对于下述情况，请说明信号量的初值、含义，并用 P，V操作写出有关互斥算法。（1） 一次只允许一个进程进入临界区；（2） 一次允许 m（mV(s)信号量 s 的变化范围为-(k-1) ,-1,0,1。其中，s=1 表示有 1 个空闲且可用的临界资源，且没有进程进入类名为 s 的临界区；s=0 表示有 1 个进程在临界区中（该临界资源已被某进程占用） ，但无等待使用该临界资源的进程；s=-n(1nk-1，n 为整数) 表示有 1 个进程在临界区中，且有 n 个进程等待使用该临界资源。（2）一次允许 m（mV(s)信号量 s 的变化范围为-(k-m)
4、 ,-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）何时会发生死锁
5、？（2）请提出一种可预防死锁发生的简单方法。北2、 某超市市场科容纳 100 人同时购物，入口处备有篮子，每个购物者可取 1 只篮子入内购物，出口处结账并归还篮子（出、入口仅容 1 人通过） 。请试用 P，V 操作及信号量写出如下情况的购物同步算法：（1）1 个出入口，且一次只允许 1 人通过；（2）1 个入口，n 个出口（n1 且为整数） 。3、设有无穷多个缓冲区和无穷多个信息，甲进程把信息逐个写入每个缓冲区，乙进程则逐个地从缓冲区中取出信息。试问：（1）两个进程间的制约关系；（2）用 P，V 操作写出两个进程的同步算法，并给出信号量的初值；（3）指出信号量的值的变化范围及取值的含义。作业三
6、解答过程：1、 （1）何时会发生死锁？北（2）请提出一种可预防死锁发生的简单方法北方向方向方向方向路口S1路口S2路口S3路口S4设 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 为正整数） 。2、 （1）1 个出入口，且一次只允许 1 人通过：设超市容量信号量为
7、 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
8、）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=0i=i+1V（S）乙进程：j=0j=j+1P（S）（3）信号量 S 的变化范围为-1,+ 中的整数，当 S=-1 时表示缓冲区从未被写入信息或缓冲区信息被乙进程读空，且乙进程要求进一步读缓冲区
9、中的信息，即乙进程超前甲进程欲读取缓冲区的信息而受阻。作业四：作业、进程调度1、下面哪几种调度算法适合于作业调度，哪些适合进程调度？（1）先来先服务（2）轮转法（3）短作业优先（4）优先级高者优先（5）长作业优先2、作业调度算法选择作业的原则可以是保证系统吞吐量大、对用户公平合理或者充分发挥系统资源的利用率。下表给出了 3 种简单的作业调度算法： 调度算法 吞吐量大 公平合理 发挥资源利用率先来先服务最短作业优先最高相应比优先（1）请指出每种算法主要是体现了上述哪种原则。 （在对应的行列上打上记号）（2）如果在实际系统中只采用上述 3 种简单算法的任一种，都只能体现其中一种原则而其它原则得不到
10、反映。为此，给出下列能反映多种原则的调度算法，并假定完全根据优先数从高到低顺序挑选作业，作业优先数按下述公式计算：R(优先数)=(作业等待时间) 2+1/(作业要求运行时间)请问这种算法反映了上述原则中的哪些原则？并简述理由。3、假设有 4 道作业，它们的提交时刻及运行时间由下表给出：作业号 提交时刻/小时 执行时间/小时1 10.00 22 10.20 13 10.40 0.54 10.50 0.3计算在单道程序环境下，采用先来先服务调度算法、最短作业优先调度算法和最高响应比优先调度算法时的平均周转时间和平均带权周转时间，并指出他们的调度顺序。作业四解答过程：1、适用于作业调度用的算法：（1
11、） （3） （4） （5） ，适用于进程调度用的算法：（1） （2）（4） 。2、 （1）调度算法 吞吐量大 公平合理 发挥资源利用率先来先服务 最短作业优先 最高相应比优先 （2）该算法体现了先来先服务原则和最短作业优先原则。理由如下：体现先来先服务原则：假若两作业运行时间相同，但到达时间不同，早到达的作业等待时间长，根据公式计算，它的优先数大，则优先调度。体现最短作业优先原则：假若两道作业同时到达，但运行时间不等，根据公式计算，运行时间短的作业其优先数高，因而优先调度。3、 （1）先来先服务（FCFS）调度：调度顺序为 1234。作业号 到达时间 结束时间 周转时间 带权周转时间1 10.
12、00 12.00 2 1.002 10.20 13.00 2.8 2.803 10.40 13.50 3.1 6.204 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 14 10.50 12.30 1.80 63 10.40 12.80 2.40 4.82 10.20 13.80 3.60 3.6平均周转时间 T=(2+1.8+
13、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.83 1.60 0.5 4.24 1.50 0.3 62 2.1 1 3.13 1.9 0.5 4.8作业号 到达时间 结束时间 周转时间 带权周转时间1 10.0
14、0 12.00 2 14 10.50 12.30 1.80 63 10.40 12.80 2.40 4.82 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 ）页
15、面淘汰算法求出缺页率 f，并画出图表表示之；（ 3）按最近最久未使用（LRU）页面置换算法求出缺页率 f，并画出图表表示之。2、有系统其主存容量为 1024K（字节） ，有 6 个作业同时到达，各作业要求主存量和运行时间如下表所示。假定系统初启时，将主存 1024K 按作业的编号顺序分给各道作业，并假定是多 CPU 下，分配到主存的作业都可以立即运行。请问：（1）1 秒后，主存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？（2）2 秒后，主存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？（3）在（2）后，此时有一个作业 7 要求进入主存，它需要主存量为 30K，按上述两种算法应把那一块空白区分给它，并画出分配后的链接情况。作业编号 需主存量（K） 运行时间（s）1 200 22 120 13 100 34 50 15 80 36 320 2
