操作系统原理期末考试试题B卷_2010_ - 参考答案.pdf

《操作系统原理期末考试试题B卷_2010_ - 参考答案.pdf》由会员分享，可在线阅读，更多相关《操作系统原理期末考试试题B卷_2010_ - 参考答案.pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第 1 页，共 18 页 南开大学信息技术科学学院本科生 2010-2011 年度第一学期操作系统原理课程期末试卷（B 卷）南开大学信息技术科学学院本科生 2010-2011 年度第一学期操作系统原理课程期末试卷（B 卷）专业年级姓名学号成绩 一、简答题（本题共一、简答题（本题共 30 分，每题分，每题 6 分，必做）分，必做）草稿区草稿区 1.为什么需要设计进程状态呢？请列出 2 组你了解的进程状态集，并简要描述状态转移过程。为什么需要设计进程状态：通过进程状态才能实现对进程的调度和管理（1 分）进程状态集 1：就绪状态、执行状态、堵塞状态 进程状态集 2：就绪状态、执行状态、堵塞状态、新

2、建、退出、挂起态 每个状态集 2.5 分，只要内容正确即可，如果回答有偏差，酌情扣分。得得 分分 执行状态 就绪状态 堵塞状态 挂起状态 执行状态 就绪状态 堵塞状态 第 2 页，共 18 页 2.何谓进程调度？请列出你所知道的四种进程调度方法。进程调度是指操作系统按某种策略或规则选择进程占用 CPU 进行运行的过程。调度方法包括非剥夺式的调度和可剥夺式的调度，在可剥夺式调度中有时间片轮转方法、优先级调度方法、彩票调度、多级队列调度方法。3.何谓虚拟存储管理？请列出至少三种虚拟存储管理技术？虚拟存储管理是指操作系统通过对内存资源的有效分配，实现较小的物理内存支持很大的程序运行，主要的虚拟存储管

3、理包括“覆盖块”思想、分页式管理、分段式管理和段页混合式管理。4.请简要说明 DMA 的三种工作模式，并解释在每种工作模式适合于什么样的数据传输应用？DMA 的三种模式是周期窃取式，突发模式和飞跃模式，其中周期窃取式适合于数据传输量较小、传输速度较慢的 I/O 设备，例如字符型设备，突发模式适合于数据传输量较大、传输速度较快的 I/O 设备，例如块型设备；飞跃模式适合不同 I/O 设备之间的数据通信与传输。5.请列出三种文件系统磁盘空间的分配形式，并简要分析其优缺点。优点 缺点 连续分配 1.实现简单。2.读取性能高。容易产生磁盘碎片 链表分配 能充分利用磁盘空间，可自由动态的实现文件内容的扩

4、展。1.随机读取性能较差。2.数据字节数不是 2 的整数次幂，降低系统的运行效率。索引表分配（I-Node）能高效的管理磁盘空间，支持复杂的文件系统 管理成本高，实现技术复杂 第 3 页，共 18 页 二、编程计算题（本题共二、编程计算题（本题共 5 小题，共计小题，共计 45 分，选做分，选做 4 题，多做不得分）题，多做不得分）草稿区草稿区 请在下面的表格中指定答题顺序，在对应的分值下列明题号。每格只许列出一个题号，否则做无效处理。请在下面的表格中指定答题顺序，在对应的分值下列明题号。每格只许列出一个题号，否则做无效处理。下表中必须写明所有题目的题号，如果填写不完全，视为不指定答题顺序。下

5、表中必须写明所有题目的题号，如果填写不完全，视为不指定答题顺序。如填写内容无效或者不填写表格，则按照默认的题面分值评分如填写内容无效或者不填写表格，则按照默认的题面分值评分 第一题（第一题（15 分）分）第二题（第二题（12 分）分）第三题（第三题（10 分）第四题（分）第四题（8 分）分）6.内存访问时间问题：考虑有这样一个分页系统，该系统在内存中存放了二级页表，页面大小为 4K，在 TLB 中存储了 最近访问的 16 个页表表项。如果内存访问需要 80ns，TLB 检查需要 20ns，页面交换（写/读磁盘）时间需要 5000ns。假设有 20%的被替换页面的内容被更改过，如果 TLB 命中

6、率是 95%，缺页率是 10%，请问 CPU 访问一个数据线需要 多长时间？（本题默认分值：（本题默认分值：12 分，列出计算公式与计算结果即可）分，列出计算公式与计算结果即可）计算公式，CPU 访问内存中数据的时间=niiPT1i；其中 i 是指各种内存访问情况，Ti是指在情况 i 下的访问时间，Pi是指发生该种情况的概率，题目中给出的各种百分比其实就是所谓的概率。1）第一种情况：TLB 检查（20ns）并命中（0.95 概率），直接访问内存中的页面（80ns），总时间是（20+80）*0.95=95ns 2）第二种情况：TLB 检查（20ns）未命中（0.05 概率），直接访问内存中的一级

7、页表（80ns），通过一级页表访问二级 页表（80ns），页面保存在内存中（0.90 概率，缺页率是 10%，则不缺页概率为 90%），直接访问内存中的页面（80ns）。该情况的总时间是（20+(80+80+80)*0.9）*0.05=11.8ns 3）第三种情况，TLB 检查（20ns）未命中（0.05 概率），直接访问内存中的一级页表（80ns），通过一级页表访问二级 页表（80ns），然后发生缺页中断（0.10 概率），被替换的页面无内容更改（0.80 概率，页面内容被更改的概率是 20%，则 页面内容无更改的概率是 80%），执行一次页面交换（5000ns），最后直接访问内存中的页面（

8、80ns）。得得 分分 第 4 页，共 18 页 该情况的总时间是（20+（80+80+5000*0.8+80）*0.1）*0.05=22.2ns 4）第四种情况，TLB 检查（20ns）未命中（0.05 概率），直接访问内存中的一级页表（80ns），通过一级页表访问二级 页表（80ns），然后发生缺页中断（0.10 概率），被替换的页面内容更改（页面内容被更改的概率是 20%），执行两次 页面交换（5000ns*2），最后直接访问内存中的页面（80ns）。该情况的总时间是（20+（80+80+5000*2*0.2+80）*0.1）*0.05=11.4ns 评分细则：以上四种情况的总和为 14

9、0.4ns。分析出至少四种情况的给总分的 60%，每种情况计算正确给 10%。如果分析错误，则酌情给分。备注：本题解法中其实有更为复杂的情况，那就是二级页表不在内存中引发缺页中断，但是由于题目中并未给出二级页表本身缺页的概率，所以可以默认二级页表一直在内存中。注解：从本题的解题过程中可以看出，如果 TLB 作为 Cache 的命中率足够高，那么原本非常浪费时间的多次内存访问事件反而由于发生概率小使得其对数学期望的贡献较小，最终的内存访问数据期望值是 140.4ns，非常接近一次 TLB 访问+一次内存访问（共计 100ns）的时间，这就是操作系统中进行内存访问效率优化的奥秘所在。7.考虑具有如

10、下特征的共享资源：1）资源总数为 3，每个进程只能占用 1 个资源；2）当使用该资源的进程小于 3 时，新申请资源的进程可以立刻获得资源；2）当 3 个资源均被占用时，只有当 3 个资源均被释放后，其他申请资源的 进程才能获得资源。请用信号量的方法来描述并解决这个问题。1）请说明你所定义的信号量及其他数据变量的逻辑含义，注意，应记录资源被占用数、等待资源进程数；2）使用伪代码描述资源申请及资源使用的同步互斥处理过程。（本题默认分值：（本题默认分值：15 分）分）信号量 R：记录当前可用资源的信号量，初始值为 3；信号量 T：记录当前进程已申请的资源数，初始值为 1；题目中要求每个进程只能占用一

11、个资源，这意味着在每个进程 的实现代码中，都应定义一个信号量 T，用来控制该进程申请资源的次数；信号量 M：互斥信号量，通用的互斥信号量，用于保护任何临界数据；信号量 N：记录是否可申请分配资源的信号量，初始值为 1；该信号量用于记录资源分配状态。数据变量 A：记录当前被占用资源的数量，当期为 3 时触发对信号量 N 的处理。(1)一个进程申请资源时的伪代码 Semphore S=3；/记录可用资源总数的信号量，为全局变量 Int A=0;/记录当前已分配资源数量 BOOL bFull=FALSE;/记录是否 3 个资源均被占用 第 5 页，共 18 页 Semphore M=1;/互斥信号量

12、，用以保护对变量 A 和 bFull 的访问 VOID Proc（）/进程实体 Semphore R=1;/记录该进程已申请资源的信号量，初值为 1 意味着每个进程只能申请一个资源 While()/资源申请临界区伪代码如下 P(R);/首先执行信号量 R 的 P 操作，这意味着在一个进程中不可能同时占有两个资源 P(S);/其次执行信号量 S 的 P 操作，这意味着如果可用资源数大于 0 且未出现 3 个资源均被占用的情况，则该进程可获得 1 个资源 P(M);/用互斥信号量保护对 A 和 bFull 的操作 A+;If（A=3）bFull=TRUE;/bFull 为 TRUE 意味着出现了

13、3 个资源均被占用的情况，以此为状态来控制 V(S)操作 V(M);获取一个资源并使用它 释放资源 P(M)A-;If(A=0)&bFull)bFull=FALSE;V(S);V(S);V(S);/该段代码意味着如果三个资源均被占用，则在第三个被占用资源释放后才一次性的发送三个 V(S)消息 Else if(!bFull)V(S);/该行代码是指并未出现三个资源均被占用的情况时，直接执行 V(S)以允许其他进程使用被释放的资源 V(M);V(R);/该进程在释放了占用的资源后方可继续申请资源 其他非临界区代码 评分规则：此题的关键之处在于如何记录 3 个资源均被占用的情况并以此为依据控制资源分

14、配信号量，第一项要求（信号量 R）和第二项要求（信号量 S）各占总分的 30%，第三项要求（信号量 M，变量 A 与 bFull）的用法占总分的 40%。如有其他解法可酌情给分，采用同样的分数比例进行评判。第 6 页，共 18 页 草稿区草稿区 8.现有 5 个批处理作业，编号为从 A 到 E，它们同时到达。其估计运行时间为 15,7,8,3 和 5（按 A 至 E 顺序），其优先 级为 2,5,1,3,4（值越小，表示优先级越高）。对如下 4 种调度算法，请计算每个进程的周转时间和平均周转时间。假设 所有作业都是 CPU 密集型的。1）时间片为 1 的轮转调度算法；2）优先级调度算法；3）先

15、来先服务算法（按 A 至 E 顺序）；4）最短作业优先算法。（本题默认分值：（本题默认分值：8 分，必须给出简要计算过程和计算结果）分，必须给出简要计算过程和计算结果）1)严格轮转调度，A:45 B:35 C:13 D:26 E:42 平均周转时间：(45+35+13+26+42)/5=32.2 2)调度顺序为 BEACD，A:36 B:9 C:39 D:45 E:21 平均周转时间：(36+9+39+45+21)/5=30 3)调度顺序为 ABCDE，A:15 B:24 C:27 D:33 E:45 平均周转时间：(15+24+27+33+45)/5=28.8 4)调度顺序为 CDBEA，A

16、:45 B:18 C:3 D:9 E:30 平均周转时间：(45+18+3+9+30)/5=21 评分规则：每一项调度算法的计算过程为总分的 25%，每个进程的周转时间结果正确 15%，平均周转时间正确为 10%。草稿区草稿区 9.死锁问题解决：一个系统中有 3 个进程和 4 种可分配资源，当前分配资源和最大需求如下表所示：已分配资源（R1,R2,R3,R4）剩余需求量（R1,R2,R3,R4）可用资源总量（R1,R2,R3,R4）进程 A 0 0 1 0 2 0 0 1 2 1 0 0 进程 B 2 0 0 1 1 0 1 0 进程 C 0 1 2 0 2 1 0 0 请回答以下问题：1）当

17、前状态是否安全？2）进程 A 申请 2 个单位的 R1是否允许？3）进程 C 申请 1 个单位的 R2是否允许？注意：以上三个问题是相互独立的，请提供计算思路，并对每一问题给出安全路径或不安全路径。（本题默认分值：（本题默认分值：10 分）分）第 7 页，共 18 页 1)初始状态初始状态 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 7 1 0 5 A 0 4 2 0 B 3 1 0 1 C 12 4 2 5 D 3 0 0 1 分给分给 B 之后，之后，B 退出退出 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 8

18、 3 1 5 A 0 4 2 0 C 12 4 2 5 D 3 0 0 1 分给分给 D 之后，之后，D 退出退出 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 11 4 2 5 A 0 4 2 0 C 12 4 2 5 分给分给 A 之后，之后，A 退出退出 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 15 4 2 6 C 12 4 2 5 分给分给 C 之后，之后，C 退出退出 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 第 8 页，共 18 页 16 5 2 8 所以是安

19、全的，安全路径所以是安全的，安全路径-D-A-C 初始状态初始状态 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 7 1 0 5 A 0 4 2 0 B 3 1 0 1 C 12 4 2 5 D 3 0 0 1 分给分给 D 之后，之后，D 退出退出 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 10 2 1 5 A 0 4 2 0 B 3 1 0 1 C 12 4 2 5 分给分给 B 之后，之后，B 退出退出 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 11 4 2 5 A

20、0 4 2 0 C 12 4 2 5 分给分给 C 之后，之后，C 退出退出 第 9 页，共 18 页 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 12 5 2 7 A 0 4 2 0 分给分给 A 之后，之后，A 退出退出 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 16 5 2 1 所以是安全的，安全路径为所以是安全的，安全路径为 D-B-C-A 综上，安全路径为综上，安全路径为 D-B-C-A B-D-C-A D-B-A-C B-D-A-C 2)初始状态初始状态 还需要的资源数量还需要的资源数量 系统总共还空

21、闲的资源数量系统总共还空闲的资源数量 7 1 0 5 A 0 4 2 0 B 3 1 0 1 C 12 4 2 5 D 3 0 0 1 进程进程 A 申请一个单位的申请一个单位的 R2 之后之后 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 7 0 0 5 A 0 3 2 0 B 3 1 0 1 第 10 页，共 18 页 C 12 4 2 5 D 3 0 0 1 分给分给 D，D 退出退出 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 10 1 1 5 A 0 3 2 0 B 3 1 0 1 C 12 4 2 5 分

22、给分给 B，B 退出退出 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 11 3 2 5 A 0 3 2 0 C 12 4 2 5 分给分给 A，A 退出退出 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 15 4 2 6 C 12 4 2 5 分给分给 C，C 退出退出 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 16 5 2 8 所以进程所以进程 A 申请申请 1 个单位的个单位的 R2 是容许的，安全路径为是容许的，安全路径为 D-B-A-C,且路径是唯一的。且路径是唯一的

23、。3）进程）进程 C 申请申请 6 个单位的个单位的 R1 是否允许是否允许 初始状态初始状态 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 7 1 0 5 A 0 4 2 0 第 11 页，共 18 页 B 3 1 0 1 C 12 4 2 5 D 3 0 0 1 进程进程 C 申请申请 6 个单位的个单位的 R1 之后之后 还需要的资源数量还需要的资源数量 系统总共还空闲的资源数量系统总共还空闲的资源数量 1 1 0 5 A 0 4 2 0 B 3 1 0 1 C 6 4 2 5 D 3 0 0 1 发生死锁，所以是不容许的，不安全路径为发生死锁，所以

24、是不容许的，不安全路径为 C 评分规则，如果正确的描述了每个进程还需要的资源数量以及系统目前可用资源数量，则给评分规则，如果正确的描述了每个进程还需要的资源数量以及系统目前可用资源数量，则给 10%的分数，每一问回答正确给的分数，每一问回答正确给 30%的分数，对每一问而言，如果没有计算过程只有答案，即便答案正确该问得分也只给的分数，对每一问而言，如果没有计算过程只有答案，即便答案正确该问得分也只给 5%。第 12 页，共 18 页 草稿区草稿区 10.一个进程访问 5 页：A，B，C，D，E，访问顺序如下：ABCDABEABCDE，请回答以下问题 1）若使用 FIFO 页面置换算法，该进程在

25、内存中有 3 个页框，初始时为空，请描述页面替换的次数和替换结果；2）若使用 FIFO 页面置换算法，该进程在内存中有 4 个页框，初始时为空，请描述页面替换的次数和替换结果；3）若使用 LRU 页面置换算法，该进程在内存中有 4 个页面，初始时为空，请描述页面替换的次数和替换结果？（本题默认分值：（本题默认分值：15 分，请给出计算分析的思路、过程和结果）分，请给出计算分析的思路、过程和结果）评分规则，第一问占 30%，第二问占 40%，第三问占 30%，计算过程正确给满分，只有结果正确需扣 15%的分数。第 13 页，共 18 页 草稿区草稿区 三、系统分析题（本题共三、系统分析题（本题共

26、 3 小题，共计小题，共计 25 分，选做分，选做 2 题，多做题目不得分）题，多做题目不得分）请在下面的表格中指定答题顺序，在对应的分值下列明题号。每格只许列出一个题号，否则做无效处理。请在下面的表格中指定答题顺序，在对应的分值下列明题号。每格只许列出一个题号，否则做无效处理。下表中必须写明所有题目的题号，如果填写不完全，视为不指定答题顺序。下表中必须写明所有题目的题号，如果填写不完全，视为不指定答题顺序。如填写内容无效或者不填写表格，则按照默认的题面分值评分如填写内容无效或者不填写表格，则按照默认的题面分值评分 第一题（第一题（15 分）分）第二题（第二题（10 分）分）11.进程调度是操

27、作系统的内核关键处理机制，它的设计与实现涉及到进程结构定义、时钟中断响应、就绪队列和阻塞队 列定义等诸多问题，请尝试设计一个简单的时间片严格轮转调度机制：1）简要描述你所定义的进程结构、进程列表结构以及其他所需要的数据变量。2）请用流程图或伪代码的形式来描述调度机制的核心处理过程，包括哪些函数？相互调用关系如何？（本题默认分值：（本题默认分值：15 分）分）得得 分分 第 14 页，共 18 页 草稿区草稿区 本题的参考答案为 Minix 中的进程结构描述及调度方法，参阅讲义即可。12.内存管理体系设计：动态分区技术是一种简洁易用的多道程序内存管理方法，在一些嵌入式系统中，经常采用动态分 草稿

28、区草稿区 区技术。假设在一个嵌入式操作系统环境中，所有用户进程都是被一次性加载进入内存，你的任务是设计完成用户空 间内存的动态分区管理技术体系，请尝试完成如下设计工作：1）请定义支持动态分区内存管理所需要的数据结构，注意，为了提高效率，数据结构越简单越好；2）请用伪代码或文字来描述内存分配与回收的处理过程；3）动态分区技术的最大问题是容易产生内存碎片，请设计一种方法，能够在操作系统运行过程中，定期的清理内存 碎片，请说明为实现内存碎片清理，需要定义的系统进程及其内存碎片清理过程；（本题默认分值：（本题默认分值：15 分）分）1）需要定义一个空闲分区表和空闲分区链表）需要定义一个空闲分区表和空闲

29、分区链表 首先需要定义一个全局常量，将其作为内存分配的基本单元，一般来说内存分配的基本单元可以为首先需要定义一个全局常量，将其作为内存分配的基本单元，一般来说内存分配的基本单元可以为 512 字节或字节或 1K 字节字节/空闲分区表空闲分区表 Struct StFreeTbl Int nID;/空闲分区号空闲分区号 Char*pStartAddr;/空闲分区起始地址空闲分区起始地址 Int nSize;/空闲分区的大小空闲分区的大小;/空闲分区链表空闲分区链表 Struct StFreeNode 第 15 页，共 18 页 StFreeNode*pPreNode;/指向前一个空闲分区的指针指向

30、前一个空闲分区的指针 StFreeTbl freeTbl;/空闲分区表空闲分区表 StFreeNode*pNextNode;/指向后一个空闲分区的指针指向后一个空闲分区的指针;2）内存分配过程）内存分配过程 假设任务需要分配的内存大小为假设任务需要分配的内存大小为 size，空闲分区链表为，空闲分区链表为 freeNodes /遍历空闲分区表遍历空闲分区表 For(;freeNodes-pNextNode!=NULL;freeNodes=freeNodes-pNextNode)If(当前空闲分区满足任务要求，此处可添加各种内存分配策略，如首次满足、最小适配，最大适配等当前空闲分区满足任务要求，

31、此处可添加各种内存分配策略，如首次满足、最小适配，最大适配等)返回当前空闲分区首地址；返回当前空闲分区首地址；freeNodes-freeTbl-pStartAddr+=size;/当前空闲分区起始地址向后移动当前空闲分区起始地址向后移动 size 个字节个字节 freeNodes-freeTbl-nSize-=size;/当前空闲分区大小减少当前空闲分区大小减少 size 个字节个字节 /如果该空闲分区的大小刚好等于请求分配内存的大小，则删除这个空闲分区节点；如果该空闲分区的大小刚好等于请求分配内存的大小，则删除这个空闲分区节点；内存回收过程内存回收过程 分为四种情况：分为四种情况：a)回收

32、区与空闲分区的起始地址相邻，将回收区与空闲分区合并为一个分区，并将空闲分区的其实地址设置为回收区起始地址，大小设置为回收区大小和回收区与空闲分区的起始地址相邻，将回收区与空闲分区合并为一个分区，并将空闲分区的其实地址设置为回收区起始地址，大小设置为回收区大小和 F1 大小之和。大小之和。回收区回收区 F1 第 16 页，共 18 页 b)回收区与空闲分区的结束地址相邻，将回收区与空闲分区合并为一个分区，将空闲分区的其实地址设置为回收区与空闲分区的结束地址相邻，将回收区与空闲分区合并为一个分区，将空闲分区的其实地址设置为 F1 的起始地址，大小设置为的起始地址，大小设置为 F1 和回收区大小之和

33、。和回收区大小之和。F1 回收区回收区 c)回收区在两个空闲分区之间，空闲分区起始地址设置为回收区在两个空闲分区之间，空闲分区起始地址设置为 F2 的起始地址，大小为的起始地址，大小为 F2 的大小的大小+回收区的大小回收区的大小+F1 的大小的大小 F2 回收区回收区 F1 d)回收区不与任何空闲分区相邻，新建一个空闲分区表，并加入空闲分区链表中。回收区不与任何空闲分区相邻，新建一个空闲分区表，并加入空闲分区链表中。F1 回收区回收区 F2 3）清理内存碎片的过程：内存碎片的清理是指如果在空闲链表中存在大量的小分区，则这些分区因为无法满足一些大容量的内存分配请求而无法被有效使用，内存紧缩技术

34、的实现过程是定义一个系统进程，该进程可通过设置定时器来定时唤醒，当进程运行时，它会把内存中所有的已占用分区紧缩在一起，即按照内存地址的顺序，将第二个已占用分区的起始地址调整到第一个已占用分区结束的地址（通过更改每个分区对应的内存地址来实现），依次处理第三个、第四个.。这样执行完成后，所有可用内存均合并为一个连续的 第 17 页，共 18 页 空闲分区。评分规则：以上答案是本题的最基础答案，课堂上曾详细讲解过 Minix 中动态分区的实现方式，以本题的基础答案为基准，第一问占总分的 30%，第二问占总分的 40%，第三问占总分的 30%，根据答案情况酌情给分。13.文件系统设计：文件格式对许多信

35、息系统的应用效率有着极为重要的影响，根据应用环境的特点来设计文件的逻辑结 构是系统设计人员必须具备的素质，假设你现在就是一名非常优秀的文件格式设计人员，你面临着不同应用环境下的 文件格式设计问题，请尝试回答如下问题：1）请简要说明你所了解的文件逻辑结构组织方式有哪几种？2）某种应用情境下，文件很少被修改但是需要极为频繁的随机访问，请设计一种文件逻辑结构及其数据访问方法；3）某种应用情境下，文件频繁的被修改而且需要频繁的随机访问，请设计一种文件逻辑结构及其数据访问方法；注意：请从访问速度、磁盘存储空间利用效率和易于使用（内容添加/删除/修改）等方面论述你的设计的合理性。（本题默认分值：（本题默认

36、分值：10 分）分）1）文件的逻辑结构的组织方式大体上分为三种文件的逻辑结构的组织方式大体上分为三种 第一种是字节流式的逻辑结构，该逻辑结构难以进行快速的随机访问，每一次修改时都涉及到整个字节流的插入删除操作；第一种是字节流式的逻辑结构，该逻辑结构难以进行快速的随机访问，每一次修改时都涉及到整个字节流的插入删除操作；第二种是基于记录（每个记录大小一样）的逻辑结构，该逻辑结构能够进行快速的随机访问，但对记录进行增删改时，需要对整个记录序列进行处理；第二种是基于记录（每个记录大小一样）的逻辑结构，该逻辑结构能够进行快速的随机访问，但对记录进行增删改时，需要对整个记录序列进行处理；第三种是基于树形（

37、树中每个节点的大小可不同）的逻辑结构，也是最接近面向对象思想的逻辑结构，随机访问性能高于字节流式结构，低于记录式结构；但文件内容的修改效率极高。第三种是基于树形（树中每个节点的大小可不同）的逻辑结构，也是最接近面向对象思想的逻辑结构，随机访问性能高于字节流式结构，低于记录式结构；但文件内容的修改效率极高。第 18 页，共 18 页 2）在这种情况下，文件很少被修改，因此需要注意的就是提高文件的随机访问速度。在这种情况下，文件很少被修改，因此需要注意的就是提高文件的随机访问速度。此时最适合采用记录式文件结构，可为每个文件设计一个记录索引表，该索引表中存储了文件中每条记录的编号，长度和硬盘起始位置

38、。此时最适合采用记录式文件结构，可为每个文件设计一个记录索引表，该索引表中存储了文件中每条记录的编号，长度和硬盘起始位置。当对文件进行随机访问时，首先读出索引表内容，然后计算（文件内访问地址当对文件进行随机访问时，首先读出索引表内容，然后计算（文件内访问地址/记录长度）获得记录编号，以其为索引查询索引表获得该记录的起始地址，再用（文件内访问地址记录长度）获得记录编号，以其为索引查询索引表获得该记录的起始地址，再用（文件内访问地址%记录长度）获得该记录内的偏移地址。记录长度）获得该记录内的偏移地址。当对文件进行修改时，主要的修改操作设计增、删、改，每一种操作的设计简要描述如下：当对文件进行修改时

39、，主要的修改操作设计增、删、改，每一种操作的设计简要描述如下：第一种，在某个位置增加一个记录，首先通过文件索引表找到该位置所对应的记录编号，记录式文件结构的特点是每条记录定长，因此增加一条记录的操作在索引表中就意味着为新纪录分配一个编号，这个新纪录如果在文件尾部则效率最高，如果在文件头部或中间，则需要更新其后所有记录的编号及起始地址。第一种，在某个位置增加一个记录，首先通过文件索引表找到该位置所对应的记录编号，记录式文件结构的特点是每条记录定长，因此增加一条记录的操作在索引表中就意味着为新纪录分配一个编号，这个新纪录如果在文件尾部则效率最高，如果在文件头部或中间，则需要更新其后所有记录的编号及

40、起始地址。第二种，删除某个记录，在索引表中删除一个记录的操作是将该记录之后的所有记录向前移动一个记录长度的偏移地址。第二种，删除某个记录，在索引表中删除一个记录的操作是将该记录之后的所有记录向前移动一个记录长度的偏移地址。第三种，修改某个记录，利用随机访问迅速的找到该记录的地址，然后在记录内进行内容修改操作。第三种，修改某个记录，利用随机访问迅速的找到该记录的地址，然后在记录内进行内容修改操作。3）在这种情况下，文件会被频繁修改，而且频繁访问。因此最好的选择是采用树形逻辑结构方式，在课堂上曾讲解过在这种情况下，文件会被频繁修改，而且频繁访问。因此最好的选择是采用树形逻辑结构方式，在课堂上曾讲解

41、过 I-Node 文件管理方式，可遵循文件管理方式，可遵循 I-Node 思想来设计文件系统，如下图所示。思想来设计文件系统，如下图所示。评分规则：第一问中应回答三种文件逻辑结构的组织形式，每一种回答正确则占总分的 10%，第一问占总分的 30%；第二问中应采用记录式文件逻辑结构+索引表结构，如果选择正确则获得总分的 15%，在使用记录式文件结构的基础上，如果文件读写设计思路正确，则获得总分的 10%，第二问占总分的 25%；第三问中应采用树形文件逻辑结构，最佳设计思路是采用 i-node 节点的方式进行设计，如果选择正确则获得总分的 15%，如果文件读写思路正确，则获得总分的 30%，第三问占总分的 45%