内容大纲

• 1、文件管理;
• 2、文件系统管理
• 3、输入/输出管理
• 4、缓冲区

1 文件管理

文件

• 文件是指记录在外存上的具有文件名的一组相关信息的集合。
• 系统运行时，以进程作为基本单位，用户输入输出时，以文件为基本单位。
• 可分为有结构文件和无结构文件两种。有结构文件是由若干个相关记录组成，而无结构文件则被看成一个字符流。
  图片1.png

文件的逻辑结构

• 有结构的记录式文件
  • 文件构成：由一组相似记录(如:考生信息记录)构成。
  • 记录长度：分为定长和变长。
  • 分类（按记录的组织）：
    顺序文件（适用定长记录）
    索引文件(变长，建立一张索引表)
    直接/哈希文件（键值确定物理地址）
• 无结构的流式文件
  • 文件构成：由字符流构成。
  • 长度：字节为单位
  • 访问：读写指针,通过穷举搜索的方式访问.

顺序文件的优缺点

• 优点
  • 顺序存取速度较快（批量存取）。
  • 定长记录，还可方便实现直接存取。
• 缺点
  • 对变长记录，直接存取低效

  • 不利于文件的动态增长。

    
    定长文件顺序存放

索引文件

引入—为解决变长记录文件的顺序存取低效问题。
索引文件—为变长记录文件建立一张索引表。

image.png

索引文件的特点

• 优点
  • 通过索引表可方便地实现直接存取，具有较快的检索速度。
  • 易于进行文件的增删
• 缺点
  • 索引表的使用增加了存储开销
  • 索引表的查找策略对文件系统的效率影响很大
• 注：若索引表很大，可建多级索引

目录结构

与文件管理系统和文件集合相关联的是文件目录。包含文件的相关信息，如：属性、位置和所有权等。
对目录管理的要求如下：

• 实现“按名存取”
• 提高对目录的检索速度
• 文件共享
• 允许文件重名

文件控制块和索引结点

从文件管理角度看，文件由FCB和文件体（文件本身）两部分组成。

文件控制块（FCB）

文件控制块是操作系统为管理文件而设置的数据结构，存放了文件的有关说明信息，是文件存在的标志。
FCB中的信息：

• 基本信息类：文件名、文件长度、类型、属性文件物理位置
• 存取控制信息类：文件存取权限、用户名、口令、共享计数
• 使用信息类：文件的建立日期、最后修改日期、保存期限、最后访问日期

文件目录
把所有的FCB组织在一起，就构成了文件目录，即文件控制块的有序集合。
目录项
构成文件目录的项目（目录项就是FCB）
目录文件
为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，称为目录文件。

图片2.png

单级目录

所有的用户使用一个目录

image.png

• 优点: 简单，易实现，按名存取
• 缺点:
  • 限制了用户对文件的命名（即易重名）
  • 文件平均检索时间长(查找速度慢)，不支持分类。
  • 不便于实现文件共享
  • 只适用于单用户环境

二级目录

为每个用户创建一个单独的目录

image.png

• 优点：
  • 提高了检索目录的速度；
  • 不同用户目录中可重名；
  • 不同用户可用不同文件名来访问系统中一共享文件
• 缺点:
  • 限制了各用户对文件的共享
  • 增加了系统开销，缺乏灵活性，无法反映真实世界复杂的文件结构形式。不能支持文件分组。

树形目录

在两级目录中若允许用户建立自己的子目录，则形成3级或多级目录结构（即树型目录结构）

image.png

• 路径名
  • 访问数据文件的一条路径。绝对路径、相对路径、当前路径
• 优点
  • 层次结构清晰,实现分组,便于管理和保护；
  • 解决重名问题；
  • 查找速度加快。
• 缺点
  • 查找一个文件按路径名逐层检查,由于每个文件都放在外存,多次访盘影响速度。

文件系统管理

一盘磁带、一张光盘片、一个硬盘分区或一张软盘片都称为一卷，卷是存储介质的物理单位。一个卷可以保存一个文件或多个文件，也可以一个文件保存在多个卷上。
块是存储介质上连续信息所组成的一个区域，也叫做物理记录。块是主存储器和辅助存储设备进行信息交换的物理单位，每次总是交换一块或整数块信息。

磁盘结构

1.png
image.png

分配方法

• 连续分配
• 链接分配
• 索引分配

连续分配

每个文件在磁盘上占用一组连续的物理块。磁盘地址构成一个线性空间，文件逻辑块顺序与文件物理块顺序相同。

• 优点如下：
  • 顺序访问容易，对定长记录，可方便实现直接存取。
  • 顺序访问速度快，适合连续批量访问。
• 缺点如下：
  • 要求有连续的存储空间，不利于文件动态增长。
  • 须事先知道文件的长度，寻找适当空间较费时。
  • 对变长记录，不能很好地支持直接存取。

  • 存在“碎片”问题。

    
    2.png
    image.png

磁盘空间的连续分配

image.png

链接分配

磁盘块分配方法：

• 每个文件是一个磁盘块的链接列表：块可以分散在磁盘各处。
• 按所需分配磁盘块，链接在一起。
• 在每个块中有指向下一个块的指针
• 只需要起始地址。

可以通过合并(consolidation)将一个文件的各个簇连续存放，以提高I/O访问性能。

3.png
优点
1、无外部碎片，没有磁盘空间浪费
2、无需事先知道文件大小。文件动态增长时，可动态分配空闲块。对文件的增、删、改十分方便。
*3、不需紧缩磁盘空间。
缺点
1、不能支持高效随机/直接访问，仅对顺序存取特有效
2、需为指针分配空间。---块/簇 （隐式链接）
3、可靠性较低（指针丢失/损害）

链接表FAT，每项保存下一块链接地址，整个磁盘仅设置一张。

图片3.png

索引分配

单级索引分配

链接分配方式虽然解决了连续分配方式所存在的问题， 但又出现了另外两个问题， 即：

• 不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在FAT中顺序地查找许多盘块号。
• FAT需占用较大的内存空间。

为每一个文件分配一个索引块（表），再把分配给该文件的所有块号，都记录在该索引块中。故索引块就是一个含有许多块号地址的数组。

• 该索引块的地址由该文件的目录项指出。
• 支持随机/直接存取。
• 不会产生外部碎片。
• 适用于较大的文件。

优点:

• 不要求物理块连续,便于直接存取,便于文件 的增、删、改。

缺点:

• 增加了索引表的空间开销和查找时间。

索引顺序文件

• 索引顺序文件是与索引文件结构类似，不同之处在于索引表不是为每个记录建立一个表项，而是为一组记录建立一个表项。

  
  image.png
  图片4.png

• 在UNIX系统中,还采用了混合索引分配方式,可以同时采用一级、二级、三级索引分配结构,以满足不同大小文件的需要。

• 每个文件的索引表为13个索引项,每项4个字节,登记一个存放文件信息的物理块号。最前面10项直接登记存放文件信息的物理块号,叫直接寻址。

• 如果文件大于10块,则利用第11项指向一个物理块,该块中最多可放256个文件物理块的块号,叫做一次间接寻址。对于更大的文件还可利用第12和第13项作为二次和三次间接寻址。

• UNIX中采用了三级索引结构后，文件最大可达16兆个物理块。

混合索引：UNIX（每块4KB）

image.png
练习题
UNIX中有10个直接块，1个一级间接块， 1个二级间接块， 1个三级间接块，每个块的大小4KB，UNIX系统中地址所占空间为4B。若以下问题都建立在该索引结点已经在内存中的前提下：
1.文件的大小为多大时可以只用直接块？
2.该索引结点能访问的地址空间总共多大？
3.若要读取一个文件的第10000B的内容，需要访问磁盘多少次？
4.若要访问一个文件的第10MB的内容，需访问磁盘多少次？ image.png
image.png

3 输入/输出管理

• I/O 设备种类繁多，功能和速度差异巨大，机电特性各不相同。
• 系统提供I/O指令，控制设备实现I/O操作。
• 设备管理的功能
  （1）监视系统中所有设备的状态。
  （2）设备分配。
  （3）设备控制是设备管理的另一功能，它包括设备驱动和设备中断处理，具体的工作过程是在设备处理的程序中发出驱动某设备工作的I/O指令后，再执行相应的中断处理。

数据传送控制方式

• 程序直接控制方式（轮询）
• 中断控制方式
• DMA方式
• 通道控制方式

程序直接控制方式-轮询（Polling）

程序直接控制方式是指由程序直接控制内存或CPU和外围设备之间进行信息传送的方式。通常又称为“忙—等”方式或循环测试方式。
（1）把一个启动位为“1”的控制字写入该设备的控制状态寄存器。
（2）将需输出数据送到数据缓冲寄存器。
（3）测试控制状态寄存中的“完成位”，若为0，转（2），否则转（4）。
（4）输出设备将数据缓冲寄存器中的数据取走进行实际的输出。

中断控制方式

（1）进程需要数据时，将允许启动和允许中断的控制字写入设备控制状态寄存器中，启动该设备进行输入操作。
（2）该进程放弃处理机，等待输入的完成。操作系统进程调度程序调度其他就绪进程占用处理机。
（3）当输入完成时，输入设备通过中断请求线向CPU发出中断请求信号。CPU在接收到中断信号之后，转向中断处理程序。
（4）中断处理程序首先保护现场，然后把输入缓冲寄存器中的数据传送到某一特定单元中去，同时将等待输入完成的那个进程唤醒，进入就绪状态，最后恢复现场，并返回到被中断的进程继续执行。
（5）在以后的某一时刻，操作系统进程调度程序选中提出的请求并得到获取数据的进程，该进程从约定的内存特定单元中取出数据继续工作。

图片1.png

DMA方式

DMA方式又称直接内存访问（Direct Memory Access）方式。其基本思想是在外设和主存之间开辟直接的数据交换通路。DMA采用总线周期挪用实现I/O。

DMA方式的特点是：

• 数据传送的基本单位是数据块。
• 所传送的数据是从设备送内存，或者相反。
• 仅在传送一个或多个数据块的开始和结束时，才需中断CPU，请求干预，整块数据的传送是在DMA控制器控制下完成的。

DMA控制器的组成

图片2.png

DMA方式的工作流程

图片3.png

4 缓冲区

缓冲（Buffering） - 在设备之间传送数据时，（暂时）保存数据。

• 协调数据到达速度与数据离去速度不匹配的问题。
• 协调数据大小不一致的问题。
• 确保数据的 “复制语义”。
• 减少对CPU的中断次数
• 提高CPU和I/O设备之间的并行性

单缓冲

单缓冲是操作系统提供的最简单的一种缓冲形式。每当一个进程发出一个I/O请求时，操作系统便在主存中为之分配一个缓冲区，该缓冲区用来临时存放输入/输出数据。
设备先把数据写入缓冲区，然后用户进程从缓冲区读走数据。

image.png

双缓冲

• 在双缓冲方案中，设置两个缓冲区1和2，直到缓冲区1满才输入到缓冲区2，此时操作系统可以从缓冲区1读取数据放入用户进程。

• 双缓冲方式和单缓冲方式相比，双缓冲方式能进一步提高CPU和外设的并行程度。但是在实际系统中很少采用这一方式，这是因为在计算机系统中的外设很多，又有大量的输入和输出，同时双缓冲很难匹配设备和CPU的处理速度。因此现代计算机系统中一般使用环形缓冲或缓冲池结构。

  
  image.png

环形缓冲

• 环形缓冲包含了多个大小相等的缓冲区。在主存中分配一组大小相等的存储区作为缓冲区，并将这些缓冲区链接起来，每个缓冲区中有一个指向下一个缓冲的指针，最后一个缓冲区的指针指向第一个缓冲区，这样n个- 缓冲区就成了一个环形。环形缓冲区结构如图所示。

• 需要两个指针in和out。in指向可以输入数据的第一个空缓冲区，out指向可以提取数据的第一个满缓冲区。

  
  image.png

缓冲池

从自由主存中分配一组缓冲区即可构成缓冲池。

缓冲池的组成

• 缓冲池中的缓冲区可以形成3个队列：空闲缓冲区、装输入数据的缓冲区和装输出数据的缓冲区。
• 缓冲池中还有4种工作缓冲区，收容输入数据的工作缓冲区hin，提取输入数据的工作缓冲区sin，收容输出数据的工作缓冲区sout，提取输出数据的工作缓冲区hout。

缓冲池的工作方式

缓冲区可以在收容输入、提取输入、收容输出和提取输出四种方式下工作。

image.png

• 收容输入：从空白缓冲区队列中取出一个缓冲号为number的空白缓冲区，将其作为收容输入缓冲区hin，当hin中装满了由输入设备输入的数据之后，将该缓冲区插入到装满输入数据的输入缓冲队列 in中。
• 收容输出：从空白缓冲区队列中取出一个空白缓冲区number作为收容输出缓冲区hout，待hout中装满输出数据之后，将该缓冲区插入装满输出数据的输出缓冲队列 out中。
• 提取输入：从装满输入数据的输入缓冲队列 in中取出一个装满输入数据的缓冲区number作为输入缓冲区sin，当CPU从中提取完所需数据之后，将该缓冲区释放并插入空白缓冲队列emq中。
• 提取输出：从装满输出数据的输出缓冲队列 out中取出装满输出数据的缓冲区number，将其作为sout。当sout中数据输出完毕时，系统将该缓冲区插入空白缓冲队列emq中。

缓冲池中的3种缓冲队列

1.png

F指向队首，L指向队尾。（emq指空缓冲区队列，inq装满输入数据的输入缓冲队列 ，out装满输出数据的输出缓冲队列 ）