IO管理概述

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

按使用特性分类：

人机交互类外设：鼠标、键盘、打印机
- 传输速率比较慢
存储设备：硬盘、光盘
- 传输速率比较快
网络通信设备：光猫
- 速度介于两者中间

按传输速率分类：

低速设备：几个-几百个KB/s。例如鼠标键盘
中速设备：几千个-上万个KB/s。例如激光打印机。
高速设备：几千KB-几MB/s。例如磁盘。

（重要）按信息交换的单位分类：

块设备：例如磁盘。传输速率高，可以寻址，支持随机读写。
字节设备：例如鼠标键盘。传输速率慢，不可以寻址，使用中断驱动方式。

I/O控制器——设备控制器

功能：

接受和识别来自CPU的命令：设置控制寄存器存放CPU的命令和参数
向CPU报告设备的状态：设置状态寄存器存放空闲or忙碌
数据交换：设置数据寄存器暂存要输入的数据
地址识别：通过CPU提供的地址判断CPU要读写哪一个寄存器

组成：

CPU和控制器的接口：包括数据、控制和状态寄存器。
IO逻辑：接收和识别CPU的命令，对设备发出指令。
控制器和设备的接口：控制器和设备的通信。

两种编址方式：

内存映像I/O：
1. 示意图：
2. 优点：可以采用对内存的操作指令来对控制器进行操作。
寄存器独立编址：
1. 缺点：需要专门设置指令来实现对控制器的操作。

IO四种控制方式

程序直接控制方式

核心：CPU发出指令后，轮询检查状态寄存器。
读写流程：
- CPU-->IO：发送读指令。
- 控制器启动：设置状态寄存器为1表示未就绪。
- CPU：轮询检查状态寄存器的数据，如果为1表示设备忙碌
- I/O设备准备好数据：将数据传送给控制器并报告自身状态。
- 控制器：将数据放到数据寄存器，将状态设置为0表示已就绪
- CPU：发现设备已就绪，将数据寄存器中的内容读入CPU，再把CPU内容放入内存
- 继续发送下一条读指令
三个核心问题：
- CPU干预频率：很频繁，需要不断轮询检查，是本方式的最大缺点。
- 数据传送单位：每次读写1个字。
- 数据流向：每个字的读写都需要CPU的帮助
优缺点：
- 优点：实现简单。软件就可以实现。
- 缺点：CPU和I/O只能串行工作，CPU需要一直轮询检查。

中断驱动方式

核心：CPU发出命令后阻塞进程，IO完成后向CPU发出中断请求。
读写流程：
- CPU：发出读写命令，将这个进程阻塞，切换到别的进程运行。
- I/O：完成后发出中断信号，CPU检测到中断信号后保存当前进程运行环境信息，转而去处理中断。
- 处理中断时，CPU向I/O控制器读一个字的数据传送到CPU寄存器，然后写入内存
- CPU恢复等待I/O的进程的运行环境继续执行
注意：
- 中断检查时机：CPU会在每个指令周期的末尾
- CPU要保存和恢复进程的运行环境，有时间开销，频率太高会降低性能
三个核心问题：
- CPU干预频率：实现了CPU和I/O并行工作的特点
- 数据传送单位：每次读写一个字。
- 数据流向：必须经过CPU。
主要优点和缺点：
- 优点：CPU和IO可以并行工作，利用率提升。
- 缺点：必须经过CPU，频繁中断会消耗CPU时间。

DMA方式

DMA（Direct Memory Access）：通过系统总线将内存和IO直接连接到一起。

寄存器：数据寄存器（DR）、内存地址寄存器（MAR）、数据计数器（DC）——剩余要读写的字节、状态寄存器（CR）

三个核心问题：
- CPU干预频率：仅仅在开始和结束的时候需要经过CPU
- 数据传送单位：每次读写一个或者多个块，只能是连续的块
- 数据流向：无需经过CPU
数据传输流程：
- CPU：给定要进行的（操作+数据量+数据放入的内存地址+数据的外存地址）
- 控制器：根据CPU的信息完成读写，完成后向CPU发送中断信号
优缺点：
- 优点：数据传输效率的提升。CPU和IO的并行性得到提升。
- 缺点：每次发出一条IO指令。只能读写一个或者多个连续的数据块。

通道控制方式

流程：
- CPU向通道发出IO指令：通道程序在内存的位置+哪个IO设备；CPU切换到其它进程执行
- 通道执行通道程序（其中指明了要读入和写出的数据以及位置信息）
- 通道执行完规定的任务后，向CPU发出中断信号，CPU对信号处理。
通道：一种硬件，可以识别一系列的通道指令，与CPU共享内存。
三个核心问题：
- CPU干预频率：非常低，根据CPU指示，完成一组数据块的读写后才发出中断信号
- 数据传送的单位：每次读写一组数据块。
- 数据的流向：IO和内存，不经过CPU
缺点和优点：
- 缺点：实现复杂，要硬件支持
- 优点：资源利用率很高。CPU、I/O、通道之间可以并行工作。

总结

I/O软件的层次结构

IO软件层次从上到下可以分为，其中中间三层属于IO核心子系统。

用户层软件
设备独立性软件
设备驱动程序
中断处理程序
硬件

用户层

库函数：实现了与用户交互的接口。
系统调用处理层：将用户请求翻译为格式化的I/O请求，通过系统调用请求OS内核的服务。
IO应用接口
- 字符设备接口：get/put系统调用。同字符设备读/写1个字符。
- 块设备接口：
  - read/write系统调用。向块设备的读写指针位置读/写多个字符。
  - seek系统调用。修改读写指针的位置。
- 网络设备接口：又叫做 socket接口
  - socket系统调用。创建一个网络套接字。需要指定协议。
  - bind系统调用。将套接字绑定到某个端口。
  - connect系统调用。从套接字读/写数据。
两种IO
- 阻塞IO：进程发出IO调用后需要阻塞等待。
  - 例如：get从键盘读取字符。
- 非阻塞IO：进程发出IO调用后，系统调用可以迅速返回，进程无需等待。
  - 例如：write往磁盘写数据。

（重点）设备独立性软件

描述：实现与设备硬件无关的功能。
功能：
- 提供系统调用。
- 实现设备保护，类似文件保护，即访问权限。
- 差错处理：对错误进行处理。
- 设备的分配和回收。
- 数据缓冲区管理：屏蔽设备之间的数据交换大小和传输速度差异。

OS采用两种方式管理逻辑设备表LUT

第一种方式：整个系统设置一张LUT。类似于单级目录结构。
第二种方式：每个用户设置一张LUT。类似两级目录结构。

设备驱动程序

描述：负责对硬件的具体控制。包括设置寄存器检查设备状态等。
功能：
- 不同设备的内部硬件特性不同，厂家必须提供与设备相应的驱动程序。
- 驱动程序一般会以一个独立进程的方式存在。

中断处理程序

描述：需要直接和硬件打交道。
功能：I/O会发送中断信号，系统根据中断信号类型找到中断处理程序并执行。

设备独立性软件

设备独立性软件层的负责的内容：

I/O调度：用某种算法确定一个好的顺序来处理各种IO请求。如磁盘、打印机等。
设备保护：不同用户对各个文件有不同访问权限，根据FCB来判断是否有相应的访问权限。
设备分配与回收
缓冲区管理
SPOLLing技术：也叫做假脱机技术，在用户层但是也在这章节进行讲解。

SPOLLing技术

什么是脱机技术：

背景：批处理阶段引入了脱机技术，使用磁带完成。
脱机：指的是脱离主机的控制下进行I/O操作。
目的：将独占设备改造成共享设备。
- 独占式设备：只允许各进程串行使用的设备，比如打印机。
- 共享设备：允许多进程并发执行。
细节：将低速IO设备上的数据传送到高速磁盘上。
外围控制机：慢速输入设备的数据先被送到更快速的磁带，CPU从磁带读取。

过程：多用户提出使用打印机的请求后，会由假脱机管理进程答应请求。

在磁盘输出井中为进程申请一个空闲缓冲区，并将数据放入。
申请一张空白的打印请求表，将打印请求写入表中，再将该表挂到假脱机文件队列上。
输出进程从打印请求中取出任务，并根据表中的信息将数据从输出井传送到输出缓冲区，然后输出到打印机进行打印。

设备的分配与回收

设备分配时考虑的问题

设备的固有属性：
- 独占设备：打印机。
- 共享设备：磁盘。
- 虚拟设备：使用SPOLLing技术改造后的独占式设备。
设备的分配算法：FIFO、SJF、优先级等。
设备分配中的安全性
- 安全分配方式：分配设备后就进程阻塞，IO完成才将进程唤醒。
  - 优点：破坏了“请求和保持”条件，不会死锁。
  - 缺点：CPU和IO只能串行工作，系统资源利用率低。
- 不安全分配方式：进程发出IO请求后，系统为其分配IO设备。进程可以继续执行，发出新的IO请求。某个IO请求得不到满足才阻塞。
  - 优点：CPU和IO可以并行。
  - 缺点：可能发生死锁。
静态分配：运行前分配所有资源。破坏了请求并保持。
动态分配：进程运行过程中动态申请设备。

设备分配中的数据结构

设备、控制器和通道之间的关系：

设备控制表DCT：每个设备一张。

设备类型：如打印机。
设备标识符：物理设备名。唯一。
设备状态：BUSY...
指向控制器表的指针
重复执行次数或者时间，可以判断失败
设备队列的队首指针——指向真正等待该设备的进程队列。

控制器控制表COCT：每个设备控制器都回对应一张COCT。

控制器标识符：唯一ID。
控制器状态：BUSY...
指向通道表的指针
控制器队列队首指针
控制器队列队尾指针

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

通道标识符：唯一ID
通道状态：BUSY...
与通道连接的控制器表首地址
通道队列的队首指针
通道队列的队尾指针

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

包含：设备类型、设备标识符、设备控制表、驱动入口

设备分配的步骤

根据进程请求的物理设备名查找系统设备表SDT。
根据系统设备表SDT找到设备控制表DCT。
1. 如果设备忙碌则将PCB挂到设备等待队列中。
2. 不忙碌则将设备分配给进程。
根据DCT找到COCT。
1. 如果控制器忙碌则将PCB挂到控制器等待队列中。
2. 不忙碌则将控制器分配给进程。
根据COCT找到CHCT
1. 如果通道忙碌则将PCB挂到通道等待队列中
2. 不忙碌则将通道分配到进程。

只有设备、控制器、通道三者都分配成功时，这次分配才算成功。

缺点：

用户编程必须使用物理设备名，底层对用户不透明。如果换了物理设备程序无法运行。
如果进程请求的物理设备正在忙碌，即使有同类型的其它设备，进程也必须阻塞等待。

设备分配步骤的改进方法：

逻辑设备表LUT建立了逻辑设备名和物理设备名之间的映射。
进程请求使用逻辑设备名（其实就是设备类型）查找SDT。
其它类似

缓冲区管理

什么是缓存区：存储区域，由寄存器或者内存组成。设备独立性软件负责组织和管理浙西而缓冲区。
缓冲区的作用：
- 缓和CPU和IO之间的速度不匹配问题
- 减少CPU中断频率，放宽对CPU中断相应时间的限制
- 解决数据粒度不匹配的问题
- 提高CPU和IO设备之间的并行性

单缓冲

描述：OS在主存中分配一个缓冲区。一个缓冲区的大小就是一个块。
- 缓冲区非空：无法冲入数据，只能从缓冲区讲数据传出。
- 缓冲区为空：才能冲入数据，而且必须充满。
两种初始状态：处理一块数据平均耗时 Max(C,T)+M

双缓冲

描述：主存中分配两个缓冲区。
两种初始状态：假设初始状态为工作区空，其中一个缓冲区满，另一个缓冲区空
- 处理一个数据块的平均耗时 MAX(T,C+M)
两个互相通信的机器设置双缓冲区，则同一个时刻可以实现双向的数据传输。

缓冲池

将多个大小相等的缓冲区链接为一个循环队列。
三个队列：
- 空缓冲队列
- 装满输入数据的缓冲队列
- 装满输出数据的缓冲队列
四种缓冲工作区：
- 用于收容输入数据工作缓冲区hin
- 用于提取输入数据的工作缓冲区sin
- 用于收容输出数据的工作缓冲区hout
- 用于提取输出数据工作缓冲区sout

磁盘管理

磁盘结构

磁盘、磁道、扇区
- 磁盘盘面上的每个圈就是一个磁道。
- 磁道被划分为扇区，每个扇区数据量相同，如1KB。
- 最内侧的扇区面积最小，但是数据量相同，因此数据密度最大。
如何在磁盘中读写数据
- 磁头由磁头臂带动到要读写的磁道。
- 磁盘会转动，让目标扇区从磁头下方划过，完成对扇区的读写操作。
盘面、柱面的概念
- 磁盘有多个盘面，按照圆柱的母线方向。
- 一个盘片可能会有两个盘面，正负两面。
- 所有磁头是连着同一个磁臂的，只能共进退。
- 所有盘面中相对位置相同的磁道组成柱面。
磁盘的物理地址
- 可以用（柱面号，盘面号，扇区号）来定位某个位置，读取一个块。
  - 根据柱面号移动磁臂，磁头指向柱面。
  - 激活指定盘面的磁头。
  - 磁盘旋转，读取指定扇区的数据。
磁盘的分类
- 磁头是否可以移动
  - 活动头磁盘——磁臂可以来回伸缩带动磁头定位磁道。
  - 固定头磁盘——磁头不可以移动。
- 磁盘是否可以更换
  - 固定盘磁盘
  - 可换盘磁盘

磁盘调度算法

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

寻道时间Ts：磁头移动到指定磁道需要花费时间。
- 操作系统的磁盘调度算法会直接影响寻道时间
- 启动磁头臂时间s
- 移动磁头时间。假设n条磁道，跨一个磁道消费m。
- 那么Ts = s + mn
延迟时间Tr：旋转磁盘定位到扇区的时间。
- 转速是r，Tr = (1/2) x (1/r) = 1/2xR
- 典型转速：5400转/min，7200转/min
传输时间Tt：从磁盘读出或者向磁盘写入到时间
- 转速r，字节数b，每个磁道有N个字节，Tt = (1/r)x(b/N)

总的平均存取时间 Ta = Ts + 1/2r + b/(rN)

磁盘调度算法

FCFS

思路：根据进程访问磁盘的先后顺序进行调度。
优点：公平；如果磁道集中的话还行。
缺点：如果大量进程竞争，请求访问的磁盘很分散，性能很差。

最短寻找时间优先（SSTF）

思路：优先处理和当前磁头最近的磁道。可以保证每次寻道时间最短，但无法保证总体时间最短。
优点：性能较好，平均寻道时间短
缺点：可能产生饥饿现象。即一直处理近的请求而不处理远的请求。

扫描算法（SCAN）

思路：规定只有磁头异动到最外侧磁盘才能向内移动，移动到最内测才能向外移动。这种思路很像电梯，也叫做电梯算法。
优点：平均寻道时间较短，不会产生饥饿现象。
缺点：
- 只有到达最边上的磁道才能改变磁头移动方向。可能不需要移动到最右边。
- 对各个位置的磁道响应频率不平均。

LOOK算法

解决了SCAN算法的第一个缺点。
思路：只有到达最边上的磁道才能改变磁头移动方向。磁头移动方向上没有别的请求，就可以立即改变磁头移动方向。（边移动边观察所以叫LOOK）
优点：相比SCAN进一步缩短平均寻找长度

循环扫描算法—C-SCAN算法

解决了SCAN算法的第二个问题。
思路：只有磁头朝着某个特定方向移动才处理磁道访问请求，返回时直接快速移动到开始端而不进行任何处理。
优点：对于各个磁道的响应频率很平均。
缺点：只有到达最右边才会改变方向。并且实际上不需要返回最边缘。

C-LOOK算法

思路：磁头移动的方向没有磁道访问，就让磁头返回到有磁道访问的位置而不是直接返回边缘。
优点：寻道时间进一步缩短。

减少磁盘延迟的方法

背景：磁头读入一个扇区数据后需要小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入连续的磁盘扇区可能需要很长的延迟时间。
交替编号方式：让逻辑上相邻的扇区在物理上有一定间隔。可以使得读取连续的逻辑扇区所需要的延迟时间更小。
磁盘地址结构的设计——为什么柱面号在盘面号之前：读取连续的磁盘块的时候。可以减少磁头移动消耗的时间，不太好理解。
错位命名：其实和交替的差不多的原理，不过是针对不同盘面的同一个扇区的。还是因为读取完一个扇区后磁头需要有一段时间来处理数据，从而更好进入下一个扇区。

磁盘的管理

磁盘初始化
- 第一步，低级格式化：划分扇区。一个扇区=头，尾，数据区域（512B）
  - 管理扇区所需的数据结构存放到头尾中。
  - 包括：扇区校验码等。
- 第二步，将磁盘进行分区。每个分区由若干柱面组成。
- 第三步，逻辑格式化。创建文件系统，包括根目录、创建文件系统所需要的数据结构等。
引导块：
- 初始化程序放到ROM中，ROM在出厂就写好了无法再修改。
- 读取ROM的程序，执行程序完成初始化工作。
- 现代OS中ROM只是存放很小的初始化程序，完整的初始化程序放到磁盘的引导块。启动块位于磁盘的固定位置。
- 拥有启动分区的磁盘叫做系统盘，比如C盘。
坏块的管理：
- 坏块指的是硬件故障的块。
- 简单的磁盘，在逻辑格式化的时候，可以在FAT表上标明。对OS不透明。
- 复杂的磁盘，磁盘控制器会维护坏块链表，出厂前会在物理格式化的出事后对坏块链表进行初始化。会保留一些备用扇区，替换坏块。称之为扇区备用。

固态硬盘SSD

原理：基于闪存技术，EEPROM。
组成：
- 闪存翻译层：负责翻译逻辑块号，找到对应的Page。
- 存储介质：多个闪存芯片。每个芯片包含多个块，每个块包含多个Page。
读写性能特性：
- 以Page为单位读写，相当于磁盘的扇区。
- 以Block为单位擦除，擦干净的块每一页都可以写一次，读无限次，相当于磁盘的磁道。
- 支持随机访问，给定逻辑地址，闪存翻译层可以翻译为物理地址。
- 读快、写慢。要写的页如果有数据，则不能写入。需要将块内其它页全部复制到一个新的块中，再写入新的页。
与机械硬盘相比的特点：
- SSD读写速度快，随机访问性能高，用电路控制访问位置。机械硬盘通过移磁臂访问位置，有寻道时间和旋转延迟。
- SSD安静无噪音，耐摔抗震，能耗低，造价高
- SSD的一个块被擦除次数过多可能会坏掉，而机械硬盘的扇区不会因为写的次数太多而坏掉。
磨损均衡技术：
- 思想：将擦除平均到各个块上，提高使用寿命。
- 动态磨损均衡：写入数据后优先选择累计擦除次数少的新闪存块。
- 静态磨损均衡：SSD监测并自动进行数据分块和迁移，让老旧的内存块承担读为主的存储任务，新的闪存块承担更多写任务。