万兴脑图3.内存管理-2(1)
导图社区 3.内存管理-2(1)
- 43
- 2
- 0
- 举报
-
3.内存管理-2(1)
段页式管理是分段管理和分页管理的结合，集合了页式存储管理方式 能有效提高内存利用率 和 段式存储管理方 式能反映程序的逻辑结构并有利于段的共享 两者的长处
编辑于2022-05-23 21:07:12- OS
- 内存管理
- 相似推荐
- 大纲
3.内存管理
关于内存的基础知识
内存的概念
内存是用于存放数据的硬件，程序执行前需要先放到内存中，只有在内存中的程序才可以被CPU处理
内存地址和存储单元
存储单元：如果“按字节编址”，则每个存储单元为1个字节；如果字长为16位的计算机“按字编址”，则每个存储单元大小为一个字，即16个bit
内存地址从0开始，每个地址对应一个存储单元
进程运行的基本原理
指令
告诉CPU应该去哪个地址存/取数据，这个数据应该做怎样的处理
相对地址（逻辑地址）和绝对地址（物理地址）：编译时产生的指令里的地址是“相对地址“，实际放入内存前会先把“相对地址”转化为“绝对地址”再放入内存中
从写程序到程序运行的过程
程序员
编辑
编写程序
计算机
编译
编译程序对用户源代码进行编译，生成若干目标模块
链接
链接程序把编译生成的目标模块和所需的库函数链接在一起，生成完整的装入模块
链接的三种方式
静态链接
在程序运行之前，也就是在装入程序工作之前之前，将各个目标模块和它们所需的库函数链接成一个完整的装入模块，由装入程序装入内存
装入时动态链接
装入程序和链接程序同时工作，即在装入程序将装入模块装入内存的同时，链接程序也在不断的产生装入模块
运行时动态链接
只有在程序运行时需要某个目标模块，链接程序才将其进行链接，该链接方法便于修改和更新、实现对目标模块的共享
装入
装入程序把装入模块装入内存，这个过程如果是绝对装入和静态重定位装入方式的话就会完成逻辑地址到物理地址的转换，如果是动态重定位方式则不会完成地址转换
装入的三种方式
绝对装入
编译时，产生的目标模块中的地址就已经是实际地址，所以绝对装入程序按照链接后生成的装入模块中的地址将程序装入内存
特点：绝对装入方式只适用于单道程序环境，而且，装入模块中的实际地址可在编译时给出，也可由程序员直接赋予
静态重定位
又称可重定位装入，是指在多道程序环境下，目标模块的起始地址都是从0开始的，目标模块中的程序里的其他地址都是相对于起始地址的，此时应该采用可重定位装入方式，根据内存的当前情况将装入模块装入内存的适当位置，装入过程中将装入模块中的程序里的指令和数据进行修改，该过程称为重定位。
之所以称为静态重定位。是因为地址变换通常是在装入时一次完成的
特点：一个作业装入内存时，必须要有满足其要求的足够多的内存空间，若没有就不能装入该作业，除此之外，作业一旦进入内存，整个运行期间就不能在内存中移动，也不能再申请更多的内存空间
动态重定位
又称动态运行时装入，在装入程序吧装入模块装入内存的过程中不会将程序中的地址进行地址转换，即内存中装入的程序中的所有地址依然是逻辑地址，等到程序执行时才进行地址转换，这种装入方式需要一个重定位寄存器的支持
运行的时候才会将内存地址（物理地址，我在哪）在程序的代码指令中体现
特点：采用动态重定位装入方式，允许程序在内存中发生移动
内存管理概念
内存空间的扩充
实现虚拟性
覆盖于交换技术(*)
覆盖技术(*)
解决“程序大小超过物理内存大小”的问题
思想：将程序分为多个段（或者叫多个模块），常用的模块常驻内存，不常用的模块在需要时调入内存
实现：内存被分为一个“固定区”和 若干个“覆盖区”；需要常驻内存的段放在“固定区”，调入后就不再调出；不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存
特点：必须由程序员声明覆盖结构，然后操作系统负责完成自动覆盖
缺点：对用户不透明，增加了用户编程的负担；只用于早期的操作系统，现已成为历史
交换技术(*)
思想：内存空间紧张时，系统将内存中的一些进程暂时换出内存，把外存中的一些已经具备运行条件的进程调入内存
中级调度（内存调度）就是决定哪个处于挂起态的进程重新调入内存，哪个进程被暂时换出内存等待；被换出等待的进程的状态称为挂起状态，挂起态进一步可以细分为就绪挂起、阻塞挂起两种状态
磁盘分为文件区和兑换区
覆盖技术与交换技术的区别
覆盖发生在同一个程序或进程中的
交换发生在不同进程（或作业）之间
虚拟存储技术（下一节详细展开）
内存空间的分配与回收
连续分配管理方式
概念
指为一个用户程序分配一个连续的内存空间，用户程序需要多大的内存空间，连续分配方式就为用户分配一块多大的连续的内存空间
三种分配方式
单一连续分配
定义：内存被分为系统区和用户区，顾名思义，系统区是供操作系统使用的，用户区则是为用户提供的内存空间
特点：内存中一个时刻永远只有一道程序，因此，肯定不会因为访问越界而干扰其他程序，所以无需内存保护
优点：简单、无外部碎片，可以采用覆盖技术，不需要额外的技术支持
缺点：只能用于单用户、单任务的操作系统中，有内部碎片，存储器的利用率极低
固定分区分配
定义：同样地，内存空间被分为系统区和用户区两部分，区别在于，固定分区分配方式将用户内存空间划分为若干固定大小的区域，每个分区只装入一道作业
划分分区的两种方法
分区大小相等
划分为大小相等的分区
适用于利用一台计算机去控制多个相同对象的场合，缺乏灵活性
分区大小不等
划分为多个较小的分区、适量的中等分区、少量的大分区
增加了灵活性，可以满足程序不同大小的需求
分区说明表
由来
为了便于内存分配，通常将分区按大小排队，并为之建立一张分区说明表
包含
每个分区的初始地址、大小、状态（是否已分配）
用途
当有用户程序想要装入时，便通过检索该分区说明表寻找是否有合适的分区，如果找到了，就把分区分配给程序并将状态设置为“已分配”；如果检索的结果是未找到合适分区时，则分配失败，系统拒绝为该用户程序分配内存
存在的两个问题（缺陷）
程序可能太大而放不进任何一个分区
当程序小于固定分区大小时，也会占用一个完整的内存分区空间，这样分区内部就会存在空间浪费，也就是产生了内部碎片，所以主存利用率低
优缺点
优点
可用于多道程序设计的最简单的存储分配，无外部碎片
缺点
不能实现多个进程共享一个分区，所以空间利用率很低
现状
很少用于现在的通用的操作系统中，但在某些用于控制多个相同对象的控制系统中仍然发挥着一定的作用
动态分区分配
定义：和其他两种分配方式一样，内存空间被分为系统区和用户区，不同之处在于，该分配方式是一种动态划分内存的分区方式，该动态分区方式不像前两种分区方式会预先划分用户区的内存空间，而是在进程装入内存时根据进程的大小动态的建立分区，并使分区的大小正好合适进程的需要，因此，分区的大小和数目是可变的
用什么数据结构进行管理
空闲分区表
每个空闲分区对应一个表项，表项中包含分区号、分区大小、分区起始地址等信息
空闲分区链
每个分区的起始部分和末尾部分分别设置前向指针和后向指针，起始部分还可记录分区大小等信息
当很多个空闲分区都能满足需求时如何选择分区
概念
当一个新作业要装入内存时，需要按照一定的动态分区分配算法，从空闲分区表（或空闲分区链）中选出一个合适的分区分配给该作业；分配算法对系统的性能有很大的影响
四种分配算法
首次适应（First Fit）算法
最简单、最好、最快
空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区
缺点：会使得内存的低地址部分出现很多小的内存分区，而每次分配查找时都要经过这些小分区，因此增加了系统查找的开销
最佳适应（Best Fit）算法
空闲分区按容量递增的次序形成分区链，分配内存时按顺序查找，找到第一个能满足要求的空闲分区
缺点：性能通常很差，虽然每次的分配都是最接近所需空间大小的，但会产生很小的难以利用的外部碎片
最坏适应（Worst Fit）算法
又称最大（Largest Fit）适应算法，空闲分区以容量递减的次序链接，找到第一个能满足要求的空闲分区，即找到最大的分区
缺点：与最佳适应算法相反，每次分配都会选择最大的可用块，这看起来不容易产生碎片，但随着内存分配的进行，很快就会导致没有可用的大内存块，因此性能也非常差
邻近适应（Next Fit）算法
又称循环首次适应算法，由首次适应算法演变而来，不同的地方是，查找合适的空闲分区时从上次查找结束的位置开始这次的查找
缺点：因为，在一遍扫描中，内存前面部分使用后再释放时，常常导致内存的末尾分配空间分裂成小碎片，所以通常比首次适应算法的结果要差
特点
动态分区分配没有内部碎片，但有外部碎片
内存碎片 和 外存碎片 的区别
外部碎片
指内存中的某些没有被分配的但是因为太小而无法被利用的空闲分区
内部碎片
分配给某进程中没有被用上的部分，简言之，就是分配多了造成浪费的那部分
引入紧凑技术
由于进程需要的是一整块连续的内存空间，而这些外部碎片很小，并不能满足进程的需求，故引入紧凑技术来解决外部碎片的问题，紧凑技术指的就是操作系统不时地对进程进行移动和整理
如何进行分区的分配与回收
回收内存分区时，遇到的四种情况
回收区的后面有一个相邻的空闲分区
合并，新建一个表项
回收区的前面有一个相邻的空闲分区
合并，新建一个表项
回收区的前、后各有一个空闲分区
三个合并，新建一个表项
回收区的前后都没有相邻的空闲分区
不合并，直接为其新建一个表项
连续分配管理方式的缺点：单一连续分配方式就不用多说，它只适用于单道程序处理，固然不合适；固定分区分配又缺乏灵活性，会产生大量的内部碎片，造成内存的利用率低；动态分区分配虽然比固定分区灵活些，但会产生很多外部碎片，虽然可以用“紧凑技术”处理，但是“紧凑技术”的时间成本很高
非连续分配管理方式
分页存储管理方式
内存分区固定
需要把进程的所有页面装入内存才能运行
基本分页存储管理
基本思想
把内存分为一个个相等的小分区，按照分区大小拆分进程为一个个小部分，这个小部分就是主存和进程的基本单位，进程以块为单位逐个申请主存中的块空间
如果把分区大小设置得更小，内部碎片会更小，内存利用率会更高
对内存利用率的影响
分页管理不会产生外部碎片，只会产生一块很小的内部碎片（页内碎片），进程按块申请主存可用空间
基本概念
空间划分
内存的划分
页框（页帧）
页框号（页帧号）
进程的划分
页（页面）
页面大小的要求
页面大小应该是2的整数幂以便地址转换。同时页面大小也应该适中，页面太小会使进程的页面数过多，造成页表过长，占用大量内存，而且也会增加硬件地址转换的开销，从而降低页面换入/换出的效率；页面过大又会使页内碎片增多，降低内存的利用率。总之，页面的大小应该适中，要在空间效率和时间效率之间权衡
页面的存放
各个页面不必连续存放，也不必按先后顺序存放，可以放到不相邻的各个页框中
页号
外存的划分
块
逻辑地址结构
作用
存储页号和页内偏移量信息，即我是进程的哪个部分；依据逻辑地址从页表中找到相应进程中我需要的数据所在的页面的物理地址，然后再依据物理地址和页内偏移量找到想要的数据
组成
页号P
高地址部分，长度为20位
页内偏移量W
低地址部分，长度为12位
逻辑结构决定了虚拟内存有多大的寻址空间
页表
引入页表的原因
为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表；页表一般放在内存中，且各表项是按顺序、连续的存放在内存中；
组成
由页表项组成
关于页表项大小的探讨：理论上只需要3B就可以表示内存块号的范围，但是为了方便页表的查询，常常会让一个页表项占更多的字节，使得每个页面能放下整数个页表项
页表项的组成
页号
物理块号
作用
记录页面在内存中每个页面对应的物理块号；根据页面号在表中寻找其对应的物理块号，实现从页号到物理块号的地址映射；
基本地址变换机构
作用
借助页表将逻辑地址转换为内存中的物理地址
组成
页表寄存器PTR
存放页表在内存的 起始地址F 和 页表长度M；
进程未执行时，页表的初始地址和长度存放在进程控制块中，当进程执行时才将页表起始地址和长度存入页表寄存器
其他部分
越界中断判断结构
其他
工作过程
设页面大小为L 逻辑地址为A 物理地址为E
1.计算页号和页内偏移量：根据逻辑地址计算 页号P（P=A/L）和 页面偏移量W（W=A%L）
2.判断是否越界：比较页号P和页表长度M，若P>=M，则产生越界中断，否则继续执行
3.计算物理块号：页表中页号P对应的页表项地址 = 页表始址F + 页号P✖️页表项长度，根据得出的页表项地址取出该页表项的内容b，即对应的物理块号
页表项长度vs页表长度
页表项长度：页地址占多大的存储空间
页表长度：页表含有多少表项
4.计算物理地址：E = b✖️L + W
存在的两个问题及如何改进
1
问题
每次访存操作都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则访存速度会降低
改进（引入了）
具有快表的地址变换机构
局部性原理
内容
时间局部性
因为程序中存在大量循环，所以如果执行了程序中的某条指令，那么不久后这条指令可能会再次被执行；同理，如果某个数据被访问过，不久之后该数据可能会再次被访问
空间局部性
因为很多数据在内存中是连续存放的，所以一旦程序访问了某个存储单元，在不久之后，附近的存储单元也可能被访问
应用于快表
每此访问一个逻辑地址都要查询内存中的页表，根据局部性原理，可能每次访问的数据或程序存在于同一个页面，而在页面中的不同偏移位置，所以对应的都是同一个页表项
快表（TLB）
定义
又称联想寄存器（TLB），是一种高速缓冲存储器，突出的特点是访问速度比内存快很多的
存放内容
当前访问的若干页表项
作用
加速地址变换过程
与内存中的页表的区别
访问速度比内存快很多，所以对应地，内存中的页表被称为慢表
引入快表后的地址变换过程
1.CPU给出逻辑地址之后，由硬件进行计算得出页号，并将页号送入快表中进行查找
2.若在快表中找到匹配的页号，则直接从中取出该页号对应的内存块号，将此内存块号与页内偏移量拼接形成物理地址。因此若快表命中，则访问某个逻辑地址仅需一次访存（访问高速缓存寄存器不算一次访存）
3.若在快表中未找到匹配的页号，则需要访问主存中的页表，因此若快表未命中，则访问某个逻辑地址需要两次访存，找到对应的页表项并得到内存块号后，应同时将该页表项存入快表，以便后面可能的再次访问。若快表已满，则必须按照一定的算法对旧的页表项进行替换
两种查找方式
先查快表再查慢表：先将页号送到快表进行查找，查不到再到主存中的慢表中查找
快表慢表一起查：得到的页号送到快表和慢表，若快表中提前查找到了则终止慢表的查找
效果
一般的快表的命中率可达90%以上，这样分页带来的速度损失就可以降至使用慢表方式带来的速度损失时的10%以下
快表的有效性基于著名的局部性原理
2
问题
每个进程都会引入页表，用于存储映射机制，页表不能太大，否则内存利用率会降低
改进（引入了）
两级页表
为何引入两级页表（单级页表存在的问题以及如何解决）
存在的问题
问题1：因为页表必须连续存放，所以当页表很大时，会需要占用很多连续的页框
问题2：因为进程在一段时间内可能只需要访问某几个特定的页面，也就是说，只需要一部分页表在内存中就可以让进程运行，所以没必要让整个页表常驻内存
如何解决
可用“进程分页解决进程必须连续存放在内存中的问题”的思路来解决页表必须连续存放的问题，将长长的页表分为一个个分组，使每个分组刚好可以放入一个内存块(页框)中，另外还要为页表的各个分组再建立一张页表，称为页目录表，或称外层页表，或称顶层页表
两级页表的原理、逻辑地址结构
逻辑地址结构
一级页号
与每个页目录表 一 一对应
二级页号
与每个二级页表 一 一对应
页内偏移量
页目录表和二级页表的性质
二级页表的性质
每个表的表项个数固定且相等
页目录表的性质
页目录表的个数可能不止一个
每个页目录表中的每个表项对应一个二级页表
每个页目录表的表项的个数对应二级页表的个数
引入两级页表后的地址转换过程
两级页表问题需要注意的几个细节
多级页表中，各级页表的大小不能超过一个页面，若两级页表不够，可以分更多级
多级页表的访存次数（假设没有页表机构）----- N级页表结构访问一个逻辑地址需要N+1次访存
主要作用
建立多级页表的目的在于建立索引，以便不用浪费主存空间去存储无用的页表项，也不用盲目地顺序式查找页表项
段页式存储管理
内存分区固定
基本思想
段页式管理是分段管理和分页管理的结合，集合了页式存储管理方式能有效提高内存利用率和段式存储管理方式能反映程序的逻辑结构并有利于段的共享两者的长处
基本概念
空间划分
进程地址的划分
进程的地址空间首先依据逻辑关系被分为若干段，然后将每段又分为若干大小固定的页面
内存空间的划分
同分页存储管理方式一样，把内存空间分为大小相等的内存块（页框）
逻辑地址结构
地址空间是二维的
段号S
页号P
页内偏移量W
段表、页表
段表
定义
系统为每个进程建立一张段表，一个进程只有一张段表
组成
段表表项
段号
每个段表表项的长度是相等的，所以段号是隐含的
页表长度
页表始址（页表存放的内存块号）
页表
定义
每个分段都会有一张页表，一个进程可能有很多个
组成
页表表项
页号
内存块号
段表寄存器
和页表寄存器作用几乎一样
存储内容
段表始址
段表长度
作用
在段表中寻址
判断是否越界
地址转换机构
需要三次访存
可引入快表来减少访存造成的时间损耗
第一次：根据段号查段表，得页表始址
第二次：根据页表始址和页号查页表，得到内存块号
第三次：根据内存块号和页内偏移量访存，得到想要访问的数据
不需要把进程的所有页面装入内存才能运行
请求分页存储管理（在下一节的虚拟内存管理中展开）
分段存储管理方式
内存分区不固定
基本分段存储管理
基本思想
根据程序自身的逻辑关系把程序分为一个个段，再给各段建立一个段表以便于存储管理
基本概念
空间划分
分段
段式管理方式按照程序中自身的逻辑关系划分为若干段，每段从0开始编址；分配空间时，段内要求连续，段间不要求连续
例如，用户进程由主程序、两个字程序、栈和一段数据组成，于是可以把这个用户进程划分为5段，每段从0开始编址，并给每段分配一段连续的地址空间，但段与段之间可以不连续
逻辑地址结构
段号S：其位数决定了每个进程最多可以分成多少段
段内偏移量W：其位数决定了每个段的最大长度
段表
定义
每个进程都有一张逻辑地址和内存地址映射的段表
组成
由许多段表项组成，每个段表项对应进程的一段，且各个段表项的长度都相等
段表项的组成
段号
由于段表项的长度是相等的，因此段号可以是隐含的，不占存储空间
段长
本段在主存的始址
地址变换机构
段的共享和保护
段的共享
通过两个作业的段表中相应表项中指向被共享的段的同一个物理副本实现，当一个作业正从共享段中读取数据时，必须防止另一个作业修改此共享段中的数据
不能修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码和不能修改的数据可以共享，而可以修改的代码和数据不可以共享
段的保护
存取控制保护
地址越界保护
分段管理和分页管理的对比
分页对用户不可见，分段对用户可见
分页的地址是一维的，分段的地址是二维的
分段更容易实现信息的共享和保护
无快表的分页管理、分段管理访问一个逻辑地址都需要两次访存；分段存储中也可引入快表机构
地址转换
操作系统负责实现逻辑地址到物理地址的地址转换
三种装入方式下的地址转换情况
绝对装入：编译程序负责地址转换（单道程序阶段，无操作系统）
静态重定位装入：装入程序负责地址转换（早期多道批处理阶段）
动态重定位装入：运行时进行地址转换（现代操作系统）
存储保护
作用：保证各进程在各自的内存空间内运行，不会越界访问
两种方式
设置上下限寄存器
利用重定位寄存器、界地址寄存器进行判断
虚拟内存管理
传统存储管理方式的特征
一次性
作业必须一次性全部装入内存后才能开始运行，这会造成两个问题：1. 当作业所需内存空间很大而不能全部被装入内存时，该作业将无法运行；2. 当大量作业要运行时，由于内存不足以容纳所有作业，只能使少数作业先运行，着就导致了多道程序度下降
驻留性
作业被装入内存后就会一直驻留在内存中，且直至作业运行结束，作业的任何部分都不会被换出。运行中的进程可能会因等待I/O而被阻塞，而长期处于等待状态，使得效率下降
局部性原理
时间局部性
因为程序中存在大量循环，所以如果执行了程序中的某条指令，那么不久后这条指令可能会再次被执行；同理，如果某个数据被访问过，不久之后该数据可能会再次被访问
空间局部性
因为很多数据在内存中是连续存放的，所以一旦程序访问了某个存储单元，在不久之后，附近的存储单元也可能被访问
快表以及虚拟内存技术，从广义上讲，都属于高速缓存技术，这个技术所依赖的原理就是局部性原理
虚拟内存的定义和特征
定义
基于局部性原理，在程序装入时，只将程序的一部分装入内存，然后启动程序执行，其余的留在外存。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。
简言之，就是装入时只装一部分，能运行就行，运行过程中不够再装，暂时不用的换出
特征
多次性
无需在作业运行前一次性的全部装入内存，而是允许分为多次调入内存运行
对换性
无需在作业运行时一直常驻内存，而是允许在作业的运行过程中，可以换进和换出
虚拟性
从逻辑上扩充内存的容量，使用户所感受到的内存容量远大于实际的内存容量
虚拟内存的最大容量和实际容量
虚拟内存的最大容量：由计算机的地址结构（CPU寻址范围）确定
虚拟内存的实际容量：min（内存和外存之和，CPU寻址范围）
如何实现虚拟内存技术
采用连续分配方式还是非连续分配方式
如果采用连续分配方式，会使相当一部分内存空间处于暂时或“永久”的空闲状态，造成内存资源的浪费，而且也无法从逻辑上扩大内存容量。因此，虚拟内存的实现需要建立在离散分配的内存管理方式的基础上
三种实现方式
请求分页存储管理
建立在 基本分页系统 基础之上
与基本分页式存储管理的区别在于 在运行前无需将作业的所有程序都调入内存，详细来说分为以下两类
在程序的执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息由外存调入内存，然后继续执行程序；
请求调页（或调段）功能
若内存空间不足，则由操作系统负责将内存中暂时用不到的信息换出到外存
页面置换（或段置换）功能
为了实现请求分页必须有一定的硬件支持
一定容量的内存及外存
页表机制
页号
物理块号
和基本分页系统作用一样
状态位P
用于指示该页是否已经调入内存，供程序访问时参考
访问字段A
用于记录本页在一短时间内被访问的次数，或者记录本页最近已有多长时间未被访问，供置换算法换出页面时参考
修改位M
标识该页在调入内存后是否被修改过，供调出该页时参考
外存地址
用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考
缺页中断机构
发生缺页中断的条件
在请求分页系统中，每当所要访问的页面不在内存中时，便产生一个缺页中断
发生缺页中断后的操作
请求操作系统将所缺的页调入内存，将缺页的进程阻塞（调页完成唤醒），若内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中的相应页表项，若此时内存中没有空闲块，则要淘汰某页（若被淘汰的页在内存期间被修改过，则要将其写回内存）
与一般的中断的相同处和不同处
相同处
同样要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序、恢复CPU环境等几个步骤
不同处
在指令执行期间而非一条指令执行完后产生和处理中断信号，属于内部中断
一条指令在执行期间，可能产生多次缺页中断
地址变换机构
页面置换算法
基本概念
进程运行时，若其访问的页面不在内存中而需将其调入，但内存已无空闲空间，就需要从内存中调入一页程序或数据，送入磁盘的对换区，选择调出页面的算法就称为页面置换算法
好的页面置换算法应有较低的页面更换频率，也就是说，应将以后不会再访问或以后较长时间内不会再访问的页面先调出
4️种页面置换算法
最佳置换算法（OPT，Optimal）
无法实现
先进先出置换算法（FIFO）
最近最久未使用置换算法（LRU）
时钟置换算法（CLOCK）
改进型的时钟置换算法
页面分配策略
驻留集
定义
给一个进程分配的物理页框的集合就是这个进程的驻留集，在采用了虚拟存储技术的系统中，进程的驻留集大小一般小于该进程的总大小；相对的，没有采用虚拟存储技术的系统中，进程的驻留集的大小就等于进程的总大小
注意的点
分配给一个进程的存储量越小（驻留集越小），任何时候驻留在主寸中的进程数就越多，从而可以提高处理机的时间利用效率
若一个进程在主存中的页数过少，则尽管有局部性原理，页错误率仍然会相对较高
若一个进程在主存中的页数过多，给特定的进程分配更多的主存空间对该进程的错误率没有明显的影响
驻留集太大太小都不行，都会对系统的效率又不利的影响，所以选择合适的驻留集大小是关键
几个概念
分配方式
固定分配
操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变，即驻留集大小不变
可变分配
先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况作适当的增加或减少，即驻留集大小可变
置换方式
全局置换
只掠夺
可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程
局部置换
只是自给自足
发生缺页时只能选择自己的物理块进行置换
三种策略
固定分配局部置换
系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则可能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略的缺点是：很难在刚开始就确定应该为每个进程分配多少个物理块才算合理。（采用这种策略的系统可以根据进程大小、优先级、或者是根据程序员给出的参数来确定为一个进程分配的内存块数）
可变分配全局置换
刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程：若已无空闲物理块，则会选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页，都将获得新的物理块。仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择掉出的页可能是系统中任何一个进程的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。
可变分配局部置换
刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁的发生缺页，系统会为该进程多分配几个物理块，直至该进程的缺页率趋于适当程度；反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块
固定分配全局置换
❌，全部置换意味着掠夺，意味着扩张，所以驻留集的大小一定会改变，故全局置换情况下不可能是固定分配
在何时调入页面
预调页策略
运行前调入
根据局部性原理，一次调入若干相邻的页可能会比一次调入一页更高效。但如果调入的一批页面中大多数是未被访问的，则又是低效的。因此，需要采用以预测为基础的预调页策略，将预计在不久之后便会被访问的页面预先调入内存。但目前预调页的成功率仅约50%。因此这种策略主要用于进程的首次调入，由程序员指出应先调入那些页
请求调页策略
运行期间调入
进程在运行中需要访问的页面不在内存而提出请求，有系统将所需页面调入内存。由这种策略调入的页一定会被访问，且这种策略比较易于实现，因此在目前的虚拟存储器中大多采用此策略。它的缺点是每次只调入一页，调入/调出页面数多时会花费过多的I/O开销
一般会同时使用
从何处调入页面
请求分页系统中的外存分为
文件区
存放内容
存放文件
分配方式
连续分配方式
对换区
存放内容
存放对换页面
分配方式
离散分配方式
三种情况
系统区拥有足够的对换区空间
系统区缺少足够的对换区空间
UNIX方式
抖动
定义
页面频繁换入换出的现象
原因
分配给进程的物理块不够
工作集
定义
在某段时间间隔内，进程实际访问的页面的集合
和驻留集大小对比
驻留集的大小一般不能小于工作集大小
请求分段存储管理（略）
请求段页式存储管理（略）