一.文件与文件系统

1.文件的基本概念

文件是对磁盘的抽象。 所谓文件是指一组带标识(标识即为文件名) 的、在逻辑上有完整意义的信息项的序列。

信息项：构成文件内容的基本单位(单个字节，或多个字节)，各信息项之间具有顺序关系

文件内容的意义:由文件建立者和使用者解释

要去读文件去写文件，需要定位读写指针，因此对于这样一个信息项的序列会有一个读写指针指到某一个具体的信息项。

2.设计文件系统分析

(1).从操作系统角度

怎样组织、管理文件?

文件的描述、分类
文件目录的实现
存储空间的管理
文件的物理地址
磁盘实际运作方式(与设备管理的接口)
文件系统性能
等等

(2).从用户角度

文件系统如何呈现在用户面前:

一个文件的组织
如何命名?
如何保护文件?
可以实施的操作?
等等

3.文件系统

(1).基本概念

操作系统中统一管理信息资源的一种软件，管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。

(2).需要完成的任务

统一管理磁盘空间，实施磁盘空间的分配与回收
实现文件的按名存取
- 名字空间 ——> 磁盘空间
实现文件信息的共享，并提供文件的保护、保密手段
向用户提供一个方便使用、易于维护的接口，并向用户提供有关统计信息
提高文件系统的性能
提供与I/O系统的统一接口

4.文件的分类

按文件性质和用途分类(UNIX)：普通文件；目录文件；特殊文件(设备文件)；管道文件；套接字

普通文件(regular)

包含了用户的信息，一般为ASCII或二进制文件

目录文件(directory)

管理文件系统的系统文件

特殊文件(special file)

字符设备文件：和输入输出有关，用于模仿串行I/O设备，例如终端，打印机，网卡等

块设备文件：磁盘

5.文章的逻辑结构

(1).基本概念

从用户角度看文件，由用户的访问方式确定

a以一个字节为单位,把文件看成是一个字节的序列。这是非常典型一个流式结构文件
b以记录为单位，一个记录由若干个字节组成，因此文件信息项的单位就是记录
c把文件组织成树形结构

还可以组织成堆、顺序、索引、索引顺序、散列等结构

(2).典型的文件逻辑结构与文件存取

文件逻辑结构

流式文件：构成文件的基本单位是字符

文件是有逻辑意义、无结构的一串字符的集合

记录式文件：文件由若干个记录组成，可以按记录进行读、写、查找等操作

每条记录有其内部结构

文件存取

顺序存取(访问)
随机存取(访问)
- 提供读写位置(当前位置)
- 例如:UNIX的seek操作

二.文件的存储介质

1.基本概念

典型的存储介质：磁盘(包括固态盘SSD)、磁带、光盘、U盘、……

文件的信息保存在这些存储介质上，通常是以一个独立单位来进行信息的存储传输和分配。而这个独立单位就是物理块。

物理块(块block、簇cluster)

信息存储、传输、分配的独立单位
存储设备划分为大小相等的物理块，统一编号

2.典型的磁盘结构

一块盘若干个盘片组成，每个盘片上有两个盘面
每一个盘面的信息读取都需要一个读写磁头，若干个读写磁头固定在了一个磁臂上。由磁臂带动的这些磁头沿着半径的方向进行移动。
在盘面上有若干个同心圆，称之为磁道。在磁道上存放信息。
把磁道划分成很多段，每一段称之为扇区。信息实际上是存放在每一个扇区里

任何时刻只有一个磁头处于活动状态：输入输出数据流以位串形式出现

物理地址形式: 磁头号(盘面号)、磁道号(柱面号)、扇区号

扇区：标题(10字节)、数据(512字节)、ECC纠错信息(12-16字节)

通常所说的一个扇区是 512 字节，其实是说存放的信息或者存放的数据是 512 字节，其实还有其他信息

3.磁盘访问

一次访盘请求所需要给出的参数:

读/写操作
磁盘地址(设备号，柱面号，磁头号，扇区号)
内存地址(源/目)

完成一次访盘请求的过程由三个动作组成：

寻道(时间)：磁头移动定位到指定磁道
旋转延迟(时间)：等待指定扇区从磁头下旋转经过
数据传输(时间)：数据在磁盘与内存之间的实际传输

三.磁盘空间管理

1.有关数据结构

(1).位图法

用一串二进制位反映磁盘空间中分配使用情况，每个物理块对应一位，分配物理块为0，否则为1
申请物理块时，可以在位示图中查找为1的位，返回对应物理块号
归还时，将对应位转置1

(2).空闲块表

将所有空闲块记录在一个表中，即空闲块表
主要两项内容：起始块号，块数

(3).空闲块链表

把所有空闲块链成一个链
扩展:成组链接法

2.磁盘地址与块号的转换

位图计算公式：

已知字号i、位号j ：$块号 = i × 字长 + j$

已知块号：$字号 = [ 块号 / 字长 ] 位号 = 块号\quad mod\quad 字长$

3.成组链接法设计思想

在专用块里有若干个字段，第一个字段存放了第一组的空闲块的块数，所以空闲块块数现在是二十。接着的各个字段就把二十个空闲块的块号记录在了每一个字段里头。一个文件想获取一个新的空闲块就从专用块来挑选空闲块，挑选时是从下往上挑选。如果先分配的话，一定是801这一块，然后接着分配802这一块，最后才分配820这一块。

(1).成组链接法—分配算法

查L单元(空闲块数):

当空闲块数>1 ，i=L+空闲块数;
- 从 i 单元得到一个空闲块号;
- 把该块分配给申请者;
- 空闲块数减1;
当空闲块数=1 取出L+1单元内容(一组的第一块块号或0);
- 其值=0 无空闲块，申请者等待
- 其值不等于零，把该块内容复制到专用块;
- 该块分配给申请者;

把专用块内容读到内存L开始的区域

(2).成组链接法—回收算法

归还一块:

查L单元的空闲块数;

当空闲块数<100 空闲块数加1;
- j:= L+空闲块数;
- 归还块号填入j单元。
当空闲块数=100，则把内存中登记的信息写入归还块中;
- 把归还块号填入L+1单元;
- 将L单元置成1。

四.文件控制块及文件目录

操作系统为了管理文件会把文件的各种属性都记录下来。因此这些属性是操作系统管理文件所需要的信息，按照之前对进程的设计，把文件属性所存放的这些信息称为文件控制块。

1.文件属性

(1).文件控制块(File Control Block)

为管理文件而设置的数据结构，保存管理文件所需的所有有关信息。(有时称为文件属性或元数据)

(2).常用属性

文件名，文件号，文件大小，文件地址，创建时间，最后修改时间，最后访问时间，保护，口令，创建者，当前拥有者，文件类型，共享计数，各种标志(只读、隐藏、系统、归档、ASCII/二进制、顺序/随机访问、临时文件、锁)

(1).文件目录

文件目录是操作系统中统一管理每个文件的元数据，以支持文件名到文件物理地址的转换。
将所有文件的管理信息组织在一起，即构成文件目录

(2).目录文件

将文件目录将所有文件的管理信息组织在一起后，以文件的形式存放在磁盘上，这个文件的内容是文件目录。

(3).目录项

构成文件目录的基本单元
目录项可以是FCB，目录是文件控制块的有序集合

3.文件目录结构的演化

4.与目录相关的概念

(1).一些基本概念

路径名(文件名)
- 绝对路径名：从根目录开始
- 相对路径名：从当前目录开始
当前目录/工作目录
- 当前进程正在使用的目录。
目录操作
- 创建目录、删除目录
- 读目录、写目录、改名、复制

(2).目录文件的关联

这是一个根目录文件，目录文件是由若干目录项组成的，可以看到这里有ABC 三个目录项，通过这个目录项，找到目录项所对应的文件。

五.文件的物理结构

1.基本概念

是指文件在存储介质上的存放方式。

主要解决两个问题:

假设一个文件被划分成N块，这N块在磁盘上是怎么存放的?
存放之后，其地址(块号或簇号)在FCB中是怎样记录的?

2.顺序结构

(1).基本概念

是指文件的信息存放在若干连续的物理块中。

在FCB中如何记录文件地址?

文件第一块块号
文件的长度

给出这两个信息就能知道文件中的任意一块的地址。

(2).连续结构的优缺点

优点
- 简单
- 支持顺序存取和随机存取
- 所需的磁盘寻道次数和寻道时间最少
- 可以同时读入多个块，检索一个块也很容易
缺点
- 文件不能动态增长
  - 解决办法：预留空间:浪费或重新分配和移动
- 不利于文件插入和删除
- 外部碎片:紧缩技术

2.链接结构

(1).基本概念

一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。

在FCB中如何记录文件地址?

只需要知道第一块的地址即可。

(2).链接结构的优缺点

优点
- 提高了磁盘空间利用率，不存在外部碎片问题
- 有利于文件插入和删除
- 有利于文件动态扩充
缺点
- 存取速度慢，不适于随机存取
- 可靠性问题，如指针出错
- 更多的寻道次数和寻道时间
- 链接指针占用一定的空间

链接结构的一个变形: 文件分配表 FAT

把所有指针存放在一个文件中。

表项的值有三种：0，下一块块号，-1
某文件的起始块号从何处得到？记录在FCB中。

3.索引结构

(1).基本概念

一个文件的信息存放在若干不连续物理块中。
系统为每个文件建立一个专用数据结构—索引表，并将这些物理块的块号存放在该索引表中。
索引表就是磁盘块地址数组，其中第i个条目指向文件的第i块。

在FCB中如何记录文件地址?

索引表存放在何处?

(2).索引结构示意

索引表会放在某一个物理块中，这个物理块就是索引块。索引块中就存放着所分配给文件的物理块块号。

(3).索引结构的优缺点

优点

保持了链接结构的优点，又解决了其缺点
- 既能顺序存取，又能随机存取
- 满足了文件动态增长、插入删除的要求
- 能充分利用磁盘空间
缺点
- 较多的寻道次数和寻道时间
- 索引表本身带来了系统开销，如:内存、磁盘空间，存取时间

(4).索引表的组织方式

问题：索引表很大，需要多个物理块存放时怎么办?

解决方式：

链接方式
- 一个盘块存一个索引表，多个索引表链接起来
多级索引方式
- 将文件的索引表地址放在另一个索引表中
综合模式
- 直接索引方式与间接索引方式结合

(5).多级索引与综合模式

4.UNIX的三级索引结构

UNIX文件系统采用的是多级索引结构(综合模式)

每个文件的索引表有15个索引项，每项2个字节
前12项直接存放文件的物理块号(直接寻址)
如果文件大于12块，则利用第13项指向一个物理块，在该块中存放文件物理块的块号(一级索引表)
- 假设扇区大小为512字节，物理块等于扇区块大小，一级索引表可以存放256个物理块号
对于更大的文件还可利用第14和第15项作为二级和三级索引表

试问:采用这种结构，一个文件最大可达到 ?个物理块

六.文件系统的实现

1.概述

实现文件系统需要考虑磁盘上与内存中的内容布局。

(1).磁盘上

如何启动操作系统?
磁盘是怎样管理的?怎样获取磁盘的有关信息?
目录文件在磁盘上怎么存放?普通文件在磁盘上怎么存放?

(2).内存中

当进程使用文件时，操作系统是如何支持的? 也就是文件系统的内存数据结构。

2.相关术语

磁盘分区(partition)：把一个物理磁盘的存储空间划分为几个相互独立的部分，称为分区
文件卷(volume)：磁盘上的逻辑分区，由一个或多个物理块(簇)组成
- 一个文件卷可以是整个磁盘或部分磁盘或跨盘(RAID)
- 同一个文件卷中使用同一份管理数据进行文件分配和磁盘空闲空间管理，不同的文件卷中的管理数据是相互独立的
- 一个文件卷上：包括文件系统信息、一组文件(用户文件、目录文件)、未分配空间
- 块(Block)或 簇(Cluster) : 一个或多个(2的幂)连续的扇区，可寻址数据块
格式化(format)：在一个文件卷上建立文件系统，即建立并初始化用于文件分配和磁盘空闲空间管理的管理数据——元数据

3.磁盘上的内容

存放的内容：

引导区
- 包括了从该卷引导操作系统所需要的信息
- 每个卷(分区)一个，通常为第一个扇区
卷(分区)信息
- 包括该卷(分区)的块(簇)数、块(簇)大小、空闲块(簇)数量和指针、空闲FCB数量和指针……
目录文件(根目录文件及其他目录文件)
用户文件

4.磁盘上文件系统的布局

5.内存中所需的数据结构——以UNIX为例

系统打开文件表
- 整个系统一张
- 放在内存：用于保存已打开文件的FCB

用户打开文件表
- 每个进程一个
- 进程的PCB中记录了用户打开文件表的位置

七.文件系统实例——UNIX

1.文件目录检索

访问一个文件时，用户通常给出一个文件名，通过使用文件名把文件的内容读入内存通常具有两个步骤：

目录检索
- 用户给出文件名 → 按文件名查找到目录项/FCB
- 根据路径名检索:
  - 全路径名:从根开始 \A\B\C\File1
  - 相对路径:从当前目录开始 C\File1
文件寻址
- 根据目录项/FCB中文件物理地址等信息，计算出文件中任意记录或字符在存储介质上的地址

2.目录文件实现时的改进

(1).基本概念

问题：如何加快目录检索?
一种解决方案：
- 目录项分解法：即把FCB分成两部分
  - 符号目录顶：文件名，文件号
  - 基本目录项：除文件名外的所有字段——UNIX的I节点

(2).示意图

(3).改进后的好处

例子:

假设一个FCB 占 48 个字节，物理块大小 512 字节

符号目录项：占 8 字节(文件名6字节，文件号2字节)
基本目录项：占48–6=42字节
一个目录文件有128个目录项

分解前：占13块

分解后：符号文件占 2 块，基本文件占11块

查找一个文件的平均访盘次数:

分解前:7次
分解后:2.5次

目录文件改进后减少了访盘次数，提高了文件检索速度

3.UNIX文件系统

FCB划分成两部分：目录项+i节点
- 目录项:文件名+i节点号
- 目录文件由目录项构成
- i节点:描述文件的相关信息
UNIX每个文件由一个目录项、一个i节点和若干磁盘块构成。

八.文件系统实例——FAT

1.WINDOWS—FAT16文件系统

簇大小：1、2、4、8、16、32或64扇区
文件系统的数据记录在”引导扇区”中
文件分配表FAT的作用
- 描述簇的分配状态、标注下一簇的簇号等
FAT表项：2字节
目录项：32字节
根目录大小固定

2.FAT文件系统

(1).MBR

主引导记录通常放在0号扇区。

(2).DBR

3.引导扇区

(1).BIOS参数块

(2).扩展BIOS参数块(EBPB)

4.文件分配表FAT

可以把文件分配表看成是一个整数数组，每个整数代表磁盘分区的一个簇号
状态
- 未使用、坏簇、系统保留、被文件占用(下一簇簇号)、最后一簇(0xFFFF)
簇号从0开始编号，簇0和簇1是保留的

5.FAT16目录项

6.FAT32 文件系统

(1).基本概念

FAT32的根目录区(ROOT区)不是固定区域、固定大小，而是数据区的一部分，采用与子目录文件相同的管理方式
目录项仍占32字节，但分为各种类型(包括:“.”目录项、“..”目录项、短文件名目录项、长文件名目录项、卷标项(根目录)、已删除目录项(第一字节为0xE5)等)
支持长文件名格式
支持Unicode
不支持高级容错特性，不具有内部安全特性

(2).目录项

(3).一般长文件名的实现方式

FAT32——长文件名的目录项格式

7.Windows例子

Windows为其建立了五个目录项、四个保存长文件名、一个保存压缩文件名THEQUI~1。

九.文件操作的实现

1.操作的实现

(1).创建文件

建立系统与文件的联系，实质是建立文件的FCB。

在目录中为新文件建立一个目录项，根据提供的参数及需要填写相关内容
分配必要的存储空间

(2).打开文件

根据文件名在文件目录中检索，并将该文件的目录项读入内存，建立相应的数据结构，为后续的文件操作做好准备。

文件描述符/文件句柄

2.文件操作——建立文件

create(文件名，访问权限)。

检查参数的合法性

例如:文件名是否符合命名规则；有无重名文件;

合法→2，否则→报错、返回
申请空闲目录项，并填写相关内容;
为文件申请磁盘块
返回

3.文件操作——打开文件

打开文件是为文件读写做准备。

给出文件路径名，获得文件句柄(file handle)或文件描述符(file descriptor)，需将该文件的目录项读到内存

fd=open(文件路径名，打开方式)

根据文件路径名查目录，找到目录项 (或I节点号) ;
根据文件号查系统打开文件表，看文件是否已被打开;

是 → 共享计数加1
否则 → 将目录项 (或I节点)等信息填入系统打开文件表空表项，共享计数置为1;
根据打开方式、共享说明和用户身份检查访问合法性;
在用户打开文件表中获取一空表项，填写打开方式等，并指向系统打开文件表对应表项

返回信息:fd:文件描述符，是一个非负整数，用于以后读写文件

4.文件操作——指针定位

seek(fd, 新指针的位置)

系统为每个进程打开的每个文件维护一个读写指针，即相对于文件开头的偏移地址(读写指针指向每次文件读写的开始位置，在每次读写完成后，读写指针按照读写的数据量自动后移相应数值)

由fd查用户打开文件表，找到对应的表项;
将用户打开文件表中文件读写指针位置设为新指针的位置，供后继读写命令存取该指针处文件内容。

5.文件操作——读文件

read(文件描述符，读指针，要读的长度，内存目的地址)

根据打开文件时得到的文件描述符，找到相应的文件控制块(目录项)

确定读操作的合法性

读操作合法→2，

否则→出错处理

问题:文件尚未打开?
将文件的逻辑块号转换为物理块号
- 根据参数中的读指针、长度与文件控制块中的信息，确定块号、块数、块内位移
申请缓冲区
启动磁盘I/O操作，把磁盘块中的信息读入缓冲区，再传送到指定的内存区(多次读盘)
反复执行3、4直至读出所需数量的数据或读至文件尾

十.文件系统的管理

1.文件系统的可靠性

可靠性: 抵御和预防各种物理性破坏和人为性破坏的能力

坏块问题
备份
- 通过转储操作，形成文件或文件系统的多个副本

2.文件系统备份

全量转储:
- 定期将所有文件拷贝到后援存储器
增量转储:
- 只转储修改过的文件，即两次备份之间的修改，减少系统开销
物理转储:
- 从磁盘第0块开始，将所有磁盘块按序输出到磁带
逻辑转储:
- 从一个或几个指定目录开始，递归地转储自给定日期后所有更改的文件和目录

3.文件系统一致性

(1).问题的产生:

磁盘块 → 内存 → 写回磁盘块
若在写回之前，系统崩溃，则文件系统出现不一致

(2).解决方案

设计一个实用程序，当系统再次启动时，运行该程序，检查磁盘块和目录系统。

4.磁盘块的一致性检查

UNIX一致性检查工作过程:

两张表，每块对应一个表中的计数器，初值为0

表一:记录了每块在文件中出现的次数
表二:记录了每块在空闲块表中出现的次数

5.磁盘系统的写入策略

通写(write-through)
- 内存中的修改立即写到磁盘
- 缺点:速度性能差
  
  例: FAT文件系统
延迟写(lazy-write)
- 利用回写(write back)缓存的方法得到高速
- 可恢复性差
可恢复写(transaction log)
- 采用事务日志来实现文件系统的写入
- 既考虑安全性，又考虑速度性能

十一.文件系统的安全性

1.文件保护机制

用于提供安全性、特定的操作系统机制
对拥有权限的用户，应该让其进行相应操作，否则，应禁止
防止其他用户冒充对文件进行操作

实现：

用户身份验证
访问控制

2.文件的访问的控制

(1).主动控制:访问控制表

每个文件一个
记录用户ID和访问权限
用户可以是一组用户
文件可以是一组文件

(2).能力表(权限表)

每个用户一个
记录文件名及访问权限
用户可以是一组用户
文件可以是一组文件

3.UNIX的文件访问控制

采用文件的二级存取控制审查用户的身份、审查操作的合法性。

第一级:对访问者的识别，对用户分类:
- 文件主(owner)
- 文件主的同组用户(group)
- 其他用户(other)
第二级:对操作权限的识别，对操作分类:
- 读操作(r)
- 写操作(w)
- 执行操作(x)
- 不能执行任何操作(-)

十二.文件系统的性能

磁盘服务是速度成为系统性能的主要瓶颈之一，设计文件系统应尽可能减少磁盘访问次数。

提高文件系统性能的方法有：目录项(FCB)分解、当前目录、磁盘碎片整理；块高速缓存、磁盘调度、提前读取、合理分配磁盘空间、信息的优化分布、RAID技术… …

1.块高速缓存(BLOCK CACHE)

(1).基本概念

块高速缓存又称为文件缓存、磁盘高速缓存、缓冲区高速缓存。

基本思想是:在内存中为磁盘块设置的一个缓冲区，保存了磁盘中某些块的副本。

利用方式：

检查所有的读请求，看所需块是否在块高速缓存中
如果在，则可直接进行读操作；否则，先将数据块读入块高速缓存，再拷贝到所需的地方

引入原因：由于访问的局部性原理，当一数据块被读入块高速缓存以满足一个I/O请求时，很可能将来还会再次访问到这一数据块

(2).如何实现

块高速缓存的组织：

块高速缓存的置换(修改LRU)
- 该块是否不久后会再次使用
块高速缓存写入策略
- 该块是否会影响文件系统的一致性

2.提前读取

思路：每次访问磁盘，多读入一些磁盘块
依据：程序执行的空间局部性原理
开销：较小(只有数据传输时间)
具有针对性

3.WINDOWS的文件访问方式

不使用文件缓存
- 普通方式
- 通过Windows提供的FlushFileBuffer函数实现  使用文件缓存
预读取。
- 每次读取的块大小、缓冲区大小、置换方式
- 写回。写回时机选择、一致性问题
异步模式
- 不再等待磁盘操作的完成
- 使处理器和I/O并发工作

用户对磁盘的访问通过访问文件缓存来实现。

由Windows的CacheManager实现对缓存的控制
- 读取数据的时候预取
- 在Cache满时，根据LRU原则清除缓存的内容
- 定期更新磁盘内容使其与Cache一致(1秒)
Write-back机制
- 在用户要对磁盘写数据时，只更改Cache中的内容，由Cache Manager决定何时将更新反映到磁盘

例子

4.合理分配磁盘空间

分配磁盘块时，把有可能顺序存取的块放在一起。尽量分配在同一柱面上，从而减少磁盘臂的移动次数和距离。

5.磁盘调度

当有多个访盘请求等待时，采用一定的策略，对这些请求的服务顺序调整安排，从而降低平均磁盘服务时间，达到公平、高效。

公平：一个I/O请求在有限时间内满足

高效：减少设备机械运动带来的时间开销

一次访盘时间 = 寻道时间+旋转延迟时间+传输时间

• 减少寻道时间

• 减少延迟时间

例子：

例子:假设磁盘访问序列: 98，183，37，122，14，124，65，67

读写头起始位置:53

要求计算:

磁头服务序列
磁头移动总距离(道数)

(1).先来先服务(FCFS)

思想：按访问请求到达的先后次序服务

优点：简单，公平
缺点：效率不高，相临两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利

(2).最短寻道时间优先(Shortest Seek Time First)

思想：优先选择距当前磁头最近的访问请求进行服务主要考虑寻道优先

优点：改善了磁盘平均服务时间
缺点：造成某些访问请求长期等待得不到服务

(3).扫描算法SCAN(电梯算法)

思想：当设备无访问请求时，磁头不动;当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描;否则改变移动方向，并为经过的访问请求服务，如此反复。

(4).单向扫描调度算法C-SCAN

总是从0号柱面开始向里扫描
按柱面(磁道)位置选择访问者
移动臂到达最后一个柱面后，立即带动读写磁头快速返回到0号柱面
返回时不为任何的等待访问者服务
返回后可再次进行扫描

效果：减少了新请求的最大延迟

(5).N-step-SCAN策略

把磁盘请求队列分成长度为N的子队列，每一次用SCAN处理一个子队列
在处理某一个队列时，新请求添加到其他子队列中
如果最后剩下的请求数小于N，则它们全都将在下一次扫描时处理
N值比较大时，其性能接近SCAN；当N=1时，即FIFO

克服“磁头臂的粘性”

(6).FSCAN策略

使用两个子队列

扫描开始时，所有请求都在一个队列中，而另一个队列为空
扫描过程中，所有新到的请求都放入另一个队列中
对新请求的服务延迟到处理完所有老请求之后

(7).旋转调度算法

旋转调度:根据延迟时间来决定执行次序的调度

三种情况:

若干等待访问者请求访问同一磁头上的不同扇区
若干等待访问者请求访问不同磁头上的不同编号的扇区
若干等待访问者请求访问不同磁头上具有相同的扇区

解决方案:

对于前两种情况：总是让首先到达读写磁头位置下的扇区先进行传送操作
对于第三种情况：这些扇区同时到达读写磁头位置下，可任意选择一个读写磁头进行传送操作

例子

6.信息的优化分布

记录在磁道上的排列方式也会影响输入输出操作的时间。

例子:处理程序要求顺序处理8个记录；磁盘旋转一周为20毫秒/周;花5毫秒对记录进行处理。

7.记录的成组与分解

记录的成组：把若干个逻辑记录合成一组存放一块的工作

进行成组操作时必须使用内存缓冲区，缓冲区的长度等于逻辑记录长度乘以成组的块因子。
成组目的：提高了存储空间的利用率;减少了启动外设的次数，提高系统的工作效率。
记录的分解从一组逻辑记录中把一个逻辑记录分离出来。

8.RAID技术

(1).基本概念

RAID(独立磁盘冗余阵列) (Redundant Arrays of Independent Disks) ：多块磁盘按照一定要求构成一个独立的存储设备。

目标：提高可靠性和性能

考虑：磁盘存储系统的速度、容量、容错、数据灾难发生后的数据恢复

数据的组织方式：

通过把多个磁盘组织在一起，作为一个逻辑卷提供磁盘跨越功能
通过把数据分成多个数据块，并行写入/读出多个磁盘，以提高数据传输率(数据分条stripe)
通过镜像或校验操作，提供容错能力(冗余)

最简单的RAID组织方式:镜像

最复杂的RAID组织方式:块交错校验

(2).RAID 0 — 条带化

数据分布在阵列的所有磁盘上
有数据请求时，同时多个磁盘并行操作
充分利用总线带宽，数据吞吐率提高，驱动器负载均衡

(3).RAID 1 — 镜像

最大限度保证数据安全及可恢复性
所有数据同时存在于两块磁盘的相同位置
磁盘利用率50%

(4).RAID 4 — 交错块奇偶校验

带奇偶校验
以数据块为单位

一.文件与文件系统

1.文件的基本概念

2.设计文件系统分析

(1).从操作系统角度

(2).从用户角度

3.文件系统

(1).基本概念

(2).需要完成的任务

4.文件的分类

5.文章的逻辑结构

(1).基本概念

(2).典型的文件逻辑结构与文件存取

文件逻辑结构

文件存取

二.文件的存储介质

1.基本概念

2.典型的磁盘结构

3.磁盘访问

三.磁盘空间管理

1.有关数据结构

(1).位图法

(2).空闲块表

(3).空闲块链表

2.磁盘地址与块号的转换

3.成组链接法设计思想

(1).成组链接法—分配算法

(2).成组链接法—回收算法

四.文件控制块及文件目录

1.文件属性

(1).文件控制块(File Control Block)

(2).常用属性

2.文件目录,目录项和目录文件

(1).文件目录

(2).目录文件

(3).目录项

3.文件目录结构的演化

4.与目录相关的概念

(1).一些基本概念

(2).目录文件的关联

五.文件的物理结构

1.基本概念

2.顺序结构

(1).基本概念

(2).连续结构的优缺点

2.链接结构

(1).基本概念

(2).链接结构的优缺点

3.索引结构

(1).基本概念

(2).索引结构示意

(3).索引结构的优缺点

(4).索引表的组织方式

(5).多级索引与综合模式

4.UNIX的三级索引结构

六.文件系统的实现

1.概述

(1).磁盘上

(2).内存中

2.相关术语

3.磁盘上的内容

4.磁盘上文件系统的布局

5.内存中所需的数据结构——以UNIX为例

七.文件系统实例——UNIX

1.文件目录检索

2.目录文件实现时的改进

(1).基本概念

(2).示意图

(3).改进后的好处

3.UNIX文件系统

八.文件系统实例——FAT

1.WINDOWS—FAT16文件系统

2.FAT文件系统

(1).MBR

(2).DBR

3.引导扇区

(1).BIOS参数块

(2).扩展BIOS参数块(EBPB)

4.文件分配表FAT

5.FAT16目录项

6.FAT32 文件系统