操作系统知识点整理笔记（四）

• 文件的属性：①文件名；②标识符；③类型；④位置；⑤大小；⑥创建时间、上次修改时间、文件所有者信息；⑦保护信息等。
• 按文件是否有结构分为2类：
  • 无结构文件：文件内部的数据就是一系列二进制流或字符流组成，又称为流式文件。
  • 有结构文件：由一组相似的记录组成，又称为记录式文件。每条记录由若干个数据项组成。如：数据库表文件等。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID）。根据每条记录的长度（占用的存储空间）是否相等，又可以分为定长记录和可变长记录两种。
    • 顺序文件：文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。
      • 串结构：记录之间的顺序与关键字无关，通常按照记录存入的时间决定记录的顺序。
      • 顺序结构：记录之间的顺序按关键字顺序排列。
      • 链式存储：无论是定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次往后查找。
      • 顺序存储：
        • 可变长记录：无法实现随机存取，每次只能从第一个记录开始依次往后查找。
        • 定长记录：可实现随机存取。若记录长度为L，则第i个记录存放的相对位置是。若采用串结构，无法快速找到某关键字对应的记录；若采用顺序结构，可以快速找到某关键字对应的记录（如折半查找）
    • 索引文件：建立一张索引表以加快文件检索速度，每条记录对应一个索引项，文件中的这些记录在物理上可以离散地存放。索引表本身是定长记录的顺序文件。此种结构主要用于对信息处理的及时性要求比较高的场合。
    • 索引顺序文件：为文件建立一张索引表，但并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

索引顺序文件查找效率

• 目录文件中的一条记录就是一个文件控制块（FCB），FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。FCB实现了文件名和文件之间的映射，使得用户程序可以实现按名读取。
• 早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项，且不允许文件重名。
• 早期的多用户操作系统，采用两级目录结构，分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，User File Directory）。

两级目录结构 多级目录结构，又称为树形目录结构

• 树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护，但树形结构不便于实现文件的共享。为此，提出了无环图目录结构。

无环图目录结构 索引节点（FCB的改进）

• 很多操作系统中，磁盘块的大小与内存块、页面的大小相同。内存与磁盘之间的数据交换（即读写操作，磁盘I/O）都是以块为单位进行的，即每次读入一块，或每次写出一块。
• 在外存管理中，文件的逻辑地址空间被分为一个一个的文件块，于是文件的逻辑地址也可表示为（逻辑块号，块内地址）的形式。
• 文件的物理结构（文件分配方式）：
  • 连续分配：要求每个文件在磁盘上占有一组连续的块。读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。
    • 优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序读写时速度最快。
    • 缺点：不方便文件扩展；存储空间利用率低，会产生磁盘碎片。
  • 链接分配：采取离散分配的方式，可以为文件分配离散的磁盘块。
    • 隐式链接：除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。
      • 优点：很方便文件扩展，不会有碎片问题，外存利用率高。
      • 缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要消耗少量的存储空间。
    • 显示链接：把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表（FAT，File Allocation Table）。一个磁盘只会建立一张文件分配表，开机时文件分配表放入内存，并常驻内存。
      • 优点：很方便文件扩展，不会有碎片问题，外存利用率高，并且支持随机访问，相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
      • 缺点：文件分配表需要占用一定的存储空间。
  • 索引分配：允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表-建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
    • 链接方案：若索引表太大，一个索引块装不下，则可以将多个索引块链接起来存放。
      • 缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来，想要找到第i号索引块，必须先依次读入号索引块，这就导致磁盘I/O次数过多，查找效率低下。
    • 多层索引：建立多层索引（原理类似于多级页表），使第一层索引块指向第二层的索引块，还可根据文件大小的要求再建立第三层、第四层索引块。
      • 缺点：即使是小文件，访问一个数据块依然需要k+1次读磁盘。
    • 混合索引：多种索引分配方式的结合。如：一个文件的顶层索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表）。
      • 优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。

文件分配方式-连续分配 文件连续分配的缺点1 文件连续分配的缺点2 文件分配方式-隐式链接 文件分配方式-显示链接1 文件分配方式-显示链接2 文件分配方式-索引分配 文件分配方式-多层索引 文件分配方式-混合索引

• 存储空间的划分：将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘）。有的系统支持超大型文件，可支持由多个物理磁盘组成一个文件卷。
• 存储空间的初始化：将各个文件卷划分为目录区、文件区。
  • 目录区：主要存放文件目录信息（FCB）、用于磁盘存储空间管理的信息。
  • 文件区：用于存放文件数据。

存储空间管理--空闲表法 存储空间管理--空闲链表法和空闲盘区链 存储空间管理--位示图法

• 空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。Unix系统中采用了成组链接法对磁盘空闲块进行管理。
• 文件卷的目录区中专门用一个磁盘块作为超级块，当系统启动时需要将超级块读入内存，并且要保证内存与外存中的超级块数据一致。

存储空间管理--成组链接法之分配过程 存储空间管理--成组链接法之回收过程1 存储空间管理--成组链接法之回收过程2

• 文件共享有2种方式：①基于索引节点（硬链接）；②基于符号链（软链接）。
• 多个用户共享同一个文件，意味着系统中只有“一份”文件数据，只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。

基于索引节点的共享方式（硬链接） 基于符号链的共享方式（软连接）-创建 基于符号链的共享方式（软连接）-删除

• 文件保护：保护文件数据的安全。分为3种方式：
  • 口令保护：为文件设置一个“口令”，用户请求访问该文件时必须提供“口令”。口令一般存放在文件对应的FCB或索引节点中。
    • 优点：保存口令的空间开销不多，验证口令的时间开销也很小。
    • 缺点：正确的“口令”存放在系统内部，不够安全。
  • 加密保护：使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。
    • 优点：保密性强，不需要在系统中存储“密码”。
    • 缺点：加密/解密要花费一定时间。
  • 访问控制：在每个文件的FCB（或索引节点）中增加一个访问控制列表（Access-Control List，ACL），该表中记录了各个用户可以对该文件执行哪些操作。

文件保护之访问控制 文件系统的层次结构

• 磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据。磁盘的盘面被划分成一个个磁道，这样的一个“圈”就是一个磁道。一个磁道又被划分成一个个扇区，每个扇区就是一个“磁盘块”，各个扇区存放的数据量相同（如1KB）。最内侧磁道上的扇区面积最小，因此数据密度最大。

• 如何在磁盘中读写数据？需要把“磁头”移动到想要读写的扇区所在的磁道，磁盘会转起来，让目标扇区从磁头下面划过，才能完成对扇区的读写操作。

磁盘的物理地址 磁盘的分类

• 盘片可以更换的称为可换盘磁盘，盘片不可更换的称为固定盘磁盘。

• 一次磁盘读写操作需要的时间：
  • 寻找时间（寻道时间）：在读写数据前，将磁头移动到指定磁道所花的时间。
    • 启动磁头臂耗时为s；
    • 移动磁头：假设磁头匀速移动，每跨越一个磁道耗时为m，总共需要跨越n条磁道，则寻道时间 。
  • 延迟时间：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r（单位：转/秒，转/分），则平均所需的延迟时间 就是转一圈需要的时间，找到目标扇区平均需要转半圈，因此再乘以 。磁盘的典型转速为5400转/分或7200转/分。
  • 传输时间：从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读写的字节数为b，每个磁道上的字节数为N，则传输时间为 。每个磁道要可存放N字节的数据，所以b字节的数据需要 个磁道才能存储。
  • 总的平均存取时间为。延迟时间和传输时间都与磁盘转速相关，且为线性相关，而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间。
• 磁盘调度算法有以下几种：
  • 先来先服务算法（FCFS）：根据进程请求访问磁盘的先后顺序进行调度。
    • 优点：公平，若请求访问的磁道比较集中的话，算法性能还算得过去。
    • 缺点：若有大量进程竞争使用磁盘，请求访问得磁道很分散，则FCFS在性能上很差，寻道时间长。
  • 最短寻找时间优先（SSTF）：优先处理的磁道是与当前磁头最近的磁道，可以保证每次的寻道时间最短，但并不能保证总的寻道时间最短。其实是贪心算法的思想，只是选择眼前最优，但总体未必最优。
  • 扫描算法（SCAN，电梯算法）：只有磁头移动到最外侧磁道时才能往内移动，移动到最内侧磁道时才能往外移动。
  • LOOK调度算法：若在磁头移动方向上已经没有别的请求，则可以立即改变磁头移动的方向（边移动边观察）
  • 循环扫描算法（C-SCAN）：规定只有磁头朝某个特定方向移动时才处理磁道访问的请求，而返回时直接快速移动至起始端而不处理任何请求。
  • C-LOOK调度算法：若磁头移动的方向上已经没有磁道访问请求了，则可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。

先来先服务算法 最短寻找时间优先算法 扫描算法 LOOK调度算法 循环扫描算法 C-LOOK调度算法

• 磁头读入一个扇区数据后需要一小段时间处理，若逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的“延迟时间”。
  • 解决方案：①采用交替编号来减少延迟时间，即让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。②错位命名。

磁盘地址结构的设计 错位命名

• 磁盘初始化的3个步骤：
  • 进行低级格式化（物理格式化），将磁盘的各个磁道划分为扇区，一个扇区通常分为头、数据区域（如5112B大小）、尾三个部分组成。管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码（如奇偶校验、CRC循环冗余校验码等，校验码用于校验扇区种的数据是否发生错误）。
  • 将磁盘分区，每个分区由若干个柱面组成。（即分为C盘、D盘、E盘）
  • 进行逻辑格式化，创建文件系统，包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（如 位示图、空闲分区表）。
• 引导块：初始程序可以放在ROM（只读存储器）中，ROM中的数据在出厂时就写入了，并且以后不能再修改。注意：ROM一般是出厂时就集成在主板上。ROM中只存放很小的“自举装入程序”，完整的自举程序放在磁盘的启动块（即引导块/启动分区）上，启动块位于磁盘的固定位置。计算机开机时先运行“自举装入程序”，通过执行该程序就可以找到引导块，并将完整的“自举程序”读入内存，完成初始化。
• 拥有启动分区的磁盘称为启动磁盘或系统磁盘。
• 坏了、无法正常使用的扇区就是环块，这属于硬件故障，操作系统是无法修复的，应该将环块标记出来，以免错误地使用到它。
• 对于简单的磁盘，可以在逻辑格式化时（建立文件系统时）对整个磁盘进行环块检查，标明哪些扇区是坏扇区，比如：在FAT上标明（在这种方式中，坏块对操作系统不透明）。对于复杂的磁盘，磁盘控制器（磁盘设备内部的一个硬件）会维护一个坏块链表，同时会保留一些备用扇区，用于替换环块，这种方案称为扇区备用，且这种处理方式中，环块对操作系统透明。在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。