Hexo
0%

计算机组成原理

发表于 分类于 ，

计算机组成原理

4.1.4 文件的物理结构(文件分配方式)上

操作系统对磁盘块的管理：

  1. 对非空闲磁盘块的管理—文件的物理结构/文件分配方式
  2. 对空闲磁盘块的管理—文件存储空间管理

文件的物理结构/文件分配方式：

  1. 即文件数据如何存放在外存中，或者逻辑地址到物理地址的映射
  2. 连续分配
  3. 链接分配
    3.1 隐式链接
    3.2 显式链接
  4. 索引分配

磁盘块vs内存块：磁盘中的存储单元也被分为一个个“磁盘块”。一般情况下，磁盘块的大小与内存块、页面的大小相同。内存与磁盘之间的数据交换都是以块为基本单位。

磁盘块vs文件块：在内存管理中，进程的逻辑地址被分为一个个页面，可以表示为(页面号, 块内地址)。在外存管理中，为了方便对文件数据的管理，文件的逻辑地址也被分为一个个的文件块，也可以表示为(逻辑块号，块内地址)。

用户通过逻辑地址操作自己的文件，而操作系统负责实现从逻辑地址到物理地址的映射

文件分配方式—连续分配

连续分配实现每个文件在磁盘上占有一组连续的块

文件目录

文件名 … 起始块号 长度
aaa … 4 3
bbb … 10 5

操作系统找到该文件的目录项(FCB)
物理块号=起始块号+逻辑块号

优点：连续分配方式支持顺序访问和直接访问(即随机访问)，顺序读写速度最快。
缺点：对文件的拓展不方便，存储利用率低，会产生磁盘碎片(紧凑技术)

文件分配方式—链接分配

链接分配采用离散分配的方式，为文件分配离散的磁盘块，分为隐式链接和显式链接两种。

链接分配—隐式链接

目录中记录文件的起始块号和结束块号，每个磁盘块都会保存指向下一个盘块的指针，这些指针对用户是透明的。

隐式链接只支持顺序访问，不支持随机访问。
不会产生碎片问题，方便拓展文件。

链接分配—显式链接

把用于链接文件各物理块的指针显式存放在一张表中，即文件分配表(FAT):物理块号—下一块，目录中只需要记录文件的起始块号。

一个磁盘仅设置一张FAT。开机时，FAT读入内存，并常驻内存。FAT的各个表项在物理上连续存储，且物理块号字段可以隐含。

采用显式链接方式的文件，支持顺序访问，也支持随机访问(多次访问FAT表，并不依次访问之前的磁盘块，块号的转换过程并不需要访问磁盘)，所以相比隐式链接来说，访问速度很快。
不会产生外部碎片，支持文件扩展。
文件分配表需要占用一定的存储空间

4.1.4 文件的物理结构(文件分配方式)下

操作系统对磁盘块的管理：

  1. 对非空闲磁盘块的管理—文件的物理结构/文件分配方式
  2. 对空闲磁盘块的管理—文件存储空间管理

文件的物理结构/文件分配方式：

  1. 即文件数据如何存放在外存中，或者逻辑地址到物理地址的映射
  2. 连续分配
  3. 链接分配
    3.1 隐式链接
    3.2 显式链接
  4. 索引分配

文件分配方式—索引分配

索引分配方式允许文件离散地分配在各个磁盘中，系统为每个文件建立一张索引表，索引表记录了文件的各个逻辑块对应的物理块(类似内存管理中的页面，记录逻辑页面到物理页面的映射)。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

文件目录：文件名—索引块
索引表：逻辑块号—物理块号

显式链接：文件分配表FAT是一个磁盘对应一张表
索引分配：一个文件对应一张表

索引分配支持顺序访问和随机访问，支持文件扩展

假设磁盘块大小为1KB，一个索引表表项占4B，则一个磁盘块只能存放256个索引项。

索引块的大小是有限制的，如果文件太大，一张索引表太大，无法存储在一个索引块上时，需要以下方式解决：

  1. 链接方案
  2. 多层索引
  3. 混合索引

文件分配方式—索引分配—链接方案

如果索引表太大，一个索引块装不下，那么可以将多个索引块隐式链接存放，即索引块中存放指向下一个索引块的链接。

文件项：文件名—索引块

不支持随机访问，效率低
想要访问第i号索引块，必须先访问0~i-1号索引块，导致磁盘I/O次数太多

文件分配方式—索引分配—多层索引

建立多层索引，类似多级页表，使第一层指向第二层的索引块。

文件项：文件名—索引块(一级索引表)

假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256个索引项。
若某文件采用两层索引，则该文件的最大长度可以到256 256 1KB=64MB

假设要访问1026号逻辑块，则 1026/256=4, 1026%256=2, 先将一级索引表调入内存，查询4号表项，将4号表项对应的磁盘块即二级索引表调入内存，再查询二级索引表的2号表项即可知道1026号逻辑块存放的磁盘块号。所以访问目标数据块，需要3次磁盘I/O

采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作，相比链接方案少很多。

对于小文件，每次查询又太浪费磁盘查询次数。

文件分配方式—索引分配—混合索引

混合索引方式：多种索引分配方式的结合。既包含直接地址索引、一级间接索引(指向单层索引表)、两级间接索引(指向两层索引表)。

8个直接地址：一共对应8个磁盘块
一级间接索引：对应256个磁盘块
二级间接索引：对应256*256个磁盘块

这种结构的索引支持的最大文件长度为(8+256+256 256)1KB=65800KB

若顶级索引表还没有读入内存
访问0~7号逻辑块：两次读磁盘
访问8~263：三次
访问264~65799：四次

回顾

how 目录项内容 优点 缺点
顺序分配 连续的磁盘块 起始块号，文件长度 顺序存取速度快、支持随机访问 会产生碎片，不利于文件拓展
隐式链接 除文件的最后一个盘快外，每个盘快中都存有指向下一个盘块的指针 起始块号、结束块号 可以解决碎片问题，外存利用率高，文件扩展实现方便 只能顺序访问，不能随机访问
显式链接 建立一张文件分配表FAT，显式记录盘块的先后关系，开机后FAT常驻内存 起始块号 除了拥有隐式链接的优点外，还可以通过查询内存中的FAT实现随机访问 FAT需要占用一定的存储空间
索引分配 为文件数据块建立索引表，若文件太大，可以采用链接方案、多层索引、混合索引 链接方案记录的是第一个索引块的块号，多层和混合索引记录的是顶级索引块的块号 支持随机访问，易于实现文件的扩展 索引表需要占用一定的存储空间。访问数据块钱需要先读入索引块。若采用链接方案，查找索引块需要很多次磁盘操作

4.1.5 文件存储管理

操作系统对磁盘块的管理：

  1. 对非空闲磁盘块的管理—文件的物理结构/文件分配方式
  2. 对空闲磁盘块的管理—文件存储空间管理

文件存储空间管理

  1. 存储空间的划分与初始化
    1.1 文件卷(逻辑卷)概念
    1.2 目录区与文件区
  2. 几种管理方法
    2.1 空闲表法
    2.2 空闲链表法：空闲盘块链、空闲盘区链
    2.3 位示图法
    2.4 成组链接法

三个角度：

  1. 用什么方式记录、组织空闲块
  2. 如何分配磁盘块
  3. 如何回收磁盘块

存储空间的划分与初始化：

磁盘分区：C盘、D盘等等
存储空间的划分：将物理磁盘划分为一个个文件卷(逻辑卷、逻辑盘)
文件卷：包含目录区和文件区。目录区主要存放文件目录信息(FCB)、用于磁盘存取空间管理的信息
有的系统支持超大型文件，可支持由多个物理磁盘组成一个文件卷

存储空间管理—空闲表法

用什么方式记录、组织空闲块？
用空闲盘块表记录空闲块区间：第一个空闲盘块号，空闲盘块数

如何分配磁盘块？
与内存管理中的动态分区分配类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法为文件分配哪个区间。

如何回收磁盘块：与内存管理中的动态分区分配类似，回收时注意表项的合并问题。

存储空间管理—空闲链表法

空闲链表法：

  1. 空闲盘块链：以盘块为单位组成一条空闲链，空闲盘块中存储这下一个空闲盘块的指针
  2. 空闲盘区链：以盘区(连续的盘块为一个盘区)为单位组成一条空闲链，空闲盘区中的第一个盘块记录了盘区的长度、下一个盘区的指针

空闲盘块链：

记录：操作系统记录着链头、链尾指针
分配：链头分配，并修改空闲链的链头指针
回收：链尾回收，并修改空闲链的链尾指针
优点：适用于离散分配的物理结构，为文件分配多个盘块时需要重复多次操作

空闲盘区链：

记录：操作系统记录着链头、链尾指针
分配：可以采用首次适应、最佳适应等方法，从链头开始检索，按照算法规则找到一个符合要求的空闲盘区，或者将不同盘区的盘块同时分配给一个文件
回收：注意回收区与空闲盘区相邻

存储空间管理—位示图法

位示图：每个二进制位对应一个盘块。位示图一般采用连续的“字”表示。例如0表示空闲，1表示已分配，一个字的字长为16位，表示连续的16个磁盘的空闲情况，字中的每一位对应一个磁盘。因此可以用(字号，位号)对应一个盘块号，或者(行号，列号)
(i,j)—>b:b=n*i+j, i=b/n, j=b%n

分配：顺序扫描位示图，找到K个相邻或者不相邻的空闲磁盘块，根据字号、位号算出对应的盘块号，将相应盘块分配给文件，将相应位设置为1
回收：根据回收的盘块号计算出对应的字号、位号，将相应位设置为0

存储空间管理—成组链接法

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或者空闲链表可以太大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理

文件卷的目录区中专门用一个磁盘块作为超级块，当系统启动时需要将超级块读入内存，并且要保证内存与外存中的超级块数据一致。

超级块记录了：下一组空闲盘块数，对应的空闲块号。并且第一个空闲块的记录格式与超级块的格式相同(下一组空闲盘块数，对应的空闲块号)，即为新的“超级块”，其他空闲块则是简单的空闲块。或者说第一个空闲块是特殊的空闲块，用于套娃。
若当前“超级块”没有下一个“超级块”，第一个空闲块应该设置为某个特殊值，并且下一组空闲盘块数比正常的超级块的下一组空闲盘块数少1
超级块的下一组空闲盘块数有上限

分配：如果空闲盘块数比需求大，则直接分配，如果空闲盘块数等于需求，则复制下一级“超级块”的链接到超级块中
回收：如果可以放在超级块中，则放入超级块中，如果超级块已满，则复制超级块的链接到新的磁盘块，超级块指向新的磁盘块，此时超级块的下一组盘块数为1，将回收区放入超级块

4.1.6 文件的基本操作

操作系统向上提供的最基本的功能：

  1. 创建文件(create系统调用)
  2. 删除文件 delete
  3. 读文件 read
  4. 写文件 write
  5. 打开 open
  6. 关闭 close

创建文件

  1. 在外存中找到文件所需的空间
  2. 根据文件存放路径的信息找到该目录对应的目录文件，在目录中中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。

删除文件

  1. 找到文件名对应的目录项
  2. 确定回收文件占用的磁盘块
  3. 删除文件对应的目录项

打开文件

  1. 找到文件名对应的目录项，检查用户的操作权限
  2. 将目录项复制到内存中的“打开文件表”中。并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件。

系统的打开文件表(整个系统只有一张)：编号，文件名…，打开计数器
用户进程的打开文件表：编号，文件名，…，系统表索引号
其中打开计数器用于记录该文件被几个进程打开，可以方便地实现某些文件管理的功能。

索引号也被称为文件描述符

关闭文件

  1. 将进程的打开文件表相应表项删除
  2. 回收分配给该文件的内存空间等资源
  3. 系统打开文件表的打开计数器count减1，若count=0，则删除对应表项

读文件

从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。

写文件

将文件数据从内存写入外存

4.1.7 文件共享

文件共享：

  1. 基于索引结点的共享方式(硬链接)
  2. 基于符号链的共享方式(软链接)

基于索引结点的共享方式(硬链接)

索引结点，是一种文件目录瘦身策略。将文件名之外的其他信息放到索引结点中。这样目录项只需要文件名、索引结点指针。

索引结点中设置一个链接计数变量count，用于表示链接到本索引结点上的用户目录项数。

不同用户的目录指向同一个索引结点。
文件名可以不同。
删除文件时只是count减1.

基于符号链的共享方式(软链接)

Link类型的文件，记录共享文件的存放路径，可以简单理解成快捷方式，根据存放路径一层层找到共享文件。
如果共享文件删除，那么软链接文件还在，但是已经无法找到共享文件。
由于软链接的方式访问共享文件时需要查询多级目录，会有多次磁盘I/O，因此比较慢。

4.1.8 文件保护

文件保护：

  1. 保护文件数据的安全
  2. 口令保护
  3. 加密保护
  4. 访问控制

口令保护

口令一般存放在文件对应的FCB或者索引结点中
优点：空间开销和时间开销小
缺点：正确的口令存放在系统内部，不够安全

加密保护

使用密码对文件数据进行加密，解密后才能看到正确的数据
优点：保密性强，不需要在系统中存储密码
缺点：加密/解密需要一定的时间

访问控制

在每个文件的FCB或者索引结点中增加一个访问控制列表(Access-Control List, ACL)，该表中记录了各个用户可以对该文件执行哪些操作。

访问类型：

  • 读
  • 写
  • 执行：将文件装入内存并执行
  • 添加
  • 删除
  • 列表清单：列出文件名和文件属性

精简的访问列表：以组为单位，标记各组用户对文件的权限

4.1.9 文件系统的层次结构

从上到下依次分为：

  1. 用户接口：提供read等系统调用
  2. 文件目录系统：根据文件路径找到相应的FCB或者索引结点
  3. 存取控制模块：验证用户访问权限
  4. 逻辑文件系统与文件信息缓冲区：文件记录号—>对应的逻辑地址
  5. 物理文件系统：逻辑地址—>物理地址
    6.1 辅助分配模块：分配和回收存储空间
    6.2 设备管理程序模块：与硬件交互

4.2 磁盘

4.2.1 磁盘的结构

磁盘的结构：

  1. 磁盘、磁道、扇区的概念
  2. 如何在磁盘中读/写数据
  3. 盘面、柱面的概念
  4. 磁盘的物理地址
  5. 磁盘的分类

磁盘的盘面被划分成一个个磁道。
一个磁道又被划分成一个个扇区，每个扇区就是一个磁盘块。每个扇区存放的数据量相同

磁盘块的物理地址：(柱面号，盘面号，扇区号)

磁盘的分类：

  1. 移动头磁盘、固定头磁盘
  2. 固定盘磁盘、可换盘磁盘

4.2.2 磁盘调度算法

磁盘调度算法：

  1. 一次磁盘读/写操作所需的时间
    1.1 寻找时间
    1.2 延迟时间
    1.3 传输时间
  2. 磁盘调度算法
    2.1 先来先服务 FCFS
    2.2 最短寻找时间优先 SSTF
    2.3 扫描算法 SCAN
    2.4 循环扫描算法C-SCAN

一次磁盘读写操作所需的时间

寻找时间(寻道时间) $T_s$

  1. 启动磁道臂时间 s
  2. 移动磁头时间 m*n

$T_s=s+m*n$

延迟时间 $T_R$

旋转磁盘时间，设转速为r，平均延迟时间 $T_R=1/(2r)$

传输时间 $T_t$

磁盘读出或者写入时间，设转速，设转速为r，读或写的字节数为b，每个磁道上的字节数为N。则：

$T_t=b/(rN)$

扫描算法

磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。

SCAN算法对各个位置的磁道的响应频率不平均

LOOK算法

如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向

循环扫描算法C-SCAN

磁头只能朝某个特定方向移动时才处理磁道访问请求，返回时快速移动到起始端而不处理任何请求。为了解决扫描算法对各个位置的磁道响应频率不平均的问题。

C-LOOK算法

4.2.3 减少磁盘延迟时间的方法

延迟时间：将目标扇区转到磁头下面所花的时间。或者说读入连续地址时，尽量减少时间。

磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的延迟时间。

减少磁盘延迟时间的方法—交替编号

逻辑上相邻的扇区在物理上有一定的间隔

磁盘地址结构的设计

为什么磁盘的物理地址是(柱面号，盘面号，扇区号)，而不是(盘面号，柱面号，扇区号)

假设某磁盘有8个柱面/磁道(假设最内侧柱面/磁道号为0)，4个盘面，8个扇区。则可以用3个二进制为表示柱面，2个二进制位表示盘面，3个二进制位表示扇区。

读取连续的物理地址(00,000,000)-(00,001,111)的扇区

(盘面号，柱面号，扇区号):

(00,000,000)-(00,000,111) 转两圈可读完
(00,001,000)-(00,001,111) 启动磁头臂，移动到下一个磁道

(柱面号，盘面号，扇区号):

(000,00,000)-(000,00,111) 转两圈可读完
(000,01,000)-(000,01,111) 激活相邻盘面的磁头

读取地址连续的磁盘块时，采用(柱面号，盘面号，扇区号)的地址结构可以减少磁头移动消耗的时间。

减少磁盘延迟时间的方法—错位命名

(000,00,111)-(000,01,000) 磁头读完0号盘面的111扇区，并经过一段时间的处理后，磁头已经划过1号盘面的000扇区。

所以0号盘面的0号扇区对应的时1号盘面的111扇区

4.2.4 磁盘的管理

磁盘的管理：

  1. 磁盘初始化
  2. 引导块
  3. 坏块的管理

磁盘初始化

step1：低级格式化(物理格式化)。将磁盘的各个磁道划分为扇区。一个扇区通常可以分为头、数据区域(如512B)、尾三个部分组成。管理扇区的各种数据结构一般存放在头、尾两个部分，包括扇区校验码。
step2：磁盘分区。每个分区由若干个相邻柱面组成。
step3：逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构(如 位示图、空区分区表)

引导块

计算机开机的一系列初始化工作时通过执行初始化程序(自举程序)完成的。
初始化程序可以放在ROM(只读存储器)中。ROM的数据在出厂时就已经写入了，并且以后不能再修改。
ROM一般在出厂时就集成在主板上

完整的初始化程序放在ROM中会导致 ROM中的数据无法更改，不方便。
所以ROM只存放很小的 “自举装入程序”，完整的自举程序存放在磁盘的启动块(即引导块/启动分区)上，启动块位于磁盘的固定位置。
开机时计算机先运行“自举装入程序”，通过执行该程序就可以找到引导块，并将完整的“自举程序”装入内存，完成初始化。
拥有启动分区的磁盘称为启动磁盘或者系统磁盘

坏块的管理

坏块：坏了、无法正常使用的扇区。这属于硬件故障，操作系统是无法修复的。应该将坏块标记出来，以免错误地使用到它。

对于简单的磁盘，可以在逻辑格式化时(建立文件系统)对整个磁盘进行坏块检查，表明哪些扇区是坏扇区。比如，在FAT表中标明。(在这种方式中，坏块对操作系统不透明)

对于复杂的磁盘，磁盘控制器(磁盘设备内部的一个硬件部件)会维护一个坏块链表。磁盘出厂前进行低级格式化时就会将坏块链进行初始化。同时，会保留一些备用扇区，用于替换坏块。这种方案称为扇区备用。且这种方式中，坏块对操作系统不透明。

5. I/O设备

5.1 I/O设备

5.1.1 I/O设备的基本概念和分类

操作系统提供的功能：

  1. 处理机管理
  2. 存储器管理
  3. 文件管理
  4. 设备管理

I/O设备的基本概念和分类

  1. 什么是I/O设备
  2. 按使用特性分类
  3. 按传输速率分类
  4. 按信息交换的单位分类

什么是I/O设备

UNIX系统将外部设备抽象为一种特殊的文件，用户可以使用与文件操作系统的方式对外部设备进行操作。

Write操作：向外部设备写出数据
Read操作：向外部设备读入数据

按使用特性分类

人机交互类外部设备
存储设备
网络通信设备

按信息交换的单位分类

块设备：以块为单位，可寻址，即可以随机地读写任一块，例如磁盘
字符设备：以字符为单位，不可寻址，输入输出常采用中断驱动方式，例如键盘

5.1.2 I/O控制器

I/O设备：

  1. 机械单位
  2. 电子部件：I/O控制器(又称为设备控制器)

CPU无法直接控制I/O设备，需要通过I/O控制器(又称为设备控制器)控制设备。

I/O控制器的功能：

  1. 接受和识别CPU发出的命令：控制寄存器
  2. 向CPU报告设备的状态：状态寄存器
  3. 数据交换：数据寄存器
  4. 地址识别：用于识别哪个寄存器

I/O控制器的组成：

  1. CPU与控制器的接口
  2. I/O逻辑：负责接受和识别CPU命令，并负责对设备发出命令
  3. 控制器与设备的接口1, 2,…, i (多个接口)

备注：

  1. 一个I/O控制可能会对应多个设备
  2. 数据寄存器、控制寄存器、状态寄存器可能有多个(每个控制/状态寄存器对应一个具体的设备)，且这些寄存器都要有相应的地址，才能方便CPU操作。
  3. 寄存器编址：
    3.1 或者让这些寄存器占用内存地址的一部分，称为内存映像I/O，可以采用对内存进行操作的指令对控制器进行操作
    3.2 或者采用I/O专用地址，即寄存器独立编址，需要设置专门的指令操作控制器

5.1.3 I/O控制方式

I/O控制方式

  1. 程序直接控制方式
  2. 中断驱动方式
  3. DMA方式
  4. 通道控制方式

考察点：

  1. 完成一次读写操作的流程
  2. CPU干预的频率
  3. 数据传送的单位
  4. 数据的流向
  5. 优缺点

程序直接控制方式

完成一次读写操作的流程：轮询

  1. CPU向控制器发出读指令，设备启动，并且状态寄存器设为1(未就绪)
  2. 轮询检查控制器的状态。若是1，说明还没有准备好要输入的数据
  3. 输入设备准备好数据后将数据传给控制器，并报告自身状态
  4. 控制器将输入的数据放到数据寄存器中，并将状态改为0(已就绪)
  5. CPU发现设备已就绪，即可将数据寄存器中的内容读入CPU的寄存器中，再把CPU寄存器中的内容放入内存。

CPU干预的频率：

很频繁，I/O开始之前、完成之后都需要CPU介入，
在等待I/O完成的过程中CPU需要不断地轮询检查。

数据传送的单位：字

数据的流向：

读：I/O设备—>CPU—>内存
写：内存—>CPU—>I/O设备
每个字的读写都需要CPU帮助

优点：实现简单
缺点：CPU利用率低

中断驱动方式

引入中断机制。

CPU发出读写指令后，将等待I/O的进程阻塞，执行其他进程。当I/O完成后，控制器向CPU发出一个中断信号，CPU检测到中断信号，会转去执行中断处理程序处理该中断。处理中断的过程中，CPU从I/O控制器读一个字的数据传送到CPU寄存器，再写入主存。

备注：

  1. CPU会在每个指令周期的末尾检查中断
  2. 中断处理过程中需要保存、恢复进程的运行环境

CPU干预的频率：

每次I/O操作开始之前、完成之后需要CPU介入。
等待I/O完成的过程中CPU可以切换到别的进程执行。

数据传送的单位：字

数据的流向：

读操作：I/O设备—>CPU—>内存
写操作：内存—>CPU—>I/O设备

优点：CPU与I/O设备可以并行工作
缺点：每个字在I/O设备与内存之间的传输，都需要经过CPU。而且贫寒的中断处理会消耗较多的CPU时间

DMA方式

与“中断驱动方式”相比，DMA方式(Direct Memory Access 直接存储器存取。主要用于块设备的I/O控制)有几个改进：

  1. 数据的传送单位是块
  2. 数据的流向是 设备<—>内存，不需要CPU作为中转站
  3. 仅在传送一个或者多个数据块的开始和结束时，才需要CPU干预

开始：CPU 指明此次要进行的操作；结束：控制器完成操作后，向CPU发出中断信号

DMA控制器的组成：

  1. 主机-控制器接口
    DR 数据寄存器
    MAR 内存地址寄存器
    DC 数据计数器
    CR 命令/状态寄存器
    2

磁盘和内存之间的数据传送单位：字

CPU干预的频率：仅在传送一个或者多个数据块的开始或者结束时

数据传送的单位：

每次读写一个或者多个块(注意：每次读写的只能是连续的多个块，且这些块读入内存后，在内存中也必须是连续的)

数据流向：I/O设备<—>内存

优点：数据传输效率进一步增加，CPU与I/O设备的并行性得到提升
缺点：CPU的一条I/O指令，只能读写一个或者多个连续的数据块。

通道控制方式

通道：一种硬件，可以理解为 弱鸡版的CPU。通道可以识别并执行一系列通道指令。

  1. CPU向通道发出I/O指令。仅仅指明通道程序在内存中的位置，并指明要操作的是哪个I/O设备。之后CPU就切换到其他进程执行了。
  2. 通道执行内存中的通道程序(完整的程序在内存中，CPU仅仅发出简单的I/O指令，记录了要读入写出的数据以及对应的地址)
  3. 通道执行完规定的任务后，向CPU发出中断信号，之后CPU对中断进行处理。

CPU干预的频率：

极低，通道会根据CPU的指示执行相应的通道程序，只有完成一组数据块的读写后才需要发出中断信号，请求CPU干预。

数据传送的单位：每次读写一组数据块

数据的流向：(在通道的控制下进行)：I/O 设备<—>内存

缺点：实现复杂，需要专门的通道硬件支持
优点：CPU、通道、I/O设备可以并行工作，资源利用率很高

一个通道可以控制多个I/O控制器，一个I/O控制器可以控制多个设备。

5.1.4 I/O软件层次结构

I/O软件的层次

  1. 用户层软件
  2. 设备独立性软件
  3. 设备驱动程序
  4. 中断处理程序
  5. 硬件

其中 设备独立性软件、设备驱动程序、中断处理程序 属于 操作系统的内核部分，属于核心态，称为 I/O系统，或称 I/O 核心子系统
用户层软件 属于 用户态

用户层软件

用户层软件实现了与用户交互的接口，用户可直接使用该层提供的、与I/O操作相关的库函数对设备进行操作，比如printf函数

设备独立性软件

设备独立性软件向上提供 系统调用，例如write系统调用。用户层软件将用户请求翻译成格式化的I/O请求，并通过系统调用请求操作系统内核的服务。

Windows操作系统向外提供的一系列系统调用，但是由于系统调用的格式严格，使用麻烦，因此在用户层上封装了一系列更方便的库函数接口供用户使用(Windows API)

设备独立性软件，又称设备无关性软件。与设备的硬件特性无关的功能几乎都在都这一层实现。

设备独立性软件主要实现的功能：

  1. 向上层提供统一的调用接口(read/write等)
  2. 设备保护(权限保护)
  3. 差错管理
  4. 设备的分配与回收
  5. 数据缓冲区管理：通过缓冲技术屏蔽设备之间数据交换单位大小和传输速度的差异
  6. 建立逻辑设备名到物理设备名的映射关系：通过逻辑设备表LUT，确定逻辑设备对应的物理设备，并根据设备类型选择调用相应的驱动程序，比如 打印机1/打印机2。逻辑设备名以文件的形式存在。可以为一个系统或者一个用户设置一张逻辑设备表。

设备驱动程序

设备驱动程序：主要负责对硬件设备的具体控制，将上层发出的一系列命令(read)转化为特定设备能识别的操作。设置设备寄存器、检查设备状态。

不同I/O设备有不同的硬件特性，具体细节只有设备的厂家知道。

驱动程序一般会以一个独立进程的方式存在。

中断处理程序

当I/O任务完成时，I/O控制会发送一个中断信号，系统会根据中断信号类型找到相应的中断处理程序并执行。

中断处理程序的处理流程如下：

从控制器读出设备状态—>I/O正常结束—>是—>从设备中读入一个字的数据并经由CPU放到内存缓冲区
—>否—>根据异常原因做相应处理

中断处理程序可以与硬件直接接触

硬件

I/O控制器

5.1.5 I/O核心子系统

I/O核心子系统：包括设备独立性软件、设备驱动程序、中断处理程序，这些程序属于操作系统的内核部分，即I/O系统

功能：

  1. I/O调度
  2. 设备保护
  3. 假脱机技术(SPOOLing)
  4. 设备分配与回收
  5. 缓冲区管理(缓冲与高速缓存)

I/O软件的层次

  1. 用户层软件：假脱机技术
  2. 设备独立性软件：I/O调度、设备保护、设备分配与回收、缓冲区管理
  3. 设备驱动程序
  4. 中断处理程序
  5. 硬件

5.1.6 假脱机技术

假脱机技术

  1. 什么是假脱机技术，脱机技术可以解决什么问题
  2. 假脱机技术的实现原理
    2.1 输入井和输出井
    2.2 输入进程和输出进程
    2.3 输入缓冲区和输出缓冲区
  3. 共享打印机的原理分析

脱机

脱机：脱离主机的控制的输入/输出操作，由外围控制机进行控制。

脱机技术，缓解了CPU与慢速I/O设备之间的设备，可以提前输入或者输出到外围设备。

假脱机技术

假脱机技术，又称SPOOLing技术，用软件的技术模拟脱机技术。

输入数据：输入设备—>输入缓冲区(内存)—>输入井(磁盘)
输出数据：输出设备<—输出缓冲区(内存)<—输出井(磁盘)

在输入进程(外围控制机)的控制下，输入缓冲区用于暂存从输入设备输入的数据，之后在转存到输入井中
在输出进程(外围控制机)的控制下，输出缓冲区用于暂存从输出井送来的数据，之后在传送到输出设备上

共享打印机原理分析

独占式设备：只允许各个进程串行使用的设备
共享设备：允许多个进程同时使用的设备

当多个进程提出打印请求时，假脱机管理进程为每个进程做两件事：

  1. 在磁盘输出井中为进程申请一个空闲缓冲区(在磁盘上)，输入要打印的数据
  2. 为用户进程申请一张空白的打印请求表，填入打印请求，并将该表挂到假脱机文件队列上
  3. 当打印机空闲时，输出进程按表中的要求将打印的数据从输出井经输出缓冲区输出到打印机。

SPOOLing技术可以把一台物理设备虚拟成逻辑上的多台设备，可将独占式设备改造成共享设备

5.1.7 设备的分配与回收

设备的分配与回收

  1. 设备分配时应考虑的因素
  2. 静态分配与动态分配
  3. 设备分配管理中的数据结构
  4. 设备分配的步骤
  5. 设备分配步骤的改进方法

设备分配时应该考虑的因素

  1. 设备的固有属性
  2. 设备分配算法
  3. 设备分配中的安全性

设备的固有属性：独占设备、共享设备、虚拟设备
设备的分配算法：先来先服务等
设备分配中的安全性：安全分配方式(阻塞)、不安全分配方式(不阻塞)

静态分配和动态分配

静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源
动态分配：进行运行过程中动态申请设备资源

设备分配管理中的数据结构

一个通道可以控制多个设备控制器，每个设备控制器可以控制多个设备

设备控制表
控制器控制表
通道控制表
系统设备表

设备控制表(DCT)：系统为每个设备配置一张DCT，用于记录设备情况

设备控制表DCT 作用
设备类型 如 打印机/扫描仪
设备标示符 物理设备名，唯一
设备状态 忙碌/空闲/故障
指向控制器表的指针 每个设备由一个控制器控制
重复执行次数或时间 当重复执行多次I/O操作仍不成功，才认为此次I/O失败
设备队列的队首指针 指向等待该设备的进程队列(由进程PCB组成队列)

系统会根据阻塞原因不同，将进程PCB挂到不同的阻塞队列中

控制器控制表(COCT)：每个设备控制器对应一张COCT。

控制器控制表COCT 作用
控制器标识符 各个控制器的唯一ID
控制器状态 忙碌/空闲/故障…
指向通道表的指针 每个控制器由一个通道控制
控制器队列的队首指针 指向正在等待该控制器的进程队列(由进程PCB组成队列)
控制器队列的队尾指针

通道控制表(CHCT)：每个通道对应一张CHCT

通道控制表：通道标识符、通道状态、与通道连接的控制器表首址、通道队列的队首指针、通道队列的队尾指针

系统设备表(SDT)：记录了系统中全部设备的情况，每个设备对应一个表目

系统设备表(SDT)
表目1
表目2
表目i
表目i
设备类型(逻辑设备名)
设备标识符(物理设备名)
DCT 设备控制表
驱动程序入口

设备分配的步骤

  1. 根据进程请求的物理设备名查找SDT，物理设备名时进程请求分配设备时提供的参数
  2. 根据SDT找到设备控制表DCT，若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程
  3. 根据设备控制表DCT找到控制器控制表COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程
  4. 根据控制器控制表COCT找到通道控制表CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程
  5. 只有设备、控制器、通道三者都分配成功时，这次设备才算成功，之后便可启动I/O设备

缺点：

  1. 用户编程时必须使用 物理设备名，底层细节对用户不透明，不方便编程
  2. 若换了一个设备，则程序无法运行
  3. 若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待。

设备分配步骤的改进

建立逻辑设备名与物理设备名的映射机制，用户编程时只需要提供逻辑设备名

  1. 根据进程请求提供的逻辑设备名查找系统设备表SDT
  2. 查找SDT，找到用户进程指定类型且空闲的设备，将其分配给进程。操作系统在逻辑设备表LUT中新增一个表项
  3. 根据设备控制表DCT找到控制器控制表COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程
  4. 根据控制器控制表COCT找到通道控制表CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程

逻辑设备表LUT

逻辑设备名 物理设备名 驱动程序入口地址
/dev/打印机 3 1024

逻辑设备表LUT建立了逻辑设备名与物理设备名之间的映射关系。

逻辑设备表LUT的设置问题：一个系统一张或者一个用户一张

5.1.8 缓冲区管理

缓冲区管理：

  1. 什么是缓冲区？有什么作用？
  2. 单缓冲
  3. 双缓冲
  4. 循环缓冲
  5. 缓冲池

缓冲器及其作用

缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可以利用内存作为缓冲区

硬件寄存器：成本高、容量小、速度快，如 联想寄存器存放页表项的副本
内存缓冲区：设备独立性软件的缓冲区管理

缓冲区的作用：

  1. 缓和CPU与I/O设备之间速度不匹配的矛盾
  2. 减少对CPU的中断频率，放宽对CPU中断相应时间的限制
  3. 解决数据粒度不匹配的问题
  4. 提高CPU与I/O设备之间的并行性

单缓冲

假设某用户进程请求某种块设备读入若干块的数据。
若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区，一个缓冲区的大小就是一个块。

数据：块设备—输入T—>缓冲区—传送M—>用户进程的工作区—处理C—>CPU

消耗时间 max(T,C)+M

分析方法：假定一个初始状态，下一次达到该状态所需的时间

双缓冲

双缓冲，操作系统在主存中为其分配两个缓冲区

耗时：max(T, C+M)

单缓冲只能实现同一时刻的单通信
双缓冲能实现同一时刻的双向传输

循环缓冲区

将多个大小相等的缓冲区链接成一个循环队列

in指针，指向下一个可以冲入数据的空缓冲区
out指针，指向下一个可以取出数据的满缓冲区

缓冲池

缓冲池由系统中的缓冲区组成。三个队列、四种工作缓冲区

按使用状态分为：空缓冲队列、装满输入数据的缓冲队列(输入队列)、装满输出数据的缓冲队列(输出队列)

按扮演功能又分为：用于收容输入数据的工作缓冲区(hin)、用于提取输入数据的工作缓冲区(sin)、用于收容输出数据的工作缓冲区(hout)、用于提取输出数据的工作缓冲区(sout)

输入进程请求输入数据
从空缓冲队列中取出一块作为收容输入数据的工作缓冲区 hin，充满数据后将缓冲区挂到输入队列队尾

计算进程想要取得一块输入数据
从输入队列中取得一块冲满输入数据的缓冲区作为提取输入数据的工作缓冲区sin。缓冲区读空后挂到空缓冲区队列

计算进程想要准备号的数据冲入缓冲区
空缓冲队列—>收容输出数据的工作缓冲区hout—>输出队列

输出进程请求输出数据
输出队列—>提取输出数据的工作缓冲区sout—>空缓冲队列

hin、sout：I/O设备
sin、hout：用户进程