操作系统 考研习题 详细解析（2）

操作系统 考研习题 详细解析（1）页内跳转好像失效了😭

链接：https://pan.baidu.com/s/1o5lAjg7BXEnuusdLJThMKA  提取码：bfio  操作系统和数据结构题目集

目录

文件管理

文件存储

链式、连续、索引存储

混合索引

访盘次数 / 平均访盘次数

位示图

文件存储方式比较

磁盘调度算法

磁盘访问时间

磁盘地址映射

小题

IO管理

小题

单双缓冲计算题

磁盘大小（数量）需要几位存储÷8可得一个表目占的大小(B)×盘数得FAT的空间

    这里的几位存储可以根据整个硬盘大小算出需要多少位。如题1。

    还可以根据FAT中的表项大小可知。如混合索引--题2（2）

一个索引块包含的索引节点个数×物理块大小得最大文件长度

    可以根据FAT中的表项大小推出表项（索引节点）个数。如混合索引--题2（2）

    可以根据地址所占空间（指针大小）结点个数，如混合索引--题3（2）

题1：假定磁盘块的大小为1KB，对于540MB的硬盘，其文件分配表(FAT）最少需要占用多少存储空间?

解1：对于540MB的硬盘，硬盘总块数为540MB/1KB= 540K个。 因为540K刚好小于2^20，所以文件分配表的每个表目可用20位，即20b/8= 2.5B，这样FAT占用的存储空间大小为2.5B×540K= 1350KB。

文件分配表大小=表目大小×表目数量

表目数量=所用磁盘块数量（一一对应的关系）

表目大小=一个索引节点的大小 同内存管理的索引节点。其中20位，说明由2^20种组合即块数可以映射。

这里就是根据上面的公式通过磁盘数推导出剩下的东西

题2：【2012统考真题】某文件系统空间的最大容量为4TB (1TB =2^40B)，以磁盘块为基本分配单位。磁盘块大小为1KB。文件控制块(FCB)包含一个512B的索引表区。请回答下列问题: 1)假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节?可支持的单个文件的最大长度是多少字节? 2)假设索引表区采用如下结构:第0~7字节采用格式表示文件创建时预分配的连续存储空间。其中起始块号占6B，块数占2B，剩余504B采用直接索引结构。一个索引项占6B，则可支持的单个文件的最大长度是多少字节?为使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。  

解2：这题也可以放到混合索引里，但看文件存储就一题，给它当个伴。

最大容量 / 磁盘块大小 = 盘块数；盘块数的2的次数 / 8 =索引项存储大小；索引区大小 / 索引节点大小（块号大小）= 索引区含多少项。

1）文件系统中所能容纳的磁盘块总数为4TB/1KB=2^32。要完全表示所有磁盘块，索引项中的块号最少要占32/8 = 4B。而索引表区仅采用直接索引结构，因此512B的索引表区能容纳512B/4B= 128个索引项。每个索引项对应一个磁盘块，所以该系统可支持的单个文件最大长度是128×1KB= 128KB。 2)这里考查的分配方式不同于我们熟悉的三种经典分配方式，但题目中给出了详细的解释。所求的单个文件最大长度一共包含两部分:预分配的连续空间和直接索引区。 连续区块数占2B，共可表示2^16个磁盘块，即2^16KB,直接索引区共504B/6B =84个索引项。所以该系统可支持的单个文件最大长度是2^16KB+84KB。 为了使单个文件的长度达到最大，应使连续区的块数字段表示的空间大小尽可能接近系统最大容量4TB。分别设起始块号和块数占4B，这样起始块号可以寻址的范围是2^32个磁盘块，共4TB，即整个系统空间。同样，块数字段可以表示最多2^32个磁盘块，共4TB。预分配的连续空间的块数其实就相当于直接索引。知道块数换算成索引位数（2B×8=16b）算出索引项个数得出结果 套娃般轻松惬意

题3：页大小为4KB，页表长度为1K，逻辑地址中___位用于指定页号

解3：页表有1024个索引项，一页占4KB，所以总共有2^22KB，则22-12=10位（12页内偏移量）

也可直接根据索引项1024得出有2^10页 所以需要10位。

题2（链式存储）：某个文件系统中，外存为硬盘。物理块大小为512B，有文件A包含598条记录，每条记录占255B,每个物理块放2条记录。文件A所在的目录如下图所示。文件目录采用多级树形目录结构，由根目录结点、作为目录文件的中间结点和作为信息文件的树叶组成，每个目录项占127B，每个物理块放4个目录项，根目录的第一块常驻内存。试问:

1）若文件的物理结构采用链式存储方式，链指针地址占2B，则要将文件A读入内存，至少需要存取几次硬盘? 2）若文件为连续文件，则要读文件A的第487条记录至少要存取几次硬盘? 3）一般为减少读盘次数，可采取什么措施，此时可减少几次存取操作?  

解2：注意：题目中说每个物理块放四个目录项，所以图片的1 2 3 4 5是这样子的，先访问前面的再访问同层次的后面目录项。

1)由于根目录的第一块常驻内存（即root所指的/bin,/dev, /etc, /boot可直接获得），根目录找到文件A需要5次读盘。由255x2+2=512可知，一个物理块在链式存储结构下可放2条记录及下一个物理块地址,而文件A共有598条记录，因此读取A的所有记录所需的读盘次数为598/2 = 299,所以将文件A读到内存至少需读盘299+5=304次。（598条记录需要598/2=299个数据块（每个数据块含两条记录+指针大小））

2）当文件为连续文件时，找到文件A同样需要5次读盘，且知道文件A的地址后通过计算，只需一次读盘即可读出第487条记录，所以至少需要5＋1=6次读盘。（这里的连续存储就是连续放在一起，可以直接找到物理块，也没啥好解释的🗽） 3）为减少因查找目录而读盘的次数，可采用索引结点方法。若一个目录项占16B，则一个盘块可存放512/16= 32个目录项，与本题一个盘块仅能存放4个目录相比，可使因访问目录而读盘的次数减少1/8。对查找文件的记录而言，可用一个或多个盘块来存放该文件的所有盘块号，即用链接索引方法;一个盘块可存放512/2-1 = 255个盘块号，留下一个地址用来指向下一个存储盘块号（索引块）的磁盘块号。这样，就本题来说，查找目录时需启动5次磁盘。文件A共有299个盘块，则查找文件A的某一记录时需两次取得所有盘块号，再需最多启动一次磁盘即可把A中的任意一条记录读入内存。所以，查找一条记录最多需要8次访盘，而原来的链接方法查找一条记录时，读盘次数为6～304。

（访盘次数 / 平均访盘次数的题2 也可以减少读盘次数。博主讲的也不错计算访问磁盘数_发现问题，并解决问题-CSDN博客_三级索引访问几次磁盘）

题3（连链存储）：【2014统考真题】文件F由200条记录组成，记录从1开始编号。用户打开文件后，欲将内存中的一条记录插入文件F中，作为其第30条记录。请回答下列问题，并说明理由。 1）若文件系统采用连续分配方式，每个磁盘块存放一条记录，文件F存储区域前后均有足够的空闲磁盘空间，则完成上述插入操作最少需要访问多少次磁盘块?F的文件控制块内容会发生哪些改变? 2）若文件系统采用链接分配方式，每个磁盘块存放一条记录和一个链接指针，则完成上述插入操作需要访问多少次磁盘块?若每个存储块大小为1KB，其中4B存放链接指针，则该文件系统支持的文件最大长度是多少?

解3：注意：F存储区域前后均有足够的空闲磁盘空间。因此，欲最少，则只需移动前面的块数即可。

1)系统采用顺序分配方式时，插入记录需要移动其他的记录块，整个文件共有200条记录，要插入新记录作为第30条，而存储区前后均有足够的磁盘空间，且要求最少的访问存储块数，则要把文件前29条记录前移，若算访盘次数，移动一条记录读出（访盘）和存回磁盘各是一次访盘，29条记录共访盘58次，存回第30条记录访盘1次，共访盘59次。 F的文件控制区的起始块号和文件长度的内容会因此改变。

补充：连续分配支持顺序访问和直接访问。其优点是实现简单、存取速度快。缺点是文件长度不宜动态增加，因为一个文件末尾后的盘块可能已分配给其他文件，一旦需要增加，就需要大量移动盘块。此外，反复增删文件后会产生外部碎片（与内存管理分配方式中的碎片相似，且很难确定一个文件需要的空间大小，因而只适用于长度固定的文件）。

2）文件系统采用链接分配方式时，插入记录并不用移动其他记录，只需找到相应的记录修改指针即可。插入的记录为其第30条记录，因此需要找到文件系统的第29块，一共需要访盘29次，然后把第29块的下块地址部分赋给新块，把新块存回磁盘会访盘1次,然后修改内存中第29块的下块地址字段，再存回磁盘，一共访盘31次。（最后两次就相当于两个磁盘块放回磁盘要重新访盘进行存储） 4B共32位，可以寻址2^32=4GB块存储块，每块的大小为1KB，即1024B，其中下块地址部分占4B，数据部分占1020B，因此该系统的文件最大长度是4GB×1020B=4080GB。（链接指针存放地址，因此看链接地址的位数，即可知道能映射到多少磁盘空间。还有知道了别开心太早，题目给你挖了小坑☢，一个块还要存储链接指针，需要减去，因为它不算文件的内容）原文第十八题，在下面部分

题4（索引存储）：【2018统考真题】某文件系统采用索引结点存放文件的属性和地址信息，簇大小为4KB。每个文件索引结点占64B，有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，每个地址项长度为4B。请回答下列问题: 1）该文件系统能支持的最大文件长度是多少?（给出计算表达式即可) 2）文件系统用1M ( 1M=2^20)个簇存放文件索引结点，用512M个簇存放文件数据。若一个图像文件的大小为5600B，则该文件系统最多能存放多少个这样的图像文件? 3）若文件F1的大小为6KB，文件F2的大小为40KB，则该文系统获取F1和F2最后一个簇的簇号需要的时间是否相同?为什么?

解4：建议先看混合索引下的题目，题目有点重合。几级间接地址就一个簇内的地址项的几次方即可（二刷：多级间接地址项索引的是一个簇，簇里都是地址项，而不是索引 索引节点。然后根据地址项索引物理块）

1）簇大小为4KB，每个地址项长度为4B，因此每簇有4KB/4B=1024个地址项。最大文件的物理块数可达8+ 1×1024+ 1×1024^2+ 1×1024^3，每个物理块（簇）大小为4KB，因此最大文件长度为(8+1×1024+1×1024^2+ 1×1024^3)×4KB= 32KB+4MB+4GB+ 4TB

2）文件索引结点总个数为1M×4KB/64B=64M，5600B的文件占2个簇，512M个簇可存放的文件总个数为512M/2= 256M。可表示的文件总个数受限于文件索引结点总个数，因此能存储64M个大小为5600B的图像文件。（这里给个计算小技巧：首先，这些数字要熟悉：32--2^5、1024--2^10、2048--2^11、4096--2^12、8192--2^12，然后比大小 发现4096=4KB小于5600，所以需要2个簇，此外，记不住的话最好记2^5 2^10 ...及对应的十进制 以此类推，这样子方便推算。用2的几次表示方便乘除、十进制方便加减）（二刷：我的理解是一个文件一个索引结点，所以是64M，一开始做懵了，一个索引不是能表示第一题这么多的大小吗，后来看了答案 想必是一个文件对应一个索引节点 一个索引节点对应该文件的大小吧） 3)文件F1的大小为6KB < 4KB×8= 32KB，因此获取文件F1的最后一个簇的簇号只需要访问索引结点的直接地址项。文件F2大小为40KB,(4KB×8