操作系统中
1、死锁的概念
什么是死锁
- 在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象
- 发生死锁至少有两个或两个以上的进程同时发生死锁，发生死锁后，若无外力干涉，这些进程都无法向前推进，发生死锁的进程一定是在阻塞态
- 饥饿的概念：
- 由于长期得不到想要的资源，某进程无法向前推进的现象，比如SPF如果有源源不断的短进程到来，则长进程一直无法获得处理机
- 死循环的概念
- 某进程在执行的过程中一直跳不出某个循环的现象，有时是因为程序bug导致的，有时是程序员故意为之
- 死锁、饥饿、死循环的异同
- 异如上
- 同：都是进程无法顺利向前推进的现象(故意设计的死循环除外)
死锁产生的条件
1、互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁
2、不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
3、请求和保持条件：进程已经至少保持了一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放
4、循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求
注意：发生死锁的时候一定有循环等待，但是发生循环等待的时候未必死锁，因为如果同类资源的数量大于1，当该类资源又进程释放的时候，死锁结束。如果每类资源只有1个，那就是充分必要条件了
什么时候会发生死锁
- 1、对系统资源的竞争。对不可剥夺资源的竞争可能会引起死锁，对可剥夺的资源不会产生
- 2、进程推进顺序非法。请求和释放资源的顺序不当，比如，并发执行的进程P1、P2分别申请并占有了资源R1,R2,但是之后P1进程又申请资源R2，P2进程申请资源R1，这样会导致死锁
- 3、信号量的使用不当。比如，实现互斥的P操作在实现同步的P操作之前
死锁的处理策略
- 1、预防死锁：破坏死锁产生的四个必要条件中的一个或几个
- 2、避免死锁：用某种方法阻止系统进入不安全的状态
- 3、死锁的检测和解除：允许死锁的产生，不过操作系统会负责检测出死锁的产生，然后采取某种措施解除死锁
2、死锁的处理策略----预防死锁
破坏互斥条件
把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如使用SPOOLing技术。
缺点：并不是所有的资源都可以改造成可共享使用资源，并且为了系统安全，在很多地方还必须保护这种互斥性，无法破坏
破坏不剥夺条件
- 方案一：当某个进程请求的资源得不到满足的时候，它必须立即释放保持的所有资源，待以后需要的时候再重新申请一下
- 方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺，这种方式需要考虑进程的优先级
- 缺点：
- 1、实现起来比较复杂
- 2、释放已经获得的资源可能造成前一阶段工作的失效，因此一般只适用于易保存和恢复状态的资源，如CPU
- 3、反复的申请和释放资源会增加系统的开销，降低系统吞吐量
- 4、如果采用方案一，如果一直重复这样会导致饥饿
破坏请求和保持条件
- 采用静态分配方法：进程在运行前一次申请完它所需要的全部资源
- 缺点：会造成严重的资源浪费，资源利用率低，也有可能导致饥饿(比如有三个进程A,B,C，其中A，B分别使用资源1,2，进程C需要用到A资源1和2，如果有源源不断的进程使用1或者2，则C一直不执行 )
破坏循环等待条件
- 采用顺序资源分配法：首先给系统中的资源编号，规定每个进程必须按照编号递增的顺序请求资源，编号相同资源一次申请完
- 原理分析：一个进程只有已经占有小编号的资源时，才有资格申请更大编号的资源，不可以大编号资源的进程逆向申请小编号的资源，这样就不会产生循环等待
- 缺点：
- 1、不方便增加新设备，因为可能需要重新分配所有的编号
- 2、进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费
- 3、必须按规定次序申请资源，用户编程麻烦
3、死锁的处理策略----避免死锁
- 什么是安全序列
- 所谓安全序列，就是指系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找到一个安全序列，系统就是安全状态。当然安全序列可能有多个
- 如果分配资源后，系统中找不出任何一个安全序列，系统就进入了不安全状态，这就意味着之后可能所有进程都无法顺利执行下去。如果有进程提前归还了一些资源，系统还是有可能重新回到安全状态
- 如果系统处于安全状态，就一定不会发生死锁，如果系统进入不安全状态，就可能发生死锁(处于不安全状态未必发生了死锁，但发生死锁的时候就一定是处于不安全状态)
- 可以在资源分配之前预先判断这次分配会不会导致系统进入不安全状态，以此决定是否答应资源分配请求，这是银行家算法核心思想
4、死锁的处理策略----检测和解除
为了能对系统死锁进行检测需要满足的条件
1、用某种数据结构来保存资源的请求和分配信息
上图中绿色表示已经分配的资源，蓝色表示正在请求的资源。按照上述过程，最终能够消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁。比如P2中申请一个R1，但是此时R1已经分配出去三个了，所以P2进入阻塞的状态，要等P1释放资源
解除死锁
用死锁检测算法化简资源分配图之后，还连着的边的那些进程就是死锁进程，解除死锁的主要方法：
- 1、资源剥夺法：挂起(暂时放到外存上)某些死锁进程，并抢占它的资源，将这些资源分配给其他死锁进程
- 2、撤销进程法(或终止进程法)：强制撤销部分、甚至全部死锁的进程，并剥夺这些进程的资源，这种方式的优点是实现简单，但代价有点大，撤销进程之前的运行都芜湖了
- 3、进程回退法：让一个或多个死锁进程回退到避免死锁的地步。这要求系统记录进程的历史信息，设置还原点
5、内存的基础知识
什么是内存？有何作用？
- 内存是用于存放数据的硬件。程序执行前需要先放到内存中才能被CPU处理
- 如何区分各个程序的数据在内存的什么地方？
- 给内存的存储单元编地址
- 内存地址从0开始，每个单元对应一个存储单元(相当于宾馆的房间)
- 如果计算机按字节编址，则每个存储单元大小为1字节，即1B，即8个二进制位
- 如果字长为16位的计算机按字编址，则每个存储单元大小为1个字，每个字的大小为16个二进制位(取决于计算机的字长)
- 给内存的存储单元编地址
几个常用的数量单位
- 2^10 = 1K (千)
- 2^20 = 1M (兆，百万)
- 2^30 = 1G (亿，千兆)
- 一台手机有4GB内存，是什么意思？
- 指该手机内存可以存放4 * 2^30 个字节，如果按照字节编址的话，也就是有4 * 2^30 = 2^32 个存储单元(个房间)
- 需要 2^32个地址才能一一标识，也就是地址需要用32个二进制位来表示
进程的运行原理 --- 指令
- 我们写的代码最终被翻译成CPU能够识别的指令，这些指令会告诉CPU去内存的哪个地址存/取数据，这个数据应该做什么样的处理。在编译生成的指令中一般使用的是逻辑地址(相对地址)
- 逻辑地址(相对地址) VS 物理地址(绝对地址)
- 逻辑地址就是相对初始位置的距离，在内存中实际存放的位置 = 起始位置 + 逻辑地址
- 物理地址即绝对地址，就是数据存放在内存中的实际位置
从写程序到程序运行
装入的三种方式(逻辑地址 -> 物理地址的转换)
1、绝对装入：在编译的时候就知道程序存放在内存的哪个位置，编译程序产生绝对地址的目标代码(目标模块中的指令就是内存中的绝对地址)，装入程序按照装入模块中的地址，将程序和数据装入内存。
绝对装入只适用于单道程序的环境(因为地址已经写死，如果多道程序的话会冲突)。程序中使用的绝对地址，可以在编译或者汇编的时候给出，也可由程序员直接赋予，但通常都是编译或汇编时在转换为绝对地址
2、静态重定位：又称可重定位装入，编译和链接之后指令中的地址都是从0开始的逻辑地址，根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行重定位，将逻辑地址变换为物理地址(地址变换是在装入的时候一次性完成的)
特点：一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存空间，就不能装入该作业，作业一旦进入内存之后，在运行期间不能再移动，也不能再申请内存空间
3、动态重定位(现在使用)：又称为动态运行时装入。编译和链接之后装入模块的地址都是从0开始，装入程序将装入模块装入到内存之后也不会立即将逻辑地址变换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入到内存中的地址依旧是逻辑地址，这种方式需要一个重定位寄存器(存放起始地址)的支持
特点：动态重定位时允许程序在内存中发生移动，并且可将程序分配到不连续的存储区，在程序运行前只需要装入它的部分代码就可以运行，在程序运行期间，可以动态申请内存分配
链接的三种方式
- 1、静态链接：在程序运行之前，将各个目标模块连接到装入模块
- 2、装入时动态链接：将各个目标模块装入内存时，边装入边链接
- 3、运行时动态链接：在程序执行中需要改目标模块时，才对他进行连接
6、内存管理的概念
- 操作系统负责内存空间的分配和回收
- 操作系统需要提供某种技术从逻辑上对内存空间进程扩充-----覆盖技术、交换技术、虚拟存储技术
- 操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换----三种装入方式
- 操作系统需要提供内存保护功能，保证各进程在各自存储空间内运行互不干扰
- 方法一：在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址的时候，CPU检查是否越界
- 方法二：采用**重定位寄存器(又称为基址寄存器)和界地址寄存器(又称限长寄存器)**进行越界检查。
7、内存空间的扩充-----覆盖与交换
覆盖技术：用来解决程序大小超过物理内存总和的问题
- 思想：将程序分为多个段(多个模块)。常用的段常驻内存，不常用的段在需要时调入内存
- 内存中分为一个固定区和若干个覆盖区
- 需要常驻内存的段放入固定区，调入后就不再调出(除非运行结束)
- 不常用的段放在覆盖区，需要用到时调入内存，用不到时调出内存
- 特点：必须由程序员声明覆盖结构，操作系统完成自动覆盖，缺点：对用户不透明，增加了用户编程的负担，现在不使用了
交换技术
- 设计思想：内存空间紧张的时候，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)。就是将某些进程挂起。中级调度：就是决定将哪个处于挂起状态的进程重新调入内存。(PCB会常驻内存，不会被换出内存)
- 应该在外存(磁盘)的什么位置保存被换出的进程？
- 具有对换功能的操作系统中，通常将磁盘空间分为文件区和对换区两部分。文件区主要存放文件，主要追求存储空间的利用率，因此文件区空间的管理采用离散分配方式；对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区，因为需要对换的速度，所以对换区空间的管理主要追求换入换出速度，通常采用连续分配方式。总之对换区的I/O速度比文件区的更快
- 什么时候应该交换？
- 交换通常发生在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如：在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程，如果缺页率明显下降，就可以暂停换出
- 应该换出哪些进程？
- 可优先换出阻塞进程；可换出低优先级的进程；为了防止低优先级进程发生饥饿，有的系统还会考虑进程在内存中的驻留时间
8、内存空间的分配-----连续分配管理方式
连续分配：就是为用户进程分配的必须是一个连续的内存空间
单一连续分配方式
- 内存被分为系统区和用户区，系统区通常位于内存的低地址部分，用于存放操作系统的相关数据，用户区用于存放用户进程的相关数据
- 内存中只能有一道用户程序，用户程序独占整个用户区空间
- 特点：
- 优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护
- 缺点：只能用于单用户、单任务的操作系统中；有内部碎片(分配给某进程的内存区域中，如果有些部分没有用上，就是内部碎片)；存储器利用率极低
固定分区分配
将用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的多道程序的内存管理方式。
固定分区分配分为两种：
- 分区大小相等：缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合
- 分区大小不等：增加了灵活性，可以满足不同大小的进程的需求。根据常在系统中运行的作业大小情况进行划分(比如：划分多个小分区、适量中等分区、少量大分区)
操作系统如何记录各个分区空闲或者分配的情况？
- 操作系统需要建立一个数据结构---分区说明表，来实现各个分区的分配和回收。每个表项对应一个分区，包括分区号、对应分区的大小、起始地址、状态(是否已分配)
- 当用户进程要装入内存时，由操作系统内核程序根据用户程序大小检索该表，从中找到一个满足条件的分区，然后修改分区状态
特点：
- 优点：实现简单；无外部碎片
- 缺点：
- 1、当用户程序太大时，可能所有的分区都不能满足，此时不得不采取覆盖技术来解决，但是这回降低系统性能
- 2、会产生内部碎片，内存利用率低
动态分区分配(可变分区分配)
原理：在线程装入内存时，根据进程的大小动态建立分区，并使分区的大小正好适合进程的需要，因此系统分区的大小和数目是可变的
系统要用什么样的数据结构记录内存的使用情况？
- 空闲分区表：每个空闲分区对应一个表项。表项中包含分区、分区信息、分区起始地址、状态等信息
- 空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针。
当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？
- 按照动态分区分配算法
如何进行分区的分配和回收操作？
- 如何进行分配：假设采用的数据结构是空闲分区表，则修改对应分区号，以及剩余的分区大小和起始地址等信息
- 如何进行回收：
- 情况一：回收区的前或后面有一个相邻的空闲分区，两个相邻的空闲分区合并为一个
- 情况二：回收区的前、后各有一个相邻的空闲分区，需要将一整块的空闲分区合并
- 情况三：回收区的前、后都没有相邻的空闲分区，需要新增一个空闲分区
注意：各表项的顺序不一定按照地址递增的顺序排序，具体的排序方式需要依据动态分配算法来确定
特点：没有内部碎片，但是有外部碎片
- 内部碎片：分配给某进程的内存区域中，如果有些部分没有用上
- 外部碎片：内存中的某些空闲分区由于太小难以利用
- 如果内存中空闲空间的总和本来可以满足某进程的要求，但由于该进程需要连续的内存空间，因此这些碎片不能满足进程的需求，可以通过紧凑(拼凑) 的技术来解决(把已占的内存挪位)
9、动态分区分配算法
首次适应算法
- 算法思想：每次从低地址开始查找，找到第一个能满足大小的空闲分区
- 实现：**空闲分区以地址递增的次序排列。**每次分配内存时顺序查找空闲分区链或空闲分区表，找到大小能够满足要求的第一个空闲分区。
- 缺点：导致低地址出现很多小的难以利用的空闲区
最佳适应算法(先用小的)
- 算法思想：优先使用更小的空闲区，尽可能更多的留下大片的空闲区
- 实现：空闲分区按照容量递增次序链接。每次分配内存时顺序查找空闲分区链或空闲分区表，找到大小能够满足要求的第一个空闲分区。
- 缺点：每次都选最小的分区，会留下越来越多的又小又难利用的内存块，会产生很多的外部碎片
最坏适应算法(先用大的)
- 算法思想：优先使用最大的连续空闲区，这样留下的空闲区就不会太小，更方便使用
- 实现：空闲分区按照容量递减的次序链接。每次分配内存时顺序查找空闲分区链或空闲分区表，找到大小能够满足要求的第一个空闲分区。
- 缺点：每次都选最大的分区，会导致大的空闲区迅速被用完，如果还有大进程到来，就没有内存分区可以用了
邻近适应算法
- 算法思想：每次查找从上次使用地址的下一个开始
- 实现：空闲分区以地址递增的次序排列(第一次排，后面不需要再排)，每次分配内存时从上次查找结束的位置开始查找空闲分区，找到大小能够满足要求的第一个空闲分区
- 缺点：每个空闲分区都用相同的概率被使用，也就导致高地址的大分区更可能被使用。划分为小分区，最后也就导致无大分区可用
image-20220508143045462
10、基本分页存储管理的基本概念
内存空间非连续分配管理方式
- 基本分页存储管理的思想：把内存分为一个个相等的小分区，再按照分区大小把进程拆分为一个个小部分
- 内存拆分为一个个大小相等的分区,每个分区就是一个页框(或称为页帧)。每个页框有一个编号，就是页框号，页框号从0开始
- 进程根据页框大小拆分为一个个区域，称为页(或页面)。每个页面也有一个编号，即页号，页号也是从0开始(进程的最后一个页面可能没有一个页框那么大，页框不能太大，否则会产生过大的内部碎片)
- 页面与页框有一一对应关系，页面不必连续存放，可以放到不相邻的页框中
- 逻辑地址如何转换为物理地址
- 1、算出逻辑地址对应的页号：页号 = 逻辑地址 / 页面长度
- 2、页号在内存中的起始地址：操作系统用某种数据结构记录
- 3、逻辑地址在页面的偏移量：页内偏移量 = 逻辑地址 % 页面长度
- 4、物理地址= 起始地址 + 偏移量
- 结论：如果每个页面大小是2^k,用二进制表示逻辑地址，则末尾K位标识页内偏移量，其余部分就是页号
- 页表：为了能够知道进程的每一个页面在内存中的存放位置
- 1、一个进程对应一个页表
- 2、页表由页号和块号(页框号)组成
- 页表项：页表中的一条记录
11、基地址变换机构
基地址变换机构可以借助页表将逻辑地址变换为物理地址
系统中设置一个页表寄存器，存放页表的起始地址(页表的开始地址)和页表长度(页表项的个数)，进程未执行时，页表起始地址和长度放在PCB在，当进程被调度时，才会放入页表寄存器
08589340b276ee29a357f080ed4012b 快表(联想寄存器)：访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项。
541a75aa1efce984b24df67aea29aa4
12、两级页表
单级页表的问题
- 页表必须连续存放，当页表很大的时候，需要占用很多个连续的页框
- 没必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面(后面讲解)
两级页表的原理---- 解决上面第一个问题
为离散分配的页表再建立一张页表，称为页目录表，或称外层页表，或称顶级页表(套娃)
将页表继续根据页框大小进行拆分
f7cd987ba102ecf12110ee6a4416034 根据拆分的很多个页表建立页目录表
3361d94ab3623353f7997137296d8eb 案例
484c54717461b527d7e199d942448f1 注意：
- 各级页表的大小不能超过一个面
- 两级页表访问内存的次数
- 1、第一次：访问页目录表
- 2、第二次：访问二级页表
- 3、第三次：访问目标单元
小结：
13、基本分段存储管理方式
与分页的最大区别：离散分配时所分配地址空间的基本单位不同
分段：程序按照自身的逻辑关系划分为若干个段，每个段都有一个段名，每段从0开始编程
内存分配规则：**以段为单位进行分配，每个段在内存中占据连续空间，**但各段之间可以不相邻
f6fbed833a9af8b9e4df67b0c17c3fc 分段系统的逻辑地址结构由**段号(段名)和段内地址(段内偏移量)**所组成
段号的位数决定了每个进程最多可以分几个段
段内地址位数决定了每个段的最大长度是多少
段表：能够从物理内存中找到各个逻辑段的存放位置
31fd5ca9ccd980db93b6088ea0e1d58 - 每个段对应一个段表项，其中记录了该段在内存中的起始位置(基址)和段的长度
- 各个段表项的长度是相同的，段号是可以隐含的，不占存储空间
段表寄存器：在PCB中存放段表始址和段表长度
19fda1f5ff23a13b9e546eba14effc6 分页与分段的区别
3dd975466ed41bb250ad2f71beec3fb 分段比分页相比更容易实现信息的共享和保护
- 实现共享：只需要让各个进程的段表项执行同一个段即可实现共享。不能被修改的代码称为纯代码或可重入代码，这样的代码可实现共享。可修改的代码不能实现共享(比如：有一个代码段中有很多变量，各进程并发同时访问可能造成数据不一致)。
- 实现保护与实现共享的原因相似：允许访问的部分应该隔离出来可以访问
小结：
14、段页式管理方式
分页和分段的优缺点
优点 缺点 分页管理 内存空间利用率高，不会产生外部碎片，只会产生少量的页内碎片 不方便实现信息的共享和保护 分段管理 很方便实现信息的共享和保护 如果段过大，为其分配很大的连续空间会很不方便，会产生外部碎片(产生原因与动态分区分配相似) 段页式管理 = 分段 + 分页
将进程按逻辑模块分段，再将各段分页，再将内存空间分为大小相同的页框，进程前将各页面装入各内存块中
9b68045565ab516f5f3e723c7b11f0c 段页式系统的逻辑地址结构由段号、页号、页内地址组成
image-20220513152328116 分段对用户是可见的，程序员编程时需要显示的给出段号、段内地址。而将各段分页是对用户不可见的。系统会根据段内地址自动划分页号和页内偏移地址
段表、页表
每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号(页表的起始地址)组成。每个段表项的长度相等，段号是隐含的
每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含。
image-20220513153925493 逻辑地址转物理地址
image-20220513154609606 也可以引入快表机构
15、虚拟内存的概念
也是为了进行内存空间的扩充
传统存储管理方式的问题
- 作业很大时，不能全部装入内存，导致大作业无法运行
- 当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降
- 一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源
局部性原理
- 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久后该数据很可能再次被访问(因为程序中存在着大量的循环)
- 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问(因为很多数据在内存中都是连续存放的，并且程序的指令也是顺序的在内存中存放)
高速缓冲技术
将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速的存储器中
虚拟内存
- 在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。
- 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行
- 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存
虚拟内存实际的物理内存大小没有变，只是在逻辑上进行了扩充
虚拟内存的三个主要特征
- 多次性：无需在作业运行时一次性全部装入内存，而是被允许分成多次调入内存
- 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出
- 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量
如何实现虚拟内存技术
虚拟内存技术，允许一个作业分多次调入内存。如果采用连续分配的方式，会不方便实现。因此，虚拟内存的实现需要建立在离散分配的内存管理方式的基础上
image-20220515155525114
16、请求分页存储管理
请求分页存储管理与基本分页存储管理的主要区别：
- 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行
- 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存
请求分页管理的方式
- 页表机制
- 缺页中断机构
- 地址变换机构
页表机制
image-20220515160709826 缺页中断机构
- 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断
- 此时缺页的进程阻塞，放入阻塞队列，调页完成之后再将其唤醒，放回就绪队列
- 如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项
- 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存
缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断。一条指令在执行期间，可能产生多次缺页中断(比如copy A to B，即将逻辑地址A中的数据复制到逻辑地址B，而A、B属于不同的页面，则有可能产生两次中断)
地址变换机构
image-20220515204309592 
image-20220515204850109
17、页面置换算法
算法种类：最佳置换算法(OPT)，先进先出置换算法(FIFO)，最近最久未使用置换算法(LRU)，时钟置换算法(CLOCK)，改进型的时钟置换算法
页面的换入、换出需要磁盘的I/O，会有较大的开销，因此页面置换算法应该追求更少的缺页率。
最佳置换算法(OPT)
- 每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面。追求的是最低的缺页率，但在实际过程中，只有在进程执行的过程中才能知道接下来会访问的是哪个页面，操作系统无法提前预判页面访问序列。因此最佳置换算法是无法实现的
image-20220521130218677 - 上图缺页中断发生了9次，页面置换发生了6次(注意：缺页时未必发生页面置换，若还有可用的空闲内存块，就不用进行页面置换)
- 缺页率 = 9 / 20 = 45%
先进先出置换算法(FIFO)
- 每次选择淘汰的页面是最早进入内存的页面
- 实现方法：将调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。
- 先进入的页面在之后也有可能经常的访问到，所以算法性能较差
image-20220521131041972 - 缺页9次。当分配四个内存块的时候，缺页发生10次，分配三个内存块时，缺页发生9次
- Belady异常---当为进程分配的物理块数增大时，缺页次数不减反增的异常现象
最近最久未使用置换算法(LRU)
每次淘汰的页面是最近最久未使用的页面
页表项中的访问字段记录页面自上次被访问以来所经历的时间t，当需要淘汰一个页面时，选择现有页面中t值的最大的，即最近最久未使用的页面
image-20220521132954826 找最晚出现的淘汰掉
算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大
时钟置换算法(CLOCK)
时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未使用算法(NRU)
简单的CLOCK算法实现方法：为每一个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描所有页面都是1，则将这些页面的访问依次置为0，再进行第二轮扫描(第二轮扫描一定会有访问位为0的页面)
image-20220521133823507 改进型时钟置换算法思想：简单的时钟置换算法仅仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。因此，在其他条件都相同时，应该优先淘汰没有修改过的页面，避免I/O操作。修改为=0，表示页面没有被修改过；修改为=1，表示页面被修改过，用**(访问位，修改位)**的形式表示各页面的状态，比如(1,1)表示一个页面近期被访问过，且被修改过。
- 算法规则：将所有可能被置换的页面排成一个循环队列
- 第一轮：从当前位置开始扫描到第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位(最近没有访问且没有修改过的页面)
- 第二轮：若第一轮扫描失败，则重新扫描，查找第一个(0,1)的帧用于替换。本轮将所有扫描过的帧访问位设为0 (最近没访问，但修改过的页面)
- 第三轮：若第二轮扫描失败，则重新扫描，查找第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位(最近访问过，但没有修改过的页面)
- 第四轮：若第三轮扫描失败，则重新扫描，查找第一个(0,1)的帧用于替换(最近访问过，且修改过的页面)
- 由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，所有淘汰一个页面最多进行四轮扫描
- 算法规则：将所有可能被置换的页面排成一个循环队列
18、页面分配策略
驻留集：指请求分页存储管理中给进程分配的物理块的集合，采用虚拟内存技术的系统中，驻留集大小一般小于进程的总大小
驻留集太小，会导致缺页频繁，系统要花大量的时间来处理分页，实际用于进程推进的时间很少
驻留集太大，又会导致多道程序并发度下降，资源利用率低
固定分配：操作系统为每一个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变
可变分配：先为进程分配一定数目的物理块，在进程运行期间，可以根据情况做出适当的增加或减少。即，驻留集大小可变
局部置换：发生缺页时只能选进程自己的物理块进行置换
全局置换：可将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程
局部置换 全局置换 固定分配 √ --- 可变分配 √ √ 
image-20220521200544645
何时调入页面
- 1、预调页策略：根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更加高效。但如果提前调入的页面大多数都没被访问过，则又是低效的。故这种策略主要用于进程首次调入，由程序员指出应该先调入哪些部分(运行前调入)
- 2、请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存。由于这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘I/O操作，因此I/O开销较大(运行时调入)
从何处调入页面
image-20220521202834105 抖动(颠簸)现象
刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数(分配给进程的物理块不够)
工作集：指在某段时间间隔里，进程实际访问页面的集合
驻留集的大小不能小于工作集的大小，否则进程运行过程中将频繁缺页
