第四章 存储 管理 (2)
第四章 存储器管理
4.4 分页存储管理
4.5 分段存储管理
4.6 交换与覆盖
4.7 虚拟存储器
4.8 请求分页存储管理方式第四章 存储器管理
4.4 分页存储管理
4.4.1 页式存储管理的引入
在 动态分区的存储空间中,存在,零头,问题 。 尽管采用,紧凑,技术可以解决这个问题,但要为移动大量信息花去不少的处理机时间,代价较高 。
分页,把用户程序按逻辑页划分成大小相等的部分,称为页 或虚页 。 从 0
开始编制页号,页内地址是相对于 0
编址 。
内存块
块,内存 按页的大小划分为大小相等的区域,称为内存块 （ 物理页面,页框 ）
内存 按页的大小划分为大小相等的区域，
称为内存块（物理页面，页框）。
内存分配：以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻,通过页表把作业的各个页面与页框对应起来。
4.4.2 页面与页表
1.页面和物理块分页存储管理,是将一个进程的逻辑地址空间分成若干个大小相等的片,称为页面或页,并为各页加以编号 。 相应地,也把内存空间分成与页面相同大小的若干个存储块,
称为 (物理 )块或页框 (frame),在为进程分配内存时,以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中 。 由于进程的最后一页经常装不满一块而形成了不可利用的碎片,称之为,页内碎片,。
2.页表
列 出了作业的逻辑地址与其在主存中的物理地址间的对应关系 。
页面大小,页面的大小应选择得适中,且页面大小应是 2的幂,通常为 512 B~8 KB
一个页表中包含若干个表目,表目的自然序号对应于用户程序中的页号,表目中的块号是该页对应的物理块号 。
页表的每一个表目除了包含指向页框的指针外,还包括一个存取控制字段 。
表目也称为页描述子 。
分页管理中页与页框的对应关系示意图
3,地址结构分页地址中的地址结构如下：
页号 P 位移量 W
31 12 11 0
对某特定机器,其地址结构是一定的 。 若给定一个逻辑地址空间中的地址为 A,页面的大小为 L,则页号 P和页内地址 d可按下式求得：
M O D LAd
L
A
INTP
][?
4.4.3 地址变换机构
1,基本的地址变换机构图 4-4-2分页系统的地址变换机构
2,地址变换过程
例如指令 LOAD 1,2500 的地址变换过程如下：
地址变换过程（续）
把虚拟地址 2500转换成页号 P=2,位移量 W=452；
如果页号 2大于页表大小,则中断；否则继续；
页号 2与页表起址 1000运算 （ 1000+2*20,设页描述子大小为 20） 得到页描述子地址为 1040；
从页描述子中读取块号 8；
根据页描述子的,存取控制,判断该指令是否被允许访问内存,如果不允许,则中断；否则继续；
块号 8与位移量 452运算 （ 8*1024+452=9644，
1024为页面大小 ） 得到物理地址 9644；
把数字 1写进内存地址 9644单元中 。
3.管 理
1)页表：系统为每个进程建立一个页表，
页表给出逻辑页号和具体内存块号相应的关系页表放在内存，属于进程的现场信息
2)空块管理 ——位示图
3)内存的分配与回收
0 31
0/10/10/10/10/10
1
7
……
空闲块数
……
空块管理 ——位示图内存的分配
计算一个作业所需要的总块数 N
查位示图，看看是否还有 N个空闲块
如果有足够的空闲块，则页表长度设为 N，可填入 PCB中；申请页表区，
把页表始址填入 PCB
依次分配 N个空闲块，将块号和页号填入页表
修改位示图
4.快表如果把页表放在主存中,无疑会影响系统的性能 。 这是因为每次访问主存,首先必须访问页表,读出页描述子,之后根据形成的实际地址再访问主存,这样使访问主存的次数加倍,因而使总的处理速度明显下降 。
为了解决这个问题人们采用一组硬件寄存器,
存放当前访问过的页的页描述子,
每次访问主存时,首先查找快表,若找到所需的页描述子,则快速形成物理地址 。 否则从页表中查找后形成物理地址,同时把页描述子写入快表 。 如果设计得当,快表的命中率可以很高 。
具有快表的地址变换机构图 4-4-3 具有快表的地址变换机构
4.4.4 两级和多级页表现代的大多数计算机系统,都支持非常大的逻辑地址空间 (232~264)。 页表就变得非常大,
要占用相当大的内存空间 。 可采用两个方法来解决这一问题,① 采用离散分配方式来解决难以找到一块连续的大内存空间的问题,②
只将当前需要的部分页表项调入内存,其余的页表项仍驻留在磁盘上,需要时再调入 。
1,两级页表逻辑地址结构可描述如下：
图 4-4-4 两级页表结构页目录地址目录位移 页表位移 页位移虚拟地址页表地址
.
.
.
页目录（每进程一个）
块号
.
.
.
页表代码或数据
.
.
.
内存块二级页表结构及地址映射
+
+
多级页表
32位 进程页表多大？
设：页面大小为 4K
用户空间 2GB
则：一个进程 219页设：每个内存块号 4字节则：进程页表 512页
结论：一个进程的页表的各页之间可以不连续存放
解决：页表本身使用地址索引 ——页目录第四章 存储器管理
4.5 分 段存储管理
4.5.1 分段式存储管理的引入在分页存储系统中,作业的地址空间是一维线性的,这破坏了程序内部天然的逻辑结构,造成共享,保护的困难 。 引入分段存储管理方式,主要是为了满足用户和程序员
1) 2) 信息共享
3) 信息保护 4)
5) 动态链接
...
0
S
工作区段 [B]
主程序段 [M]
...
...
0
E
P
子程序段 [X]
0
K
...
CALL [X] [E]
...
...
...CALL [Y] [F]
CALL [A] 116
...
...
0
F
L
子程序段 [Y]
0
116
N
数组 [A]
12345
...
4.5.2 分段系统的基本原理
1,分段分段地址中的地址具有如下结构：
段号 段内地址
31 16 15 0
2.段表它记录了段号，段的首（地）址和长度之间的关系每一个程序设置一个段表，放在内存,属于进程的现场信息段号
0
1
2
段首址 段长度
58K 20K
100K 110K
260K 140K
操作系统
.
.
.
.
.
B0S
A0N
Y0L
X0P
M0K
逻辑段号
0
1
2
3
4
作业 1的地址空间
1000
3200
5000
6000
8000
P
K
S
L
N
主存
K 3200
P 1500
L 6000
N 8000
S 5000
长度 段地址
0
1
2
3
4
操作系统分段管理中作业 i与段表、存储空间的关系
3,硬件支持
系统设置一对寄存器
段表始址寄存器：
用于保存正在运行进程的段表的始址
段表长度寄存器：
用于保存正在运行进程的段表的长度
（例如上图的段表长度为 3）
3,地址变换机构图 4-5-2 分段系统的地址变换过程
ClCb
+
段号 S 段内地址 d
比较比较
b + d
段 表
S>= Cl
快表物理地址段表始址寄存器 段表长度寄存器 逻辑地址
l b,,.
S l b
地址越界
d>=1
d>=1
地址映射及存储保护机制地址越界地址越界比较
4,分页和分段的主要区别
(1) 页是信息的物理单位,段则是信息的逻辑单位
(2) 页的大小固定且由系统决定，而段的长度却不固定
(3) 分页的作业地址空间是一维的，即单一的线性地址空间，分段的作业地址空间则是二维的
4.5.3 信息共享图 4-5-3 分页系统中共享 editor的示意图图 4-5-4 分段系统中共享 editor的示意图分段管理的优缺点优点：
便于动态申请内存管理和使用统一化便于共享便于动态链接缺点：产生碎片思考：与可变分区存储管理方案的相同点与不同点？
第四章 存储器管理
4.6 交换与覆盖
1,交换技术与覆盖技术
在多道环境下扩充内存的方法，
用以解决在较小的存储空间中运行较大程序时遇到的矛盾
覆盖技术主要用在早期的操作系统中
交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现
共同点：
进程的程序和数据主要放在外存，
当前需要执行的部分放在内存，
内外存之间进行信息交换
不同点：如何控制交换？
2,交换与覆盖异同点
3.覆盖技术
把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域
程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，
覆盖前面的程序段（内存“扩大”了）
覆盖：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间
一般要求作业各模块之间有明确的调用结构，
程序员要向系统指明覆盖结构，然后由由操作系统完成自动覆盖
对用户不透明，增加了用户负担
目前这一技术用于小型系统中的系统程序的内存管理上
MS-DOS的启动过程中，多次使用覆盖技术；启动之后，用户程序区
TPA的高端部分与 COMMAND.COM暂驻模块也是一种覆盖结构
4,覆盖技术的缺点
5,交换技术当内存空间紧张时，系统将内存中某些进程暂时移到外存，
把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度。多用于分时系统中
1.选择原则,将哪个进程换出 /内存？
2.交换时机的确定
3.交换时需要做哪些工作？
4.换入回内存时位置的确定
6,交换技术实现中的几个问题
将哪个进程换出 /内存？
例子：分时系统，时间片轮转法或基于优先数的调度算法，在选择换出进程时，要确定换出的进程是要长时间等待的
需要特殊考虑的是：任何等待 I/O进程中存在的问题
解决：从不换出处于等待 I/O状态的进程有些 I/O进程因 DMA而不能换出内存或换出前需要操作系统的特殊帮助
7,选择原则何时需发生交换？
例子：
只要不用就换出（很少再用）
只在内存空间不够或有不够的危险时换出
8,交换时机的确定需要一个盘交换区：必须足够大以存放所有用户程序的所有内存映像的拷贝；必须对这些内存映像的直接存取
9,交换时需要做哪些工作
换出后再换入的内存位置一定要在换出前的原来位置上吗？
受地址“绑定”技术的影响，即绝对地址产生时机的限制
10.换入回内存时位置的确定
与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构；而且，交换发生在进程或作业之间，
而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与覆盖段无关的程序段
11.覆盖与交换的比较第四章 存储器管理
4.7 虚拟存储器
1,概 述问题的提出,
程序大于内存
程序暂时不执行或运行完是否还要占用内存虚拟存储器的基本思想是：程序、数据、
堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换虚拟存储器支持多道程序设计技术
2,虚拟存储器
具有请求调入功能和自换功能,能从逻辑上对内存容量进行扩充的存储器系统 。 虚拟存储器就是一个地址空间,且具有比实存大得多的容量 。
虚拟存储器（续）
对用户：指令地址部分所限定的比实存大得多的地址实间 。
对系统：借助于各种表格机构,体现虚拟实间 。
3,虚拟存储连续性 离散性驻留性 交换性一次性 多次性以 CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术
CPU
MMU
内存 磁盘控制器总线虚拟地址物理地址MMU：内存管理单元
X
X
X
X
7
X
5
X
X
X
3
4
0
6
1
2
60K-64K
56K-60K
52K-56K
48K-52K
44K-48K
40K-44K
36K-40K
32K-36K
28K-32K
24K-28K
20K-24K
16K-20K
12K-16K
8K-12K
4K-8K
0K-4K
28K-32K
24K-28K
20K-24K
16K-20K
12K-16K
8K-12K
4K-8K
0K-4K
虚地址空间物理地址空间
} 虚页页框
1514
13
12
11
10
9
8
7
6
5
4
3
2
1
000 0
000 0
000 0
000 0
111 1
000 0
101 1
000 0
000 0
000 0
011 1
100 1
000 1
110 1
001 1
010 10
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
110
在 /不在内存页表虚地址
8196
物理地址
24580
4,虚拟存储器的容量
一个虚拟存储器的最大容量是由计算机的地址结构确定的 。 如：若 CPU的有效地址长度为 32位,则程序可以寻址范围是
0～ (2^32)-1,即虚存容量为 4GB。
虚拟存储器的容量与主存的实际大小没有直接的关系,而是由主存与辅存的容量之和所确定 。
程序局部性原理在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面
时间局部性：
一条指令被执行了，则在不久的将来它可能再被执行
空间局部性：
若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用
5,局部性原理
6,虚拟存储技术虚存：把内存与外存有机的结合起来使用，从而得到一个容量很大的,内存,,这就是虚存实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作目的：提高内存利用率第四章 存储器管理
4.8 请求分页存储管理一,请求式分页存储管理请求式分页也称虚拟页式存储管理与 纯分页存储管理不同，请求式分页管理系统在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面
1.需要解决的问题系统需要解决下面三个问题：
系统如何获知进程当前所需页面不在主存。
当发现缺页时，如何把所缺页面调入主存。
当主存中没有空闲的页框时，为了要接受一个新页，需要 把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。
2,页描述子的扩充页号、驻留位、内存块号、外存地址、访问位、
修改位、（存取控制、辅存地址）
中断位：表示该页是在内存还是在外存
访问位：表示该页最近被访问过,根据访问位来决定淘汰哪页
修改位：查看此页是否在内存中被修改过页号 中断位 内存块号 外存地址 访问位 修改位
3.地址变换与缺页中断查页表时,当存在位指示该页不在主存时,则引起一个缺页中断发生,相应的中断处理程序把控制转向缺页中断子程序 。 执行此子程序,即把所缺页面装入主存 。 然后处理机重新执行缺页时打断的指令 。 这时,就将顺利形成物理地址 。 如下图所示 。
4.请求分页存储管理地址变换流程二,页面置换算法当要放一页面到全满的主存块时,系统需淘汰一页 。 用来选取淘汰哪一页的规则,叫置换算法 。
最佳置换算法
先进先出置换算法
最近最久未用置换算法
近似的 LRU算法 （ NRU算法 ）
1.最佳置换算法最佳置换算法是由 Belady于 1966年提出的一种理论上的算法 。 其所选择的被淘汰页面,将是以后永不使用的,或许是在最长 (未来 )时间内不再被访问的页面 。
采用最佳置换算法,通常可保证获得最低的缺页率 。
假定系统为某进程分配了三个物理块,并考虑有以下
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
进程运行时,先将 7,0,1三个页面装入内存 。 以后,
当进程要访问页面 2时,将会产生缺页中断 。 此时 OS根据最佳置换算法,将选择页面 7予以淘汰 。
利用最佳页面置换算法时的置换图
2,先进先出 (FIFO)页面置换算法利用 FIFO置换算法时的置换图置换时 选择在内存中驻留时间最长的页并淘汰之
3,最近最久未使用 (LRU)置换算法
LRU页面置换算法选择最后一次访问时间距离当前时间最长的一页并淘汰之。即淘汰没有使用的时间最长的页。实现代价很高（时间戳或硬件方法）
LRU置换算法的硬件支持
1) 寄存器为了记录某进程在内存中各页的使用情况,须为每个在内存中的页面配置一个移位寄存器,可表示为,R=Rn-1Rn-
2Rn-3 … R2R1R0
某进程具有 8个页面时的 LRU访问情况
2) 栈用栈保存当前使用页面时栈的变化情况
4,Clock置换算法
1) 简单的 Clock置换算法 (近似的 LRU算法）
简单 Clock置换算法的流程和示例
2) 改进型 Clock置换算法由访问位 A和修改位 M可以组合成下面四种类型的页面：
1类 (A=0,M=0),表示该页最近既未被访问,又未被修改,
是最佳淘汰页 。
2类 (A=0,M=1),表示该页最近未被访问,但已被修改,
并不是很好的淘汰页 。
3类 (A=1,M=0),最近已被访问,但未被修改,该页有可能再被访问 。
4类 (A=1,M=1),最近已被访问且被修改,该页可能再被访问。
(1) 从指针所指示的当前位置开始,扫描循环队列,寻找 A=0且 M=0的第一类页面,将所遇到的第一个页面作为所选中的淘汰页 。 在第一次扫描期间不改变访问位 A。
(2) 如果第一步失败,即查找一周后未遇到第一类页面,
则开始第二轮扫描,寻找 A=0且 M=1的第二类页面,将所遇到的第一个这类页面作为淘汰页 。 在第二轮扫描期间,将所有扫描过的页面的访问位都置 0。
(3) 如果第二步也失败,亦即未找到第二类页面,则将指针返回到开始的位置,并将所有的访问位复 0。 然后重复第一步,如果仍失败,必要时再重复第二步,此时就一定能找到被淘汰的页 。
5,其它置换算法
1,最少使用 (LFU,Least Frequently Used)置换算法
2,页面缓冲算法 (PBA,Page Buffering Algorithm)
缺页中断（ Page Fault）
在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去
如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号
若此时内存中没有空闲块，则要淘汰某页，
若该页在内存期间被修改过，则要将其写回外存影响缺页次数的因素
(1) 分配给进程的物理页面数
(2) 页面本身的大小
(3) 程序的编制方法
(4) 页面淘汰算法性能问题颠簸（抖动）,
在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动原因：
页面淘汰算法不合理
分配给进程的物理页面数太少工作集（ Working Set）模型
基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断
如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数
对于给定的访问序列选取定长的区间，称为工作集窗口，落在工作集窗口中的页面集合称为工作集页面共享对于数据页面工共享,可以安排在诸作业地址空间中的任何一个页面上 。 至于库例程的共享则不然,
它必须把共享的例程,安排到所有共享它的作业地址空间中相同的页面中,即共享例程所在的地址空间必须重叠 。 如下图所示 。
页面共享实现页面共享的问题实现页面共享引起的主要问题是,当共享页从主存中淘汰或被重新装入主存时,共享此页的所有作业页表中的相应,页面存在,位都必须更新 。 具体实现时采用如下技术：
实现页面共享的问题（续）
为那些被共享的页面独立设置一张页表 —— 公共页表,当某个被共享的页面与辅存之间交换时,中需对这个公共页表的表目加以更新,至于有共享页面的作业之页表,其相应表目设有一指针,指向该页在公共页表的表目即可 。
总之,实现页面共享,必须使共享的页面具有相同的页号,或者要在地址之间重叠,这将带来麻烦 。 因此分页不利于共享 。 这可以在分段存储管理中得到改进 。
页面尺寸
TLB的大小、位置、访问方式
局部与全局分配策略
装入策略 与 清除策略
负载控制
多级页表其他有关设计问题快表 TLB
为加快地址映射速度，改善系统性能
采用联想映射技术同时查找
置于 MMU（ Memory Management Unit）中
大小：
– Intel 80x86/Pentium,32项
– SGI MIPS R4000,48项
命中率（在 TLB中发现一个页面的百分比）
TLB的两种访问方式：
– 软件访问
– 硬件访问局部与全局分配策略
分配给一个进程多少页面？
– 固定数目分配 与 可变数目分配
置换范围
– 全局 与 局部三种组合：固定 + 局部可变 + 全局固定 + 全局页面装入策略与清除策略
装入方式
–请求调页
–预先调页
清除方式
–请求
–预先
第四章 存储器管理
4.4 分页存储管理
4.5 分段存储管理
4.6 交换与覆盖
4.7 虚拟存储器
4.8 请求分页存储管理方式第四章 存储器管理
4.4 分页存储管理
4.4.1 页式存储管理的引入
在 动态分区的存储空间中,存在,零头,问题 。 尽管采用,紧凑,技术可以解决这个问题,但要为移动大量信息花去不少的处理机时间,代价较高 。
分页,把用户程序按逻辑页划分成大小相等的部分,称为页 或虚页 。 从 0
开始编制页号,页内地址是相对于 0
编址 。
内存块
块,内存 按页的大小划分为大小相等的区域,称为内存块 （ 物理页面,页框 ）
内存 按页的大小划分为大小相等的区域，
称为内存块（物理页面，页框）。
内存分配：以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻,通过页表把作业的各个页面与页框对应起来。
4.4.2 页面与页表
1.页面和物理块分页存储管理,是将一个进程的逻辑地址空间分成若干个大小相等的片,称为页面或页,并为各页加以编号 。 相应地,也把内存空间分成与页面相同大小的若干个存储块,
称为 (物理 )块或页框 (frame),在为进程分配内存时,以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中 。 由于进程的最后一页经常装不满一块而形成了不可利用的碎片,称之为,页内碎片,。
2.页表
列 出了作业的逻辑地址与其在主存中的物理地址间的对应关系 。
页面大小,页面的大小应选择得适中,且页面大小应是 2的幂,通常为 512 B~8 KB
一个页表中包含若干个表目,表目的自然序号对应于用户程序中的页号,表目中的块号是该页对应的物理块号 。
页表的每一个表目除了包含指向页框的指针外,还包括一个存取控制字段 。
表目也称为页描述子 。
分页管理中页与页框的对应关系示意图
3,地址结构分页地址中的地址结构如下：
页号 P 位移量 W
31 12 11 0
对某特定机器,其地址结构是一定的 。 若给定一个逻辑地址空间中的地址为 A,页面的大小为 L,则页号 P和页内地址 d可按下式求得：
M O D LAd
L
A
INTP
][?
4.4.3 地址变换机构
1,基本的地址变换机构图 4-4-2分页系统的地址变换机构
2,地址变换过程
例如指令 LOAD 1,2500 的地址变换过程如下：
地址变换过程（续）
把虚拟地址 2500转换成页号 P=2,位移量 W=452；
如果页号 2大于页表大小,则中断；否则继续；
页号 2与页表起址 1000运算 （ 1000+2*20,设页描述子大小为 20） 得到页描述子地址为 1040；
从页描述子中读取块号 8；
根据页描述子的,存取控制,判断该指令是否被允许访问内存,如果不允许,则中断；否则继续；
块号 8与位移量 452运算 （ 8*1024+452=9644，
1024为页面大小 ） 得到物理地址 9644；
把数字 1写进内存地址 9644单元中 。
3.管 理
1)页表：系统为每个进程建立一个页表，
页表给出逻辑页号和具体内存块号相应的关系页表放在内存，属于进程的现场信息
2)空块管理 ——位示图
3)内存的分配与回收
0 31
0/10/10/10/10/10
1
7
……
空闲块数
……
空块管理 ——位示图内存的分配
计算一个作业所需要的总块数 N
查位示图，看看是否还有 N个空闲块
如果有足够的空闲块，则页表长度设为 N，可填入 PCB中；申请页表区，
把页表始址填入 PCB
依次分配 N个空闲块，将块号和页号填入页表
修改位示图
4.快表如果把页表放在主存中,无疑会影响系统的性能 。 这是因为每次访问主存,首先必须访问页表,读出页描述子,之后根据形成的实际地址再访问主存,这样使访问主存的次数加倍,因而使总的处理速度明显下降 。
为了解决这个问题人们采用一组硬件寄存器,
存放当前访问过的页的页描述子,
每次访问主存时,首先查找快表,若找到所需的页描述子,则快速形成物理地址 。 否则从页表中查找后形成物理地址,同时把页描述子写入快表 。 如果设计得当,快表的命中率可以很高 。
具有快表的地址变换机构图 4-4-3 具有快表的地址变换机构
4.4.4 两级和多级页表现代的大多数计算机系统,都支持非常大的逻辑地址空间 (232~264)。 页表就变得非常大,
要占用相当大的内存空间 。 可采用两个方法来解决这一问题,① 采用离散分配方式来解决难以找到一块连续的大内存空间的问题,②
只将当前需要的部分页表项调入内存,其余的页表项仍驻留在磁盘上,需要时再调入 。
1,两级页表逻辑地址结构可描述如下：
图 4-4-4 两级页表结构页目录地址目录位移 页表位移 页位移虚拟地址页表地址
.
.
.
页目录（每进程一个）
块号
.
.
.
页表代码或数据
.
.
.
内存块二级页表结构及地址映射
+
+
多级页表
32位 进程页表多大？
设：页面大小为 4K
用户空间 2GB
则：一个进程 219页设：每个内存块号 4字节则：进程页表 512页
结论：一个进程的页表的各页之间可以不连续存放
解决：页表本身使用地址索引 ——页目录第四章 存储器管理
4.5 分 段存储管理
4.5.1 分段式存储管理的引入在分页存储系统中,作业的地址空间是一维线性的,这破坏了程序内部天然的逻辑结构,造成共享,保护的困难 。 引入分段存储管理方式,主要是为了满足用户和程序员
1) 2) 信息共享
3) 信息保护 4)
5) 动态链接
...
0
S
工作区段 [B]
主程序段 [M]
...
...
0
E
P
子程序段 [X]
0
K
...
CALL [X] [E]
...
...
...CALL [Y] [F]
CALL [A] 116
...
...
0
F
L
子程序段 [Y]
0
116
N
数组 [A]
12345
...
4.5.2 分段系统的基本原理
1,分段分段地址中的地址具有如下结构：
段号 段内地址
31 16 15 0
2.段表它记录了段号，段的首（地）址和长度之间的关系每一个程序设置一个段表，放在内存,属于进程的现场信息段号
0
1
2
段首址 段长度
58K 20K
100K 110K
260K 140K
操作系统
.
.
.
.
.
B0S
A0N
Y0L
X0P
M0K
逻辑段号
0
1
2
3
4
作业 1的地址空间
1000
3200
5000
6000
8000
P
K
S
L
N
主存
K 3200
P 1500
L 6000
N 8000
S 5000
长度 段地址
0
1
2
3
4
操作系统分段管理中作业 i与段表、存储空间的关系
3,硬件支持
系统设置一对寄存器
段表始址寄存器：
用于保存正在运行进程的段表的始址
段表长度寄存器：
用于保存正在运行进程的段表的长度
（例如上图的段表长度为 3）
3,地址变换机构图 4-5-2 分段系统的地址变换过程
ClCb
+
段号 S 段内地址 d
比较比较
b + d
段 表
S>= Cl
快表物理地址段表始址寄存器 段表长度寄存器 逻辑地址
l b,,.
S l b
地址越界
d>=1
d>=1
地址映射及存储保护机制地址越界地址越界比较
4,分页和分段的主要区别
(1) 页是信息的物理单位,段则是信息的逻辑单位
(2) 页的大小固定且由系统决定，而段的长度却不固定
(3) 分页的作业地址空间是一维的，即单一的线性地址空间，分段的作业地址空间则是二维的
4.5.3 信息共享图 4-5-3 分页系统中共享 editor的示意图图 4-5-4 分段系统中共享 editor的示意图分段管理的优缺点优点：
便于动态申请内存管理和使用统一化便于共享便于动态链接缺点：产生碎片思考：与可变分区存储管理方案的相同点与不同点？
第四章 存储器管理
4.6 交换与覆盖
1,交换技术与覆盖技术
在多道环境下扩充内存的方法，
用以解决在较小的存储空间中运行较大程序时遇到的矛盾
覆盖技术主要用在早期的操作系统中
交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现
共同点：
进程的程序和数据主要放在外存，
当前需要执行的部分放在内存，
内外存之间进行信息交换
不同点：如何控制交换？
2,交换与覆盖异同点
3.覆盖技术
把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域
程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，
覆盖前面的程序段（内存“扩大”了）
覆盖：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间
一般要求作业各模块之间有明确的调用结构，
程序员要向系统指明覆盖结构，然后由由操作系统完成自动覆盖
对用户不透明，增加了用户负担
目前这一技术用于小型系统中的系统程序的内存管理上
MS-DOS的启动过程中，多次使用覆盖技术；启动之后，用户程序区
TPA的高端部分与 COMMAND.COM暂驻模块也是一种覆盖结构
4,覆盖技术的缺点
5,交换技术当内存空间紧张时，系统将内存中某些进程暂时移到外存，
把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度。多用于分时系统中
1.选择原则,将哪个进程换出 /内存？
2.交换时机的确定
3.交换时需要做哪些工作？
4.换入回内存时位置的确定
6,交换技术实现中的几个问题
将哪个进程换出 /内存？
例子：分时系统，时间片轮转法或基于优先数的调度算法，在选择换出进程时，要确定换出的进程是要长时间等待的
需要特殊考虑的是：任何等待 I/O进程中存在的问题
解决：从不换出处于等待 I/O状态的进程有些 I/O进程因 DMA而不能换出内存或换出前需要操作系统的特殊帮助
7,选择原则何时需发生交换？
例子：
只要不用就换出（很少再用）
只在内存空间不够或有不够的危险时换出
8,交换时机的确定需要一个盘交换区：必须足够大以存放所有用户程序的所有内存映像的拷贝；必须对这些内存映像的直接存取
9,交换时需要做哪些工作
换出后再换入的内存位置一定要在换出前的原来位置上吗？
受地址“绑定”技术的影响，即绝对地址产生时机的限制
10.换入回内存时位置的确定
与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构；而且，交换发生在进程或作业之间，
而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与覆盖段无关的程序段
11.覆盖与交换的比较第四章 存储器管理
4.7 虚拟存储器
1,概 述问题的提出,
程序大于内存
程序暂时不执行或运行完是否还要占用内存虚拟存储器的基本思想是：程序、数据、
堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换虚拟存储器支持多道程序设计技术
2,虚拟存储器
具有请求调入功能和自换功能,能从逻辑上对内存容量进行扩充的存储器系统 。 虚拟存储器就是一个地址空间,且具有比实存大得多的容量 。
虚拟存储器（续）
对用户：指令地址部分所限定的比实存大得多的地址实间 。
对系统：借助于各种表格机构,体现虚拟实间 。
3,虚拟存储连续性 离散性驻留性 交换性一次性 多次性以 CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术
CPU
MMU
内存 磁盘控制器总线虚拟地址物理地址MMU：内存管理单元
X
X
X
X
7
X
5
X
X
X
3
4
0
6
1
2
60K-64K
56K-60K
52K-56K
48K-52K
44K-48K
40K-44K
36K-40K
32K-36K
28K-32K
24K-28K
20K-24K
16K-20K
12K-16K
8K-12K
4K-8K
0K-4K
28K-32K
24K-28K
20K-24K
16K-20K
12K-16K
8K-12K
4K-8K
0K-4K
虚地址空间物理地址空间
} 虚页页框
1514
13
12
11
10
9
8
7
6
5
4
3
2
1
000 0
000 0
000 0
000 0
111 1
000 0
101 1
000 0
000 0
000 0
011 1
100 1
000 1
110 1
001 1
010 10
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 0 0 0 1 0 0
110
在 /不在内存页表虚地址
8196
物理地址
24580
4,虚拟存储器的容量
一个虚拟存储器的最大容量是由计算机的地址结构确定的 。 如：若 CPU的有效地址长度为 32位,则程序可以寻址范围是
0～ (2^32)-1,即虚存容量为 4GB。
虚拟存储器的容量与主存的实际大小没有直接的关系,而是由主存与辅存的容量之和所确定 。
程序局部性原理在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面
时间局部性：
一条指令被执行了，则在不久的将来它可能再被执行
空间局部性：
若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用
5,局部性原理
6,虚拟存储技术虚存：把内存与外存有机的结合起来使用，从而得到一个容量很大的,内存,,这就是虚存实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作目的：提高内存利用率第四章 存储器管理
4.8 请求分页存储管理一,请求式分页存储管理请求式分页也称虚拟页式存储管理与 纯分页存储管理不同，请求式分页管理系统在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面
1.需要解决的问题系统需要解决下面三个问题：
系统如何获知进程当前所需页面不在主存。
当发现缺页时，如何把所缺页面调入主存。
当主存中没有空闲的页框时，为了要接受一个新页，需要 把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。
2,页描述子的扩充页号、驻留位、内存块号、外存地址、访问位、
修改位、（存取控制、辅存地址）
中断位：表示该页是在内存还是在外存
访问位：表示该页最近被访问过,根据访问位来决定淘汰哪页
修改位：查看此页是否在内存中被修改过页号 中断位 内存块号 外存地址 访问位 修改位
3.地址变换与缺页中断查页表时,当存在位指示该页不在主存时,则引起一个缺页中断发生,相应的中断处理程序把控制转向缺页中断子程序 。 执行此子程序,即把所缺页面装入主存 。 然后处理机重新执行缺页时打断的指令 。 这时,就将顺利形成物理地址 。 如下图所示 。
4.请求分页存储管理地址变换流程二,页面置换算法当要放一页面到全满的主存块时,系统需淘汰一页 。 用来选取淘汰哪一页的规则,叫置换算法 。
最佳置换算法
先进先出置换算法
最近最久未用置换算法
近似的 LRU算法 （ NRU算法 ）
1.最佳置换算法最佳置换算法是由 Belady于 1966年提出的一种理论上的算法 。 其所选择的被淘汰页面,将是以后永不使用的,或许是在最长 (未来 )时间内不再被访问的页面 。
采用最佳置换算法,通常可保证获得最低的缺页率 。
假定系统为某进程分配了三个物理块,并考虑有以下
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
进程运行时,先将 7,0,1三个页面装入内存 。 以后,
当进程要访问页面 2时,将会产生缺页中断 。 此时 OS根据最佳置换算法,将选择页面 7予以淘汰 。
利用最佳页面置换算法时的置换图
2,先进先出 (FIFO)页面置换算法利用 FIFO置换算法时的置换图置换时 选择在内存中驻留时间最长的页并淘汰之
3,最近最久未使用 (LRU)置换算法
LRU页面置换算法选择最后一次访问时间距离当前时间最长的一页并淘汰之。即淘汰没有使用的时间最长的页。实现代价很高（时间戳或硬件方法）
LRU置换算法的硬件支持
1) 寄存器为了记录某进程在内存中各页的使用情况,须为每个在内存中的页面配置一个移位寄存器,可表示为,R=Rn-1Rn-
2Rn-3 … R2R1R0
某进程具有 8个页面时的 LRU访问情况
2) 栈用栈保存当前使用页面时栈的变化情况
4,Clock置换算法
1) 简单的 Clock置换算法 (近似的 LRU算法）
简单 Clock置换算法的流程和示例
2) 改进型 Clock置换算法由访问位 A和修改位 M可以组合成下面四种类型的页面：
1类 (A=0,M=0),表示该页最近既未被访问,又未被修改,
是最佳淘汰页 。
2类 (A=0,M=1),表示该页最近未被访问,但已被修改,
并不是很好的淘汰页 。
3类 (A=1,M=0),最近已被访问,但未被修改,该页有可能再被访问 。
4类 (A=1,M=1),最近已被访问且被修改,该页可能再被访问。
(1) 从指针所指示的当前位置开始,扫描循环队列,寻找 A=0且 M=0的第一类页面,将所遇到的第一个页面作为所选中的淘汰页 。 在第一次扫描期间不改变访问位 A。
(2) 如果第一步失败,即查找一周后未遇到第一类页面,
则开始第二轮扫描,寻找 A=0且 M=1的第二类页面,将所遇到的第一个这类页面作为淘汰页 。 在第二轮扫描期间,将所有扫描过的页面的访问位都置 0。
(3) 如果第二步也失败,亦即未找到第二类页面,则将指针返回到开始的位置,并将所有的访问位复 0。 然后重复第一步,如果仍失败,必要时再重复第二步,此时就一定能找到被淘汰的页 。
5,其它置换算法
1,最少使用 (LFU,Least Frequently Used)置换算法
2,页面缓冲算法 (PBA,Page Buffering Algorithm)
缺页中断（ Page Fault）
在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去
如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号
若此时内存中没有空闲块，则要淘汰某页，
若该页在内存期间被修改过，则要将其写回外存影响缺页次数的因素
(1) 分配给进程的物理页面数
(2) 页面本身的大小
(3) 程序的编制方法
(4) 页面淘汰算法性能问题颠簸（抖动）,
在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动原因：
页面淘汰算法不合理
分配给进程的物理页面数太少工作集（ Working Set）模型
基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断
如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数
对于给定的访问序列选取定长的区间，称为工作集窗口，落在工作集窗口中的页面集合称为工作集页面共享对于数据页面工共享,可以安排在诸作业地址空间中的任何一个页面上 。 至于库例程的共享则不然,
它必须把共享的例程,安排到所有共享它的作业地址空间中相同的页面中,即共享例程所在的地址空间必须重叠 。 如下图所示 。
页面共享实现页面共享的问题实现页面共享引起的主要问题是,当共享页从主存中淘汰或被重新装入主存时,共享此页的所有作业页表中的相应,页面存在,位都必须更新 。 具体实现时采用如下技术：
实现页面共享的问题（续）
为那些被共享的页面独立设置一张页表 —— 公共页表,当某个被共享的页面与辅存之间交换时,中需对这个公共页表的表目加以更新,至于有共享页面的作业之页表,其相应表目设有一指针,指向该页在公共页表的表目即可 。
总之,实现页面共享,必须使共享的页面具有相同的页号,或者要在地址之间重叠,这将带来麻烦 。 因此分页不利于共享 。 这可以在分段存储管理中得到改进 。
页面尺寸
TLB的大小、位置、访问方式
局部与全局分配策略
装入策略 与 清除策略
负载控制
多级页表其他有关设计问题快表 TLB
为加快地址映射速度，改善系统性能
采用联想映射技术同时查找
置于 MMU（ Memory Management Unit）中
大小：
– Intel 80x86/Pentium,32项
– SGI MIPS R4000,48项
命中率（在 TLB中发现一个页面的百分比）
TLB的两种访问方式：
– 软件访问
– 硬件访问局部与全局分配策略
分配给一个进程多少页面？
– 固定数目分配 与 可变数目分配
置换范围
– 全局 与 局部三种组合：固定 + 局部可变 + 全局固定 + 全局页面装入策略与清除策略
装入方式
–请求调页
–预先调页
清除方式
–请求
–预先
