• 目的： • （1）提高存储空间的利用率 • （2）提高文件的访问速度
6.3.1
连续分配
• 每个文件分配一组相邻接的盘块，也称物理 顺序文件。 • 主要问题：随着使用，磁盘碎片增多，性能 下降，需要磁盘整理。 • 优点：顺序访问速度快，定位容易，只需记 录第一个簇的位臵。可以通过紧缩 (compact)将外存空闲空间合并成连续的区 域。 • 缺点：需要连续的空间，当文件长度变化难 于处理，即必须事先知道文件的长度。
• (2) 假设索引表采用如下结构：第0～7字节 采用<起始块号，块数>格式表示文件创建 时预分配的连续存储空间，其中起始块号占 4B，块数占2B；剩余504B采用直接索引结 构，一个索引项占6B，则可支持的单个文件 最大长度是多少？为了使单个文件的长度达 到最大，请指出起始块号和块数分别占用字 节数的合理值并说明理由。 • 块数占2B，单个文件的最大长度 • 216×1KB ＋ 504/6 ×1KB＝65620KB • <4,4> <1,7> <2,6> <3,5> • 只要块数在4B以上就可以表示连续232个块， 使文件达到最大4TB。
• 关闭：将内存中对应的文件表目复制到外存 目录表中，从内存打开文件表中删除对应的 目录项。 • 3. 其它文件操作 • 以系统调用的形式提供给用户，有： • 1）关于文件属性的操作：改变文件名、改 变文件所有者、改变文件的访问权限等。 • 2）有关目录操作的：创建目录、删除目录 等。 • 3）实现文件共享的操作
索引分配
• 例：某文件系统的最大容量为4TB，以磁盘 块为基本分配单位，盘块大小为1KB。FCB 包含一个512B的索引表区。 • （1）假设索引表区采用直接索引，索引表 区存放文件占有的磁盘块号。索引表项中块 号最少占用多少字节？可支持的单个文件的 最大长度是多少字节？ • 磁盘最多盘块数：4TB / 1KB =2 32 • 所以需要4字节存放盘块号。 • 文件最大长度 512/4 ×1KB ＝ 128KB
• 2、对顺序文件的读写： • （1） 定长记录：设臵读或写指针每次读/写 一个记录后 ptr = ptr+L 使指针指向下一个 记录。 • （2）变长记录：设臵读或写指针每次读/写 一个记录后 ptr = ptr+Li 使指针指向下一 个记录。 • 3、顺序文件的优缺点 • 优点：批量处理数据，快！介质：磁带。 • 缺点：对单个记录处理困难，插入或删除尤 其如此。
• (2) 主要方法：两种 – 簇大小可变，其上限较大：I/O访问性能 较好。但簇大小可变，文件存储空间的管 理困难，因为要指明每个簇的尺寸。 – 簇大小固定，较小：文件存储空间使用灵 活，但I/O访问性能下降，文件管理所需 空间开销较大
6.3.3 索引分配
• 1、单级索引（直接索引） • 为每个文件分配一个索引块。记录分配给该 文件的所有盘块号，文件目录项中记录该索 引块的盘块号。 • 问题：浪费外存空间，对小文件尤其如此。
• 2、无结构文件 • 文件体为字节流，不划分记录，顺序访问， 每次读写访问可以指定任意数据长度，系统 不对文件进行格式处理，即流式文件。在 UNIX系统中，所有文件（有结构或无结构） 都看成是流式文件。
6.2.2 顺序文件 (sequential file)
• 1、逻辑记录的排序 • 文件中的记录可按照任意顺序排序，分两种 情况： • （1）串结构：记录顺序与关键字无关，存入 时间决定顺序 • （2）顺序结构：记录按关键字排序，检索效 率高。 • 顺序结构比串结构有更高的检索效率。
第六章 文件管理
• 信息是计算机系统中的重要资源，操作系统 中的一个重要组成部分，文件系统，负责信 息的组织、存储和访问。文件系统的功能就 是提供高效、快速和方便的信息存储和访问 功能。
• 文件管理的目的: • (1) 方便的文件访问和控制：以符号名称作为文件 标识，便于用户使用； • (2) 并发文件访问和控制：在多道程序系统中支持 对文件的并发访问和控制； • (3) 统一的用户接口：在不同设备上提供同样的接 口，方便用户操作和编程； • (4) 多种文件访问权限：在多用户系统中的不同用 户对同一文件会有不同的访问权限； • (5) 优化性能：存储效率、检索性能、读写性能； • (6) 差错恢复：能够验证文件的正确性，并具有一 定的差错恢复能力；
文件分配表
簇的大小
• 文件存储单位：簇（cluster）――簇又称为部 分(portion) • 文件的存储空间通常由多个独立的簇组成，而 每个簇包含若干个连续的外存存储单位（如扇 区sector），如何确定每个簇的大小？ • （1）簇的大小 – 两个极端：大到能容纳整个文件，小到一 个外存存储块（一个扇区） – 簇较大：提高I/O访问性能，减小管理开销 – 簇较小：簇内的碎片浪费较小，特别是大量 小文件时有利。
• 2．文件的物理结构：又称文件的存储结构， 文件在外存上组织形式，与存储介质的存储 性能有关。
6.2.1 文件逻辑结构的类型
1、有结构文件—记录式文件 （1） 定长记录：寻址简单 （2） 变长记录： ①数据项数目不同：如论文中的关键词等。 ②数据项本身长度不定，如病历中的病史。 有结构文件的组织方式： （1）顺序文件：文件中的记录按照某种顺序排列， 适合于定长记录文件 • （2）索引文件：若记录长度可变，则建立一张索 引表，每个记录一个表项，加快检索。 • （3）索引顺序文件：建立索引表，一组记录一个 表项 • • • • • • •
索引号 长度 指针 0 1 m0 m1
R0 R1
…..
Ri
索引表 逻辑文件
6.2.4 索引顺序文件 (indexed-sequential file)
• 是顺序文件和索引文件结合的产物。 • 将顺序文件中的所有记录分为若干组；为顺 序文件建立一张索引表，每组的第一个记录 在索引表中有对应表项。 • 查找任意记录时，先据关键字查索引表（此 时可采用各种查找算法），找到所在组的第 一个记录，之后顺序查找该组。
• • • • • •
文件属性： （1） 文件类型 （2） 文件长度 （3） 文件的物理位臵 （4） 文件的存取控制 （5） 文件的创建人、创建时间、修 改时间
6.1.2 文件类型
• 多种分类法： • 1）用途：系统文件、用户文件、库文件 • 2）文件中的数据形式：源文件、目标文件、 可执行代码文件。 • 3）存取属性：只执行文件、只读文件、读写 文件 • 4）文件逻辑结构：有结构文件（记录、数据 项）、无结构文件（流式文件） • 5）文件的存储结构：顺序文件、链接文件、 索引文件
• 2. 哈希文件 • 哈希文件是应用最广泛的一种直接文件。 • 记录位臵由哈希函数确定。检索时给出记录 键值，通过哈希函数计算出该记录在文件中 的相对位臵，通常是一个目录表中的表项， 该表目的内容指向相应记录所在的物理块。 • 访问速度最快，但在主文件中有空闲空间浪 费。
6.3
外存分配方式（文件实现）
• 例：若一个用户进程通过read系统调用读取 磁盘文件，则下列关于此过程的叙述正确的 是 • 1. 若该文件的数据不在内存，则该进程进入 睡眠等待状态 • 2. 请求read系统调用会导致CPU从用户态 切换到核心态。 • 3. read系统调用的参数应该包含文件的名称。 • 3是错的，因为要先open得到一个文件句柄， 之后有关文件的系统调用都用这个句柄。
连续分配
6.3.2
链接分配
• 1、隐式链接 • 分配给文件的盘块不连续，在每个簇中有指 向下一个簇的指针。目录中只存放第一和最 后一块的簇号（盘块号）。 • 解决顺序文件的离散存储的问题。 • 链接分配只适合于顺序访问， • 指针单独存放在一张表中，称文件分配表 （FAT），与文件对应的目录项中存放文件 首块的地址，表中的序号与物理块号对应。
• （3） 二级间接索引：1个，1K个一级索引 块：1K*1K*4KB=4GB。 • （4）三级间接索引：1个，1K个两次间接 索引，1K*4GB=4TB。
UNIX 混合文件存储方案
• 例：设文件索引节点中有7个地址项，其中4 个地址项是直接地址索引，2个地址项是一 级间接索引，1个地址项是二级间接索引， 每个地址项大小为4B。若磁盘索引块和磁盘 数据块大小均为256B，则可表示的单个文 件的最大长度是 • 答： 1057KB
6.2.3 索引文件(indexed file)
• 记录大小不必相同，不必排序，存放在主文 件(primary file)中。另外建立一张索引表， 每个记录在表中对应一个索引项，索引项按 照记录中的某个关键字域排序。对同一主文 件，可以针对不同的关键字域建立多个索引 表（注意：和多级索引并不相同）。索引文 件的记录项通常较小，查找速度快，便于随 机访问(random access)。
姓名 关键字 逻辑地址 A B An Bing An Kang An Qing Bao Rong Bi Jing Bon Long Z 索引文件
其它属性
顺序文件
6.2.5
直接文件和哈希文件 (hashed file）
• 1. 直接文件 • 前面几种文件结构对记录进行存取时，都须 利用给定的记录键值，先对线性表或链表进 行检索，以找到指定记录的物理地址。 • 直接文件是根据记录的键值直接就可获得记 录的物理地址。 • 组织直接文件的关键在于实现从键值到物理 地址的转换。
6.1 文件和文件系统
• 6.1.1 文件、记录和数据项 • 1、数据项 • （1）基本数据项 ：可命名的最小数据单位， 原子数据，有数据类型。--数据库中的字段。 如：学号、姓名、年龄等。 • （2）组合数据项：由若干数据项组成，如工 资。 • 2、记录：一组相关数据项集合，用于描述一 个对象在某方面的属性。主关键字（关键字） 用于标识一个记录。 •
• 3、文件 • 文件：由创建者定义，具有文件名的一组相 关元素的集合。文件名是文件的标识符号。 • 有结构文件由若干相关记录组成；无结构文 件被看成是一个字符流。 • 文件包括两部分： – 文件体：文件本身的信息； – 文件属性：文件存储和管理信息；如：文 件名、文件内部标识、文件存储地址、访 问权限、访问时间等；