操作系统-文件
2020 年 12 月 15 日 234 4271 字 暂无评论

01.初始文件管理

  • 文件的定义

    • 一组有意义的信息的集合。
  • 文件的属性

    • 文件名、标识符、类型、位置、大小、保护信息等。

  • 文件内部应该如何被组织起来(文件的逻辑结构)

  • 文件之间应该如何被组织起来(目录结构)

  • 操作系统应该向上提供哪些功能(create、delete、open、close、read、write系统调用)
  • 文件应如何放在外存中(文件的物理结构)
  • 操作系统如何管理外存中的空闲块(存储空间的管理)
  • 操作系统需要提供的其他文件管理功能

    • 文件共享
    • 文件保护

02.文件的逻辑结构

2.1无结构文件

  • 无结构文件

    • 文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。

2.2有结构文件

  • 有结构文件

    • 由一组相似的记录组成,又称“记录式文件”。
    • 每条记录有若干个数据项组成。
    • 如:数据库表文件。一般来说,每条记录有一个数据项可作为关键字(作为识别不同记录的ID)。
    • 根据各条记录的长度(占用的存储空间)是否相等,又可分为定长记录可变长记录两种。

2.3有结构文件的逻辑结构

  • 顺序文件

    • 文件中记录一个接一个地顺序排列(逻辑上),记录可以是定长的或可变长的。
    • 各个记录在物理上可以顺序存储链式存储

      • 链式存储:无论是定长/可变长记录,都无法实现随机存取,每次只能从第一个记录开始依次往后查找。
      • 顺序存储

        • 可变长记录无法实现随机存取。每次只能从第一个记录开始依次往后查找。
        • 定长记录可实现随机存取。记录长度为L,则第i个记录存放的相对位置是i*L。若采用串结构,无法快速找到某关键字对应的记录。
        • 若采用顺序结构可以快速找到某关键字对应的记录(如折半查找)
  • 索引文件

    • 建立一张索引表,每个记录对应一个表项。各记录不用保持顺序,方便增加/删除记录。
    • 索引表本身就是定长记录的顺序文件,一个索引表项就是一条定长记录,因此索引文件可支持随机存取。
    • 若索引表按关键字顺序排列,则可支持快速检索
    • 解决了顺序文件不方便增/删记录的问题,同时让不定长记录的文件实现了随机存取。但索引表可能占用很多的空间。
  • 索引顺序文件

    • 将记录分组,每组对应一个索引表项。
    • 检索记录时先顺序查索引表,找到分组,再顺序查找分组。
    • 当记录过多时,可建立多级索引表。

03.文件目录

3.1文件控制块(实现文件目录的关键数据结构)

  • 一个文件对应一个FCB,一个FCB就是一个目录项,多个FCB组成文件目录。
  • 对目录的操作:搜索、创建文件、删除文件、显示文件、修改文件

3.2目录结构

  • 单级目录结构

    • 一个系统只有一张目录表,不允许文件重名
  • 两级目录结构

    • 不同用户的文件可以重名,但不能对文件进行分类
  • 多级(树形)目录结构

    • 不同目录下的文件可以重名,可以对文件进行分类,不方便文件共享
    • 系统根据“文件路径”找到目标文件。
    • 从根目录出发的路径是“绝对路径
    • 从“当前目录”出发的路径是“相对路径
  • 无环图目录结构

    • 在树形目录结构的基础上,增加一些指向同一节点的有向边,使整个目录成为一个有向无环图。
    • 为共享结点设置一个共享计数器,计数器为0时才真正删除该结点

3.3索引结点(对文件控制块的优化)

  • 除了文件名之外的所有信息都放到索引结点中,每个文件对应一个索引结点
  • 目录项中只包含文件名、索引结点指针,因此每个目录项的长度大幅减小。
  • 由于目录项长度减小,因此每个磁盘块可以存放更多个目录项,因此检索文件时磁盘I/O的次数就少了很多。

04.文件的物理结构

4.1文件块、磁盘块

4.2文件分配方式

  • 连续分配

    • 连续分配方式要求每个文件在磁盘上占有一组连续的块
    • 读取某个磁盘块时,需要移动磁头。访问的两个磁盘块相隔越远,移动磁头所需时间就越长。
    • 连续分配的文件在顺序读/写时速度最快
    • 物理上采用连续分配,存储空间利用率低,会产生难以利用的磁盘碎片
    • 优点:支持顺序访问和直接访问(即随机访问);连续分配的文件在顺序访问时速度最快。
    • 缺点:不方便文件拓展;存储空间利用率低,会产生持磁盘碎片。

  • 链接分配

    • 隐式链接

      • 除文件的最后一个盘块之外,每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。
      • 优点:很方便文件拓展,不会有碎片问题,外存利用率高。
      • 缺点:只支持顺序访问,不支持随机访问,查找效率低,指向下一个盘块的指针也需要耗费少量的存储空间。

  • 显式连接

    • 把用于链接文件各物理块的指针显式地存放在一张表中,即文件分配表FAT,File Allocation Table)。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存,并常驻内存
    • 优点:很方便文件拓展,不会有碎片问题,外存利用率高,并且支持随机访问。相比于隐式链接来说,地址转换时不需要访问磁盘,因此文件的访问效率更高
    • 缺点:文件分配表的需要占用一定的存储空间。
  • 索引分配

    • 索引分配允许文件离散地分配在各个磁盘中,系统会为每个文件建立一张索引表,索引表中记录了文件的各个逻辑块对应的物理块。(索引表的功能类似于内存管理中的页表--建立逻辑页面到物理页面之间的映射关系)。
    • 索引表存放的磁盘块称为索引块
    • 文件数据存放的磁盘块称为数据块

  • 链接方案:如果索引表太大,一个索引块装不下,那么可以将多个索引块链接起来存放。

  • 多层索引:建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。

  • 混合索引:多种索引分配方式的结合。例如,一个文件的顶级索引表中,既包含直接地址索引(直接指向数据块),又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)。

05.文件存储空间管理

  • 存储空间的划分与初始化

    • 文件卷(逻辑卷),目录区、文件区的概念。
    • 目录区包含文件目录、空闲表、位示图、超级块等用于文件管理的数据。
  • 空闲表法

    • 空闲表中记录每个连续空闲区的起始盘块号、盘块数。
    • 分配时可采用首次适应、最佳适应等策略;回收时注意表项的合并问题
  • 空闲链表法

    • 空闲盘块链

      • 盘块为单位组成一条空闲链。
      • 分配时从链头依次取出空闲块,回收时将空闲块查到链尾。
    • 空闲盘区链

      • 盘区为单位组成一条空闲链。
      • 分配时可采用首次适应、最佳适应等策略;回收时注意相邻空闲盘区合并问题。
  • 位示图法

    • 一个二进制位对应一个盘块。(字号,位号)或(行号,列号)与盘块号一一对应。
    • 重要考点:要能够自己退出盘块号->(字号,位号)之间的相互转换公式。
    • 需要注意的题目条件

      • 二进制位0/1到底哪个代表空闲,哪个代表不空闲。
      • 字号、位号、盘块号到底是从0开始还是从1开始。
  • 成组链接法

    • UNIX采用的策略,适合大型文件系统。

06.文件的基本操作

  • 创建文件

    • 分配外存空间,创建目录项。
  • 删除文件

    • 回收外存空间,删除目录项。
  • 打开文件

    • 将目录项中的信息复制到内存中的打开文件表中,并将打开文件表的索引号返回给用户
    • 打开文件之后,对文件的操作不再需要每次都查询目录,可以根据内存中的打开文件表进行操作。
    • 每个进程有自己的打开文件表,系统中也有一张总的打开文件表。
    • 进程打开文件表中特有的属性:读写指针、访问权限(只读?只写?)
    • 系统打开文件表中特有的属性:打开计数器(有多少个进程打开了该文件)
  • 关闭文件

    • 将进程打开文件表中的相应表项删除。
    • 系统打开文件表的打开计数器减1,若打开计数器为0,则删除系统表的表项。
  • 读文件

    • 根据读指针、读入数据量、内存位置将文件数据从外存读入内存
  • 写文件

    • 根据写指针、写出数据量、内存位置将文件数据从内存写出外存。

07.文件共享

  • 硬链接

    • 各个用户的目录项指向同一个索引结点。
    • 索引结点中需要有链接计数count
    • 某用户想删除文件时,只是删除该用户的目录项,且count--。
    • 只有count==0时才能真正删除文件数据和索引结点,否则会导致指针悬空。

  • 软链接(符号链接)

    • 在一个Link型的文件中记录共享文件的存放路径(Windows快捷方式)。
    • 操作系统根据路径一层一层查找目录,最终找到共享文件。
    • 即使软链接指向的共享文件已被删除,Link型文件依然存在,只是通过Link型文件中的路径去查找共享文件会失败(找不到对应目录项)。
    • 由于用软链接的方式访问共享文件时要查询多级目录,会有多次磁盘I/O,因此用软链接访问。

08.文件保护

8.1口令保护

  • 为文件设置一个“口令”(如:abc112233),用户请求访问该文件时必须提供“口令”。

    • 口令一般存放在文件对应的FCB索引结点中。用户访问文件前需要先输入“口令”,操作系统会将用户提供的口令与FCB中存储的口令进行对比,如果正确,则允许该用户访问文件。
  • 优点:保存口令的空间开销不多,验证口令的时间开销也很小。
  • 缺点:正确的“口令”存放在系统内部,不够安全。

8.2加密保护

  • 使用某个“密码”对文件进行加密,在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。

  • 优点:保密性强,不需要在系统中存储“密码”。
  • 缺点:编码/译码,或者说加密/解密要花费一定时间。

8.3访问控制

  • 在每个文件的FCB(或索引结点)中增加一个访问控制列表Access-Control List,ACL),该表中记录了各个用户可以对该文件执行哪些操作。

09.文件系统的层次结构

  • 用一个例子来辅助记忆文件系统的层次结构:
  • 假设某用户请求删除文件“D:/工作目录/学生信息.xlsx”的最后100条记录。

    • 用户需要通过操作系统提供的接口发出上述请求——用户接口
    • 由于用户提供的是文件的存放路径,因此需要操作系统一层一层地查找目录,找到对应的目录项——文件目录系统
    • 不同的用户对文件有不同的操作权限,因此为了保证安全,需要检查用户是否有访问权限——存取控制模块(存取控制验证层)
    • 验证了用户的访问权限之后,需要把用户提供的“记录号”转变为对应的逻辑地址——逻辑文件系统与文件信息缓冲区
    • 知道了目标记录对应的逻辑地址后,还需要转换成实际的物理地址——物理文件系统
    • 要删除这条记录,必定要对磁盘设备发出请求——设备管理程序模块
    • 删除这些记录后,会有一些盘块空闲,因此要将这些空闲盘块回收——辅助分配模块

10.磁盘的结构

  • 磁盘、磁道、扇区的概念

    • 磁盘由表面涂有磁性物质的圆形盘片组成。
    • 每个盘片被划分为一个个磁道,每个磁道又划分为一个个扇区。
  • 如何在磁盘中读/写数据

    • 磁头移动到目标位置,盘片旋转,对应扇区划过磁道才能完成读/写。
  • 盘面、柱面的概念

    • 磁盘有多个盘片“摞”起来,每个盘片有两个盘面。
    • 所有盘面中相对位置相同的磁道组成柱面。
  • 磁盘的物理地址

    • 柱面号、盘面号、扇区号
  • 磁盘的分类

    • 根据磁头是否可移动

      • 固定头磁盘(每个磁道有一个磁头)。
      • 移动头磁盘(每个盘面只有一个磁头)。
    • 根据盘片是否可更换

      • 固定盘磁盘。
      • 可换盘磁盘。

11.磁盘调度算法

11.1一次磁盘读/写操作需要的时间

  • 寻找时间(寻道时间):启动磁臂、移动磁头所花的时间
  • 延迟时间:将目标扇区转到磁头下面所花的时间。
  • 传输时间:读/写数据花费的时间。

11.2先来先服务(FCFS)

  • 按访问请求到达的先后顺序进行处理。

  • 优点:公平
  • 缺点:如果有大量进程竞争使用磁盘,请求访问的磁道很分散,则FCFS性能很差,寻道时间长。

11.3最短寻找时间优先(SSTF)

  • 每次都优先响应距离磁头最近的磁道访问请求。
  • 贪心算法思想,能保证眼前最优,但无法保证总的寻道时间最短。
  • 缺点:可能导致饥饿。

11.4扫描算法(电梯算法、SCAN)

  • 只有磁头移动到最边缘的磁道时才可以改变磁头移动方向。
  • 缺点:对各个位置磁道的响应频率不平均。

11.5循环扫描算法(C-SCAN)

  • 只有磁头朝某个方向移动时才会响应请求,移动到边缘后立即让磁头返回起点,返回途中不响应任何请求。

11.6LOOK算法

  • SCAN算法的改进,只要在磁头移动方向上不再有请求,就立即改变磁头方向。

11.7C-LOOK算法

  • C-SCAN算法的改进,只要在磁头移动方向上不再有请求,就立即让磁头返回。

12.减少延迟时间的方法

  • 交替编号

    • 具体做法:让编号相邻的扇区在物理上不相邻。
    • 原理:读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区。

  • 错位命名

    • 具体做法:让相邻盘面的扇区编号“错位”。
    • 原理:与“交替编号”的原理相同。“错位命名法”可降低延迟时间。

  • 磁盘地址结构的设计

    • 为什么要用(柱面号,盘面号,扇区号)的结构。不用(盘面号,柱面号,扇区号)的结构。
    • 原因:在读取地址连续的磁盘块时,前者更不需要移动磁头

13.磁盘的管理

  • 磁盘的初始化

    • 低级格式化/物理格式化:划分扇区。
    • 磁盘分区(C盘、D盘、E盘)。
    • 逻辑格式化:建立文件系统(建立根目录文件、建立用于存储空间管理的数据结构)。
  • 引导块

    • 计算机启动时需要运行初始化程序(自举程序)来完成初始化。
    • ROM中存放很小的自举装入程序。
    • 完整的自举程序存放在初始块(引导块)中。
  • 坏块的管理

    • 简单的磁盘:逻辑格式化时将坏块标记出来。
    • 复杂的磁盘:磁盘控制器维护一个坏块链,并管理设备用扇区。

版权属于:zfh

本文链接:http://zfhblog.com/index.php/archives/188/



评论已关闭