操作系统原理笔记(三)
七、设备管理
7.1 设备管理概述
设备分类
- 块设备：以块为单位传输信息的设备，通常为存储设备，如磁盘、磁带、光驱
- 字符设备：以字符为单位将信息从计算机外部输入到计算机内或从计算机内输出到外部，如键盘、显示器、打印机
- 网络设备：负责计算机之间的信息传输，如以太网、无线、蓝牙
设备管理的目标
提高设备利用率
方便用户使用：提供使用方便且独立于设备的接口
设备管理的功能
状态追踪：动态记录设备状态
设备分配和回收
- 静态分配：程序进入系统的时候就进行分配，退出系统的时候回收全部资源
- 动态分配：进程提出设备申请时进行分配，使用完毕立即收回
设备控制：实施设备驱动和中断处理的工作
设备独立性
用户在程序中使用的设备与实际使用的设备无关——在用户程序中，只使用逻辑设备名
逻辑设备名：用户自己指定的设备名，可以更改
物理设备名：系统提供的设备的标准名称，是永久的，可以更改的
实现方式
- 在高级语言中用软通道实现
- 在批处理系统中，用联接说明语句来定义
- 在交互系统中，用指派命令来定义
设备控制块：记录设备的硬件特性，连接和使用情况的一组数据
- 设备名——设备的物理名称
- 设备属性
- 命令转换表——包含设备特定的I/O例程地址，表示设备能执行何种I/O操作，若不具备相应功能则填-1
7.2 I/O控制
7.2.1 I/O控制方式
- 循环测试I/O方式
- I/O中断方式
- DMA方式
- 通道方式
7.2.2 I/O子系统
在应用程序提供I/O应用接口
每个通用设备类型都通过一组标准函数（以及接口）来访问.
设备驱动程序
能直接控制设备运转的程序，它根据各类设备的特点和性能来编写
每一类设备有一个相应的设备驱动程序，能控制同类中多台物理设备同时工作
设备I/O完成或出错时产生中断，由该类设备的中断处理程序处理
设备处理进程
为每一类设备设置一个设备处理进程
没有I/O请求时，该进程睡眠
当有I/O请求来到时，该进程被唤醒，进行设备驱动工作
I/O接口程序
首先把逻辑设备转化为物理设备
合法性检查，这个设备能否执行这个操作
形成I/O请求块，发送给设备处理进程
处理顺序
用户进程请求IO
首先进入I/O过程
由I/O过程进入I/O处理进程
I/O处理进程启动I/O设备进行I/O操作，进入等待状态
I/O设备执行完I/O操作后进入中断唤醒I/O处理进程
I/O处理进程则唤醒调用该I/O的用户进程
7.3 缓冲技术(★)
7.3.1 缓冲技术概述
两种不同速度的设备之间传输信息的平滑传输过程
缓冲的类别
- 硬件缓冲：使用缓冲器——用来暂时存放数据的一种存储装置
- 软件缓冲：在I/O操作期间用来临时存放I/O数据的一块存储区域
缓冲的目的
- 处理数据流的生产者与消费者速度差异
- 协调传输数据大小不一致的设备
7.3.2 缓冲类型
单缓冲
读设备得数据
- 首先获得一个空的缓冲区
- 设备把物理记录送到缓冲区中
- 用户请求数据时，系统将依据逻辑记录特性从缓冲区提取数据并发送到用户进程存储区
- 如果用户请求数据且缓冲区中没有数据时，进程被迫等待
写数据到设备
- 首先获得一个空的缓冲区
- 用户将一个逻辑记录从进程存储区送到缓冲区中
- 当缓冲区写满时，系统将缓冲区内容作为物理记录写到设备上
- 当进程输出信息且缓冲区已满时 ，进程被迫等待
双缓冲
两个缓冲区
数据输入
- 输入设备首先填满buf1
- 进程从buf1提取数据的时候，输入设备填满buf2；当缓冲区一个空，一个满的时候就可以交换
- 即进程提取一个缓冲区，设备往另外一个缓冲区输入数据
数据输出
- 进程首先填满buf1
- 设备从buf1提取数据时，进程往buf2输出数据；当缓冲区一个空，一个满的时候就交换
环形缓冲
- 缓冲区构成一个环形链表，有读指针和写指针
- 读写元素分别从读指针和写指针写数据
缓冲池
- 将系统内所有的缓冲区统一管理起来，形成能用于输入/输出的缓冲池
- 缓冲池通常由若干大小相同的缓冲区组成，是系统的公用资源，任何进程都可以申请使用缓冲池中的各个缓冲区
7.3.3 UNIX缓冲区管理
- 缓冲管理数据结构
- 缓存数组：含有磁盘上的数据的存储器数组
- 缓存首部：描述缓冲区特性的数据结构
- 设备号，使用该缓冲区的设备号
- 块号，由设备号指出的设备上相对于第0块的块号
- 状态信息flag
- 指向数据区域的指针
- 设备缓冲区队列前后向指针
- 空闲缓冲区队列前后向指针
- 队列结构
- 设备缓冲区队列（b链）：与某类设备有关的所有缓冲区
- 空闲缓冲区队列（av链）：可供重新分配使用的空闲缓冲区组成的队列
- 缓冲管理算法
- 当某个缓冲区被分配用于读/写某设备时：置B_ BUSY=1，位于b链上，不在av链上；
- 当读/写操作结束时：释放缓冲区，置B_BUSY=0，仍留在b链上，并送入av链尾；
- 若进程需要的信息在缓冲区中时：在该设备的b链上找到，置B_BUSY=1；从av链上摘除，使用完后，送入av链队尾；
- 对空闲缓冲区队列的处理：当需要一个空闲缓冲区时，总是取av链的首元素；一个使用过的缓冲区释放时，送入av链队尾——实现了精确的LRU算法；
- 对延迟写的处理：当一个具有延迟写标记的缓冲区移到av链头，要用于分配时，立即进行写操作。从av链上摘除，使用完后又送入av头部
7.4 设备分配
7.4.1 分配算法(★)
先来先服务
优先级高者优先
特定设备分配算法——磁盘调度算法
磁盘访问时间
寻道时间$T_s$
- 把磁臂（磁头）移动到指定磁道上所经历的时间
- 启动磁臂的时间s与磁头移动n条磁道所花费的时间之和，即$T_s=s+m\times n$
- 其中，m是与磁盘驱动器速度有关的常数；对一般磁盘，m=0.2；对高速磁盘，m ≤ 0.1，磁臂的启动时间约为2ms
旋转延迟时间$T_{\tau}$
- 指定扇区移动到磁头下面所经历的时间
- 对于硬盘，旋转速度约为5400r/min，每转需时11.1ms， 平均旋转延迟时间为5.55 ms
- 对于软盘，旋转速度为300r/min或600r/min，平均旋转延迟时间为50~100ms
传输时间$T_t$
- 把数据从磁盘读出或向磁盘写入数据所经历的时间
- $T_t$的大小与每次所读/写的字节数b和旋转速度有关，即$T_t=\frac{b}{rN}$
- 其中，r为磁盘每秒钟的转数，N为一条磁道上的字节数
访问时间：$T_a=T_s+T_{\tau}+T_t$
先来先服务FCFS
- 按进程请求访问磁盘的先后次序进行调度
- 假设有如下请求序列： 98, 183, 37, 122, 14, 124, 65, 67，磁头当前的位置在53
- 寻道序列如下
- 按进程请求访问磁盘的先后次序进行调度
| 下磁道 | 移道数 |
|---|---|
| 98 | 45 |
| 183 | 85 |
| 37 | 146 |
| 122 | 85 |
| 14 | 108 |
| 124 | 110 |
| 65 | 59 |
| 67 | 2 |
| 总道数 | 640 |
| 平均 | 80 |
最短寻道时间优先SSTF
- 选择从当前磁头位置所需寻道时间最短的请求
- 寻道序列如下
| 下磁道 | 移道数 |
|---|---|
| 65 | 12 |
| 67 | 2 |
| 37 | 30 |
| 14 | 23 |
| 98 | 84 |
| 122 | 24 |
| 124 | 2 |
| 183 | 59 |
| 总道数 | 236 |
| 平均 | 29.5 |
扫描算法（SCAN、电梯算法）
- 磁头从磁盘的一端开始向另一端移动，沿途响应访问请求，直到到达了磁盘的另一端，此时磁头反向移动并继续响应服务请求
- 寻道序列如下
| 下磁道 | 移道数 |
|---|---|
| 65 | 12 |
| 67 | 2 |
| 98 | 31 |
| 122 | 24 |
| 124 | 2 |
| 183 | 59 |
| 37 | 146 |
| 14 | 23 |
| 总道数 | 299 |
| 平均 | 37.4 |
循环扫描算法（CSCAN）
- 规定磁头从磁盘的一端开始向另一端单向移动，沿途响应访问请求
- 寻道序列如下
| 下磁道 | 移道数 |
|---|---|
| 65 | 12 |
| 67 | 2 |
| 98 | 31 |
| 122 | 24 |
| 124 | 2 |
| 183 | 59 |
| 14 | 169 |
| 37 | 23 |
| 总道数 | 322 |
| 平均 | 40.3 |
7.4.2 分配策略
- 独享分配：分配独享设备——在一个作业整个运行期间占用的设备
- 共享分配：分配多个作业、进程共同使用的共享设备
- 虚拟分配
- 所谓虚拟技术，是在一类物理设备上模拟另一类物理设备的技术，是将独占设备转化为共享设备的技术。
- 通常把用来代替独占型设备的那部分外存空间 （包括有关的控制表格）称为虚拟设备。
- 进程先把元素写入位于磁盘中的虚拟设备
- 然后虚拟设备分配管理器再把磁盘中的虚拟设备数据写入物理设备
- SPOOLING（一种实例虚拟设备分配策略）
- 预输入
- 应用程序需要数据之前，OS已经把所需要的数据放入输入井中存放，应用程序可以直接从输入井获取数据
- 缓输出
- 应用程序执行的时候，将输出数据写入输出井中，当应用程序执行完毕后，OS将输出井的数据输出
- 利用通道和中断技术，在主机控制之下，由通道完成输入输出工作。系统提供一个软件系统 （包括预输入程序、缓输出程序、井管理程序、预输入表、缓输出表）。它提供输入收存和输出发送的功能，使外部设备可以并行操作。这一软件系统称为SPOOLING系统。
- 基础
- 辅存空间
- 通道和中断
- 数据结构
- 软件
- 预输入，缓输出，井管理程序
- 预输入
八、文件系统
8.1 文件系统概述
文件的概念
在逻辑上上具有完整意义的信息集合，以文件名作为标识
文件是具有符号名的信息项（数据项、记录）的集合
文件的属性
文件名：每个文件有一个给定的名字，包括文件符号名和内部标识符
- 用户使用文件符号名来标记文件
- 系统使用内部标志符来标记文件
文件拓展名：标记文件的使用特征
文件属性：包含文件类别、保护级等信息，如文件大小、文件所有者、文件创建时间、最后修改时间
文件系统
文件系统是操作系统中负责管理和存取文件信息的软件机构
组成
- 管理文件所需的数据结构，如目录表、文件控制块、存储分配表
- 管理程序
功能
- 用户视角：“按名存取”的功能
- 系统视角：辅存空间管理、构造文件结构、文件共享、存取文件的方法、文件保护、一组文件操作命令
文件组织两种结构
逻辑结构（用户角度）
物理结构（系统角度）：在物理存储器上的表现形式
逻辑记录：文件中按信息在逻辑上的独立含义来划分的信息单位，对文件进行存取操作的基本单位
物理记录：在存储介质上，由连续信息组成的一个区域称为磁盘块，也可以叫物理记录
8.2 文件的逻辑结构与存取方法
文件的逻辑结构
流式文件
- 流式文件是相关的有序字符的集合，是无结构的，仅仅是一堆字节组成的字符的集合
- 存取方式：按信息的个数或以特殊字符为界进行存取
记录式文件
- 记录式文件是一种有结构的文件，在逻辑上被看成一组连续顺序的记录的集合
文件存取方法
顺序存取
- 后一次存取总是在前一次存取的基础上进行的
- 只有取完第一个才能取第二个
- 不必给出具体的存取位置
随机存取
- 用户以任意次序请求某个记录，可以随便取第n个元素
- 需指出起始存取位置（例如记录号）
8.3 文件的物理结构(★)
连续文件
一个文件分配在磁盘连续区域的物理块
文件在文件目录里记录的信息：文件符号名，文件的第一个磁盘块块号，文件占据的磁盘块数
串联文件
- 文件结构由按顺序串联的若干个物理块组成，每个物理块的最后一个字作为链接字用来指示后续物理块的物理地址
- 文件在文件目录里记录的信息：文件符号名，文件的第一个磁盘块块号（剩下的磁盘块号通过每个磁盘块的链接字指示）
- 文件分配表FAT
- 把串联文件中的链接字集中在一个结构中，既保持了串联文件的优点，也克服了其随机存取速度慢的缺点
- 即以链接方式存储文件的系统中记录磁盘分配和跟踪空白磁盘块（簇）的数据结构
- 该表在文件系统格式化后产生，共包含N个表项，每个表项对应一个簇，编号从0开始直至N-1（N为磁盘中簇的总数）
- 每个表项中的内容为存放文件数据的下一个簇的簇号。
- 文件的首地址（第一个簇号）存放在目录中，从目录中找到文件的首地址后，就能找到文件在磁盘上的所有存放地址
- 在FAT表中，全0表示空闲簇，全1表示文件结尾簇，其余均表示文件的下一簇
索引文件
系统为每个文件建立逻辑块号与物理块号的对照表，这张表称为该文件的索引表
索引文件由数据块和索引表构成
组织类型
- 直接索引：索引表就是存储数据的物理块块号
- 一级间接索引
- 文件目录项中的表项——一级间接索引表块的块号
- 一级间接索引表块的表项——文件逻辑记录所在的磁盘块号
- 二级间接索引
- 文件目录项中的表项——二级间接索引表块的块号
- 二级间接索引表块的表项——一级间接索引表块的块号
- 一级间接索引表块的表项——文件逻辑记录所在的磁盘块号
8.4 文件目录(★)
文件控制块FCB
- 文件系统为每个文件建立的唯一的数据管理结构
- 文件标识和控制信息：文件名、用户名、文件权限 、文件类型
- 文件逻辑结构信息
- 文件物理结构信息
- 文件使用信息
- 文件管理信息
文件目录
文件目录是记录文件控制块FCB信息的数据结构
文件目录项：记录一个文件的信息，存在两种两种目录项
普通文件的FCB
子目录的目录文件的FCB
文件目录在系统里面是以目录文件的形式存在的，是一个具体的文件
目录文件至少包含两个目录项
- 当前目录项
- 父目录项
一级文件目录
- 已建立的所有文件的文件名、存放地址和有关的说明信息都放在一张表中
- 不允许文件重名
- 在多用户环境中，易出现重名问题
二级文件目录
- 将文件目录分成主目录和用户文件目录两级
- 每个用户建立一个用户文件目录，登记该用户建立的所有文件的相关信息
- 主目录登记系统中各个用户文件目录的相关信息
树形文件目录
- 目录文件就包含了这个目录下面所有数据文件和目录文件对应的文件目录项
- 数据文件一定在树叶上
- 树形结构中每一层就是一个目录
文件路径名：多级目录中，文件的路径名是由根目录到该文件的通路上所有目录文件符号名和该文件的符号名组成的字符串，相互之间用分隔符分隔
8.5 文件存储空间管理
- 空闲文件目录
- 将所有空闲块记录在一个表中，即空闲块表
- 表项内容：起始块号，空闲块个数
- 空闲块链：把所有空闲块链成一个链
- 位示图
- 用一串二进制位反映磁盘空间中分配使用情况
- 每个物理块对应一位，已分配物理块为1，否则为0
- 申请物理块时，可以在位示图中查找为0的位，返回对应物理块号
- 归还时，将对应位置为0
8.6 文件的共享与安全(★)
文件共享：某一个或者某一部分的文件让多个用户共同使用
文件安全：文件本身不得被未经文件所有者授权的任何用户存取
保护方法：对用户的权限进行验证，是指用户在存取文件之前，需要检查用户的存取权限是否符合规定
文件查找
当前目录
- 当前目录是当前用户正在使用的文件所在的目录
- 当指定当前目录后，用户对文件的所有访问都是相对于”当前目录“进行的
链接技术
- 一个目录中的一个表目直接指向另一个目录表目对应的物理位置
UNIX/Linux的链接
硬链接
- 不同的目录项引用同一个文件，$I$结点相同
- 在索引文件中增加链接计数，用于记录共享数量
- 硬链接与源文件等价，两个文件的物理结构项一样
- 不能链接目录文件
- 删除源文件后，硬链接文件可照常使用
- 硬链接只限于本文件系统
- 硬链接可以加快文件查找速度
软链接/符号链接
- 创建一个LINK类型的新文件，文件中仅包含被链接文件的路径名
- 删除源文件后，软链接文件的操作会失败
- 软链接可以链接到处于不同文件系统的文件及目录
- 软链接不可以加快文件查找速度
8.7 文件操作与文件备份
文件的操作
文件的打开
- 首先获得文件路径名
- 按照名字查找文件目录结构获得目录项找到FCB（注意，只用找到FCB就可以，对应的数据块不需要）
- 存入活跃文件目录表
- 建立文件读写状态信息表，将访问指针指向文件首
文件关闭
- 检查参数，获得fd；
- 在打开文件表和文件读写状态信息表中把对应文件占用的空间释放
- 如果“活跃文件目录表”中文件控制块不再使用，则释放该文件控制块所占的内存空间
文件创建
- 检查参数合法性
- 建立一个文件控制块，并在目录表中建目录项。
- 将参数填入文件控制块
- 分配文件所存放的外存空间（也可在写数据时分配），将文件物理存储信息填入文件控制块中
文件删除
- 检查参数，得到文件名（路径名）
- 按名查找文件目录结构得到目录项，找到文件的文件控制块
- 按文件控制块中的定位信息（如索引表）释放文件所占外存空间
- 从文件目录结构中删除文件控制块及目录项
文件相关的表
进程控制块里面有有打开文件表，记录这个进程打开了什么文件
对于进程的打开的许多文件有一个读写状态信息表，记录进程读或者写一个文件写到文件的哪里了
活跃文件目录表，就是记录所有打开过的文件的FCB，读写状态信息表中就指向活跃文件目录表
文件备份
周期性转储：过一个周期就把存储器所有内容存一遍
增量性转储：以文件为单位，定期转储上次转储后改过的新文件
8.8 UNIX文件系统(★)
8.8.1 文件系统概述
文件特点
- 树型文件目录结构
- 可安装拆卸的文件系统
- 文件是无结构的字符流式文件
- 将外部设备与文件一样对待
索引表
索引文件结构
- 文件索引节点
- 把文件目录项中除了名字以外的信息全部存放到一个磁盘的数据块上，这种数据块称为磁盘索引节点，简称$I$节点
- 包含文件所有者、文件类型、文件存取许可权、文件链接数目、文件长度、地址索引表
- 每个$I$节点的大小为$128$字节
- 一个$UNIX$文件系统中能够创建的文件数量，既受到索引节点区中$I$节点数量的约束，又受到数据区中数据块数量的约束
- 文件索引节点
地址索引表
- UNIX第七版：使用地址索引表$i_addr[8]$描述物理结构
- $i_addr[0]-i_addr[7]$为直接索引表
- 最大为$8\times$磁盘块大小
- 大型文件
- $i_addr[0]-i_addr[6]$为一级间接索引表
- 最大为$7\times256\times$磁盘块大小
- 巨型文件
- $i_addr[0]-i_addr[6]$为一级间接索引表
- $i_addr[7]$为二级间接索引表
- 最大为$(7\times256+256\times256)\times$磁盘块大小
- UNIX V：使用地址索引表$i_addr[13]$描述物理结构
- 前10个用于直接索引
- 第11个用于一级间接索引
- 第12个用于二级间接索引
- 第13个用于三级间接索引
- 最大为$(10+256+256^2+256^3)\times $磁盘块大小
- UNIX第七版：使用地址索引表$i_addr[8]$描述物理结构
文件目录结构
- 每个目录项包含16个字节，第1、2字节为相应文件的辅存$I$节点号，后14个字节为文件名
树型目录结构
每个文件系统都有一个根目录文件，它的辅存i节点是相应文件存储设备上辅存索引区中的第一个。
文件目录项存储的是索引节点的节点号，要获得文件，要先打开索引节点，在索引节点中根据节点地址寻找文件本身的数据.（或者是目录或者是数据）
打开文件的结构
活动i节点表
- 当执行打开文件操作时，将文件辅存$I$节点的有关信息拷贝到主存，形成活动$I$节点表，他由若干个活动$I$节点组成
系统打开文件表
- 一个文件可以被不同进程以相同或不同路径名打开，因此通过构造系统打开文件表记录所有进程打开过什么文件
- 读写标志：表示文件的打开模式，读或者写
- 引用计数：多少个进程用该读写标志打开该文件
- 指向该文件对应的主存索引节点
- 一个文件可以被不同进程以相同或不同路径名打开，因此通过构造系统打开文件表记录所有进程打开过什么文件
用户文件描述符表
- 每个进程里面的结构，用来记录这个进程用何种方式打开过何种文件，会指向系统打开文件表中的一个表项
子进程共享父进程的“系统打开文件表项” ，该表项的文件打开计数f_count加1，子进程直接使用父进程open()操作返回的文件描述符fd即可访问该文件
父进程的close()操作不影响子进程对该文件的使用
父子进程独立运行后，各自open的文件就不再共享
8.8.2 文件存储空间的管理
引导块：大小为一个磁盘块，包含引导程序
管理块：记录文件系统各种数据
- 直接管理的空闲块数s_nfree
- 空闲块号栈s_free[]
- 直接管理的空闲$I$节点数s_ninode
- 空闲$I$节点号栈s_inode[]
空闲磁盘块的管理——成组链接法
将空闲表和空闲链两种方法相结合
系统初启时，文件存储区是空闲的；将空闲块从尾倒向前，每100块分为一组 (最后一组为99块)，每一组的最后一块作为索引表，用来登记下一组100块的物理块号和块数；最前面一组（可能不足100块）的物理块号和块数存放在管理块的s_free[100]和s_nfree中
分配算法
- s_nfree-1
- 如果s_nfree为0了，就把s_free[0]也就是下一个管理块载入到内存中
回收算法
- s_nfree+1
- 如果达到了100，就把当前管理块释放到磁盘中，然后初始化，s_free[0]为原来释放到的那个磁盘块块号
