第6章 文件管理-2.pdfVIP

第第六章第六章章 文件管理文件管理件 1 6.5 文件存储空间的管理 先要记住先要记住空闲存储空间空闲存储空间的情况的情况。为此为此，设置设置 相应的数据结构相应的数据结构；；系统要提供对存储空间系统要提供对存储空间分配和分配和 回收的功能。 11. 空闲表法空闲表法 33. 位示图位示图法法 2. 空闲链表法 4. 成组链接法 2 6.5.1 空闲表法和空闲链表法（1） 11. 空闲表法空闲表法  空闲表：外存每个空闲区对应一个空闲表项  空间的分配和回收空间的分配和回收 （（可采用多种方式可采用多种方式，如首次适应算如首次适应算 法、循环首次适应算法等） 序号 第一空闲盘块表 空闲盘块数 11 22 44 2 9 3 33 1515 55    空闲盘块表 3 6.5.1 空闲表法和空闲链表法（2） 22. 空闲链表法空闲链表法 所有空闲盘区拉成所有空闲盘区拉成一条空闲链条空闲链。根据构成链的基根据构成链的基 本元素的不同，可有两种链表方式：  空闲空闲盘块盘块链链 （以盘块为基本单位构成链） 优点：分配和回收一个盘块的过程非常简单； 缺点：空闲盘块链可能很长。  空闲空闲盘区盘区链链 （以盘区为基本单位） 分配和回收过程较复杂，但空闲盘区链较短。 4 6.5.2 位示图法位示图法 1. 位示图  每一位表示一个块/簇，值0和1分别表示空闲和占用  占用空间少、容易找到相邻的空闲盘块 5 22. 盘块的分配盘块的分配((三步三步)) 顺序扫描位示图顺序扫描位示图，找出找出一个个//组组值是值是00的二的二 进制位 将找到的二进制位，转换成对应的盘块 号 b = n(i-1) + j 修改位示图 map[ i,j ] = 1 6 3. 盘块的回收(2步)  将盘块号b转换成位于图中的行号和列号 i ((b-1)) DIV n + 1 j=(b-1) MOD n + 1  修改位示图 map[i,j]= 0 7 6.5.3 成组链接法 11. 空闲盘块的组织空闲盘块的组织 （图6-2