1、#*操作系统课程作业（2013 年春）姓名：学号：专业：年级：学校：日期：#*作业一：作业管理1、 有三道程序 A、B、C 在一个系统中运行，该系统有输入、输出设备各 1 台。三道程序A、B、C 构成如下：A：输入 32 秒，计算 8 秒，输出 5 秒B：输入 21 秒，计算 14 秒，输出 35 秒C：输入 12 秒，计算 32 秒，输出 15 秒问： （1）三道程序顺序执行的总时间是多少？（2）充分发挥各设备的效能，并行执行上述三道程序，最短需多少时间（不计系统开销）？并给出相应的示意图。2、 假设一个单 CPU 系统，以单道方式处理一个作业流，作业流中有 2 道作业，共占用CPU 计算时
2、间、输入卡片数和打印输出行数如下：作业号 占用 CPU 计算时间 输入卡片张数 打印输出行数1 3 分钟 100 张 2000 行2 2 分钟 200 张 600 行其中，卡片输入机速度为 1000 张/分钟，打印机输出速度为 1000 行/ 分钟，试计算：（1） 不采用 spooling 技术，计算这两道作业的总运行时间（从第 1 道作业输入开始到最后一个作业输出完毕） 。（2） 如采用 spooling 技术，计算这 2 道作业的总运行时间（不计读 /写盘时间） ，并给出相应的示意图。#*作业二：进程管理1、 请写出两程序 S1 和 S2 可并发执行的 Bernstein 条件。2、 有以
3、下 5 条语句，请画出这 5 条语句的前趋图。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)3、 设在教材第 62 页 3.6.4 节中所描述的生产者消费者问题中，其缓冲部分为 m 个长度相等的有界缓冲区组成，且每次传输数据长度等于有界缓冲区长度以及生产者和消费者可对缓冲区同时操作。重新描述发送过程 deposit(data)和接收过程 remove(data)。12 nP12Pin. C12Cik.有 界 缓 冲 区 m4、 设有 k 个进程共
4、享一临界区，对于下述情况，请说明信号量的初值、含义，并用 P，V操作写出有关互斥算法。（1） 一次只允许一个进程进入临界区；（2） 一次允许 m（mk）个进程进入临界区。#*作业三：进程管理1、 假若一个街道交通如下图所示，若有一长度大于两个路口距离的车，可以从东南西北四个方向开来，问（1）何时会发生死锁？（2）请提出一种可预防死锁发生的简单方法。2、 某超市市场科容纳 100 人同时购物，入口处备有篮子，每个购物者可取 1 只篮子入内购物，出口处结账并归还篮子（出、入口仅容 1 人通过） 。请试用 P，V 操作及信号量写出如下情况的购物同步算法：（1）1 个出入口，且一次只允许 1 人通过；
5、（2）1 个入口，n 个出口（n1 且为整数）。3、设有无穷多个缓冲区和无穷多个信息，甲进程把信息逐个写入每个缓冲区，乙进程则逐个地从缓冲区中取出信息。试问：（1）两个进程间的制约关系；（2）用 P，V 操作写出两个进程的同步算法，并给出信号量的初值；（3）指出信号量的值的变化范围及取值的含义。#*作业四：作业、进程调度1、下面哪几种调度算法适合于作业调度，哪些适合进程调度？（1）先来先服务（2）轮转法（3）短作业优先（4）优先级高者优先（5）长作业优先2、作业调度算法选择作业的原则可以是保证系统吞吐量大、对用户公平合理或者充分发挥系统资源的利用率。通常情况下，采用简单算法只能体现其中一种原则
6、而其它原则得不到反映。为此，给出下列能反映多种原则的调度算法，并假定完全根据优先数从高到低顺序挑选作业，作业优先数按下述公式计算：R(优先数)=(作业等待时间) 2+1/(作业要求运行时间)请问这种算法反映了上述原则中的哪些原则？并简述理由。3、假设有 4 道作业，它们的提交时刻及运行时间由下表给出：作业号 提交时刻/小时 执行时间/小时1 10.00 22 10.20 13 10.40 0.54 10.50 0.3计算在单道程序环境下，采用先来先服务调度算法、最短作业优先调度算法和最高响应比优先调度算法时的平均周转时间和平均带权周转时间，并指出他们的调度顺序。#*作业五：存储管理1、假定某页
7、式虚拟系统中，页面大小为 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 按作业的编号顺序分给各道作业，并假定是多 CP
8、U 下，分配到主存的作业都可以立即运行。请问：（1）1 秒后，主存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？（2）2 秒后，主存空白区按首次适应和最佳适应算法的链接方式链接，将如何链接？（3）在（2）后，此时有一个作业 7 要求进入主存，它需要主存量为 30K，按上述两种算法应把那一块空白区分给它，并画出分配后的链接情况。作业编号 需主存量（K） 运行时间（s）1 200 22 120 13 100 34 50 15 80 36 320 2#*作业六：文件管理1、在 UNIX 系统中，为使文件的索引表较小又能允许组织大文件，采用直接索引与多次间接索引（多级索引）方式，给出一个文
9、件的所有磁盘的块号，如下图。假设每个磁盘块大小为 1024 字节，并且每个间接块容纳 256 个块号，试问：（1）如某进程要读取某文件的字节偏移量为 9000 处的数据，应如何找到它所在的磁盘块及块内位移量？（2）如想要存取 350000 处，又将如何？直接 0 4096直接 1 228直接 2 45423直接 3 401直接 4 702直接 5 11111直接 6 10直接 7 101直接 8 367直接 9 90间接 428间接 9156间接 8242、磁道（0-90 道）的存取正在处理第 55 道的服务请求，对于磁盘访问序列（磁道号）：22、77、35、90、40、83、66，试问对以下
10、的磁盘 I/O 请求调度算法而言，满足以上请求序列，磁头将如何移动，移动距离为多少？若每移动一个柱面需 3ms，计算总共花费的寻道时间。（1）先来先服务算法（FCFS）（2）最短查找时间优先调度（SSTF）（3）扫描调度（SCAN） （电梯调度算法）（4）循环扫描（C-SCAN）算法3、如果磁道范围 0-99，刚结束第 50 道的服务请求，对于磁道序列70，25，40，85，90，55，分别按第 2 题（1）-（4）四种磁道扫描方法，磁头将如何移动？#*作业一：作业管理3、 有三道程序 A、B、C 在一个系统中运行，该系统有输入、输出设备各 1 台。三道程序A、B、C 构成如下：A：输入 32
11、 秒，计算 8 秒，输出 5 秒B：输入 21 秒，计算 14 秒，输出 35 秒C：输入 12 秒，计算 32 秒，输出 15 秒问： （1）三道程序顺序执行的总时间是多少？（2）充分发挥各设备的效能，并行执行上述三道程序，最短需多少时间（不计系统开销）？并给出相应的示意图。4、 假设一个单 CPU 系统，以单道方式处理一个作业流，作业流中有 2 道作业，共占用CPU 计算时间、输入卡片数和打印输出行数如下：作业号 占用 CPU 计算时间 输入卡片张数 打印输出行数1 3 分钟 100 张 2000 行2 2 分钟 200 张 600 行其中，卡片输入机速度为 1000 张/分钟，打印机输出
12、速度为 1000 行/ 分钟，试计算：（3） 不采用 spooling 技术，计算这两道作业的总运行时间（从第 1 道作业输入开始到最后一个作业输出完毕） 。（4） 如采用 spooling 技术，计算这 2 道作业的总运行时间（不计读 /写盘时间） ，并给出相应的示意图。#*作业一解答过程：1、 （1）三道程序顺序执行的总时间是：32+8+5+21+14+35+12+32+15=174 秒。（2）充分发挥各设备的效能，并行执行上述三道程序，最短需 90 秒（按 BCA 顺序执行） ，示意图如下：时间（秒）90输入计算输出输入计算输出输入计算输出程序 C程序 B21 35程序 A0 7065
13、85注：按 ABC 执行需 117s，按 ACB 执行需 126s，按 BAC 执行需 112s，按 BCA 执行需90s，按 CAB 执行 114s，按 CBA 执行需 99s。2、 （1）不采用 spooling 技术，计算这两道作业的总运行时间为：100/1000（输入）+3（执行） +2000/1000（输出）+200/1000+2+600/1000=7.9 分钟时间（分）7.9输入计算输出输入计算输出程序 2程序 10.1 3.1 5.1 7.3（2）采用 spooling 技术，这 2 道作业的总运行时间为 5.7 分钟。5.3#*时间（分）输入计算输出输入计算输出程序 2程序 10.1 3.1 5.1 5.70.2
