操作系统：07第七章 文件系统

1、第七章第七章 文件系统文件系统n OS 实现系统资源管理实现系统资源管理: 硬件资源、软件资源硬件资源、软件资源;n 软件资源软件资源: 程序、数据程序、数据;n 文件管理文件管理: 软件资源以文件形式存于外存空间软件资源以文件形式存于外存空间, 软件资源管理通常称为文件管理软件资源管理通常称为文件管理;n 文件管理由文件系统来完成文件管理由文件系统来完成;n 文件系统在设备管理之上。文件系统在设备管理之上。1. 文件的概念文件的概念 文件文件: 具有具有符号名符号名而且在逻辑上具有完整意义的而且在逻辑上具有完整意义的 信息项的有序序列。信息项的有序序列。7.1 文件与文件系统文件与文件系统7

2、.1.1 文文 件件编号编号:01kn-1信息项信息项信息项信息项信息项信息项信息项信息项文件名文件名: 符号名符号名, 文件创建时确定文件创建时确定, 访问时用访问时用;信息项信息项: 构成文件的基本单位构成文件的基本单位; 等长或不等长等长或不等长; 有顺序关系有顺序关系;读读/写指针写指针: 信息项的读信息项的读/写位置写位置;读读/写指针写指针2. 文件分类文件分类l 系统文件系统文件, 用户文件用户文件; l 临时文件临时文件, 永久文件永久文件; l 只读文件只读文件, 只写文件只写文件, 读读/写文件写文件;l 磁盘文件磁盘文件, 磁带文件磁带文件, 磁鼓文件磁鼓文件; l 目录

3、文件目录文件, 普通文件普通文件; l 程序文件程序文件, 数据文件数据文件;l 程序文件程序文件 源文件源文件, 目标文件目标文件, 可执行文件可执行文件, 头文件头文件, 库文件。库文件。7.1.1 文文 件件 UNIX文件分类文件分类n 普通文件普通文件: 内容可以是程序、数据、图象等内容可以是程序、数据、图象等, 保存在磁盘块中保存在磁盘块中;n 目录文件目录文件: 文件描述信息文件描述信息(文件名文件名, 文件号文件号)序列序列, 保存在磁盘块中保存在磁盘块中;n 特殊文件特殊文件: 将各种设备作为文件处理。将各种设备作为文件处理。l 界面统一界面统一, 使用文件与使用设备命令相同使

4、用文件与使用设备命令相同, 申请设备申请设备open, 释放释放close, 读读read, 写写write;l 利用文件保护功能可以保护设备。利用文件保护功能可以保护设备。7.1.1 文文 件件7.1.2 文件系统文件系统文件系统文件系统: 文件与管理信息资源的程序集合文件与管理信息资源的程序集合 称为文件系统。称为文件系统。l 为用户提供按名存取文件的手段为用户提供按名存取文件的手段; l 文件的组织形式文件的组织形式;l 外存空间的管理外存空间的管理;l 处于设备管理上层。处于设备管理上层。7.2 文件的访问方式文件的访问方式7.2.1 顺序访问顺序访问: 磁带磁带l 从文件起始位置开始

5、顺序访问从文件起始位置开始顺序访问;l 从文件中间某处开始顺序访问。从文件中间某处开始顺序访问。7.2.2 随机访问随机访问: 磁盘、光盘磁盘、光盘l 按信息项编号随机访问按信息项编号随机访问;l 按关键字按关键字(key)随机访问。随机访问。7.3 文件的组织文件的组织n 文件的组织文件的组织: 又称文件结构又称文件结构;n 逻辑组织逻辑组织: 外部组织形式外部组织形式, 用户看到的文件组织形式。用户看到的文件组织形式。n 物理组织物理组织: 内部组织形式内部组织形式, 物理存储设备上的组织形式。物理存储设备上的组织形式。n OS完成逻辑组织形式到物理组织形式的转换。完成逻辑组织形式到物理组

6、织形式的转换。7.3.1 文件的逻辑组织文件的逻辑组织1. 流式文件流式文件l 非结构形式的字节序列非结构形式的字节序列(UNIX, Windows, etc);l 构成文件的基本单位是字节。构成文件的基本单位是字节。l 用户可以对非结构的流式文件用户可以对非结构的流式文件 按自定义的结构来处理。按自定义的结构来处理。编号编号:01kn-1字节字节字节字节字节字节字节字节读读/写指针写指针7.3.1 文件的逻辑组织文件的逻辑组织(Cont.)2. 记录式文件记录式文件: 记录的序列记录的序列l 等长记录等长记录(优点优点: 处理方便处理方便, 速度快速度快; 缺点缺点: 空间浪费空间浪费);l

7、 不等长记录不等长记录(优点优点: 省空间省空间; 缺点缺点: 处理不便处理不便, 速度慢速度慢);l 流式文件是记录式文件的特例。流式文件是记录式文件的特例。编号编号:01kn-1记录记录记录记录记录记录记录记录读读/写指针写指针7.3.2 文件的物理组织文件的物理组织n 物理组织物理组织: 逻辑组织到磁盘块的映射。逻辑组织到磁盘块的映射。文件文件: 记录记录(字节字节)序列序列磁盘磁盘: 块块(block)序列序列n 考虑因素考虑因素: 记录格式记录格式: 等长或不等长等长或不等长, 流式不必考虑流式不必考虑; 空间开销空间开销: 除保存文件内容之外的存储开销除保存文件内容之外的存储开销;

8、 访问速度访问速度: 顺序顺序/随机访问速度随机访问速度; 长度变化长度变化: 动态增长动态增长/减少。减少。n 组织形式组织形式: 顺序结构、链接结构、索引结构、散列结构、倒排结构。顺序结构、链接结构、索引结构、散列结构、倒排结构。7.3.2 文件的物理组织文件的物理组织(Cont.) 顺序结构顺序结构 又称连续结构。又称连续结构。一个文件占有若干连续的磁盘块。一个文件占有若干连续的磁盘块。FCB首块号首块号28块数块数4块块28块块29块块30块块31磁盘空间磁盘空间优优 点点: 速度快速度快, 节省空间节省空间; 缺缺 点点: 长度变化困难。长度变化困难。 链接结构：链接结构：又称串联结

9、构又称串联结构, 一文件可存于不连续块中一文件可存于不连续块中, 块间以指针相连。块间以指针相连。7.3.2 文件的物理组织文件的物理组织(Cont.)优优 点点: 长度变化容易。长度变化容易。缺缺 点点: 随机访问速度慢。随机访问速度慢。FCB首块号首块号28块数块数4块块28块块30块块45块块46磁盘空间磁盘空间7.3.2 文件的物理组织文件的物理组织(Cont.) 索引结构索引结构 一文件可存于不连续块中一文件可存于不连续块中, 块号记在索引块中。块号记在索引块中。优优 点点: 随机访问速度快随机访问速度快; 长度变化容易。长度变化容易。缺缺 点点: 额外需要索引块额外需要索引块, 存

10、储开销大存储开销大; FCB索引块号索引块号28块数块数4块块43块块87块块97块块98磁盘空间磁盘空间0431872973984索引块索引块287.3.2 文件的物理组织文件的物理组织(Cont.) 散列结构散列结构 适用于定长记录和按键随机查找的访问方式适用于定长记录和按键随机查找的访问方式; 通常用于构造文件目录通常用于构造文件目录, 一个记录内容就是一个目录项。一个记录内容就是一个目录项。n 计算地址计算地址: hash(key)=addr (在磁盘或文件中的存放位置在磁盘或文件中的存放位置)7.3.2 文件的物理组织文件的物理组织(Cont.)n 问问 题题: 给定给定 key1

11、key2 , 有有 hash(key1) = addr1 , hash(key2) = addr2 , 若若addr1=addr2 , 则发生则发生conflict 。n Conflict resolution: l 顺序探查法顺序探查法: 如发生冲突如发生冲突, 则在冲突位置开始则在冲突位置开始 顺序探查第一个空闲的存储位置顺序探查第一个空闲的存储位置。l 记录中增加两个域记录中增加两个域: 冲突计数冲突计数; 记录位置的空闲标志。记录位置的空闲标志。7.3.2 文件的物理组织文件的物理组织(Cont.) 保存记录保存记录: 保存记录的键值为保存记录的键值为 key .地址地址空闲空闲标志标

12、志冲突冲突计数计数addr:12键值键值key记录内容记录内容1键值键值key1记录内容记录内容Hash(key)=addr文件空间文件空间保存记录保存记录 key计算计算hash(key) addr, adaddr对应的记录位置对应的记录位置冲突记数加冲突记数加1位置位置 ad 空闲空闲?ad指向下一个指向下一个记录位置记录位置ad记录位置标记为占用记录位置标记为占用记录记录key内容内容ad记录位置记录位置保存记录保存记录 key结束结束FT7.3.2 文件的物理组织文件的物理组织(Cont.) 查找记录查找记录: 查找键值为查找键值为key的记录。的记录。查找记录查找记录keyhash(

13、key)ad,addr取取ad对应记录的冲突记数对应记录的冲突记数countad记录键值记录键值=keycount-count=0找到结束找到结束未找到结束未找到结束ad记录空闲记录空闲hash(ad.key)=addrcount=0ad指向下一个指向下一个记录位置记录位置FFFFFTTTTT7.3.2 文件的物理组织文件的物理组织(Cont.) 删除记录删除记录: 删除键值为删除键值为key的记录。的记录。删除记录删除记录key调用调用“查找记录查找记录key”找到找到key?记录记录key不存在不存在返回返回addr=hash(key)ad.空闲标志空闲标志=0addr.冲突计数减冲突计数

14、减1删除记录删除记录key返回返回FT特点特点:按关键字检索速度快。按关键字检索速度快。用途用途:常用于目录检索。常用于目录检索。注意注意:Hash空间可循环使用空间可循环使用, 满时保存失败。满时保存失败。7.3.2 文件的物理组织文件的物理组织(Cont.)5. 倒排结构倒排结构 l 键键: 记录中的域称为键记录中的域称为键;l 主键主键: 记录中能唯一区分文件中所有记录的键记录中能唯一区分文件中所有记录的键 称为主键称为主键; 其它键称为其它键称为次键次键。l 倒排结构倒排结构: 以键值和记录地址构成的索引结构以键值和记录地址构成的索引结构 称为倒排结构。称为倒排结构。l 主索引主索引:

15、 键值为主键的索引称为主索引键值为主键的索引称为主索引;l 次索引次索引: 键值为次键的索引称为次索引。键值为次键的索引称为次索引。7.3.2 文件的物理组织文件的物理组织(Cont.)表表7-1 各种文件物理结构的主要特性各种文件物理结构的主要特性特性特性 物理物理 结构结构长度长度变化变化内存内存开销开销外存外存开销开销顺序访问速度顺序访问速度按号随机访问速度按号随机访问速度 按键随机访问速度按键随机访问速度定长定长变长变长定长定长变长变长定长定长变长变长顺序结构顺序结构难难小小小小快快快快快快慢慢慢慢慢慢链接结构链接结构易易小小小小快快快快慢慢慢慢慢慢慢慢索引结构索引结构易易大大大大快快

16、快快快快慢慢慢慢慢慢散列结构散列结构易易小小小小快快倒排结构倒排结构易易大大大大快快快快UNIX文件物理结构文件物理结构 P389390)i_addr0i_addr9i_addr10i_addr11i_addr12i_node文件最大长度文件最大长度=10+256+2562+2563(块块)多级索引多级索引+链接结构链接结构信息块信息块索引块索引块7.3.2 文件的物理组织文件的物理组织(Cont.)例：例：在在UNIX系统中，设磁盘物理块大小为系统中，设磁盘物理块大小为1KB，每个索引块可以，每个索引块可以 保存保存256个索引项。假设某个索引项。假设某UNIX文件大小为文件大小为1028K

17、B。 请画出该请画出该UNIX文件的物理结构；文件的物理结构； 计算访问以下逻辑块号（逻辑块号从计算访问以下逻辑块号（逻辑块号从0开始）时，开始）时， 需要多少次需要多少次I/O传输：传输： 265； 266； 1025。解：解： 零级索引和一级索引能保存的块数零级索引和一级索引能保存的块数10256266块；块； 剩下的剩下的1028266762块，可用二级索引。块，可用二级索引。 7622562+250，即占用二级索引的，即占用二级索引的3个索引项。个索引项。 该文件的该文件的UNIX物理结构如图所示。物理结构如图所示。 根据文件的物理结构，访问逻辑块号根据文件的物理结构，访问逻辑块号 2

18、65需要需要2次次I/O； 266需要需要3次次I/O ； 1025需要需要3次次I/O7.3.2 文件的物理组织文件的物理组织(Cont.)i_addr0i_addr9i_addr10i_addr11i_addr12i_nodenull。逻辑块逻辑块0 0逻辑块逻辑块9 9逻辑块逻辑块1010逻辑块逻辑块265265。逻辑块逻辑块266266逻辑块逻辑块521521逻辑块逻辑块522522逻辑块逻辑块777777逻辑块逻辑块778778逻辑块逻辑块10271027。null250块256块256块256块给定的给定的UNIX文件的物理结构文件的物理结构7.3.2 文件的物理组织文件的物理组织

19、(Cont.)7.4 文件目录文件目录7.4.1 文件控制块与目录项文件控制块与目录项1. 文件控制块文件控制块(FCB)l 文件存在的标志文件存在的标志, 其中保存系统管理文件需要的全部信息其中保存系统管理文件需要的全部信息;l 每个文件一个每个文件一个FCB, 保存在外存保存在外存;l 建立文件时创建建立文件时创建, 删除文件时撤销。删除文件时撤销。2. 目录项目录项l 目录文件中的一项目录文件中的一项, 内容为内容为FCB;l 通常目录项名为文件名。通常目录项名为文件名。7.4.2 文件目录与目录文件文件目录与目录文件1. 文件目录文件目录l 用于检索文件的目录用于检索文件的目录;l 目

20、录项构成的有序序列目录项构成的有序序列;l 给定一个文件名给定一个文件名, 通过查找文件目录找到相应的目录项通过查找文件目录找到相应的目录项(FCB)。2. 目录文件目录文件l 内容为目录项的文件内容为目录项的文件, 长度固定的记录式文件长度固定的记录式文件;l 实现文件目录的管理。实现文件目录的管理。文件控制块文件控制块FCB文件名文件名文件号文件号用户名用户名文件地址文件地址文件长度文件长度记录大小记录大小文件类型文件类型文件属性文件属性共享说明共享说明文件逻辑结构文件逻辑结构文件物理结构文件物理结构建立日期建立日期保存日期保存日期最后修改日期和时间最后修改日期和时间最后访问日期和时间最后

21、访问日期和时间口令口令其它其它目录项目录项1(FCB1)目录项目录项2 (FCB2)目录项目录项n (FCBn)目录文件目录文件n 目录目录, 文件图示文件图示 :文文件件目目录录7.4.2 文件目录与目录文件文件目录与目录文件(Cont.)7.4.3 单级目录与多级目录单级目录与多级目录1. 单级目录单级目录(Single-Level Directory) 整个系统只有一个目录整个系统只有一个目录, 所有文件均登记在该目录中。所有文件均登记在该目录中。FCB1FCB2FCBiFCBnfile1file2fileifilen目录文件目录文件普通文件普通文件单级目录结构单级目录结构缺点缺点: N

22、aming problem; Grouping problem Protection problem.单级目录例单级目录例:7.4.3 单级目录与多级目录单级目录与多级目录(Cont.)2. 二级目录二级目录(Two-Level Directory)l 系统目录系统目录(公共目录公共目录), 用户目录用户目录(私用目录私用目录);l 为每个用户单独设置目录。为每个用户单独设置目录。FCB1 FCBj用户目录用户目录普通文件普通文件USER1USERiUSERkFCB1 FCBmFCB1 FCBn系统目录系统目录二级目录结构二级目录结构7.4.3 单级目录与多级目录单级目录与多级目录(Cont.

23、)二级目录例二级目录例:特点特点: Path name; Can have the same file name for different user; Efficient searching; No grouping capability.7.4.3 单级目录与多级目录单级目录与多级目录(Cont.)3. 多级目录多级目录(Multi-Level Directory)l 目录为树形结构目录为树形结构;l 叶结点是一般文件或目录文件叶结点是一般文件或目录文件;l 非叶结节点是目录文件非叶结节点是目录文件;l 根结点称作根目录文件。根结点称作根目录文件。优点优点:l 便于文件分类便于文件分类;l

24、 查找速度快查找速度快(由于每个文件目录下文件少由于每个文件目录下文件少);l 可以实现文件连接可以实现文件连接(Link)。7.4.3 单级目录与多级目录单级目录与多级目录(Cont.)多级目录例多级目录例:rootUnixbinusrlibdevetcVIusersWangLiSd1d2f1flibclibCClpConsolebinYaccPasswordf27.4.3 单级目录与多级目录单级目录与多级目录(Cont.)n 将将FCB分为次部和主部两部分。分为次部和主部两部分。l 次部次部: (文件名文件名, 文件号文件号) u长度固定长度固定(UNIX 16 bytes);u保存在目录

25、文件中。保存在目录文件中。l 主部主部: (其它其它, 连接记数连接记数)u记录长度固定记录长度固定(UNIX 32 bytes);u保存在外存固定区域保存在外存固定区域, 打开时读入内存打开时读入内存;u给定文件号给定文件号, 可计算主部位置。可计算主部位置。改进的好处改进的好处l 可以提高查找速度可以提高查找速度(顺序查找顺序查找)l 可以实现文件连接可以实现文件连接(link)7.4.4 文件目录的改进文件目录的改进改进的文件目录图示改进的文件目录图示:文件号文件号FCB主部主部1FCB1主部主部2FCB2主部主部nFCBn主部主部目录项目录项1(FCB1次部次部)目录项目录项2 (FC

26、B2次部次部)目录项目录项n (FCBn次部次部)文件目录文件目录目目录录文文件件7.4.4 文件目录的改进文件目录的改进(Cont.)l 顺序查找顺序查找n个记录，个记录， 找到一个记录的平均查找记录的次数找到一个记录的平均查找记录的次数 =(1+2+n)/n=(n+1)/2l 设未分次部和主部的设未分次部和主部的FCB构成的文件目录占构成的文件目录占n个磁盘块，个磁盘块， 则顺序查找文件目录，找到一个文件目录的平均访问磁盘则顺序查找文件目录，找到一个文件目录的平均访问磁盘块的次数块的次数=(n+1)/2 l 设次部构成的文件目录占设次部构成的文件目录占m个磁盘块，则顺序查找文件目个磁盘块，

27、则顺序查找文件目录，找到一个文件的平均访盘次数录，找到一个文件的平均访盘次数(m+1)/2+17.4.4 文件目录的改进文件目录的改进(Cont.)7.4.5 根目录与当前目录根目录与当前目录1. 根目录根目录 树状结构树状结构(多级目录多级目录)文件系统中文件系统中, 根结点对应的目录称为根目录根结点对应的目录称为根目录; 根目录保存在外存空间固定位置根目录保存在外存空间固定位置。2. 当前目录当前目录 目前正在使用的工作目录称为当前目录。目前正在使用的工作目录称为当前目录。n 查找路径查找路径l 由根目录开始查找由根目录开始查找;l 由当前目录开始查找。由当前目录开始查找。n 查找算法查找

28、算法l 顺序查找顺序查找(UNIX);l hash查找查找;l 对分查找对分查找(要求文件名排序要求文件名排序)。7.4.6 文件目录的查找文件目录的查找7.5 文件的共享文件的共享文件共享文件共享: 多个进程共用系统中的同一个文件多个进程共用系统中的同一个文件; 操作系统和文件使用者共同完成文件共享控制。操作系统和文件使用者共同完成文件共享控制。7.5.1 文件共享的目的文件共享的目的 节省存储空间节省存储空间: cc, vi, yacc 的共享的共享; 进程相互通信进程相互通信7.5.2 文件共享的模式文件共享的模式1.异步使用同一文件异步使用同一文件: 任意时刻只能有一个进程任意时刻只能

29、有一个进程使用一个文件使用一个文件;2.同时使用同一文件同时使用同一文件: 多个进程可以同时使用同多个进程可以同时使用同一个文件一个文件(R/W规则规则)。7.5.3 文件共享的实现文件共享的实现1. 公共目录公共目录: 系统设若干所有用户都能访问的公共目录系统设若干所有用户都能访问的公共目录, 共享文件登记在公共目录中共享文件登记在公共目录中;2. 连连 接接: 通过连接使一个文件具有多个名字通过连接使一个文件具有多个名字, 不同用户通过不同名字访问同一个文件不同用户通过不同名字访问同一个文件;3. 共享说明共享说明: 创建文件时规定共享用户及其使用权限。创建文件时规定共享用户及其使用权限。

30、7.5 文件的共享文件的共享(Cont.)7.5 文件的共享文件的共享(Cont.)文件共享实现链接例文件共享实现链接例:rootusruserswanglid1d2f1f2, 15f1, 15i_number=15link(“/usr/users/wang/d2/f1”, “/usr/users/li/f2”);unlink(“/usr/users/wang/d2/f1”);7.6 文件的保护、保密与安全文件的保护、保密与安全n 保护保护: 防止用户对文件进行非授权的访问。防止用户对文件进行非授权的访问。n 保密保密: 防止文件内容泄露。防止文件内容泄露。n 安全安全: 防止文件被破坏。防止

31、文件被破坏。l 自然因素自然因素l 人为因素人为因素7.6.1 文件的保护文件的保护(Protection)n File owner/creator should be able to control:l what can be done;l by whom .n Types of accessl Readl Writel Executel Appendl Deletel List7.6.1 文件的保护文件的保护(Protection) 存取控制矩阵存取控制矩阵: amn ， m个用户个用户, n个文件。个文件。f1fjfnu1a11a1ja1nuiai1aijainumam1amjamnai

32、j :rweamd特点特点: 权限规定细权限规定细, 过于繁琐过于繁琐, 占较多存储空间。占较多存储空间。7.6.1 文件的保护文件的保护(Protection)n 用户分成若干类用户分成若干类;n 同类用户对同一文件访问权限相同同类用户对同一文件访问权限相同;n 不同类用户对同一文件访问权限不同不同类用户对同一文件访问权限不同;n UNIX 用户分类用户分类 4类类: 文件主文件主, 同组用户同组用户, 其它用户其它用户, 特权用户。特权用户。 访问权限说明访问权限说明 RWERWERWE文件主权限文件主权限同组用户权限同组用户权限其他用户权限其他用户权限特权用户权限特权用户权限访问权限说明

33、访问权限说明7.6.1 文件的保护文件的保护(Protection) 分级目录分级目录n 多级目录系统中多级目录系统中, 规定不同用户对同一子目录的访问权限规定不同用户对同一子目录的访问权限;n 如果用户不能访问某一目录如果用户不能访问某一目录, 即该用户不能访问该目录下的任何文件。即该用户不能访问该目录下的任何文件。7.6.2 文件的保密文件的保密 口令口令n 创建文件时用户规定一个口令创建文件时用户规定一个口令, 系统将其记在系统将其记在FCB中中;n 访问文件要求给出口令访问文件要求给出口令, 并与并与FCB中口令比较。中口令比较。 特点特点: 简单简单; 保密性不强保密性不强(eg.

34、对系统操作员不保密对系统操作员不保密)。 密码密码n 保存时加密保存时加密(key);n 读取时解密读取时解密(key). 特点特点: 对文件内容加密对文件内容加密, 速度慢速度慢; 效果好。效果好。n 文件加文件加/解密简单实现解密简单实现l 保存时保存时, 用一个用一个key启动一个随机数发生器启动一个随机数发生器, 产生一个产生一个 随机数序列随机数序列, 将其依次将其依次“添加添加”到文件的各个字中。到文件的各个字中。l 读取时读取时, 用同一个用同一个key启动同一个随机数发生器启动同一个随机数发生器, 产生产生 相同随机数序列相同随机数序列, 将其依次由文件的各个字中将其依次由文件

35、的各个字中”减去减去” 。n 线性同余法产生伪随机数：线性同余法产生伪随机数： void random(int *key) *key = (*key)*C1+C2) % C3; 7.6.2 文件的保密文件的保密(Cont.)C1, C2是质数常量是质数常量, C3是随机数范围是随机数范围(0C3-1);key通常叫随机源通常叫随机源, 也叫种子也叫种子, 它决定产生的随机数序列的随机性。它决定产生的随机数序列的随机性。7.6.3 文件系统的安全文件系统的安全n Backupl 定期将磁盘上文件备份到磁带上定期将磁盘上文件备份到磁带上;l 发生故障时由磁带恢复发生故障时由磁带恢复(limited

36、 recovery)。 n实现方法实现方法 转储转储: 文件由磁盘备份到磁带的过程文件由磁盘备份到磁带的过程; 1. 完全转储完全转储: 定期将磁盘上文件全部备份到磁带上定期将磁盘上文件全部备份到磁带上;2. 增量转储增量转储: 开始时做一次完全转储开始时做一次完全转储; 之后之后, 每次只对与上次每次只对与上次不同的不同的数据进行备份。数据进行备份。3. 差分转储差分转储: 开始时做一次完全转储开始时做一次完全转储; 之后之后, 每次只对与第一次不同的数据进行备份。每次只对与第一次不同的数据进行备份。n磁盘整理磁盘整理l 利用转储和恢复可以对磁盘进行整理。利用转储和恢复可以对磁盘进行整理。

37、(使文件物理块连续使文件物理块连续, 空闲盘块连续空闲盘块连续)7.7 文件系统的实现文件系统的实现7.7.1 内存所需的表目内存所需的表目 系统打开文件表系统打开文件表(系统一个系统一个): 存于存于OS空间空间FCB主部主部文件号文件号共享计数共享计数修改标志修改标志 文文 件件 号号 : 用于确定用于确定FCB主部在外存中的位置主部在外存中的位置; 共享计数共享计数 : 记录使用该文件的进程个数记录使用该文件的进程个数, 为为0时表示该表项为空表项时表示该表项为空表项; 修改标志修改标志 : 若若FCB被修改过被修改过, 则关闭文件时需要把内存的则关闭文件时需要把内存的FCB写回外存。写

38、回外存。7.7.1 内存所需的表目内存所需的表目(Cont.) 用户打开文件表用户打开文件表文件文件描述符描述符打开方式打开方式读写指针读写指针入口入口(地址地址)0n-1n 文件描述符文件描述符就是用户打开文件表项位置就是用户打开文件表项位置( (非负整数非负整数),), 打开文件时返回给进程打开文件时返回给进程; ;n 用户打开文件表位置存在进程用户打开文件表位置存在进程PCBPCB中中; ;n 系统可以单设系统可以单设 空间空间, , 也可以放在进程的也可以放在进程的PCBPCB中。中。读写指针应该读写指针应该是文件的逻辑是文件的逻辑地址，初值应地址，初值应为为0 0，随着读，随着读写调

39、整。写调整。 用户打开文件表用户打开文件表/系统打开文件表的联系系统打开文件表的联系文件文件描述符描述符打开方式打开方式读写指针读写指针入入 口口kl用户打开文件表用户打开文件表进程进程Pi文件文件描述符描述符k进程进程Pj文件文件描述符描述符lPCB共享计数共享计数 其它其它2系统打开文件表系统打开文件表7.7.1 内存所需的表目内存所需的表目(Cont.)n 表项表项: (首空闲块号首空闲块号, 空闲块数空闲块数); n 表尾标记表尾标记: 空闲块数为空闲块数为0;n 分配方式分配方式: 最先适应最先适应, 下次适应、最佳适应下次适应、最佳适应, 最坏适应等最坏适应等;n 存放位置存放位置

40、: 平时外存平时外存, 使用时读入内存系统区。使用时读入内存系统区。 空闲块表空闲块表: 适于连续物理组织结构的文件系统。适于连续物理组织结构的文件系统。 空闲块链空闲块链n 所有空闲块连成一个链所有空闲块连成一个链; n 申请申请/释放以块为单位释放以块为单位, 都对链头操作都对链头操作;n 节省空间节省空间, 但速度慢但速度慢(申请申请/释放都需要释放都需要1次次I/O);7.7.2 外存空间的管理外存空间的管理7.7.2 外存空间的管理外存空间的管理(Cont.) 位示图位示图: 字位映像图字位映像图 n 位示图的位示图的 1 位表示外存一块的状态位表示外存一块的状态; n 申请申请:

41、找到位示图中为找到位示图中为 0 的字位的字位, 将该字位改为将该字位改为 1 , 返回该字位对应的块号返回该字位对应的块号;n 释放释放: 将位示图中释放块号对应的字位置将位示图中释放块号对应的字位置 0;n 存放位置存放位置: 平时外存平时外存, 使用时读入内存使用时读入内存, 若有修改写回外存。若有修改写回外存。 成组链接成组链接(Unix): 空闲块链与空闲块表的结合。空闲块链与空闲块表的结合。n 多个多个(最多最多100个个) 空闲块为空闲块为1组组, 组之间相互链接组之间相互链接;n 最前面的组缓冲到内存最前面的组缓冲到内存; 该组称作该组称作超级块超级块。n 超级块结构超级块结构

42、(P393394):struct filesys int s_nfree; /组中空闲块个数组中空闲块个数(100); int s_free100; /s_free0指向下一组指向下一组; /其它为本组中空闲块号其它为本组中空闲块号; super_block;7.7.2 外存空间的管理外存空间的管理(Cont.)空闲块的成组链接图示空闲块的成组链接图示:s_nfree100s_free0s_free1n11s_free99n199100n21n299100n31n399Knj1njK-1超级块超级块空闲块组表空闲块组表空闲块的成组链接例空闲块的成组链接例: P394图图13.14空闲块组表空闲

43、块组表空闲块组表空闲块组表7.7.2 外存空间的管理外存空间的管理(Cont.)上述结构表示：上述结构表示：磁盘中共有磁盘中共有 1(j-1)100(K-1)个空闲块个空闲块.初始超级块如下：初始超级块如下：s_nfree1s_free0s_free1nulls_free99null100n21n299100n31n399Knj1njK-1超级块超级块空闲块组表空闲块组表空闲块组表空闲块组表空闲块组表空闲块组表100n11n199空闲块组表空闲块组表7.7.2 外存空间的管理外存空间的管理(Cont.)s_nfree39s_free050s_free140s_free3812100150149

44、51#50100350349251#250100250249151#15087NULL449351#350#351#449#40#12#149#51#249#151#349#251内存内存超级块超级块7.7.2 外存空间的管理外存空间的管理(Cont.)成组链接的空闲块管理成组链接的空闲块管理: 超级块已读入内存。超级块已读入内存。n 申请申请: s_nfree1, 取块号取块号s_free-s_nfree分配分配; s_nfree=1, 将将s_free0所指连接块读入内存所指连接块读入内存 (作为超级块作为超级块), 分配块号分配块号s_free0。n 释放释放: s_nfree100,

45、s_frees_nfree+=释放块号释放块号; s_nfree=100, 将将s_nfree和和s_free拷贝到释放块中拷贝到释放块中, 将该块号记录到将该块号记录到s_free0, s_nfree=1。7.7.2 外存空间的管理外存空间的管理(Cont.)7.8 文件系统的界面文件系统的界面 创建文件创建文件: creat(path_name, fcb_args)n 参数说明参数说明l path_name: 文件路径名文件路径名;l fcb_args: FCB参数。参数。n 执行步骤执行步骤: 为此文件分配一个为此文件分配一个FCB主部主部, 初始化初始化; 将文件名和文件号作为将文件名

46、和文件号作为FCB次部填到末级目录中次部填到末级目录中; 以写方式打开。以写方式打开。例如例如: creat(“/usr/li/d1/f1”, mode) 打开文件打开文件: fd=open ( path_name, mode )n 参数说明参数说明: path_name: 文件路径名文件路径名; mode: 打开方式打开方式.n 执行步骤执行步骤 根据文件路径名查目录找到根据文件路径名查目录找到FCB次部次部; 合法性检查合法性检查(根据打开方式、共享说明、用户身份根据打开方式、共享说明、用户身份); 根据文件号查根据文件号查看该文件是否已被打开看该文件是否已被打开, 如是则共享计数加如是则

47、共享计数加1; 否则找一个空闲的否则找一个空闲的系统打开文件表项系统打开文件表项, 并将外存中并将外存中FCB主部等信息填主部等信息填入此表项入此表项, 共享计数置为共享计数置为1; 在在用户打开文件表用户打开文件表中找一空表项中找一空表项, 填写打开方式和填写打开方式和 读写指针读写指针(初值为初值为0), 并指向并指向系统打开文件表系统打开文件表的对应表项。的对应表项。n 返回信息返回信息: fd: 文件描述符文件描述符(用户打开文件表入口用户打开文件表入口), 一个一个非负整数非负整数。7.8 文件系统的界面文件系统的界面(Cont.) 关闭文件关闭文件: close ( fd )n 参

48、数说明参数说明: fd: 文件描述符。文件描述符。n 执行步骤执行步骤: 由由 fd 查查用户打开文件表用户打开文件表, 找到找到系统打开文件表系统打开文件表入口入口; 系统打开文件表中共享计数减系统打开文件表中共享计数减 1 ; 如减如减 1 后的值为后的值为0且修改标志为且修改标志为 1 , 则将此则将此 FCB 由内存写回外存由内存写回外存FCB主部主部; 将将 fd 所对应的所对应的用户打开文件表项用户打开文件表项置为空闲。置为空闲。 7.8 文件系统的界面文件系统的界面(Cont.) 指针定位指针定位: seek ( fd, offset )n 参数说明参数说明:l fd: 文件描述

49、符文件描述符;l offset: 新的指针位置。新的指针位置。n 执行步骤执行步骤: 由由 fd 查查用户打开文件表用户打开文件表, 找到对应的找到对应的入口入口; 检查检查参数合法性参数合法性; 将用户打开文件表中将用户打开文件表中文件读写指针文件读写指针位置设定为位置设定为offset, 后续读写命令由该指针处存取文件内容。后续读写命令由该指针处存取文件内容。7.8 文件系统的界面文件系统的界面(Cont.) 读文件读文件: read ( fd , nrd , buf )n 参数说明参数说明:lfd: 文件描述符文件描述符;lnrd: 读入记录个数读入记录个数;lbuf: 内存起始位置。内

50、存起始位置。n 执行步骤执行步骤: 由由 fd 查查用户打开文件表用户打开文件表, 找到对应的系统打开文件表找到对应的系统打开文件表入口入口; 合法性检查合法性检查(用户打开文件表中所记录的打开方式、存取方式用户打开文件表中所记录的打开方式、存取方式); 根据读写指针和文件物理结构，计算读写指针对应的磁盘物理地址根据读写指针和文件物理结构，计算读写指针对应的磁盘物理地址 addr(物理块号物理块号, 偏移偏移); 把从把从addr开始的开始的 nrd 个记录读入内存中由个记录读入内存中由 buf 起始的区域；起始的区域； 调整文件读写指针为：当前读指针调整文件读写指针为：当前读指针sizeof

51、(记录结构记录结构)nrd。7.8 文件系统的界面文件系统的界面(Cont.) 写文件写文件: write ( fd, nwt , buf )n参数说明参数说明: fd: 文件描述符文件描述符; nwt : 写出记录个数写出记录个数; buf: 内存起始位置。内存起始位置。n 执行步骤执行步骤: 由由 fd 查查用户打开文件表用户打开文件表, 找到对应的找到对应的入口入口; 合法性检查合法性检查(用户打开文件表中所记录的打开方式、存取方式用户打开文件表中所记录的打开方式、存取方式); 根据读写指针及文件物理结构计算当前读写指针对应的根据读写指针及文件物理结构计算当前读写指针对应的 磁盘物理地址

52、磁盘物理地址(物理块号物理块号I, offset); 如果：如果：块号块号I=文件最末块号文件最末块号& offsetsizeof(记录结构记录结构)nwt磁盘块大小磁盘块大小; 则需要：则需要： 申请磁盘块申请磁盘块; 修改文件物理结构表；修改文件物理结构表； 将内存中由将内存中由 buf 起始的起始的 nwt 个记录个记录 写到地址写到地址(物理块号物理块号I, offset)起始的磁盘区域起始的磁盘区域; 调整读写指针：当前读写指针调整读写指针：当前读写指针sizeof(记录结构记录结构)nwt 。7.8 文件系统的界面文件系统的界面(Cont.) 建立连接建立连接: link

53、(old_name , new_name )n 参数说明参数说明: l old_name: 已存在的文件路径名已存在的文件路径名;l new_name: 欲连接的文件路径名。欲连接的文件路径名。n 执行步骤执行步骤: 查目录找到文件查目录找到文件old_name的的FCB次部次部, 由此得到文件号由此得到文件号; 查目录找到文件查目录找到文件new_name的末级目录的末级目录; 将文件号与将文件号与new_name中末级名字合起来构成一个中末级名字合起来构成一个 新的目录项新的目录项, 将其填入将其填入new_name的末级目录文件中的末级目录文件中; 将将FCB主部中的连接计数加主部中的连

54、接计数加1. 例如例如: link(“/usr/Li/f1”, “/usr/Zhang/d2/f2”)7.8 文件系统的界面文件系统的界面(Cont.) 断开连接断开连接: unlink ( path_name )n 参数说明参数说明: path_name: 文件路径名文件路径名.n 执行步骤执行步骤: 查目录找到文件查目录找到文件 path_name 的的FCB主部主部; 将连接计数值减将连接计数值减 1; 如减如减 1 后的值为后的值为 0, 则则归还该文件所占用的全部存储块归还该文件所占用的全部存储块, 该文件将被撤销该文件将被撤销; 将将FCB次部由上级目录中清除次部由上级目录中清除.

55、 例如例如: unlink(“/usr/Zhang/d2/f2”)7.8 文件系统的界面文件系统的界面(Cont.)UNIX文件系统的实现文件系统的实现n 内存所需表目内存所需表目( (UNIX) )l用户打开文件表用户打开文件表nu_ofile ( (每个进程一个每个进程一个) )nfile ( (整个系统一个整个系统一个) )l系统打开文件表系统打开文件表nInode ( (整个系统一个整个系统一个) )n 外存空间的管理外存空间的管理l空闲块表空闲块表l字位映像图字位映像图(Linux)l成组连接成组连接 (UNIX approach)UNIX内存表目：内存表目：1. u_ofile (

56、每进程一个每进程一个)struct user int u_ofileNOFILE; #define NOFILE 15 2. file (系统一个系统一个)struct file char f_flag; /R,W,PIPE char f_count; /使用该文件进程家族的进程个数使用该文件进程家族的进程个数 int f_inode; /指向指向inode表项表项 char *f_offset; /字符读写指针字符读写指针 fileNFILE#define NFILE 100UNIX文件系统的实现文件系统的实现(Cont.)u_ofile的下标为文件描述符的下标为文件描述符fd，u_ofil

57、efd指向指向file表的表项。表的表项。目录项为目录项为UNIX系统的系统的FCBstruct inode /(P395;外存外存;共共32 bytes，外存块大小，外存块大小512 bytes) int i_mode; /文件类型和用户权限文件类型和用户权限 char i_nlink; /文件链接计数文件链接计数 char i_uid; /文件主文件主id char i_gid; /同组用户同组用户id char i_size0; /most significant of size char *i_size1; /least significant of size int i_addr8;

58、 /i_addr0 i_addr5为为0级索引，级索引， / i_addr6为一级索引；为一级索引； i_addr7为二级索引；为二级索引； int i_atime2; /最后访问时间最后访问时间 int i_mtime2; /最后修改时间最后修改时间UNIX文件系统的实现文件系统的实现(Cont.)UNIX文件系统的实现文件系统的实现(Cont.)struct inode (内存内存：P395396 ) int i_flag; /主部修改标志主部修改标志 char i_count; /打开该文件的次数；打开该文件的次数；file表项指向该表项指向该inode表项的个数表项的个数 char i

59、_dev; char i_number; char i_mode; char i_nlink; /连接计数连接计数 char i_uid; char i_gid; char i_size0; char *i_size1; int i_addr8; int i_lastr; i_nodeNINODE;表间联系：表间联系：u_ofile file (n) (1)file inode (n) (1)read(4,)read(4,)write(6,)用户空间用户空间u_ofileu_ofilefilei_node磁盘空间磁盘空间系统空间系统空间.数据块数据块.i_list表间联系表间联系UNIX外存空

60、间管理：外存空间管理：0 1 2 k k+1 n-1导导引引块块超超级级块块 inode区域区域每块每块16个个inode, 从从0起依次编号起依次编号 文件存储区域文件存储区域(普通文件普通文件,目录文件目录文件)超级块超级块(super block)： (1) 记载文件卷上记载文件卷上k+1块到块到n-1块中所有空闲块，块中所有空闲块， (2) inode区中区中100个空闲个空闲inode. (缓存缓存) 文件安装文件安装(mount)后后超级块读入内存。超级块读入内存。注：占用区域已经记载在各个文件的注：占用区域已经记载在各个文件的inode中。中。Struct filesys int s_i