操作系统原理笔记（4）

操作系统第六七八章知识点总结

文件管理

文件和文件系统

数据项、记录和文件

• 数据项
  • 基本数据项：描述以对象某种属性的字符集，如学号、姓名、年龄这些不能再细分的
  • 组合数据项：若干个基本数据项组成的，就是还可以细分的
• 记录
  • 描述一个对象在某方面的属性，注意要有关键字key，方便查找
• 文件
  • 多条记录组成文件

文件属性：类型、长度、物理位置、建立时间（即最后一次修改时间）

文件名和类型

• 文件名和拓展名
• 文件类型
  • 按用途分：系统文件、用户文件、库文件
  • 按文件数据形式：源文件、目标文件、可执行文件
  • 按存取控制属性：只执行文件、只读文件、读写文件
  • 按组织形式和处理方式分类：普通文件、目录文件、特殊文件

文件系统的层次结构

• 对象及其属性
  • 管理对象：文件、目录、磁盘存储空间
• 对对象操纵和管理的软件集合
  • I/O控制层、基本文件系统层、基本I/O管理程序、逻辑文件系统
• 文件系统的接口
  • 命令接口、程序接口

文件操作

• 最基本的文件操作
  • 创建、删除、读、写、设置读写位置
• 文件的“打开”和“关闭”操作
• 其他文件操作
  • 设置和获得文件的属性、查询文件状态

有关目录的，就是创建、删除、改变当前目录等

文件的逻辑结构

文件逻辑结构的类型

有结构文件：记录式文件
无结构文件：流式文件

• 按文件是否有结构分类
  • 有结构文件（如数据库）：定长记录、变长记录
  • 无结构文件（txt）：源程序、可执行文件
• 按文件的组织方式分类
  • 顺序文件：可以定长可以变长，一直按顺序下去（如犯人的记录）
  • 索引文件：加张索引表
  • 索引顺序文件：分组，组内是顺序，组头有索引

顺序文件

• 顺序文件的排列方式
  • 串结构：要从头开始找
  • 顺序结构：有个关键字
• 顺序文件的优缺点
  • 最高效、但交互应用中效率好差、而且增加删除一个记录困难
  • 所以要配置一个运行记录文件，按时合并

记录寻址

• 隐式寻址方式
  • 一个一个读，读了（n-1）个才找到n
• 显式寻址方式
  • 定长就方便，直接乘索引号即可
  • 变长就要加上Li，表示一段记录的长度
  • 或者利用关键字查找

索引文件

①按关键字建立索引
索引文件三要素：索引号、长度、指针
多个索引表的索引文件：从不同属性查找同一对象

索引顺序文件

• 索引顺序文件的特征
  • 引入文件索引表，可以实现对索引顺序文件的随机访问；
  • 增加溢出文件，可以记录新增加、删除和修改的记录
• 一级索引顺序文件
  • 分组，组首进入索引顺序文件
• 两级索引顺序文件
  • 索引顺序表做组

直接文件和哈希文件

• 直接文件
  • 关键字本身就决定记录的物理地址，所以可以直接查找，有键值转换
• 哈希文件
  • A = H(K)，通常是指向某一目录表相应表目的指针

文件目录

要求：
实现“按名存取”
提高对目录的检索速度
文件共享
允许文件重名

文件控制块和索引结点

• 文件控制块FCB
  • 包含三类信息：基本信息、存取控制信息、使用信息
  • 基本信息：文件名、文件物理位置、文件逻辑结构、文件物理结构
  • 存取控制信息：各类人的存取权限
  • 使用信息类：建立时间、最近修改时间、当前使用信息
    ②索引结点
  • 引入：怕文件目录太大，只用文件名，轻量级文件目录
  • 磁盘索引结点：文件主标识符、文件类型、文件存取权限、文件物理地址、文件长度、文件连接计数、文件存取时间
  • 内存索引结点：索引结点编号、状态、访问计数、文件所属文件系统的逻辑设备号、链接指针

简单的文件目录

• 单级文件目录
  • 整个文件系统只有，一张目录表，目录项有：文件名、文件扩展名、文件长度、文件类型、文件物理地址和其他属性
  • 每次创建都要搜索有没有相同的文件名
  • 优点是简单，但只实现了“按名存取”，其他三个要求没有实现
• 两级文件目录
  • MFD→UFD
  • 会有隔离，这个结构可以有效将多个用户隔开，在各个用户完全无关时，这是一个优点。
  • 但如果要合作完成一个大任务时，这种隔离就会使诸多用户之间不便于共享

树形结构目录

• 树形目录
  • 一个目录文件中的目录项，可以既作为目录文件的FCB，又是数据文件的FCB
• 路径名和当前目录
  • 路径名：唯一通路，用/连接
  • 当前目录，相对路径名，绝对路径名
• 目录操作
  • 创建、删除、不删除非空目录、可删除非空目录
  • 改变、移动、链接目录、查找目录
• 目录查询技术
  • 线性检索法：在单级目录中，用用户提供的文件名，顺序查找；在树形目录中，就按路径名查找
  • Hash方法：建立一张Hash索引文件目录，利用Hash方法查询——利用用户提供的文件名，转换为文件目录索引值，再用索引值在目录中查找
  • 注：如果使用了通配符，就无法用Hash方法检索了
  • “冲突”：1.看目录项是否空 2.看文件名是否匹配 3. 如果不匹配，就要在Hash值加上一个常数，形成新的索引值

文件共享

基于有向无循环图实现文件共享

• 有向无循环图DAG
  • 由附加操作Append来完成，而新增加的盘块只会出现在执行了操作的目录中，新增加的部分不能被共享
• 利用索引结点
  • 用索引结点，任何用户对共享文件所进行的Append操作或修改，都将引起相应结点内容的改变
  • 还增加一个count链接计数
  • 其他用户在使用，拥有者删了，文件依然存在

利用符号链接实现文件共享

• 利用符号链接的基本思想
  • 即允许一个文件或子目录有多个父目录，但只有一个是“主”父目录
• 如何利用符号链实现共享
  • 由系统创建一个LINK类型的新文件，取名为F，并将F写入链接父目录D5中，就可以实现D5与F8的链接。新文件只有被链接文件F8的路径名——所以叫做“符号链接”——新文件的路径名被看做“符号链”
• 利用符号链实现共享的优点
  • 用户删了链接文件，也不会删掉本来的文件；文件主删了文件，其他用户访问不了，自然会删掉符号链
• 利用符号链的共享方式存在的问题
  • 读盘需时、符号链太多，琐碎

第八章 磁盘存储器的管理

外存的组织方式

连续组织方式、链接组织方式、索引组织方式

连续组织方式

位于同一磁道，读写不用移动磁头
优点：顺序访问容易、顺序访问速度快
缺点：要求为一个文件分配连续的存储空间、要事先知道文件长度、不够灵活删除和插入、对于动态增长的文件，很难分配空间

链接组织方式

优点：消除外部碎片，提高外存利用率；对插入、删除修改记录都非常容易；能够适应动态增长
隐式链接：一个跟一个，如同链表；碎片多；万一一个错，整个文件用不了
显式链接：将各物理块的指针显式存在内存的一个表内，每个FCB对应一个字段，因为在内存查找，所以大大提高检索速度，还减少访问磁盘的次数，而这叫做FAT

索引组织方式

• 单级索引组织方式
  • 不支持高效直接存取，要对一个较大的文件进行存取，就要顺序地查找许多盘块号
  • FAT需要占用较大内存空间
  • 所以创造“表中表”——索引分配图
• 多级索引组织方式
  • 就是多级，如同“全语言字典”
  • 优点：大大加快对大型文件的查找速度
• 增量式索引组织方式
  • 增量式索引组织方式的基本思想
  • 小的用直接寻址、中的用单级索引组织方式、大的用两三级索引组织方式
  • Unix System V的组织方式：索引结点有13个地址项，前十个是直接地址，最大放40KB；第十一个是一次间接地址，1K个盘块号，允许文件长达4MB；如果还超过4MB+40KB，就放二次间接地址，有4GB；还超过，就放3次间接地址，有4TB

文件存储空间的管理

空闲表法和空闲链表法

• 空闲表法
  • 即在外存所有空闲区建立一张空闲表，每个空闲区对于一个表项，记录序号、第一空闲盘块号、空闲盘块数
  • 分配和回收与内存相似，但在外存为加快分配速度，连续分配依然有用。小的连续分配，大的离散分配，多媒体文件依然连续分配
• 空闲链表法
  • 空闲盘块链：一直分配，按链表分配。如果删除文件就挂在链尾
  • 优点：简单，缺点：但为一个文件分配时可能重复操作多次，分配和回收效率较低，而且盘块链会很长
  • 空闲盘区链：优点：分配回收效率较高，盘区链短；缺点复杂

位示图法

• 位示图
  • 利用二进制的一位来表示磁盘中一个盘块的使用情况，也可以是二维数组
• 盘块的分配
  • 扫描位示图，找到一个或一组0，之后计算盘块号： b = n(i -1)+j，修改位示图=1
• 盘块的回收
  • 从盘块号转换为行列号：
  • i = (b-1) DIV n +1
  • j = (b-1) MOD n + 1

成组链接法

• 空闲盘块的组织
  • 每组含有盘块总数N和该组所有盘块号记入前一组的第一个盘块的S.free(0)~S.free(99)，这样各组第一个盘块可链接成一条链
• 空闲盘块的分配与回收
  • 当栈中空闲盘块号已达100时，表示栈已满，便将先有栈中100个盘块号记入新回收的盘块中，将盘块号作为新栈底