数据结构chapter6_文件管理

数据结构chapter6_文件管理

管理硬件资源:处理机管理,存储器管理,I/O设备管理. 管理硬件资源:处理机管理,存储器管理, 设备管理. 设备管理 管理软件资源:文件管理(是指对文件进行操作和管理的 管理软件资源:文件管理(软件集合. 软件集合. ) – 软件资源:主要包括各种系统程序,标准例程库和各类应 软件资源:主要包括各种系统程序, 用程序,都以文件形式存储在外部存储器上. 用程序,都以文件形式存储在外部存储器上. – 操作系统本身也要求文件管理功能 – 提供用户与外存的界面

数据结构chapter6_文件管理

文件管理面向用户实现按文件名存取文件 文件系统(文件管理)的基本功能: 文件系统(文件管理)的基本功能:– 按用户要求创建一个新文件或删除一个存在的 文件; 文件; – 按用户要求,对文件进行读或写操作; 按用户要求,对文件进行读或写操作; – 文件存储空间管理; 文件存储空间管理; – 用户只要使用文件名就可以对文件进行访问; 用户只要使用文件名就可以对文件进行访问; – 对文件实现严格的维护; 对文件实现严格的维护; – 实现文件的共享与保护. 实现文件的共享与保护.

数据结构chapter6_文件管理

文件系统文件系统是对文件存贮器的空间进行组织分 配 , 负责文件的存贮, 并对存入的文件进行保护 负责文件的存贮 , 检索的系统. 检索的系统. 与文件管理有关的软件 ––– 文件管理软件 被管理的文件 ––– 管理的对象 目录, 实施管理的数据结构 ––– 目录,索引 文件系统所要解决的问题(功能 文件系统所要解决的问题 功能) 功能

数据结构chapter6_文件管理

文件系统: 文件系统:1) 有效地分配文件存贮器的存贮空间 物理介质 有效地分配文件存贮器的存贮空间(物理介质 物理介质)

2) 提供一种组织数据的方法 按名存取,逻辑结构, 提供一种组织数据的方法(按名存取,逻辑结构, 按名存取 组织数据) 组织数据

3) 提供合适的存取方法 顺序存取,随机存取 提供合适的存取方法(顺序存取 随机存取) 顺序存取,

数据结构chapter6_文件管理

6.1 文件结构和存取方法 6.2 文件存储空间的管理 6.3 文件目录 6.4 文件存取控制和文件系统的安全

数据结构chapter6_文件管理

6.1文件结构和存取方法逻辑文件:从用户观点出发, 逻辑文件:从用户观点出发,所观察到的文件组织形式,是用户可以直接处理的数据及其结构, 织形式,是用户可以直接处理的数据及其结构, 它独立于文件及其介质的物理特性,又称为文件 它独立于文件及其介质的物理特性, 组织. 组织. 物理文件:文件的存储结构, 物理文件:文件的存储结构,是文件在外存上存 储组织形式,与存储介质的存储特性有关. 储组织形式,与存储介质的存储特性有关.

数据结构chapter6_文件管理

文件的逻辑结构 记录式文件(有格式文件):是一种有结构的文 记录式文件(有格式文件):是一种有结构的文

): 由一个或多个记录组成. 件.由一个或多个记录组成. 以逻辑记录为单位 进行存取. 进行存取.– 定长记录文件:文件中所有记录的长度相同. 定长记录文件:文件中所有记录的长度相同. – 变长记录文件:每个记录的长度可以不同 变长记录文件:

无结构的流式文件(无格式文件):是有序字符 无结构的流式文件(无格式文件):是有序字符 ): 的集合,文件的长度等于该文件包含的字符数. 的集合,文件的长度等于该文件包含的字符数. 流式文件不分成记录, 流式文件不分成记录,而是直接由一连串信息组 成.

数据结构chapter6_文件管理

记录文件l1 记录1 l2 记录2 l1 指示记 录长度(a) 变长 (b) 定长

记录1 记录2 l l

l2

变长: 变长:每个记录的头几个字节存储记录长度

数据结构chapter6_文件管理

流式文件对流式文件而言, 对流式文件而言,它是按信息的个数或 以特殊字符为界进行存取的. 以特殊字符为界进行存取的. 优点: 优点: 在空间利用上比较省,没有额外的说明和 在空间利用上比较省, 控制信息. 控制信息.

数据结构chapter6_文件管理

文件的物理结构将外存划分为固定大小的块--物理块,每块通常为512 将外存划分为固定大小的块--物理块,每块通常为512 --物理块 字节或1024字节. 1024字节 字节或1024字节.

连续结构 顺序文件:为每个逻辑文件分配一组连 连续结构/顺序文件: 顺序文件续编号的物理块. 续编号的物理块.连续结构保证了逻辑文件中的记录 顺序与物理文件存储器中文件占用物理块的顺序的一 致性. 致性. 文件名 起始物理块号 文件长度

25 逻辑块0 逻辑块

26 逻辑块1 逻辑块

27 逻辑块2 逻辑块

28 逻辑块3 逻辑块 …

数据结构chapter6_文件管理

对于这种顺序结构文件, 对于这种顺序结构文件,用户应给出文件的 最大长度, 最大长度,以便在用户建立文件时为其分配足够 大的外存空间. 大的外存空间.

优点:结构简单,存取速度快. 优点:结构简单,存取速度快. 缺点:需确定文件的最大长度, 缺点:需确定文件的最大长度,不利于文件 的动态增长;存在外存存储空间的碎片( 的动态增长;存在外存存储空间的碎片(外 部碎片) 部碎片)问题

数据结构chapter6_文件管理

链表结构 链接文件: 是一种非连续的存储结构, 链表结构/链接文件: 是一种非连续的存储结构, 链接文件其物理文件可以由不邻接的物理块组成. 其物理文件可以由不邻接的物理块组成.在每一个 物理块中设立一个链接字, 物理块中设立一个链接字,使存储文件信息的物理 块形成链表结构. 块形成链表结构.– 优点:空间利用率高;文件可以块为单位动态地增长和 优点:空间利用率高; 删除,易于文件扩充. 删除,易于文件扩充. – 缺点:难以随机存取任意块的内容;文件的各记录分散, 缺点:难以随机存取任意块的内容;文件的各记录分散, 查询时间慢,

有链接指针,降低磁盘空间的利用率. 查询时间慢,有链接指针,降低磁盘空间的利用率. 文件名 起始物理块号 文件长度 … 8 物理块22 物理块 16 物理块8 物理块 NULL

物理块28 物理块

链表结构的文件

数据结构chapter6_文件管理

索引结构 随机文件结构: 索引结构/随机文件结构: 随机文件结构系统为每个文件建立一张从逻辑块号到物理块号的 映射表,即索引表. 映射表,即索引表.索引文件的索引项按文件的逻 辑块号顺序排列.具有这种结构的文件称索引文件. 辑块号顺序排列.具有这种结构的文件称索引文件. 分单级索引,多重索引. 分单级索引,多重索引. – 优点:具有链表结构文件的优点;可随机访问物 优点:具有链表结构文件的优点; 理块. 理块. – 缺点:索引结构可能要花费较多的外存空间.增, 缺点:索引结构可能要花费较多的外存空间. 删物理块时,索引表项的移动耗费时间. 删物理块时,索引表项的移动耗费时间.

数据结构chapter6_文件管理

文件目录文件名 索引表指针

逻辑块号 0 1 2

物理块号124 56 45

物理块124 56 45

索引表

数据结构chapter6_文件管理

文件的存取方法读写文件存储器上的一个物理块的方法. 读写文件存储器上的一个物理块的方法.

顺序存取: 顺序存取:– 记录式文件中:严格按照物理记录排列的顺序依次存取. 记录式文件中:严格按照物理记录排列的顺序依次存取. – 无结构的流式文件:从文件当前位置开始读写,然后根据 无结构的流式文件:从文件当前位置开始读写, 当前位置的位移读写后继的信息. 当前位置的位移读写后继的信息.

直接存取(随机存取):按任意次序存取文件中 直接存取(随机存取):的记录, 的记录,而不是顺序的– 记录式文件中:对定长记录的顺序文件,可直接存取;对 记录式文件中:对定长记录的顺序文件,可直接存取; 变长记录的顺序文件,需建立一张索引表, 变长记录的顺序文件,需建立一张索引表,以指出每个记 录的长度和起始位置,索引表按记录号顺序排列. 录的长度和起始位置,索引表按记录号顺序排列. – 无结构的流式文件:事先把该文件的现行位置指针设置到 无结构的流式文件: 欲读写信息的起始位置. 欲读写信息的起始位置.

数据结构chapter6_文件管理

记录文件l1 记录1 l2 记录2 l1 指示记 录长度(a) 变长 (b) 定长

记录1 记录2 l l

l2

Pi +1 = Pi + li + 2

Pi +1 = Pi + l

变长:每个记录的头几个字节存储记录长度, 变长:每个记录的头几个字节存储记录长度,这里 为2个字节

数据结构chapter6_文件管理

磁盘(磁鼓) 磁盘(磁鼓) 文件的物理 结构 存取方法 连续 顺序,直接 顺序, 链表 顺序 索引 顺序,直接 顺序,

磁带 连续 顺序

文件结构, 文件结构,存储设备和存取方法之间的关系

数据结构chapter6_文件管理

6.2 文件存储空间的管理目的:方便用户按文件名存取文件. 目的:方便用户按文件名

存取文件. 为了有效地管理和分配文件存储空间, 为了有效地管理和分配文件存储空间,系统应解决下述几个 问题: 问题: 如何登记空闲区的分布情况; 如何登记空闲区的分布情况; 如何按需要给一个文件分配存储空间; 如何按需要给一个文件分配存储空间; 当一文件或其一部分不再需要保留时, 当一文件或其一部分不再需要保留时,如何回收其占用的存 储空间. 储空间. 常用的文件存储器是磁盘, 常用的文件存储器是磁盘,其空闲盘存储空间的管理常使用的 技术有: 技术有:

空闲块链表结构 空闲文件目录 位映象图结构

数据结构chapter6_文件管理

空闲块链表结构在空闲块中设立链接字,以建立链表, 在空闲块中设立链接字,以建立链表,系统将盘上的 所有空闲块链接成一个空闲块链表. 所有空闲块链接成一个空闲块链表.– 优点:简单,系统开销小. 优点:简单,系统开销小. – 缺点:工作效率低. 缺点:工作效率低.…

NULL

n

空闲块链表结构

数据结构chapter6_文件管理

空闲文件目录系统把磁盘存储空间中一个连续的未分配的存储区称 为一个"空闲文件" 空闲文件" 为一个"空闲文件",并为 "空闲文件" 建立一个 目录,每个表项对应一个"空闲文件" 目录,每个表项对应一个"空闲文件" .– 优点:仅当有少量的空闲区时效果较好,适用于连续文件 优点:仅当有少量的空闲区时效果较好, – 缺点:当有大量的小空闲区时,效率大大降低. 缺点:当有大量的小空闲区时,效率大大降低. 空闲文件的起始块号 块数

2 9 - 15

4 3 0 5

2,3,4,5 9,10,11 空表项 15,16,17,18,19

数据结构chapter6_文件管理

位映象图结构一个物理块用一位二进制数表示其使用情况:0表示空闲块; 一个物理块用一位二进制数表示其使用情况: 表示空闲块; 表示空闲块 1表示使用块.盘空间中的每一个物理块都用一对应的二进制 表示使用块. 表示使用块 位来表示它,并称所有这些二进制位组成的序列为该盘的位 位来表示它, 映象图. 映象图.盘的位映象图又称为盘图或盘图文件 . – 优点:分配和释放都可以在内存的位映象图上完成,速度 优点:分配和释放都可以在内存的位映象图上完成, 快.位编号: 位编号: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 盘图: 盘图: 1 1 1 1 0 0 1 1 0 0 0 1 1 1 0 1 0 1… 使用块:物理块0, , , , , , , , , , , 注: 使用块:物理块 ,1,2,3,6,7,11,12,13,15,17,… 空闲块:物理块4, , , , , , , 空闲块:物理块 ,5,8,9,10,14,16,…

位映象图示例

本文来源：https://www.bwwdw.com/article/erm4.html