操作系统-六-八章

• 前言：
• 系列博文
• 第六章 文件管理
• • 1. 文件的定义
  • 2. 文件的分类
  • 3. 文件逻辑结构分类
  • 4. 文件物理结构分类
  • 5. 外存储设备
  • 6. 磁盘计算
  • 7. 文件存取方式
  • 8. 文件目录
  • 9. 文件目录块（FCB）
  • 10. 目录文件
  • 11. 目录结构
  • 12. 全路径名&相对路径
  • 13. 目录项分解法
  • 14. 存储空间分配与回收
  • 15. 回收和分配算法
  • 16. 记录的成组
  • 17. 建立文件
  • 18. 打开文件
  • 19. 读文件
  • 20. 写文件
  • 21. 关闭文件
  • 22. 删除文件
  • 23. 指针定位
  • 24. 文件的保护
  • 25. 存取控制矩阵
  • 26. 二级存取控制
  • 27. UNIX 系统内部数值
  • 28. 提高文件系统性能的方法
  • 29. 磁盘调度算法
  • 30. 先来先服务调度算法（ FCFS)
  • 31. 最短寻道时间优先调度算法（ SSTF)
  • 32. 扫描算法（ SCAN)
  • 33. 文件分配表（FAT）
  • 34. 文件系统执行 close（）
• 第七章 I/O 设备管理
• • 1. 设备管理
  • 2. 设备管理的主要任务
  • 3. 设备的分类
  • 4. I/O 设备的控制方式
  • 5. 程序直接控制方式（PIO(Programmed I/O，程控 I/O)方式）
  • 6. 程序直接控制的关键部件
  • 7. 中断控制方式
  • 8. 中断控制方式的处理过程
  • 9. DMA（直接内存访问)方式
  • 10. DMA 控制的关键部件
  • 11. 通道控制方式
  • 12. 通道的功能
  • 13. I/O 系统硬件结构
  • 14. I/O 软件分层
  • 15. 与设备无关 I/O 软件功能
  • 16. 典型的 I/O 技术
  • 17. 缓冲技术
  • 18. 设备分配技术
  • 19. 虚拟设备
  • 20. SPOOLing 技术
  • 21. 提高 I/O 性能的技术
  • 22. 设备表作用
  • 23. 设备独立层
  • 24. “准备就绪”信号
  • 25. 外部设备命令传递
  • 26. 高速缓存
  • 27. 键盘的 I/O 控制
• 第八章 死锁
• • 1. 死锁、饥饿和活锁
  • 2. 死锁产生的原因
  • 3. 产生死锁的四个条件
  • 4. 死锁检测
  • 5. 死锁预防
  • 6. 死锁避免
  • 7. 安全与不安全状态
  • 8. 银行家算法
  • 9. 死锁解除法
  • 10. 资源分配图化简方法
  • 11. 独占设备预防死锁

前言：

作者在CSDN博客上开通了[网络工程师]专栏，目的在于激励自己坚持学习。由于是初次进行博客创作、经验不足、可能比较粗糙，如有错漏之处希望大家能够指正、也欢迎大家一起交流学习。

如需查看完整学习博文（笔记）请点击 [网络工程师] 进行查看

系列博文

1、四级网络工程师和四级信息安全工程师考试须知与学习方法

2、四级网络工程师笔记-操作系统（上）

3、四级网络工程师笔记-操作系统（中）

4、四级网络工程师笔记-操作系统（下）

5、四级网络工程师笔记-计算机网络（上）

6、四级网络工程师笔记-计算机网络（中）

7、四级网络工程师笔记-计算机网络（下）

第六章 文件管理

1. 文件的定义

⚫ 文件可以被解释为一组带标识的、在逻辑上有完整意义的信息项的序列。

⚫ 这个标识为文件名，信息项构成了文件内容的基本单位。

⚫ 信息项是构成文件内容的基本单位，这些信息项是一组有序序列，它们之间具有一定的顺序关系；

⚫ 文件提供了一种将数据保存在外部存储介质上以便于访问的功能。为了方便用户使用，每个文件都有特定的名称。

⚫ 文件名称的长度因系统而异。

⚫ 有的文件系统不区分文件名的大小写，而有的则加以区分。

⚫ 有的操作系统对不同的后缀有特定的解释，而有的则没有统一的规定。

⚫ 一般地，文件建立在存储器空间里，以便使文件能够长期保存。即：文件一旦建立，就一直存在，直到该文件被删除或该文件超过事先规定的保存期限。

2. 文件的分类

1) 按文件的用途分类

① 系统文件

② 库函数文件

③ 用户文件

2) 按文件的组织形式分类

① 普通文件

② 目录文件

③ 特殊文件

3) 一些常见的文件分类方式

⚫ 按文件的保护方式可划分为：只读文件、读写文件、可执行文件、无保护文件等。

⚫ 按信息的流向分类可划分为：输入文件、输出文件和输入输出文件等。

⚫ 按文件的存放时限可划分为：临时文件、永久文件和档案文件等。临时文件，即记有临时性信息的文件;永 久性文件，即其信息需要长期保存的文件；档案文件，即保存在作为“档案”用的磁带或光盘等永久性介质上以备查证和恢复时使用的文件。

⚫ 按文件所使用的介质类型分类可划分为：磁盘文件、磁带文件、卡片文件和打印文件等。

⚫ 还可以按文件的组织结构分类。比如，由用户组织的文件称逻辑文件，逻辑文件可采用流式文件和记录式文件两种组织方式。而文件在存储介质上的组织方式是文件的物理结构（物理文件），常用的组织方式有顺序文件、链接文件和索引文件等。

4) UNIX 类操作系统中文件的分类

⚫ 在 UNIX 类操作系统中，文件系统包括 3 种类型的文件：

① 普通文件。这是内部无结构的一串平滑的字符所组成的文件。

② 目录文件。这是由文件目录项所构成的文件。

③ 特殊文件。在 UNIX 类操作系统中， 把 I/O 设备也看成是一种文件——特殊文件。

⚫ 文件系统分类的目的是:对不同文件进行管理，提高系统效率；同时，提高文件系统的用户界面友好性。

3. 文件逻辑结构分类

可以把文件划分成 3 类逻辑结构:无结构的字符流式文件、定长记录文件和不定长记录文件构成的记录树，定长记录文件和不定长记录文件可以统称为记录式文件。

1) 流式文件

⚫ 流式文件是有序字符的集合，其长度为该文件所包含的字符个数，所以又称为字符流文件。

⚫ 在流式文件中，构成文件的基本单位是字符。

⚫ 可以认为流式文件就是一串有开头和结尾的连续字符；

⚫ 流式文件无结构。所以用户对流式文件可以方便地进行操作。

⚫ 源程序、目标代码等文件属于流式文件。UNIX 类系统采用的是流式文件结构。

2) 记录式文件

⚫ 记录式文件是一组有序记录的集合。在记录式文件中，构成文件的基本单位是记录。

⚫ 记录是一个具有特定意义的信息单位，它由该记录在文件中的逻辑地址（相对位置）与记录名所对应的一组键、属性及其属性值所组成，可按键进行查找。

⚫ 记录式文件可分为定长记录文件和不定长记录文件两种。

⚫ 在定长记录文件中，各个记录长度相等。在检索时，可以根据记录号 i 及记录长度 L 就可以确定该记录的逻辑地址。

⚫ 在不定长记录文件中，各个记录的长度不等，在查找时，必须从第一个记录起一个记录一个记录查找，直到找到所需的记录。

⚫ 记录式的有结构文件可把文件中的记录按各种不同的方式排列，构成不同的逻辑结构，以便用户对文件中的记录进行修改、追加、查找和管理等操作。

4. 文件物理结构分类

常用的文件物理结构有顺序结构、链接结构、索引结构和 I 节点结构。

1) 顺序结构（连续分配）

⚫ 顺序结构又称连续结构，它把逻辑上连续的文件信息依次存放在连续编号的物理块中。这是一种逻辑记录顺序核物理记录顺序完全一致的文件。

⚫ 在顺序结构中，一个文件的目录项中只要指出该文件占据的总块数和起始块号即可。

⚫ 优点：

① 由于从文件的逻辑块号到物理块号的变换，知道了文件在文件存储设备上的起始块号和文件长度，就能很快进行存取。

② 且顺序结构支持顺序存取和随机存取。

⚫ 对于顺序存取，顺序结构的存取速度快。

⚫ 缺点：

① 文件不能动态增长。对于顺序结构的文件，不利于文件插入和删除。

② 随着文件不停地被分配和被删除，空闲空间逐渐被分割为很小的部分，最终导致出现存储碎片， 虽然空间满足，但由于不连续且都是小碎片而无法分配。

2) 链接结构（不连续分配）

⚫ 链接结构的实质就是为每个文件构造所使用磁盘块的链表。

⚫ 使用这种链接结构的文件，将逻辑上连续的文件分散存放在若干不连续的物理块中。

⚫ Windows 的 FAT 文件系统采用的是链接结构，但将所有链指针集中存放。

⚫ 优点：

① 解决存储碎片问题，有利于文件动态扩充；

② 有利于文件插入和删除，提高了磁盘空间利用率。

③ 方便链接结构的文件动态扩充。

⚫ 缺点： 存取速度慢，不适于随机存取文件;

① 磁盘的磁头移动多，效率相对较低;

② 存在文件的可靠性问题，比如指针出错，文件也就出错了；

③ 链接指针需要占用一定的空间。

⚫ 链接结构的文件所使用的物理块是不连续分配的，所以一个链接结构的文件的所有物理块在磁盘上是分散分布的。

⚫ 与顺序结构的文件相比，在访问一个链接结构的文件时需要更多的寻道次数和寻道时间。

3) 索引结构

⚫ 索引结构的文件把每个物理盘块的指针字集中存放在被称为索引表的数据结构中的内存索引表中。

⚫ 优点：

① 索引文件结构保持了链接结构的优点，又解决了其缺点。

② 索引结构文件既适于顺序存取，也适于随机存取。

③ 可以将有关逻辑块号和物理块号的信息全部保存在了一个集中的索引表中。

④ 索引文件可以满足文件动态增长的要求，也满足了文件插入、删除的要求；

⑤ 索引文件还能充分利用外存空间。

⚫ 缺点：

① 会引起较多的寻道次数和寻道时间；

② 索引表本身增加了存储空间的开销。

4) 索引结构的实例—— I 节点

⚫ I 节点是一种多级索引文件结构。

⚫ I 节点最早出现在 UNIX 操作系统中，是多级索引结构文件在 UNIX 中的具体实现。

⚫ 掌握了 I 节点也就掌握了多级索引文件结构的工作原理。

⚫ I 节点的基本思想是，给每个文件赋予一张称为 I 节点的小表， 在这张小表中列出了文件属性和文件中各块在磁盘上的地址

⚫ I 节点的文件结构，既适合小文件使用，也可供大型文件使用，灵活性比较强。这种文件结构占用的系统空间比一般多级索引结构的文件要少。

5. 外存储设备

l 外存储设备通常由驱动部分和存储介质两部分组成。

l 外存储设备存取的过程方式因各种具体存储设备而异，不过也有一定共性。

l 外存储设备存取的过程大致如下：读状态-置数据-置地址-置控制-再读状态。

6. 磁盘计算

⚫ 在随机存取设备中，磁盘是一种典型的随机存取设备。

⚫ 磁盘设备允许文件系统直接存取磁盘上的任意物理块。

⚫ 磁盘一般由若干磁盘片组成，每个磁盘片对应两个读/写磁头，分别对磁盘片的上下两面进行读写。

⚫ 磁盘上每个物理块的位置可用柱面号（ 磁道号）、磁头号和扇区号表示， 这些地址与物理块号一一对应。其计算公式如下：

① 已知物理块号，则磁盘地址：

柱面号=[物理块号/(磁头数 ×扇区数）]

磁头号=[(物理块号 mod(磁头数× 扇区数））/扇区数]扇区号=(物理块号 mod(磁头数× 扇区数）)mod 扇区数

② 已知磁盘地址：

物理块号=柱面号 ×(磁头数 × 扇区数)+磁头号 × 扇区数+扇区号

l 磁头臂是沿半径方向移动的。

l 访问磁盘时，首先要移动磁头臂到相应柱面（磁道）上，然后旋转盘片将指定磁头定位在指定扇区上，最后控制磁头对扇区中的数据进行读写。

⚫ 一次访盘时间由寻道时间、旋转定位时间和数据传输时间组成；

⚫ 寻道时间由于是机械动作，因而所花费的时间最长， 传输时间花费时间最短。

7. 文件存取方式

⚫ 在用户面前，文件呈现的是文件的逻辑结构，这与用户使用文件的方式相适应；

⚫ 在存储介质面前，文件呈现的是文件的物理结构，这与文件所使用存储介质的特性有关；

⚫ 文件的存取方式是文件的逻辑结构和物理结构之间的映射或变换机制；

⚫ 文件常用的存取方法有:顺序存取和随机存取两种方式。

① 顺序存取： 按从前到后的次序依次访问文件的各个信息项。

② 随机存取： 又称直接存取， 即允许用户按任意的次序直接存取文件中的任意一个记录， 或者根据存取命令把读写指针移到文件中的指定记录处读写。

⚫ UNIX 类操作系统的文件系统采用了顺序存取和随机存取两种方法。

8. 文件目录

⚫ 在一个计算机系统中保存有许多文件，用户在创建和使用文件时只给出文件的名字，由文件系统根据文件名找到指定文件。

⚫ 为了便于对文件进行管理，设置了文件目录，用于检索系统中的所有文件。

⚫ 文件系统的一个特点是“按名存取”，即用户只要给出文件的符号名就能方便地存取在外存空间的该文件的信息，而不必了解和处理文件的具体物理地址。

9. 文件目录块（FCB）

⚫ 文件控制块 FCB 是系统为管理文件而设置的一个描述性数据结构。FCB 是文件存在的标志，它记录了系统管理文件所需要的全部信息。

⚫ FCB 通常应包括以下内容： 文件名、文件号、用户名、文件地址、文件长度、文件类型、文件属性、共享计数、文件的建立日期、保存期限、最后修改日期、最后访问日期、口令、文件逻辑结构、文件物理结构，等等，

⚫ 其中文件名、文件大小、文件创建时间和磁盘起始地址是文件控制块中必须保存的信息。

⚫ 在文件控制块中的信息可以分成文件存取控制信息、文件结构信息和文件管理信息。

10. 目录文件

⚫ 多个文件的文件控制块集中在一起组成了文件的目录。

⚫ 通常，文件目录以文件的形式保存起来，这个文件就被称为目录文件。目录文件是长度固定的记录式文件。

⚫ 在目录文件中，每个文件的文件控制块又称为目录文件中的目录项。

⚫ 有时，为了节省内存的空间，就把目录文件保存在外存储器上，在需要时才把目录文件调入内存。

11. 目录结构

1) 一级目录结构

⚫ 在系统中设置一张线性目录表，表中包括了所有文件的文件控制块，每个文件控制块指向一个普通文件，这就是一级目录结构；

⚫ 一级目录结构是一种最简单、最原始的文件目录结构。

⚫ 有了一级目录，文件系统就可实现对文件空间的管理和按名存取。

⚫ 一级目录表中各文件只能按连续结构或顺序结构存放，因此，文件名与文件必须一一对应，限制了用户对文件的命名，不能重名。

⚫ 优点： 简单， 容易实现。

⚫ 缺点： 搜索效率较低，文件平均检索时间长。

2) 二级目录结构

⚫ 为克服一级目录结构中文件目录命名中的可能冲突，并提高对目录文件的检索速度，一级目录被改进扩充成二级目录。

⚫ 在二级目录结构中，目录被分为两级：

① 第一级称为主文件目录（ Main File Directory， MFD),给出了用户名和用户子目录所在的物理位置；

② 第二级称为用户文件目录（ User File Directory， UFD)， 又称用户子目录， 给出了该用户所有文件的 FCB。

⚫ 优点： 解决了文件的重名问题， 可以实现用户间的文件共享， 查找时间也降低了。

⚫ 缺点： 增加了系统的开销。

3) 树形目录

⚫ 把二级目录的层次关系加以推广，就形成了多级目录，又称树形目录结构。

⚫ 在树形目录结构中，最高层为根目录，最低层为文件。

⚫ 根目录是唯一的，由它开始可以查找到所有其他目录文件和普通文件。根目录一般可放在内 存。从根结点出发到任一个非叶结点或叶结点（文件） 都有且仅有一条路径， 该路径上的全部分支组成了一个全路径名。

⚫ 树形目录结构的优点是便于文件分类，且具有下列特点：

① 层次清楚。

② 解决了文件重名问题。

③ 查找搜索速度快。

12. 全路径名&相对路径

有两种根据路径名检索的方法，一种是全路径名，另一种是相对路径。

⚫ 全路径名

① 使用全路径名检索的方法，需要从根目录开始，列出由根到用户指定文件的全部有关子目录， 全路径名又称为“ 绝对路径名”。

② 缺点： 不方便， 影响访问速度， 耗费时间。

⚫ 相对路径

① 用于检索的路径名只是从当前目录开始到所要访问文件的一段路径，即以当前目录作为路径的相对参照点。

② 优点： 检索路径缩短，检索速度提高。

13. 目录项分解法

⚫ 为加快目录检索可采用目录项分解法，即把目录项（ FCB)分为符号目录项（ 次部） 和基本目录项（主部） 两部分。

⚫ 符号目录项包含文件名以及相应的文件号；

⚫ 基本目录项包含了除文件名外文件控制块的其他全部信息；

⚫ 例子：

假设一个文件控制块有 48 字节，符号目录项占 8 字节，其中文件名占 6 字节，文件号占 2 字节； 基

本目录项占 48-8=40 字节。设物理块的大小为 512 字节。

在进行目录项分解前，一个物理块可以存放 512/48≈ 10 个文件控制块。在进行目录项分解后， 一个物理块可以存放 512/8=64 个符号目录项，或者 512/40≈ 12 个基本目录项。

如果一个目录文件有 128 个目录项，那么分解前 128×48/512=12，即需要 12 个物理块存放该目录文件。

在进行目录项分解后，符号目录文件占 128×8/512=2，即需要 2 个物理块存放符号文件。基本目录项占

128×40/512=10，即需要 10 个物理块存放基本目录文件。下面，计算查找一个文件的平均访盘次数。

分解前：（ 1+12)/2=6.5 次。分解后：（ 1+2)/2+1=2.5 次。

⚫ 目录项分解法的优点：减少了访问磁盘的次数，提高了文件目录检索速度。

14. 存储空间分配与回收

在设计空闲空间登记表的数据结构时，一般有四种不同的方案可以考虑，下面分别介绍。

1) 位示图

⚫ 位示图法的基本思想是，利用一串二进制位（ bit)的值来反映磁盘空间的分配使用情况。

⚫ 在位示图中，每一个磁盘中物理块用一个二进制位对应，如果某个物理块为空闲，则相应的二进制位为 0;如果该物理块已分配了， 则相应的二进制位为 1；

⚫ 在申请磁盘物理块时，可在位示图中从头查找为 0 的位， 如果发现了为 0 的位， 则将其改为 1， 同时返回该二进制位对应的物理块号。

⚫ 在归还不再使用的物理块时，则在位示图中将该物理块所对应的二进制位改为 0， 表示这块物理块恢复为空闲状态。

⚫ 优点：

① 对空间分配情况的描述能力强。一个二进制位就描述一个物理块的状态；

② 位示图占用空间较小，因此可以复制到内存，使查找既方便又快速；

③ 适用于各种文件物理结构的文件系统。

2) 空闲块表

⚫ 空闲块表是专门为空闲块建立的一张表，该表记录外存储器中全部空闲的物理块，包括每个空闲块的第一个空闲物理块号和该空闲块中空闲物理块的个数；

⚫ 空闲块表方式特别适合于文件物理结构为顺序结构的文件系统。

3) 空闲块链表

⚫ 将外存储器中所有的空闲物理块连成一个链表，用一个空闲块首指针指向第一个空闲块，随后的每个空闲块中都含有指向下一个空闲块的指针，最后一块的指针为空，表示链尾，这样就构成了一个空闲块链表；

⚫ 在空闲块链表模式中对空间的申请和释放是以块为单位的。申请空间时从链首取空闲块，空间释放时将物理块接入链尾。

⚫ 空闲块链表法节省内存，但申请空间和回收空间的速度较慢，实现效率较低。

4) 成组链接

对链接表的一个改进方案是将 n 个空闲盘块的地址存放在第一个空闲块中， 其余 n-1 个空闲盘块是实际空闲的。

假设每 100 个空闲块为一组。第一组的 100 个空闲块块号放在第二组的头一块中， 而第二组的其余

99 块是完全空闲的。第二组的 100 个块号又放在第 3 组的头一块中。依此类推， 组与组之间形成链接关系。在最后一组的块号中第 2 个单元填“ 0”，表示该块中指出的块号是最后一组的块号，空闲块链到此结束。在这个空闲块链中，不足 100 块的那个组的块号通常放在内存的一个专用块中。这种方式称为成组链接。

15. 回收和分配算法

1. 分配一个空闲块

查 L 单元内容（ 空闲块数）：

当空闲块数>1， i:= L+ 空闲块数； 从 i 单元得到一空闲块号；

把该块分配给申请者； 空闲块数减 1。

当空闲块数=1，取出 L+1 单元内容（一组的第一块块号或 0);

取值=0， 无空闲块，申请者等待；

取值≠ 0 ， 把该块内容复制到专用块； 该块分配给申请者；

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

2. 归还一块

查 L 单元的空闲块数；

当空闲块数<100， 空闲块数加 1; j：=L+空闲块数；

归还块号填入 j 单元。

当空闲块数=100，把主存中登记的信息写入归还块中； 把归还块号填入 L+1 单元；

将 L 单元置成 1。

16. 记录的成组

⚫ 把若干个逻辑记录合成一组存放在一个物理块的工作称为“ 记录的成组”， 每块中的逻辑记录个数称为“ 块因子”。

⚫ 由于信息交换以块为单位，所以要进行成组操作时必须使用内存的缓冲区，该缓冲区的长度等于要进行成组的最大逻辑记录长度乘以成组的块因子。

17. 建立文件

⚫ 用户首先调用文件系统的“ 建立文件” 操作，在请求调用该操作时提供所要创建的文件的文件名及若干参数:用户名、文件名、存取方式、存储设备类型、记录格式、记录长度， 等等。

⚫ 建立文件系统调用的一般格式为： create(文件名， 访问权限，（ 最大长度））。

⚫ 建立文件的具体步骤如下：

① 检查参数的合法性：

文件名是否符合命名规则，若是，则进行下一步②； 否则报错， 返回。

② 检查同一目录下有无重名文件：

若没有，则进行下一步③;否则报错， 返回。

③ 在目录中有无空闲位置：

若有，则进行下一步④;否则，不成功返回 Q

有的系统可能要为此文件申请数据块空间（申请一部分或一次性全部申请）。

④ 填写目录项内容：

包括:文件名、用户名、存取权限、长度置零、首地址等。

⑤ 返回。

18. 打开文件

⚫ 打开文件，是使用文件的第一步，任何一个文件使用前都要先打开，即把文件控制块 FCB 送到内存。

⚫ 打开文件系统调用的一般格式为:fd**=**open(文件路径名， 打开方式）。

⚫ 打开文件时，系统主要完成以下工作：

① 根据文件路径名查目录，找到 FCB 主部。

② 根据打开方式、共享说明和用户身份检查访问合法性。

③ 根据文件号查系统打开文件表，看文件是否已被打开。

如果是，共享计数加 1;否则，将外存中的 FCB 主部等信息填入系统打开文件表空表项，共享计数置为 1。

④ 在用户打开文件表中取一空表项，填写打开方式等，并指向系统打开文件表对应表项。返回信息：文件描述符 fd，这是一个非负整数， 用于以后读写文件。

19. 读文件

⚫ 打开文件后，就可以读取文件中的信息。

⚫ 读文件系统调用的一般格式为： read(文件名，（ 文件内位置）， 要读的长度， 内存目的地址）。

⚫ 隐含参数：文件主。

⚫ 读写方式可为读、写和既读又写等。

⚫ 读文件时，系统主要完成以下工作：

① 检查长度是否为正整数：

若是，则进行下一步②;否则，转向⑩。

② 根据文件名查找目录，确定该文件在目录中的位置。

③ 根据隐含参数中的文件主和目录中该文件的存储权限数据，检查是否有权读。若是，则进行下一步④;否则，转向⑩。

④ 由文件内位置与要读的长度计算最末位置，将其与目录中的文件长度比较，超过否？若是，则转向⑩； 否则， 进行下一步⑤。也可将参数中的长度修正为目录中的文件长度。

⑤ 根据参数中的位置、长度和目录中的映射信息，确定物理块号、需要读出的块数等读盘参数

（参数准备完毕后，进行物理的读盘操作，读盘操作可能要进行多次）。

⑥ 根据下一块号读块至内存缓冲区。

⑦ 取出要读的内容，也许要进行成组的分解，将取出的内容送至参数中的内存目的地址。

⑧ 根据块内长度或起始块号+块数， 确定还读下一块吗？ 同时确定下一块块号： 若是，则转向⑤;否则，进行下一步⑨。

⑨ 正常返回。

⑩ 错误返回，返回相应错误号。

20. 写文件

⚫ 写文件系统调用的一般格式为： write(文件名， 记录键， 内存位置）。

⚫ 把内存中指定单元的数据作为指定的一个记录写入指定文件中，系统还将为其分配物理块，以便把记录信息写到外存上。

21. 关闭文件

⚫ 文件关闭后一般不能存取，若要存取，则必须再次打开。

⚫ 关闭文件系统调用的一般格式为： close(文件名）。

⚫ 系统根据用户提供的文件名或文件描述符，在该文件的文件控制块上做修改。

22. 删除文件

⚫ 删除文件系统调用的一般格式为： delete(文件名）。

⚫ 系统根据用户提供的文件名或文件描述符，检查此次删除的合法性，若合法， 则收回该文件所占用的文件控制块及物理块等资源。

23. 指针定位

⚫ 指针定位的一般格式为： seek(fd， 新指针的位置）。

⚫ 指针定位时，系统主要完成以下工作：

① 由 fd 检查用户打开文件表， 找到对应的入口；

② 将用户打开文件表中文件读写指针位置设为新指针的位置，供后续读写命令存取该指针处文件内容。

24. 文件的保护

文件系统经常采用建立副本和定时转储的方法来保护文件。

1) 建立副本

⚫ 对文件建立副本，是保护文件不受破坏的有效方法。

⚫ 一般用于短小且极为重要的文件。

2) 定时转储

⚫ 定时转储的含义是，每隔一定的时间就把文件转储到其他的存储介质上。

⚫ UNIX 系统就是釆用定时转储的方法保护文件，以提高文件的可靠性。

⚫ 按照转储内容可分为增量转储和全量转储。增量转储是指备份自上一次转储以来更改过的文件。

⚫ 按照转储方式可分为物理转储和逻辑转储。

① 物理转储是从磁盘的第 0 块开始，将全部磁盘块按序输出到另一介质上，直到最后一块复制完毕。

② 而逻辑转储是从一个或几个指定的目录开始，递归地转储其自给定日期（例如，最近一次增量转储或全量转储的日期）后有所更改的全部文件和目录。

3) 规定文件的存取权限

规定用户使用文件的权限的方法有两种：

⚫ 采用树形目录结构。

凡能得到某级目录的用户就可得到该级目录所属的全部目录和文件，按目录中规定的存取权限使用目录或文件。

⚫ 存取控制表。

列出每个用户对每个文件或子目录的存取权限。

25. 存取控制矩阵

⚫ 在存取控制矩阵方式中，系统以一个二维矩阵来实施文件的存取控制。

⚫ 在这个二维矩阵中，其中一维代表所有的用户，另一维代表所有的文件。

⚫ 两维交叉点所对应的矩阵元素则是某一个用户对一个文件的存取控制权限，包括读 R、写 W 和执行 E， 当然， 还可以有其他的划分形式。

26. 二级存取控制

⚫ 对文件实施存取控制的另一种方法是二级存取控制。

⚫ 二级存取控制方法中设立两个存取级别。

① 在第一级，把用户按某种关系划分为若干用户组，进行对访问者的识别；

② 在第二级，进行对操作权限的识别。

⚫ 常用的文件保密措施还有隐蔽文件目录、设置口令与使用密码等。

27. UNIX 系统内部数值

⚫ 读（ Read)操作（ R);

⚫ 写（ Write)操作（ W);

⚫ 执行（ e X e c u t e )操作（ X ) ;

⚫ 不能执行任何操作（–）。

⚫ UNIX 系统内部使用数值来表示上述的文件属性每一个属性与文件属性中的一个二进制位相对

应。如果该存取权限设置了，对应的二进制位就是 1， 如果该存取权限没有设置， 对应的二进制位是 0。

l 例： a.out 的权限属性 rwxr**- -** xr**–** x 用二进制来表示就是 111101101。在 UNIX 中常使用八进制的形式表示，于是 a.out 的这个权限是 755。

28. 提高文件系统性能的方法

常见的技术措施有如下几种：块高速缓存、磁盘空间的合理分配和对磁盘调度算法进行优化。

1) 块高速缓存

其基本思想是，系统在内存中保存一些磁盘块，这些磁盘块在逻辑上属于磁盘，内存的这一区域被称为块高速缓存。

块高速缓存的内容需要定期写回到磁盘上，以保存对磁盘块的修改。

2) 合理分配磁盘空间

在磁盘空间中分配块时，应该把有可能顺序存取的块放在一起，最好在同一柱面上。

这样可以有效地减少磁盘臂的移动次数，加快了文件的读写速度，从而提高了文件系统的性能。

3) 磁盘的驱动调度

磁盘是一种高速旋转的存储设备。磁头沿着盘片直径方向移动， 同时对指定磁道上的扇面中的数据进行读写操作。当多个访盘请求在等待时，系统采用一定的策略，对这些请求的服务顺序进行调整安 排，使寻道时间和延迟时间都尽可能小的那个访问请求可以优先得到服务，并降低若干个访问者的总访问时间，增加磁盘单位时间内的操作次数。其目的在于降低平均磁盘服务时间， 从而实现公平、高效的访盘请求。

29. 磁盘调度算法

1) 磁盘的存取访问时间

磁盘的存取访问时间由 3 部分组成：

⚫ 寻道时间，即将磁头移动到相应的磁道或柱面所需的时间；

⚫ 旋转延迟时间，即一旦磁头到达指定磁道，必须等待所需要的扇区旋转到读头下的时间；

⚫ 传输时间，即信息在磁盘和内存之间的实际传送时间。

⚫ 一次磁盘服务的总时间就是以上 3 个时间之和。要使磁盘服务尽可能地快， 就需要操作系统提供合适的磁盘调度算法，以改善磁盘服务的平均时间。

2) 设计磁盘调度算法应当考虑两个基本因素：

⚫ 公平性： 一个磁盘访问请求应当在有限时间内得到满足。

⚫ 高效性： 减少设备机械运动所带来的时间开销，增加磁盘缓存。

3) 磁盘驱动调度

磁盘驱动调度由“ 移臂调度” 和“ 旋转调度”两部分组成。

⚫ 移臂调度

根据访问者指定的柱面位置来决定执行次序的调度，称为“ 移臂调度”。移臂调度的目的是尽可能地减少操作中的寻找时间。

⚫ 一般可采用以下几种移臂调度算法： 先来先服务调度算法（ FCFS)、最短寻道时间优先调度算法

（ SSTF)、 扫描算法（SCAN)、循环扫描算法（ C-SCAN)。

30. 先来先服务调度算法（ FCFS)

⚫ 即按照访问请求的次序为各个进程服务，这是最公平而又最简单的算法，但是效率不高。

⚫ 因为磁头引臂的移动速度很慢，如果按照访问请求发出的次序依次读写各个磁盘块，则磁头引臂将可能频繁大幅度移动，容易产生机械振动，亦造成较大的时间开销，影响效率。

31. 最短寻道时间优先调度算法（ SSTF)

⚫ SSTF 算法以寻道优化为出发点， 优先为距离磁头当前所在位置最近磁道（ 柱面） 的访问请求服务。

⚫ 这种算法改善了平均服务时间，但也存在缺点：假设某一段时间外磁道请求不断，则可能有内磁道请求长时间得不到服务，缺乏公平性。

32. 扫描算法（ SCAN)

⚫ 这种算法因其基本思想与电梯的工作原理相似，故又称电梯算法。

⚫ SCAN 算法也是一种寻道优化的算法， 它克服了 SSTF 算法的缺点。

⚫ SSTF 算法只考虑访问磁道与磁头当前位置的距离， 而未考虑磁臂的移动方向， 而 SCAN 算法则既考虑距离，也考虑方向，且以方向优先。

⚫ 这种算法比较公平，而且效率较高。

33. 文件分配表（FAT）

⚫ FAT 是一个简单的文件系统， 最初为 DOS 操作系统设计， 适用于小容量的磁盘， 具有简单的目录结构。

⚫ 为了向后兼容，也为了方便用户升级，目前新版本的 Wmdows 仍然提供对 FAT 的支持。

⚫ FAT 文件系统总共有 3 个版本： FAT-12、FAT-16 和 FAT-32， 取决于用多少二进制位表示磁盘地

址。

⚫ FAT 文件系统以簇为单位进行分配， 所以 FAT-16 文件系统表示用 16 位（ 2 字节） 表示簇号。

34. 文件系统执行 close（）

执行“关闭”操作时，文件系统主要完成如下工作：

① 将活动文件表中该文件的“当前使用用户数”减 1；若此值为 0，则撤销此表目，并保存文件控制块写入磁盘或者缓存；

② 若活动文件表目内容已被改过，则表目信息应复制到文件存储器上相应表目中，以使文件目录保持最新状态；

③ 卷定位工作，一个关闭后的文件不能再使用，若要再使用，则必须再次执行“打开”操作。

第七章 I/O 设备管理

1. 设备管理

⚫ 设备管理是操作系统的主要功能之一，它负责管理所有输入输出设备以完成期望的数据传设备管

理；

⚫ 由于计算机系统中存在着大量的输入/输出设备，其性能和应用特点可能完全不同。所以要建立一

个通用的、一致的设备访问接口，使用户和应用程序开发入员能够方便地使用输入/输出设备。

2. 设备管理的主要任务

⚫ 设备管理的主要任务有：缓冲区管理、设备分配、设备处理、虚拟设备以及实现设备独立性。

⚫ 操作系统主要通过缓冲技术、中断技术和虚拟技术来解决 I/O设备系统的性能；

⚫ 操作系统需要在设备管理和系统的其他部分之间提供简单而易于使用的接口；

⚫ 对于设备拥有者而言，多用户多任务环境中的设备使用应该通过协调避免冲突，设备不能被破坏。

3. 设备的分类

1) 按设备的使用特性分类

按设备的使用特性分类，可以分为 I/O 设备和存储设备。

⚫ I/O 设备：

① 是计算机与外部世界交换信息的设备。

② 输入设备是计算机用来接受指令和数据等信息的设备（ 键盘、鼠标等）；

③ 输出设备是计算机用来传送处理结果的设备（显示器、打印机等）；

④ 在计算机数据采集和过程控制等应用中，各种传感器、传动器、模拟/数字转换器、数字/模拟转换器等也属于 I/O 设备；

⑤ 调制解调器、网络适配器（网络接口卡） 等数据通信设备也属于 I/O 设备，这类设备用于构建计算机网络通信系统。

⚫ 存储设备：

① 是计算机用来存放信息的设备，例如磁带、磁盘、光盘、U 盘等各种外存设备。

② 其中，可移动的磁带或磁盘在用于不同机器间传送数据时也可看作是 I/O 设备。

2) 按设备的信息组织方式来划分

按信息组织方式来划分设备，可以把 I/O 设备划分为字符设备（character device)和块设备(block device)。

⚫ 字符设备

① 键盘、终端、打印机等以字符为单位组织和处理信息的设备；

② 字符设备通常以字符为单位发送或者接收字符流，而不存在任何块结构。

③ 字符设备不可寻址，所以没有任何寻址操作。除磁盘以外的大多数设备，例如网络接口卡、打印机、鼠标等可看作字符设备。

⚫ 块设备

① 磁盘、磁带等以数据块为单位组织和处理信息的设备

② 基本特性： 能够随时读写其中的任何一块而与所有别的块无关。

③ 外存类设备通常是块设备，因其记录长度通常为一个数据块，例如磁盘的扇区或者由若干扇区组成的簇。

3) 按设备的共享属性分类

按设备的共享属性可以将设备分为共享设备、独占设备和虚拟设备。

⚫ 共享设备

共享设备是指在一段时间内允许多个进程使用的设备。磁盘是典型的共享设备。

⚫ 独占设备

独占设备也称为独享设备，是指在一段时间内只允许一个进程使用的设备。独占设备的使用效率低是造成死锁的条件之一。

⚫ 虚拟设备

虚拟设备是指利用虚拟技术把独占设备改造成可由多个进程共享的设备。SPOOLing 系统是一种非常重要的虚拟设备技术。

4. I/O 设备的控制方式

有程序直接控制方式、中断控制方式、DMA 方式和通道控制方式。

5. 程序直接控制方式（PIO(Programmed I/O，程控 I/O)方式）

⚫ 指由用户进程直接控制内存或 CPU 和外围设备之间进行信息传送的方式，

⚫ 也称为“忙-等”方式、轮询方式或循环测试方式， 控制者是用户进程。

⚫ 过程

① 用户进程从外围设备输入数据时，通过 CPU 发出启动设备准备数据的启动命令(通常是把一个启动位为 1 的控制字通过数据总线写入设备的控制寄存器中）。

② 用户进程进入测试等待状态。在等待时间， CPU 不断地用一条测试指令检查设备的状态寄存器是否为完成状态（通常是检测状态寄存器的完成位是否为1)，而外围设备只有将输入数据送入数据缓冲寄存器之后，才将该寄存器置为完成状态。

③ 当 CPU 检测到设备的状态寄存器为完成状态，则从设备的数据缓冲寄存器读取数据到内存或 CPU。

④ 反之，当用户进程需要向输出设备输出数据时，也必须同样发出启动命令和等待设备准备好之后才能输出数据。

l 优点：CPU 和外设的操作能通过状态信息得到同步，而且硬件结构比较简单；

l 缺点：CPU 效率较低，传输完全在 CPU 控制下完成，对外部出现的异常事件无实时响应能力。

所以，程序直接控制方式只适用于那些 CPU 执行速度较慢，而且外围设备较少的系统，如单片机系统。

6. 程序直接控制的关键部件

I/O 设备数据传送控制方式中，实现程序直接控制方式需要的关键部件包括设备状态寄存器、地址总线和数据总线、设备控制寄存器、设备数据缓冲区和地址译码器。

7. 中断控制方式

⚫ 中断是在发生了一个异常事件时，调用相应处理程序（通常称为中断服务程序）进行服务的过程。

⚫ 中断服务程序与中断时 CPU 正在执行的进程是相互独立的， 相互不传递数据。

⚫ 优点：

① CPU与外设在大部分时间内并行工作，有效地提高了计算机的效率。

② 具有实时响应能力，可适用于实时控制场合。

③ 及时处理异常情况，提高计算机的可靠性。

8. 中断控制方式的处理过程

⚫ CPU 通过数据总线发出命令，启动外设工作，当前进程阻塞，调度程序调度其他进程；

⚫ 外设数据准备好，置位中断请求触发器；

⚫ 若此时接口中断屏蔽触发器状态为非屏蔽状态，则接口向 CPU 发出中断请求（IR）；

⚫ CPU 接受中断请求（设备控制器的功能），且中断为允许中断状态，则中断判优电路工作；

⚫ 中断判优电路对优先级最高的中断请求给予响应（INTA），CPU 中断正在执行的其他进程，转而执行中断服务程序。所以需要的关键部件是：中断控制器、地址总线和数据总线、设备控制器。

9. DMA（直接内存访问)方式

⚫ 目的：

① 减少 I/O 数据交换消耗的处理时间；

② 提升高速的外围设备以及成组交换数据的速度。

⚫ DMA 方式的数据块传送过程可分为 3 个阶段:传送前预处理、数据传送、传送后处理。

① 预处理阶段——由 CPU 执行 I/O 指令对 DMAC 进行初始化与启动。

② 数据传送阶段——由 DMAC 控制总线进行数据传输。当外设数据准备好后发 DMA 请求， CPU 当前机器周期结束后响应 DMA 请求，DMAC 从 CPU 接管总线的控制权，完成对内存寻址，决定数据传送的内存单元地址，对数据传送字进行计数，执行数据传送的操作。

③ 后处理阶段——传送结束，DMAC 向 CPU 发中断请求，报告 DMA 操作结束。CPU 响应中断，转入中断服务程序，完成 DMA 结束处理工作， 包括校验数据， 决定是否结束传送等。

⚫ DMA 方式一般用于高速传送成组的数据。

⚫ 优点：

① 操作均由硬件电路实现，传输速度快；

② CPU 仅在初始化和结束时参与， 对数据传送基本上不干预， 可以减少大批量数据传输时 CPU 的开销；

③ CPU 与外设并行工作， 效率高。

⚫ 局限性：

① DMA 方式在初始化和结束时仍由 CPU 控制；

② 在大型计算机系统中，为了进一步减轻 CPU 的负担和提高计算机系统的并行工作程度， 除了设置

DMA 器件之外， 还设置了专门的硬件装置——通道。

10. DMA 控制的关键部件

实现 DMA控制方式需要的关键部件包括:DMA控制器、地址总线和数据总线。

11. 通道控制方式

⚫ 通道（ channel）是一个特殊功能的处理器，它有自己的指令和程序，可以实现对外围设备的统一管理和外围设备与内存之间的数据传送。

⚫ 引入通道的目的： 是为了进一步减少数据输入输出对整个系统运行效率的影响。

⚫ 按照信息交换方式分类

① 选择通道

是一种高速通道，在物理上它可以连接多个设备，但是这些设备不能同时工作；

选择通道主要用于连接高速外围设备，如磁盘、磁带等，信息以成组方式高速传输； 优点： 以数据块为单位进行传输， 传输率高；

缺点： 通道利用率低。

② 数组多路通道

当某个设备进行数据传送时，通道只为该设备服务；

当设备在执行寻址等控制性动作时，通道暂时断开与这个设备的连接，挂起该设备通道程序，为其他设备服务；

优点： 数据块为单位进行传输， 传输率高；又具有多路并行操作的能力， 通道利用率高。缺点： 控制复杂。

③ 字节多路通道

是一种简单的共享通道，在分时的基础上为多台低速和中速设备服务。

特点:各设备与通道之间的数据传送是以字节为单位交替进行的， 各设备轮流占用一个短的时间片； 多路并行操作能力与数组多路通道相同。

12. 通道的功能

⚫ 接受 CPU 的指令， 按指令要求与指定的外围设备进行通信。

⚫ 从内存读取属于该通道的指令，并执行通道程序，向设备控制器和设备发送各种命令。

⚫ 组织外围设备和内存之间进行数据传送，并根据需要提供数据缓存的空间，以及提供数据存入内存的地址和传送的数据量。

⚫ 从外围设备得到设备的状态信息，形成并保存通道本身的状态信息，根据要求将这些状态信息送到内存的指定单元，供 CPU 使用。

⚫ 将外围设备的中断请求和通道本身的中断请求，按序及时报告 CPU。

13. I/O 系统硬件结构

⚫ 计算机 I/O 系统硬件结构主要包含 3 部分：适配器和接口部件、设备控制器、设备硬件。

14. I/O 软件分层

一般可以分为四层：中断处理程序，设备驱动程序，与设备无关的操作系统软件，用户级软件（ 指用户空间的 I/O 软件）。

15. 与设备无关 I/O 软件功能

① 设备驱动程序的统一接口

② 设备命名： 在操作系统的 I/O 软件中， 对 I/O 设备采用了与文件统一命名的方法，即采用文件系统路径名的方法来命名设备。

③ 设备保护：对设备进行必要的保护，防止无授权的应用或用户的非法使用，是设备保护的主要作用。

④ 提供一个与设备无关的逻辑块

⑤ 缓冲： 对于常见的块设备和字符设备， 一般都使用缓冲区。

⑥ 存储设备的块分配：在创建一个文件并向其中填入数据时， 通常在硬盘中要为该文件分配新的存储块。

⑦ 独占设备的分配和释放

⑧ 错误处理

一般而言，所有设备都需要的 I/O 功能可以在与设备独立的软件中实现。这类软件面向应用层并提供一个统一的接口。

16. 典型的 I/O 技术

⚫ 在 I/O 设备管理中， 为了提高设备和 CPU 的效率， 引入了各种技术。

⚫ 经常使用技术有： 缓冲技术、设备分配技术、SPOOLing 技术、DMA 与通道技术。

17. 缓冲技术

⚫ 为了解决中央处理机和外部设备的速度不匹配和负荷不均衡问题，为了提高各种设备的工作效率， 增加系统中各部分的并行工作速度

⚫ 缓冲技术是计算机系统中常用的技术。一般，数据到达速度和离去速度不匹配的地方都可以通过设置缓冲区，以缓解处理机与设备之间速度不匹配的矛盾，并减少对 CPU 的 I/O 中断次数从而提高资源利用率和系统效率。

18. 设备分配技术

1) 设备分配算法的数据结构

⚫ 在设备分配算法的实现中，常采用的数据结构主要含四张表。

① 系统设备表 SDT(System Device Table)：登录了该设备的名称、标识及设备控制表 DCT 的入口地址等相关的信息。

② 设备控制表 DCT(Device Control Table)： 在 DCT 中充分体现出了设备的各方面特征，以及与该设备相连的设备控制器的情况，并保存了控制器块的入口位置。

③ 控制器控制表 COCT(Controller Control Table)：用于登录某控制器的使用分配情况及与该控制器相连的通道的情况。

④ 通道控制表 CHCT(Channel Control Table)：反映了通道的情况，系统中的每个通道都有一张 CHCT。

2)设备分配的原则

⚫ 设备分配的总原则：一方面要充分发挥设备的使用效率，同时又要避免不合理的分配方式造成死锁、系统工作紊乱等现象，使用户在逻辑层面上能够合理方便地使用设备。

⚫ 考虑设备的特性和安全性

设备的特性是设备本身固有的属性，一般分为独占、共享和虚拟设备等；

⚫ 从安全性方面考虑：

① 安全分配方式： 安全，效率比较低， CPU 与 I/O 设备串行工作、

② 不安全分配方式两种：提高了运行效率，但存在造成死锁的可能，因此设备分配程序中应该增加预测死锁的安全性计算，在一定程度上增加了程序的复杂性。

⚫ 设备分配策略

与进程的调度相似， 设备的分配也需要一定的策略， 通常采用先来先服务（ FIFO)和高优先级优先等策略。

① 先来先服务策略： 当多个进程同时对一个设备提出 I/O 请求时，系统按照进程提出请求的先后次序，把它们排成一个设备请求队列，并且总是把设备首先分配给排在队首的进程使用。

② 高优先级优先策略：给每个进程提出的 I/O 请求分配一个优先级，在设备请求队列中把优先级高的排在前面，如果优先级相同则按照 FIFO 的顺序排列。

3) 独占设备的分配

独占设备每次只能分配给一个进程使用，这种使用特性隐含着死锁的必要条件，所以在考虑独占设备的分配时，一定要结合有关防止和避免死锁的安全算法。

4) 共享设备的分配

① 共享设备是可由若干个进程同时共享的设备，例如磁盘。

② 通常，共享型设备的 I/O 请求来自文件系统、虚拟存储系统或输入输出管理程序，其具体设备已经确定，因而设备分配比较简单，即当设备空闲时分配，占用时等待。

19. 虚拟设备

⚫ 系统中独占设备有限，不能满足多个进程，因而引起大量进程由于等待某些独占设备而阻塞，造成系统“瓶颈”。

⚫ 申请到独占设备的进程运行期间利用率低，设备常处于空闲状态。

⚫ 从而引入虚拟设备技术。

⚫ 实现这一技术的软、硬件系统被称为 SPOOLing(Simultaneous Peripheral Operation On Line,外围设备同时联机操作）系统。

20. SPOOLing 技术

⚫ SPOOLing 技术是一种同时的外围设备联机操作技术，通常称为“假脱机技术”。

⚫ SPOOLing 系统的 3 大组成部分：输入井和输出井、输入缓冲和输出缓冲、输入进程 SPi 和输出进程 SPo。

21. 提高 I/O 性能的技术

⚫ 通过应用缓冲技术，解决传输速度差异的问题。

⚫ 通过应用异步 I/O 技术，使 CPU 不必等待 I/O 的操作结果。

⚫ 通过应用 DMA 和通道部件， 使 CPU 与这些部件能并行执行。

⚫ 通过应用虚拟设备技术，减少进程阻塞时间，提高独占设备的利用率。

22. 设备表作用

⚫ 为了实现设备的独立性，系统必须设置一张逻辑设备表，用于将应用程序中所用的逻辑设备名映射为物理

设备名。

⚫ 在该表每个表目中有 3 项：逻辑设备名、物理设备名和设备驱动程序入口地址。

⚫ 系统设备表 SDT，在 SDT 中每个接入系统中的设备都有一个表目项。登录了设备的名称，标识设备控制表

DCT 的入口地址等相关信息。

⚫ 全面反映了系统中的外设资源的情况，逻辑设备与物理设备之间对应关系等。

23. 设备独立层

设立设备独立层的主要目的是用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护、以及设备分配与释放等，同时为设备管理和数据传送提供必要的存储空间。

24. “准备就绪”信号

⚫ 在程序控制 I/O 方式中，输出设备的主要作用是通过输出设备输出数据；

⚫ 若输出设备向处理机返回“准备就绪”信号，则表示输出缓冲区已空或者可以向输出缓冲区写数据，CPU 可以向输出设备再次提供输出的数据。

25. 外部设备命令传递

当用户使用外部设备时，其控制设备的命令传递途径依次为： 用户应用层→设备独立层→设备驱动层→设备硬件。

26. 高速缓存

⚫ 高速缓存不是缓冲，在计算机存储系统的层次结构中，介于中央处理器和主存储器之间的高速小容量存储器。

⚫ 它和主存储器一起构成一级的存储器。

⚫ 高速缓冲存储器和主存储器之间信息的调度和传送是由硬件自动进行的。

27. 键盘的 I/O 控制

⚫ 键盘的工作原理是由键盘控制器专门来完成的，当键盘控制器收到数据后通过中断控制器 IRQ1 引脚向CPU

发送中断请求。

⚫ 当 CPU 响应中断后就会调用键盘中断处理程序来读取控制器中的键盘扫描码。因此键盘的 I/O 控制是通过中断方式来实现的。

第八章 死锁

1. 死锁、饥饿和活锁

⚫ 死锁是指在多道程序中，一组进程中的每个进程均无期限的等待被该组进程中的另一个进程所占有且永远不会释放的资源。

⚫ 饥饿是指一个可运行的进程尽管能继续执行，但被调度器无限期地忽视，而不能被调度执行的情况。饥饿可以通过先来先服务资源分配策略来避免。

⚫ 活锁指的是任务或者执行者没有被阻塞，由于某些条件没有满足，导致一直重复尝试，失败，尝试，失败。

⚫ 活锁和死锁的区别在于活锁的实体是在不断的改变状态，活锁有可能自行解开，死锁则不能。

2. 死锁产生的原因

产生死锁的原因主要有两个:

⚫ 一是竞争资源，系统提供的资源数量有限，不能满足每个进程的需求；

⚫ 二是多道程序运行时，进程推进顺序不合理。

3. 产生死锁的四个条件

1) 互斥条件

资源是独占的且排他使用。进程互斥使用资源，即任一时刻一个资源只能给一个进程使用，其他进程若请求一个资源而该资源被另一进程占有时，则申请者等待，直到资源被占用者释放。

2) 不可剥夺条件

又称不可抢占或不可强占。进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，而只能由获得该资源的进程自愿释放。

3) 请求和保持条件

又称部分分配或占有申请。进程每次申请它所需要的一部分资源，在申请新的资源的同时，继续占用已分配到的资源。

4) 循环等待条件

又称环路等待。在发生死锁时，必然存在一个进程等待队列｛ P1,P2，···， Pn｝，其中P1等待 P2 占有的资源，P2 等待 P3 占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路。环路中每一个进程已占有的资源同时被另一个进程所申请，即前一个进程占有后一个进程所请求的资源。

4. 死锁检测

⚫ 操作系统可定时运行一个“死锁检测”程序，该程序按一定的算法去检测系统中是否存在死锁。

⚫ 检测死锁的实质是确定是否存在“循环等待”条件，检测算法确定死锁的存在并识别出与死锁有关的进程和资源，以供系统采取适当的解除死锁措施。

5. 死锁预防

⚫ 在设计系统时确定资源分配算法，限制进程对资源的申请，从而保证不发生死锁。

⚫ 具体的做法是破坏产生死锁的四个必要条件之一：

① 破坏“互斥条件”：可以通过采用假脱机（SPOOLing）技术，允许若干个进程同时输出；

② 破坏“不可剥夺”条件：如果资源没有被等待进程占有，那么该进程必须等待，在其等待过程中，其资源也有可能被剥夺；

③ 破坏“请求和保持”条件：可以采用静态分配资源策略，将满足进程条件的资源一次性分配给进程，也可以采用动态资源分配，即需要资源时才提出申请，系统在进行分配；

④ 破坏“循环等待”条件：进程申请资源时，必须严格按照资源编号的顺序进行，否则系统不予分配。

6. 死锁避免

⚫ 死锁避免的基本思想是：系统对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源； 如果分配后系统可能发生死锁， 则不予分配， 否则予以分配。

⚫ 这是一种保证系统不进入死锁状态的动态策略。

7. 安全与不安全状态

如果操作系统能保证所有的进程在有限时间内得到所需的全部资源，则称系统处于“ 安全状态”，否则说系统是不安全的。

⚫ 安全状态是指： 如果存在一个由系统中所有进程构成的安全序列{P1，…， Pn}，则系统处于安全状态。一个进程序列{P1，…，Pn}是安全的，如果对于其中每一个进程 Pi（ 1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程 pj(j<i） 当前占有资源量之和。系统处于安全状态则不会发生死锁。

⚫ 如果不存在任何一个安全序列，则系统处于不安全状态。不安全状态一定导致死锁，但不安全状态不一定是死锁状态。即系统若处于不安全状态则可能发生死锁。

8. 银行家算法

⚫ 银行家算法是一种最有代表性的避免死锁的算法，又被称为“资源分配拒绝”法。

⚫ 安全序列计算过程：

① 分别求出各进程所需最大资源数量(a)、已分配资源数(b)、缺少资源数©和资源剩余可分配量(d)；

② 拿 c 和 d 进行比较:

d>c:满足分配，此时 d1=d-c;

否则不满足，寻找下个可满足的进程；

③ 进程分配运行后释放该进程资源,则d2=d1+a=d+b;

④ 按此步骤继续计算寻找可分配进程，直至完成所有进程分配。

9. 死锁解除法

死锁解除法可归纳为两大类：

⚫ 剥夺资源：使用挂起/激活机制挂起一些进程，剥夺它们占有的资源给死锁进程，以解除死锁。经常使用的方法有还原算法和建立检查点。

⚫ 撤销进程：撤销死锁进程，将它们占有的资源分配给另一些死锁进程，直到死锁解除为止。撤销代价的标准有进程优先数、进程类的外部代价和运行代价，即重新启动进程并运行到当前撤销点所需要的代价。

10. 资源分配图化简方法

1. 在资源分配图中，找出一个既非等待又非孤立的进程结点 Pi，由于 Pi 可获得它所需要的全部资源，且运行完后释放它所占有的全部资源，故可在资源分配图中消去所有的申请边和分配边，使之成为既无申请边又无分配边的孤立结点。

2. 将 Pi 所释放的资源分配给申请它们的进程，即在资源分配图中将这些进程对资源的申请边改为分配边。

3. 重复 1）、2） 两步骤，直到找不到符合条件的进程结点。

⚫ 经过化简后，若能消去资源分配图中的所有边，使所有进程都成为孤立结点，则该图是可完全化简的；否则为不可化简的。

⚫ 所有的化简顺序将导致相同的不可化简图。可以证明，系统处于死锁状态的充分条件是，当且仅当该系统的资源分配图是不可完全化简的。

11. 独占设备预防死锁

⚫ 对于系统中的独占设备，为预防出现死锁，一般需要避免动态分配锁。也就说，锁应该采用静态分配。

⚫ 死锁预防的一种措施，就是定时重试和定时放弃锁。

⚫ 为了避免多个进程同时获取锁，因此锁的分配必须是采用加锁的互斥方式。

⚫ 死锁预防，在系统设计时确定资源分配算法，保证不发生死锁。

⚫ 具体的做法是破坏产生死锁的 4 个必要条件之一，其中破坏“循环等待”条件主要是通过“资源有序分配法”来解决死锁。