操作系统复习篇（中）：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个新特征：

引入文件索引表:实现随机访问
增加溢出文件：记录新增、删除和修改的记录

操作系统复习篇（下）