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

1、1,5.2.3 记录成组技术 问题: 逻辑记录的长度和物理块大小不相等或不是整倍数时该如何处理? 记录成组技术将多个逻辑记录合成一组并保存在物理块上的方法,2,1逻辑记录长度为物理块大小的整数因子 一个物理块可以装下整数个记录。 计算记录所在的相对块号的方法是： 相对块号 = 记录地址 DIN 物理块大小 对于连续文件和串联文件来说，知道了相对块号和文件首地址，顺序查找即可找到相应的物理块。,3,对于索引文件，要对索引表作适当的修改。 一种方法：利用文件的相对块号作为索引，而不是记录号 相对块号 = 记录号 DIN 每个物理块存放的记录数 再根据索引表查到相应的物理块号地址，最后确定该记录在物

2、理块中的地址，从而得到最终的地址。,4,对于哈希文件，一个物理块容纳多个记录正好可以把Hash函数值相同的记录放在同一个物理块中来处理键值冲突，如果记录填满一个物理块时，则可申请一个新的物理块。,5,2逻辑记录长度不为物理块大小的整数因子 解决方法有三种： (1) 空间空闲法，即只存放整数个记录，让剩余空间空闲。 (2) 调整物理块的大小。可以根据文件记录长度改变磁盘的磁道、扇区划分格式，使其可以放下整数个记录。但一般说来，改变格式也不是十分方便的，况且还涉及到其它问题，如已经存入的信息如何处理等，所以这种方法通常是不用的。,6,(3) 扩充软件法。这种办法允许记录跨物理块存储，并采用扩充软件

3、功能的办法来适应记录的存取。如图所示，第3条记录在物理块1和物理块2中各有一部分。 算法： 根据逻辑地址，确定第三条记录的始地址， 即记录头； 确定记录的首地址所在的物理块号； 计算记录的首地址在物理块内的相对地址； 计算记录在第一个物理块中的有效长度； 计算记录剩余的长度，如果等于0，则说明读取完毕，否则计算出记录剩余部分的逻辑地址。,7,5.2.4 文件存储空间管理 文件的存储有两种策略： 一种是为文件分配连续的存储空间，即连续的存储块 增加文件内容需移动；删除文件会有碎片。 另一种是为文件分配不一定连续的块。 现在几乎所有的文件系统都把文件存储空间分成固定大小的块来存储文件。存储文件的块

4、与块之间不必相邻。这样，可以更有效地利用外存空间，但是分配和回收的速度可能会受到影响。,8,1块大小的考虑 由于文件是按块分配的，块的大小是一个十分重要的问题。 如果块过大，可能会造成空间的浪费。块过小，意味着每个文件都由许多块组成，必然会影响文件的存取速度。 一般系统中，文件存储块的大小常采用512 B、1 KB或2 KB。当然，随着时间的推移，用户对资源的需求在增加，块的大小也应随之改变。例如，1984年调查表明，UNIX系统的文件大小平均在1 KB左右，而到1997年，一般系统中文件的平均长度已升至10 KB以上。,9,2空闲块管理（物理块的分配和回收的问题） 三种方法： 1) 空白文件

5、目录 把一个连续的未分配区域（可能包含若干个空闲块）看作一个文件，称为空白文件。系统为所有的空白文件建立一个目录，即空白文件目录。每个空白文件对应于空白文件目录中的一个表目，分配回收类似内存的可变式分区存储管理算法（有合并）。,10,2) 空闲块链接法 空闲块链接法可以分为：空闲盘块链、空闲盘区链及成组链接法。 (1) 空闲盘块链 所有空闲盘块链接在一起，设一个指针，指向链头 空闲盘块链法的分配与回收过程都十分简单，但是空闲盘块链可能会很长。,11,(2) 空闲盘区链。 空闲盘区链法是将若干连续的空闲盘块作为一个空闲盘区，每个区含有一个指向下一个空闲盘区的指针及本空闲盘区大小的说明，所有空闲盘

6、区形成一个链，设一个指针，指向链头，如图5-16所示。 分配算法可以参考内存的可变式分区存储管理算法(有合并)。 为了提高对空闲盘区链的查找速度，通常在内存建立空闲盘区的链表。 空闲盘区链法的分配与回收过程比较复杂，但是空闲盘区链较短。,12,(3) 成组链接法。 在UNIX系统中采用了一种改进的方法。 它把文件存储空间的空闲盘块分组，再将每组具体的空闲盘块号及个数记录到另一组的第一个空闲盘块中，组与组之间通过每组的第一块链接起来，将当前使用的一组空闲盘块号及块数放在空闲盘块号栈中。 系统启动后，文件存储空间的分配与回收通过已进入内存的空闲盘块号栈进行； 栈空时，将链接的下一组空闲盘块号及块数

7、调入； 栈满时，将栈中的空闲盘块号作为一组，加入链中，这就是成组链接法，如图5-17所示。,13,图5-17 空闲盘块的成组链接法,14,图5-21 成组链接法的一次分配过程(分配三块),15,图5-18 成组链接法分配算法,16,图5-20 成组链接法的一次回收过程 (回收12、125、65、156),17,图5-19 成组链接法回收算法,18,5.2文件结构和文件存取 5.2.1 文件逻辑结构及文件存取(顺序;直接;按键) 5.2.2 文件物理结构 连续;链接;索引(简单;链接式;多级索引);散列 5.2.3 记录成组技术 5.2.4 文件存储空间管理 1.块大小的考虑 2.空闲块管理 1

8、)空白文件目录 2)空闲块链接法(空闲盘块链;空闲盘区链;成组链接法) 3)位示图 3.磁盘I/O调度算法,19,3) 位示图 通过位示图进行文件存储空间的分配与回收。 首先，为文件存储空间建立位示图，位示图中的字位与文件存储空间的物理块一一对应，反映文件存储空间的使用情况。 在位示图中，字位为0，表示对应物理块是空闲的；字位为1，表示对应的物理块已被占用。 假如0字0位对应文件存储空间的200号物理块，则1字8位的0表示文件存储空间的224号物理块是空闲块，而2字0位的1表示文件存储空间的232号物理块是已被占用的，如图5-22所示。,20,图5-22 位示图,21,分配时，需要将位示图中为

9、0的字位换算成对应的文件存储空间的物理块号，并修改字位为1； 回收时，需要将回收的物理块号对应于位示图的相应字位，并将其置为0，以备后用。 例如图5-22所示， 分配时，若找出i行j列为0，则可知其对应的空闲块号b=i16+j+200，分配b块后，将i行j列置为1。 回收时，若回收块号为b，则位示图上对应位号为 i=(b-200) DIN 16 j=(b-200) MOD 16 然后就可将i行j列置为0.,22,3磁盘I/O调度算法 磁盘是可以被多个进程共享的设备。当进程有磁盘I/O请求时，通常将进程阻塞在磁盘I/O的等待队列上。对于阻塞在磁盘I/O等待队列上的进程，应选择适当的调度算法，使得

10、进程的平均寻道时间为最少，又不致落下某些进程，使之得不到调度。 1) 先来先服务调度算法(FCFS) 根据进程访问磁盘的先后次序进行调度。该算法简单、公平，每个进程的请求都能依次得到处理，不会落下某些进程的请求。但是当磁盘I/O阻塞队列中相邻进程访问磁道的跳跃性较大时，则寻道长度较大，寻道时间较长。,23,2) 最短寻道时间优先调度算法(SSTF) 选择与当前磁头所在磁道距离最近的进程I/O请求进行调度，使得每次的寻道长度与时间最短。 这种调度算法通常比先来先服务调度算法有较好的调度性能，但是当磁头所在磁道附近不断有新的I/O请求到达时，则距离磁头位置较远进程的I/O请求可能被落下，长时间得不到调度，以致被“饿死”。,24,3) 扫描算法(SCAN) 扫描算法是当前磁头沿一个方向移动时，对所遇到的磁道上的I/O请求依次响应，直至该移动方向再无I/O请求时，磁臂换向；磁头向反方向移动时，再对所遇磁道上的I/O请求依次响应，往返交替。这种调度算法可以防止最短寻道时间优先调度算法中某些进程被“饿死”的现象。 扫描算法有较好的寻道性能，但是当有进程的I/O请求到达刚被扫描过的磁道时，则这个请求会被推迟，直到磁头沿此方向扫描到头换向后，再次扫描到这个I/O请求