第五章 输入输出系统·
5.1 I/O硬件基本原理·
I/O设备分类·
传输速度：低速中速高速
信息交换单位：块设备和字符设备
共享属性：独占设备，共享设备，虚拟设备
5.2 I/O软件基本原理·
I/O控制技术·
程序控制I/O(PIO,Programmed I/O)·
轮询或查询方式IO
CPU代进程向IO模块发出指令，之后忙等，直到操作完成进程继续执行
中断驱动方式(Interrupt-driven I/O)·
I/O操作结束后由设备控制器主动通知程序结束信息，不用轮询
外设数据处理时CPU不需等待，但是每输入输出一个数据CPU都要中断，浪费CPU时间
直接存储访问方式(DMA, Direct Memory Access)·
直接存储器访问方式
由一个专门的控制器完成数据从内存到设备或者设备到内存的传输工作，是数据块的传输
优点·
- CPU只干预I/O操作的开始和结束， 而当中的数据读写过程无需CPU控制，适于高速设备
缺点·
- 数据传送的方向、存放数据的内存地址及传送数据的长度等都由CPU控制，占 用了CPU时间。
- 每个设备占用一个DMA 控制器，当设备增加时，需要增加新的DMA 控制器
通道技术（Channel）·
与DMA几乎一样
通道是一个特殊功能的处理器，有自己的指令体系，专门负责数据输入输出的传输控制，与CPU分别使用内存，实现运算与IO的并行
执行一个通道程序可完成几组IO操作，减少了CPU干预，但费用较高
可同时控制多种设备，区别于DMA只能控制一台或少数几台同类设备
缓冲技术·
匹配CPU和外设不同处理速度，减少CPU中断次数，提高并行性
- 单缓冲： 1个缓冲区，CPU外设轮流使用
- 双缓冲： 2个缓冲区，CPU和外设可以连续处理，但要求速度相近
- 环形缓冲：生产者—消费者问题
缓冲池·
缓冲区队列：
- 空闲缓冲区
- 输入缓冲区
- 输出缓冲区
设备分配·
对进程使用外设过程的管理。
两个做法：
- 在进程间切换使用外设，如键盘和鼠标；
- 通过一个虚拟设备把外设与应用进程隔开，只由虚拟设备来使用设备。
数据结构·
- 设备控制表 DCT 每个设备一张
- 控制器控制表 I/O控制器的配置和状态
- 通道控制表 每个通道一张
- 系统设备表 系统内一张 记录所有设备状态和对应的控制表入口
单通道IO设备系统分配·
一个设备对应一个控制器，一个控制器对应一个通道
多通道IO系统设备分配·
一个设备与几个控制器相连，一个控制器与几个通道相连
假脱机技术SPOOLing·
把独享设备转变成具有共享特征的虚拟设备，从而提高设备利用率
中断处理程序·
- 关中断
- 保存现场
- 转入设备中断处理程序
- 进行中断处理
- 恢复被中断进程的现场
- 开中断
- 设置MMU以执行下一个进程
设备驱动程序·
- 将抽象I/O请求转换为对物理设备的请求
- 检查I/O请求的合法性
- 初始化设备
- 启动设备
- 发出I/O命令
- 响应中断请求
- 构造通道程序
5.3 OS设备管理实例·
第六章 磁盘存储管理·
6.1 磁盘存储的工作原理·
温切斯特盘
基本概念·
- 扇区（sector） 盘片被分成许多扇形的区域
- 磁道（track） 盘片上以盘片中心为圆心，不同半径的同心圆。
- 柱面（cylinder) 硬盘中，不同盘片相同半径的磁道所组成的圆柱。
- 每个磁盘有两个面，每个面都有一个磁头(head)。
磁盘的组织·
读一个扇区需要柱面/磁头/扇区。
一维逻辑块数组按照顺序映射到磁盘扇区
磁盘访问时间·
磁盘延迟=软件的Queue处理+Disk Service Time(寻道+旋转+传输)
寻道时间·
磁头从当前位置移到指定磁道上所经历时间
$s:启动磁盘时间$
$m:磁头移动一条磁道所花时间$
$T_s=m*n+s$
旋转延迟时间·
平均$T_r$为$50到100ms$
$T_r=1/(2r)$
传输时间·
$T_t$为与磁盘进行数据交换（读出或写入）的时间
$T_t$的大小与每次所读／写的字节数b，旋转速度r以及磁道上的字节数N有关
$T_t = b/(rN)$
$b/N—需要多少转$
$r—多少转/s$
传输数据的大小 (通常是1个扇区): 512B
旋转速度：3600 RPM ~ 15000 RPM
典型的传输速度：2MB~50 MB/秒
总访问时间·
$T_a=T_s+1/(2r)+b/(rN)$
磁盘调度算法·
先来先服务 FCFS·
按访问请求先后次序服务
最短寻道时间优先 SSTF·
优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先。
可能导致饥饿，即一些请求长时间得不到服务
扫描算法 SCAN 电梯调度·
磁盘臂沿特定方向移动到最后一层, 满足路径中的所有请求。
然后转回并反向移动至最低层, 满足路径中的所有请求。
循环扫描算法 CSCAN·
- 按照所要访问的柱面位置的次序去选择访问者。
- 移动臂到达最后一个柱面后，立即带动读写磁头快速返回到0号柱面。
- 返回时不为任何的等待访问者服务。
- 返回后可再次进行扫描。
SCAN算法偏向于处理最里或最外的磁道访问请求，CSCAN可以避免
LOOK算法·
SCAN算法改进
CLOOK算法·
CSCAN算法改进
每次向一个方向移动到最高请求柱面，之后返回最低请求柱面，不理会返回路径上的请求
6.2 保证磁盘可靠性·
RAID·
廉价冗余磁盘阵列,Redundant arrays of inexpensive disks
- 冗余技术提高可靠性
- 并行提高性能
数据分段并行交叉存取
组成磁盘阵列的不同方式称为RAID级别，分为0-6 7个级别，还有一个RAID10
6.3 提高I/O访问速度·
主要途径·
- 选择性能好的磁盘
- 并行化
- 采用适当的调度算法
- 设置磁盘高速缓冲区
提高磁盘I/O速度——缓存·
- 独立缓存/以虚拟内存为缓存
- 置换算法 LRU
- 周期性写回
优化数据布局·
- 优化物理块的分布
- 优化索引节点的分布
其他方法·
- 提前读
- 延迟写
- 虚拟盘
6.4 磁盘管理的实例·
第七章 文件系统·
7.1 文件系统基本概念·
文件作为数据的存储和访问单位
文件包括：
- 文件体：文件本身内容 （data）
- 文件说明：文件存储和管理的相关信息，如：文件名、文件内部标识、文件存储地址、访问权限、访问时间等；（meta-data）
文件可以视为与进程地址空间无关的一段单独连续的逻辑地址空间
现代OS：一切皆文件
7.2 文件系统实现方法·
文件系统管理对象：
- 文件
- 目录
- 磁盘存储空间
文件控制块 FCB·
基本信息·
- 文件名
- 物理位置
- 文件逻辑结构 有无结构
- 文件物理结构 （顺序、索引）
访问控制信息·
- 文件所有者 创建的用户
- 访问权限 读、写、执行、删除
使用信息·
- 创建时间，上一次修改时间，当前使用信息等等
文件逻辑结构和物理结构·
文件逻辑结构（文件组织）·
文件物理结构·
文件存放方式，在存储介质上的位置、链接和编目方法
主要结构：连续结构（顺序存取，适用于变化不大的顺序访问文件）、索引结构、串联结构（随机存取，采用链接指针，动态性好，易于扩充）
索引结构 ※※※·
为每个文件建立逻辑块号与物理块号的对照表：索引表。
文件由数据文件和索引表构成，这种文件称为：索引文件。
索引表位置：文件目录中，文件开头
索引表大小：固定/非固定大小
索引文件在存储区占两个区，索引区–放索引表，数据区–放数据文件本身。
访问索引文件·
- 先查文件索引号，由逻辑块号查得物理块号
- 由此物理块号获得所要求的信息
索引表的组织·
- 链接模式
- 多个索引表链接起来
- 多级索引
- 综合模式
- 直接索引与间接索引结合
目录·
目录的实现·
直接法：目录项=文件名+FCB
间接法：目录项=文件名+FCB地址
符号文件目录的查询·
顺序查寻法·
依次比对名字
Hash方法·
将符号名唯一的变换为符号表中的表目索引
磁盘空间管理·
空闲表法·
| 序号 | 第一空闲盘块号 | 空闲盘块数 |
|---|---|---|
| 1 | 2 | 4 |
| 2 | 3 | 3 |
空闲链表法·
分为空闲盘区链和空闲盘块链
位示图（位图法）·
成组链表法·
每组的第一个空闲块记录下一组空闲块的物理盘块号和空闲块总数。
保护文件的方法·
- 建立副本
- 定时转储
- 规定文件的权限
7.3 文件系统实例分析·
FAT·
EXT2·
Linux VFS·
LFS·
习题·
文件系统·
一个Unix文件系统采用2KB大小的数据块和4字节的数据块地址。每个i节点包括10个直接索引，1个一级间接索引和1个二级间接索引。（1）该文件系统中文件最大为多少KB？（本小题5分）（2）假设磁盘上一半的文件大小恰好为2KB，另一半文件的大小恰好为1.5KB，那么磁盘空间的利用率是多少？如果数据块大小改为1KB，磁盘空间利用率是多少？（只考虑存储文件数据的磁盘块）（本小题6分）（3）小明编写了一个读取文件的程序，可以从不同大小的文件中随机读取一定量数据，结果发现读取大文件时的平均性能有明显下降。请分析主要原因，并尝试给出解决该问题的思路。（本小题4分）
(1)
2KB/4=512个磁盘块
(10+1*512+1*512*512)*2KB=
(2)
(2/2+1.5/2)/2=0.875