操作系统复习篇（上）：https://developer.aliyun.com/article/1446294

多级队列调度算法

就绪队列从一个分为多个，如：

• 前台【交互式】
• 后台【批处理】

每个队列有自己的调度算法，如:

• 前台——RR
• 后台——FCFS

调度需在队列间进行：

• 固定优先级调度，即前台运行完后再运行后台，有可能产生饥饿
• 给定时间片调度，即每个队列得到一定的CPU时间，进程在给定时间内执行；如80%的时间执行前台的RR调度，20%的时间执行后台的FCFS调度

多级反馈队列调度算法

进程能在不同队列间移动

其他调度算法的局限性：

• 短进程优先算法，仅照顾短进程而忽略了长进程
• 如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用

优点：

• 不必事先知道各种进程所需的执行时间
• 可以满足各种类型进程的需要

基于公平原则的调度算法

主要考虑调度的公平性

保证调度算法：

• 性能保证，而非优先运行
• 如保证处理及分配的公平性

公平分享调度算法：

• 调度的公平性主要针对用户而言
• 使所有用户都获得相同的处理及时间或时间比例

3.3实时调度

实时调度是针对实时任务的调度

实时任务，都联系着一个截止时间：

• 硬实时HRT任务
• 软实时SRT任务

实时调度应具备一定的条件：

• 提供必要的信息：就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级
• 系统处理能力强（周期性）
• 采用抢占式调度机制
• 采用快速切换机制：对终端具有快速响应能力、快速的任务分派能力

非抢占式调度算法

非抢占式轮转调度算法：

• 响应时间：数秒至数十秒
• 可用于要求不太严格的实时控制系统

非抢占式优先级调度算法：

• 响应时间：数秒至数百毫秒
• 可用于有一定要求的实时控制系统

抢占式调度算法

基于时钟中断的抢占式优先级调度：

• 响应时间：几十毫秒至几毫秒
• 可用于大多数实时系统

立即抢占的优先级调度：

• 响应时间：几毫秒至几百微秒
• 可用于有严格时间要求的实时系统

最早截止时间优先（EDF）调度算法

• EDF根据任务的截止时间确定优先级，截至时间越早，优先级越高
• 既可用于抢占式调度，也可用于非抢占式调度
• 非抢占式调度用于非周期实时任务
• 抢占式调度用于周期实时任务

最低松弛度优先LLF算法

• 根据任务的紧急程度（松弛度）确定任务优先级

• 松弛度越低，优先级越高
• 松弛度=必须完成时间-本身的运行时间-当前时间

• 主要用在抢占式调度方式中

优先级倒置现象

采用优先级调度和抢占方式，可能产生优先级倒置现象：高优先级进程被低优先级进程延迟或阻塞

解决方法：

• 制定一些规定，如规定低优先级进程执行后，其所占用的处理及不允许被抢占
• 建立动态优先级继承

3.4Linux进程调度

默认调度算法：完全公平调度算法CFS算法

基于调度器类：允许不同的可动态添加的调度算法并存，每个类都有一个特定的优先级

• 总调度器：根据调度器类的优先顺序，依次对调度器类中的进程进行调度
• 调度器类：使用所选的调度器类算法（调整策略）进行内部的调度
• 调度器类的默认优先级顺序为：Stop_Task>Real_Time>Fair>Idle_Tasks

普通进程调度：

• 采用SCHED_NORMAL调度策略
• 分配优先级、挑选进程并允许、计算使其运行多久
• CPU运行时间与友好值（-20~+19）有关，数值越低优先级越高

实时进程调度：

• 实时调度的进程比普通进程具有更高的优先级
• SCHED_FIFO：金承若处于可执行状态，就会一直执行，直到它自己被阻塞或主动放弃CPU
• SCHED_RR:与SCHED_FIFO大致相同，只是进程在耗尽其时间片后，不能再执行，而是需要接受CPU的调度

3.5死锁概述

概念

• 死锁（Deadlock）：

• 指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态是，若无外力作用，这些进程将永远不能再向前推进
• 一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源

• 可重用性资源：一次只能分配给一个进程，不允许多个进程共享，遵循：请求资源、使用资源、释放资源
• 可消耗性资源：由进程动态创建和消耗（进程间通信的消息）
• 可抢占性资源：某进程在获得这类资源后，该资源可以再被其他进程或系统抢占，CPU（处理机）和主存区
• 不可抢占性资源：当系统把这类资源分配给某进程后，不能强行收回，只能在进程用完后自行释放，打印机、磁带机

产生死锁的必要条件

• 互斥：一段时间内某资源只能被一个进程占用
• 请求和保持：一个至少持有一个资源的进程等待获得额外的有其他进程持有的资源
• 不可抢占：一个资源只有当持有它的进程完成任务后，自由的释放
• 循环等待：等待资源的进程之间存在环

死锁原因

• 竞争不可抢占性资源引起死锁
• 竞争可消耗性资源引起死锁
• 进程推进顺序不当引起死锁

处理死锁的方法

确保系统永远不会进入死锁状态

• 死锁预防
• 死锁避免

允许进入死锁状态，然后恢复系统

• 死锁检测
• 死锁恢复

忽略这个问题，假装系统中从未出现过死锁。这个方法被大部分的操作系统采用，包括UNIX

方法：

• 预防死锁：破坏死锁的四个必要条件中一个或几个
• 避免死锁：在资源动态分配是，防止系统进入不安全状态
• 检测死锁：实现不采取任何措施，允许死锁发生，但即使检测死锁发生
• 解除死锁：检测到死锁发生时，采取相应措施，将进程从死锁状态中解脱出来

3.6预防死锁

破坏死锁的四个必要条件中的一个或几个

互斥：

互斥条件是共享资源必须的，不仅不能改变，还应加以保证

请求和保持：

必须帮正进程申请资源的时候没有占用其他资源

• 要求进程在执行前一次性申请全部的资源，只有没有占有资源时才可以分配资源
• 资源利用率低，可能出饥饿
• 改进：进程只获得运行初期所需的资源后，便开始运行；其后台在运行过程中逐步释放已分配的且用毕的全部资源，然后再请求新资源

非抢占：

• 如果一个进程的申请没有实现，它要释放所有占有的资源
• 先占的资源放入进程等待资源列表中
• 进程在重新得到旧的资源的时候可以重新开始

循环等待：

对所有的资源类型排序进行线性排序，并赋予不同的序号，要求进程按照递增顺序申请资源

• 如何规定每种资源的序号是十分重要的
• 限制新类型设备的增加
• 作业使用资源的顺序与系统规定的顺序不同
• 限制用户简单、自主的编程

3.7避免死锁

设一个简单而有效的模型，要求每一个进程声明它所需要的资源的最大数

死锁避免算法动态检查资源分配状态以确保不会出现循环等待的情况

资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量

安全状态

• 当进程申请一个有效的资源的时候，系统必须确定分配后是安全的
• 如果存在一个安全序列，则系统处于安全态
• 即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕
• 进程序列是安全的，如果每一个进程Pi所申请的可以被满足的资源数加上其它进程所持有的该资源数小于系统总数。

不安全状态

可能会到达死锁，但不是死锁

安全状态和不安全状态的区别

• 安全状态出发，能保证所有进程都能完成
• 不安全状态出发，无法保证（可能部分完成）

基本事实

• 如果一个系统在安全状态，就没有死锁
• 如果一个系统不是处于安全状态，就有可能死锁
• 死锁避免=>确保系统永远不会进入不安全状态

银行家算法

Dijkstra提出的银行家算法：其这样的名字是由于该算法原本是为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。在OS中也可以用它来实现避免死锁

• 针对资源有多个实例
• 每一个进程必须事先声明使用的最大量
• 当一个进程请求资源，它可能要等待
• 当一个进程得到所有的资源，它必须在有限的时间释放它们

这部分建议去B站找个视频来复习

3.8死锁的检测与解除

当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此，系统必须：

• 保存有关资源的请求和分配信息
• 提供一种算法，以利用这些信息来检测系统是否已经入死锁状态

基本事实

如果图没有环，那么不会有死锁

如果图有环，那么：

• 如果每一种资源类型只有一个实例，那么死锁发生
• 如果一种资源类型有多个实例，那么可能死锁

资源分配图的简化

• 在资源分配图中，找出一个既不阻塞又非独立的进程节点Pi。在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去Pi所有的请求边和分配边，使之成为孤立的结点
• P1释放资源后，便可使P2获得资源而继续运行，直到P2完成后又释放出它所占有的全部资源
• 在进行一系列的简化后，若能消去图中所有的边，使所有进程都成为孤立结点，则称该图是可完全简化的；若不能，则称其不可完全简化

死锁定理

• 对于较复杂的资源分配图，可能有多个既未阻塞，又非孤立的进程节点，不同的简化顺序，是否会得到不同的简化图？有关文献已经证明，所有的简化顺序，都将得到相同的不简化图
• S为死锁状态的充分必要条件是：当且仅当S状态的资源分配图使不可完全简化的。该充分条件称为死锁定理

死锁的解除

常用解除死锁的两种方法：

• 抢占资源。从一个或多个进程中抢占足够数量的资源给死锁进程，以解除死锁
• 终止或撤销进程。终止系统中一个或多个死锁进程，直到打破循环回路，使死锁状态消除为止。

• 终止所有死锁进程（最简单方法）
• 逐个终止进程（稍温和方法）

进程终止

中断所有的死锁进程

一次中断一个进程，直到死锁环消失

应该选择怎样的中断程序，使“代价最小”？

• 进程的优先级
• 进程需要计算多久，以及需要多久结束
• 进程使用的资源，进程完成还需要多少资源
• 进程是交互的还是批处理的

其他问题

• 通信死锁
• 活锁
• 饥饿

通信死锁

• 竞争性同步：资源死锁

• 多个进程任务无关联，只是共享资源

• 协同同步：通信死锁

• 多个进程共同完成一个任务，无共享资源

• 通信死锁的场景：信息丢失
• 通信死锁的解决：超时重发

活锁

活锁场景：

• 多个礼貌的进程

• 获取资源成功
• 请求新资源失败
• 释放已有资源
• 再次尝试

• 有限的表容量

• 每个进程占有部分
• 试图申请更多资源

饥饿

饥饿场景：

• 打印机分配

• 优先小文件
• 小文件多

• 优先级调度

• 高优先级进程多

解决方案：先来先服务

四、进程同步

4.1进程同步的概念

概念

主要任务：使并发执行的进程之间能有小弟共享资源和相互合作，从而使程序的执行具有可再现性

进程间的制约关系：

• 间接相互制约关系（互斥关系）

• 进程互斥使用临界资源

• 直接相互制约关系（同步关系）

• 进程间相互合作

临界资源：

• 系统中某些资源一次只允许一个进程使用，这样的资源称为临界资源或互斥资源或共享变量
• 诸进程间采取互斥方式，实现了对这种资源的共享

临界区：进程中涉及临界资源的代码段

进入区：用于检查是否可以进入临界区的代码段

退出去：将临界区正被访问的标志恢复为未被访问标志

剩余区：其他代码

同步机制应遵循的准则

• 空闲让进：当无进程处于临界区，应允许一个请求进入临界区的进程立即进入自己的临界区
• 忙则等待：已有进程处于其临界区，其他试图进入临界区的进程必须等待
• 有限等待：等待进入临界区的进程不能“死等”
• 让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）

进程同步机制

• 软件同步机制：使用编程方法解决临界区问题

• 有难度、具有局限性，现在很少采用

• 硬件同步机制：使用特殊的硬件指令，可有效实现进程互斥
• 信号量机制：一种有效的进程同步机制，已被广泛应用
• 管程机制：新的进程同步机制

4.2软件同步机制

不做介绍

4.3硬件同步机制

关中断：

• 进入锁测试之前关闭终端，完成锁测试并上锁之后才打开中断
• 可有效保证互斥，但存在很多缺点

Test-and=Set指令

Swap指令

缺点：

• 不符合“让权等待”原则，浪费CPU时间
• 很难解决复杂的同步问题

4.4信号量机制 （推荐看B站）

信号量-软件解决方案：

• 保证两个或多个代码段不被并发调用
• 在进入关键代码段前，进程必须获取一个信号量，否则不能运行
• 执行完该关键代码段，必须释放信号量
• 信号量有值，为正说明它空闲，为负说明其忙碌

类型：

• 整型信号量
• 记录型信号量
• AND型信号量
• 信号量集

整型信号量

• 信号量S-整型变量
• 提供两个不可分割的【原子操作】访问信号量（即要么都执行，要么都不执行）

void wait(int s){
 while(s<=0){};
 s--;
}
void signal(int s){
 s++;
}

• Wait(s)又称为P(S)
• Signal又称为V（S）
• 缺点：进程忙等

记录型信号量

每个信号量S除一个整数值S.value外，还有一个进程等待队列S.list，存放则色在该信号量的各个进程PCB

typedef struct {
  int value;
  Struct process* L;
}semaphore
 
void wait(semphore S) {
  S.value--;
  if (S.value < 0) {
    block(S.L);
  }
}
 
void signal(semphore S) {
  S.value++;
  if (S.value <=0) {
    wakeup(S.L);
  }
}

五、存储器管理

5.1存储器的层次结构

金字塔模型，越高越少，性能越高，价格越贵

概念

• 可执行寄存器：寄存器和主存储器
• 主存储器：内存或主存
• 寄存器：访问速度最快，与CPU协调工作，价格贵

• 高速缓存：介于寄存器和存储器之间

• 备份主存常用数据，减少对主存储器的访问次数
• 缓和内存与处理机之间的矛盾

• 磁盘缓存

• 暂时存放频繁使用的一部分磁盘数据和信息
• 缓和主存和I/O设备在速度上的不匹配
• 利用贮存的部分空间，主存可看成辅存的高速缓存

5.2程序的装入和链接

程序的运行步骤：

• 编译：由编译程序（Compiler）对源程序进行编译，形成若干个目标模块
• 链接：由链接程序（Linker）将目标模块和它们所需要的库函数链接在一起，形成一个完整的装入模块
• 由装入程序（Loader）将装入模块装入内存

物理地址和逻辑地址

物理地址（绝对地址）

• 物理内存的地址，内存以字节为单位编址
• 物理地址空间：所有物理地址的集合

逻辑地址（虚拟地址、相对地址）

• 由CPU产生的地址，即程序编译后使用的相对于0字节的地址
• 逻辑地址空间：由程序所生成的所有逻辑地址的集合

内存保护的实现：硬件

• 基地址寄存器：保存最小的合法物理内存地址（基地址）
• 界限寄存器：保存合法的地址范围大小（界限地址）
• 内存空间保护的实现：判断“基地址<=物理地址<（基地址+界限地址）”是否成立

程序的装入

绝对装入方式：

• 编译时产生的地址使用绝对地址
• 程序或数据被修改时，需要重新编译程序

可重定位装入方式：

• 编译后的目标模块使用相对地址
• 在装入时，完成重定位（静态重定位）
• 需硬件支持

动态运行时装入方式：

• 编译后的目标模块使用相对地址
• 在装入时，完成重定位（动态重定位）

程序的链接

静态链接：

• 在程序运行前，将各目标模块及他们所需的函数链接成一个完成整的装配模块，以后不再拆开
• 对相对地址进行修改；变换外部调用信号

装入时动态链接：

• 在装入内存时，采用边装入边链接的链接方式
• 便于修改和更新
• 便于实现对目标模块的共享

运行时动态链接：

• 将某些目标模块的链接推迟到执行时才执行。即在执行过程中，若发现一个被调用模块尚未装入内存时，立即由OS去找该模块并将它装入内存，并把它连接到调用者模块上
• 加快装入过程，节省大量的内存空间

5.3对换与覆盖

略

5.4连续分配存储管理方式

连续分配方式：为一个用户程序分配一个连续的内存空间。

分类：

• 单一连续分配
• 固定分区分配
• 动态分区分配
• 动态可重定位分区分配

单一连续分配

内存：

• 系统区：供OS使用、低址部分
• 用户去：供用户使用

分配方式：单道程序环境下，金装有一道用户程序，即整个内存的用户空间由改进成独占

• 内存分配管理十分简单，内存利用率低
• 用于单用户、单任务OS

未采取存储器保护措施：节省硬件、方案可行

固定分区分配

• 最早的，也是最简单的一种可运行多道程序的存储管理方式
• 与先把可分配的主存储器空间分割成若干个连续区域，称为一个分区
• 每个分区的大小可以相同也可以不同。但分区大小不变，每个分区装一个且只能装一个作业
• 内存分配：如果有一个空闲区，则分配给进程

动态分区分配

• 又称为可变分区分配，根据进程的实际需要，动态地位置分配内存空间
• 数据结构：表、链
• 分配算法：顺序式、索引式
• 分配操作：分配内存、回收内存

分配算法：

• 基于顺序搜索的动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法
• 基于索引搜索的动态分区分配算法：快速适应算法、伙伴系统、哈希算法

快速适应算法：

• 将空闲分区按其容量大小进行分类，具有相同容量的所有空闲分区设有一个空闲分区链表
• 系统设有一张管理索引表，每一项对应一个空闲分区类型
• 分配时，根据进程长度，从索引表中寻找能容纳它的最小空闲分区链表；从链表中取下第一块进行分配

• 特点：

• 优点：不分割分区，不产生碎片，查找效率高
• 缺点：分区归还主存时算法复杂，系统开销较大，存在浪费

伙伴系统：

• 分区大小均为2的k次幂
• 内存按2的幂的大小来分配，如4KB、8KB等
• 满足要求是以2的幂为单位的
• 如果请求不为2的幂，则需要调整到下一个更大的2的幂：先计算一个i值，使2i-1

当分配需求小于现在可用内存时，当前段就分为两个更小的2的幂段

• 继续上述操作直到合适的段大小

• 主要用于多处理机系统中（Linux早期版本）

哈希算法：

• 建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项对应于一个空闲分区链表的头指针
• 进行分配时，根据空闲区大小，通过计算哈希函数，得到在哈希表中的位置，找到对应的空闲分区链表
• 优点：查找快速

动态可重定位分区分配

• 连续分配存在的问题

• 碎片：不能被利用的小分区
• 解决方案：紧凑，要求代码和数据可以在内存中移动
• 紧凑：通过移动内存中的作业位置，以把原来多个分散的小分区拼接成一个大分区的方法，也叫“拼接”

• 动态重定位：在指令运行时，实现地址转换（相对地址转换为绝对地址）
• 分配算法：类似于动态分区分配算法，增加了紧凑的功能

5.5分页存储管理方式

• 进程的逻辑空间可能是不连续的，如果有可用的物理内存，它将分给进程
• 把物理内存分成大小固定的块，称为物理块（frame）。（大小为2的幂，通常为1KB~8KB）
• 把逻辑内存也分成固定大小的块，称为页（page）
• 保留所有空闲块的记录
• 运行一个有N页大小的程序，需要找到N个空的页框来装入程序
• 存在页内碎片：进程最后一页经常装不满，而形成不可利用的碎片

页表

• 系统为每个进程建立了一张页表
• 逻辑地址空间内所有页，一次在页表中有一表项，记录相应页在内存中对应的物理块号
• 页表的作用：实现从页号到块号的地址映射

页表的实现

• 页表被保存在主存中
• 页表寄存器（PTR）指向页表的起始地址和长度
• 在这个机制中，每一次的数据/指令存取需要两次内存访问，一次是访问页表，一次是访问数据/指令
• 解决两次访问的问题，是采用小但专用且快速的硬件缓冲，这种缓冲称为转换表缓冲器（TLB）或联想寄存器

页表结构

现代的大多数计算机系统，都支持非常大的逻辑地址空间。在这样的环境下，页表就变得非常大，要占用相当大的空间。

解决方法：

• 对页表所需要的内存空间，采用离散分配方式
• 部分页表调入内存

页表结构：两级页表、多级页表、反置页表

5.6分段存储管理方式

略

六、虚拟存储器

6.1虚拟存储器概述

前面所介绍的各种存储器管理方式，有一个共同特点：作业全部装入内存后才能运行

问题：

• 大作业装不下
• 少量作业得以运行

解决方法：

• 扩充内存
• 逻辑上扩充内存容量（虚拟存储器）

虚拟存储器定义

基于局部性原理，应用程序在运行之前，没有必要全部装入内存，仅需将那些当前要运行的部分页面或段先装入内存便可运行，其余部分暂留在盘上

虚拟存储器：具有请求调度功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统

其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而成本接近于外存

虚拟存储器的特征

• 多次性：作业中的程序和数据允许被分成多次调入内存
• 对换性：作业运行时无需常驻内存
• 虚拟性：从逻辑上扩充了内存容量，使用户看到的内存容量远大于实际内存容量

虚拟存储器的实现方法

请求分页系统：

• 硬件支持：页表、缺页中断、地址变换机构
• 软件支持：请求调页软件、页面置换软件

请求分段系统：

• 硬件支持：段表、缺段中断、地址变换机构
• 软件支持：请求调段软件、段置换软件

段页式虚拟存储器：

• 增加请求调页和页面置换
• Intel 80386及以后

操作系统复习篇（下）：https://developer.aliyun.com/article/1446305