操作系统简明教程PPT第5章3.pptVIP

5.2.3 记录成组技术 问题: 逻辑记录的长度和物理块大小不相等或不是整倍数时该如何处理? 记录成组技术——将多个逻辑记录合成一组并保存在物理块上的方法 1．逻辑记录长度为物理块大小的整数因子 一个物理块可以装下整数个记录。 计算记录所在的相对块号的方法是： 相对块号 = 记录地址 DIN 物理块大小 对于连续文件和串联文件来说，知道了相对块号和文件首地址，顺序查找即可找到相应的物理块。 对于索引文件，要对索引表作适当的修改。 一种方法：利用文件的相对块号作为索引，而不是记录号 相对块号 = 记录号 DIN 每个物理块存放的记录数 再根据索引表查到相应的物理块号地址，最后确定该记录在物理块中的地址，从而得到最终的地址。 对于哈希文件，一个物理块容纳多个记录正好可以把Hash函数值相同的记录放在同一个物理块中来处理键值冲突，如果记录填满一个物理块时，则可申请一个新的物理块。 2．逻辑记录长度不为物理块大小的整数因子 解决方法有三种： (1) 空间空闲法，即只存放整数个记录，让剩余空间空闲。 (2) 调整物理块的大小。可以根据文件记录长度改变磁盘的磁道、扇区划分格式，使其可以放下整数个记录。但一般说来，改变格式也不是十分方便的，况且还涉及到其它问题，如已经存入的信息如何处理等，所以这种方法通常是不用的。 (3) 扩充软件法。这种办法允许记录跨物理块存储，并采用扩充软件功能的办法来适应记录的存取。如图所示，第3条记录在物理块1和物理块2中各有一部分。 算法：① 根据逻辑地址，确定第三条记录的始地址， 即记录头； ② 确定记录的首地址所在的物理块号； ③ 计算记录的首地址在物理块内的相对地址； ④ 计算记录在第一个物理块中的有效长度； ⑤ 计算记录剩余的长度，如果等于0，则说明读取完毕，否则计算出记录剩余部分的逻辑地址。 5.2.4 文件存储空间管理 文件的存储有两种策略： 一种是为文件分配连续的存储空间，即连续的存储块 增加文件内容需移动；删除文件会有碎片。 另一种是为文件分配不一定连续的块。 现在几乎所有的文件系统都把文件存储空间分成固定大小的块来存储文件。存储文件的块与块之间不必相邻。这样，可以更有效地利用外存空间，但是分配和回收的速度可能会受到影响。 1．块大小的考虑 由于文件是按块分配的，块的大小是一个十分重要的问题。 如果块过大，可能会造成空间的浪费。块过小，意味着每个文件都由许多块组成，必然会影响文件的存取速度。 一般系统中，文件存储块的大小常采用512 B、1 KB或2 KB。当然，随着时间的推移，用户对资源的需求在增加，块的大小也应随之改变。例如，1984年调查表明，UNIX系统的文件大小平均在1 KB左右，而到1997年，一般系统中文件的平均长度已升至10 KB以上。 2．空闲块管理（物理块的分配和回收的问题） 三种方法： 1) 空白文件目录 把一个连续的未分配区域（可能包含若干个空闲块）看作一个文件，称为空白文件。系统为所有的空白文件建立一个目录，即空白文件目录。每个空白文件对应于空白文件目录中的一个表目，分配回收类似内存的可变式分区存储管理算法（有合并）。 2) 空闲块链接法 空闲块链接法可以分为：空闲盘块链、空闲盘区链及成组链接法。 (1) 空闲盘块链 所有空闲盘块链接在一起，设一个指针，指向链头 空闲盘块链法的分配与回收过程都十分简单，但是空闲盘块链可能会很长。 (2) 空闲盘区链。 空闲盘区链法是将若干连续的空闲盘块作为一个空闲盘区，每个区含有一个指向下一个空闲盘区的指针及本空闲盘区大小的说明，所有空闲盘区形成一个链，设一个指针，指向链头，如图5-16所示。 分配算法可以参考内存的可变式分区存储管理算法(有合并)。 为了提高对空闲盘区链的查找速度，通常在内存建立空闲盘区的链表。 空闲盘区链法的分配与回收过程比较复杂，但是空闲盘区链较短。 (3) 成组链接法。 在UNIX系统中采用了一种改进的方法。 它把文件存储空间的空闲盘块分组，再将每组具体的空闲盘块号及个数记录到另一组的第一个空闲盘块中，组与组之间通过每组的第一块链接起来，将当前使用的一组空闲盘块号及块数放在空闲盘块号栈中。 系统启动后，文件存储空间的分配与回收通过已进入内存的空闲盘块号栈进行； 栈空时，将链接的下一组空闲盘块号及块数调入； 栈满时，将栈中的空闲盘块号作为一组，加入链中，这就是成组链接法，如图5-17所