如需转载，请根据 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 许可，附上本文作者及链接。
本文作者： Alice
作者昵称： 沉。
本文链接： http://example.com/2020/11/05/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%EF%BC%88%E4%B8%89%EF%BC%89/
四、文件管理
4.1、文件的基本概念
文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件。
标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。
类型：指明文件的类型
位置：文件存放的路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见）
大小：指明文件大小创建时间、上次修改时间文件所有者信息
保护信息：对文件进行保护的访问控制信息
文件之间是如何组织起来的：
操作系统向上提供了哪些功能？
文件共享：使多个用户可以共享使用一个文件
文件保护：如何保证不同的用户对文件有不同的操作权限
小结：
4.2、文件的逻辑结构
所谓的“逻辑结构”，就是指在用户看来，文件内部的数据应该是如何组织起来的。而“物理结构”指的是在操作系统看来，文件的数据是如何存放在外存中的。
按文件是否有结构分类，可以分为无结构文件、有结构文件两种。
无结构文件：文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。如：Windows 操作系统中的 .txt 文件。
文件内部的数据其实就是一系列字符流，没有明显的结构特性。因此也不用探讨无结构文件的“逻辑结构”问题。
有结构文件：由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID），根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种
顺序文件：顺序文件：文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。
索引表本身是定长记录的顺序文件。因此可以快速找到第 i 个记录对应的索引项。可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。
另外，可以用不同的数据项建立多个索引表。
索引顺序文件：
多级索引顺序文件：
小结：
4.3、文件目录
4.3.1、文件控制块
需要对目录进行哪些操作？
搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项
删除文件：当删除一个文件时，需要在目录中删除相应的目录项
显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名）
4.3.2、目录结构
早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。
单级目录实现了“按名存取”，但是不允许文件重名。在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。显然，单级目录结构不适用于多用户操作系统。
两极目录结构
早期的多用户操作系统，采用两级目录结构。分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，User Flie Directory）。
多级目录结构
树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了“无环图目录结构”。
无环图目录结构：
可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）。
需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。
只有共享计数器减为0时，才删除结点。
注意：共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。
索引结点（FCB的改进）
存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。
相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等
小结：
4.4、文件的物理结构
类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”。很多操作系统中，磁盘块的大小与内存块、页面的大小相同
在内存管理中，进程的逻辑地址空间被分为一个一个页面同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。
4.4.1、连续分配
连续分配方式要求每个文件在磁盘上占有一组连续的块
（逻辑块号，块内地址）——>（物理块号，块内地址）。只需转换块号就行，块内地址保持不变
物理块号 = 起始块号 + 逻辑块号
可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问（即随机访问）
读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。
结论：连续分配的文件在顺序读/写时速度最快
连续分配的缺点： 物理上采用连续分配的文件不方便拓展。物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片可以用紧凑来处理碎片，但是需要耗费很大的时间代价。
连续分配总结：
连续分配方式要求每个文件在磁盘上占有一组连续的块。
优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序访问时速度最快
缺点：不方便文件拓展；存储空间利用率低，会产生磁盘碎片
4.4.2、链接分配
链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。
采用链式分配（隐式链接）方式的文件，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。
采用隐式链接的链接分配方式，很方便文件拓展。 另外，所有的空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高。
隐式链接总结：
链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。
隐式链接——除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。
优点：很方便文件拓展，不会有碎片问题，外存利用率高。
缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间
显示链接：
采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问 i 号逻辑块时，并不需要依次访问之前的 0 ~ i-1号逻辑块），由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。
显然，显式链接也不会产生外部碎片，也可以很方便地对文件进行拓展。
显示链接总结：
显式链接——把用于链接文件各物理块的指针显式地存放在一张表中，即 文件分配表（FAT，FileAllocation Table）。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内 存。
优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接 来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
缺点：文件分配表的需要占用一定的存储空间。
4.4.3、索引分配
索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
①链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。
②多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。
- 采用 K 层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要 K + 1 次读磁盘操作
③混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表） 。
超级超级超级重要考点：①要会根据多层索引、混合索引的结构计算出文件的最大长度（Key：各级索引表最大不能超过一个块）；②要能自己分析访问某个数据块所需要的读磁盘次数（Key：FCB中会存有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件——顶级索引块是否已调入内存）
总结：
4.5、文件存储空间管理
存储空间管理——空闲表法
适用于 “连续分配方式”
如何分配磁盘块：与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
如何回收磁盘块：与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况——①回收区的前后都没有相邻空闲区；②回收区的前后都是空闲区；③回收区前面是空闲区；④回收区后面是空闲区。总之，回收时需要注意表项的合并问题。
存储空间管理——空闲链表法
空闲盘块链:
操作系统保存着链头、链尾指针。
如何分配：若某文件申请 K 个盘块，则从链头开始依次摘下 K 个盘块分配，并修改空闲链的链头指针。
如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。（适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作）
空闲盘区链：
操作系统保存着链头、链尾指针。
如何分配：若某文件申请 K 个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。
如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。
存储空间管理——位示图法
位示图：每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。
如何分配：若文件需要K个块，①顺序扫描位示图，找到K个相邻或不相邻的“0”；②根据字号、位号算出对应的盘块号，将相应盘块分配给文件；③将相应位设置为“1”。
如何回收：①根据回收的盘块号计算出对应的字号、位号；②将相应二进制位设为“0”
存储空间管理——成组链接法
空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。
文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。
如何分配？Eg ：需要100个空闲块①检查第一个分组的块数是否足够。100=100，是足够的。②分配第一个分组中的100个空闲块。但是由于300号块内存放了再下一组的信息，因此300号块的数据需要复制到超级块中。
如何回收？Eg ：假设每个分组最多为100个空闲块，此时第一个分组已 有100个块，还要再回收一块。需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。
总结：
4.6、文件的基本操作
创建文件：进行 Create 系统调用时，需要提供的几个主要参数：
- 所需的外存空间大小（如：一个盘块，即1KB）
- 文件存放路径（“D:/Demo”）
- 文件名（这个地方默认为“新建文本文档.txt”）操作系统在处理 Create 系统调用时，主要做了两件事：
- 在外存中找到文件所需的空间（结合上小节学习的空闲链表法、位示图、成组链接法等管理策略，找到空闲空间）
- 根据文件存放路径的信息找到该目录对应的目录文件（此处就是 D:/Demo 目录），在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。
删除文件：进行 Delete 系统调用时，需要提供的几个主要参数：
- 文件存放路径（“D:/Demo”）
- 文件名（“test.txt”）操作系统在处理 Delete 系统调用时，主要做了几件事：
- 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项。
- 根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。（回收磁盘块时，根据空闲表法、空闲链表法、位图法等管理策略的不同，需要做不同的处理）
- 从目录表中删除文件对应的目录项
打开文件：在很多操作系统中，在对文件进行操作之前，要求用户先使用 open 系统调用“打开文件”，需要提供的几个主要参数：
- 文件存放路径（“D:/Demo”）
- 文件名（“test.txt”）
- 要对文件的操作类型（如：r 只读；rw 读写等）操作系统在处理 open 系统调用时，主要做了几件事：
- 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，并检查该用户是否有指定的操作权限。
- 将目录项复制到内存中的“打开文件表”中。并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件。
- 可以方便实现某些文件管理的功能。例如：在Windows系统中，我们尝试删除某个txt文件，如果此时该文件已被某个“记事本”进程打开，则系统会提示我们“暂时无法删除该文件”。其实系统在背后做的事就是先检查了系统打开文件表，确认此时是否有进程正在使用该文件。
关闭文件：进程使用完文件后，要“关闭文件”操作系统在处理 Close 系统调用时，主要做了几件事：
- 将进程的打开文件表相应表项删除
- 回收分配给该文件的内存空间等资源
- 系统打开文件表的打开计数器count 减1，若 count = 0，则删除对应表项。
读文件：进程使用 read系统调用完成写操作。需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可），还需要指明要读入多少数据（如：读入 1KB）、指明读入的数据要放在内存中的什么位置。操作系统在处理 read 系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。
写文件：进程使用 write 系统调用完成写操作，需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可），还需要指明要写出多少数据（如：写出 1KB）、写回外存的数据放在内存中的什么位置操作系统在处理 write 系统调用时，会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存。
小结：
4.7、文件共享
基于索引结点的共享方式（硬链接）
注意：多个用户共享同一个文件，意味着系统中只有“一份”文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。如果是多个用户都“复制”了同一个文件，那么系统中会有“好几份”文件数据。其中一个用户修改了自己的那份文件数据，对其他用户的文件数据并没有影响。
基于符号链的共享方式（软连接）
小结：
4.8、文件保护
口令保护：
- 口令一般存放在文件对应的 FCB 或索引结点中。用户访问文件前需要先输入“口令”，操作系统会将用户提供的口令与FCB中存储的口令进行对比如果正确，则允许该用户访问文件
- 优点：保存口令的空间开销不多，验证口令的时间开销也很小。
- 缺点：正确的“口令”存放在系统内部，不够安全。
加密保护：
- 使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。
- 一个最简单的加密算法——异或加密假设用于加密/解密的“密码”为“01001”
- 优点：保密性强，不需要在系统中存储“密码”
- 缺点：编码/译码，或者说加密/解密要花费一定时间。
访问控制
- 在每个文件的FCB（或索引结点）中增加一个访问控制列表（AccessControl List, ACL），该表中记录了各个用户可以对该文件执行哪些操作。
小结：
文件系统的层次结构
用一个例子来辅助记忆文件系统的层次结构：假设某用户请求删除文件 “D:/工作目录/学生信息.xlsx” 的最后100条记录。
用户需要通过操作系统提供的接口发出上述请求——用户接口
由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项——文件目录系统
不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限——存取控制模块（存取控制验证层）
验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址——逻辑文件系统与文件信息缓冲区
知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址——物理文件系统
要删除这条记录，必定要对磁盘设备发出请求——设备管理程序模块
删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收——辅助分配模块
4.9、磁盘结构
如何在磁盘中读/写数据：需要把“磁头”移动到想要读/写的扇区所在的磁道。磁盘会转起来，让目标扇区从磁头下面划过，才能完成对扇区的读/写操作。
盘面、柱面
磁盘的物理地址：
可用（柱面号，盘面号，扇区号）来定位任意一个“磁盘块”。在“文件的物理结构”小节中，我们经常提到文件数据存放在外存中的几号块，这个块号就可以转换成（柱面号，盘面号，扇区号）的地址形式。可根据该地址读取一个“块”
- 根据“柱面号”移动磁臂，让磁头指向指定柱面；
- 激活指定盘面对应的磁头；
- 磁盘旋转的过程中，指定的扇区会从磁头下面划过，这样就完成了对指定扇区的读/写。
磁盘的分类：
磁头可以移动的称为活动头磁盘。磁臂可以来回伸缩来带动磁头定位磁道
磁头不可移动的称为固定头磁盘。这种磁盘中每个磁道有一个磁头
盘片可以更换的称为可换盘磁盘
盘片不可更换的称为固定盘磁盘
4.10、磁盘调度算法
一次磁盘读/写操作需要的时间
寻找时间（寻道时间）TS：在读/写数据前，将磁头移动到指定磁道所花的时间。
启动磁头臂是需要时间的。假设耗时为 s；
移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为 m，总共需要跨越 n 条磁道。则：寻道时间 TS = s + m*n
延迟时间TR：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为 r （单位：转/秒，或 转/分），则平均所需的延迟时间 TR = (1/2)*(1/r) = 1/2r
传输时间Tt：从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为 r，此次读/写的字节数为 b，每个磁道上的字节数为 N。则：传输时间Tt = (1/r) * (b/N) = b/(rN)
先来先服务算法（FCFS）
最短寻找时间优先（SSTF）
扫描算法（SCAN）:
SSTF 算法会产生饥饿的原因在于：磁头有可能在一个小区域内来回来去地移动。为了防止这个问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移 动。这就是扫描算法（SCAN）的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。
LOOK 调度算法
扫描算法（SCAN）中，只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。LOOK 调度算法就是为了解决这个问题，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。（边移动边观察，因此叫 LOOK）
循环扫描算法（C-SCAN）
SCAN算法对于各个位置磁道的响应频率不平均，而 C-SCAN 算法就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。
C-LOOK 调度算法
C-SCAN 算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不一定需要返回到最边缘的磁道上。C-LOOK 算法就是为了解决这个问题。如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。
小结：
4.11、减少延迟时间的方法
减少延迟时间的方法：交替编号
若采用交替编号的策略，即让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。
磁盘地址结构的设计
若物理地址结构是（柱面号，盘面号，扇区号）由于柱面号/磁道号相同，只是盘面号不同，因此不需要移动磁头臂。只需要激活相邻盘面的磁头即可
减少延迟时间的方法：错位命名
小结：
4.12、磁盘的管理
磁盘初始化：
- 进行低级格式化（物理格式化），将磁盘的各个磁道划分为扇区。一个扇区通常可分为 头、数据区域（如512B大小）、尾 三个部分组成。管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码（如奇偶校验、CRC循环冗余校验码等，校验码用于校验扇区中的数据是否发生错误）
- 将磁盘分区，每个分区由若干柱面组成（即分为我们熟悉的 C盘、D盘、E盘）
- 进行逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构
引导块：
坏块的管理：
对于简单的磁盘，可以在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如：在 FAT 表上标明。（在这种方式中，坏块对操作系统不透明）
对于复杂的磁盘，磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个坏块链表。在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。会保留一些“备用扇区”，用于替换坏块。这种方案称 为扇区备用。且这种处理方式中，坏块对操作系统透明。
小结：
五、IO设备
5.1、I/O设备的基本概念和分类
什么是I/O设备？
“I/O” 就是 “输入/输出”（Input/Output）
I/O 设备就是可以将数据输入到计算机，或者可以接收计算机输出数据的外部设备，属于计算机中的硬件部件
I/O设备按使用特性分类：
- 人机交互类外部设备（数据传输速度慢）
- 存储设备（数据传输速度块）
- 网络通信设备（数据传输速度基于上述两者之间）
人机交互类外设：鼠标、键盘、打印机等——用于人机交互
存储设备：移动硬盘、光盘等——用于数据存储
网络通信设备：调制解调器等——用于网络通信
I/O按传输速率分类：
- 低速设备
- 中速设备
- 高速设备
低速设备：鼠标、键盘等——传输速率为每秒几个到几百字节
中速设备：如激光打印机等——传输速率为每秒数千至上万个字节
高速设备：如磁盘等——传输速率为每秒数千字节至千兆字节的设备
I/O设备按照信息交换的单位分类：
- 块设备，传输速率较高，可寻址，即对它可随机地读/写任一块
- 字符设备，传输速率较慢，不可寻址，在输入/输出时常采用中断驱动方式
块设备：如磁盘等——数据传输的基本单位是“块”
字符设备：鼠标、键盘等——数据传输的基本单位是字符。
小结：
5.2、I/O控制器
I/O设备：
- 机械部件
- 电子部件（I/O控制器，设备控制器）
I/O设备的机械部件主要用来执行具体I/O操作。
如我们看得见摸得着的鼠标/键盘的按钮；显示器的LED屏；移动硬盘的磁臂、磁盘盘面。
I/O设备的电子部件通常是一块插入主板扩充槽的印刷电路板。
5.2.1、I/O设备的电子部件（I/O控制器）
CPU无法直接控制I/O设备的机械部件，因此I/O设备还要有一个电子部件作为CPU和I/O设备机械部件之间的“中介”，用于实现CPU对设备的控制。
这个电子部件就是I/O控制器，又称设备控制器。CPU可控制I/O控制器，又由I/O控制器来控制设备的机械部件。
I/O控制器的功能：
接收和识别发出的命令
如CPU发来的 read/write 命令，I/O控制器中会有相应的控制寄存器来存放命令和参数
向CPU报告设备的状态
I/O控制器中会有相应的状态寄存器，用于记录I/O设备的当前状态。如：1表示空闲，0表示忙碌
数据交换
I/O控制器中会设置相应的数据寄存器。输出时，数据寄存器用于暂存CPU发来的数据，之后再由控制器传送设备。输入时，数据寄存器用于暂存设备发来的数据，之后CPU从数据寄存器中取走数据。
地址识别
类似于内存的地址，为了区分设备控制器中的各个寄存器，也需要给各个寄存器设置一个特定的“地址”。I/O控制器通过CPU提供的“地址”来判断CPU要读/写的是哪个寄存器
I/O控制器的组成：
值得注意的小细节：
一个I/O控制器可能会对应多个设备；
数据寄存器、控制寄存器、状态寄存器可能有多个（如：每个控制/状态寄存器对应一个具体的设备），且这些寄存器都要有相应的地址，才能方便CPU操作。有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像I/O；另一些计算机则采用I/O专用地址，即寄存器独立编址。
内存映像I/O v.s寄存器独立编址
小结：
5.2.2、I/O控制方式
需要注意的问题：
完成一次读/写操作的流程；
CPU干预的频率；
数据传送的单位；
数据的流向；
主要缺点和主要优点。
程序直接控制方式：
完成一次读/写操作的流程
CPU干预的频率很频繁，I/O操作开始之前、完成之后需要CPU介入，并且在等待I/O完成的过程中CPU需要不断地轮询检查。
数据传送的单位每次读/写一个字
数据的流向读操作（数据输入）：I/O设备——CPU——内存，写操作（数据输出）：内存——CPU——I/O设备，每个字的读/写都需要CPU的帮助
主要缺点和主要优点
优点：实现简单。在读/写指令之后，加上实现循环检查的一系列指令即可（因此才称为“程序直接控制方式”）
缺点：CPU和I/O设备只能串行工作，CPU需要一直轮询检查，长期处于“忙等”状态 ，CPU利用率低。
中断驱动方式：
引入中断机制。由于I/O设备速度很慢，因此在CPU发出读/写命令后，可将等待I/O的进程阻塞，先切换到别的进程执行。当I/O完成后，控制器会向CPU发出一个中断信号，CPU检测到中断信号后，会保存当前进程的运行环境信息，转去执行中断处理程序处理该中断。处理中断的过程中，CPU从I/O控制器读一个字的数据传送到CPU寄存器，再写入主存。接着，CPU恢复等待I/O的进程（或其他进程）的运行环境，然后继续执行。
注意：
CPU会在每个指令周期的末尾检查中断；
中断处理过程中需要保存、恢复进程的运行环境，这个过程是需要一定时间开销的。可见，如果中断发生的频率太高，也会降低系统性能
中断驱动方式流程：
完成一次读/写操作的流程（见右图，Key word：中断）
CPU干预的频率 每次I/O操作开始之前、完成之后需要CPU介入。等待I/O完成的过程中CPU可以切换到别的进程执行。
数据传送的单位 每次读/写一个字
数据的流向读操作（数据输入）：I/O设备——CPU——内存，写操作（数据输出）：内存——CPU——I/O设备
主要缺点和主要优点
优点：与“程序直接控制方式”相比，在“中断驱动方式”中，I/O控制器会通过中断信号主动报告I/O已完成，CPU不再需要不停地轮询。CPU和I/O设备可并行工作，CPU利用率得到明显提升。
缺点：每个字在I/O设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间。
DMA方式：
与“中断驱动方式”相比，DMA方式（ Direct Memory Access，直接存储器存取。主要用于块设备的I/O控制）有这样几个改进：
数据的传送单位是“块”。不再是一个字、一个字的传送；
数据的流向是从设备直接放入内存，或者从内存直接到设备。不再需要CPU作为“快递小哥”。
仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。
DMA方式的流程：
完成一次读/写操作的流程
CPU干预的频率仅在传送一个或多个数据块的开始和结束时，才需要CPU干预。
数据传送的单位每次读/写一个或多个块（注意：每次读写的只能是连续的多个块，且这些块读入内存后在内存中也必须是连续的）
数据的流向（不再需要经过CPU）读操作（数据输入）：I/O设备——内存，写操作（数据输出）：内存——I/O设备
主要缺点和主要优点
优点：数据传输以“块”为单位，CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内存，数据传输效率进一步增加。CPU和I/O设备的并行性得到提升。
缺点：CPU每发出一条I/O指令，只能读/写一个或多个连续的数据块。如果要读/写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU要分别发出多条I/O指令，进行多次中断处理才能完成。
通道控制方式：
通道：一种硬件，可以理解为是 “弱鸡版的CPU”。通道可以识别并执行一系列通道指令
通道控制方式流程：
完成一次读/写操作的流程（见右图）
CPU干预的频率极低，通道会根据CPU的指示执行相应的通道程序，只有完成一组数据块的读/写后才需要发出中断信号，请求CPU干预。
数据传送的单位每次读/写一组数据块
数据的流向（在通道的控制下进行）读操作（数据输入）：I/O设备——内存，写操作（数据输出）：内存——I/O设备
主要缺点和主要优点
缺点：实现复杂，需要专门的通道硬件支持
优点：CPU、通道、I/O设备可并行工作，资源利用率很高。
小结：
5.3、I/O软件的层次结构
设备独立性软件，又称设备无关性软件。与设备的硬件特性无关的功能几乎都在这一层实现
中断处理程序：
用户通过调用用户层软件提供的库函数发出的I/O请求
用户层软件通过“系统调用”请求设备独立性软件层的服务
设备独立性软件层根据LUT调用设备对应的驱动程序
驱动程序向I/O控制器发出具体命令
等待I/O完成的进程应该被阻塞，因此需要进程切换，而进 程切换必然需要中断处理
5.4、IO核心子系统
I/O调度：用某种算法确定一个好的顺序来处理各个I/O请求。如：磁盘调度（先来先服务算法、最短寻道优先算法、SCAN算法、C-SCAN算法、LOOK算法、C-LOOK算法）。当多个磁盘I/O请求到来时，用某种调度算法确定满足I/O请求的顺序。
同理，打印机等设备也可以用先来先服务算法、优先级算法、短作业优先等算法来确定I/O调度顺序。
操作系统需要实现文件保护功能，不同的用户对各个文件有不同的访问权限（如：只读、读和写等）。
在UNIX系统中，设备被看做是一种特殊的文件，每个设备也会有对应的FCB。当用户请求访问某个设备时，系统根据FCB中记录的信息来判断该用户是否有相应的访问权限，以此实现“设备保护”的功能。（参考“文件保护”小节）
5.5、假脱机技术（SPOOLing技术）
手工操作阶段：主机直接从 I/O设备获得数据，由于设备速度慢，主机速度很快。人机速度矛盾明显，主机要浪费很多时间来等待设备
批处理阶段引入了脱机输入/输出技术（用磁带完成）：引入脱机技术后，缓解了CPU与慢速I/O设备的速度矛盾。另一方面，即使CPU在忙碌，也可以提前将数据输入到磁带；即使慢速的输出设备正在忙碌，也可以提前将数据输出到磁带。
“假脱机技术”，又称“SPOOLing 技术”是用软件的方式模拟脱机技术。 SPOOLing 系统的组成如下：
要实现SPOOLing 技术，必须要有多道程序技术的支持。系统会建立 “输入进程”和 “输出进程”。
共享打印机原理分析：
独占式设备——只允许各个进程串行使用的设备。一段时间内只能满足一个进程的请求。
共享设备——允许多个进程“同时”使用的设备（宏观上同时使用，微观上可能是交替使用）。可以同时满足多个进程的使用请求。
当多个用户进程提出输出打印的请求时，系统会答应它们的请求，但是并不是真正把打印机分配给他们，而是由假脱机管理进程为每个进程做两件事：
在磁盘输出井中为进程申请一个空闲缓冲区（也就是说，这个缓冲区是在磁盘上的），并将要打 印的数据送入其中；
为用户进程申请一张空白的打印请求表，并将用户的打印请求填入表中（其实就是用来说明用户的打印数据存放位置等信息的），再将该表挂到假脱机文件队列上。当打印机空闲时，输出进程会从文件队列的队头取出一张打印请求表，并根据表中的要求将要打印的数据从输出井传送到输出缓冲区，再输出到打印机进行打印。用这种方式可依次处理完全部的打印任务
虽然系统中只有一个台打印机，但每个进程提出打印请求时，系统都会为在输出井中为其分配一个存储区（相当于分配了一个逻辑设备），使每个用户进程都觉得自己在独占一台打印机，从而实现对打印机的共享。
SPOOLing 技术可以把一台物理设备虚拟成逻辑上的多台设备，可将独占式设备改造成共享设备。
小结：
5.6、设备与备份回收
设备的固有属性可分为三种：独占设备、共享设备、虚拟设备。
独占设备——一个时段只能分配给一个进程（如打印机）
共享设备——可同时分配给多个进程使用（如磁盘），各进程往往是宏观上同时共享使用设备，而微观上交替使用。
虚拟设备——采用 SPOOLing 技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用（如采用 SPOOLing 技术实现的共享打印机）
从进程运行的安全性上考虑，设备分配有两种方式：
- 安全分配方式：为进程分配一个设备后就将进程阻塞，本次I/O完成后才将进程唤醒。（eg：考虑进程请求打印机打印输出的例子） 一个时段内每个进程只能使用一个设备
- 优点：破坏了“请求和保持”条件，不会死锁
- 缺点：对于一个进程来说，CPU和I/O设备只能串行工作
- 不安全分配方式：进程发出I/O请求后，系统为其分配I/O设备，进程可继续执行，之后还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞。一个进程可以同时使用多个设备
- 优点：进程的计算任务和I/O任务可以并行处理，使进程迅速推进
- 缺点：有可能发生死锁（死锁避免、死锁的检测和解除）
静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源
动态分配：进程运行过程中动态申请设备资源
设备控制表（DCT）：系统为每个设备配置一张DCT，用于记录设备情况
控制器控制表（COCT）：每个设备控制器都会对应一张COCT。操作系统根据COCT的信息对控制器进行操作和管理。
通道控制表（CHCT）：每个通道都会对应一张CHCT。操作系统根据CHCT的信息对通道进行操作和管理。
系统设备表（SDT）：记录了系统中全部设备的情况，每个设备对应一个表目。
设备分配的步骤：
- 根据进程请求的物理设备名查找SDT（注：物理设备名是进程请求分配设备时提供的参数）
- 根据SDT找到DCT，若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程。
- 根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。
- 根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。
- 注：只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动I/O设备进行数据传送
缺点：
用户编程时必须使用“物理设备名”，底层细节对用户不透 明，不方便编程
若换了一个物理设备，则程序无法运行
若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待
改进方法：建立逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名
逻辑设备表（LUT）建立了逻辑设备名与物理设备名之间的映射关系。某用户进程第一次使用设备时使用逻辑设备名向操作系统发出请求，操作系统根据用户进程指定的设备类型（逻辑设备名）查找系统设备表，找到一个空闲设备分配给进程，并在LUT中增加相应表项。 如果之后用户进程再次通过相同的逻辑设备名请求使用设备，则操作系统通过LUT表即可知道用户进程实际要使用的是哪个物理设备了，并且也能知道该设备的驱动程序入口地址。
逻辑设备表的设置问题： 整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复，适用于单用户操作系统每个用户一张LUT：不同用户的逻辑设备名可重复，适用于多用户操作系统
小结：
5.7、缓冲区管理
缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。
使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合（如存储器管理中所用的联想寄存器，由于对页表的访问频率极高，因此使用速度很快的联想寄存器来存放页表项的副本）
一般情况下，更多的是利用内存作为缓冲区，“设备独立性软件”的缓冲区管理就是要组织管理好这些缓冲区
缓冲区的作用：
- 缓和CPU与I/O设备之间的速度不匹配的矛盾
- 减少对CPU的中断频率，放款对CPU中断响应时间的限制
- 减少数据粒度不匹配的问题
- 提高CPU与I/O设备之间的并行性
5.7.1、单缓冲
注意：当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。
结论：采用单缓冲策略，处理一块数据平均耗时 Max(C, T)+M
5.7.2、双缓冲
结论：采用双缓冲策略，处理一个数据块的平均耗时为 Max (T, C+M)
使用单/双缓冲在通信时的区别：
注：管道通信中的“管道”其实就是缓冲区。要实现数据的双向传输，必须设置两个管道
5.7.3、循环缓冲
将多个大小相等的缓冲区链接成一个循环队列。
5.7.4、缓冲池
缓冲池由系统中共用的缓冲区组成。这些缓冲区按使用状况可以分为：空缓冲队列、装满输入数据的缓冲队列（输入队列）、装满输出数据的缓冲队列（输出队列）。另外，根据一个缓冲区在实际运算中扮演的功能不同，又设置了四种工作缓冲区：用于收容输入数据的工作缓冲区（hin）、用于提取输入数据的工作缓冲区（sin）、用于收容输出数据的工作缓冲区（hout）、用于提取输出数据的工作缓冲区（sout）
总结：
完结撒花~~
-------------本文结束感谢您的阅读-------------
本文链接： http://example.com/2020/11/05/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%EF%BC%88%E4%B8%89%EF%BC%89/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
