操作系统——文件管理
- 2019 年 10 月 14 日
- 笔记
目录
一、文件系统
1.1文件与文件系统
1、文件
1）数据项
在文件系统中，数据项是最低级的数据组织形式。分为两种类型：
- 基本数据项。描述一个对象某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，又称字段。除了数据名还有数据类型
- 组合数据项。由若干基本数据项组成
数据项的名字和类型共同定义了数据项的“型”，表征一个实体在数据项上的数据称为“值”
2）记录
记录是一组相关数据项的集合，用于描述一个对象在某方面的属性
一个记录应包含哪些数据项取决于需要描述对象的哪个方面
唯一标识一个记录的一个或多个数据项称为关键字
3）文件
文件是具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件
有结构文件由若干个相关记录组成，无结构文件看成是一个字符流
文件是文件系统中最大的数据单位
文件属性包括：文件类型、文件长度、文件的物理地址、文件的建立时间
2、文件系统
1）定义
文件系统是操作系统用于明确磁盘或分区上的文件的方法和数据结构，即在磁盘上组织文件的方法；也指用于存储文件的磁盘或分区，或文件系统种类
操作系统中负责管理和存储文件信息的软件机构称为文件管理系统，简称文件系统
文件系统由三部分组成：与文件管理有关软件、被管理文件以及实施文件管理所需数据结构
从系统角度来看，文件系统是对文件存储器空间进行组织和分配，负责文件存储并对存入的文件进行保护和检索的系统。具体地说，它负责为用户建立文件，存入、读出、修改、转储文件，控制文件的存取，当用户不再使用时撤销文件等
2）文件系统的层次结构
文件系统的模型可分为三个层次：最底层是对象及其属性，中间层是对对象进行操纵和管理的软件集合，最高层是文件系统提供给用户的接口
文件系统管理的对象：文件、目录、磁盘存储空间
与文件系统有关的软件分为四个层次：
- I/O控制层。文件系统的最底层，主要由磁盘驱动程序组成
- 基本文件系统层。处理内存与磁盘之间数据块的交换
- 基本 I/O管理程序。完成与磁盘 I/O有关的事务
- 逻辑文件系统。处理与文件和记录相关的操作
文件系统的接口：命令接口，程序接口
1.2文件的逻辑结构
用户看到的文件称为逻辑文件，它由一系列逻辑记录组成。从用户角度看，文件的逻辑记录是能被存取的基本单位
1、顺序文件
排列方式：
- 串结构：按存入时间的先后排序。对串结构文件进行检索时，每次都必须从头开始，逐个查找
- 顺序结构：按关键字排序。检索时可利用有效的查找算法，如折半查找、跳步查找等
优点：
- 最佳应用场合是对文件中的记录进行批量存取
- 所有逻辑文件中顺序文件的存取效率最高
- 顺序存储设备（如磁带）只能存储顺序存储文件
缺点：
- 用户查找或修改单个记录需要在记录中逐个查找
- 增删一个记录很困难
2、索引文件
出现原因：变长记录文件查找一个记录必须从第一个记录查起，耗时很长
为变长记录文件建立一张索引表，主文件中的每个记录在索引表中设置一个表项，包括指向记录的指针和记录的长度
索引表按关键字排序，其本身也是一个定长记录的顺序文件。这样就把对变长记录顺序文件的顺序检索变为对定长记录索引文件的随机检索
优点：
- 将需要顺序查找的文件改造成可随即查找的文件，提高了查找速度
- 记录的插入、删除非常方便
缺点：除了主文件，还需配置一张索引表，每个记录都要有一个索引项，增加了存储开销
3、索引顺序文件
基本克服了边长记录顺序文件不能随机访问，以及不便于记录插入、删除的缺点，但记录仍按关键字排序
增加了两个新特征：
- 引入文件索引表，通过该表能实现对顺序文件的随机访问
- 增加溢出文件，记录增加的、删除的、修改的记录
1）一级索引顺序文件
首先将变长记录顺序文件的所有记录分为若干组（如50个一组），然后为顺序文件建立一张索引表，并为每组的第一个记录在索引表中建立一个索引项，包括该记录的关键字和指向该记录的指针
对索引顺序文件进行检索时，先利用用户提供的关键字和某种查找算法检索索引表，找到该记录所在组；然后利用顺序查找法查找主文件，直到找到记录
2）两级索引顺序文件
先为文件建立一张低级索引表，若干记录一组；再为低级索引表建立一张高级索引表，若干低级索引表一组。每个表项存放的是低级索引表每组第一个表项的关键字以及指向该表项的指针
1.3文件目录
对目录管理的要求：
- 实现”按名存取“
- 提高对目录的检索速度
- 文件共享
- 允许文件重名
1、文件控制块和索引节点
1）文件控制块
文件控制块中应包括三类信息：基本信息，存取控制信息，使用信息
基本信息包括：文件名，文件物理位置，文件逻辑结构，文件物理结构
存取控制信息包括：文件主、核准用户、一般用户的存取权限
使用信息包括：文件的建立日期和时间，文件上次修改的日期和时间，当前使用信息
2）索引结点
在检索目录文件的过程中只用到了文件名，仅当其中的文件名和指定查找的文件名匹配时，才从该目录文件中读取文件的物理地址
为使检索更高效，系统把文件名和文件描述信息分开，将文件描述信息单独形成一个称为索引结点的数据结构
- 磁盘索引结点：存放在磁盘上的索引结点。每个文件有唯一的磁盘索引结点
- 内存索引结点：存放在内存中的索引结点。当文件被打开时，要将磁盘索引结点拷贝到内存索引结点中
2、单级文件目录和两级文件目录
1）单级文件目录
整个文件系统只建立一张目录表，每个文件占一个目录项，每个目录项含文件名、文件扩展名、文件长度、文件类型、文件物理地址及其他文件属性。此外还设置一个状态位表示文件是否空闲
建立新文件时，先检索所有的目录项以保证新文件名在目录中唯一。然后从目录表中找出一个空白目录项，填入新文件的信息并置状态位为 1。删除文件时，先从目录中找到该文件的目录项，回收文件所占存储空间，再清除目录项
优点：简单
缺点：只能实现按名存取，查找速度慢，不允许重名，不便于实现文件共享
2）两级文件目录
为每个用户建立一个单独的用户文件目录 UFD，它由用户所有文件的文件控制块组成
系统中建立一个主文件目录 MFD，MFD中每个用户目录文件都占有一个目录项，包括用户名和指向该用户目录文件的指针
在两级目录文件中，如果用户希望有自己的 UFD，可请求系统为自己建立；当不再需要时请求系统管理员撤销即可。有了 UFD后，用户想增删文件，OS只需检查该用户的 UFD，然后执行相关操作
3、树形目录结构
电脑日常使用的结构即树形目录结构。以 Linux为例，方框代表目录文件，圆圈代表数据文件
1）路径名
在树形结构中，从根目录到任何数据文件都只有唯一的路
该路径从主目录开始，把全部目录文件名与数据文件名用”/“连接起来你，构成该数据文件唯一的路径名
2）当前目录
进程运行时访问的文件大多局限于某个范围，每次从主目录开始查找极不方便，于是为进程设置一个”当前目录“，进程对各文件的访问都相当于当前目录进行
从当前目录到数据文件构成的路径叫相对路径名
从主目录开始的路径名叫绝对路径名
1.4文件共享
1、基于有向无循环图
树形结构目录不适合文件共享
如果允许一个文件可以有多个父目录，即有多个属于不同用户的多个目录，同时指向同一个文件，虽然会破坏树的特性，但这些用户可用对称的方式实现文件共享而不必通过其属主目录访问
如何建立父目录与共享文件间的链接？
方法一：
如果文件目录中包含的是文件的物理地址，即文件所在盘块的盘号，链接时必须将文件的物理地址拷贝到父目录中
但以后父目录向文件中添加新内容时必然相应增加新的盘块，这些新增盘块只会出现在执行了操作的目录中，新增的内容不能被共享
方法二：
在文件目录中只设置文件名和指向相应索引结点的指针
如图，用户 Wang和 Lee的文件目录中都设置有指向共享文件的索引结点指针，任何用户对共享文件的操作都会引起相应结点内容的改变，这些改变对用户可见，从而能让用户共享
索引结点中有一个链接计数 count，表示链接到本索引结点上的用户目录项的数目
当某用户 C创建一个文件，并有其它用户 B共享该文件。当 C删除文件时，也删除了该文件的索引结点，会导致 B的指针悬空，执行的操作半途而废
2、利用符号链接
1）基本思想
允许一个文件或子目录有多个父目录，但仅有一个作为主父目录，其它父目录通过符号链接方式与之相链接
这样的好处是属主结构（实线连接起来的结构）仍然是简单树，对文件的删除、查找更为方便
2）实现
为使链接父目录 D5能共享文件 F，可以由系统创建一个 LINK类型的新文件，取名 F，并将 F写入链接父目录 D5中，以实现 D5与 F8的链接。新文件 F中只包含被链接文件 F8的路径名
当用户通过 D5访问被链接的文件 F8，且正要读 LINK类新文件时，此要求被 OS截获，OS根据新文件中的路径名找到文件 F8进行操作。这样就实现了用户 B对文件 F的共享
优点：
- 只有文件主才拥有指向其索引结点的指针，共享该文件的其它用户只有该文件的路径名
- 当文件拥有者删除共享文件后，其他用户会因为系统找不到该文件而访问失败，然后删除符号链而不会有任何影响
缺点：
- 其他用户读共享文件时，系统根据给定的文件路径名逐个分量查找目录，开销甚大，且增加了启动磁盘的频率
- 要为每个共享用户建立一条符号链，耗费一定的磁盘空间
1.5文件保护
为了防止文件共享可能会导致的文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取，即解决对文件的读、写、执行的许可问题。为此必须在文件系统中建立相应的文件保护机制
文件保护通过口令保护、加密保护和访问控制等方式实现。其中，口令保护和加密保护是为了防止用户文件被他人存取或窃取，而访问控制用于控制用户对文件的访问方式
1、访问类型
对文件的保护可以从限制对文件的访问类型出发。可加以控制的访问类型主要有以下几种：
- 读：从文件中读
- 写：向文件中写
- 执行：将文件装入内存并执行
- 添加：将新信息添加到文件结尾部分
- 删除：删除文件，释放空间
- 列表清单：列出文件名和文件属性
此外可以对文件的重命名、复制、编辑等加以控制。这些高层的功能可以通过系统程序调用低层系统调用来实现
保护可以只在低层提供。例如，复制文件可利用一系列的读请求来完成，这样具有读访问的用户同时也具有复制和打印的权限
2、访问控制
解决访问控制最常用的方法是根据用户身份进行控制。而实现基于身份访问的最普通方法是为每个文件和目录增加一个访问控制列表，以规定每个用户名及其所允许的访问类型
这种方法的优点是可以使用复杂的访问方法，缺点是长度无法预期并且可能导致复杂的空间管理。可使用精简的访问列表可以解决这个问题，精简的访问列表包括拥有者、组和其他三种用户类型：
- 拥有者：创建文件的用户。
- 组：一组需要共享文件且具有类似访问的用户。
- 其他：系统内的所有其他用户。
只需用三个域写出访问列表中三类用户的访问权限：
- 文件拥有者在创建文件时，说明创建者用户名及所在的组名；系统在创建文件时也将文件主的名字、所属组名写在该文件的 FCB中
- 用户访问该文件时，按照拥有者所拥有的权限访问文件，如果用户和拥有者在同一个用户组则按照同组权限访问，否则只能按其他用户权限访问
口令和密码是另外两种访问控制方法
- 口令指用户在建立一个文件时提供一个口令，系统为其建立 FCB时附上相应口令，同时通知允许共享该文件的其他用户。用户请求访问时必须提供相应口令
- 密码指用户对文件进行加密，文件被访问时需要使用密钥
注意：
- 现代操作系统常用的文件保护方法，是将访问控制列表与用户、组和其他成员访问控制方案一起组合使用
- 对于多级目录结构而言，不仅需要保护单个文件，而且还需要保护子目录内的文件, 即需要提供目录保护机制。目录操作与文件操作并不相同，因此需要不同的保护机制
二、文件系统实现
2.1文件系统层次结构
1、用户调用接口
文件系统为用户提供与文件及目录有关的调用，如新建、打开、读写、关闭、删除文件，建立、删除目录等
此层由若干程序模块组成，每一模块对应一条系统调用，用户发出系统调用时，控制即转入相应的模块
2、文件目录系统
文件目录系统的主要功能是管理文件目录，其任务有管理活跃文件目录表、管理读写状态信息表、管理用户进程的打开文件表、管理与组织在存储设备上的文件目录结构、调用下一级存取控制模块
3、存取控制验证
实现文件保护主要由该级软件完成，它把用户的访问要求与FCB中指示的访问控制权限进行比较，以确认访问的合法性
4、逻辑文件系统与文件信息缓冲区
逻辑文件系统与文件信息缓冲区的主要功能是根据文件的逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号
5、物理文件系统
物理文件系统的主要功能是把逻辑记录所在的相对块号转换成实际的物理地址
6、分配模块
分配模块的主要功能是把逻辑记录所在的相对块号转换成实际的物理地址
7、设备管理程序模块
设备管理程序模块的主要功能是分配设备、分配设备读写用缓冲区、磁盘调度、启动设备、处理设备中断、释放设备读写缓冲区、释放设备等
2.2目录实现
目录分配和目录管理算法的选择对文件系统的效率、性能和可靠性有很大的影响
1、线性列表
最为简单的目录实现算法就是使用存储文件名和数据块指针的线性列表，这种方法编程简单但是运行时较为费时
要创建新文件，必须首先搜索目录以确定没有同样名称的文件存在，接着，在目录后增加一个新条目，要删除文件时，根据给定文件名搜索目录，接着释放分配给他的空间，如果需要重用目录条目，可以有许多办法，可以将目录条目标记为不再使用或者可以将它加到空闲目录条目上
2、哈希表
用于文件目录的另一个数据结构就是哈希表，采用这种方法时，处理使用线性列表存储目录条目，还使用了哈希数据结构。哈希表根据文件名得到一个值，并返回一个指向线性列表中元素的指针，大大减小了目录搜索时间
哈希表的最大困难就是其通常固定的大小和哈希函数对大小的依赖性
2.3文件实现
1、文件分配方式
文件分配对应于文件的物理结构，是指如何为文件分配磁盘块。常用的磁盘空间分配方式有三种：连续分配、链接分配和索引分配。有的系统对三种方式都支持，但是更普遍的是一个系统只提供一种方法支持
1）连续分配
连续分配方法要求每个文件在磁盘上占有一组连续的块。磁盘地址定义了磁盘上的一个线性排序，这种排序使作业访问磁盘时需要的寻道数和寻道时间最小
文件的连续分配可以用第一块的磁盘地址和连续块的数量来定义。如果文件有 n块长并从位置 b开始，那么该文件将占 b，b + 1，b + 2，…，b + n – 1
一个文件的目录条目包括开始块的地址和该文件所分配区域的长度
连续分配支持顺序访问和直接访问
优点：实现简单、存取速度快
缺点：
- 文件长度不宜动态增加，因为一个文件末尾后的盘块可能已经分配给其他文件，一旦需要增加就需要大量移动盘块
- 反复增删文件后会产生外部碎片（与内存管理分配方式中的碎片相似），并且很难确定一个文件需要的空间大小，因而只适用于长度固定的文件。
2）链接分配
链接分配解决了连续分配的碎片和文件大小问题
采用链接分配，每个文件对应一个磁盘块的链表；磁盘块分布在磁盘的任何地方，除最后一个盘块外，每个盘块都有指向下一个盘块的指针，这些指针对用户是透明的
目录包括文件第一块的指针和最后一块的指针。创建新文件时，目录中会增加一个新条目
链接分配中每个目录项都有一个指向文件首块的指针，该指针初始化为 NULL 以表示空文件，大小字段为0。写文件会通过空闲空间管理系统找到空闲块，将该块链接到文件的尾部，以便于写入；读文件则通过块到块的指针进行读操作
优点：
- 链接分配方式没有外部碎片，空闲空间列表上的任何块都可以用来满足请求
- 创建文件时并不需要说明文件大小，只要有空闲块文件就可以创建，也无需合并磁盘空间
缺点：
- 无法直接访问盘块，只能通过指针顺序访问文件，以及盘块指针消耗了一定的存储空间
- 链接分配方式的稳定性也是一个问题
- 系统在运行过程中由于软件或者硬件错误导致链表中的指针丢失或损坏，会导致文件数据的丢失
3）索引分配
链接分配解决了连续分配的外部碎片和文件大小管理的问题，但是链接分配不能有效支持直接访问（FAT除外），索引分配解决了这个问题
索引分配把每个文件的所有的盘块号都集中在一起构成索引块。每个文件都有其索引块，这是一个磁盘块地址的数组。索引块的第 i 个条目指向文件的第 i 个块，目录条目包括索引块的地址，要读第 i 块，通过索引块的第 i 个条目的指针来查找和读入所需的块
创建文件时，索引块的所有指针都设为空。当首次写入第 i 块时，先从空闲空间中取得一个块，再将其地址写到索引块的第 i 个条目
优点：索引分配支持直接访问，且没有外部碎片问题
缺点：索引块的分配增加了系统存储空间的开销
索引块的大小是一个重要的问题，每个文件必须有一个索引块，因此索引块应尽可能小，但索引块太小就无法支持大文件。可以采用以下机制来处理这个问题：
链接方案：一个索引块通常为一个磁盘块，因此本身能直接读写。为了处理大文件，可以将多个索引块链接起来
多层索引：多层索引使第一层索引块指向第二层的索引块，第二层的索引块再指向文件块。这种方法根据最大文件的大小的要求，可以继续到第三层或第四层。例如，4096B的块，能在索引块中存入1024个4B的指针。两层索引允许1048576个数据块，即允许最大文件为4G
混合索引：将多种索引分配方式相结合的分配方式。例如，系统既采用直接地址又采用单级索引分配方式或两级索引分配方式
此外，访问文件需要两次访问外存——首先要读取索引块的内容，然后在访问具体的磁盘块。因而降低了文件的存取速度，为了解决这一问题，通常将文件的索引块读入内存的缓冲区，以加快文件的访问速度
2、文件存储器空间管理
文件存储管理空间的划分与初始化
一般来说，一个文件存储在一个文件卷中。文件卷可以是物理盘的一部分，也可以是整个物理盘，支持超大型文件的文件卷也可以是有多个物理盘组成。
在一个文件卷中，文件数据信息的空间（文件区）和存放文件控制信息FCB的空间（目录区）是分离的。由于存在很多种类的文件表示和存放格式，所以现代操作系统中一般都有很多不同的文件管理模块，通过他们可以访问不同格式的逻辑卷中的文件。逻辑卷在提供文件服务前，必须由对应的文件程序进行初始化，划分好目录区和文件区，建立空闲空间管理表格及存放逻辑卷信息的超级块。
文件存储设备分成许多大小相同的物理块，并以块为单位交换信息，因此，文件存储设备的管理实质上是对空闲块的组织和管理，它包括空闲块的组织，分配与回收等问题。
1）空闲表法
空闲表法属于连续分配方式，它与内存的动态分配方式类似，为每个文件分配一块连续的存储空间
系统为外存上的所有空闲区建立一张空闲盘块表，每个空闲区对应一个空闲表项，其中包括表项序号、该空闲区第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列
空闲盘区的分配与内存的动态分配类似，同样是采用首次适应算法、循环首次适应算法等。例如，在系统为某新创建的文件分配空闲盘块时，先顺序的检索空闲盘块表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户（进程），同时修改空闲盘块表
系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并
2）空闲链表法
将所有空闲盘区拉成一条空闲链，根据构成连所有的基本元素不同，可以把链表分成两种形式：空闲盘块链和空闲盘区链
①空闲盘块链是将磁盘上所有空闲空间以盘块为单位拉成一条链
当用户因创建文件而请求分配存储空间时，系统从链首开始，一次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块一次并入空闲盘块链的末尾
优点：分配和回收一个盘块很简单
缺点：为一个文件分配盘块时，可能要重复多次操作
②空闲盘区链是将磁盘上所有空闲盘区（每个盘区可包含若干个盘块）拉成一条链
在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小（盘块数）的信息。分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区域相邻接的空闲盘区相合并
3）位视图法
位视图是利用二进制的移位来表示磁盘中的一个盘块的使用情况
磁盘上所有的盘块都有一个二进制位与之对应，当其值为0时，表示对应的盘块空闲；当其值为1时，表示对应的盘块已分配
盘块的分配：
- 顺序扫描位视图，从中找出一个或一组其值为0的二进制位
- 将所找到的一个或一组二进制位，转换成与之对应的盘块号。假定找到的其值为0的二进制位，位于位视图的第 i 行，第 j 列，则其相应的盘块号硬干下式计算：b = n * ( i – 1) + j
- 修改位视图，令 map[ i , j ] = 1
盘块的回收：
- 将回收盘块的盘块号转换成位视图中的行号和列号
- 修改位视图，令 map[ i , j ] = 0
4）成组链接法
空闲表法和空闲链表法都不适用于大型文件系统，因为会造成空闲表或空闲链表太大
UNIX系统中采用成组链接法，这种方法结合了空闲表和空闲链表法两种方法，克服了表太大的缺点
思想：把顺序的 n个空闲扇区地址保存在第一个空闲扇区内，其后一个空闲扇区则保存另一顺序空闲扇区的地址，如此继续直至所有空闲扇区均予以链接。系统只需要保存一个指向第一个空闲扇区的指针
表示文件存储器空闲空间的位向量表或第一个成组链块以及卷中的目录区、文件区划分都需要存放在辅存储器中，一般放在卷头位置，UNIX系统中叫超级块。在对卷中文件进行操作前，超级块需要预先读入系统空间的主存，并且经常保持主存超级块与辅存卷中超级块的一致性
三、磁盘组织与管理
3.1磁盘的结构
磁盘是表面涂有磁性物质的金属或塑料构成的圆形盘片
通常一个称为磁头的导体线圈从磁盘中存取数据。在读/写操作期间，磁头固定，磁盘在下面高速旋转
磁盘盘面上的数据存储在一组同心圆中，称为磁道。每个磁道与磁头一样宽，一个盘面上有上千个磁道
磁道又划分为几百个扇区，每个扇区固定存储大小，一个扇区称为一个盘块
相邻磁道及相邻扇区间通过一定的间隙分隔开，以避免精度错误
由于扇区按固定圆心角划分，所以密度从外道向内道递增，磁盘的存储能力受限于最内道的最大记录密度
磁盘安装在一个磁盘驱动器中，它由磁头臂、用于旋转磁盘的主轴和用于数据输入/输出的电子设备组成。多个盘片垂直堆叠，组成磁盘组，每个盘面对应一个磁头，所有磁头固定在一起，与磁盘中心的距离相同且一起移动。所有盘片上相对位置相同的磁道组成柱面
扇区就是磁盘可寻址的最小存储单位，磁盘地址用“柱面号 ● 盘面号 ● 扇区号（或块号）”表示
磁盘按不同方式可以分为若干类型：
- 磁头相对于盘片的径向方向固定的称为固定头磁盘，每个磁道一个磁头
- 磁头可移动的称为活动头磁盘，磁头臂可以来回伸缩定位磁道
- 磁盘永久固定在磁盘驱动器内的称为固定盘磁盘
- 可移动和替换的称为可换盘磁盘
3.2磁盘调度算法
一次磁盘读写操作的时间由寻找（寻道）时间、延迟时间和传输时间决定：
①寻找时间Ts
活动头磁盘在读写信息前，将磁头移动到指定磁道所需要的时间
这个时间除跨越 n条磁道的时间外，还包括启动磁臂的时间 s，即：Ts = m * n + s
m为与磁盘驱动器速度有关的常数，约为0.2ms，磁臂的启动时间约为2ms
②延迟时间Tr
磁头定位到某一磁道的扇区（块号）所需要的时间
设磁盘的旋转速度为r，则：Tr = 1 / 2r
对于硬盘，典型的旋转速度为5400r/m，相当于一周11.1m，则Tr为5.55ms；对于软盘，其旋转速度在300600r/m之间，则Tr为50100ms
③传输时间Tt
从磁盘读出或向磁盘写入数据所经历的时间
这个时间取决于每次所读/写的字节数b和磁盘的旋转速度：Tt = b / r * N
r为磁盘每秒钟的转数，N为一个磁道上的字节数
在磁盘存取时间的计算中，寻道时间与磁盘调度算法相关，而延迟时间和传输时间与磁盘旋转速度线性相关，所以在硬件上，转速是磁盘性能的一个非常重要的参数
1、先来先服务（FCFS）算法
FCFS算法根据进程请求访问磁盘的先后顺序进行调度处理
优点：
-
具有公平性
-
如果只有少量进程需要访问，且大部分请求都是访问簇聚的文件扇区，则会达到较好的性能
缺点：如果有大量进程竞争使用磁盘，那么该算法在性能上往往低于随即调度
2、最短寻找时间优先（SSTF）算法
SSTF选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道
优点：每次的寻找时间最短。当然总是选择最小寻找时间并不能保证平均寻找时间最小，但是能提供比FCFS算法更好的性能
缺点：会产生饥饿现象
3、扫描（SCAN）算法
又称电梯调度算法
SCAN算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象
SCAN算法对最扫描过的区域不公平，在访问局部性方面不如 FCFS算法和 SSTF算法好
4、循环扫描（C-SCAN）算法
在扫面算法的基础上规定磁头单向移动来提供服务，回返时直接快速移动至起始端而不服务任何请求
SCAN算法偏向于处理接近最里或最外层磁道的访问请求，所以使用C-SCAN算法来避免这个问题
采用 SCAN算法和 C-SCAN算法时磁头总是严格地遵循从盘面的一端到另一端，显然在实际使用时还可以改进，即磁头移动只需要到达最远端的一个请求即可返回，不需要到达磁盘端点
这种形式的 SCAN算法和 C-SCAN算法成为 LOOK和 C-LOOK调度。这是因为它们在朝一个给定方向移动前会查看是否有请求
3.3磁盘的管理
1、磁盘初始化
一个新的磁盘只是一个含有磁性记录材料的空白盘
在磁盘能存储数据之前，它必须分成扇区以便磁盘控制器能进行读和写操作，这个过程称为低级初始化（物理分区）
低级初始化为磁盘的每个扇区采用特别的数据结构。每个扇区的数据结构通常由头、数据区域和尾部组成，头部和尾部包含一个初始化为空的目录
2、引导块
计算机启动时需要运行一个初始化程序（自举程序），它初始化 CPU、寄存器、设备控制器和内存等，接着启动操作系统。为此，该自举程序应找到磁盘上的操作系统内核，装入内存，并转到起始地址，从而开始操作系统的运行
自举程序通常保存在 ROM中，为了避免改变自举程序需要改变 ROM硬件的问题，只在 ROM中保留很小的自举装入程序，将完整功能的自举程序保存在磁盘的启动块上。启动块位于磁盘的固定位，拥有启动分区的磁盘称为自动磁盘或者系统磁盘
3、坏块
由于磁盘有移动部件且容错能力弱，所以容易导致一个或多个扇区损坏。部分磁盘甚至从出厂时就有坏扇区
根据所使用的磁盘和控制器，对这些块有多种处理方式：
-
对于简单磁盘，如电子集成驱动器，坏扇区可手工处理，如 MS-DOS的 Format命令执行逻辑格式化时便会扫描磁盘以检查坏扇区，坏扇区在 FAT表会标明，因此程序不会使用
-
对于复杂磁盘，如小型计算机系统接口，其控制器维护一个磁盘坏块链表，该链表在出厂前进行低级格式化时就初始化，并在磁盘的整个使用过程中不断更新。低级格式化将一些块保留作为备用，对操作系统透明。控制器可以用块来逻辑地替代坏块，这种方案称为扇区备用
对坏块的处实质上就是用某种机制使系统不去使用坏块。坏块属于硬件故障，操作系统无法修复坏块
