第4章 文件管理

• 4.1.1 文件的概念
  • 1. 文件的定义
    • 文件（File）：是以计算机硬盘为载体的存储在计算机上的信息集合，文件可以是文本文档、图片、程序等。 注：（1）在系统运行时，计算机以进程为基本单位进行资源的调度和分配。（2）在用户进行的输入、输出中，则以文件为基本单位。​​
    • 文件系统：用于实现用户输入、输出、访问、修改和保存文件等操作管理的。 从用户角度讲，文件系统是操作系统的重要部分之一，用户关心如何命名、分类和查找文件，如何保证文件数据的安全性及对文件可以进行哪些操作。而对其中的细节如文件如何存储、如何管理文件辅存区域等不是很关心。
    • 文件的结构 通过自底向上的方式来定义。
    • （1）数据项。数据项是文件系统中最低级的数据组织形式，可分为以下两种类型：
    • 基本数据项。用于描述一个对象的某种属性的一个值，是数据中可命名的最小逻辑数据单位，即原子数据。 如姓名、日期或证件号等。
    • 组合数据项。由多个基本数据项组成。
    • （2）记录。是一组相关的数据项的集合，用于描述一个对象在某方面的属性。 如一个考生的报名记录包括考生姓名、出生日期、报考学校代号、身份证号等一系列。
    • （3）文件。是指由创建者所定义的一组相关信息的集合，逻辑上可分为有结构文件和无结构文件两种。
    • 有结构文件（又称记录式文件）：由一组相似的记录组成。 如报考某学校的所有考生的报考信息记录。
    • 无结构文件（又称流式文件）：被视为一个字符流。 如一个二进制文件或字符文件。
    • 文件的特点
    • 在操作系统中，通常讲程序和数据组织成文件。
    • 文件可以是数字、字母或二进制代码，基本访问单元可以是字节、行或记录。
    • 文件可以长期存储于硬盘或其他二级存储器中，允许可控制的进程间共享访问，能够被组织成复杂的结构。
  • 2. 文件的属性 文件具有一定的属性，系统不同，文件的属性也会有所不同。
    • 通常文件有如下属性：
    • （1）名称。文件名称唯一，以容易读取的形式保存。
    • （2）标识符。标识文件系统内文件的唯一标签，通常为数字，是对人不可读的一种内部名称。
    • （3）类型。被支持不同类型的文件系统所使用。
    • （4）位置。指向设备和设备上文件的指针。
    • （5）大小。文件的当前大小（用字节、字或块表示），也可以包含文件允许的最大值。
    • （6）保护。对文件进行保护的访问控制信息。
    • （7）时间、日期和用户标识。文件创建、上次修改和上次访问的相关信息，用于保护和跟踪文件的使用。
    • 文件的属性的特点
    • 所有文件的信息都保存在目录结构，而目录结构保存在外存上。
    • 文件信息在需要时才调入内存。
    • 通常目录条目包括文件名称及唯一的标识符，而标识符定位其他属性的信息。
  • 3. 文件的基本操作 文件属于抽象数据类型。
    • （1）创建文件。
    • （2）写文件。
    • （3）读文件。
    • （4）文件重定位（文件寻址）。
    • （5）删除文件。先从目录中找到要删除文件的目录项，使之称为空项，然后回收该文件所占用的存储空间。
    • （6）截断文件。允许文件所有属性不变，并删除文件内容，即讲其长度设为0并释放其空间。
  • 4. 文件的打卡与关闭
    • 每个打开文件都有如下关联信息：
    • 文件指针。系统跟踪上次的读写位置作为当前文件位置的指针，这种指针对于打开文件的某个进程来说是唯一的，因此必须与磁盘文件属性分开保存。
    • 文件打开计数。因为多个进程可能打开同一个文件，所以系统在删除打开文件条目时，必须等待最后一个进程关闭文件。计数器跟踪打开和关闭的数量，计数为0时，系统关闭文件，删除该条目。
    • 文件磁盘位置。绝大多数文件操作都要求系统修改文件数据。该信息保存在内存中，以免为每个操作都从磁盘中读取。
    • 访问权限。每个进程打开文件都需要一个访问模式（创建、只读、读写、添加等）。该信息保留在进程的打开文件表中，以便操作系统能够允许或拒绝之后的I/O请求。
• 4.1.2 文件的逻辑结构 文件的逻辑结构实际上是指文件的内部，数据逻辑上是如何组织起来的。按逻辑结构，文件可划分为有结构文件和无结构文件。​
  • 0. 文件的逻辑结构与物理结构的区别

    

    • 区别
  • 0. 有结构文件和无结构文件的区别

    

    • 区别
  • 1. 无结构文件（流式文件）
  • 2. 有结构文件（记录式文件）

    

    

    

    • （1）顺序文件。
    • （2）索引文件。 索引表本身是定长记录的顺序文件。
    • 图示
    • 对于定长记录文件，要查找第 i 条记录，可直接根据式子计算得到第 i 条记录相对于第1条记录的地址：
    • 对于可变长记录文件，要查找第 i 条记录，必须顺序地查找前 i – 1 条记录，从而获得相应记录的长度L，进而按下式计算出第i条记录的首址：
    • （3）索引顺序文件。
    • 图示
    • 对于含有N条记录的顺序文件，查找某关键字值的记录时，平均需要查找N/2次。
    • 对于含有N条记录的索引顺序文件，假设N条记录分为√N组，索引表中有√N个表项，每组有√N条记录，查找某关键字值的记录时，先顺序查找索引表，需要查找√N/2次，然后在主文件对应的组中顺序查找，也需要查找√N/2次，因此共需要查找√N/2+√N/2=√N次。
    • （4）直接文件或散列文件。
• 4.1.3 目录结构
  • 0. 前言：目录管理的基本要求
    • “按名存取”；
    • 提高对目录的检索速度；
    • 在共享系统中提供用于控制访问文件的信息；
    • 允许文件重名，通过树形结构解决和实现。
  • 1. 文件控制块和索引结点
    • （1）文件控制块
    • 定义：文件控制块（FCB）是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。
    • FCB主要包含以下信息：
    • 基本信息。如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
    • 存取控制信息。如文件存取权限等。
    • 使用信息。如文件建立时间、修改时间等。
    • （2）索引结点
    • 引入目的：在检索目录文件的过程中，只用到了文件名，只有当查找文件名与目录项中文件名匹配成功时，才需要从该目录项中读取该文件的物理地址。故不需要把文件的所有信息都调入内存，可以节省系统开销。
    • 索引结点：有的系统（如UNIX）采用了文件名和文件描述信息分开的方法，文件描述信息单独形成一个称为索引结点的数据结构，简称 i 结点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针构成。 存在在磁盘上的所有结点称为磁盘所有结点，UNIX中的每个文件都有一个唯一的磁盘索引结点。文件被打开时，磁盘索引结点复制到内存的索引结点中，以便于使用。
  • 2. 目录结构

    

    

    

    

    

    • 在目录上可能需要执行的操作有：搜索、创建文件、删除文件、显示目录、修改目录等。
    • 考虑以下几种目录结构：
    • （1）单级目录结构。
    • 访问：当访问一个文件时，先按文件名在该目录中查找到相应的FCB，经合法性检查后执行相应的操作。
    • 新建：当建立一个新文件时，必须先检索所有目录项以确保没有“重名”的情况，然后在该目录中增设一项，把FCB的全部信息保存在该项中。
    • 删除：当删除一个文件时，先从该目录中找到该文件的目录项，回收该文件所占用的存储空间，然后清除该目录项。
    • 图示
    • （2）两级目录结构。
    • 访问：当某用户欲对其文件进行访问时，只需搜索该用户对应的UFD。
    • 图示
    • （3）多级目录结构（树形目录结构）。
    • 访问：用户要访问某个文件时，用文件的路径名标识文件，文件路径名是个字符串，由从根目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。
    • 绝对路径：从根目录出发的路径称为绝对路径。
    • 相对路径：相对路径由从当前目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。 为什么引入当前目录：当层次较多时，每次从根目录查询会浪费时间，于是加入了当前目录。进程对各文件的访问都是相对于当前目录进行的。
    • 图示
    • （4）无环图目录结构。
    • 删除：当某用户删除一个共享结点时，若系统只是简单地将它删除，则当另一共享用户需要访问时，会因无法找到这个文件而发生错误。为此，可为每个共享结点设置一个共享计数器，每当图中增加对该结点的共享链时，计数器加1；每当某用户提出删除该结点时，计数器减1。仅当共享计数器为0时，才真正删除该结点，否则仅删除请求用户的共享链。
    • 共享文件（或目录）与文件拷贝（副本）的区别：
    • 若两个文件拷贝，则每个程序员看到的是拷贝而不是原件，然而当一个文件被修改后，则另一个程序员的拷贝不会改变。
    • 对于共享文件，只存在一个真正的文件，任何改变都会为其他用户所见。
    • 图示
• 4.1.4 文件共享
  • 1. 基于索引结点的共享方式（硬链接）
    • 硬链接是指共享文件指向同一个索引结点。
    • 在这种共享方式中，如文件的物理地址及其他的文件属性等信息，不再放在目录项中，而是放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。在索引结点中还有一个链接计数count，用于表示链接到本索引结点（即文件）上的用户目录项的数目。 如count=2，表示有两个用户目录链接到本文件，或者说有两个用户共享此文件。
    • 文件的创建者删除原文件，那么索引结点也被删除了，但会留下一个悬空指针，使其他共享的用户不能访问到该文件了。
    • 如果想要删除，只需要将文件的count减1，然后删除字节目录中的相应目录项即可，其他用户仍可访问。当count=0时表示没有用户使用该文件，系统负责删除该文件。
  • 2. 利用符号链接实现文件共享（软链接）
    • 软连接是指保存共享文件的路径名，类似于Windows系统的快捷方式。
    • 文件的创建者删除原文件，其他用户通过符号链去访问它时，会出现访问失败，于是将符号链删除，不会产生任何影响。
    • 每次访问时，需要多次读盘，使得访问文件的开销变大并增加了启动磁盘的频率，此外，符号链的索引节点也需要耗费一定的磁盘空间。
    • 符号链的优点是即网络共享只需要提供该文件所在机器的网络地址及该机器中的文件路径。
  • 3. 硬链接和软链接的联系区别
    • 两种链接方式都存在一个共同问题，即每个共享文件都有几个文件名。遍历整个文件系统时，会多次遍历到该共享文件。
    • 硬链接和软链接都是文件系统中的静态共享方法。动态共享是指两个进程同时对同一个文件进行操作。
    • 硬链接就是多个指针指向一个索引结点，只要还有一个指针指向索引结点，索引节点就不能删除；软链接就算把到达共享文件的路径记录下来，当要访问文件时，根据路径寻找文件。
    • 硬链接的查找速度要比软链接的快。
• 4.1.5 文件保护

  

  • 0. 前言
    • 为什么要引入文件保护：为了防止文件共享可能会导致文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取。
    • 实现方式：口令保护、加密保护和访问控制等。
  • 1. 访问控制
  • 注意
  • 口令和密码保护都是防止用户文件被他人存取或窃取，并没有控制用户对文件的访问类型。
  • 目录操作与文件操作不同，因此需要不同的保护机制。

用一个例子来辅助记忆文件系统的层次结构：​假设某用户请求删除文件“D:/工作 目录/学生信息.xIsx”的最后100条记录。1. 用户需要通过操作系统提供的接口发出.上述请求– -用户接口2. 由于用户提供的是文件的存放路径，因此需要操作系统- -层一层地查找目录，找到对应的目录项–文件目录系统3. 不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限一一存取控制模块(存取控制验证层)4. 验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址—逻辑文件系统与文件信息缓冲区5. 知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址—物理文件系统6. 要删除这条记录，必定要对磁盘设备发出请求–设备管理程序模块7. 删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收—-辅助分配模块

目录实现的基本方法有线性表和哈希表。​目录的实现就是为了查找。目录查询是通过在磁盘上反复搜索完成的，需要不断进行I/O操作，开销较大，所以为了减少I/O操作，把当前使用的文件目录复制到内存，以后要使用该文件时只需在内存中操作，降低了磁盘操作次数，提高了系统速度。​

• 4.2.1 文件系统层次结构
• 1. 用户调用接口：文件系统为用户提供与文件及目录有关的调用。 如新建、打开、读写、关闭、删除文件，建立、删除目录等。
• 2. 文件目录系统：主要功能是管理文件目录。 如管理活跃文件目录表、管理读写状态信息表、管理用户进程的打开文件表、管理与组织存储设备上的文件目录结构、调用下一级存取控制模块。
• 3. 存取控制验证模块：实现文件保护，把用户的访问请求与FCB中指示的访问控制权限进行比较，以确认访问的合法性。
• 4. 逻辑文件系统与文件信息缓冲区：根据文件的逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号。
• 5. 物理文件系统：把逻辑记录所在的相对块号转换成实际的物理地址。
• 6. 辅助分配模块：管理辅存空间，即负责分配辅存空闲空间和回收辅存空间。
• 7. 设备管理程序模块：主要功能是分配设备、分配设备读写缓冲区、磁盘调度、启动设备、处理设备中断、释放设备读写缓冲区、释放设备等。
• 4.2.2 目录实现
• 1. 线性列表
• 2. 哈希表
• 4.2.3 文件实现 文件的实现就是研究文件的物理结构，即文件数据在物理存储设备上是如何分布和组织的。同一个问题有两方面的回答：一是文件的分配方式，讲的是对磁盘非空闲块的管理；二是文件存储空间管理，讲的是对磁盘空闲块的管理。​

  

  文件分配对应于文件的物理结构，是指如何为文件分配磁盘块。常用的磁盘空间分配方法有三种：连续分配、链接分配和索引分配。​​

  

  

   

  • 1. 文件分配方式
  • （1）连续分配 文件的连续分配可以用第一块的磁盘地址和连续块的数量来定义。一个文件的目录条目包括开始块的地址和该文件所分配区域的长度。连续分配支持顺序访问和直接访问。​​
  • 图示
  • （2）链接分配
  • ①隐式链接。 每个文件对应一个磁盘块的链表；磁盘块分布在磁盘的任意地方，除最后一个盘块外，每个盘块都有指向下一个盘块的指针，指针对用户是透明的；目录包括文件第一块的指针和最后一块的指针；​​
  • 创建新文件：目录中增加一个新条目。每个目录项都有一个指向文件首块的指针（也有一个指向文件最后一块的指针），该指针初始化为NULL表示空文件，大小字段为0。
  • 写文件：通过空闲空间管理系统找到空闲块，讲该块链接到文件尾部，以便写入。
  • 读文件：通过块到块的指针顺序读块。
  • 图示
  • ②显示连接。 文件分配表FAT整个磁盘中仅有一张。每个表项存放对应块的下一块链接指针，即下一个盘块号。文件的第一个盘块号记录在目录中，后续的盘块可通过查FAT查到。
  • 当某进程请求操作系统分配一个磁盘块时，操作系统只需要从FAT中找到为-2的表项，并将对应的磁盘块分配给进程即可。
  • FAT表在启动时就会被读入内存，因此查找FAT的过程是在内存中进行，提高了检索速度。
  • FAT表与全部盘块一一对应，用特殊数字-1表示文件的最后一块，用-2表示这个磁盘块是空闲的（也可以用-3，-4等）。
  • 图示
  • （3）索引分配 链接分配解决了连续分配的外部碎片和文件大小管理的问题，但链接分配不能有效之间访问（FAT除外），索引分配解决了这个问题。
  • 图示
  • 每个文件都有其索引块，这是一个数组，数组里面是磁盘块地址。
  • 索引块的第 i 个条目指向文件的第 i 块。
  • 目录条目包括索引块的地址。
  • 要读第 i 块，通过索引块的第 i 个条目的指针来查找和读入所需的块。
  • 创建文件时，索引块的所有指针都设为空，首次写入第 i 块时，先从空闲空间中取得一个块，再将其地址写到索引块的第 i 个条目。
  • 访问文件需要两次访问外存——首先要读取索引块的内容，然后访问具体的磁盘块，降低了文件的存取速度。为了解决这问题，通常将文件的索引块读入内存的缓冲区，以加快文件的访问速度。
  • 索引块的大小要合适，每个文件必须有一个索引块，因此索引块尽可能小，但太小又无法支持大文件。可采用如下方法来解决：
  • 链接方案。将多个索引块链接起来。
  • 多层索引。多层索引使第一层索引块指向第二层的索引块，第二层的索引块再指向文件块。甚至可以第三层、第四层。
  • 混合索引。将多种索引分配方式相结合的分配方式。
  • 2. 文件存储空间管理

    

    

    

    

    

    

    操作系统保存着链头、链尾指针。适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作​

    

    操作系统保存着链头、链尾指针。​离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高。

    

    

    

    • （1）文件存储器空间的划分与初始化。
    • 逻辑卷与物理盘的关系：文件卷可以是物理盘的一部分，也可以是整个物理盘，支持超大型文件的文件卷也可由多个物理盘组成。
    • （2）文件存储器空间管理。 文件存储设备的管理实质上是对空闲块的组织和管理，包括空闲块的组织、分配与回收等问题。
    • ①空闲表法：将所有空闲区记录在一个表中。适合连续分配。
    • 如何分配磁块：与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
    • 如何回收磁盘块：与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况―—①回收区的前后都没有相邻空闲区;②回收区的前后都是空闲区;③回收区前面是空闲区;④回收区后面是空闲区。总之，回收时需要注意表项的合并问题。
    • ②空闲链表法：将所有空闲块链成一个链表。适合离散分配。
    • 空闲盘块链：以盘块为单位组成一条空闲链。
    • 如何分配：若某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。
    • 如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。
    • 空闲盘区链：以盘区为单位组成一条空闲链。
    • 如何分配：若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给-一个文件， 注意分配后可能要修改相应的链指针、盘区大小等数据。
    • 如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的-一个空闲盘区挂到链尾。
    • ③位示图法：用一串二进制位反映磁盘空间中分配使用情况，每个物理块对应一位, 分配物理块为1，否则为0申请物理块时，可以在位示图中查找为0的位，返回对应物理块号；归还时，将对应位转置0。描述能力强，适合各种物理结构（对连续文件稍差），本身占空间少，可常驻内存，而字位号到块号的转换也不难。Linux使用。
    • 位示图：每个二进制对应一个盘块，本例中“0”表示盘块空闲，“1”表示盘块已分配。 注意：所使用的位示图中行和列都是从1开始编号，若考试题目中从0开始编号，则需要调整。
    • 盘块号、行号、列号都从1开始
    • 盘块号、行号、列号都从0开始
    • 如何分配：若文件需要k个块，①顺序扫描位示图，找到k个相邻或不相邻的“0”；②根据字号、位号算出对应的盘块号，将相应盘块分配给文件；③将相应位设置为“1”。
    • 如何回收：①根据回收的盘块号计算出对应的行号、列号；②将相应二进制位设为“0”。
    • ④成组链接法：链上每个节点记录1组空闲块。适合大型文件系统，分配、释放快，链本身短,占空间少。UNIX用 。
    • 图示

• 4.3.1 磁盘的结构

  

  

  

  • 磁盘示意图
  • 磁盘：是由表面涂有磁性物质的金属或塑料构成的圆形盘片。 磁盘安装在一个磁盘驱动器中，由磁头臂、用于旋转磁盘的主轴和用于数据输入/输出的电子设备组成。磁盘按不同的方式可分为若干类型：​
  • 固定头磁盘：磁头相对于盘片的径向方向固定的，每个磁道一个磁头。
  • 活动头磁盘：磁头可移动的，磁头臂可来回伸缩定位磁道。
  • 固定盘磁盘：磁盘永久固定在磁盘驱动器内的。
  • 可换盘磁盘：可移动和替换磁盘的。
  • 柱面：所有盘片上相对位置相同的磁道组成柱面。 磁盘的柱面数与一个盘面上的磁道数是相等的。由于每个盘面都有自己的磁头，因此，盘面数等于总的磁头数。
  • 磁头：导体线圈组成，从磁盘存取数据。 读/写期间，磁头固定，磁盘在下面高速旋转。
  • 磁道：磁盘盘面上的数据存储在一组同心圆中，称为磁道。
  • 扇区（盘块）：从圆心向外画直线，可以将磁道划分为若干个弧段，每个磁道上一个弧段被称之为一个扇区。 扇区固定存储大小，通常为512B。扇区是磁盘可寻址的最小存储单位。磁盘地址用“柱面号 · 盘面号 · 扇区号（或块号）”表示。​
  • 磁道间隙：相邻磁道通过一定间隙分隔开，以避免精度错误。扇区间隙亦是如此。 扇区的密度从最外道向里道增加，磁盘的存储能力受限于最内道的最大记录密度。
  • 4.3.2 磁盘调度算法
    • 1. 读写时间

    

    一次磁盘读写操作的时间由寻找（寻道）时间、延迟时间和传输时间决定。除了减少寻找时间外，减少延迟时间也是提高磁盘传输效率的重要因素。可以对盘面扇区进行交替编号，对磁盘片组的不同盘面错位命名。​寻道时间和延迟时间都可以通过一定的方法进行削减，但传输时间是磁盘本身性质所决定的，不能通过一定的措施减少。​

    • （1）寻找时间Ts。 在磁盘的存取时间计算中，寻道（寻找）时间与磁盘的调度算法有关。调度算法直接决定寻找时间，从而决定总的存取时间。​​
    • （2）延迟时间Tr。 延迟时间和传输时间都与磁盘旋转速度相关，且线性相关。
    • （3）传输时间Tt。
    • （4）启动时间。 一般忽略，控制器的启动时间。
    • 2. 调度算法

    

    • （1）先来先服务（First Come First Served，FCFS）算法。
    • 示例：磁盘请求队列中的请求顺序分别为55，58，39，18，90，160，150，38，184，而磁头的初始位置是磁道100，采用FCFS算法时磁头运行轨迹如下：

    

    磁头共移动了100-55 + 58-55 + 58-39 + 39-18 + 90-18 + 160-90 + 160-150 + 150-38 + 184-38=45+3+19+21+72+70+10+112+146=498个磁道，平均寻找长度=498/9=55.3。（注：由于磁头的初始位置是磁道100，而FCFS算法是先来先服务，所以要将磁头从100移到第一个请求55的地方，需要移动磁道数为100-55=45个；而根据FCFS第二个请求按顺序是58，磁头从55到58要移动磁道数为58-55=3个，….，后面依次按照FCFS算法来计算即可。磁道顺序是100——55——58——39——18——90——160——150——38——184）。

    • （2）最短寻找时间优先（Shortest Seek Time First，SSTF）算法。
    • 示例：磁盘请求队列中的请求顺序分别为55，58，39，18，90，160，150，38，184，而磁头的初始位置是磁道100，采用SSTF算法时磁头运行轨迹如下：

      

    磁头共移动了100-90+90-58+58-55+55-39+39-38+38-18+150-18+160-150+184-160=10+32+3+16+1+20+132+10+24=248个磁道，平均寻找长度=248/9=27.5。（注：由于磁头的初始位置是磁道100，而SSTF算法是最短寻找时间优先，比较请求队列中的几个顺序，发现90离100最近，即100-90=10是最短寻找时间，现在磁头到90位置了，继续比较，发现58到90的距离是最短的，即90-58=32是最短寻找时间，…，后面依次按照SSTF算法来计算即可。磁道顺序是100——90——58——55——39——38——18——150——160——184）。

    • （3）扫描（SCAN）算法（又称电梯调度算法）。 采用SCAN算法不但要知道磁头的当前位置，还要知道磁头的移动方向。
    • 示例：磁盘请求队列中的请求顺序分别为55，58，39，18，90，160，150，38，184，而磁头的初始位置是磁道100，假设磁头沿着磁道号增大的顺序移动，采用SCAN算法时磁头运行轨迹如下：

      

    磁头共移动了150-100+160-150+184-160+200-184+200-90+90-58+58-55+55-39+39-38+38-18=50+10+24+16+110+32+3+16+1+20=282个磁道，平均寻找长度=282/9=31.33。（注：由于磁头的初始位置是磁道100，而SCAN算法规定了磁头移动方向是沿着磁道号增大的顺序移动，故150离100最近而不是90，并且要移动到最大值200（即磁盘端点），才开始往回移动也就是从200移到90。磁道顺序是100——150——160——184——200——90——58——55——39——38——18）。​

    • （4）循环扫描（Circular SCAN，C-SCAN）算法。
    • 示例：磁盘请求队列中的请求顺序分别为55，58，39，18，90，160，150，38，184，而磁头的初始位置是磁道100，假设磁头沿着磁道号增大的顺序移动，采用C-SCAN算法时磁头运行轨迹如下：

      

    磁头共移动了150-100+160-150+184-160+200-184+200-0+18-0+38-18+39-38+55-39+58-55+90-58=50+10+24+16+200+18+20+1+16+3+32=390个磁道，平均寻找长度=390/9=43.33。（注：与SCAN算法不同的是，到达磁盘端点200时，下一个访问的磁道号是0（即起始磁盘端点）而不是距离最近的90号。磁道顺序是100——150——160——184——200——0——18——38——39——55——58——90）。​​

    • 改进：实际中不必到大磁盘端点（即200号和0号），只需要到达最远端的一个请求即可返回。
    • LOOK调度（即这种形式的SCAN算法）

    

    • C-LOOK调度（即这种形式的C-SCAN算法）

    

  • 4.3.3 磁盘的管理
    • 1. 磁盘初始化：对磁盘进行低级格式化和逻辑格式化。
      • 低级格式化（物理分区）：在磁盘能够存储数据之前，它必须分成扇区以便磁盘控制器能进行读和写操作。
      • 逻辑格式化：对物理分区创建文件系统，操作系统将初始的文件系统数据结构存储道磁盘上。
    • 2. 引导块：存放自举程序。 计算机启动时需要运行一个初始化程序（自举程序）。
      • 自举程序的作用：初始化CPU、寄存器、设备控制器和内存等，接着启动操作系统。
      • 自举程序通常保存在ROM中。 只在ROM中保留很小的自举程序，将完整功能的自举程序保留在磁盘的启动块上，启动块位于磁盘的固定位。拥有启动分区的磁盘称为启动磁盘或系统磁盘（通常就是我们说的C盘）。
    • 3. 坏块：对于损坏扇区的处理。 对于坏块的处理就算使系统不去使用它。坏块属于硬件故障，操作系统是不能修复的。
      • 对于简单磁盘，如电子集成驱动器（IDE），坏扇区可手工处理。
      • 对于复杂磁盘，如小型计算机系统接口（SCSI），其控制器维护一个磁盘坏块链表，在出厂前进行低级格式化时就已经初始化，并在使用过程中不断更新。