操作系统复习篇（中）：https://developer.aliyun.com/article/1446300
6.2请求分页存储管理方式
请求分页中的硬件支持
请求页表机制、缺页中断机构、地址变换机构
请求页表机制：
- 状态为：指示该页是否在内存
- 访问字段：记录该页在一段时间内被访问的次数
- 修改位：标志该页是否被修改过
- 外村地址：指示该页在外存中的地址（物理块号）
缺页中断机构：
- 在指令执行期间产生和处理中断信号
- 一条指令在执行期间，可能产生多次缺页中断
地址变换机构：与分页内存管理方式类似
请求分页中的内存分配
最小物理块数的确定：保证进程正常运行所需的最小物理块数
物理块的分配策略：
- 固定分配 局部置换
- 可变分配 全局置换
- 可变分配 局部置换
物理块分配算法：
- 平均分配算法
- 按比例分配算法
- 考虑优先权的分配算法
页面调入策略
何时调入页面：
- 预调页策略：预先调入一些页面到内存
- 请求调页策略:发现需要访问的页面不在内存是，调入内存
从何处调入页面：
- 如系统拥有足够的对换区空间，全部从对换区调入所需页面
- 如系统缺少足够的对换区空间，凡是不会被修改的文件，都直接从文件区调入；当换出这些页面时，由于未被修改而不必将它们重写磁盘，以后再调入时，仍从文件区直接调入
- UNIX方式：未运行过的页面，从文件区调入；曾经运行过但又被换出的页面，从对换区调入
页面调入方法
- 查找所需页在磁盘上的位置
- 查找一内存空闲块：
- 如果有空闲块，就直接使用
- 如果没有空闲块，使用页面置换算法选择一个“牺牲“内存块
- 将牺牲内存块的内容写到磁盘上，更新页表和物理块表
- 将所需页读入空闲块，更新页表
- 重启用户进程
6.3页面置换算法
种类
- 最佳置换算法（OPT）
- 先进先出置换算法（FIFO）
- 最近最久未使用置换算法（LRU）
- 最少使用算法（LFU）
- Clock置换算法
- 页面缓冲算法PBA
需要一个最小的缺页率
通过运行一个内存访问的特殊序列（访问序列），计算这个序列的缺页次数
最佳置换算法（OPT）
被置换的页将是之后最长时间不被使用的页
由于需要预知未来，因此无法实现，但可以用来作为置换算法的性能评价依据。
先进先出置换算法（FIFO）
思路：总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰
实现简单，性能较差，因为调出的页可能是经常访问的。很少单独使用
最近最久未使用置换算法（LRU）
核心思想：根据历史预测未来
LRU算法的硬件支持：寄存器、栈
寄存器：为内存中的每个页面设置一个移位寄存器
- 被访问的页面对应寄存器的Rn-1位置为1，定时右移
- 具有最小数值的寄存器所对应的页面为淘汰页
栈：保存当前使用的各个页面的页面号
- 被访问的页，移到栈顶
- 栈底时最近最久未使用页面的页面号
这种方法是最优置换算法的一种近似，但开销比较大
最少使用算法（LFU）
为内存中的每个页面设置一个移位寄存器，用来记录该页面的被访问频率
思路：缺页时，置换访问次数最少的页面
特征：
- 开销较大
- 开始时频繁使用，但以后不使用的页面很难置换
- 解决方法：计数定期右移
Clock置换算法
简单的Clock算法
- 每个页都与一个访问位相关联，初始值为0
- 当页被访问时访问位为1
- 置换时选择访问位为0的页；若为1，重新置为0
改进型Clock算法
- 除需考虑页面的使用情况外，还需增加置换代价
- 淘汰时，同时检查访问位A与修改位M
- A=0,M=0:最佳淘汰页
- A=0,M=1
- A=1,M=0
- A=1,M=1:最坏淘汰页
- 置换时，循环一次查找第一类、第二类页面，找到为止
页面缓冲算法PBA
影响效率的因素：页面置换算法、写回磁盘的频率、读入内存的频率
目的：
- 显著降低页面换进、换出的频率，减少了开销
- 可采用较简单的置换策略，如不需要硬件支持
具体做法：设置两个链表
- 空闲页面链表：保存空闲物理块
- 修改页面链表：保存已修改且需要被换出的页面等被换出的页面数目到达一定值时，再一起换出外存
6.4抖动与工作集
抖动：一个进程的页面经常换入换出
如果一个进程没有足够的页，那么缺页率将很高，将导致：
- CPU利用率低下
- 操作系统任务需要增加多道程序设计的道数
- 系统中将加入一个新的进程
产生抖动的原因
根本原因：
- 同时在系统中运行的进程太多
- 同时分配给每一个进程的物理块太少，不能满足进程运行的基本要求,致使进程在运行时，频繁换页，必须请求系统将所缺页面调入内存
抖动的发生与系统为进程分配物理块的多少有关
工作集
所谓工作集，时指在某段时间间隔t里进程是既要访问页面的集合，用 
表示， 
属于 
.
工作集的变化：
- 进程开始执行后，随着访问新页面逐步建立比较稳定的工作集
- 当内存访问的局部性区域位置大致稳定时，工作及大小也大致稳定
- 局部性区域的位置变化时，工作集快速扩张和收缩过度到下一个稳定值
抖动的预防方法
采取局部置换策略：只能在分配给自己的空间内进行置换
把工作集算法融入到处理机调度中
利用L=S准则调节缺页率：
- L是缺页之间的平均时间
- S是平均却页服务时间
- L>S说明很少发生缺页
- L<S说明频繁缺页
- L=S磁盘和处理机都可达到最大利用率
选择暂停进程
6.5请求分段存储管理方式
略
七、输入/输出系统
7.1I/O系统的功能、模型和接口
I/O系统管理的主要对象：I/O设备和对应的设备控制器
I/O系统的主要任务：完成用户提出的I/O请求，提高I/O速率和设备利用率
I/O系统的基本功能
- 能够隐藏物理设备的细节
- 能够保证OS与设备无关
- 能够提高处理机和I/O设备的利用率
- 能够对I/O设备进行控制
- 能够确保对设备的正确共享
- 能够处理错误
各种I/O模块之间的关系
I/O系统的上下接口：
- 上接口：I/O系统接口
- 下接口：软件/硬件接口
- 在上、下接口之间是I/O系统
I/O系统的分层：
- 中断处理程序
- 设备驱动程序
- 与设备无关的I/O软件
I/O系统接口
块设备接口：
- 块设备：数据的存取和传输都是以数据块为单位的设备，如磁盘，光盘，通常采用DMA I/O方式
- 隐藏了磁盘的二维结构
- 将抽象命令映射为底层操作
流设备（字符设备）接口：
- 字符设备：数据的存取和传输都是以字符为单位的设备，如键盘，打印机。不可寻址
- 通常采用中断驱动I/O方式
- get和put操作：字符设备采用顺序存取方式
- in-control指令：包含许多参数，每个参数均表示一个与具体设备相关的特定功能
网络通信接口：
- OS提供相应的网络软件和网络通信接口，以使计算机能通过网络同网络上的其他计算机进行通信
7.2I/O设备和设备控制器
I/O设备的类型
- 按使用特性分类：存储设备、I/O设备
- 按传输速率分类：
- 低速：键盘、鼠标等
- 中速：行式打印机等
- 高速 ：磁带机、磁盘机
- 按信息交换单位分类：块设备、字符设备
- 按设备的共享属性分类：独占设备、共享设备
设备与控制器之间的接口
通常，设备并不是直接与CPU进行通信，而是与设备控制器通信，因此，在设备与设备控制器之间应有一接口，在该接口中有三类信号个对应一条信号线，分别是：数据、状态、控制信号线。
设备控制器
- 主要功能：控制一个或多个I/O设备，以实现I/O设备和计算机之间的数据交换
- 是CPU与I/O设备之间的接口，接受CPU的命令，控制I/O设备工作
- 是一个可编制的设备：
- 当仅控制一个设备时，只有唯一地址
- 当控制多个设备时，有多个地址，并每一个地址对应一个设备
基本功能：
- 接受和识别命令
- 数据交换
- 标识和报告设备的状态
- 地址识别
- 数据缓冲区
- 差错控制
设备控制器的组成：
- 设备控制器与处理机的接口：实现CPU与设备控制器之间的通信，包括数据、地址和控制线
- 与设备的接口：连接设备
- I/O逻辑：实现对设备的控制
内存映像I/O
驱动程序将抽象I/O命令转换成具体的命令和参数等装入设备控制器的相应寄存器，由控制器执行这些命令，具体实施对I/O设备的控制。具体方法：
- 采用特定I/O指令：访问内存和设备需要两种不同的指令
- 采用内存映像I/O形式：在编址上不再区分内存单元地址和设备控制器中的寄存器地址，统一编址k。k在0~n-1范围时，为内存地址；若k>=n时，为某控制器的寄存器地址。统一了访问方法，简化了I/O编程
I/O通道
I/O通道的引入：
目的：使一些原来由CPU处理的I/O任务转由通道来承担，从而把CPU从繁杂的I/O任务中解脱出来。
通道是特殊处理机，与普通处理机的区别：指令类型单一、没有自己的内存（与CPU共享内存）
通道类型：
- 字节多路通道：按字节交叉方式工作的通道
- 数组选择通道：可以连接多台高速设备，但在一段时间内只允许一台设备传输数据，传输率高
- 数组多路通道：结合前两者优点，含有多个非分配型子通道
“瓶颈”问题：通道价格昂贵，造成通道不足。
解决方法：增加设备到CPU间的通路而不增加通道
多路方式不仅解决了“瓶颈”问题，而且提高了系统的可靠性
I/O设备的控制方式
- 用轮询的可编程I/O方式（基本不用）：
- 实现容易但效率偏低，CPU会长期处于忙等
- 使用中断的可编程I/O方式（广泛采用）：
- 当某进程要启动某个I/O设备工作时，便由CPU向相应的设备控制器发出一条I/O命令，然后立即返回继续执行原来的任务。设备控制器域是按照命令的要求去控制指令的I/O设备。此时，CPU与I/O设备并行操作
- 直接存储器访问方式（DMA）：进一步减少CPU对I/O设备的干预
- 数据传输的基本单位是数据块
- 所传送的数据是从I/O设备直接送入内存的，或者相反
- 仅在传送一个或多个数据块的开始和结束时，才需CPU干预
- I/O通道方式：是DMA方式的发展，可进一步减少CPU的干预
- 是对一组数据快以读/写及有关的控制和管理作为单位干预
- 可实现CPU、通道和I/O设备三者的并行操作
- 通道程序：由一系列通道指令构成，通道指令不同于CPU指令
7.3中断和中断处理程序
介绍
中断和陷入：
- 中断：CPU对I/O设备发来的中断信号的一种响应
- 陷入：CPU内部事件引起的中断
中断向量表：存放每个设备的中断处理程序的入口地址，并为每个设备的中断请求作为一个中断号，对应于中断向量表中的一个表项
中断优先级：系统为每个中断源规定不同的优先级
对多中断的处理方式
当处理及正在处理一个中断时，又来了一个新的中断请求，有两种处理方式：
- 屏蔽（禁止）中断
- 嵌套中断
Linux中的中断处理
采用了上半部和下半部机制：
- 上半部：中断处理程序。（简单快速，执行时禁止一些或全部中断）
- 下半部：一些虽然与中断有关但是可以延后执行的任务（稍后执行，执行时可以响应所有的中断）
中断处理程序的设计：
- 注册中断
- 处理中断
- 注销中断
7.4设备驱动程序
略
7.5与设备无关的I/O软件
略
7.6用户层的I/O软件
略
7.7缓冲区管理
缓冲区是一个存储区域，可以由专门的硬件组成；更多的是利用内存。
引入缓冲区的原因：
- 缓和CPU与I/O设备间速度不匹配的矛盾
- 减少对CPU的中断频率，放宽对CPU中断响应时间的限制
- 解决数据粒度不匹配的问题
- 提高CPU与I/O设备之间的并行性
单缓冲
每当用户进程发出一I/O请求时，操作系统便在主存中位置分配一缓冲区
在设备输入时
- T:从磁盘把一块数据输入到缓冲区的时间
- M:操作系统将该缓冲区中的数据送到工作区的时间
- C:CPU对这块数据处理的时间
- 当T>C，系统对每一块数据的处理时间为M+T（C忽略）
- 反之，则为M+C
- 系统对每一块数据的处理时间为：Max(C,T)+M
双缓冲
- 在设备输入时，先将数据送入第一缓冲区，装满后便转向第二缓冲区
- 此时操作系统可以从第一缓冲区移出数据，并送入用户进程，接着由CPU对数据进行计算
- 在双缓冲时，系统处理一块数据的时间可以粗略地认为是Max(C,T),如果C>T，则可使CPU不必等待设备输入
环形缓冲区
当输入和输出两者的速度相差悬殊，双缓冲的效果则不够理想，不过可以随着缓冲区数量的增加，使情况有所改善。
多个缓冲区：
- 在循环缓冲中包含多个缓冲区，其每个缓冲区的大小相同
- 作为输入的多缓冲区可分为三类：
- 用于装输入数据得空缓冲区R
- 已装满数据的缓冲区G
- 计算进程正在使用的现行工作缓冲区C
- 多个指针：
- 作为输入的缓冲区可设置3个指针：
- 用于指示及算您成下一个而用缓冲区G的指针Nextg
- 指示输入进程下次可用的空缓冲区R的指针Nexti
- 用于指示计算进程正在使用的缓冲区C的指针Current
缓冲池
当系统较大时，将会有许多循环缓冲，这不仅要消耗大量的内存，且利用率不高。
为了提高缓冲区利用率，引入公共缓冲池，在池中设置了多个可供若干个进程共享的缓冲区
缓冲池的组成：
- 空闲缓冲队列：空闲缓冲区所链城的队列
- 输入队列：装满输入数据的缓冲区所链成的队列
- 输出队列：装满输出数据的缓冲区所链成的队列
- 4中工作缓冲区：收容输入、提取输出、收容输出、提取输入缓冲区
缓存和缓冲
- 缓冲可以保存数据项的唯一的现有版本
- 缓存指示提供一个位于其他地方的数据项的更快存储副本
- 有时，同一个内存区，既可以是缓冲，也可以是缓存
7.8磁盘性能概述和磁盘调度
磁盘结构
- 盘面（磁头）：磁盘设备可能包含一个或多个盘片，每个盘片分为一个或两个盘面，每个面上有一个读写磁头
- 磁道（柱面）：每个盘面可分为若干磁道
- 扇区：每条磁道逻辑上分成若干大小相同的扇区。每个扇区的大小相当于一个盘块（数据块）
- 每条磁道上可存储相同数目的二进制位
- 磁盘密度即每英寸中所存储的位数，显然是内层磁道叫外层磁道的密度高
容量=柱面*磁头*扇区
磁盘的类型
分类一：硬盘、软盘
分类二：单片盘、多片盘
分类三：
- 固定头：每个磁道上都有一个读写磁头
- 并行方式读/写，有效提高I/O速度
- 主要用于大容量磁盘
- 移动头：每个盘面仅有一个磁头，能移动寻道
- 串行方式读/写，I/O速度较慢
- 广泛应用于中、小磁盘设备中
磁盘访问时间
磁盘在工作时是以恒定速率旋转
为了读写：
- 磁头必须移动到要求的磁道上
- 等待所制定的山区开始位置旋转到磁头下
- 开始读写数据
磁盘的访问时间=寻道时间+旋转延迟时间+传输时间
早期的磁盘调度算法
磁盘调度的目标， 使使磁盘的平均寻道时间最小
- 先来先服务FCFS
- 最短寻道时间优先SSTF
- SCAN算法
- 循环扫描算法C-SCAN
- CLOCK
- NStepSCAN算法
- FSCAN算法
先来先服务FCFS调度算法
最简单的磁盘调度算法，但平均寻道时间可能较长
最短寻道时间优先SSTF
选择这样的进程，其要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但不保证平均寻道时间最短（贪心算法）
SSTF明显优于FCFS,但可能会出现饥饿
SCAN算法
也称：电梯调度算法。不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头当前的移动方向
磁臂从磁盘的一段向另一端移动，沿途响应服务请求，当到达另一端是，磁头改变移动方向，继续处理。磁头在磁盘上来回扫描
循环扫描算法C-SCAN
提供比SCAN算法更均匀的等待时间
磁头从磁盘一端移动到另一端，随着移动不断处理请求。不过，当磁头移动到另一端时，马上返回到磁盘开始，返回时并不处理请求。
CLOCK
C-SCAN的一种形式。磁头之移动到一个方向上最远的请求位置。戒指，马上回头，而不是继续道磁盘的尽头
NStepSCAN算法
“磁臂粘着”现象：进程反复请求对某一磁道的I/O操作
将磁盘请求队列分为若干个长度为N的子队列；按FCFS算法依次处理子队列；每个子队列使用SCAN算法
FSCAN算法
是 NStepSCAN算法的简化：
请求队列分为两个子队列：
- 当前所有请求队列，按SCAN算法调度
- 扫描期间，新出现的请求队列，推迟到下一次扫描时处理
八、文件管理
8.1文件和文件系统
数据项、记录和文件
数据项：
- 基本数据项：描述一个对象的某种属性，又称字段
- 组合数据项：由若干个基本数据项组成
记录：
- 记录时一组相关数据项的集合，用于描述一个对象在某方面的属性
- 关键字：唯一能表示一个记录的数据项
- 如；学号、学号+课程号
文件：具有文件名的一组相关元素的集合
- 有结构文件（记录）、无结构文件（字符流）
- 在文件系统中温嘉三年hi最大的单位，描述了一个对象集
文件类型
按用途分类：
- 系统文件
- 用户文件
- 库文件
按文件中数据的形式分类：
- 源文件
- 目标文件
- 可执行文件
按存取控制属性分类：
- 只执行文件
- 只读文件
- 读写文件
按组织形式和处理方式分类：
- 普通文件
- 目录文件
- 特殊文件
文件系统的层次结构
对象及其属性
- 对象：文件、目录、磁盘存储空间
对对象操纵和管理的软件集合
- 文件管理系统的核心部分
文件系统的接口
- 命令接口
- 程序接口
文件系统的功能
- 对文件存储空间的管理
- 对文件目录的管理
- 用于将文件的逻辑地址转换为物理地址的机制
- 对文件读和写的管理
- 对文件的共享和保护
与文件系统有关的软件
- I/O控制层：文件系统最底层，设备驱动程序层
- 基本文件系统层：处理内存与磁盘之间数据块的交换
- 基本I/O管理程序：完成与磁盘I/O有关的事物
- 逻辑文件系统：处理与记录和文件相关的操作
文件操作
最基本的文件操作：
- 创建文件、删除文件、读文件、写文件
- 设置文件的读/写位置
文件的打开和关闭操作：
- 打开：系统将文件从外存拷贝到内存打开文件表的一个表目中
- 关闭：把文件从打开文件表的表目中删除
其他文件操作：
- 重命名、改文件拥有者、查询文件状态等
- 创建/删除目录
8.2文件的逻辑结构
文件结构
- 文件的逻辑结构：从用户观点所观察的文件组织形式
- 文件的物理结构：文件的存储结构，指系统将文件存储在外村上所形成的一种存储组织形式
- 不仅与存储介质的存储性能有关
- 也与所采用的外村分配方式有关
文件的逻辑结构和物理结构，都影响文件的检索速度
文件名和文件类型
按文件是否有结构分类：
- 有结构文件（记录式文件）
- 定长记录
- 变长记录
- 无结构文件（流式文件）
- 源程序、可执行文件、库函数
有结构文件按文件的记录方式分类：
- 顺序文件
- 索引文件
- 索引顺序文件
顺序文件
串结构：按存入时间的先后顺序，记录间的顺序与关键字无关，但检索比较费时
顺序结构：指定一个字段为关键字，所有记录按关键字排序。检索时可用有效的查找算法。
优点：有利于大批记录读写、存取效率最高、可存储在顺序存储设备上
缺点：增删改查效果差
索引文件
按关键字建立索引：
- 为边长记录文件建立一张索引表
- 索引表按关键字排序
- 实现直接存取
具有多个索引表的索引文件：
- 为顺序文件建立多个索引表
- 为每一个可能会成为索引条件的域配置一张索引表
顺序索引文件
- 有效克服了变长记录文件不便于直接存取的缺点
- 保留了顺序文件的关键特征：记录按关键字的顺序组织
- 新增了2个新特征：
- 引入文件索引表:实现随机访问
- 增加溢出文件：记录新增、删除和修改的记录
