磁盘的结构

磁盘、磁道、扇区、盘面、柱面

• 同一个圆的磁道，被切分成了若干个扇区（一个扇区=一个磁盘块）
• 每个扇区存放的数据量相同。

• 多个盘面叠在一起组成磁盘，垂直方向上位置相同的磁道形成柱面

物理地址

• 磁盘的物理地址组成：
• 柱面号（找到是哪个磁道）
• 盘面号（找到是哪个盘面）

• 扇区号（找到是哪个扇区）

• 读取过程：

• 根据柱面号，磁头移动到指定柱面
• 激活该盘面对应的磁头
• 磁盘旋转过程中，指定的扇区就会从磁头下面划过，就可以读写了。

磁盘调度算法

一次磁盘读写需要的时间

• 寻道时间：将磁头移动到指定磁道需要的时间

• 启动磁头臂的时间

• 移动磁头找到对应磁道的时间

• 延迟时间：盘面旋转，使得磁头定位到扇区所需时间

• 传输时间：从磁盘读出/写入到磁盘 所需的时间

磁盘调度算法

先来先服务

• 按照进程发起的访问磁盘请求的先后顺序，不加调整的直接进行磁盘读写
• 优缺点：
• 请求访问的磁道比较集中的话，性能尚可。类似于随机读写。

最短寻找时间优先

• 类似贪心算法，当有多个读写请求到达时，每次都选当前寻道时间最短的读写请求处理。

• 优缺点：

• 局部最优并不能保证总体最优。

• 有可能出现饥饿现象，目前离得远的磁道，可能会被源源不断到来的更近的磁道的请求所顶掉。

扫描算法（电梯算法）

• 规定只有当磁盘移动到最外侧/内侧时，才允许向相反方向移动。

• 优缺点：

• 不会产生饥饿现象
• 当移动到最外侧的路径中没有请求的话，移动到最外侧的路程是浪费的
• 各个位置的磁道，访问响应频率不均匀。

LOOK算法

• 改进电梯算法的缺点1：在电梯算法的基础上，如果在磁头移动方向上已经没有别的请求。就可以立刻改变磁头移动方向。
• 优点：相比电梯算法，寻道时间缩短。

C-SCAN（循环扫描）算法

• 改进电梯算法的缺点2：规定只有磁头向某个方向移动时才会处理请求；这个方向移动到末端就直接快速返回另一端起点，不处理任何请求。
• 优缺点：
• 还是存在：当移动到最外侧的路径中没有请求的话，移动到最外侧的路程是浪费的的缺点

C-look算法

• 结合look和c-scan特点：磁头移动方向上如果没有请求的话，就掉头返回，并且不用返回到另一端，而是返回到距离另一端最近的有磁盘访问请求的位置即可。

减少磁盘延迟时间的算法

背景

• 延迟时间是指：目标扇区转到磁头下面所花的时间。
• 机械原理理解：磁头读取完一块扇区的内容后，需要一小段时间处理；但是盘面又在不停的旋转。所以，如果将逻辑相邻的扇区，安排成物理相邻的话，则读入1号扇区后并不能马上读入2号扇区，得等盘片重新再转到2号才行。

交替编号

• 逻辑相邻的扇区，物理上设计成间隔一定的扇区，磁头处理时间过去，盘面就正好转到逻辑上的下一个扇区，节省时间。

磁盘的管理

磁盘的初始化

• 低级格式化（物理格式化）

• 将磁盘的各个磁道，划分为扇区

• 每个扇区由头、尾、数据区组成，头尾回放管理扇区的数据（奇偶校验、CRC校验等）

• 磁盘分区

• 将磁盘分区，每个分区由若干个柱面组成

  

• 逻辑格式化

• 创建文件系统：包括文件系统根目录、初始化存储空间管理的数据结构（位示图、空闲分区表等）

引导块

• 计算机启动时，需要进行一些初始化工作（CPU、memory的初始化），这些初始化工作是通过初始化程序（自举程序）来完成的。
• 自举程序可以放在ROM中，ROM的数据出厂就集成在主板上写死了，不能更改；所以不方便对自举程序进行更新。
• 所以现在一般都在ROM中只放一小段的“自举装入程序”，完整的自举程序存放在磁盘上的启动块（即引导块/启动分区）上，启动块放在磁盘的固定位置上。
• 开机时，先运行ROM上的自举装入程序，通过该程序找到磁盘上的引导块，并将其上的完整自举程序读入内存，完成初始化。

坏块的管理

• 坏块是磁盘块物理损坏，系统无法修复，只能标记出来，不要分配。
• 简单磁盘可以采用：逻辑格式化时，对磁盘进行坏块检查，标明坏扇区，在FAT表上注明。
• 复杂磁盘可以采用：磁盘控制器（磁盘内部的一个硬件），来维护一个坏块链表。

IO管理

IO设备

• 处理机、存储器、文件都属于是计算机内部设备，IO设备是外部设备，OS也负责管理IO设备

• UNIX系统将IO设备抽象成特殊文件，用户可以使用与文件操作相同的方式对外部设备进行操作。

分类

按用途：

• 人机交互设备
• 存储设备
• 网络设备

按数据交换方式：

• 块设备（磁盘）
• 传输速率高，可寻址，可随机读写
• 字符设备（鼠标键盘）
• 慢、不可寻址、常采用中断驱动的方式来输入输出

IO控制器

介绍

• CPU无法直接控制IO设备的物理部件，因此IO设备还需要有一个电子部件，通常是一块插入主板扩充槽的电路板。作为CPU和IO设备的中介，实现对设备的控制。
• 功能
• 接收、识别CPU发出的命令（控制器中设立控制寄存器，存放命令和参数）
• 向CPU报告设备的状态（控制器中设立状态寄存器，用于记录设备的状态）
• 数据交换（控制器中设立数据寄存器，用于暂存CPU和设备之间交换的数据）
• 地址识别（类似于内存的地址，这些寄存器也被标记了特定的地址，控制器通过CPU提供的地址来识别CPU读写的是哪个寄存器）

组成

• CPU的地址线，指明需要操作的设备；控制线，指明具体的指令。
• 具体数据放到数据寄存器中；命令的参数放到控制寄存器中；设备状态放在状态寄存器中。

注意：

• 一个IO控制器可能对应多个设备，所以可能也有多个寄存器。

• 多个寄存器都要编址，才方便CPU操作。

• 编址方式1：让这些寄存器顺着内存编址往下编，称为内存映像IO

• 编址方式2：寄存器独立编址

  

IO控制方式

程序直接控制

• Key word：CPU轮询控制寄存器
• 以读IO为例：
• CPU向IO控制器中的IO逻辑发起读指令，IO逻辑对设备发起读请求。同时设置控制寄存器状态为未就绪（busy）
• 由于IO设备速度比CPU慢太多了，CPU就一直轮询状态寄存器。
• IO设备准备好数据后就通过IO逻辑将数据放到数据寄存器中；同时状态寄存器设为0，表示就绪。

• CPU轮询到状态寄存器0，就从数据寄存器中读出数据，放到CPU的寄存器中，再放入内存。

• CPU干预频率：需要不断轮询检查

• 数据传送单位：一个字（CPU一次操作处理实际位数的多少，字的位数叫字长，如32位 64位等）
• 数据流向：
• 读：IO设备-CPU-内存
• 写：内存-CPU-IO设备
• 优缺点：
• 优点：程序简单
• 缺点：CPU和IO只能串行工作，CPU长期忙等，利用率低。

中断驱动方式

中断机制：

• CPU发出读写命令后，将等待IO的进程阻塞；转而到别的进程执行。

• 当IO完成后，控制器向CPU发出中断信号，CPU检测到信号后，保存当前进程现场。

• 转而去执行中断程序，处理该中断；CPU从IO控制器读出一个字的信息，放到CPU寄存器，再放入内存。

• CPU恢复之前IO阻塞的进程环境，继续执行。

特点：

• CPU在每个指令周期的末尾检查中断。

• 中断也要时间开销，来保存恢复运行环境。

• CPU干预频率：CPU和IO设备可以并行工作

• 数据传送单位：一个字
• 数据流向：
• 读：IO设备-CPU-内存
• 写：内存-CPU-IO设备
• 优缺点：
• 优点：CPU IO可以并行工作
• 缺点：每次只传送一个字，数据都得经过CPU，频繁的中断处理消耗较多CPU时间。

直接存储器读取

• 数据的传送单位是：块

• 数据不再需要CPU作为中转，会是从IO设备直接调入内存。

• 仅在一个或多个数据块开始和结束时，才需要CPU干预。

工作流程

DMA控制器

• CPU干预的频率：仅在传送一个或多个数据块的开始和结束时才需要CPU干预
• 数据读写单位：一个或多个块。（多个块的情况下，IO只能是读写连续的多个块，而且都要存放在连续的内存中）
• 数据的流向：io设备 - 内存，不需经过CPU
• 优缺点
• 优：数据传输单位是块，CPU效率提高；数据不需要经过CPU，CPU io并行性得到提高。
• 缺：如果需要读取在外存离散的数据块，或者要存放到内存中离散的地址中，就需要CPU发出多个IO指令，需要多次中断处理。

通道控制方式

• CPU干预的频率：极低，只需要对通道程序发出指令，完成一组数据块的读写后才需要发送中断信号，请求CPU干预。
• 数据读写单位：一组数据块
• 数据流向：IO - 内存
• 优缺点
• 优点：CPU、通道、IO设备可以并行工作，效率高
• 缺点：需要专门硬件支持

IO软件层次结构

用户层软件

• 提供一些与IO操作相关的库函数,对设备进行操作。（e.g. printf("Hello world")）

• 用户层软件通过将用户请求翻译成格式化的IO请求，通过系统调用请求操作系统内核服务。

[!info] Windows API
Windows中，OS提供了一些系统调用，但是由于系统调用的格式严格，不容易直接使用；因此在用户层向上又封装了一层更方便的库函数供用户使用（Windows API）

设备独立性软件

• 实现与设备无关的一些接口
• 向上提供统一的调用接口（read/write等）
• 对设备的保护（设备被看作一种特殊的文件，也具有用户访问权限）
• 差错处理
• 设备分配与回收
• 数据缓冲区管理（通过缓冲技术，屏蔽设备之间数据交换单位大小和传输速度的差异）
• 建立逻辑设备名和物理设备名的映射关系；根据设备类型选择相应的驱动程序。
  • 设备独立性软件通过“逻辑设备表”（LUT）来确定逻辑设备对应的物理设备，并找到该设备的驱动程序入口地址。

设备驱动程序

• 不同设备内部的硬件特性不同，这些特性只有厂家了解，因此厂家必须提供与设备相对应的驱动程序、CPU执行驱动程序提供的指令来完成对硬件的控制。
• 驱动程序主要负责对硬件设备的具体控制，将上层发出的命令转化为特定设备可以识别的操作，如设置设备寄存器、检查设备状态等。

中断处理程序

• 硬件设备完成IO操作后，IO控制器会发送一个中断信号，操作系统根据中断信号的类型判断下一步操作。

IO核心子系统

• 包括设备独立性软件、设备驱动程序、中断处理程序；他们属于操作系统内核部分，即IO子系统
• IO核心子系统主要完成以下功能：

IO调度

• 用某种算法确定各个IO请求的处理次序

设备保护

• 设备在UNIX系统中也是文件，也有FCB来控制权限，用户访问某个设备时，也会根据FCB中的权限信息来鉴权。

假脱机技术

• 脱机技术
• 背景：CPU和输入输出设备的速度严重不匹配
• 解决：在批处理发展阶段，引入了脱机技术。在外围控制机的控制下，打孔纸带输入设备的数据先被传送到磁带上，之后主机从磁带上读入数据，更快了；输出过程类似。

• 脱机就是脱离了主机的控制的输入输出操作

• 假脱机技术

• SPOOLing技术：用软件方式模拟脱机技术。

• 首先，需要在磁盘上开辟出“输入井”和“输出井”

• 在内存中有输入输出缓冲区，在输入输出进程的控制下，缓冲区用于暂存从设备的IO，再转存到输出井中。

​

• 共享打印机原理分析
• 首先，打印机本质是独占设备，但是可以通过假脱机技术改造成共享设备，即多个进程可以同时请求。
• 当用户进程申请使用打印机时，系统会接受请求，但并不是真正把打印机分配给他们，而是由假脱机技术管理进程来调配：
  • 在磁盘输出井中，为进程申请一块空闲缓冲区，将要打印的数据发送过去
  • 给用户进程申请一张空白的打印请求表，将打印请求填入，指明输出数据的存放位置。
  • 将打印请求表挂到假脱机文件队列上，当打印机空闲时，输出进程就从队列队头取出请求表，找到磁盘输出井上的数据，发送到内存缓冲区，再到打印机进行打印。

缓冲区管理

缓冲区

缓冲区的作用：

• 解决速度不匹配

缓冲区写满或被取走后，才会产生中断信号，打断CPU。减少打断CPU次数。

• 解决数据粒度不匹配

• 例如输出进程每次生成一块数据，但是IO设备每次只能输出一个字符。

• 提高并行性

单缓冲

• 用户进程从某种块设备读入数据，若采用单缓冲的策略，OS会在内存中为其分配一个缓冲区。
• 缓冲区非空，就不能继续往里写，得等到读空了才能写；缓冲区空了，得完全写满后，才能开始读取。

双缓冲

• 用户进程从某种块设备读入数据，若采用单缓冲的策略，OS会在内存中为其分配两个缓冲区。

• 两台相互通信的机器，采用双缓冲区，可以实现双向数据传输：

循环缓冲区

• 将大小相等的缓冲区组成循环队列

缓冲池

• 缓冲池由系统中共用的缓冲区组成。

• 按使用状况可以分为：空缓冲队列、装满输入数据的缓冲队列、装满输出数据的缓冲队列

  

• 按功能不同，可分为：用于接收输入数据的（hin）、用于接收输出数据的（hout）、用于提取输入数据的（sin）、用于提取输出数据的（sout）

  

• 如果输入进程请求输入数据

• 从空缓冲队列取出一块，作为hin，开始接收输入数据，写满之后，挂到输入队列队尾。
• 如果用户进程需要取得一块输入数据
• 从输入队列队头取出一块，作为sin，进程读完数据（将数据转移到进程的工作区当中）之后，缓冲区挂回到空缓冲区队列。
• 如果用户进程将新鲜出炉的数据放入缓冲区
• 从空缓冲队列取出一块，作为hout，开始接收数据，写满之后，挂到输出队列队尾。
• 如果输出进程需要输出数据
• 从输出队列队头取出一块，作为sout，缓冲区数据被读完之后，挂回到空缓冲队列队尾。

固态硬盘

结构

• HDD读写是以扇区为单位的，SSD读写是以页为单位。
• SSD擦除数据是以块为单位。
• 一个页写了数据就不能再写了；如果还向往这个页里面写，就要把整个块全擦除才行。这时会将其他页的数据复制到另一个擦除过的块里面，再在新块的页里面写入新+旧的数据。最后再把旧的块擦除掉。这样物理地址就变了，闪存翻译层会重新映射。