死锁处理策略-避免死锁

什么是安全序列？

• 安全序列就是系统按照这个顺序分发资源，那么每个进程都能够顺利完成
• 安全序列可能有多个
• 只要找到一个安全序列，那么系统就进入到了安全状态
• 如果没有任何一个安全序列，那么系统就是不安全的状态。
• 不安全状态可能会发生死锁，但是死锁发生一定就是系统处于不安全状态。

银行家算法

银行家算法思想

• 分配资源之前判断这次分配是不是会导致系统进入不安全状态。
• 为了避免死锁。

下面例题

• 主要看当前拥有的资源是否满足进程的资源要求，分配，执行并且返还，进程进入到安全序列，然后再次分配，
• 如果最后所有进程都能够进到安全序列，那么这个系统就是安全的。

银行家算法步骤

1. 检查申请是不是超过了之前声明的最大需求数。
2. 检查此时系统可用的资源是否满足这次的请求。
3. 试探分配。
4. 安全性检查算法看看这次分配是否导致系统进入不安全状态。

安全性检查算法步骤

1. 检查可用资源是不是满足某个进程的最大需求，如果可以加入安全系列。并且把进程的持有的资源回收。
2. 不断重复看看是否能把所有进程弄进安全序列。

死锁的处理策略–检测和接触

死锁的检测

为了对系统死锁检测

1. 使用某种数据结构保存资源的请求和分配信息
2. 提供一种算法，利用上述信息检测系统是否进入死锁的状态。

两种节点

• 进程节点：对应进程
• 资源节点：对应一类资源

两种边

• 进程结点->资源结点：表示进程想申请多少个资源
• 资源节点->进程节点：表示已经为进程分配多少个资源。

• 如果系统可用资源满足进程需求，那么进程能够继续执行，不会阻塞

• 如果进程结束了执行，并且归还资源，那么其他等待资源的进程的进程被激活。并且顺利执行。

• 如果最后能够消除所有的边的话，那么说明一定没有发生死锁。

检测死锁的算法

• 找不不阻塞而且正在申请资源的点，如果发现有足够的资源，那么就让进程完成获取资源执行。并且归还资源，并且找到下一个进程。
• 如果全部进程都可以获取资源执行完成，那么就是不会发生死锁，否则，那么就会发生死锁。

解除死锁的办法

1. 资源剥夺法，挂起死锁进程，抢占它的资源。分配给其它死锁进程。
2. 撤销进程法：撤销话，可能前面进程执行的代码就无效了。
3. 进程回退法：回退到避免死锁的位置。

对谁动手？

1. 进程优先级
2. 执行多长的时间。
3. 还有多久能够完成。
4. 进程已经使用多少资源。

总结

• 死锁检测需要两种数据结构，两个边
  • 进程节点，进程指向资源表示请求
  • 资源节点，资源指向进程表示分配
• 死锁检测算法
  • 依次消除不阻塞进程相连的边，知道没有边可以消除
  • 如果资源分配图无法完全简化，那么就会发生死锁。
• 解除的方法
  • 资源剥夺，就是直接抢占，并且让该进程进入到外存
  • 撤销进程，成本太大
  • 进程回退，也是成本太大。

内存的基础知识

什么是内存？有什么作用？

• 内存用于存放数据的硬件，程序执行前需要加载进内存。

怎么区分程序放到内存什么位置？

• 给内存的存储单元编地址。
• 每个地址对应一个存储单元
• 大小
  • 按字节编址，说明每个存储单元就是1个字节
  • 字长是16位，那么就是按字编程，每个存储单元是1个字也就是两个字节。

补充知识：几个常用单位

• G换算过来就是2^30，如果问地址长度，意思就是问你需要多个二进制才能表示完整个地址的所有位置，那么你就需要知道有多少个存储单元，按照存储单元的个数对应地址的长度。这里很明显就是4 * 2^30也就是232的地址长度，也就是需要32个这样的二进制数。

进程的运行原理-指令

• 指令的参数通常都是逻辑地址（相对地址），因为在编译之前是完全无法知道数据会存放到什么地方。
• cpu会通过指令执行对应的操作。
• 把程序放入内存的时候就想办法获取程序的起始地址就能获取到程序其它代码的相对地址。

从写程序到程序执行

• 首先就是程序员编写代码
• 编译：代码编译成模块，这些模块就是机器语言
• 链接：然后再把各个目标模块和库函数链接成大模块
• 装入：最后就是让装入程序把装入模块装入到内存。
• 目标模块的地址都是逻辑地址。

装入模块装入内存

• 如果直接按照逻辑地址，那么最后得到的数据肯定是错误的，因为逻辑地址必须要通过程序的初始地址开始计算出来。

装入的三种方式

绝对装入

• 意思就是在编译链接成模块的时候直接产生代码的绝对地址。适合用于单道程序设计。但是必须刚开始就知道程序会装入到内存的哪个位置。

静态重定位

• 编译和链接后的装入模块地址都是从0开始
• 装入程序装入模块的时候就会根据程序的初始地址根据相对地址来进行重定位。把逻辑地址转换成物理地址。也就是只在装入的时候进行一次物理地址的转换。

特点

• 必须分配其要求的所有内存空间
• 运行期间程序不能够继续移动。

动态重定位

• 动态运行时装入。实际上装入到内存的模块的地址还是逻辑地址，只不过有重定位寄存器来存放模块的起始地址。而且能够通过cpu计算出当前的所需要运行的物理地址。
• 允许程序在运行的时候移动。

链接的三种方式

静态链接

• 把目标模块和所需的库函数链接不再分开。

装入时动态链接

• 一边装入内存一边链接

运行时动态链接

• 需要模块的时候才会去链接。方便修改。

总结

• 主要介绍了指令的存储方式
• 逻辑地址如何转换为物理地址
• 程序装入的过程，写代码->编译->链接->装入内存
• 装入转换地址的三种方式
  • 绝对装入：直接在编译链接的时候使用绝对地址
  • 可重定位装入：链接之后通过装入程序完成地址的转换
  • 动态运行时装入：也就是通过重定位寄存器记录模块的初始地址，并且计算得出绝对地址。这种程序是可以在内存到处流动的。
• 还有三种链接方式
  • 静态链接：装入前就链接好了
  • 装入动态链接：一边装入内存一边链接
  • 运行时动态链接：需要使用的时候才会装入模块到内存和链接。

内存管理的概念

内存空间的分配与回收

操作系统需要管理内存的什么？

1. 操作系统负责管理内存空间的分配和回收

2. 操作系统需要提供某种技术从逻辑上对内存空间进行扩充。

3. 操纵系统需要实现地址转换，负责程序的逻辑地址和物理地址之间的转换。

4. 操作系统提供内存保护，各个进程在自己的存储空间运行。
   1. 方法1：设置上下限寄存器，不让进程访问其它进程和操作系统程序。
   2. 方法2：采用重定位寄存器（基地址寄存器，记录模块的基地址）和界地址寄存器（限长寄存器，记录最大的逻辑地址）进行越界检查。

• 操作系统怎么记录哪些区域被分配，哪些是空闲的？

• 进程运行完如何回收？

• 很多位置可以放进程，那么放到哪里？

总结

• 操作系统需要处理的问题
  • 地址转换
  • 内存空间拓展
  • 内存空间分配和回收
  • 存储保护

覆盖与交换

覆盖技术

• 核心思想：把程序分为多个段，常用段常驻内存，不常用的需要的时候调入内存

• 内存分为固定段，和若干个覆盖区。

• 主要是解决程序太大内存不足的问题。

下面的例子

• A可以使用一个固定区，由于B和C并不是一起被调用的，而且B和C不是同时调用，所以可以使用覆盖区。

• 对于B和C可以同时使用一个覆盖区

• DEF也可以使用同一个覆盖区

• 但是这种需要程序员自己声明覆盖结构，操作系统完成覆盖，对用户不透明，增加用户编程的负担。

交换技术

• 如果内存空间不足，把某些进程存入外存，把外存的具备运行条件的进程换入内存的交换思想。
• 其实这个就是中级调度，把挂起的进程调度到内存。这里的PCB是常驻在内存，作用是指向进程存入的外存位置，和记录现在的状态。

• 交换技术的相关问题

1. 应该放到外存什么位置保存被换出的进程

• 存放到连续空间分配的对换区，对换区的IO速度更快。

2. 什么时候应该交换

• 在内存非常紧张的时候，如果经常缺页的时候，那么就可以换出一些进程。

3. 应该换出哪些进程？

• 优先换出阻塞进程
• 换出优先级低的。

总结

• 覆盖技术，通过判断程序的调入情况分为固定和覆盖区，如果不是经常调用的那么就使用覆盖区，经常需要使用的那么就使用固定区
• 交换技术相关的比如中级调度，和挂起的两个状态相关。挂起只是把进程存储外存，并且留下PCB记录状态和存入的位置。

连续分配管理的方式

单一连续分配方式

• 系统区：存放到低地址
• 用户区：存放到高地址，但是用户程序独占整个用户区。

优点

• 实现简单，没有外部碎片，不一定需要内存保护

缺点

• 只适用单用户、单任务操作系统，有内部碎片。

固定分区分配

• 分区大小相等

缺乏灵活性，如果遇到太大程序无法执行。太小的程序会导致内存碎片太多

• 分区大小不同

灵活性更好，可以满足各个程序的需求。

如何管理分区

• 通过一个表，记录分区号，大小，起始地址，状态等

优点

• 实现简单，没有外部碎片

缺点

• 用户程序太大的时候可能会导致程序无法装入，或者需要覆盖技术。降低了性能
• 产生了内部碎片

动态分区分配

• 进程进入内存的时候才会根据进程大小建立分区。

• 系统要用什么样的数据结构记录内存使用情况？

两种数据结构

• 空闲分区表，记录分区号，分区大小和起始地址还有分区的状态。
• 空闲分区链表，头和尾连接上一个或者是下一个空闲分区，头会记录分区的各种大小和位置的信息。

• 当很多个空闲分区都能满足需求的时候应该选择哪个分区？

使用的是动态分区分配算法完成选择。

• 如果处理分区的分配和回收操作？

如何分配？空闲分区表的处理

• 第一种情况就是进程5比较小的4MB直接分配到分区1号，直接减去大小和重新计算起始地址。

• 第二种情况就是进程5分配到3号的分区，刚好使用完4MB那么直接删除分区3信息

如何回收？

• 第一种情况回收的分区和空闲分区相邻直接更新分区的大小和起始地址。相当于合并在一起。

• 情况三，这种就是回收进程4刚好在空闲分区1和空闲分区2之间，那么回收之后可以合并三个分区到分区1。更新大小和起始地址。

• 情况四，如果刚好没有相邻任何分区，那么就直接创建一个空闲分区的项就可以了。

碎片讨论

• 内存碎片：分配给进程的空间，有些部分没用上
• 外部碎片：内存的空闲空间太小无法使用。

外部碎片的解决方案

• 紧凑，直接把那些进程移动到一起。

总结

• 一共讨论3种分配方式
  • 单一分配
  • 固定分区分配
  • 动态分区分配
    • 两种数据结构，空闲分区表和空闲分区链表
    • 以及四种回收的表修改方法
• 还有就是关于碎片的回收方案可以使用紧凑，然后重新计算起始地址。

动态分区分配算法

首次适应算法

• 算法思想：每次从低地址开始找，找到第一个适应的分区

• 实现：空闲分区按照地址递增次序排列。每次分配内存顺序查找空闲分区链表。

最佳适应算法

• 算法思想：优先使用更小的空间
• 如何实现：空闲分区按照容量递增次序排列。
• 问题就是会留下越来越多的小碎片，产生很多外部碎片

最坏适应算法

• 算法思想：优先使用最大的空闲区
• 如何实现：按照容量从大到小排序
• 问题是大分区用完，如果来了大程序就无法装入了。

邻近适应算法

• 算法思想：首次适应算法在低地址会出现很多外部碎片，所以那些小碎片的查找可能会消耗性能，所以每次查找都是从上一次查找结束的位置下一个继续查找
• 实现：空闲分区按照地址递增的顺序排序，每次分配内存都是从上一次查找完的位置继续查找。

对比

• 首次适应算法，可以保留高地址的大空间（最佳适应算法的优点）
• 邻近适应算法，可以让高地址和低地址都有相同的概率被使用，但是可能无法保留大空间。
• 首次适应算法的效果比较好

总结

• 总结了四种使用空闲分区的算法。
  • 首次适应（留下大空间，而且性能折中比较好的。）
  • 最佳适应（能够留下大空间）
  • 最坏适应（选大空间）
  • 邻近适应（公平，加快查找速度）

基本分页存储管理的基本概念

连续分配的缺点

1. 缺乏灵活性，碎片太多
2. 动态分配也是会出现很多碎片，虽然可以使用紧凑技术，但是消耗性能。

所以可以考虑非连续分配方式。减少这些内存碎片，把进程分好多个块去存放。

• 连续分配：为用户进程分配一定是一个连续的空间分配
• 非连续分配：为用户进程分配可以是一些分散的内存空间。

固定分配到非连续分配版本

• 实际上就是划分更小的分区，并且能够把进程拆分成多个部分存储到不连续的各个小分区里面。

分页存储管理的基本概念

• 内存空间分成很多个大小相同的分区
• 每个分区就是页框，每个页框都有自己的编号。
• 进程也划分成很多个页存储到内存的各个页中。他们是一一对应的。

进程地址空间分页之后，操作系统如何实现逻辑地址到物理地址的转换？

• 连续存放的转换思想：记录起始地址+目标的偏移量。

分页如何进行地址转换？

• 实际上就是依靠单个页的特点是连续的，所以只需要知道页的起始地址，和需要访问的偏移量就能够找到对应的数据
• 那么问题来了

1. 如何找到逻辑地址的页号
2. 页号对应的页的内存起始地址怎么找
3. 如何知道逻辑地址在页的偏移量。
4. 物理地址=页面的起始地址+页内的偏移量。

如何计算页号和偏移量

• 页号=逻辑地址/页的大小
• 页内偏移量=逻辑地址%页大小
• 页的起始位置通过操作系统的某个数据结构来记录。
• 页面大小通常是2的幂次。

• 前20位是记录页号的X，后面12位就是记录偏移地址。也就是每次计算出页号直接拼上后面的偏移地址就能够找到对应的数据位置。
• 也就是每个页占用2^kB的话，那么就占用了这个地址的后面k位，其它都是用来表示页号的。

逻辑地址结构

• 有对应的页号占用M位（表示可以展示多少个2^m页）
• 页内偏移量占用K位（主要看每个页占用多个2^kB的大小。）
• 现在解决了页号的求解和页内偏移量的求解和逻辑地址的结构问题

页表

怎么知道进程每个页面的存放位置？

• 操作系统为每个进程创建一张页表。

1. 一个进程有一个页表
2. 每页对应一个页表项
3. 页表项包括页号和块号（块号 * 内存大小可以获取到块的起始地址）
4. 页表记录进程页面和实际存放的位置。
5. 页号是隐含的

为什么页表项是相同的，而且页号是隐含的？

对于下面的问题分析

• 物理内存总共是4G也就是2^{32个存储单位，每个页是4K就是2}12个存储单位。
• 那么要求多少个页就是这两个变量相除，得到2^{20个页也就是需要表示2}20个内存块，这个时候每个页表项就需要表示0-2^{20-1所以需要3个字节，3个字节表示的2}24的范围表示，所以可以容纳这么多的块号。

总结

• 主要介绍了页的基本概念
• 解决了页号和页内偏移量问题通过逻辑地址存储
• 通过页表解决了定位进程页的位置，并且隐含了页号，通过计算物理内存的容量和页的大小得到需要表示多少块号，从而计算出页表项的大小。这也说明为什么页表项的大小是相同的。接着就是通过其实位置和需要访问的页号来计算出页在页表的位置，再找到对应块号的页在内存的位置。

基本地址变换机构

• 系统会设置一个页表寄存器，存放页表在内存的起始位置和页表的长度。这些都是存储在PCB上面的。每次调度才会更新页表寄存器的值。

整个访问过程

1. 首先就是计算出逻辑地址的页号和页内偏移量
2. 然后就是判断页号是否越界
3. 然后就是计算出页号所在页表项的位置
4. 最后就是得到块号计算出物理地址和访问目标单元。

页表项的大小限制

• 如果页表项是3B的时候会发现一个页4096%3是刚好剩下1B，所以访问第1365个页的时候刚好就是X+3*1365+1这里还需要+1导致页表项的存储不是连续的，那么计算就会很麻烦，所以对于页表项可以拓展到4个字节存储。那么页表项无论有多少个都可以连续用完一个页。

总结

• 这里介绍了页表寄存器的作用和切换进程通过PCB更新页表寄存器，PCB存储着自己页表的起始位置和对应的页表项长度
• 地址变换的过程只需要逻辑地址+页的长度就可以直接计算和定位
  • 根据逻辑地址计算页号和偏移量
  • 判断页号的合法性
  • 根据页号和页表起始地址计算出页表项地址，然后得到块号计算出物理地址
  • 根据物理地址访问内存。

具有块表的地址变换机构

局部性原理

• 时间局部性：指令执行之后不久再次执行多次
• 空间局部性：某个存储空间访问一次不久之后再次被访问。

由于多次访问同一个逻辑地址，所以会多次计算，有没有办法通过局部性原理减少计算次数？

• 通过快表

什么是快表

• 快表就是联想寄存器（TLB），访问速度比内存快的高速缓存存储器。可以存储若干个页表项。
• 内存中的页表也可以被称为慢表。
• 其实就是多了一个添加缓存的过程，查询一次0号页之后把0号页的页号和块号存储到快表，那么下次还是查找0号页的时候就不需要去到内存访问页表了。
• 对于直接访问快表只需要一次访存直接访问物理的内存数据位置，但是如果要访问也页表那么就要访问页表一次，还要去访问物理的内存数据一次。

下面的案例

• 实际上就是访问快表+一次访存，乘上命中率然后加上访问一次快表和两次内存乘以没有命中的概率得到的就是平均耗时
• 如果慢表和快表同时查询，也就是快表查询的同时慢表也可以查询。

总结

• 快表的好处就是减少了一次访存。

两级页表

单级页表项的问题

下面的分析

• 实际上就是出现在每个页的大小是4KB也就是占用12个位置，现在有20个位置是用来分配页号的，也就是每个进程可以存储2^{20个页，那么对应的页表就需要是2}20 * 4B一个也页表就要占用2^22B和(222)/(2^{12)个页。足足是2}10个页框才能装下一个页表，占用的内存太大。
• 通常进程只需要访问几个页，所以没有必要让整个进程的页表常驻内存。

如何解决单级页表问题

问题1：页表连续存放，所以页表很大的时候就需要占用很多个连续页框

问题2：进程访问的页其实不多，没必要让页表所有项常驻内存

思考：如何解决进程连续存储问题？

• 通过把进程分页
• 所以模仿思路来吧页表进行分组让页表能够离散地分配。

两级页表的原理、地址结构

• 相当于就是把原本的页表拆分成各个组，比如现在有2^{20个页表项，那么由于每个页只能存放2}12/2^2也就是210个页表项在页中。所以每2^10作为一组。
• 然后再创建一个目录页表指向这些不同组的页表项。每个组有2^{10个页表项。对于目录页自己能够存放2}10个项。页目录记录的是页号+

访问的过程

• 首先就是根据一级页号在目录页表找到对应的普通页表所在的内存，读出这个页表
• 然后就是根据二级页号在普通页表中找到目标数据所在的内存块，计算出物理地址
• 访问内存。

• 可以在目录页上标记这个组页表项的页是不是存在于内存。并且在有需要的时候才从磁盘调入进来。

• 几个细节需要注意
  • 页表的大小不能超过一个页面。所以页号最多只能是10个位。
  • 所以下面的例题是需要分出3级页表。
  • 而且对于二级页表来说需要访问内存3次。第一次是目录页表访问，第二次是二级页表访问，最后一次才是访问数据的内存位置。

总结

• 二级页表解决了单级页表的占用太大空间问题。一个也页表可能会占有2^{20个页表项，相当于就是2}10个页框才能装下一个页表。缓解这个问题可以使用一个页目录来进行把页表每1024个页表项作为一组，分为多组。每个组的内存块都是一个页，所以可以作为一个目录项存储到目录页表中，而且能够通过虚拟技术把不需要的页先存到外存并且在目录项进行一个标记。
• 以前那种就是通过一个页表来访问数据页的位置。页表是连续存储的，所以导致页表项很多的时候占用大量的页。但是解决连续存储问题，就可以通过分组来解决，那页表分为多个组，那么这些组可以通过目录来定位，那么就可以进行不连续的存储。并且可以通过两级的不同页号和目录页起始地址来定位数据页的位置。

基本分段存储管理方式

分段

• 进程按照自身逻辑划分若干个段，每个段都有段名。
• 内存分配规则：以段为单位分配。每个段在内存都是连续。而且各个段可以不相邻。
• 使用段号来区分段
• 和分页不同的地方就是离散分配所分配的地址空间基本单位不同。
• 它是通过逻辑功能模块来划分的。在实际分配的时候会把段名转换为段号

• 段号决定每个进程最多可以分多少个段。
• 段内地址位数决定每个段的最大长度。

下面的例子

• 段号占了16个位，那么说明就是能够表示2^{16个段，然后段内地址是2}16说明每个段的空间是64KB。

• 对于D和X来说就是段名，他们会翻译成对应的段号，对于A和B来说会翻译成段内地址。

段表

程序分为各个段，如何找到段的位置？

• 可以使用段表

对于下面的例子

• 可以使用段表来存储各个段的初始地址和各个段的长度。
• 最大的段长2^16所以是64KB只需要使用16位就能够表示整个段长了。由于逻辑地址结构的限制。
• 由于基地址需要表示所有的物理内存的存储单位，可以看到物理内存是4GB而且按照字节编址那么就是有2^32个存储单位需要表示。实际上就是16（这个是表示段长所需要的bit）+32（这是表示内存所有单位所需要的bit）
• 所以可以忽略段号，只需要知道段号就可以根据初始地址查询到段的位置。

地址转换

• 逻辑地址需要通过计算来转换成物理地址。通常就是通过段号找到段在段表的位置，然后切换成基地址+偏移地址就是物理地址。

段的查询过程

需要一个段表寄存器，存储段表的合法长度和段表的起始地址，这些都是在PCB上面存储的。

这里的段表长度规范就是段号的最大个数是2^16。

1. 首先就是判断逻辑地址的段号是不是符合规范
2. 然后就是计算出段在段表的位置，获取到基地址
3. 然后就是基地址和偏移地址计算出物理地址。

段和页的对比

• 段的长度不同，但是页的长度是相同的。
• 段是信息的逻辑单位，页是信息物理单位
• 分段可见，但是分页不可见。
• 之所以需要记录段的长度是为了计算段的位置。一个程序分为多个段，段不是规定长度所以需要计算。
• 页是一维的，因为页表一下子就可以根据一个逻辑地址一下子定位出页的位置，但是段还需要段名和段内偏移地址并且需要转化段名+偏移地址为逻辑地址。再转移为物理地址。

• 分段比分页更容易实现信息的共享和保护。只需要修改段的指向地址即可，但是对于页来说就不行因为一些可以共享的代码可能在两个页所以标记起来非常难。段只需要改变地址和加上一个是否能够访问的标识就可以了。

总结

• 主要讲解了分段的基本概念和地址换算
• 段表和页表的不同，在于段的长度不同
• 段能够更好的保护代码和共享代码。

段页式管理方式

分段分页的优缺点

• 分页内存利用率高，但是不是逻辑模块划分，很难实现信息的保护和共享
• 分段能够利用逻辑模块实现信息共享，但是分配大空间不方便，而且会产生外部碎片。

分段+分页管理

• 逻辑模块分段，分段之后再进行分页。

段页式管理的逻辑地址结构

• 段号可以分多少个段
• 页号决定每个段有多少个页
• 页内偏移量决定页的大小。
• 分段对用户可见，所以需要段号和段内地址，分页不可见，所以页的信息在段内地址进行划分。

段表和页表

• 段表存放的是段号+页表长度+页表存放的块号（页表的起始地址）。
• 对于页表来说还是页号+块号。
• 每个段对应一个页表。一个进程对应一个段表，多个段和多个页表

访存的过程

1. 判断段号的合法性
2. 根据段号找到对应的页表的位置
3. 判断页号的合法性，因为一个段可能会有多个页，所以需要验证页号的合法性
4. 然后根据页号找到对应的页表项计算出物理内存地址访存数据
5. 所以总共访存了3次，段表一次，页表一次，还有数据一次。

总结

• 介绍了段页管理方式，划分逻辑模块划分多个段，然后段再划分多个页。、
• 最后根据段表的改良，存储段号+页表长度（判断页号合法性）+页表的块号
• 页表还是老样子
• 解决了纯页表不能划分逻辑模块导致无法共享信息的问题，解决纯段的无法解决内存利用率的问题。

虚拟内存的基本概念

传统存储管理的缺点

一次性

• 作业很大的时候可能会导致不能执行，因为传统内存管理要求程序一次性导入
• 如果作业太大，导致其他程序无法装入影响并发性。

驻留性

• 作业被装入之后一直存在内存，直到结束，但是实际上使用到的数据只有一小部分导致内存资源的浪费。

虚拟内存的定义和特征

• 先存入程序很快使用到的部分，其它部分先存放到外存
• 等需要使用的时候操作系统会将所需的信息调入到内存。
• 内存不够操作系统会调出那些不用的数据到外存
• 用户看来似乎有一个比内存更大的内存就是虚拟内存。

易混知识点

虚拟内存的最大容量是计算机的地址结构（cpu寻址范围）决定的

虚拟内存的实际容量=min（内存+外存，cpu寻址范围）他们之间的最小值。

虚拟内存的特征

• 多次性：允许程序被分成多次调入内存
• 对换性：作业不需要一直常驻内存，可以在作业运行的时候换入换出。
• 虚拟性：逻辑上拓展了内存的容量。

如何实现虚拟内存技术

• 建立在离散分配的内存管理方式的基础之上。

请求分页和传统分页的区别

• 程序访问信息不在可以请求操作系统来调入（操作系统提供请求调页的功能）
• 内存不足的时候可以换出一些用不到的信息。（操作系统提供页面置换的功能）

请求分页管理方式

页表机制

• 操作系统需要知道哪些页面被调入内存，哪些没有

• 内存不够的时候操作系统需要通过某些指标来换出页面

• 所以页表增加了字段

  • 状态：是否在内存
  • 访问字段：被访问多少次，置换算法的参考指标
  • 修改位：是否被修改过
  • 外存地址：存在外存的什么地址

缺页中断机构

• 程序请求的页面不在的时候就需要产生一个缺页中断，操作系统完成这个缺页中断处理程序。
• 然后调入页面
  • 有空闲页直接分配
  • 没有空闲页就执行置换算法，换出一个使用频率低的页面。

• 缺页中断是目标页面未调入内存产生的，因此属于内中断（故障，系统可以修复）。
• 一条指令执行的时候可能会产生多次缺页中断

地址变换机构

请求分页存储管理与基本分页存储管理

增加步骤

• 请求调度（查到页表项并且判断是否在内存）

• 页面置换

• 修改页表项。

• 对于快表如果页面换出，那么就要立刻删除这个页面。

查询步骤

1. 查快表
2. 查慢表
3. 可能调页（调入后页面加入到快表）
4. 查快表
5. 访问存储单元