# 操作系统

# 操作系统概述

# 操作系统的发展

操作系统是根据实际的 "需求" 而产生和发展的.

1 - 无操作系统

• 最早人们用手工操作的方式使用计算机, 将程序和数据用纸带的形式输入进计算机, 手动控制计算机运行程序. 这种方式用户独占计算机, 资源的利用率低;
• 随着 CPU 的速度不断提升, 出现了手工操作的慢速与 CPU 的高速之间不必配的矛盾. 导致计算机资源的利用率进一步变低;
• 为了解决 CPU 与 I/O 设备之间速度不匹配的问题, 引入了『 脱机输入 / 输出 』技术.
  • 用户预先把程序和数据通过 "外围机" 以慢速输入到 "输入带" 上. 当 CPU 需要这些内容时, "输入带" 可以高速传输到内存;
  • 同理, CPU 把输出内容高速地传送到 "输出带", 然后 "传送带" 再通过外围机把内容慢速地传输给外部输出设备;

2 - 单道批处理系统

• 单道批处理系统是最早出现的一种操作系统, 但只能算是现代操作系统的前身, 不算是现代操作系统;
• 为了让计算机可以得到充分地利用, 应尽量使 CPU 连续运行, 减少空闲时间;
• 做法是将一批作业通过脱机输入的方式传输到输入带中, 并在计算机中配置一个『 监督程序 』用来管理作业的运行;
• 计算机在 "监督程序" 的控制下一个一个顺序地处理作业, 直到把所有输入带上的作业都处理完;
• 这便形成了早期的『 批处理系统 』
• 因为监督程序每次只调入一道程序进入内存中让 CPU 运行, 如果程序进行 I/O 操作, 就会造成 CPU 空闲, 导致 CPU 利用率下降;

3 - 多道批处理系统

• 为了进一步提高 CPU 的利用率出现了多道批处理系统;
• 它能将一个以上的作业调入主存中, 并让它们同时处于运行状态. 这些作业间共享处理器, 外设以及其他资源;
• 虽然宏观上多个程序都在运行, 但是任一时间 CPU 上只运行一个程序, 多个程序间轮流使用 CPU, 交替运行;

• 在实现多道批处理系统时, 需要妥善地解决如下的一系列问题:
  • 如何分配处理器给程序, 给谁, 什么时候给, 什么时候回收?
  • 如何给每个程序分配必要的内存空间?
  • 如何让多个程序能共享多种类型的 I/O 设备?
  • 如何保证数据的安全性和一致性;

4 - 操作系统的形成

• 为了解决多道批处理系统里涉及的各种问题, 又在其内部添加了一堆软件, 这样便形成了完整的操作系统;
• 简单说, 操作系统是一组控制和管理计算机硬件和软件资源 ,合理地组织计算机工作流程以及方便用户使用的程序的集合;

# 操作系统的主要功能 & 服务

1 - 处理器管理:

• 操作系统能够对处理器进行分配和运行实施有效的管理;
• 多道程序环境下, 处理器的分配和运行是以『 进程 』为基本单位的. 因此对处理器的管理可以归结为对进程的管理;
• 主要功能如下:

2 - 存储器管理:

• 操作系统能够对内存进行分配, 保护和扩充. 主要功能如下:

3 - 设备管理:

• 操作系统能够对计算机系统内的所有设备实施有效的管理. 主要功能如下:

4 - 文件管理:

• 操作系统能够对计算机中的信息进行管理, 称为『 文件管理 』, 主要任务就是支持文件存储, 检索和修改等操作. 解决文件的共享, 保密和保护问题. 主要功能如下;

5 - 用户接口:

• 为了方便用户使用, 操作系统还提供了用户接口:

# 操作系统的运行环境

# 核心态 & 用户态

为了避免操作系统及其关键数据受到用户程序有意或无意的破坏, 通常将『 处理器的执行状态 』分成两种:

• 核心态 / 系统态: 是操作系统中系统程序执行时所处的状态, 具有较高的特权, 能执行一切指令, 能访问所有的存储器;
• 用户态: 是用户程序执行时所处的状态, 具有较低特权, 只能执行规定的指令, 访问指定的存储器;

# 中断 & 异常

中断, 也称为 "外中断", 是系统正常功能的一部分, 用以在当前进程运行时, 插入一个需要优先处理的操作. 操作完又会继续执行中断前的进程.

异常, 也称为 "内中断", 是错误引起的. 通常异常会引起中断.

# 系统调用

操作系统的一个主要功能是为应用程序运行提供良好的环境, 为了实现这个目的, 内核提供了一系列具有功能的内核函数. 同时, 操作系统提供一组称为『 系统调用 System Call 』的接口给用户, 系统调用可以把应用程序的请求传递给内核, 然后调用响应的内核函数实现预期的功能, 并将处理结果返回给应用程序.

系统调用通常包括的功能有, 进程控制, 文件系统控制, 内存管理, 网络管理, 用户管理, etc;

用户程序调用系统调用时, 会通过『 陷入 trap 』指令引起一个中断, 进入操作系统的系统内核, 此时从 "用户态" 变为 "系统态", 然后执行相应的内核函数, 最后将处理结果返回给应用程序, 此时 "系统态" 变为 "用户态"

# 进程管理

# 进程 & 线程

# 程序并发执行的问题

一个程序由若干个程序段组成, 它们按照先后次序顺序执行. 当处理器在运行一个程序时, 呈现出如下特性:

• 顺序性: 处理器严格按照程序所规定的顺序一步步地执行;
• 封闭性: 程序在运行时独占系统的各种资源, 这些资源的状态只有本程序才能改变, 程序执行结果不受外部因素影响;
• 可再现性: 只要程序执行时的初始条件和执行环境相同, 重复执行程序, 每次结果都相同;

但是当程序并发执行时, 虽然提高了系统的处理能力和资源的利用率, 但是也带来一些新问题:

• 间断性:
• 失去封闭性: 多个程序共享系统中的资源, 那么这些资源的状态可能由多个程序所改变, 致使程序的运行失去封闭性;
• 不可再现性: 因为失去了封闭性, 一个程序在执行时, 可能会受到其他程序的影响. 这也导致运行结果可能每次都不一样;

为了让程序并发执行, 必须要满足一些限制条件, 以保持程序的封闭性和可再现性.

• 将程序 $p_i$ 在执行期间需要 "引用" 的所有变量的集合, 称为『 读集 』 $R(p_i) = \{a_1, a_2, ... , a_m\}$
• 将程序 $p_i$ 在执行期间需要 "改变" 的所有变量的集合, 称为『 写集 』 $W(p_i) = \{b_1, b_2, ... , b_n\}$

当两个程序 $p_1$ 和 $p_2$ 同时满足一下 3 个条件, 它们便可以并发执行, 每个程序都保持封闭性和可再现性. 此条件称为『 Bernstein 条件 』

# 进程的定义 & 描述

因为在多道程序环境下, 程序并发执行会带来如上的问题, 所以就引入了『 进程 』的概念.

进程的定义: 进程是程序在一个数据集合上的运行过程, 是系统进行资源分配和调度的一个独立单位;

进程和程序的关系:

• 程序要执行时, 操作系统创建一个进程, 把程序和需要的数据装入其中, 然后放入内存等待 CPU 执行;
• 进程使程序能够与其他程序并发执行;
• 多个进程同时存在于内存中, 能在一段时间内同时运行;

进程的组成:

进程一般由如下几个部分组成:

• 进程控制块 PCB: 用以唯一标识进程, 存储程序执行瞬间的状态, 以及一些相关信息的数据结构;
• 程序段: 需要执行的程序代码段;
• 数据段: 程序运行需要的原始数据, 程序执行过程中产生的中间或结果数据;

进程控制块 PCB 根据操作系统要求的不同, 所包含的内容也各有不同, 但是一般包含如下:

• 进程标识符 PID: 进程的唯一标识;
• 进程当前状态: 进程的当前状态, 作为进程调度程序分配处理器的依据;
• 进程队列指针: 用以记录 PCB 队列中的下一个 PCB. 系统中的 PCB 可能组织成多个队列. 例如, 就绪队列, 阻塞队列;
• 程序和数据地址: 进程的程序段和数据段所在的地址;
• 进程优先级: 反映进程要求 CPU 的紧急程度, 优先级高的进程可以优先获得处理器;
• CPU 现场保护区: 当进程因某些原因释放处理器时, CPU 现场信息 ( 例如, 指令计数器, 状态寄存器, etc ) 需要保存在 PCB 的该区域中, 以便进程重新获得处理器时可以继续之前的状态执行;
• 通信信息: 记录进程在执行过程中与别的进程信息交换的情况;
• 家族信息: 系统允许进程创建子进程, 从而形成一个进程家族树, 一个进程与家族的关系需要记录在 PCB 的该区域;
• 占有资源信息: 进程所需资源以及已分配资源的清单

# 进程的状态 & 转换

进程在运行过程中, 由于系统中多个进程并发运行以及相互制约的结果, 使得进程的状态不断地变化:

• 创建状态: 进程正在被创建, 向系统申请空白的 PCB 并初始化, 然后系统给该进程分配运行所需的资源, 然后转入就绪状态;
• 就绪状态: 进程已获得了除处理器之外的所有资源, 一旦获得处理器就可以立即执行;
• 执行状态 ( 运行状态 ) : 正在被处理器执行的进程;
• 阻塞状态 ( 等待状态 ) : 正在执行的进程, 因发生了某事件而无法执行下去 ( 例如, 等待 I/O 操作完成 ) 此时进程处于阻塞状态, 需要把处理器分配给其他进程;
• 结束状态: 进程从系统中被删除, 导致进程结束的事件可能是进程正常执行完毕, 进程发送异常, 或者外部干预;

# 线程

进程具有如下两个基本属性:

• 进程是一个拥有资源的独立单元;
• 进程是一个可以被处理器独立调度和分配的单元;

为了使进程能并发执行, 操作系统需要进行一系列进程操作, 例如, 创建进程, 撤销进程, 阻塞/唤醒进程, 进程切换. 在执行这些操作时, 需要为进程分配 / 回收资源, 为运行进程保存现场信息, 这些工作会有很多时间和空间上的花销.

因此, 如果进程操作太多就会导致资源的浪费. 如果限制进程数量, 进程切换的频率又会限制系统的并发程度;

为了使程序更好地并发执行, 需要尽量减少操作系统的开销, 同时保证系统的并发程度, 为此引入了『 线程 』的概念.

线程的定义: 线程是进程中一个相对独立的, 可调度的执行单元. 线程只拥有一些在运行时必须的资源, 一个进程中的线程共享进程拥有的全部资源;

可以理解为, 操作系统的设计者把进程拥有的两个属性分开来, 第一个交给进程, 第二个交给线程;

# 处理器调度

# 处理器的三级调度

在多道程序环境下, 一个作业从提交到执行, 经常需要经历多级调度. 不同的操作系统, 采用的调度层级也不同. 👇 下图展示了 "三级调度" 的过程:

高级调度:

• 也称为 "宏观调度", "作业调度", "长程调度";
• 主要任务是按照一定的原则从外存上处于后备状态的作业中选择一个或多个, 给它们分配内存, I/O 设备等必要资源, 并建立相应的进程;

中级调度:

• 也称 "中程调度", "交换调度";
• 主要任务是按照某种策略, 将处于 "外存对换区" 中具备运行条件的进程调度内存, 并将其状态修改为 "就绪状态", 挂在就绪队列上等待执行;
• 或者将处于内存中暂时不能运行的进程交换到外存对换区, 此时进程的状态被称为 "挂起状态";

低级调度:

• 也称 "微观调度", "进程调度", "短程调度";
• 主要任务是按照某种策略从就绪队列中选取一个进程, 将处理器分配给它;

# 进程调度

将处理器分配给进程的任务是由『 进程调度程序 』完成的.

进程调度的功能:

• 记录系统中所有进程的有关情况 & 状态特性:
  • 将系统中各进程的执行情况和状态记录在 PCB 中, 同时根据各进程的状态和资源需求将 PCB 组织成相应的队列, 并根据运行情况将进程 PCB 在各个队列中进行转换;
• 选择获得处理器的进程:
  • 按照一定的策略选择一个处于就绪状态的进程, 使其得到处理器执行;
• 处理器分配:
  • 当正在运行的进程由于某种原因要放弃处理器时, 进程调出程序需要保存当前进程的 CPU 现场, 然后把它状态改为阻塞或就绪状态, 并插入到对应的队列中;
  • 同时, 从就绪队列中选出一个进程, 恢复其 CPU 现场, 让其得到处理器执行;

引起进程调度的原因:

• 正在运行的进程结束了. 可能是正常结束, 也可能是发生异常而结束;
• 正在运行的进程进入了阻塞状态;
• 执行完系统调用后返回用户进程. 可以看作是系统进程执行完毕, 从而调度到一个新的用户进程;
• 在采用抢占方式的系统中, 一个优先级更高的进程请求使用处理器;
• 在分时系统中, 分配给该进程的时间片用完了;

不能进行进程调度的情况:

• 处理中断的过程中. 中断属于系统工作的一部分, 逻辑上不属于一个进程, 所以不应该剥夺正在处理进程的处理器资源;
• 进程处于临界区时. 在临界区中, 进程独占式的访问共享资源, 期间不应该有其他并行程序打扰;
• 执行需要完全屏蔽中断的原子操作中. 例如, 加锁, 解锁, 中断线程保护, 恢复等不可再分和打断的原子操作;

进程调度的方式: 当一个进程正在执行时, 如果一个更为重要或紧迫的进程需要进行处理 ( 优先级更高的进程进入就绪队列 ) , 该如何分配处理器;

• 抢占方式 ( 可剥夺方式 ) : 立即执行正在执行的进程, 将处理器分配给优先级更高的进程;
• 非抢占方式 ( 不可剥夺方式 ) : 正在执行的进程继续执行, 直到该进程完成或变成阻塞状态时, 才把处理器分配给优先级更高的进程;

# 常见调度算法

先来先服务调度算法 ( 作业调度, 进程调度 ) :

• 最简单的调度算法. 基本思想是按照进程进入就绪队列的先后顺序来分配处理器. 采用 "非抢占" 的调度方式;
• 缺点: 该算法对于每一个进程都是公平的, 假设有一个长进程 ( 执行完毕花费 $10t$ ) 一个短进程 ( $1t$ ). 如果长进程先执行, 短进程就要等待 $10t$. 而如果短进程先执行, 长进程只需要等待 $1t$

短作业 ( 进程 ) 优先调度算法 ( 作业调度, 进程调度 ) :

• 基本思想是把处理器分配给能最快完成的作业 ( 或进程 )
• 缺点: 如果多个短进程不断地进入就绪队列, 长进程就会一直等待处理器, 得不到执行, 这个现象叫做 "饥饿";

优先级调度算法 ( 作业调度, 进程调度 ) :

• 基本思想是把处理器分配给优先级最高的进程;
• 优先级相同的情况下, 一般按照 "先来先服务" 或 "短作业优先" 的策略来选择进程执行;

进程优先级的确定分为两种:

• 静态优先级: 创建进程时确定的.

  • 确定静态优先级主要依据有如下几种:
    • 进程类型: 系统进程的优先级高于用户进程;
    • 作业的资源要求: 进程所申请的资源越多, 那么估计运行的时间就越长, 优先级也就越低;
    • 用户类型: 计算机可以按照不同的标准分类, 不同用户创建的进程优先级可以设置差别;

• 动态优先级: 创建进程时先确定一个优先级, 然后在进程运行过程汇总该根据情况调整优先级.

  • 确定动态优先级主要依据有如下几种:
    • 进程占有 CPU 时间的长短: 一个进程占用 CPU 的时间约长, 优先级越低, 再次获得调度的可能性变小;
    • 就绪进程等待 CPU 时间的长短: 一个进行在就绪队列中等待的时间越长, 优先级越高, 获得调度的可能性越大;

时间片轮转调度算法 ( 进程调度 ) :

• 在分时系统中, 进程的调度通常采用时间片轮转调度算法;
• 每个进程被执行时, 会规定一个执行时间, 称为 "时间片". 当时间到了之后, 系统就把正在执行的进程暂停, 然后送至就绪队列末尾. 之后再把处理器分配给下一个就绪进程;

高响应比优先调度算法 ( 作业调度 ) :

• 结合了 "先来先服务" 和 "短作业优先" 的两种调度算法的优点;
• 基本思想是每次进行作业调度时, 先计算就绪队列中每个作业的响应比, 挑选响应比最高的作业投入运行;
• 响应比 = 作业响应时间 / 估计运行时间;
• 同时照顾到短作业和长作业, 短作业运行时间短, 响应比较高. 长作业在等待事件很长时, 响应比也变高;

多级队列调度算法 ( 进程调度 ) :

• 基本思想是根据进程的性质和类型, 将就绪队列分为若干个独立的队列, 每个进程固定地属于一个队列, 每个队列采用一种调度算法, 不同的队列可以采用不同的调度算法;

多级反馈队列调度算法 ( 进程调度 ) :

• 结合了 "时间片轮转优先级调度算法" 和 "优先级调度算法";
• 首先设置多个就绪队列, 每个队列对应不同的优先级, 进程所在的队列的优先级越高, 该队列采用的时间片就越短; 当前一个队列为空时, 后一个队列中的进程才会被调度;
• 当处理器正在运行某个进程时, 如果有新进程进入了优先级更高的队列中, 此时新进程将抢占正在运行进程的处理器;

# 同步 & 互斥

# 同步 & 互斥的基本概念

互斥 - 间接相互制约关系:

• 定义: 若某一资源同一时间只能被一个进程使用. 一个进程占用资源时, 另一个进程想使用必须等待前一个进程释放资源之后才行. 这两个进程间呈现出 "互斥" 的关系.
• 为了维持两个进程间的互斥关系, 系统应当遵循如下准则:

同步 - 直接相互制约关系:

• 定义: 若一个进程收不到另一个进程给它提供的必要信息就无法运行下去, 这两个进程呈现出 "同步" 的关系.

临界资源 & 临界区: 把同时仅允许一个进程使用的资源称为『 临界资源 』

• 为了保证对临界资源的正确使用, 可以把对临界资源的访问过程分为如下 4 个部分, 它们都属于要访问临界资源的进程, 是进程中的一部分代码:
  • 进入区: 在进入临界区使用临界资源之前, 需要在进入区检查该进程是否可以进入临界资源;
  • 临界区: 进程中用于访问临界资源的代码;
  • 退出区: 释放对于临界区相应的限制, 允许其他进程进入;
  • 剩余区: 进程中除了上述三个部分之外的其他代码;

# 互斥实现方法

可以通过软件方法, 或者硬件方法来实现进程间互斥. 下面 👇 只介绍软件方法的实现:

算法 1:

设置一个公用整形变量 turn, 用来表示允许进入临界区的进程标识.

• 若 turn 为 0, 则允许进程 $P_0$ 进入临界区. 否则循环检查该变量, 直到 turn 变为 0;
• 在 $P_0$ 的退出区, 修改 turn 为 1, 此时进程 $P_1$ 则可以进入临界区;
• 在 $P_1$ 的退出区, 再把 turn 改为 0. 如此循环往复;

此方法强制两个进程交替地进入临界区, 很容易造成资源利用不充分:

• 🌰 例如, $P_0$ 在退出区把 turn 改为 1 允许 $P_1$ 进入临界区, 但是此时 $P_1$ 并不想访问临界资源, 而 $P_0$ 想再次访问临界资源, 可是 $P_0$ 却无法进入临界区;
• 此算法没有实现『 空闲让进 』的准则;

算法 2:

设置标示数组 flag[] 来表示进程是否在临界区中执行:

• 每个元素的初始值均设置为 false;
• 在每个进程访问该临界资源之前, 先检查另一个进程是否在临界区中, 若不在, 则修改本进程对应的临界区标志为 true 并进入临界区;
• 在退出区修改本进程对应的临界区标志为 false;

虽然解决了 "空闲让进" 的问题, 但是也带来了新的问题:

• 🌰 例如, 如果两个进程同时都想进入临界区, 并且发现对方的临界区标志都为 false, 于是两个进程同时进入了各自的临界区;
• 这样就违背了『 忙则等待 』的准则;

算法 3:

设置标志数组 flag[] 表示进程是否 "希望" 进入临界区:

• 每个进程在访问临界资源之前, 先将自己的标志设置为 true, 表示希望进入临界区;
• 然后检查另一个进程的标志, 如果也为 true, 则进程等待. 反之, 则进入临界区;

虽然可以防止两个进程同时进入临界区, 但是可能会出现两个进程同时进不了临界区的问题:

• 🌰 例如, 两个进程都想进入临界区, 它们把自己的标志都设置为 true, 同时去检查对方的状态, 发现对方也想进入临界区. 于是双方都开始等待, 导致谁也进不去临界区;
• 这就造成了『 死等 』的现象, 违背了『 有限等待 』的准则;

算法 4:

是 "算法 1" 和 "算法 3" 的结合.

标志数组 flag[] 表示进程是否希望进入临界区, 或是否正在临界区中执行, 此外还设置一个 turn 变量, 表示允许进入临界区的进程标识:

• 在进程想进入临界区时把对应的 flag 标志设置为 true. 同时把 turn 标志设为允许另一个进程进入临界区;
• 如果恰好此时另一个进程也想进入临界区, 它也会执行上述的操作;
• 无论怎么样, 两个进程同时想进入临界区时, 必定只有一个进程的 flag 标识为 true 同时 turn 标识对应到它. 则此进程进入临界区, 另一个进程等待;

# 信号量

荷兰的计算机科学家 Dijkstra 在 1965 年提出了一个同步机构, 称为『 信号量 』基本思想是, 在多个互相合作的进程之间使用简单的信号来同步.

信号量是一个确定的二元组 (s,q):

• s 是一个具有非负初值的整型变量, 表示系统中的某类资源的数目.
  • 值大于 0 时, 表示系统中当前可用资源的数目;
  • 值小于 0 时, 表示系统中因请求该类资源而被阻塞的进程的数目;
• q 是一个初始状态为空的队列, 用以存放等待访问该资源的进程;

建立信号量时, 必须说明 s 的意义和初始值, 并且安排一个空队列;

信号量的值只能由 $P$ 操作 ( wait 操作 ) 和 $V$ 操作 ( signal 操作 ) 改变;

• $P(s)$ 执行时, 先执行 s = s - 1, 若 s >= 0 则该进程继续运行. 若 s < 0 则阻塞该进程, 并将它插入到该信号量的等待队列中;
• $V(s)$ 执行时, 先执行 s = s + 1, 若 s > 0 则继续执行该进程. 若 s <= 0 则从该信号量等待队列中移出第一个进程, 将其插入到就绪队列, 然后再返回原进程继续执行;

信号量实现进程同步:

假设存在并发进程 $P_1$ 和 $P_2$. $P_1$ 中有一条语句 $S_1$, $P_2$ 中有一条语句 $S_2$, 要求 $S_1$ 必须在 $S_2$ 之前执行.

信号量实现进程互斥:

假设有进程 $P_1$ 和 $P_2$, 两者有各自的临界区, 系统要求同时只能有一个进程进入自己的临界区.

# 经典同步问题

生产者 - 消费者问题:

生产者 - 消费者是对许多相互合作的进程的一种抽象, 描述了一组生产者向一组消费者提供产品, 它们共享一个缓冲区, 生产者向里投入产品, 消费者从中取走产品;

---

读者 - 写者问题:

有许多进程共享一个数据区, 一些进程只向数据区执行 "读取" 操作, 一些进程只向数据区执行 "写入" 操作. 需要满足如下条件:

• 任意多个读者可以同时读数据;
• 一次只能有一个写者可以写入;
• 如果一个写者正在写入, 禁止任何读者执行读操作;

该问题可以分情况有多种实现:

• 读者优先算法: 只有当没有读者进行读操作时, 写者才可以写入, 否则写者就等待, 直至所有读者都不再读取数据区;

  • 设置整型变量 readcount, 用以记录当前正在读取数据区的读者的数量, 初始值为 0. 大于 0 时, 写者不可以执行写操作;
  • 设置互斥信号量 rmutex 初始值为 1, 用以保证多个读者进程对于 readcount 的互斥访问;
  • 设置互斥信号量 mutex 初始值为 1, 用以控制写者进程对数据区的互斥访问;

• 公平情况算法: 进程执行的顺序完全按照到达顺序. 即当有读者试图进行读操作时, 如果有写进程正在进行写操作, 后续到达的读者要进行等待;
  • 和读者优先算法相比, 增加一个信号量 wmutex 初始值为 1, 表示是否有写者正在执行, 或在等待执行写操作. 通过 wmutex 可以让读写进程按照到达顺序执行, 避免读者进程优先;

• 写者优先算法: 当写者和读者同时等待时, 写者先执行, 只要等待队列中有写者, 不管何时到达, 都优先与读者执行;
  • 设置信号量 readable 用以控制写者到达时可以优先于读者进入临界区. 第一个写者到达后申请占用 readable, 最后一个写者离开后释放 readable, 期间读者一直申请不到 readable 信号量, 所以就一直被阻塞;
  • 设置整型变量 writecount 用以记录写者的数量;
  • 设置信号量 wmutex 用以控制写者间互斥访问 writecount;
  • 设置信号量 mutex 用于控制写者对数据区的互斥写入;

---

哲学家进餐问题: 5 个哲学家围绕着一个圆桌而坐, 桌上放着 5 根筷子, 每两个哲学家之间有一根筷子. 哲学家的工作包括 "思考" 和 "进餐", 进餐时需要同时拿起左右两边的两根筷子, 思考时将筷子放回原处.

• 在这个问题中, 筷子是临界资源, 同一根筷子不能被两个哲学家同时使用, 因此需要设置一个信号量数组来控制哲学家对筷子的使用;

• 为了防止『 死锁 』的发生 ( 假设 5 个哲学家同时拿左边的筷子, 然后再想拿右边筷子的时, 会因为没有筷子而无限等待 ) 将哲学家编号, 奇数号的哲学家先拿左边的筷子, 偶数号的哲学家先拿右边的筷子;

---

理发师问题: 理发店有一个理发师, 一把理发椅和若干供顾客等待的凳子:

• 没有顾客时, 理发师休息.
• 当有一个顾客到来时, 同时没有顾客在剪发, 则顾客坐在理发椅上剪发;
• 如果有顾客正在剪发, 则找椅子坐下来等待;
• 如果没有空椅子, 则顾客离开;

第一种思路: 将理发椅和等待的椅子看作是两种不同的资源;

第二种思路: 将理发椅和等待的椅子看作是同一种资源;

# 死锁

一组进程中, 所有进程都处于永久阻塞的状态, 每个进程都在无限期地等待某个其他进程占用的资源, 若无外力作用, 这些进程将永远无法向前推进. 这种现象叫做『 死锁 』

🌰 例子：

例如, 系统中有一台打印机和一台输入设备, 进程 $P_1$ 占用输入设备, 同时提出使用打印机的请求. 但是此时打印机被进程 $P_2$ 占用. 而 $P_2$ 在未释放打印机之前, 又提出请求使用正在被 $P_1$ 占用的输入设备. 这样两个进程就无休止地等待下去, 无法继续执行了.

# 死锁产生的原因

可以把系统中的资源分为:

• 可剥夺资源: 即使资源正被一个进程所占有, 但另一个进程可以强行把该资源剥夺过来自己使用;
  • 进程对于可剥夺资源的竞争不会造成死锁;
• 不可剥夺资源: 一个进程不可以剥夺另一个进程所占有的资源, 资源只能被占用进程主动释放;
  • 进程对于不可剥夺资源的竞争可能会造成死锁;

一个资源属于哪一种分类, 取决于资源的性质.

• 🌰 例如, 打印机就是一个 "不可剥夺资源", 而主存和 CPU 就是 "可剥夺资源".

---

死锁产生的原因是进程间竞争资源. 如果系统中只有一个进程在运行, 它独享所有的资源, 就不会有死锁发生了.

下图 👇 展示了进程 $P_1$ 和 $P_2$ 的运行时对资源的请求步骤.

$P_1$ 和 $P_2$ 进程对资源 A 和 B 产生了竞争, 但是资源竞争不一定会产生死锁, 只有进程运行过程中请求和释放资源的顺序不当时, 才会导致死锁.

下图 👇 展示了不同执行顺序时, 两条进程运行的情况;

• 在路径 ④ 中, $P_2$ 先申请资源 B, $P_1$ 再申请资源 A. 此时资源 A 和 B 都被占用了, 进程 $P_1$ 没有办法申请资源 B, 进程 $P_2$ 也没有办法申请资源 A. 进程陷入了死锁.
• 其他执行路径下, 两条线程都可以顺利执行;

# 死锁产生的必要条件

从上面的论述可以推出, 死锁产生的必要条件有如下 4 条:

# 处理死锁的基本方法

目前处理死锁的方法主要有 4 种:

1. 鸵鸟算法: 对死锁视而不见, 不解决死锁;
2. 预防死锁: 通过设置某些限制条件, 去破坏产生死锁的 4 个必要条件中的一个或几个来预防死锁的产生;
3. 避免死锁: 在资源的动态分配过程中, 用某种方式避免系统进入可能会产生死锁的不安全状态, 从而避免死锁的产生;
4. 检查及解除死锁: 及时检测出死锁的发生, 然后采取某种措施解除死锁;

# 死锁的预防

要想防止死锁, 只需破坏产生死锁的 4 个必要条件之一即可.

1 - 破坏互斥条件: 允许多个进程同时访问同一个资源, 但有些资源同一时间只能被一个进程访问. 所以通过破坏互斥条件来防止死锁的发生是不太可取的方案;

2 - 破坏不剥夺条件: 对于一个已经获得某些资源的进程, 若进程想要请求的新资源不能被满足, 则它必须释放所有已经获取的资源, 等以后再重新申请资源.

• 这种方式使得进程之前为获得资源所做的工作都被抛弃了, 造成了系统开销的浪费, 降低了系统吞吐量;
• 这种方式通常不会应用于剥夺资源后代价太大的场合;

3 - 破坏请求与保持条件: 可以采用 "预先静态分配方式", 在进程运行前一次性申请所有所需的资源, 在资源未满足之前不投入运行. 一旦投入运行, 这些资源就一直归他所有. 但是这样对于那些在进程中只在后期采用到, 或者在某些情况下根本不会用到的资源, 也要预先申请, 导致资源不能被充分利用, 资源利用率下降;

4 - 破坏环路等待条件: 可以采用 "有序资源分配法", 将系统中所有的资源按照类型赋予一个编号, 要求每个进程严格按照编号递增的次序请求资源, 同类资源一次性申请完. 这样就不会出现进程对资源的请求出现环路的情况. 但是对于资源编号后不宜修改, 限制了新资源的添加. 而且不同作业对于资源的使用顺序也不可控, 也增加了程序编程的复杂性;

# 死锁的避免

"预防死锁" 中介绍的策略, 都施加了较强的限制条件. 实现起来简单, 但是限制了系统性能.

"避免死锁" 的方法中, 所施加的限制较弱, 有可能获得较好的系统性能.

安全状态 & 不安全状态:

在避免死锁的方法中, 允许进程动态的申请资源, 系统在资源分配之前, 先计算资源分配的安全性.

• 若某一时刻, 系统能按照某种顺序为每个进程分配所有所需的资源, 使得每个进程都能顺利完成, 则成为此时的系统处于『 安全状态 』称该序列为『 安全序列 』
• 若某一时刻不存在这样的安全序列, 则称系统状态为『 不安全状态 』, 有可能会发生 "死锁"

银行家算法:

最具有代表性的避免死锁的算法是 "银行家算法". 假设系统中有 $n$ 个进程 $(P_1, P_2, ... , P_n)$ , $m$ 类资源 $(R_1, R_2, ... , R_n)$, 银行家算法中需要创建如下的数据结构:

• 可利用资源向量 Avaliable: 含有 $m$ 个元素的数组, 其中 Avaliable[i] 的值表示第 i 类资源现有的空闲数量, 其初始值为该资源的总数量, 其值随着资源的分配与回收动态变化;
• 最大需求矩阵 Max: 是一个 $n x m$ 的二维数组矩阵, 定义了系统中每一个进程对每类资源的最大需求数量, Max[i][j] 表示的值是第 i 个进程对第 j 类资源的最大需求数;
• 分配矩阵 Allocation: 是一个 $n x m$ 的二维数组矩阵, 定义了系统中每一类资源当前以及分配给每一个进程的资源数目. Allocation[i][j] 表示的值是第 i 个进程当前拥有的第 j 类资源的数量;
• 需求矩阵 Need: 是一个 $n x m$ 的二维数组矩阵, 定义了每个进程还需要的各类资源的数目;

银行家算法的描述:

定义 $Request_i$ 向量, 表示第 i 个进程向系统提出的一次申请, 申请的各类资源的数量就是该向量的各个分量;

安全性算法的描述:

🌰 例子：

# 死锁的检测 & 解除

死锁检测:

进程对于资源的请求与占用可以用 "资源分配图 System Resource Allocation Graph, SRAG" 来表示.

• 用圆圈代表进程. 用方框代表每类资源, 框内用圆圈代表资源的个数;
• "申请资源" 用一条从进程到资源的有向边来表示;
• "分配资源" 用一条从资源到进程的有向边来表示;

上图 👆 表示的状态如下:

• 进程 $P_1$ 已经占用两个 $r_1$ 资源, 而且正在申请一个 $r_2$ 资源;
• 进程 $P_2$ 已经占用一个 $r_1$ 资源和一个 $r_2$ 资源, 而且正在申请一个 $r_1$ 资源;

可以通过简化资源分配图的方式来检测是否系统状态 $S$ 是死锁状态:

• 在图中找到一个 "即不拥塞又非孤立" 的进程节点 $P_i$ ( 存在与资源连接 ) 并且申请资源的数量小于系统中已有的空闲资源的数量;
• 也就是说 $P_i$ 可以获得所需的所有资源, 并且正常完成运行, 然后释放占用的所有资源. 相当于 $P_i$ 消去所有与资源连接的边, 变成一个孤立的节点;
• 进程 $P_i$ 释放完资源后, 可以唤醒那些因等待资源而 "阻塞" 的进程成为 "非阻塞进程", 然后再按照上面的步骤进行简化;
• 重复前面的两个步骤之后, 如果能消去图中所有的边, 则称该图是『 可完全简化的 』否则就是『 不可完全简化的 』, 系统处于 "死锁" 状态;

死锁检测算法:

死锁检测算法通过判断某一时刻系统是否处于 "不可完全简化的" 状态, 来判断是否系统发生了死锁. 具体思路:

• 获得某时刻 t 系统中各类可利用资源的数目向量 avaliable(t);
• 然后找出一个即不拥塞又非孤立的进程, 它对各类资源请求的数目均小于系统现有的各类可用资源的数目. 也就是说它能获得所有所需的资源, 正常运行结束, 然后释放占用的资源;
• 把这样的进程加入到 "可运行结束" 的进程序列中. 然后假设该进程执行结束, 释放了所有资源, 之后再对剩下的进程再进行上述的考察;
• 如果有几个进程不能加入 "可运行结束" 序列的话, 那么系统就发生了死锁;

死锁解除:

一旦检测出死锁, 就应该让陷入死锁的进程从死锁状态中解除出来. 常用方法有 3 个:

# 死锁 & 饿死

有的时候系统的资源分配策略是不公平的, 可能进程间不会发生死锁, 但是有的进程需要等待很长时间才能获得所需的资源. 这个等待时间给进程的执行带来了明显的影响, 这种现象称为『 进程饥饿 』当饥饿达到一定程度, 即使进程执行完毕可能也不再具有实际意义时, 称为『 饿死 』

与饥饿相关的一个概念是『 活锁 』, 指的是进程发生了饥饿, 一直在等待资源, 不能继续执行, 好像 "死锁" 一样. 但是进程最终是可以得到资源的;

# 内存管理

# 内存管理基础

应用程序从源文件到内存中执行的进程, 大致分为 3 个阶段:

1. 通过 "编译程序 Compiler" 将源代码编译成若干个 "目标模块 Object Module";
2. 然后通过 "链接程序 Linker" 将目标模块以及程序所需的类库链接在一起, 形成完整的 "装入模块 Load Module";
3. 最后, 通过 "装入程序 Loader" 将装入模块装入内存并执行;

• 对于程序开发者来说, 它们并不需要知道数据和程序段存放的具体地址, 它们通过给数据和程序段用标识符命名, 然后通过名称就可以对其进行访问了. 这些名称称为程序『 名地址 / 符号名地址 』
• 源代码编译成目标代码后, 并一起无法得知代码最终在内存中的物理位置, 所以 0 号单元开始编址, 这称为程序的『 相对地址 / 虚拟地址 / 逻辑地址 』
• 链接程序把多个从 0 号开始编址的模块, 链接成一个装入模块时, 会按照各个模块的相对地址将其地址构成统一的从 0 开始编址的相对地址;
• 当装入程序把装入模块装入内存时, 通过地址转换将逻辑地址转换成实际的『 物理地址 』, 这个过程叫做『 重定位 』

程序的 "装入" 有 3 种方式:

• 绝对装入: 编译时就知道程序将要驻留在内存的物理地址，编译程序产生含有物理地址的目标代码;
• 可重定位装入: 根据内存当前的状况，将装入模块装入到内存的适当位置，地址变换通常在装入时一次完成之后不会再改变。这种方式也称为『 静态重定位 』。实现起来非常简单，将操作系统为程序分配了一个以某地址为起始地址的一个连续主存区域后，重定位是将程序中指令或者操作数的逻辑地址加上这个起始地址就得到了物理地址。
  • 要求为每个程序分配一个连续的储存区, 如果空间不足以放下程序就不分配, 程序执行期间不能移动, 不能再申请新的内存;
• 动态运行装入: 允许程序运行时在内存中移动位置。装入模块装入到内存后，所有的地址都是相对地址，在程序执行过程中，每当访问到相应的指令或数据时，才将对应的相对地址转化为物理地址。也称为『 动态重定位 』。实现时要依靠硬件地址变换机构。
  • 可以将程序分配到不连续的存储区中, 程序运行之前装入它的部分代码即可投入运行, 程序运行期间可以根据需求动态申请新内存;

# 覆盖 & 交换

覆盖技术 Overlay:

• 主要应用于早期的操作系统中, 早期计算机中内存的容量很小, 某些大作业不能一次性装入内存中;
• 覆盖技术把一个大的程序划分成一系列相对独立的程序单位, 每个单位称为『 覆盖 』
• 把程序执行时并不要求同时装入内存的覆盖组成一组, 称为『 覆盖段 』
• 覆盖段分配到同一个存储区域, 称为『 覆盖区 』, 覆盖区的大小由对应覆盖段中最大的覆盖来确定. 每次只将覆盖段中的一个覆盖装入内存中;
• 覆盖技术打破了必须将一个进程的全部信息都装入主存才能运行的限制;

交换技术 Swapping:

• 交换技术把暂时不用的某个程序及数据部分从内存移到外存中去, 以便腾出必要的内存空间;
• 处理器三级调度中的 "中级调度" 就采用了交换技术, 把暂时不用的进程移入外存;
• 交互记住打破了一个程序一旦进入主存便一直运行到结束的限制;

# 内存管理的功能

总的来说, 操作系统提供的内存管理主要包含如下功能:

• 内存的分配 & 回收: 为程序的运行提供内存的分配与回收;
• 地址变换: 将程序的逻辑地址转换成内存中的物理地址;
• 扩充内存: 为用户提供比物理内存空间更大的虚拟地址空间, 从逻辑上实现扩充内存容量的目的;
• 存储保护: 保证进入内存的各个进程都在自己的存储空间内运行, 互不干扰;

# 连续分配管理方式

连续分配只允许将一个程序装入到连续的内存分区中.

内部碎片 & 外部碎片：

在介绍连续分配管理方式之前, 先介绍 "内部碎片" 和 "外部碎片" 概念:

• 内部碎片: 已经分配给进程, 但是不能被利用的内存空间;
• 外部碎片: 因为空间太小, 而无法分配给申请内存的新进程的内存空间;

# 单一连续分配

• 最简单的存储管理方式, 通常只用于单用户, 单任务的操作系统中;
• 将内存分为两个连续存储区域, 一个区域固定地分配给操作系统使用. 另一部分给用户作业使用, 通常用户作业只占用一部分内存, 剩下的内存空间就被浪费掉了, 会产生 "内部碎片";
• 采用 "静态重定位" 方式把进程装入内存, 适合单道程序, 可采用覆盖技术. 进程一旦进入内存, 就要等待进程结束才能是否内存. 无法实现多道程序共享内存;

# 固定分区分配

• 是一种最简单的适应于多道程序的存储管理方式;
• 将内存划分为若干个固定大小的分区, 每个分区可以装入一道程序. 分区大小可以不等, 但事先必须确定, 运行时不可以更改;
  • 系统需要一张分区说明表, 以记录可用于分配的分区号, 分区的大小, 分区的起始地址, 以及分区状态;
  • 当某个用户程序要装入内存时, 由 "内存分配程序" 检索分区说明表, 找出能满足需求的 "未分配" 分区分配给该程序. 然后修改分区说明表中相应分区的状态为 "已分配". 如果找不到大小足够的分区, 则拒绝为此程序分配内存;
• 采用 "静态重定位" 方式进程装入内存. 不能实现多道程序共享一个主存空间, 内存利用率较低, 会产生 "内部碎片";

# 动态连续分配

是一种动态划分内存空间的存储管理方式. 在作业进入主存时, 根据作业大小动态地建立分区, 使分区的大小刚好满足作业的需求;

分区分配中的数据结构:

需要创建相应的数据结构来记录内存的使用情况, 常用的有两种形式:

• 空闲分区表: 设置一个表格来登记内存中的空闲分区, 每个表项包含分区号, 起始地址, 空间大小, 状态;
• 空闲分区链: 设置一个链表把内存中的空闲分区用指针链接起来. 用每个空闲分区的起始的若干字节空间存放相关信息, 以及一个指向下一个空间的指针;

分区分配的算法:

需要按照一定的策略从空闲分区表中选出一个满足作业需求的分区分配给作业. 如果空闲分区的容量大于作业需要的空间大小, 则把多出来的空间仍然留在空闲分区表中, 同时需要对空闲分区表中相关的信息进行修改.

目前常用的分配算法有 4 种:

1. 首次适应算法:
   • 把空闲分区按照 "地址递增" 的次序在空闲分区表上顺序排列, 每次分配内存时从队首开始找, 直到找到足够大的空闲分区, 然后按照作业大小从空闲分区划分一块内存空间给作业. 剩下的部分留在空闲分区表;
   • 由于经常有被分割下来的剩余空间, 所以会导致存在很多 "外部碎片". 而且每次都从头开始找空闲分区, 加大了查找的开销;
2. 下次适应算法:
   • 在 "首次适应算法" 的基础上, 把队列改成循环队列. 而且每次从上次找到的空闲分区的下一个分区开始找;
   • 不用每次都从头开始找, 减少了查找的开销. 但是可能每次查找到的空闲分区的大小可能要比作业需要的大很多, 导致大的空间被切分, 致使缺乏大的空闲分区;
3. 最佳适应算法:
   • 要求将空闲分区按照 "容量大小递增" 的次序排列, 每次未作业分配空间时, 都能找到满足空间大小的最小的空闲分区;
   • 但是也会产生很多 "外部碎片";
4. 最差适应算法:
   • 要求将空闲分区按照 "容量大小递减" 的次序排列, 每次总是将满足要求的最大的空闲空间分配给作业;
   • 会造成大的空闲空间被分割, 致使缺乏大的空闲分区;

分区的回收:

• 作业执行结束后, 系统回收已使用完毕的分区. 根据回收分区的大小和首地址, 在空闲分区表中查找其有没有相邻的空闲分区, 如果有的话就将它们合并成一个大的空闲分区, 并修改相关的分区信息;

分区分配的动态管理:

通过经常的切割空闲分区, 产生了很多个 "外部碎片". 致使最终有一堆空间很小的空闲分区, 分区的大小都不足以放入一个作业了.

为了能够对这些分区进行利用, 需要进行分区分配动态管理. 常用方法有如下两种:

• 拼接技术: 将已分配分区全部移动到主存的一端, 将内存中无法被利用的存储空间连接成一个大的空闲分区;
• 动态重定位分区分配技术: 在分配算法中添加拼接功能;

优缺点:

• 优点:
  • 实现了多道程序共用主存, 也就是多个进程同时存在于主存的不同位置;
• 缺点:
  • 主存利用不够充分, 存在 "外部碎片";
  • 没有实现多进程共享主存, 也就是多个进程都使用同一个内存空间;
  • 没有实现主存的扩充. 进程可使用的内存地址空间依旧是内存的物理空间大小;

# 非连续分配管理方式

非连续分配允许将一个程序分散地装入到不相邻的内存分区中.

根据分区大小是否固定分为:

• 分页存储管理: 根据运行作业时是否需要把作业的所有页都装入内存才能运行而分为:
  • 基本分页存储管理方式;
  • 请求分页存储管理方式;
• 分段存储管理;

# 基本分页存储管理方式

分页的原理:

• 用户作业的地址空间被划分为若干个大小相等的区域, 称为『 页 / 页面 』
• 将主存的存储空间也分为与页面大小相等的区域, 称为『 块 / 物理块 』
• 在为作业分配存储空间时, 总是以 "块" 为单位来分配, 可以将作业中的任意一页放到主存的任意一块中;
• 在进行进程调度时, 必须将作业的所有页面一次调入主存. 如果主存中没有足够的物理块, 则作业等待.这种储存管理方式称为『 简单分页 / 纯分页 』

分页存储管理系统中的 "逻辑地址" 包含两个部分:

• 页号 P;
• 页内位移 W:

假设逻辑地址为 $A$, 页面的大小为 $L$:

• 页号 $P = (int) \hspace{4px} A / L$
• 页内位移 $W = A \% L$

页表:

使用 "页表" 记录页面与内存块的映射关系. 页表中的每项由 "页号" 和 "块号" 组成.

基本地址变换机构:

使用一个 页面寄存器 PTR 来存放页表在内存中的起始地址和页表的长度.

具有 "快表" 的地址变换机构:

可以在地址变换机构中添加一个具有并行查找功能的高速缓冲存储器, 称为『 快表 』存放正在运行的作业正在访问的那些页表项, 其余部分仍旧放在内存中.

两级页表:

• 随着页号位数的增加, 页表长度会指数增加. 会导致整张页表很难连续地存放在内存中;
• 两级页表将逻辑地址划分为 "外层页号" "外层页内地址" "页内地址";
  • 先用外层页号 P1 在 "外部页表" 上查找, 找出对应的 "二级页表" 的首地址;
  • 然后用二层页表的首地址, 加上外层页内地址 P2 得到页表项地址;
  • 取出里面的值 ( 即物理块号 ) 与页内地址 d 相结合就得到物理地址;

页的共享: 实现共享的方式是, 让共享的用户地址空间中的页指向相同的物理块;

# 基本分段存储管理方式

• 作业的地址空间由若干个逻辑分段组成. 每个分段有自己的名字;
• 每个分段都是从 0 开始编址, 并采用一段连续的地址空间;
• 各段之间不要求连续;

段表及地址变换过程:

系统为每个进程建立了一个 "段表", 来记录每个分段的逻辑地址与物理地址的映射关系. 表项中包含 "段号", "段长", "段的内存起始地址"

系统中设置 段表寄存器 来存放段表的起始地址和段表长度.

分段的共享: 通过使多个作业的段表中相应表项都指向被共享段的同一个物理副本来实现;

分段和分页的区别:

# 基本段页式存储管理方式

地址空间首先被分为若干个逻辑分段, 每段都有自己的段号. 然后再奖每一段分为若干个大小固定的页. 主存空间分为若干个页面大小的物理块;

系统需要为每个进程建立一张 "段表" 和一张 "页表". 需要配置一个段表寄存器来储存 "段表" 的起始地址和长度;

# 虚拟内存管理

前面介绍的存储管理方式需要将程序一次性全部地装入内存才可以运行, 并且知道运行结束才释放资源.

在程序执行的过程中, 有很多代码是很少用到的 ( 例如, 错误处理代码 ), 或者需要较长时间的 I/O 操作. 如果按照上面的做法把程序装入内存, 会造成空间利用率的降低.

为此需要一种能只装入部分程序就可以让程序运行的存储管理技术, 即虚拟内存管理技术;

局部性原理:

• 时间局部性: 刚刚执行过的指令, 或访问过的数据, 在一个较短的时期内还会再次访问;
• 空间局部性: 一段时间内调用的指令, 访问的数据, 都在集中在同一段空间里;

虚拟内存的定义和特征:

• 基于局部性原理, 在程序装入时, 只讲一部分放入内存, 其余部分放在外存 ( 部分装入 )
• 在程序执行时, 如果访问的信息不在内存里, 再去外存中调入需要的部分进入内存 ( 请求调入 )
• 另一方面将内存中暂时不需要的信息拿出来放到外存上, 从而腾出空间存放要调入内存的信息 ( 置换功能 )

内存容量在逻辑上被扩充了, 构成了『 虚拟内存 』用户在运行程序时, 可以突破物理内存容量的限制;

# 请求分页存储管理方式

"分页存储管理方式" 需要一次性把程序的所有页面都装入内存, 当程序太大时就无法被装入内存执行了.

"请求分页存储管理方式" 等同于 "分页存储管理方式" + "请求调页功能" + "页面置换功能"

• 作业运行前, 只需要将程序的一部分页面装入主存, 就可以运行程序了;
• 在访问过程中, 根据需要从外存调入新的页面装;
• 通过置换功能可以将不用的页面放入外存上;

页表结构:

缺页中断 & 地址变换

若系统发现要访问的页面不再内存中, 便会发出一个 "缺页中断信号", 此时用户程序被中断, 控制转入操作系统的缺页中断处理程序上.

# 页面置换算法

页面置换算法是用来选出内存中不需要的, 要被换出去存入外存的页面的算法.

先进先出 FIFO 算法:

• 最简单的页面置换算法, 总是淘汰掉最先进入内存的页面, 也就是总是淘汰掉在内存中驻留时间最长的页面, 使用队列来实现;
• 但是最早调入的页面往往是最频繁使用的, 所以该算法可能与实际运行规律不符;

最少使用 LRU 算法:

• 淘汰最长时间没有被使用的页面, 使用寄存器组和栈来实现, 性能较好;

时钟置换 CLOCK 算法:

• 也称为『 最近未使用 NRU 算法 』
• 给每个页面设置一个 "访问位", 用以标识该页面最近有没有被访问过. 维护了一个内存中所有页面组成的循环链表, 当程序访问了链表中的页面时, 页面的访问位就设置为 1;
• 如果页面不存在于链表中, 就遍历循环链表找到一个空位, 或者找到访问位为 0 的页面淘汰掉, 然后把需要的页面从外存中引入. 如果遇到访问位为 1 的页面, 把 访问位的值设置为 0;

改进型时钟 CLOCK 算法:

• 考虑了页面载入内存中是否被修改的问题, 增加了 "修改位". 当访问位同为 0 的时候, 优先淘汰掉没有被修改过的页面;
• 因为修改过的页面还需要写回到外存中. 此算法可以减少 I/O 次数, 但是会增加扫描次数;

# 页面分配策略

在请求分页存储管理系统中, 可以采取两种页面分配策略: 固定分配, 可变分配;

在进行页面置换的时候, 可以采取两种策略: 全局置换, 局部置换;

组合起来可以有如下 3 种合适的策略 ( 固定分配全局置换不合理, 所以不存在 ) :

# 页面调入策略

# 抖动现象 & 缺页率

Belady 异常: 由于 FIFO 算法的置换特征与进程访问内存的动态特征相矛盾, 会导致缺页率可能随着分配的物理块数量的增加而增加.

抖动现象: 刚被淘汰的页面, 过不久就又被程序访问, 并且调入后不久就又被调出, 如此反复;

缺页率 & 命中率:

# 请求分段存储管理系统

整体来讲, 和 "请求分页存储管理系统" 各方面类似.

# 内存管理方式之间的对比

# 文件管理

# 文件系统基础

# 文件的基本概念

文件的概念: 文件是具有名称的一组相关元素的集合;

文件的组成结构:

• 数据项: 是文件系统中最低级的数据组织形式, 分为如下两类:
  • 进本数据项: 用于描述一个对象的某种属性的一个值. 例如, 姓名, 年龄, 日期, etc;
  • 组合数据项: 由多个基本数据项组成;
• 记录: 一组相关的数据项的集合, 用以描述一个对象在某方面的一组属性;
• 文件: 一组相关信息的集合, 逻辑上可以分为:
  • 有结构文件: 由一组相似的记录组成;
  • 无结构文件: 一组字符流, 又称流式文件. 例如, 二进制流文件

文件的属性:

文件的分类:

按照用途分类:

按照保护级别分类:

按照信息流分类:

按照数据形式分类:

文件的操作:

# 文件的逻辑结构

文件按照逻辑结构来分类, 可以分为:

• 有结构的记录式文件;
• 无结构的流式文件;

记录式文件可以分为:

• 顺序文件:
• 索引文件:
• 索引顺序文件:

流式

# 目录结构

# 文件系统及实现

# I/0 管理