当前位置：文档之家 › 第七章 文件系统

第七章 文件系统

  • 格式：ppt
  • 大小：177.00 KB
  • 文档页数：50

下载文档原格式

  / 50

合集下载

科学出版社Linux操作系统实用教程(鞠文飞编著)第7章文件系统与文件管理精品PPT课件

科学出版社Linux操作系统实用教程(鞠文飞编著)第7章文件系统与文件管理精品PPT课件
• 硬盘术语：扇区、磁道、柱面 • 分区 • Windows与Linux在分区方式上的区别 • 分区类型：主分区和扩展分，逻辑分区的编号从数字5开始。 – 例如，/dev/sda硬盘有4个主分区，其名称依次为/dev/sda1、/dev/sda2、
件系统，解决了Minix文件系统的性能问题，支持最大2TB文件 系统（Linux 2.6内核提升到32TB）。Ext2没有日志，现在基本上 已被Ext3、Ext4取代。 • ② Ext3文件系统 2001年引入Linux，在Ext2文件系统的基础上增 加了日志功能，与Ext2之间可以相互转换，性能非常稳定，可 靠性极佳。 • ③ ReiserFS文件系统 一个基于B树的文件系统，性能卓越，具 有良好的收缩性，具有日志功能。④ XFS文件系统 具备日志功 能，非常健壮，具备可伸缩性。 • ⑤ 交换文件系统 交换文件系统即虚拟内存交换空间（swap分 区）。一般不算是常规的文件系统。 • ⑥ vfat文件系统 仅用于兼容于Windows，是20世纪90年代流行 的文件系统，没有日志功能，可靠性较差，不支持文件权限。
• 利用硬盘保存数据时，需要进行分区和格式化，分区和格式 化的过程就是建立文件系统的过程。
• 类Unix操作系统大多支持VFS文件系统。VFS即虚拟文件系统， 是在传统文件系统之上的抽象层。这是一种抽象化的文件系 统概念，让用户无需关心实际使用的各种文件类型的各种复 杂性，用户可以使用标准的文件系统相关的调用（例如 read()、write()、open()、close()等）访问不同的文件系统。
7.1.2 Linux支持的文件系统
• Linux内核支持的文件系统非常广泛，包括JFS、ReiserFS、 Ext、Ext2、Ext3、ISO9660、XFS、Minix、MSDOS、 UMSDOS、VFAT、NTFS、HPFS、NFS、SMB、SysV、PROC 等。其中，ISO9660用于CD-ROM，MSDOS和VFAT用于古 老的MS-DOS和Windows系统，NTFS则是Windows操作系 统的主流文件系统，NFS为网络文件系统。在Linux操作 系统的固有的标准文件系统中，Ext4的发展前景最为光 明，此外btrfs也开始崭露头角。

科学出版社Linux操作系统实用教程(鞠文飞编著)第7章 文件系统与文件管理

科学出版社Linux操作系统实用教程(鞠文飞编著)第7章 文件系统与文件管理

• 在文件系统列显示了UUID。 UUID是通用惟一标识码，用于 唯一辨识设备。
7.3 Linux目录与文件
• Linux将所有可以访问的对象都表示为文件，其 中甚至包括进程、设备和网络连接等。 • 每个文件至少具备文件名、拥有者和访问权限 等属性。这些属性被保存在inode上。inode即 索引节点，用来保存文件的基本信息，Linux访 问文件都是通过访问inode进行的。 • 目录是保存文件和其他目录的容器，在Linux操 作系统中是一种特殊的文件，目录保存inode 和文件名列表。在图形用户界面中，目录被称 作文件夹。
第7章 文件系统与文件管理
7.1 文件系统概述
• 在类Unix领域中，存在着一个关键理念： “一切皆文件”，各种数据、设备甚至程 序进程都以文件的形式存在于文件系统中， 即使我们熟悉的文件夹，在Linux中都是作 为目录文件访问的。
7.1.1 文件系统
• 文件系统（File System）是一套用于实现数据存储、分 级组织、访问等操作的抽象数据类型。狭义的文件系统 表示存储在计算机上的文件和目录的数据结构，从计算 机数据管理和存储的角度来说，文件系统是为了长久地 存储和访问数据而为用户提供的一种基于文件和目录的 存储机制。 • 利用硬盘保存数据时，需要进行分区和格式化，分区和 格式化的过程就是建立文件系统的过程。 • 类Unix操作系统大多支持VFS文件系统。VFS即虚拟文件 系统，是在传统文件系统之上的抽象层。这是一种抽象 化的文件系统概念，让用户无需关心实际使用的各种文 件类型的各种复杂性，用户可以使用标准的文件系统相 关的调用（例如read()、write()、open()、close()等）访 问不同的文件系统。
• • • • • •
硬盘术语：扇区、磁道、柱面 分区 Windows与Linux在分区方式上的区别 分区类型：主分区和扩展分区 分区表 分区编号

第7章 文件管理

第7章 文件管理

7.2.1 文件逻辑结构的类型
1. 有结构文件 (1) 定长记录。 (2) 变长记录。 根据组织形式不同分为：
(1) 顺序文件。
(2) 索引文件。
(3) 索引顺序文件。
2. 无结构文件 如果说大量的数据结构和数据库，是采用有结构的文 件形式的话，则大量的源程序、 可执行文件、 库函数等， 所采用的就是无结构的文件形式，即流式文件。 其长度以
一类是有关目录的，如创建一个目录，删除一个目录，改变
当前目录和工作目录等；此外，还有用于实现文件共享的系 统调用和用于对文件系统进行操作的系统调用等。
7.2 文件的逻辑结构
对于任何一个文件，都存在着以下两种形式的结构： （1）文件的逻辑结构(File Logical Structure)。 (2) 文件的物理结构， 又称为文件的存储结构， 是指文 件在外存上的存储组织形式。
最先存入的记录作为第一个记录，其次存入的为第二个记
录， …… 依此类推。 第二种情况是顺序结构，指文件中的所有记录按关键 字 ( 词)排列。可以按关键词的长短从小到大排序，也可以 从大到小排序；或按其英文字母顺序排序。
2. 顺序文件的优缺点
顺序文件的最佳应用场合，是在对诸记录进行批量存取时， 即每 次要读或写一大批记录。此时，对顺序文件的存取效率是所有逻辑文 件中最高的；此外，也只有顺序文件才能存储在磁带上 , 并能有效地 工作。 如果用户(程序)要求查找或修改单个记录，为此系统便要去逐个 地查找诸记录。 这时,顺序文件所表现出来的性能就可能很差， 尤其 是当文件较大时，情况更为严重。
字节为单位。对流式文件的访问，则是采用读写指针来指
出下一个要访问的字符。可以把流式文件看作是记录式文 件的一个特例。在 UNIX 系统中，所有的文件都被看作是

第七章文件系统

第七章文件系统
18
一、空白(闲)文件目录
将文件存储设备上的每个由多个连续的空闲块组成的空 闲区看作一个空闲文件，系统为所有的空闲文件单独建立一 个目录称为空闲文件目录，每个空闲文件在这个目录中占一 个表目，记录了空闲文件的第一个空闲块的块号和空闲块的 数目 。
序号 第一个空白块号 空白块个数
物理块号
19
空白文件目录
按文件保留要求也可划分为三类： 1）临时文件。指保留用户暂时使用的文件，无副本。 2）永久文件，指保留用户经常用到的文件，有副本。 3）档案文件，指只作备份保存起来的文件，以备查证和恢 复用。
4
四、文件系统
文件系统：操作系统中负责管理文件的机构。 文件系统负责文件的创立，撤消，读写，修改，复制
和存取控制等，并管理存放文件的各种资源。
记录式文件中的记录
文件的存取方法:
等长记录。每个记录的长度都相同
变长记录。每个记录的长度不等， 文件长度则为各记录长度之和。
文件的存取方法是指：按照文件的逻辑结构存取文件的形式。 文件的存取方法是由文件的性质和用户使用文件的情况来决 定的。
根据存取的顺序关系可分为两类：顺序存取和随机存取。
顺序存取：按照文件信息的逻辑顺序依次进行读写的存取方 法称为顺序存取。采用顺序存取方法的文件称为顺序文件。
卷：存储介质的物理单位。 物理块：文件的存储设备通常划分为大小相等的物理块，物 理块是分配和传输信息的基本单位。物理块的大小与设备有 关，但与逻辑记录的大小无关。 文件的物理结构：存储文件信息的物理块的组织形式。
常用的文件物理组织方式：连续文件、链接文件和索引文件。 11
一、连续存放方式——连续文件
2、成组链接法的分配与回收过程：
首先，系统在初启时把文件资源表（专用块）复制到内

第7章 文件系统

第7章 文件系统

7.3.3 索引文件
2单级索引分配
7.3.3 索引文件
3多级索引分配
7.3.3 索引文件
4 UNIX系统文件索引结构
7.3.4 有结构文件的比较
• 有结构文件包括顺序文件、链接文件和索引文件。 • 在逻辑上，每种文件都是连续的。 • 但是，在物理结构上，只有顺序文件是连续存储数据的，而 其他方式都是离散存储的，如表7-1所示。
7.1.3 文件系统的基本概念
1 文件 •文件是由创建者所定义的、具有文件名的一组相关元素的集合 。 •文件名是文件的标识符号。 •文件包括两部分，文件体(文件本身的信息)和文件说明(文件存 储和管理信息；如：文件名、文件内部标识、文件存储地址、 访问权限和访问时间等)。 •文件属性包括文件类型、文件长度、文件的物理位置以及文件 的建立时间。
7.1.3 文件系统的基本概念
2 文件系统 •文件系统是操作系统中以文件方式管理计算机软件资源的软件 以及被管理的文件和数据结构(如目录和索引表等)的集合。 •研究文件系统的两种观点是用户观点和操作系统观点。用户观 点研究文件系统如何呈现在其面前，一个文件由什么组成，如 何命名，如何保护文件，可以进行何种操作等等。操作系统观 点研究文件目录怎样实现，怎样管理存储空间，文件存储位置 ，磁盘实际运作方式(与设备管理的接系统的概念
2 了解文件逻辑结构的分类
3 理解连续/链接/索引分配的方法
4 理解目录管理的方法
5 了解文件的共享与保护方法
求
6 6．了解数据一致性控制
You Know !
• 对用户来说，文件系统是操作系统中最直接可见的部分。计 算机的重要作用之一就是能快速处理大量信息，从而，信息 的组织、存取和保管就成为一个极为重要的内容。 • 文件系统是计算机组织、存取和保存信息的重要手段。

第07章 UNIX文件管理系统

第07章 UNIX文件管理系统

2）文件系统安装与拆卸 安装文件系统命令mount mount [option] filesystem mountpoint 说明： option可取：
-h -----输出该命令帮助信息 -V-----输出该命令版本号 -a -----按fstab文件所指位置安装所有文件系统 -F-----为设备生成一个安装点 -r-----安装的只读文件 -w----安装文件可读可写
卸载文件系统umount umount[option] filesystem option可取：
-a-----对所有在/etc/mtab中描述的文件卸载 -h-----输出帮助信息并退出 -n-----卸载时不写/etc/mtab -r-----当卸载失败时，重装成只读文件系统 -V-----输出umount版本号
• 不同用户的不同级别共享 • 父子进程对文件的共享 • 文件的链接共享 使用硬链接及符号链接的命令: % lnabc.c xyz.c % ln-s xyz.c def.c （查看结构） • 通过管道线的文件共享 管道文件的大小限定及访问特性
硬连接及符号链接原理图
返回
有关文件处理的系统调用
1.文件描述符 高级语言中的输入/输出库函数是对FILE类型的指针操 作,c语言处理中自动打开stdin,stdout,stderr三个文 件。 系统调用中用一个整形数描述打开的文件，它就是文 件描述符。
1)检索当前目录的索引节点 2)通过当前目录找到当前目录文件查 出..节点 3)检索..索引节点 4)通过..文件找到..文件查出a的索引节 点号 5)检索a的索引节点号 6)找到a的目录文件,查出b的索引节点 号 7)检索b,找到b的文件位置 8)访问文件b
3.文件共享的实现及应用 UNIX中有多种文件共享方式:

《Linux实验教程》教学课件 第7章 文件系统的设计与实现


Ext2文件系统(4)
块组描述符 – 每个块组都有一个块组描述符ext2_group_desc，记录该
块组的以下信息： – 数据块位示图。表示数据块位示图占用的块号，此位示
图反映块组中数据块的分配情况，在分配或释放数据块 时需使用数据块位示图。 – inode位示图。表示inode位示图占用的块号，此位示图反 映块组中inode的分配情况，在创建或删除文件时需使用 inode位示图。 – inode表。块组中inode占用的数据块数，系统中的每个文 件对应一个inode，每个inode都由一个数据结构来描述。 – 空闲块数、空闲inode数和已用数目。 – 一个文件系统中的所有块组描述符结构组成一个块组描 述结构表，每个块组在其超级块之后都包含一个块组描 述结构表的副本，实际上，Ext2文件系统仅使用块组1中 的块组描述结构表。
– 文件和文件系统 – 文件分类和属性 – 文件控制块和文件目录
UNIX类文件系统和非UNIX类文件系统
• UNIX类文件使用四种和文件系统相关的抽象概念： 文件、目录项、索引节点和安装点。
• 文件(file)—文件是由文件名标识的有序字节串，典 型的配套文件操作有读、写、创建和删除等。
• 目录项(dentry)—是文件路径名中的一部分。 • 索引节点(inode)—是存放文件控制信息的数据结构，
又分磁盘块中的inode和主存中活动的inode。 • 安装点(mount point)—文件系统被安装在一个特定
的安装点上，所有的已安装文件系统都作为根文件 系统树中的叶子出现在系统中。
主要内容
• 背景知识 – 文件系统基本概念 – 文件管理的数据结构 – Ext2文件系统
• 实验内容 – 模拟实现一个Linux文件系统

操作系统文件管理

➢ 对对象操纵和管理的软件集合
➢是核心部分。包括: 对文件存储空间的管理、 对文件目录的管理、用于将文件的逻辑地址转 换为物理地址的机制、对文件读和写的管理， 以及对文件的共享与保护等功能。
文件和文件系统
➢文件系统的层次结构
➢ 文件系统的接口 ➢命令接口 ➢程序接口
文件和文件系统
➢文件操作
➢ 文件的创建，打开，读写，关闭和删除和设置读/ 写位置
➢文件系统概念
➢ OS中负责管理和存取文件信息的软件机构。负责 文件的建立，撤消，存入，读写，修改和复制， 还负责完成对文件的按名存取和进行存取控制。
文件和文件系统
➢文件系统的层次结构
文件和文件系统
➢文件系统的层次结构
➢ 对象及其属性 ➢文件、目录和磁盘存储空间。
文件和文件系统
➢文件系统的层次结构
ow ner＝ c cou nt＝ 2
ow ner＝ c cou nt＝ 1
链接前
建 立 链接 后
进程B链接前后的情况
拥 有 者删 除 文 件后
文件共享
利用符号链实现文件共享
在利用符号链方式实现文件共享时， 只是文件主才 拥有指向其索引结点的指针；而共享该文件的其他用户， 则只有该文件的路径名，并不拥有指向其索引结点的指 针。
指针 pt r
…
i
mi
…
索引表
…
…
R0 R1
Ri
逻辑文件
索引顺序文件
键 An Qi Bao Rong Chen Lin
逻辑 地址
姓名 An Qi An Kang
其它 属性
Bao Rong
…
逻辑 文件
哈希(Hash)文件
目录表

第7章-汤小丹-计算机操作系统-官方课件-第四版-计算机-操作系统--课件-

12
第七章 文 件 管 理
图7-2 文件系统模型
13
第七章 文 件 管 理
1. 对象及其属性 文件管理系统管理的对象如下： (1) 文件。 (2) 目录。 (3) 磁盘(磁带)存储空间。
14
第七章 文 件 管 理
2. 对对象操纵和管理的软件集合 该层是文件管理系统的核心部分。文件系统的功能大多 是在这一层实现的，其中包括有：① 对文件存储空间的管理； ② 对文件目录的管理；③ 用于将文件的逻辑地址转换为物 理地址的机制；④ 对文件读和写的管理；⑤ 对文件的共享 与保护等功能。在实现这些功能时，OS通常都采取了层次组 织结构，即在每一层中都包含了一定的功能，处于某个层次 的软件，只能调用同层或更低层次中的功能模块。
33
第七章 文 件 管 理
2. 一级索引顺序文件 最简单的索引顺序文件只使用了一级索引。其具体的建 立方法是，首先将变长记录顺序文件中的所有记录分为若干 个组，如50个记录为一个组。然后为顺序文件建立一张索引 表，并为每组中的第一个记录在索引表中建立一个索引项， 其中含有该记录的关键字和指向该记录的指针。索引顺序文 件是最常见的一种逻辑文件形式，如图7-5
16
第七章 文 件 管 理
7.1.4 文件操作 1. 最基本的文件操作 最基本的文件操作包含下述内容： (1) 创建文件。 (2) 删除文件。 (3) 读文件。 (4) 写文件。 (5) 设置文件的读/写位置。
17
第七章 文 件 管 理
2. 文件的“打开”和“关闭”操作 当用户要求对一个文件实施多次读/写或其它操作时，每 次都要从检索目录开始。为了避免多次重复地检索目录，在 大多数OS中都引入了“打开”(open)这一文件系统调用，当 用户第一次请求对某文件进行操作时，须先利用open系统调 用将该文件打开。

操作系统文件管理


7.2.1 文件逻辑结构的类型
1.有结构文件 1.有结构文件
(1)定长记录 (2) 变长记录
2. 无结构(流式)文件
流式文件是相关信息的有序集合,或者说是有 一定意义的字符流. 对大量的源程序,可执行文件,库函数等,所采 用的就是无结构的文件形式,即流式文件 流式文件.其长 流式文件 度以字节为单位.对流式文件的访问,则是采用 读写指针来指出下一个要访问的字符.可以把流 式文件看作是记录式文件的一个特例. 好处:提供很大的灵活性
4. 外存的特点
容量大,断电后仍可保存信息, 速度较慢,成本较低 两部分组成:驱动部分+存储介质 种类很多 外存空间组织与地址与存取方式 非常复杂 I/O过程方式非常复杂
5. 用户对外存的要求
用户对外存的使用:读写外存数据 用户对外存的要求:方便,高效率,安全 (1) 在读写外存时不涉及硬件细节,使用 逻辑地址和逻辑操作 (2) 存取速度尽可能快,容量大且空间利 用率高 (3) 外存上存放的信息安全可靠,防止来 自硬件的故障和他人的侵权 (4) 可以方便地共享,动态扩缩,携带拆 卸,了解存储情况和使用情况 (5) 以尽可能小的代价完成上述要求
第七章
文件管理 与存储介质
物理块(块) 在文件系统中,文件的存储设备 常常划分为若干大小相等的物理 块.同时也将文件信息划分成相 同大小的逻辑块(块),所有块 统一编号.以块为单位进行信息 的存储,传输,分配 存储介质:磁盘,磁带,光盘
1. 磁
带
永久保存大容量数据 顺序存取设备: 前面的物理块被存取访问之后, 才能存取后续的物理块的内容, 存取速度较慢,主要用于后备存储, 或存储不经常用的信息,或用于 传递数据的介质
1) 文件系统功能
用户角度:实现"按名存取" 系统角度:是对文件存储器的存储 空间进行组织,分配,负责文件的 存储并对存入的文件实施保护,检 索的一组软件的集合.
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

（1）顺序结Biblioteka （连续结构）：将一个在逻辑上连续的文 件信息依次存放到物理块中。
特点：一个文件占有若干连续的物理块。 磁盘空间 … 块18 … 首块=18 块数=5 ... FCB 块19
块20
块21 块22
...
优点：知道文件在存储设备上的起始地址和文件长度后能快速存取。 缺点：文件一旦确定后不易改变，不利于文件的扩充和增生，且文 件进行某些部分删除后会留下无法使用的零头空间。
7.4.1 文件控制块与目录项 – 文件控制块(FCB) • 文件存在的标志，其中保存系统管理文件 需要的全部信息 – 目录项 • 目录文件中的一项，内容为FCB
7.4.2 文件目录与目录文件 – 文件目录 • 用于检索文件的目录 – 目录文件 • 内容为目录项的文件
目录项1＝FCB1
目录项2＝FCB2
7.6 文件的保护、保密与安全
• 保护：防止用户对文件进行非授权的访问 • 保密：防止文件内容泄露 • 安全：防止文件被破坏
7.6.1文件的保护 1.存取控制矩阵
f1 …… fj …… fn
u1 a11….… a1j ……. a1n
… … …… … …… ... ui ai1 …… aij ….… ain … … …… … …… ... um am1 ….. amj ….… amn 优点：简单，一目了然
2.二级目录
二级目录结构主要由主目录（系统目录）和用户文件目录构成，所有 的用户目录均登记于系统目录中，每个用户目录下登记着该用户 的文件。 优点：较好地解决了重名问题，并且使搜索时间变短。 缺点：不能将文件加以分类；当用户文件较多时其查找速度仍比较慢。 wang的文件目录
主目录
用户名 其它 始址 … wang zhang … … … … … … …
FCB主部 … 文件号 … 共享计数 … 修改标志 …
2.用户打开文件表
文件描述符 打开方式 读/写指针 系统打开文件表入口
… … … ……
3.用户打开文件表与系统打开文件表之间的联系
其他 系统打开文件表入口 … … … … 共享计数 … 2 … 其他 … … …
进程P1的用户打开文件表 其他 系统打开文件表入口 … … … …
顺序探查法：如发生冲突，则在冲突位置开始顺序探查 第一个空闲的存储位置。 …
hash(key)=addr：
冲突计数 空闲标志
原记录内容 （包括key）
一个记录
…
保存记录：
计算addr=hash(key) 对应冲突记数加1 T
本记录空闲
F
标记为占用 填记录内容
顺取下一个
查找记录：
计算addr=hash(key)
系统打开文件表
进程P2的用户打开文件表
7.7.2 外存空间的管理
1.空闲块表
首空闲块 空闲块数 12 7 38 27 96 4 0 －
2.空闲块链
…
块12
…
块27
…
块38 块39
…
3.字位映像图
1 0 … 1 … 0
7.8 文件系统的界面
1.创建文件 命令形式：creat(path_name,fcb_args) 参数含义：path_name:文件路径名 fcb_args:FCB中的其他参数 2.打开文件 命令形式：fd=open(path_name,mode) 参数含义： path_name:文件路径名 mode:打开方式 3.关闭文件 命令形式：close(fd) 参数含义：fd:文件描述符
编号： 0 1 … … k
记录
记录 记录
… …
n-1
记录
读/写指针
注：流式文件是记录式文件的特例。
7.3.2 文件的物理组织 1.文件的物理结构又称文件的存储结构，指文件在外存上 的存储组织形式。 • 考虑因素 – 记录格式 • 等长或不等长, 流式不必考虑 – 空间开销 • 除保存文件内容之外的存储开销 – 访问速度 • 随机访问速度 – 长度变化 • 动态增长 2.文件的物理结构有：顺序结构、链接结构、索引结构、 散列结构、倒排结构
学生档案
No. 9005011 9005032 9005040 9005045 9005023 记录地址 5274 2189 3092 2010 1098
Dept 计算机 化学 数学 经济
记录地址 5274,2010 3092 2189 1098
以No.为主键的主索引
以Dept.为主键的主索引
7.4 文件目录
…
目录项n＝FCBn
文件目录
7.4.3 单级目录和多级目录 1.单级目录 单级目录结构把系统中的所有文件都建立在一目 录下，每个文件占用其中一个目录项。当建立 文件时，就在文件目录下增加一个空的目录项， 并填入相应的内容；当删除一个文件时，根据 文件名查找相应的目录项，找到对应的目录项 后将内容全部置空。 优点：简单。 缺点：文件说明项只能按顺序存放，文件重名， 搜索效率低。
7.4.5 根目录与当前目录（自学） 7.4.6 文件目录的查找 1.由根目录开始查找 2.由当前目录开始查找 查找算法： （1）顺序查找 （2）Hash查找 （3）对分查找
7.5 文件的共享
7.5.1 文件共享的目的 – 节省存储空间 – 进程相互通讯 7.5.2 文件共享的模式 – 不同时使用 – 同时使用 7.5.3 文件共享的实现 – 公共目录 – 连接 – 共享说明
取addr对应记录的冲突记数count
T 无此记录
count=0
T
F 本记录空闲 F
key=key’?
顺取下一记录
T
找到
F
T
h(key)=h(key’)? F
count:=count-1
T
count=0 F 顺取下一记录
无此记录
删除记录：
调用查找过程(key)
F
错误返回
找到
T
置空闲标志 (找到记录)
（2）链接结构（串联结构）：用非连续的物理块来存放信息，物 理块之间没有物理块号的顺序，其中每个物理块中有一个指针， 指向其后续的另一个物理块，从而使得存放同一个文件的物理 块连接成一个串联队列。
磁盘空间
…
块18 … 首块=18 块数=3 ... FCB ... ... 块80
...
块92
特点：一文件可存于不连续块中，块间以指针相连。 优点：不必在文件说明信息中指明文件的长度，只需指 明文件第一个块号即可，文件长度可以动态增长，只 要调整连接指针就可以在任何一个信息块之间插入或 删除一信息块。 缺点：只能按队列中的指针顺序搜索，效率较低，而且 只能顺序存取，不能随机存取。
7.3 文件的组织
7.3.1 文件的逻辑组织 一、流式文件（无结构文件） 无结构的流式文件是相关的有序字符的集合，文件的长 度即为所含的字符数。如：源程序文件和目标代码程 序等。
编号： 0 1 … … k 字节 … … n-1 字节
字节 字节
读/写指针
二、记录式文件（有结构文件） 有结构的记录式文件即由若干个相关的记录构成的文件。 如果文件中所有记录的长度都相等，则称为等长记录文件； 如果文件中各记录的长度不相等，则称为变长记录文件。 文件的长度即为各记录的长度之和。
第七章 文件系统
7.1 文件与文件系统
一、文件的概念 1.定义：文件是具有符号名而且在逻辑上具有完整意义的 信息项的序列。
编号：
0
1
信息项
…
…
k
信息项
…
…
n-1
信息项
信息项
读(写)指针 2.文件的分类 二、文件系统 定义：文件与管理文件的程序集合称文件系统。
7.2 文件的访问方式
一、顺序访问 • 从文件起始位置开始顺序访问 • 从文件中间某处开始顺序访问 二、随机访问 • 按记录编号随机访问 • 按关键字随机访问
[例]设散列函数h(n)=(676*l1+26*l2+l3)(mod t)，t＝11，li为键n的第i个 英文字母序号。键表长11，键名为英文字母。按线性散列法计算将 任意7个键放入链表中所用的计算次数。这里令a＝2，c＝1。 解：设7个关键字分别为：zhl，ouy，lwj，yks，lxz，suy，hls 则有：h(n)=(767*l1+26*l2+l3) mod 11 （1）线性散列法：hi(k)=(h1(k)+2i) mod 11 h(zhl)=(676*26+26*8+12) mod 11＝9 h(ouy)=(676*15+26*21+25) mod 11 =8 h(lwj)=(676*12+26*23+10) mod 11=8 h2＝（8+2*2） mod 11＝1 h(yks)=(676*25+26*11+19) mod 11=1 h2＝（1+2*2） mod 11＝5 h(lxz)=(676*12+26*24+26) mod 11=6 h(suy)=(676*19+26*21+25) mod 11=6 h2＝（6+2*2） mod 11＝10 h(hls)=(676*8+26*12+19) mod 11＝8 h2＝（8+2*2）mod 11＝1 h3＝（8+2*3）mod 11＝3
4.指针定位 命令形式：seek(fd,offset) 参数含义：fd:文件描述符 offset:新的指针定位 5.读文件 命令形式：read(fd,nrcd,buf) 参数含义：fd:文件描述符 nrcd:读入记录个数 buf：内存起始位置 6.写文件 命令形式：write(fd,nrcd,buf) 参数含义： （同上）
aij:
R W E A M D