输入/输出和存储系统。
AMDAHL定律、输入/输出结构
- 计算机系统整体性能的速度提升取决于某个特定部件本身的加速率和该部件在系统中的使用率。公式表示为 S = ( (1-f)+f/k )^-1。式中，S为系统整体性能的加速率，f表示较快部件完成的工作部分，k为新部件的加速率。例如，某计算机需要70%时间执行CPU操作和30%时间等待磁盘服务，当前有两种升级方案：10000￥使得处理器价格提高50%，或7000￥使得磁盘处理能力为当前系统的250%。若选择升级处理器，则f = 0.70，k = 1.5，S = 1 / ((1-0.7)+0.7/1.5) = 1.30；若选择升级磁盘，则f = 0.30，k = 2.5，S约为1.22。由此可看出升级处理器带来的整体性能提升更高，但考虑价格因素，对提升的每个百分点，升级CPU需要333￥，而升级磁盘只要318￥。
- 输入/输出定义为在外部设备和由CPU、主存储器组成的主机系统之间移动编码数据的一个子系统部件。
- 输入输出子系统包括
- 用于I/O功能的主存储器模块
- 提供将数据从系统中移入和移出所需要的总线通道
- 主机和外围设备中的控制模块
- 连接外部元件的接口、连接主机系统和外围设备的电缆等
- 协议：在发送设备和接收设备之间交换的各种信号的具体形式和信号所代表的意义，包括命令信号、状态信号、数据传递信号。接收设备对命令和发送来的数据做出应答的协议交换称为握手。
- 通常处理大量数据信息的外部设备都有缓冲存储器，如打印机、磁带驱动器等，缓冲器允许主机系统以尽可能快的方式将大量数据发送到外围设备中。设备控制电路负责从系统的缓冲器中提取或输入数据，例如包括在写数据时对磁盘定位，将打印头或激光术移动到下一字符位置，启动打印头，弹出打印纸等操作。
- 磁盘和磁带属于持久性存储，其相对易失性存储时间更长。数据在磁性介质中可以保存约5年，在光学介质中可保存大约100年。
I/O控制方法
- 程序控制的I/O：系统为每个I/O设备至少分配一个专用的寄存器，CPU持续不断的监视每个寄存器，等待数据到达，该方法称为轮询。一旦CPU检测到某个“数据就绪”的条件，就为该寄存器准备指令执行等操作。该方法的优点在于：可以通过编程控制每个外部设备的行为，改变程序就可以调整系统所控制的外部设备的数目和类型，以及轮询的权限和时间间隔。缺点在于：不断对寄存器轮询使得CPU持续处于繁忙等待循环中，直到开始服务某个I/O请求。如果没有任何I/O任务要处理，CPU就无法从事任何有用的操作。因此程序控制的I/O最适合用于自动提款机等一些用来控制或监视外部事件的系统。
- 中断控制的I/O：在有数据发送需求时由外部设备通知CPU，如果没有外部设备发出服务请求来中断CPU，则CPU继续执行其他任务。通常使用CPU的标志寄存器中的一个二进制位表示中断信号，该位称为中断标志。一旦中断标志置位，操作系统就会中断正在执行的程序，并保存该程序的状态和各种可变的信息，提取请求中断的I/O设备的地址矢量。在完成I/O操作后CPU会完全恢复到中断前状态并继续执行。该方法和程序控制I/O的相似之处为：都可以对I/O服务程序进行修改以适应外部硬件的改变。许多主流操作系统均使用中断控制的I/O，为防止病毒制造者修改I/O设备地址矢量指向恶意代码，操作系统均提供了保护机制防止这类操作。
- 直接存储器存取（DMA）：无论何种中断控制的I/O，CPU都需要从I/O设备移入和移出数据。在这个过程中，CPU会完全运行一些类似如下为代码的指令
1 | WHILE More-input AND NOT Error |
这些指令非常简单，可以使用一个专用芯片编程。如果一个系统使用DMA，则CPU不再需要执行冗长的I/O指令，仅需为DMA提供需要传输数据字节的地址、字节数以及目标I/O设备地址。CPU和DMA的通信由CPU上的专用I/O寄存器完成。DMA执行I/O操作的具体细节时，CPU会继续执行下一个任务，DMA完成后会发送一个中断请求通知CPU。
程序控制的I/O每次传输一个字节，中断控制的I/O每次可以按字节或小数据块形式传输，具体取决于I/O设备。通常速度较慢的设备如键盘，传输相同字节数的数据要比磁盘驱动器和打印机产生更多的中断过程。DMA方法是面向数据块的I/O处理方式，只在一组字节的传输结束后才中断CPU。当DMA发出I/O完成的信号后，CPU会给出下一个要读取或写入的内存地址，而传输失败时，CPU会独自做出适当的相应，因此DMA的I/O需要很少的CPU参与。
DMA控制器和CPU共享存储器总线，任一时刻只能有一个设备控制总线，通常I/O设备比CPU从内存中提取程序指令和数据的优先级高，因为很多I/O设备操作都限制在紧凑的时间参数内，如果特定的时间周期内没有检测到事件发生，这些I/O设备就会被强制超时休息，并中止当前I/O进程。为避免超时休息，DMA会利用平时由CPU使用的存储器周期完成I/O操作，称为周期窃取。因为I/O趋向于在总线上产生突发式的传输，即成块成组的发送数据，在这些突发式传输的间隙，CPU会被授权访问总线。
- 通道控制的I/O：DMA适用于小型单用户计算机，对于大型多用户计算机通常采用I/O通道的智能型DMA接口。一个或多个的I/O处理器可以控制多条不同的I/O路径，这些路径被称为通道路径。对于慢速设备如打印机，通道路径可以复用，允许几个这类设备仅通过一个控制器管理。在IBM的大型计算机中，一个多路复用的通道路径称为多路复用器通道，而服务于磁盘控制器和其他快速设备的通道称为选择器通道。I/O通道由一些被称为I/O处理器（IOP）的小CPU控制，IOP具有执行程序的能力，其与DMA的主要区别在于1）I/O处理器的智能特性：能够对协议进行协商，发出各种设备命令，独立于CPU传输，CPU只负责为其创建程序指令、通知其指令所在地址。2）通道控制的I/O系统都配备单独的总线，用来格力主机和I/O操作，IOP只在从主存储器提取指令时才使用系统存储器总线。因此通道控制的I/O通常在高吞吐量的环境中使用。
磁盘技术
磁盘驱动器技术出现前，顺序存储介质如打孔卡片、磁带、纸带等是唯一可用的持久性存储介质。如果某个用户所需的数据写在磁带卷轴的尾部，必须读完整卷才能读取，并且每次只能阅读一个记录。1956年IBM公司发布第一台商用磁盘计算机，简称RAMAC，使用随机访问方法的会计和控制计算机。其使用的磁盘驱动器，每个磁盘直径24英寸，磁盘每一面只能容纳50000个7位字符，售价数百万美元。到2000年，IBM推广的磁盘直径尺寸仅为1英寸，保存1GB字节数据，平均访问时间15ms，价格低于300$。
磁盘驱动器
- 磁盘驱动器被称为随机存储设备，或直接存储设备。磁盘上的每个存储单元被称为扇区，有独一无二的存取地址。这些扇区按照同心圆环的形式划分为一圈一圈的磁道（每个同心圆环为一个磁道），每个磁道上的扇区数都相同，因此数据在磁盘中心写入的数据比磁盘边缘更加密集。有的厂商会把全部扇区制作为近似相同的容量，这样外部磁道可以放置比内部磁道更多的扇区，存储更多信息，这种方法称为分区位，现在很少被使用，因为需要更复杂的驱动控制电路。磁道从磁盘最外的磁道0开始编号，在一条磁道分布的圆周上，扇区的分配顺序可能不连续，这样允许驱动器电路有时间在读取下一个扇区之前处理完扇区进程的内容，这种技术称为交叉存储技术。现代磁盘驱动器大多一次读取一条磁道，而不是一次读取一个扇区，因此交叉存储技术已经不再流行。
- 磁盘（hard）包括控制电路和一个或多个金属/玻璃盘片，称为碟片。盘片上镀有一层薄的磁性材料薄膜，碟片堆叠在转轴上，通过一个马达带动磁盘碟片旋转，速度可达每分钟15000rpm，典型的磁盘转速为5400rpm和7200rpm。磁盘的读写头安装在一个旋转的磁盘驱动臂上，磁盘驱动臂通过其转轴上缠绕的线圈的感应磁场来进行准确定位，整个梳状的读写头可以向磁盘中心移动或从磁盘中心移开。
对于一个堆叠的磁盘结构，磁盘上的各个磁道上下一一对应，形成一个圆柱面。一组梳状的读写头每次可以访问一个柱面。通常磁盘的可用面上都有一个磁头，但对于一些老式的磁盘系统特别是移动磁盘，最上层碟片的上表面和最下层磁盘的下表面常常都是不用的。磁盘磁头从来都不会触及磁盘的表面，而是悬浮在磁盘表面的上方，之间仅仅相隔几个微米厚的空气层。当磁盘系统断电后，磁头退到一个安全的地方，这一过程称为停靠磁头。如果读写头接触到磁盘表面，就会损坏磁盘，称为磁头撞损。 - 寻道时间指磁盘驱动臂定位到指定的磁道上所需的时间。寻道时间并不包括磁头读取磁盘目录的时间。磁盘目录将逻辑文件信息如my_story.doc，映射到对应的物理扇区位置，如第7柱面中第3表面的第72扇区。部分高性能的磁盘会在每个可用面的每个磁道上都提供一个读写头，消除了寻道时间。旋转延迟是指读写头定位到指定的扇区所需的时间。旋转延迟和寻道时间的和为存取时间。
- 在每次执行读写操作前都必须读取磁盘目录，由于磁盘最外层的磁道在相同面积内有最低的位密度，因此与内层磁道相比更不容易出现位错误。为保证更高的可靠性，可以把磁盘目录存放在最外层磁道，即磁道0。因此每次存取操作驱动臂都必须向外摆动到磁道0，然后回到所需数据的磁道上。随着记录技术和纠错算法发展，目前已经允许磁盘目录放到能够提供最佳性能的位置上，即最中间的磁道上。实际情况中，操作系统以群组的形式为扇区分配地址，称为区块。每个块中扇区的数目决定了分配表的大小，如果分配的块越小，则当一个文件不能装满整个块时，浪费的空间就越小；而如果每个块中的扇区数目过少，则记录块的分配表会很大，查找速度会减慢。
## 软盘
- 软盘组织方式与硬盘相似，按照磁道和扇区寻址。区别在于软盘的磁性材料涂层附着在一个软性的聚酯塑料基片上，并且由于软盘不能像硬盘一样密封，因此软盘的数据密度和旋转速度受到很大限制。软盘的读写头必须接触到磁盘的磁表面，当读写头上有其他颗粒时，摩擦会引起磁性涂层的磨损，因此必须定期清洗磁头。软盘的组织结构和操作规范更统一。以3.5’’ 1.44MB DOS/Windows软盘为例，每个扇区含512个字节，每条磁道有18个扇区，软盘的每一面有80条磁道。扇区0为软盘的引导扇区，紧接着的是两个完全相同的文件分配表（File Allocation Table，FAT）的副本，标准的1.44MB软盘的每个FAT大小为9个扇区长。每个区块是一个可编址的单元，1.44MB软盘中每个区块即为一个扇区。磁盘根目录占据从扇区19开始的14个扇区，每个根目录的条目占用32字节，每个根目录存储文件名、文件属性、文件时间表、文件大小、存放的起始区块编号，起始的区块编号指向FAT中的某个条目。如果某个数据文件占用多个区块，则允许追踪这个数据文件跨越的扇区链。
- FAT是一个简单的表结构，采用位图形式记录磁盘上每个区块的基本信息，指示区块是否处于空闲、保留、数据占用或坏区状态。因为每个1.44MB磁盘包含18×80×2 = 2880个扇区，所以每个FAT条目需要12位用来指出一个区块。实际上每个FAT条目都为16位宽，因此称为FAT16。若一个文件跨越多个区块，则该文件的第一个FAT条目中同样包含一个转向该文件下一个FAT条目的指针。
- 举例：假设文件占用了从扇区121开始的4个扇区，读取文件时会进行如下操作
1.读取磁盘目录查找文件起始区块121,读取第一个区块取回文件第一部分。2.读取位于区块121的FAT条目查找文件剩余部分，表中可得下一数据区块对应的FAT条目为124。3.读取区块124和相应的FAT条目，之处下一数据在126。4.读取区块126和相应的FAT条目，之处下一数据在122。5.读取区块122和对应的FAT，在下一扇区位置找到FAT索引 120 121 122 123 124 125 126 127 FAT内容 97 124 EOF 1258 126 122 577 标志，因此结束。
独立磁盘冗余阵列
1988年美国加州大学伯克利分校的David Patterson、Garth Gibson和Randy Katz三人发表了“廉价磁盘冗余阵列的实例”的论文，创造RAID一词，介绍了如何利用若干数量的廉价小磁盘替代大型机上的大型昂贵的单磁盘。论文中三人定义了5种类型（称为级）的RAID，每一级RAID具有不同的性能和可靠性，后来经过各厂商发展，增加了其他RAID级。更高编号的RAID层次不一定是更好的RAID系统，下面使用的编号方法保留了Berkeley命名方法。
- RAID Level 0：简称RAID-0，是将数据以条带形式存放在几个磁盘表面上，一个记录会占用几个磁盘表面的多个扇区，又称为磁盘跨区、块交错数据分带或磁盘分带。分带是简单的将逻辑顺序的数据进行分段，分段可以小到单一位，或某个特定大小的块。因为RAID-0不提供冗余，因此在各种RAID配置结构中，RAID-0有最佳性能，尤其在每个磁盘都有自己的独立控制器和高速缓存时。RAID-0非常廉价，但系统整体可靠性为单个磁盘期望性能的几分之一。如阵列由5个磁盘组成，每个磁盘设计寿命50000小时，则整个系统期望设计寿命50000/5 = 10000 小时。磁盘数增加，失效概率随之增加。没有冗余导致RAID-0没有容错能力，因此RAID-0的唯一好处在于性能，通常用于非关键的而又需要高速读取、写入的数据，或改变不太频繁和经常被分的数据，或低成本场合。
- RAID Level 1：称为磁盘镜像，是所有RAID级中失效保护最佳的方案，存储方式和RAID-0相同，但每次写入数据都会复制到另一组完全相同的磁盘上。这种方式的读取性能更优异，尤其在镜像盘（第二组磁盘）和住驱动器相差180度旋转时，减少一半反应时间。RAID-1适合于面向事务、高可用率的工作环境，以及高容错率的应用，如会计、工资表。
- RAID Level 2：因为RAID-1方案成本为RAID-0的两倍，因此RAID-2只是用磁盘组中的一个或几个磁盘存储其他磁盘中的数据信息。RAID-2在每个条带中只写入一位数据，而不采用任意大小的块写入数据，这样需要至少八个磁盘表面才能存放数据，另外需要一组磁盘驱动器存放纠错信息，这些纠错位由海明编码生成。如果磁盘阵列中的任何一个驱动器损坏，可以用海明驱动器重建这个驱动器。同样，如果海明驱动器出错，也可以用数据驱动器重建。然而，所有驱动器必须严格同步，并且生成海明编码的过程非常耗时。
- RAID Level 3：RAID-3同RAID-2一样，每次按照一位的方式将数据交错分配到各个驱动器的条带中，但与RAID-2不同的是，RAID-3只使用一个驱动器来保存简单的奇偶校验位，只需对每一位进行异或即可。利用这种方法可以对一个损坏的驱动器重建，例如6号驱动器损坏并要被替换，只要对其他7个数据驱动器和奇偶校验器上的数据异或即可。RAID-3需要同步操作，比RAID-1和RAID-2更经济，不适合面向事务的应用程序，更适合读写大块数据块的情况。
- RAID Level 4：RAID-4和RAID-2一样，是理论上的RAID级。使用一个奇偶校验位驱动器和一组数据磁盘，将数据写入统一大小的条带中，奇偶校验位也存储为条带。然而RAID-4使系统性能严重下降，因为数据盘对奇偶校验盘有竞争情况。假设正在处理奇偶校验块，如果有一个条带1和条带4的写入请求，在RAID-0和RAID-1时会直接写入，而RAID-4的奇偶校验则成为了瓶颈。
- RAID Level 5：RAID-5是所有以RAID为基础的应用系统中使用数量最多的，能够以最少的成本提供最佳的保护，改进了RAID-4，将奇偶校验位写到多个磁盘上而非一个磁盘。但在所有RAID层次中，RAID-5需要的磁盘控制器是最复杂的。图中绿色方块代表奇偶校验位。
- RAID Level 6：前面所有的RAID系统只能允许最多有一个磁盘出错，但通常磁盘驱动器出错呈现成簇的倾向（寿命相同，灾难性事件）。RAID-6对每排数据使用两组纠错条带，除使用奇偶校验位外还使用Reed-Soloman纠错编码提供二层保护。RAID-6的写入性能很差，并且生成Reed-Soloman编码需要的代价很大，因此目前没有商业配置的RAID-6系统。
- RAID混合系统：如RAID-10，将RAID-0的分带和RAID-1的镜像结合。
数据压缩
- 压缩系数 = 1 - 压缩后的文件大小/压缩前的文件大小 × 100%
- 字符的熵：衡量一个消息中的信息量。如果某个符号x在一个消息中出现的概率为P(x)，则该字符的熵H = -P(x)×log(2)P(x)。整个消息的平均熵则为消息中所有n个符号的熵求和取平均。熵为编码一个消息所需的二进制位数建立了低限。除了这个低限外的其他位不会增加信息。例如“Hello World!”中，平均的符号熵为3.022，因此低限为3.022×12个字符 = 36.26或37位，因此如果用8位ASCII编码表示，则冗余位为8×12 - 37 = 59个。
赫夫曼编码
- 按照消息中不同字符出现的频率构成赫夫曼树，之后按照左分支标记0，右分支标记1的方式编码。这样频率最高的符号在编码中占用最少的位，并产生的是前缀编码。
- 赫夫曼编码实际将实数集的元素映射为整数子集中的元素，因此精度上的欠缺可能使产生的编码有冗余，不能刚好使用平均熵的位数压缩。
算术编码
- 编码方式：将实数集映射到实数集中，利用消息中符号集的概率在0和1之间分割实数轴。使用越频繁的符号，分割所得到的区间快越大。
- 举例：“HELLO WORLD!”在该语句中共有12个字符，这些符号中出现最低的概率是1/12，其他概率都是1/12的整数倍，因此可将0到1之间的区间划分为12个部分。除了L和O之外，其他每个符号都分配了1/12的区间，符号L和O则分配了3/12和2/12的区间。区间映射关系如下表
通过连续划分与符号所分配区间成比例的数值范围（0.0到1.0）来对消息进行编码。例如当前区间位置为1/8，而字母L获得了1/4的当前区间，如上表，接下来对L编码，将1/8乘以1/4得到L的新的当前区间1/32。如果下一个字符是另一个字母L，则将1/32再乘以1/4得到当前的区间值1/128。这个编码过程会一直持续下去，直到整条消息编码完成。过程可用伪代码描述。符号 频率 区间 符号 频率 区间 D 1/12 [0.0…0.083) R 1/12 [0.667…0.750) E 1/12 [0.083…0.167) W 1/12 [0.750…0.833) H 1/12 [0.167…0.250) (space) 1/12 [0.833…0.917) L 3/12 [0.250…0.500) ! 1/12 [0.917…1.0) O 2/12 [0.500…0.667)
1 | ALGORITHM Arith_Code( Message ) |
该过程用表格表示：
| 符号 | 区间 | CharLoVal | CharHiVal | LoVal | HiVal |
| 0.0 | 1.0 | ||||
| H | 1.0 | 0.167 | 0.25 | 0.167 | 0.25 |
| E | 0.083 | 0.083 | 0.167 | 0.173889 | 0.180861 |
| L | 0.006972 | 0.25 | 0.5 | 0.1756320 | 0.1773750 |
| L | 0.001743 | 0.25 | 0.5 | 0.17606775 | 0.17650350 |
| O | 0.00043575 | 0.5 | 0.667 | 0.176285625 | 0.176358395 |
| (space) | 0.00007277025 | 0.833 | 0.917 | 0.1763462426 | 0.1763523553 |
| W | 0.00000611270 | 0.75 | 0.833 | 0.1763508271 | 0.1763513345 |
| O | 0.00000050735 | 0.5 | 0.667 | 0.1763510808 | 0.1763511655 |
| R | 0.00000008473 | 0.667 | 0.75 | 0.1763511373 | 0.176351444 |
| L | 0.00000000703 | 0.25 | 0.5 | 0.1763511391 | 0.1763511409 |
| D | 0.00000000176 | 0 | 0.083 | 0.1763511391 | 0.1763511392 |
| ! | 0.00000000015 | 0.917 | 1.0 | 0.176351139227 | 0.176351139239 |
| 0.176351139227 |
Ziv-Lempel字典系统
JPEG压缩
专栏目录：计算机理论基础
此专栏的上一篇文章：计组与体系结构笔记（五）：存储器相关
此专栏的下一篇文章：操作系统（一）：概念导读
原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2015/11/14/Computer-Organization-Architecture6/) 、作者信息（Forec）和本声明。