《2022年操作系统作业题及答案 .pdf》由会员分享，可在线阅读，更多相关《2022年操作系统作业题及答案 .pdf（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、操作系统 课程作业2013 年春：学号：专业：年级：学校：日期：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 23 页作业一：作业管理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、统，以单道方式处理一个作业流，作业流中有2 道作业， 共占用 CPU计算时间、输入卡片数和打印输出行数如下：作业号占用 CPU 计算时间输入卡片张数打印输出行数1 3 分钟100 张2000 行2 2 分钟200 张600 行其中，卡片输入机速度为1000 张/分钟，打印机输出速度为1000 行/分钟，试计算：（1）不采用spooling 技术，计算这两道作业的总运行时间从第1 道作业输入开始到最后一个作业输出完毕。（2）如采用 spooling 技术，计算这2 道作业的总运行时间不计读/写盘时间，并给出相应的示意图。精选学习资料 - - - - - - - - - 名师归纳总结 - - -
3、- - - -第 2 页，共 23 页作业二：进程管理1、 请写出两程序S1 和 S2 可并发执行的Bernstein 条件。2、 有以下 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 个长度相等的有界缓冲区组成，且每次传输数据长度等于有界缓冲区长度以及生产者和消费者可对缓冲区同时操作。重新描述发送过程
4、deposit(data)和接收过程remove(data)。12nP1P2PiPn.C1C2CiCk.有界缓冲区 m4、 设有 k 个进程共享一临界区，对于下述情况，请说明信号量的初值、含义，并用P，V操作写出有关互斥算法。（1）一次只允许一个进程进入临界区；（2）一次允许 mmk 个进程进入临界区。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 23 页作业三：进程管理1、 假假设一个街道交通如以下图所示，假设有一长度大于两个路口距离的车，可以从东南西北四个方向开来，问1何时会发生死锁？2请提出一种可预防死锁发生的简单方法。2、 某
5、超市市场科容纳100 人同时购物，入口处备有篮子，每个购物者可取1 只篮子入内购物，出口处结账并归还篮子出、入口仅容1 人通过。请试用 P，V 操作及信号量写出如下情况的购物同步算法：11 个出入口，且一次只允许1 人通过；2 1个入口， n 个出口 n1 且为整数。3、设有无穷多个缓冲区和无穷多个信息，甲进程把信息逐个写入每个缓冲区，乙进程则逐个地从缓冲区中取出信息。试问：1两个进程间的制约关系；2用 P，V 操作写出两个进程的同步算法，并给出信号量的初值；3指出信号量的值的变化范围及取值的含义。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4
6、 页，共 23 页作业四：作业、进程调度1、下面哪几种调度算法适合于作业调度，哪些适合进程调度？1先来先服务2轮转法 3短作业优先4优先级高者优先5长作业优先2、作业调度算法选择作业的原则可以是保证系统吞吐量大、对用户公平合理或者充分发挥系统资源的利用率。通常情况下， 采用简单算法只能表达其中一种原则而其它原则得不到反映。为此， 给出以下能反映多种原则的调度算法，并假定完全根据优先数从高到低顺序挑选作业，作业优先数按下述公式计算：R(优先数 )=(作业等待时间)2+1/(作业要求运行时间) 请问这种算法反映了上述原则中的哪些原则？并简述理由。3、假设有4 道作业，它们的提交时刻及运行时间由下表
7、给出：作业号提交时刻 /小时执行时间 /小时1 10.00 2 2 10.20 1 3 10.40 0.5 4 10.50 0.3 计算在单道程序环境下，采用先来先服务调度算法、最短作业优先调度算法和最高响应比优先调度算法时的平均周转时间和平均带权周转时间，并指出他们的调度顺序。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 23 页作业五：存储管理1、假定某页式虚拟系统中，页面大小为100 个单元，某作业占有实页面数为M=3 ，它的访问地址走向序列为75，175，66，267，32， 102，333，166，22，255，256数字为
8、虚存的逻辑地址 。 1请指出这些单元对应的页面访问顺序序列；2按先来先服务 FIFO页面淘汰算法求出缺页率f，并画出图表表示之； 3按最近最久未使用LRU页面置换算法求出缺页率f，并画出图表表示之。2、有系统其主存容量为1024K字节，有 6 个作业同时到达，各作业要求主存量和运行时间如下表所示。假定系统初启时，将主存1024K 按作业的编号顺序分给各道作业，并假定是多 CPU 下，分配到主存的作业都可以立即运行。请问：11 秒后，主存空白区按首次适应和最正确适应算法的链接方式链接，将如何链接？22 秒后，主存空白区按首次适应和最正确适应算法的链接方式链接，将如何链接？3在 2后，此时有一个作
9、业7 要求进入主存，它需要主存量为30K，按上述两种算法应把那一块空白区分给它，并画出分配后的链接情况。作业编号需主存量 K运行时间 s1 200 2 2 120 1 3 100 3 4 50 1 5 80 3 6 320 2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 23 页作业六：文件管理1、在 UNIX系统中，为使文件的索引表较小又能允许组织大文件，采用直接索引与多次间接索引多级索引方式，给出一个文件的所有磁盘的块号，如以下图。假设每个磁盘块大小为 1024 字节，并且每个间接块容纳256 个块号，试问：1如某进程要读取某文
10、件的字节偏移量为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 间接824 2、磁道 0-90 道的存取正在处理第55 道的服务请求，对于磁盘访问序列磁道号：22、77、 35、90、40、 83、66，试问对以下的磁盘I/O 请求调度算法而言，满足以上请求序列，磁头将如何移动， 移动距离为多少？假设每移动一个柱面需3ms， 计算总共
11、花费的寻道时间。1先来先服务算法FCFS2最短查找时间优先调度SSTF3扫描调度 SCAN 电梯调度算法4循环扫描 C-SCAN 算法3、如果磁道范围0-99，刚结束第50 道的服务请求，对于磁道序列70， 25，40，85，90，55，分别按第2 题 1-4四种磁道扫描方法，磁头将如何移动？精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 23 页作业一：作业管理3、 有三道程序A、B、C 在一个系统中运行，该系统有输入、输出设备各1 台。三道程序A、B、C 构成如下：A：输入 32 秒，计算8 秒，输出5 秒B：输入 21 秒，计算1
12、4 秒，输出 35 秒C：输入 12 秒，计算32 秒，输出 15 秒问： 1三道程序顺序执行的总时间是多少？2充分发挥各设备的效能，并行执行上述三道程序，最短需多少时间不计系统开销？并给出相应的示意图。4、 假设一个单CPU 系统，以单道方式处理一个作业流，作业流中有2 道作业， 共占用 CPU计算时间、输入卡片数和打印输出行数如下：作业号占用 CPU 计算时间输入卡片张数打印输出行数1 3 分钟100 张2000 行2 2 分钟200 张600 行其中，卡片输入机速度为1000 张/分钟，打印机输出速度为1000 行/分钟，试计算：（3）不采用spooling 技术，计算这两道作业的总运行
13、时间从第1 道作业输入开始到最后一个作业输出完毕。（4）如采用 spooling 技术，计算这2 道作业的总运行时间不计读/写盘时间，并给出相应的示意图。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 23 页作业一解答过程：1、 1三道程序顺序执行的总时间是：32+8+5+21+14+35+12+32+15=174秒。 2充分发挥各设备的效能，并行执行上述三道程序，最短需 90 秒 按 BCA 顺序执行，示意图如下：注：按 ABC 执行需 117s，按 ACB 执行需 126s，按 BAC 执行需 112s，按 BCA 执行需 90s
14、，按 CAB 执行114s，按 CBA 执行需 99s。2、 1不采用spooling 技术，计算这两道作业的总运行时间为：100/1000输入 +3执行 +2000/1000 输出 +200/1000+2+600/1000=7.9 分钟2采用 spooling 技术，这2 道作业的总运行时间为5.7 分钟。时间分输入计算输出输入计算输出程序 2 程序 1 0.1 3.1 5.1 5.7 时间分7.9 输入计算输出输入计算输出程序 2 程序 1 0.1 3.1 5.1 7.3 时间秒90 输入计算输出输入计算输出输入计算输出程序 C 程序 B 21 35 程序 A 0 70 65 85 0.2
15、 5.3 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 23 页作业二：进程管理5、 请写出两程序S1 和 S2 可并发执行的Bernstein 条件。6、 有以下 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) 7、 设在教材第62 页 3.6.4 节中所描述的生产者消费者问题中，其缓冲部分为m 个长度相等的有界缓冲区组成，且每
16、次传输数据长度等于有界缓冲区长度以及生产者和消费者可对缓冲区同时操作。重新描述发送过程deposit(data)和接收过程remove(data)。12nP1P2PiPn.C1C2CiCk.有界缓冲区 m8、 设有 k 个进程共享一临界区，对于下述情况，请说明信号量的初值、含义，并用P，V操作写出有关互斥算法。（1）一次只允许一个进程进入临界区；（2）一次允许 mmk 个进程进入临界区。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 23 页作业二解答过程：1、Bernstein 条件可并发执行的条件：设 R(Si)=a1,a2,am
17、 表示程序 Si 在执行期间所需要引用读变量的集合-读集W(Si)= b1,b2, ,bn表示程序 Si 在执行期间要改变写变量的集合-写集如果两个程序S1 和 S2 能同时满足下述条件，它们便能并发执行，否则不能R(S1)W(S2)= ，W(S1)R(S2)= ，W(S1)W(S2)= 也可以写成R(S1) W(S2)W(S1)R(S2)W(S1)W(S2)= 2、前趋图：3、设第 i 块缓冲区的公用信号量为bufi ，初值为1；生产者进程的私用信号量为produce，初值为m；消费者进程的私用信号量为consume，初值为0。发送过程 deposit(data)和接收过程remove(da
18、ta)描述如下：Deposit(data)：Begin P(produce) 选择一个空缓冲区i P(bufi) 送数据入缓冲区i V(consume) V(bufi) End Remove(data)：Begin P(consume) 选择一个满缓冲区i P(bufi) 取缓冲区i 中的数据V(produce) V(bufi) End 4、 1一次只允许一个进程进入临界区：设 s 为互斥信号量，初值为1，表示有1 个空闲且可用的共享临界资源对任一进程Pi1i k ：P(s) V(s) 信号量 s 的变化范围为-(k-1) , ,-1,0,1。 其中，s=1 表示有 1 个空闲且可用的临界资源
19、，且没有进程进入类名为s 的临界区； s=0表示有 1 个进程在临界区中该临界资源已被某进程占用，但无等待使用该临界资源的进程；s=-n(1n k-1 ，n 为整数 )表示有1 个进程在S4 S2 S1 S5 S3 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 23 页临界区中，且有n 个进程等待使用该临界资源。2一次允许mmk个进程进入临界区：设 s 为互斥信号量，初值为m，表示有m 个空闲且可用的共享临界资源，即可允许m个进程同时进入该临界区对任一进程Pi1i k ：P(s) V(s) 信号量 s 的变化范围为-(k-m) ,
20、,-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 个进程等待使用该临界资源。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 23 页作业三：进程管理
21、3、 假假设一个街道交通如以下图所示，假设有一长度大于两个路口距离的车，可以从东南西北四个方向开来，问1何时会发生死锁？2请提出一种可预防死锁发生的简单方法。./ 4、 某超市市场科容纳100 人同时购物，入口处备有篮子，每个购物者可取1 只篮子入内购物，出口处结账并归还篮子出、入口仅容1 人通过。请试用 P，V 操作及信号量写出如下情况的购物同步算法：11 个出入口，且一次只允许1 人通过；21 个入口， n 个出口 n1 且为整数。3、设有 无穷多个缓冲区和无穷多个信息，甲进程把信息逐个写入每个缓冲区，乙进程则逐个地从缓冲区中取出信息。试问：1两个进程间的制约关系；2用 P，V 操作写出两
22、个进程的同步算法，并给出信号量的初值；3指出信号量的值的变化范围及取值的含义。北精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 23 页作业三解答过程：1、 1何时会发生死锁？2请提出一种可预防死锁发生的简单方法设 4 个路口为4 个资源，其信号量分别设为S1，S2，S3 和 S4，初值均为1，代表资源空闲可用，下面用P， V 操作预防死锁问题：方向进程：PS1，S2 VS1， S2方向进程：PS2，S4 VS2，S4方向进程：PS3，S4 VS3，S4方向进程：PS1，S3 VS1， S3信号量 S1，S2，S3 和 S4 的变化范
23、围均为- ,-1,0,1 。其中， S1S4=1 表示有 1 个空闲且可用的临界资源，且没有进程进入类名为S1S4 的临界区； S1S4=0 表示有 1 个进程在临界区中， 目前无空闲且可用的临界资源，但无等待使用该临界资源的进程；S1S4=-mm为正整数 表示有 1个进程正在该临界区中，目前无空闲且可用的临界资源，且有 m 个进程等待使用该临界资源。北方向方向方向方向路口S1 路口S2 路口S3 路口S4 北精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 23 页2、 11 个出入口，且一次只允许1 人通过：设超市容量信号量为S，初
24、值为 100；购物进程为Pi，购物信号量为mutex，初值为1。购物进程 Pi 同步描述：PSPmutex V mutex Pmutex V mutexV S信号量 S 的变化范围为-m,-1,0,1 ,100 (m 为正整数 )。其中， S=100 表示有 100 个空闲且可用的临界资源，且没有进程进入类名为S 的临界区； s=j(1j100，j 为整数 )表示有 100-j 个进程正在该临界区中，且仍有j 个空闲且可用的临界资源，但无等待使用该临界资源的进程； s=0 表示有 100 个进程在临界区中，目前无空闲且可用的临界资源，但无等待使用该临界资源的进程；s=-m (m 为正整数 )表
25、示有 100 个进程在临界区中，目前无空闲且可用的临界资源，且有m 个进程等待使用该临界资源；信号量mutex 的变化范围为-99 ,-1,0,1 。其中，21 个入口， n 个出口 n1 且为整数设购物进程为Pi,；超市容量信号量为S，初值为100；入口互斥信号量为mutex1，初值为 1；出口互斥信号量为mutex2，初值为 n。购物进程 Pi 同步描述：PSPmutex1 V mutex1 Pmutex2 V mutex2V S信号量 S 的变化范围为-m , ,-1,0,1 ,100 m 为正整数。 其中，；信号量 mutex1和 mutex2 的变化范围均为-99 ,-1,0,1 。
26、其中，3、 1两个进程间的制约关系：乙进程不能先于甲进程执行，而甲进程不受乙进程约束。 2设置 1 个信号量S，S表示甲进程写满的缓冲区的个数，S 初值为 0，表示缓冲区为空，则甲、乙两进程的同步算法描述为甲进程：i=0 i=i+1 VS乙进程：j=0 j=j+1 PS 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 23 页3信号量S 的变化范围为 -1, +中的整数，当S=-1 时表示缓冲区从未被写入信息或缓冲区信息被乙进程读空，且乙进程要求进一步读缓冲区中的信息，即乙进程超前甲进程欲读取缓冲区的信息而受阻。精选学习资料 - -
27、- - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 23 页作业四：作业、进程调度1、下面哪几种调度算法适合于作业调度，哪些适合进程调度？1先来先服务2轮转法 3短作业优先4优先级高者优先5长作业优先2、作业调度算法选择作业的原则可以是保证系统吞吐量大、对用户公平合理或者充分发挥系统资源的利用率。下表给出了3 种简单的作业调度算法：调度算法吞吐量大公平合理发挥资源利用率先来先服务最短作业优先？1请指出每种算法主要是表达了上述哪种原则。在对应的行列上打上记号2如果在实际系统中只采用上述3 种简单算法的任一种，都只能表达其中一种原则而其它原则得不到反映。为此， 给
28、出以下能反映多种原则的调度算法，并假定完全根据优先数从高到低顺序挑选作业，作业优先数按下述公式计算：R(优先数 )=(作业等待时间)2+1/(作业要求运行时间) 请问这种算法反映了上述原则中的哪些原则？并简述理由。3、假设有4 道作业，它们的提交时刻及运行时间由下表给出：作业号提交时刻 /小时执行时间 /小时1 10.00 2 2 10.20 1 3 10.40 0.5 4 10.50 0.3 计算在单道程序环境下，采用先来先服务调度算法、最短作业优先调度算法和最高响应比优先调度算法时的平均周转时间和平均带权周转时间，并指出他们的调度顺序。精选学习资料 - - - - - - - - - 名师
29、归纳总结 - - - - - - -第 17 页，共 23 页作业四解答过程：1、适用于作业调度用的算法：1 3 4 5 ，适用于进程调度用的算法：1 2 4 。2、 1调度算法吞吐量大公平合理发挥资源利用率先来先服务最短作业优先 2该算法表达了先来先服务原则和最短作业优先原则。理由如下：表达先来先服务原则：假假设两作业运行时间相同，但到达时间不同，早到达的作业等待时间长，根据公式计算，它的优先数大，则优先调度。表达最短作业优先原则：假假设两道作业同时到达，但运行时间不等，根据公式计算，运行时间短的作业其优先数高，因而优先调度。3、 1先来先服务FCFS调度：调度顺序为1 2 34。作业号到达
30、时间结束时间周转时间带权周转时间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
31、 平均周转时间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.
32、00 12.00 2 1 4 10.50 12.30 1.80 6 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 23 页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小时精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 23 页作业五：存储管理1、假定某页式虚拟系统中，页面大小为100 个单元，某作业占有实
33、页面数为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 下，分配到主存的作业都可以立即运行。请问：11 秒后，主存空白区按首次适应和最正确适应算法的
34、链接方式链接，将如何链接？22 秒后，主存空白区按首次适应和最正确适应算法的链接方式链接，将如何链接？3在 2后，此时有一个作业7 要求进入主存，它需要主存量为30K，按上述两种算法应把那一块空白区分给它，并画出分配后的链接情况。作业编号需主存量 K运行时间 s1 200 2 2 120 1 3 100 3 4 50 1 5 80 3 6 320 2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 23 页作业五解答过程：1、 1访问序列为0，1，0， 2，0，1，3，1，0，2， 2。2FIFO：页面0 1 0 2 0 1 3 1
35、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% 。3LRU ：页面0 1 0 2 0 1 3 1 0 2 2 1 0 1 0 2 0 1 3 1 0 2 2 2 0 1 0 2 0 1 3 1 0 0 3 1 1 2 0 0 3 1 1 缺页缺页率 f=5/11=45.45% 。2、 11 秒后，主存空白区按首次适应和最正确适应算法的链接方式：首次适应算法：120 50154 最正确适应算法：50120154 22 秒后，主存空白区的链接方式：首次适应算法：320
36、 50474 最正确适应算法：50320474 32 秒后，作业7 要求进入主存：首次适应算法：290 50474 最正确适应算法：20320474 200 120 100 50 80 320 154空闲精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 23 页作业六：文件管理1、在 UNIX系统中，为使文件的索引表较小又能允许组织大文件，采用直接索引与多次间接索引多级索引方式，给出一个文件的所有磁盘的块号，如以下图。假设每个磁盘块大小为 1024 字节，并且每个间接块容纳256 个块号，试问：1如某进程要读取某文件的字节偏移量为900
37、0 处的数据， 应如何找到它所在的磁盘块及块内位移量？2如想要存取350000 处，又将如何？直接 0 4096 直接 1 228 直接 2 45423 直接 3 401 直接 4 702 直接 5 11111 直接 6 10 直接 7 101 直接 8 367 直接 9 90 间接428 间接9156 间接824 2、磁道 0-90 道的存取正在处理第55 道的服务请求，对于磁盘访问序列磁道号：22、77、 35、90、40、 83、66，试问对以下的磁盘I/O 请求调度算法而言，满足以上请求序列，磁头将如何移动， 移动距离为多少？假设每移动一个柱面需3ms， 计算总共花费的寻道时间。1先来
38、先服务算法FCFS2最短查找时间优先调度SSTF3扫描调度 SCAN 电梯调度算法4循环扫描 C-SCAN 算法3、如果磁道范围0-99，刚结束第50 道的服务请求，对于磁道序列70， 25，40，85，90，55，分别按第2 题 1-4四种磁道扫描方法，磁头将如何移动？367 808 数据块331 3333 一次间址75 9156 331 二次间址0 3333 数据块816 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 23 页作业六解答过程：1、 1根据 9000/1024=8.8，故该字节在文件索引8从 0 开始计直接块中，于
39、是可从表目项中读出内容为367，即该字节在磁盘块号为367 的盘块中；再根据9000mod1024=808，查表在 367 号磁盘块的808 字节即为文件的9000 字节。 2350000/1024=341.8 ，则该字节在文件的逻辑块号为341 的块中，故可知它必在二次间接寻址中因为直接+1 次间接可寻256+10=266 块 。根据 (341-266)/256=75/256=0.29 整数部分为0 ，可知其在二次间接块中0 的表目上，又因为75mod256=75，可知在一次间接75 表目处，从题表中可分别读出表目项内容为331 和 3333，可知在磁盘块3333 中。由350000mod1
40、024=816，得出文件的350000 字节是 3333 磁盘块的816 字节。2、 1先来先服务算法FCFS ：访问序列552277359040 8366 总移动柱面距离为：33+55+42+55+50+43+17=295 ，总寻道时间为3ms*295=885ms 。 2最短查找时间优先调度SSTF ：根据各个I/O 请求的不同，总是为接近当前磁头位置的请求提供优先服务，也就是先执行查找时间最小的那个请求。由于查找时间正比于两个请求的柱面差值，所以磁头移动总是移到距当前最近的柱面上去。很明显，它比FCFS 改善了磁盘的服务。从本质上讲，它是 SJF短作业优先调度的形式。同样，可能导致某些请求
41、长期得不到服务被饿死当不断有I/O 请求时。访问序列 55667783 904035 22 总移动柱面距离为：11+11+6+7+50+5+13=103 ，总寻道时间为3ms*103=309ms 。3扫描调度SCAN ：由于 I/O 请求具有动态性质，所以可以采取扫描法。磁头从磁盘的一端出发，向另一端移动，扫过所有柱面，遇到请求就服务。直到移到另一端后，移动方向反过来，继续做下面的服务。访问序列 55667783 904035 22 总移动柱面距离为：11+11+6+7+50+5+13=103 ，总寻道时间为3ms*103=309ms 。4循环扫描 C-SCAN 算法：它是SCAN 扫描算法的变种，这是为了适应极大量存取请求而设计的。 磁头臂总是从0 号柱面至最大号柱面顺序扫描，到头后直接返回0 号柱面重复进行，就像是循环至0 号柱面一样也可视为单向扫描。在一个柱面上，磁头臂往往停留，待磁盘旋转一定圈数之后，再移向另一个柱面。为了在磁盘移动每一周时间内执行更多的存取，必须考虑旋转优化考虑等待时间与传送时间。访问序列 55667783 900 223540 总移动柱面距离为：11+11+6+7+90+22+13+5=165 ，总寻道时间为3ms*165=495ms 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 23 页